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