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 int GWEN_IdTable64_AddId(GWEN_IDTABLE64 *idt, uint64_t id){
00083 unsigned int i;
00084
00085 assert(idt);
00086 assert(id);
00087
00088 for (i=0; i<GWEN_IDTABLE64_MAXENTRIES; i++) {
00089 if (idt->entries[i]==0) {
00090 idt->entries[i]=id;
00091 idt->freeEntries--;
00092 return 0;
00093 }
00094 }
00095 return -1;
00096 }
00097
00098
00099
00100 int GWEN_IdTable64_HasId(const GWEN_IDTABLE64 *idt, uint64_t id){
00101 unsigned int i;
00102
00103 assert(idt);
00104 assert(id);
00105
00106 for (i=0; i<GWEN_IDTABLE64_MAXENTRIES; i++) {
00107 if (idt->entries[i]==id) {
00108 return 1;
00109 }
00110 }
00111 return 0;
00112 }
00113
00114
00115
00116 int GWEN_IdTable64_DelId(GWEN_IDTABLE64 *idt, uint64_t id){
00117 unsigned int i;
00118
00119 assert(idt);
00120 assert(id);
00121
00122 for (i=0; i<GWEN_IDTABLE64_MAXENTRIES; i++) {
00123 if (idt->entries[i]==id) {
00124 idt->entries[i]=0;
00125 idt->freeEntries++;
00126 return 0;
00127 }
00128 }
00129 return -1;
00130 }
00131
00132
00133
00134 int GWEN_IdTable64_IsEmpty(const GWEN_IDTABLE64 *idt){
00135 assert(idt);
00136 return GWEN_IDTABLE64_MAXENTRIES==idt->freeEntries;
00137 }
00138
00139
00140
00141 int GWEN_IdTable64_IsFull(const GWEN_IDTABLE64 *idt){
00142 assert(idt);
00143 return idt->freeEntries==0;
00144 }
00145
00146
00147
00148 unsigned int GWEN_IdTable64_GetCount(const GWEN_IDTABLE64 *idt){
00149 assert(idt);
00150 return GWEN_IDTABLE64_MAXENTRIES-idt->freeEntries;
00151 }
00152
00153
00154
00155 uint64_t GWEN_IdTable64_GetFirstId(GWEN_IDTABLE64 *idt){
00156 unsigned int i;
00157
00158 assert(idt);
00159 idt->current=0;
00160 for (i=0; i<GWEN_IDTABLE64_MAXENTRIES; i++) {
00161 if (idt->entries[i]!=0) {
00162 idt->current=i;
00163 return idt->entries[i];
00164 }
00165 }
00166 return 0;
00167 }
00168
00169
00170
00171 uint64_t GWEN_IdTable64_GetNextId(GWEN_IDTABLE64 *idt){
00172 unsigned int i;
00173
00174 assert(idt);
00175
00176 for (i=idt->current+1; i<GWEN_IDTABLE64_MAXENTRIES; i++) {
00177 if (idt->entries[i]!=0) {
00178 idt->current=i;
00179 return idt->entries[i];
00180 }
00181 }
00182 idt->current=GWEN_IDTABLE64_MAXENTRIES;
00183 return 0;
00184 }
00185
00186
00187
00188 uint64_t GWEN_IdTable64_GetFirstId2(const GWEN_IDTABLE64 *idt,
00189 uint64_t *tabIdx){
00190 unsigned int i;
00191
00192 assert(idt);
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 uint64_t GWEN_IdTable64_GetNextId2(const GWEN_IDTABLE64 *idt,
00205 uint64_t *tabIdx){
00206 unsigned int i;
00207
00208 assert(idt);
00209
00210 for (i=(*tabIdx)+1; i<GWEN_IDTABLE64_MAXENTRIES; i++) {
00211 if (idt->entries[i]!=0) {
00212 *tabIdx=i;
00213 return idt->entries[i];
00214 }
00215 }
00216 return 0;
00217 }
00218
00219
00220
00221
00222
00223
00224 GWEN_IDLIST64 *GWEN_IdList64_new(){
00225 GWEN_IDLIST64 *idl;
00226
00227 GWEN_NEW_OBJECT(GWEN_IDLIST64, idl);
00228 idl->refCount=1;
00229 idl->idTables=GWEN_IdTable64_List_new();
00230 return idl;
00231 }
00232
00233
00234
00235 void GWEN_IdList64_Attach(GWEN_IDLIST64 *idl) {
00236 assert(idl);
00237 assert(idl->refCount);
00238 idl->refCount++;
00239 }
00240
00241
00242
00243 void GWEN_IdList64_free(GWEN_IDLIST64 *idl){
00244 if (idl) {
00245 assert(idl->refCount);
00246 if (--(idl->refCount)==0) {
00247 GWEN_IdTable64_List_free(idl->idTables);
00248 GWEN_FREE_OBJECT(idl);
00249 }
00250 }
00251 }
00252
00253
00254
00255 int GWEN_IdList64_AddId(GWEN_IDLIST64 *idl, uint64_t id){
00256 GWEN_IDTABLE64 *idt;
00257
00258 assert(idl);
00259
00260 idl->current=0;
00261 idt=GWEN_IdTable64_List_First(idl->idTables);
00262
00263 while(idt) {
00264 if (!GWEN_IdTable64_IsFull(idt))
00265 break;
00266 idt=GWEN_IdTable64_List_Next(idt);
00267 }
00268
00269 if (!idt) {
00270 idt=GWEN_IdTable64_new();
00271 GWEN_IdTable64_List_Add(idt, idl->idTables);;
00272 }
00273
00274 GWEN_IdTable64_AddId(idt, id);
00275 idl->entryCount++;
00276 return 0;
00277 }
00278
00279
00280
00281 int GWEN_IdList64_DelId(GWEN_IDLIST64 *idl, uint64_t id){
00282 GWEN_IDTABLE64 *idt;
00283
00284 assert(idl);
00285
00286 idl->current=0;
00287 idt=GWEN_IdTable64_List_First(idl->idTables);
00288
00289 while(idt) {
00290 if (!GWEN_IdTable64_DelId(idt, id)) {
00291
00292 GWEN_IdList64_Clean(idl);
00293 idl->entryCount--;
00294 return 0;
00295 }
00296 idt=GWEN_IdTable64_List_Next(idt);
00297 }
00298 return -1;
00299 }
00300
00301
00302
00303 int GWEN_IdList64_HasId(const GWEN_IDLIST64 *idl, uint64_t id){
00304 GWEN_IDTABLE64 *idt;
00305
00306 assert(idl);
00307
00308 idt=GWEN_IdTable64_List_First(idl->idTables);
00309
00310 while(idt) {
00311 if (GWEN_IdTable64_HasId(idt, id))
00312 return 1;
00313 idt=GWEN_IdTable64_List_Next(idt);
00314 }
00315 return 0;
00316 }
00317
00318
00319
00320 void GWEN_IdList64_Clean(GWEN_IDLIST64 *idl) {
00321 GWEN_IDTABLE64 *idt;
00322
00323 assert(idl);
00324 idl->current=0;
00325 idt=GWEN_IdTable64_List_First(idl->idTables);
00326
00327 while(idt) {
00328 GWEN_IDTABLE64 *next;
00329
00330 next=GWEN_IdTable64_List_Next(idt);
00331 if (GWEN_IdTable64_IsEmpty(idt)) {
00332
00333 GWEN_IdTable64_free(idt);
00334 }
00335 idt=next;
00336 }
00337 }
00338
00339
00340
00341 uint64_t GWEN_IdList64_GetFirstId(GWEN_IDLIST64 *idl){
00342 GWEN_IDTABLE64 *idt;
00343
00344 assert(idl);
00345
00346 idt=GWEN_IdTable64_List_First(idl->idTables);
00347
00348 while(idt) {
00349 GWEN_IDTABLE64 *next;
00350 uint64_t id;
00351
00352 next=GWEN_IdTable64_List_Next(idt);
00353 id=GWEN_IdTable64_GetFirstId(idt);
00354 if (id) {
00355 idl->current=idt;
00356 return id;
00357 }
00358 idt=next;
00359 }
00360
00361 return 0;
00362 }
00363
00364
00365
00366 uint64_t GWEN_IdList64_GetNextId(GWEN_IDLIST64 *idl){
00367 GWEN_IDTABLE64 *idt;
00368 uint64_t id;
00369
00370 assert(idl);
00371
00372 idt=idl->current;
00373 if (idt) {
00374 id=GWEN_IdTable64_GetNextId(idt);
00375 if (id) {
00376 idl->current=idt;
00377 return id;
00378 }
00379 }
00380 else {
00381 idl->current=0;
00382 return 0;
00383 }
00384
00385 idt=GWEN_IdTable64_List_Next(idt);
00386 while (idt) {
00387 id=GWEN_IdTable64_GetFirstId(idt);
00388 if (id) {
00389 idl->current=idt;
00390 return id;
00391 }
00392 idt=GWEN_IdTable64_List_Next(idt);
00393 }
00394
00395 idl->current=0;
00396 return 0;
00397 }
00398
00399
00400
00401 int GWEN_IdList64_Sort(GWEN_IDLIST64 *idl){
00402 GWEN_IDLIST64_ITERATOR *it;
00403 GWEN_IDTABLE64 *idt;
00404 unsigned int cnt;
00405 uint64_t *ptr;
00406 unsigned int i;
00407
00408 assert(idl);
00409
00410
00411 idt=GWEN_IdTable64_List_First(idl->idTables);
00412 cnt=0;
00413 while(idt) {
00414 GWEN_IDTABLE64 *next;
00415
00416 next=GWEN_IdTable64_List_Next(idt);
00417 cnt+=GWEN_IdTable64_GetCount(idt);
00418 idt=next;
00419 }
00420
00421 if (!cnt)
00422 return 0;
00423
00424
00425 ptr=(uint64_t*)malloc(sizeof(uint64_t)*cnt);
00426 assert(ptr);
00427
00428 it=GWEN_IdList64_Iterator_new(idl);
00429 for (i=0; i<cnt; i++) {
00430 uint64_t id;
00431
00432 if (i==0)
00433 id=GWEN_IdList64_Iterator_GetFirstId(it);
00434 else
00435 id=GWEN_IdList64_Iterator_GetNextId(it);
00436 assert(id);
00437 ptr[i]=id;
00438 }
00439 GWEN_IdList64_Iterator_free(it);
00440
00441
00442 GWEN_IdTable64_List_Clear(idl->idTables);
00443 idl->current=0;
00444
00445
00446 while(1) {
00447 int rpl;
00448
00449 rpl=0;
00450 for (i=0; i<(cnt-1); i++) {
00451 if (ptr[i]>ptr[i+1]) {
00452 uint64_t id;
00453
00454 id=ptr[i];
00455 ptr[i]=ptr[i+1];
00456 ptr[i+1]=id;
00457 rpl=1;
00458 }
00459 }
00460 if (!rpl)
00461 break;
00462 }
00463
00464
00465 for (i=0; i<cnt; i++) {
00466 GWEN_IdList64_AddId(idl, ptr[i]);
00467 }
00468 free(ptr);
00469
00470 return 0;
00471 }
00472
00473
00474
00475 void GWEN_IdList64_Clear(GWEN_IDLIST64 *idl){
00476 assert(idl);
00477 GWEN_IdTable64_List_Clear(idl->idTables);
00478 idl->entryCount=0;
00479 idl->current=0;
00480 }
00481
00482
00483
00484 GWEN_IDLIST64 *GWEN_IdList64_dup(const GWEN_IDLIST64 *idl){
00485 GWEN_IDLIST64 *nidl;
00486 GWEN_IDTABLE64 *idt;
00487
00488 assert(idl);
00489 nidl=GWEN_IdList64_new();
00490
00491 idt=GWEN_IdTable64_List_First(idl->idTables);
00492 while(idt) {
00493 if (idt->freeEntries!=GWEN_IDTABLE64_MAXENTRIES){
00494 int i;
00495
00496 for (i=0; i<GWEN_IDTABLE64_MAXENTRIES; i++) {
00497 if (idt->entries[i]!=0)
00498 GWEN_IdList64_AddId(nidl, idt->entries[i]);
00499 }
00500 }
00501 idt=GWEN_IdTable64_List_Next(idt);
00502 }
00503
00504 return nidl;
00505 }
00506
00507
00508
00509 uint64_t GWEN_IdList64_GetFirstId2(const GWEN_IDLIST64 *idl,
00510 uint64_t *pos){
00511 GWEN_IDTABLE64 *idt;
00512 int tabNum=0;
00513
00514 assert(idl);
00515
00516 idt=GWEN_IdTable64_List_First(idl->idTables);
00517
00518 while(idt) {
00519 GWEN_IDTABLE64 *next;
00520 uint64_t id;
00521 uint64_t tabIdx;
00522
00523 next=GWEN_IdTable64_List_Next(idt);
00524 id=GWEN_IdTable64_GetFirstId2(idt, &tabIdx);
00525 if (id) {
00526 *pos=(tabNum*GWEN_IDTABLE64_MAXENTRIES)+tabIdx;
00527 return id;
00528 }
00529 tabNum++;
00530 idt=next;
00531 }
00532
00533 return 0;
00534 }
00535
00536
00537
00538 uint64_t GWEN_IdList64_GetNextId2(const GWEN_IDLIST64 *idl,
00539 uint64_t *pos){
00540 GWEN_IDTABLE64 *idt;
00541 int i;
00542 int tabNum;
00543 uint64_t tabIdx;
00544
00545 assert(idl);
00546 tabNum=(*pos)/GWEN_IDTABLE64_MAXENTRIES;
00547 tabIdx=(*pos)%GWEN_IDTABLE64_MAXENTRIES;
00548
00549
00550 i=tabNum;
00551 idt=GWEN_IdTable64_List_First(idl->idTables);
00552 while(i--) idt=GWEN_IdTable64_List_Next(idt);
00553 assert(idt);
00554
00555 while(idt) {
00556 GWEN_IDTABLE64 *next;
00557 uint64_t id;
00558
00559 next=GWEN_IdTable64_List_Next(idt);
00560 id=GWEN_IdTable64_GetNextId2(idt, &tabIdx);
00561 if (id) {
00562 *pos=(tabNum*GWEN_IDTABLE64_MAXENTRIES)+tabIdx;
00563 return id;
00564 }
00565 tabNum++;
00566 idt=next;
00567 }
00568
00569 return 0;
00570 }
00571
00572
00573
00574 GWEN_IDLIST64_ITERATOR *GWEN_IdList64_Iterator_new(GWEN_IDLIST64 *idl) {
00575 GWEN_IDLIST64_ITERATOR *it;
00576
00577 assert(idl);
00578 GWEN_NEW_OBJECT(GWEN_IDLIST64_ITERATOR, it);
00579
00580 GWEN_IdList64_Attach(idl);
00581 it->list=idl;
00582
00583 return it;
00584 }
00585
00586
00587
00588 void GWEN_IdList64_Iterator_free(GWEN_IDLIST64_ITERATOR *it) {
00589 if (it) {
00590 if (it->currentTable)
00591 GWEN_IdTable64_free(it->currentTable);
00592 GWEN_IdList64_free(it->list);
00593 GWEN_FREE_OBJECT(it);
00594 }
00595 }
00596
00597
00598
00599 uint64_t GWEN_IdList64_Iterator_GetFirstId(GWEN_IDLIST64_ITERATOR *it) {
00600 GWEN_IDTABLE64 *idt;
00601
00602 assert(it);
00603
00604 idt=GWEN_IdTable64_List_First(it->list->idTables);
00605
00606 while(idt) {
00607 GWEN_IDTABLE64 *next;
00608 unsigned int i;
00609
00610 next=GWEN_IdTable64_List_Next(idt);
00611
00612 for (i=0; i<GWEN_IDTABLE64_MAXENTRIES; i++) {
00613 if (idt->entries[i]!=0) {
00614
00615 GWEN_IdTable64_Attach(idt);
00616
00617 GWEN_IdTable64_free(it->currentTable);
00618
00619 it->currentTable=idt;
00620 it->currentIndex=i;
00621
00622 return idt->entries[i];
00623 }
00624 }
00625
00626 idt=next;
00627 }
00628
00629 GWEN_IdTable64_free(it->currentTable);
00630 it->currentTable=NULL;
00631 it->currentIndex=0;
00632
00633 return 0;
00634 }
00635
00636
00637
00638 uint64_t GWEN_IdList64_Iterator_GetNextId(GWEN_IDLIST64_ITERATOR *it) {
00639 GWEN_IDTABLE64 *idt;
00640 uint32_t startIdx;
00641
00642 assert(it);
00643
00644 idt=it->currentTable;
00645 startIdx=it->currentIndex+1;
00646
00647
00648 while(idt) {
00649 GWEN_IDTABLE64 *next;
00650 unsigned int i;
00651
00652 next=GWEN_IdTable64_List_Next(idt);
00653
00654 for (i=startIdx; i<GWEN_IDTABLE64_MAXENTRIES; i++) {
00655 if (idt->entries[i]!=0) {
00656
00657 GWEN_IdTable64_Attach(idt);
00658
00659 GWEN_IdTable64_free(it->currentTable);
00660
00661 it->currentTable=idt;
00662 it->currentIndex=i;
00663
00664 return idt->entries[i];
00665 }
00666 }
00667
00668
00669 startIdx=0;
00670 idt=next;
00671 }
00672
00673 GWEN_IdTable64_free(it->currentTable);
00674 it->currentTable=NULL;
00675 it->currentIndex=0;
00676
00677 return 0;
00678 }
00679
00680
00681
00682
00683
00684
00685
00686
00687
00688
00689
00690
00691
00692