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