idlist.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 "idlist_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_IDTABLE, GWEN_IdTable)
00045
00046
00047
00048
00049 GWEN_IDTABLE *GWEN_IdTable_new(){
00050 GWEN_IDTABLE *idt;
00051
00052 GWEN_NEW_OBJECT(GWEN_IDTABLE, idt);
00053 GWEN_LIST_INIT(GWEN_IDTABLE, idt);
00054
00055 idt->freeEntries=GWEN_IDTABLE_MAXENTRIES;
00056 return idt;
00057 }
00058
00059
00060
00061 void GWEN_IdTable_free(GWEN_IDTABLE *idt){
00062 if (idt) {
00063 GWEN_LIST_FINI(GWEN_IDTABLE, idt);
00064 GWEN_FREE_OBJECT(idt);
00065 }
00066 }
00067
00068
00069
00070 int GWEN_IdTable_AddId(GWEN_IDTABLE *idt, uint32_t id){
00071 unsigned int i;
00072
00073 assert(idt);
00074 assert(id);
00075
00076 for (i=0; i<GWEN_IDTABLE_MAXENTRIES; i++) {
00077 if (idt->entries[i]==0) {
00078 idt->entries[i]=id;
00079 idt->freeEntries--;
00080 return 0;
00081 }
00082 }
00083 return -1;
00084 }
00085
00086
00087
00088 int GWEN_IdTable_HasId(const GWEN_IDTABLE *idt, uint32_t id){
00089 unsigned int i;
00090
00091 assert(idt);
00092 assert(id);
00093
00094 for (i=0; i<GWEN_IDTABLE_MAXENTRIES; i++) {
00095 if (idt->entries[i]==id) {
00096 return 1;
00097 }
00098 }
00099 return 0;
00100 }
00101
00102
00103
00104 int GWEN_IdTable_DelId(GWEN_IDTABLE *idt, uint32_t id){
00105 unsigned int i;
00106
00107 assert(idt);
00108 assert(id);
00109
00110 for (i=0; i<GWEN_IDTABLE_MAXENTRIES; i++) {
00111 if (idt->entries[i]==id) {
00112 idt->entries[i]=0;
00113 idt->freeEntries++;
00114 return 0;
00115 }
00116 }
00117 return -1;
00118 }
00119
00120
00121
00122 int GWEN_IdTable_IsEmpty(const GWEN_IDTABLE *idt){
00123 assert(idt);
00124 return GWEN_IDTABLE_MAXENTRIES==idt->freeEntries;
00125 }
00126
00127
00128
00129 int GWEN_IdTable_IsFull(const GWEN_IDTABLE *idt){
00130 assert(idt);
00131 return idt->freeEntries==0;
00132 }
00133
00134
00135
00136 unsigned int GWEN_IdTable_GetCount(const GWEN_IDTABLE *idt){
00137 assert(idt);
00138 return GWEN_IDTABLE_MAXENTRIES-idt->freeEntries;
00139 }
00140
00141
00142
00143 uint32_t GWEN_IdTable_GetFirstId(GWEN_IDTABLE *idt){
00144 unsigned int i;
00145
00146 assert(idt);
00147 idt->current=0;
00148 for (i=0; i<GWEN_IDTABLE_MAXENTRIES; i++) {
00149 if (idt->entries[i]!=0) {
00150 idt->current=i;
00151 return idt->entries[i];
00152 }
00153 }
00154 return 0;
00155 }
00156
00157
00158
00159 uint32_t GWEN_IdTable_GetNextId(GWEN_IDTABLE *idt){
00160 unsigned int i;
00161
00162 assert(idt);
00163
00164 for (i=idt->current+1; i<GWEN_IDTABLE_MAXENTRIES; i++) {
00165 if (idt->entries[i]!=0) {
00166 idt->current=i;
00167 return idt->entries[i];
00168 }
00169 }
00170 idt->current=GWEN_IDTABLE_MAXENTRIES;
00171 return 0;
00172 }
00173
00174
00175
00176 uint32_t GWEN_IdTable_GetFirstId2(const GWEN_IDTABLE *idt,
00177 uint32_t *tabIdx){
00178 unsigned int i;
00179
00180 assert(idt);
00181 for (i=0; i<GWEN_IDTABLE_MAXENTRIES; i++) {
00182 if (idt->entries[i]!=0) {
00183 *tabIdx=i;
00184 return idt->entries[i];
00185 }
00186 }
00187 return 0;
00188 }
00189
00190
00191
00192 uint32_t GWEN_IdTable_GetNextId2(const GWEN_IDTABLE *idt,
00193 uint32_t *tabIdx){
00194 unsigned int i;
00195
00196 assert(idt);
00197
00198 for (i=(*tabIdx)+1; i<GWEN_IDTABLE_MAXENTRIES; i++) {
00199 if (idt->entries[i]!=0) {
00200 *tabIdx=i;
00201 return idt->entries[i];
00202 }
00203 }
00204 return 0;
00205 }
00206
00207
00208
00209
00210
00211
00212 GWEN_IDLIST *GWEN_IdList_new(){
00213 GWEN_IDLIST *idl;
00214
00215 GWEN_NEW_OBJECT(GWEN_IDLIST, idl);
00216 idl->idTables=GWEN_IdTable_List_new();
00217 return idl;
00218 }
00219
00220
00221
00222 void GWEN_IdList_free(GWEN_IDLIST *idl){
00223 if (idl) {
00224 GWEN_IdTable_List_free(idl->idTables);
00225 GWEN_FREE_OBJECT(idl);
00226 }
00227 }
00228
00229
00230
00231 int GWEN_IdList_AddId(GWEN_IDLIST *idl, uint32_t id){
00232 GWEN_IDTABLE *idt;
00233
00234 assert(idl);
00235
00236 idl->current=0;
00237 idt=GWEN_IdTable_List_First(idl->idTables);
00238
00239 while(idt) {
00240 if (!GWEN_IdTable_IsFull(idt))
00241 break;
00242 idt=GWEN_IdTable_List_Next(idt);
00243 }
00244
00245 if (!idt) {
00246 idt=GWEN_IdTable_new();
00247 GWEN_IdTable_List_Add(idt, idl->idTables);;
00248 }
00249
00250 GWEN_IdTable_AddId(idt, id);
00251 idl->entryCount++;
00252 return 0;
00253 }
00254
00255
00256
00257 int GWEN_IdList_DelId(GWEN_IDLIST *idl, uint32_t id){
00258 GWEN_IDTABLE *idt;
00259
00260 assert(idl);
00261
00262 idl->current=0;
00263 idt=GWEN_IdTable_List_First(idl->idTables);
00264
00265 while(idt) {
00266 if (!GWEN_IdTable_DelId(idt, id)) {
00267
00268 GWEN_IdList_Clean(idl);
00269 idl->entryCount--;
00270 return 0;
00271 }
00272 idt=GWEN_IdTable_List_Next(idt);
00273 }
00274 return -1;
00275 }
00276
00277
00278
00279 int GWEN_IdList_HasId(const GWEN_IDLIST *idl, uint32_t id){
00280 GWEN_IDTABLE *idt;
00281
00282 assert(idl);
00283
00284 idt=GWEN_IdTable_List_First(idl->idTables);
00285
00286 while(idt) {
00287 if (GWEN_IdTable_HasId(idt, id))
00288 return 1;
00289 idt=GWEN_IdTable_List_Next(idt);
00290 }
00291 return 0;
00292 }
00293
00294
00295
00296 void GWEN_IdList_Clean(GWEN_IDLIST *idl) {
00297 GWEN_IDTABLE *idt;
00298
00299 assert(idl);
00300 idl->current=0;
00301 idt=GWEN_IdTable_List_First(idl->idTables);
00302
00303 while(idt) {
00304 GWEN_IDTABLE *next;
00305
00306 next=GWEN_IdTable_List_Next(idt);
00307 if (GWEN_IdTable_IsEmpty(idt)) {
00308 GWEN_IdTable_List_Del(idt);
00309 GWEN_IdTable_free(idt);
00310 }
00311 idt=next;
00312 }
00313 }
00314
00315
00316
00317 uint32_t GWEN_IdList_GetFirstId(GWEN_IDLIST *idl){
00318 GWEN_IDTABLE *idt;
00319
00320 assert(idl);
00321
00322 idt=GWEN_IdTable_List_First(idl->idTables);
00323
00324 while(idt) {
00325 GWEN_IDTABLE *next;
00326 uint32_t id;
00327
00328 next=GWEN_IdTable_List_Next(idt);
00329 id=GWEN_IdTable_GetFirstId(idt);
00330 if (id) {
00331 idl->current=idt;
00332 return id;
00333 }
00334 idt=next;
00335 }
00336
00337 return 0;
00338 }
00339
00340
00341
00342 uint32_t GWEN_IdList_GetNextId(GWEN_IDLIST *idl){
00343 GWEN_IDTABLE *idt;
00344 uint32_t id;
00345
00346 assert(idl);
00347
00348 idt=idl->current;
00349 if (idt) {
00350 id=GWEN_IdTable_GetNextId(idt);
00351 if (id) {
00352 idl->current=idt;
00353 return id;
00354 }
00355 }
00356 else {
00357 idl->current=0;
00358 return 0;
00359 }
00360
00361 idt=GWEN_IdTable_List_Next(idt);
00362 while (idt) {
00363 id=GWEN_IdTable_GetFirstId(idt);
00364 if (id) {
00365 idl->current=idt;
00366 return id;
00367 }
00368 idt=GWEN_IdTable_List_Next(idt);
00369 }
00370
00371 idl->current=0;
00372 return 0;
00373 }
00374
00375
00376
00377 int GWEN_IdList_Sort(GWEN_IDLIST *idl){
00378 GWEN_IDTABLE *idt;
00379 unsigned int cnt;
00380 uint32_t *ptr;
00381 unsigned int i;
00382
00383 assert(idl);
00384
00385
00386 idt=GWEN_IdTable_List_First(idl->idTables);
00387 cnt=0;
00388 while(idt) {
00389 GWEN_IDTABLE *next;
00390
00391 next=GWEN_IdTable_List_Next(idt);
00392 cnt+=GWEN_IdTable_GetCount(idt);
00393 idt=next;
00394 }
00395
00396 if (!cnt)
00397 return 0;
00398
00399
00400 ptr=(uint32_t*)malloc(sizeof(uint32_t)*cnt);
00401 assert(ptr);
00402
00403 for (i=0; i<cnt; i++) {
00404 uint32_t id;
00405
00406 if (i==0)
00407 id=GWEN_IdList_GetFirstId(idl);
00408 else
00409 id=GWEN_IdList_GetNextId(idl);
00410 assert(id);
00411 ptr[i]=id;
00412 }
00413
00414 GWEN_IdTable_List_Clear(idl->idTables);
00415 idl->current=0;
00416
00417
00418 while(1) {
00419 int rpl;
00420
00421 rpl=0;
00422 for (i=0; i<(cnt-1); i++) {
00423 if (ptr[i]>ptr[i+1]) {
00424 uint32_t id;
00425
00426 id=ptr[i];
00427 ptr[i]=ptr[i+1];
00428 ptr[i+1]=id;
00429 rpl=1;
00430 }
00431 }
00432 if (!rpl)
00433 break;
00434 }
00435
00436
00437 for (i=0; i<cnt; i++) {
00438 GWEN_IdList_AddId(idl, ptr[i]);
00439 }
00440 free(ptr);
00441
00442 return 0;
00443 }
00444
00445
00446
00447 void GWEN_IdList_Clear(GWEN_IDLIST *idl){
00448 assert(idl);
00449 GWEN_IdTable_List_Clear(idl->idTables);
00450 idl->entryCount=0;
00451 idl->current=0;
00452 }
00453
00454
00455
00456 GWEN_IDLIST *GWEN_IdList_dup(const GWEN_IDLIST *idl){
00457 GWEN_IDLIST *nidl;
00458 GWEN_IDTABLE *idt;
00459
00460 assert(idl);
00461 nidl=GWEN_IdList_new();
00462
00463 idt=GWEN_IdTable_List_First(idl->idTables);
00464 while(idt) {
00465 if (idt->freeEntries!=GWEN_IDTABLE_MAXENTRIES){
00466 int i;
00467
00468 for (i=0; i<GWEN_IDTABLE_MAXENTRIES; i++) {
00469 if (idt->entries[i]!=0)
00470 GWEN_IdList_AddId(nidl, idt->entries[i]);
00471 }
00472 }
00473 idt=GWEN_IdTable_List_Next(idt);
00474 }
00475
00476 return nidl;
00477 }
00478
00479
00480
00481 uint32_t GWEN_IdList_GetFirstId2(const GWEN_IDLIST *idl,
00482 uint32_t *pos){
00483 GWEN_IDTABLE *idt;
00484 int tabNum=0;
00485
00486 assert(idl);
00487
00488 idt=GWEN_IdTable_List_First(idl->idTables);
00489
00490 while(idt) {
00491 GWEN_IDTABLE *next;
00492 uint32_t id;
00493 uint32_t tabIdx;
00494
00495 next=GWEN_IdTable_List_Next(idt);
00496 id=GWEN_IdTable_GetFirstId2(idt, &tabIdx);
00497 if (id) {
00498 *pos=(tabNum*GWEN_IDTABLE_MAXENTRIES)+tabIdx;
00499 return id;
00500 }
00501 tabNum++;
00502 idt=next;
00503 }
00504
00505 return 0;
00506 }
00507
00508
00509
00510 uint32_t GWEN_IdList_GetNextId2(const GWEN_IDLIST *idl,
00511 uint32_t *pos){
00512 GWEN_IDTABLE *idt;
00513 int i;
00514 int tabNum;
00515 uint32_t tabIdx;
00516
00517 assert(idl);
00518 tabNum=(*pos)/GWEN_IDTABLE_MAXENTRIES;
00519 tabIdx=(*pos)%GWEN_IDTABLE_MAXENTRIES;
00520
00521
00522 i=tabNum;
00523 idt=GWEN_IdTable_List_First(idl->idTables);
00524 while(i--) idt=GWEN_IdTable_List_Next(idt);
00525 assert(idt);
00526
00527 while(idt) {
00528 GWEN_IDTABLE *next;
00529 uint32_t id;
00530
00531 next=GWEN_IdTable_List_Next(idt);
00532 id=GWEN_IdTable_GetNextId2(idt, &tabIdx);
00533 if (id) {
00534 *pos=(tabNum*GWEN_IDTABLE_MAXENTRIES)+tabIdx;
00535 return id;
00536 }
00537 tabNum++;
00538 idt=next;
00539 }
00540
00541 return 0;
00542 }
00543
00544
00545
00546
00547
00548
00549
00550
00551
00552
00553