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 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