idlist64.c
Go to the documentation of this file.00001
00002
00003
00004
00005
00006
00007
00008
00009
00010
00011
00012
00013
00014
00015
00016
00017
00018
00019
00020
00021
00022
00023
00024
00025
00026
00027
00028
00029
00030 #ifdef HAVE_CONFIG_H
00031 # include <config.h>
00032 #endif
00033
00034
00035 #include "idlist64_p.h"
00036 #include <gwenhywfar/debug.h>
00037
00038
00039 #include <stdlib.h>
00040 #include <assert.h>
00041 #include <string.h>
00042
00043
00044 GWEN_LIST_FUNCTIONS(GWEN_IDTABLE64, GWEN_IdTable64)
00045
00046
00047
00048
00049 GWEN_IDTABLE64 *GWEN_IdTable64_new(){
00050 GWEN_IDTABLE64 *idt;
00051
00052 GWEN_NEW_OBJECT(GWEN_IDTABLE64, idt);
00053 idt->refCount=1;
00054 GWEN_LIST_INIT(GWEN_IDTABLE64, idt);
00055
00056 idt->freeEntries=GWEN_IDTABLE64_MAXENTRIES;
00057 return idt;
00058 }
00059
00060
00061
00062 void GWEN_IdTable64_free(GWEN_IDTABLE64 *idt){
00063 if (idt) {
00064 assert(idt->refCount);
00065 if (--(idt->refCount)==0) {
00066 GWEN_LIST_FINI(GWEN_IDTABLE64, idt);
00067 GWEN_FREE_OBJECT(idt);
00068 }
00069 }
00070 }
00071
00072
00073
00074 void GWEN_IdTable64_Attach(GWEN_IDTABLE64 *idt){
00075 assert(idt);
00076 assert(idt->refCount);
00077 idt->refCount++;
00078 }
00079
00080
00081
00082 static inline int GWEN_IdTable64_AddId(GWEN_IDTABLE64 *idt, uint64_t id){
00083 unsigned int i;
00084
00085 for (i=0; i<GWEN_IDTABLE64_MAXENTRIES; i++) {
00086 if (idt->entries[i]==0) {
00087 idt->entries[i]=id;
00088 idt->freeEntries--;
00089 return 0;
00090 }
00091 }
00092 return -1;
00093 }
00094
00095
00096
00097 static inline int GWEN_IdTable64_AppendId(GWEN_IDTABLE64 *idt, uint64_t id){
00098 if (idt->freeEntries) {
00099 unsigned int i;
00100
00101 i=GWEN_IDTABLE64_MAXENTRIES-idt->freeEntries;
00102 idt->entries[i]=id;
00103 idt->freeEntries--;
00104 return 0;
00105 }
00106 else
00107 return -1;
00108 }
00109
00110
00111
00112 static inline int GWEN_IdTable64_HasId(const GWEN_IDTABLE64 *idt, uint64_t id){
00113 unsigned int i;
00114
00115 for (i=0; i<GWEN_IDTABLE64_MAXENTRIES; i++) {
00116 if (idt->entries[i]==id) {
00117 return 1;
00118 }
00119 }
00120 return 0;
00121 }
00122
00123
00124
00125 static inline int GWEN_IdTable64_DelId(GWEN_IDTABLE64 *idt, uint64_t id){
00126 unsigned int i;
00127
00128 for (i=0; i<GWEN_IDTABLE64_MAXENTRIES; i++) {
00129 if (idt->entries[i]==id) {
00130 idt->entries[i]=0;
00131 idt->freeEntries++;
00132 return 0;
00133 }
00134 }
00135 return -1;
00136 }
00137
00138
00139
00140 static inline int GWEN_IdTable64_IsEmpty(const GWEN_IDTABLE64 *idt){
00141 return GWEN_IDTABLE64_MAXENTRIES==idt->freeEntries;
00142 }
00143
00144
00145
00146 static inline int GWEN_IdTable64_IsFull(const GWEN_IDTABLE64 *idt){
00147 return idt->freeEntries==0;
00148 }
00149
00150
00151
00152 static inline unsigned int GWEN_IdTable64_GetCount(const GWEN_IDTABLE64 *idt){
00153 return GWEN_IDTABLE64_MAXENTRIES-idt->freeEntries;
00154 }
00155
00156
00157
00158 static inline uint64_t GWEN_IdTable64_GetFirstId(GWEN_IDTABLE64 *idt){
00159 unsigned int i;
00160
00161 assert(idt);
00162 idt->current=0;
00163 for (i=0; i<GWEN_IDTABLE64_MAXENTRIES; i++) {
00164 if (idt->entries[i]!=0) {
00165 idt->current=i;
00166 return idt->entries[i];
00167 }
00168 }
00169 return 0;
00170 }
00171
00172
00173
00174 static inline uint64_t GWEN_IdTable64_GetNextId(GWEN_IDTABLE64 *idt){
00175 unsigned int i;
00176
00177 for (i=idt->current+1; i<GWEN_IDTABLE64_MAXENTRIES; i++) {
00178 if (idt->entries[i]!=0) {
00179 idt->current=i;
00180 return idt->entries[i];
00181 }
00182 }
00183 idt->current=GWEN_IDTABLE64_MAXENTRIES;
00184 return 0;
00185 }
00186
00187
00188
00189 static inline uint64_t GWEN_IdTable64_GetFirstId2(const GWEN_IDTABLE64 *idt,
00190 uint64_t *tabIdx){
00191 unsigned int i;
00192
00193 for (i=0; i<GWEN_IDTABLE64_MAXENTRIES; i++) {
00194 if (idt->entries[i]!=0) {
00195 *tabIdx=i;
00196 return idt->entries[i];
00197 }
00198 }
00199 return 0;
00200 }
00201
00202
00203
00204 static inline uint64_t GWEN_IdTable64_GetNextId2(const GWEN_IDTABLE64 *idt,
00205 uint64_t *tabIdx){
00206 unsigned int i;
00207
00208 for (i=(*tabIdx)+1; i<GWEN_IDTABLE64_MAXENTRIES; i++) {
00209 if (idt->entries[i]!=0) {
00210 *tabIdx=i;
00211 return idt->entries[i];
00212 }
00213 }
00214 return 0;
00215 }
00216
00217
00218
00219
00220
00221
00222 GWEN_IDLIST64 *GWEN_IdList64_new(){
00223 GWEN_IDLIST64 *idl;
00224
00225 GWEN_NEW_OBJECT(GWEN_IDLIST64, idl);
00226 idl->refCount=1;
00227 idl->idTables=GWEN_IdTable64_List_new();
00228 return idl;
00229 }
00230
00231
00232
00233 void GWEN_IdList64_Attach(GWEN_IDLIST64 *idl) {
00234 assert(idl);
00235 assert(idl->refCount);
00236 idl->refCount++;
00237 }
00238
00239
00240
00241 void GWEN_IdList64_free(GWEN_IDLIST64 *idl){
00242 if (idl) {
00243 assert(idl->refCount);
00244 if (--(idl->refCount)==0) {
00245 GWEN_IdTable64_List_free(idl->idTables);
00246 GWEN_FREE_OBJECT(idl);
00247 }
00248 }
00249 }
00250
00251
00252
00253 int GWEN_IdList64_AddId(GWEN_IDLIST64 *idl, uint64_t id){
00254 GWEN_IDTABLE64 *idt;
00255
00256 assert(idl);
00257
00258 idl->current=0;
00259 idt=GWEN_IdTable64_List_First(idl->idTables);
00260
00261 while(idt) {
00262 if (!GWEN_IdTable64_IsFull(idt))
00263 break;
00264 idt=GWEN_IdTable64_List_Next(idt);
00265 }
00266
00267 if (!idt) {
00268 idt=GWEN_IdTable64_new();
00269 GWEN_IdTable64_List_Add(idt, idl->idTables);;
00270 }
00271
00272 GWEN_IdTable64_AddId(idt, id);
00273 idl->entryCount++;
00274 return 0;
00275 }
00276
00277
00278
00279 int GWEN_IdList64_DelId(GWEN_IDLIST64 *idl, uint64_t id){
00280 GWEN_IDTABLE64 *idt;
00281
00282 assert(idl);
00283
00284 idl->current=0;
00285 idt=GWEN_IdTable64_List_First(idl->idTables);
00286
00287 while(idt) {
00288 if (!GWEN_IdTable64_DelId(idt, id)) {
00289
00290 GWEN_IdList64_Clean(idl);
00291 idl->entryCount--;
00292 return 0;
00293 }
00294 idt=GWEN_IdTable64_List_Next(idt);
00295 }
00296 return -1;
00297 }
00298
00299
00300
00301 int GWEN_IdList64_HasId(const GWEN_IDLIST64 *idl, uint64_t id){
00302 GWEN_IDTABLE64 *idt;
00303
00304 assert(idl);
00305
00306 idt=GWEN_IdTable64_List_First(idl->idTables);
00307
00308 while(idt) {
00309 if (GWEN_IdTable64_HasId(idt, id))
00310 return 1;
00311 idt=GWEN_IdTable64_List_Next(idt);
00312 }
00313 return 0;
00314 }
00315
00316
00317
00318 void GWEN_IdList64_Clean(GWEN_IDLIST64 *idl) {
00319 GWEN_IDTABLE64 *idt;
00320
00321 assert(idl);
00322 idl->current=0;
00323 idt=GWEN_IdTable64_List_First(idl->idTables);
00324
00325 while(idt) {
00326 GWEN_IDTABLE64 *next;
00327
00328 next=GWEN_IdTable64_List_Next(idt);
00329 if (GWEN_IdTable64_IsEmpty(idt)) {
00330
00331 GWEN_IdTable64_free(idt);
00332 }
00333 idt=next;
00334 }
00335 }
00336
00337
00338
00339 uint64_t GWEN_IdList64_GetFirstId(GWEN_IDLIST64 *idl){
00340 GWEN_IDTABLE64 *idt;
00341
00342 assert(idl);
00343
00344 idt=GWEN_IdTable64_List_First(idl->idTables);
00345
00346 while(idt) {
00347 GWEN_IDTABLE64 *next;
00348 uint64_t id;
00349
00350 next=GWEN_IdTable64_List_Next(idt);
00351 id=GWEN_IdTable64_GetFirstId(idt);
00352 if (id) {
00353 idl->current=idt;
00354 return id;
00355 }
00356 idt=next;
00357 }
00358
00359 return 0;
00360 }
00361
00362
00363
00364 uint64_t GWEN_IdList64_GetNextId(GWEN_IDLIST64 *idl){
00365 GWEN_IDTABLE64 *idt;
00366 uint64_t id;
00367
00368 assert(idl);
00369
00370 idt=idl->current;
00371 if (idt) {
00372 id=GWEN_IdTable64_GetNextId(idt);
00373 if (id) {
00374 idl->current=idt;
00375 return id;
00376 }
00377 }
00378 else {
00379 idl->current=0;
00380 return 0;
00381 }
00382
00383 idt=GWEN_IdTable64_List_Next(idt);
00384 while (idt) {
00385 id=GWEN_IdTable64_GetFirstId(idt);
00386 if (id) {
00387 idl->current=idt;
00388 return id;
00389 }
00390 idt=GWEN_IdTable64_List_Next(idt);
00391 }
00392
00393 idl->current=0;
00394 return 0;
00395 }
00396
00397
00398
00399 static int __compAscending(const void *pa, const void *pb) {
00400 uint64_t a=*((const uint64_t*)pa);
00401 uint64_t b=*((const uint64_t*)pb);
00402
00403 if (a<b)
00404 return -1;
00405 else if (a>b)
00406 return 1;
00407 else
00408 return 0;
00409 }
00410
00411
00412
00413 static int __compDescending(const void *pa, const void *pb) {
00414 uint64_t a=*((const uint64_t*)pa);
00415 uint64_t b=*((const uint64_t*)pb);
00416
00417 if (a<b)
00418 return 1;
00419 else if (a>b)
00420 return -1;
00421 else
00422 return 0;
00423 }
00424
00425
00426
00427 static int GWEN_IdList64__Sort(GWEN_IDLIST64 *idl, int ascending){
00428 GWEN_IDLIST64_ITERATOR *it;
00429 GWEN_IDTABLE64 *idt;
00430 unsigned int cnt;
00431 uint64_t *ptr;
00432 unsigned int i;
00433
00434 assert(idl);
00435
00436
00437 idt=GWEN_IdTable64_List_First(idl->idTables);
00438 cnt=0;
00439 while(idt) {
00440 GWEN_IDTABLE64 *next;
00441
00442 next=GWEN_IdTable64_List_Next(idt);
00443 cnt+=GWEN_IdTable64_GetCount(idt);
00444 idt=next;
00445 }
00446
00447 if (!cnt)
00448 return 0;
00449
00450
00451 ptr=(uint64_t*)malloc(sizeof(uint64_t)*cnt);
00452 assert(ptr);
00453
00454 it=GWEN_IdList64_Iterator_new(idl);
00455 for (i=0; i<cnt; i++) {
00456 uint64_t id;
00457
00458 if (i==0)
00459 id=GWEN_IdList64_Iterator_GetFirstId(it);
00460 else
00461 id=GWEN_IdList64_Iterator_GetNextId(it);
00462 assert(id);
00463 ptr[i]=id;
00464 }
00465 GWEN_IdList64_Iterator_free(it);
00466
00467
00468 GWEN_IdTable64_List_Clear(idl->idTables);
00469 idl->current=0;
00470
00471 if (ascending)
00472 qsort(ptr, cnt, sizeof(uint64_t), __compAscending);
00473 else
00474 qsort(ptr, cnt, sizeof(uint64_t), __compDescending);
00475
00476
00477 for (i=0; i<cnt; i++) {
00478 GWEN_IdList64_AddId(idl, ptr[i]);
00479 }
00480 free(ptr);
00481
00482 return 0;
00483 }
00484
00485
00486
00487 int GWEN_IdList64_Sort(GWEN_IDLIST64 *idl){
00488 return GWEN_IdList64__Sort(idl, 1);
00489 }
00490
00491
00492
00493 int GWEN_IdList64_ReverseSort(GWEN_IDLIST64 *idl){
00494 return GWEN_IdList64__Sort(idl, 0);
00495 }
00496
00497
00498
00499 void GWEN_IdList64_Clear(GWEN_IDLIST64 *idl){
00500 assert(idl);
00501 GWEN_IdTable64_List_Clear(idl->idTables);
00502 idl->entryCount=0;
00503 idl->current=0;
00504 }
00505
00506
00507
00508 GWEN_IDLIST64 *GWEN_IdList64_dup(const GWEN_IDLIST64 *idl){
00509 GWEN_IDLIST64 *nidl;
00510 GWEN_IDTABLE64 *idt;
00511
00512 assert(idl);
00513 nidl=GWEN_IdList64_new();
00514
00515 idt=GWEN_IdTable64_List_First(idl->idTables);
00516 while(idt) {
00517 if (idt->freeEntries!=GWEN_IDTABLE64_MAXENTRIES){
00518 int i;
00519
00520 for (i=0; i<GWEN_IDTABLE64_MAXENTRIES; i++) {
00521 if (idt->entries[i]!=0)
00522 GWEN_IdList64_AddId(nidl, idt->entries[i]);
00523 }
00524 }
00525 idt=GWEN_IdTable64_List_Next(idt);
00526 }
00527
00528 return nidl;
00529 }
00530
00531
00532
00533 uint64_t GWEN_IdList64_GetFirstId2(const GWEN_IDLIST64 *idl,
00534 uint64_t *pos){
00535 GWEN_IDTABLE64 *idt;
00536 int tabNum=0;
00537
00538 assert(idl);
00539
00540 idt=GWEN_IdTable64_List_First(idl->idTables);
00541
00542 while(idt) {
00543 GWEN_IDTABLE64 *next;
00544 uint64_t id;
00545 uint64_t tabIdx;
00546
00547 next=GWEN_IdTable64_List_Next(idt);
00548 id=GWEN_IdTable64_GetFirstId2(idt, &tabIdx);
00549 if (id) {
00550 *pos=(tabNum*GWEN_IDTABLE64_MAXENTRIES)+tabIdx;
00551 return id;
00552 }
00553 tabNum++;
00554 idt=next;
00555 }
00556
00557 return 0;
00558 }
00559
00560
00561
00562 uint64_t GWEN_IdList64_GetNextId2(const GWEN_IDLIST64 *idl,
00563 uint64_t *pos){
00564 GWEN_IDTABLE64 *idt;
00565 int i;
00566 int tabNum;
00567 uint64_t tabIdx;
00568
00569 assert(idl);
00570 tabNum=(*pos)/GWEN_IDTABLE64_MAXENTRIES;
00571 tabIdx=(*pos)%GWEN_IDTABLE64_MAXENTRIES;
00572
00573
00574 i=tabNum;
00575 idt=GWEN_IdTable64_List_First(idl->idTables);
00576 while(i--) idt=GWEN_IdTable64_List_Next(idt);
00577 assert(idt);
00578
00579 while(idt) {
00580 GWEN_IDTABLE64 *next;
00581 uint64_t id;
00582
00583 next=GWEN_IdTable64_List_Next(idt);
00584 id=GWEN_IdTable64_GetNextId2(idt, &tabIdx);
00585 if (id) {
00586 *pos=(tabNum*GWEN_IDTABLE64_MAXENTRIES)+tabIdx;
00587 return id;
00588 }
00589 tabNum++;
00590 idt=next;
00591 }
00592
00593 return 0;
00594 }
00595
00596
00597
00598 GWEN_IDLIST64_ITERATOR *GWEN_IdList64_Iterator_new(GWEN_IDLIST64 *idl) {
00599 GWEN_IDLIST64_ITERATOR *it;
00600
00601 assert(idl);
00602 GWEN_NEW_OBJECT(GWEN_IDLIST64_ITERATOR, it);
00603
00604 GWEN_IdList64_Attach(idl);
00605 it->list=idl;
00606
00607 return it;
00608 }
00609
00610
00611
00612 void GWEN_IdList64_Iterator_free(GWEN_IDLIST64_ITERATOR *it) {
00613 if (it) {
00614 if (it->currentTable)
00615 GWEN_IdTable64_free(it->currentTable);
00616 GWEN_IdList64_free(it->list);
00617 GWEN_FREE_OBJECT(it);
00618 }
00619 }
00620
00621
00622
00623 uint64_t GWEN_IdList64_Iterator_GetFirstId(GWEN_IDLIST64_ITERATOR *it) {
00624 GWEN_IDTABLE64 *idt;
00625
00626 assert(it);
00627
00628 idt=GWEN_IdTable64_List_First(it->list->idTables);
00629
00630 while(idt) {
00631 GWEN_IDTABLE64 *next;
00632 unsigned int i;
00633
00634 next=GWEN_IdTable64_List_Next(idt);
00635
00636 for (i=0; i<GWEN_IDTABLE64_MAXENTRIES; i++) {
00637 if (idt->entries[i]!=0) {
00638
00639 GWEN_IdTable64_Attach(idt);
00640
00641 GWEN_IdTable64_free(it->currentTable);
00642
00643 it->currentTable=idt;
00644 it->currentIndex=i;
00645
00646 return idt->entries[i];
00647 }
00648 }
00649
00650 idt=next;
00651 }
00652
00653 GWEN_IdTable64_free(it->currentTable);
00654 it->currentTable=NULL;
00655 it->currentIndex=0;
00656
00657 return 0;
00658 }
00659
00660
00661
00662 uint64_t GWEN_IdList64_Iterator_GetNextId(GWEN_IDLIST64_ITERATOR *it) {
00663 GWEN_IDTABLE64 *idt;
00664 uint32_t startIdx;
00665
00666 assert(it);
00667
00668 idt=it->currentTable;
00669 startIdx=it->currentIndex+1;
00670
00671
00672 while(idt) {
00673 GWEN_IDTABLE64 *next;
00674 unsigned int i;
00675
00676 next=GWEN_IdTable64_List_Next(idt);
00677
00678 for (i=startIdx; i<GWEN_IDTABLE64_MAXENTRIES; i++) {
00679 if (idt->entries[i]!=0) {
00680
00681 GWEN_IdTable64_Attach(idt);
00682
00683 GWEN_IdTable64_free(it->currentTable);
00684
00685 it->currentTable=idt;
00686 it->currentIndex=i;
00687
00688 return idt->entries[i];
00689 }
00690 }
00691
00692
00693 startIdx=0;
00694 idt=next;
00695 }
00696
00697 GWEN_IdTable64_free(it->currentTable);
00698 it->currentTable=NULL;
00699 it->currentIndex=0;
00700
00701 return 0;
00702 }
00703
00704
00705
00706 int GWEN_IdList64_AppendId(GWEN_IDLIST64 *idl, uint64_t id) {
00707 GWEN_IDTABLE64 *idt;
00708
00709 assert(idl);
00710
00711 idt=GWEN_IdTable64_List_Last(idl->idTables);
00712 if (idt) {
00713 if (GWEN_IdTable64_IsFull(idt)) {
00714 idt=GWEN_IdTable64_new();
00715 GWEN_IdTable64_List_Add(idt, idl->idTables);
00716 }
00717 }
00718 else {
00719 idt=GWEN_IdTable64_new();
00720 GWEN_IdTable64_List_Add(idt, idl->idTables);
00721 }
00722
00723 GWEN_IdTable64_AppendId(idt, id);
00724 idl->entryCount++;
00725 return 0;
00726 }
00727
00728
00729
00730 uint64_t GWEN_IdList64_GetIdAt(const GWEN_IDLIST64 *idl, uint64_t idx) {
00731 GWEN_IDTABLE64 *idt;
00732 uint64_t tableNum=idx / GWEN_IDTABLE64_MAXENTRIES;
00733 uint64_t tableIdx=idx % GWEN_IDTABLE64_MAXENTRIES;
00734
00735 assert(idl);
00736
00737 idt=GWEN_IdTable64_List_First(idl->idTables);
00738
00739 while(idt && tableNum) {
00740 idt=GWEN_IdTable64_List_Next(idt);
00741 tableNum--;
00742 }
00743
00744 if (!idt) {
00745 DBG_INFO(GWEN_LOGDOMAIN, "Index %lld not found", (long long)idx);
00746 return 0;
00747 }
00748
00749 return idt->entries[tableIdx];
00750 }
00751
00752
00753
00754
00755
00756
00757
00758
00759
00760
00761