gwenhywfar
4.3.3
|
00001 /*************************************************************************** 00002 $RCSfile$ 00003 ------------------- 00004 cvs : $Id$ 00005 begin : Mon Mar 01 2004 00006 copyright : (C) 2004 by Martin Preuss 00007 email : martin@libchipcard.de 00008 00009 *************************************************************************** 00010 * * 00011 * This library is free software; you can redistribute it and/or * 00012 * modify it under the terms of the GNU Lesser General Public * 00013 * License as published by the Free Software Foundation; either * 00014 * version 2.1 of the License, or (at your option) any later version. * 00015 * * 00016 * This library is distributed in the hope that it will be useful, * 00017 * but WITHOUT ANY WARRANTY; without even the implied warranty of * 00018 * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the GNU * 00019 * Lesser General Public License for more details. * 00020 * * 00021 * You should have received a copy of the GNU Lesser General Public * 00022 * License along with this library; if not, write to the Free Software * 00023 * Foundation, Inc., 59 Temple Place, Suite 330, Boston, * 00024 * MA 02111-1307 USA * 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 /* No trailing semicolon here because this is a macro call */ 00046 00047 00048 00049 GWEN_IDTABLE *GWEN_IdTable_new(void){ 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 } /* for */ 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 } /* for */ 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 } /* for */ 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 } /* for */ 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 } /* for */ 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 } /* for */ 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 } /* for */ 00204 return 0; 00205 } 00206 00207 00208 00209 00210 00211 00212 GWEN_IDLIST *GWEN_IdList_new(void){ 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 /* find free table */ 00239 while(idt) { 00240 if (!GWEN_IdTable_IsFull(idt)) 00241 break; 00242 idt=GWEN_IdTable_List_Next(idt); 00243 } /* while */ 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 /* find table */ 00265 while(idt) { 00266 if (!GWEN_IdTable_DelId(idt, id)) { 00267 /* found a table which had this id */ 00268 GWEN_IdList_Clean(idl); 00269 idl->entryCount--; 00270 return 0; 00271 } 00272 idt=GWEN_IdTable_List_Next(idt); 00273 } /* while */ 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 /* find free table */ 00286 while(idt) { 00287 if (GWEN_IdTable_HasId(idt, id)) 00288 return 1; 00289 idt=GWEN_IdTable_List_Next(idt); 00290 } /* while */ 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 /* find free table */ 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 } /* while */ 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 /* find free table */ 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 } /* while */ 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 } /* while */ 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 /* count ids */ 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 } /* while */ 00395 00396 if (!cnt) 00397 return 0; 00398 00399 /* move ids to a temporary list */ 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 } /* for */ 00413 00414 GWEN_IdTable_List_Clear(idl->idTables); 00415 idl->current=0; 00416 00417 /* sort temporary list */ 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 } /* for */ 00432 if (!rpl) 00433 break; 00434 } /* while */ 00435 00436 /* move back from temporary list */ 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 /* find free table */ 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 } /* while */ 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 /* seek table */ 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 } /* while */ 00540 00541 return 0; 00542 } 00543 00544 00545 00546 00547 00548 00549 00550 00551 00552 00553