gwenhywfar
4.3.3
|
00001 /*************************************************************************** 00002 $RCSfile$ 00003 ------------------- 00004 cvs : $Id: idlist.c 705 2005-02-23 02:16:57Z aquamaniac $ 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 #ifdef HAVE_CONFIG_H 00029 # include <config.h> 00030 #endif 00031 00032 00033 #include "idmap_p.h" 00034 00035 #include <gwenhywfar/misc.h> 00036 #include <gwenhywfar/debug.h> 00037 00038 00039 #include <stdlib.h> 00040 #include <assert.h> 00041 #include <string.h> 00042 00043 00044 00045 GWEN_IDMAP *GWEN_IdMap_new(GWEN_IDMAP_ALGO algo) { 00046 GWEN_IDMAP *map; 00047 00048 GWEN_NEW_OBJECT(GWEN_IDMAP, map); 00049 map->algo=algo; 00050 switch(algo) { 00051 case GWEN_IdMapAlgo_Hex4: 00052 GWEN_IdMapHex4_Extend(map); 00053 break; 00054 case GWEN_IdMapAlgo_Unknown: 00055 default: 00056 DBG_ERROR(GWEN_LOGDOMAIN, "Unknown algo %d", algo); 00057 GWEN_IdMap_free(map); 00058 return 0; 00059 } 00060 00061 return map; 00062 } 00063 00064 00065 00066 void GWEN_IdMap_free(GWEN_IDMAP *map) { 00067 assert(map); 00068 if (map->freeDataFn) 00069 map->freeDataFn(map); 00070 GWEN_FREE_OBJECT(map); 00071 } 00072 00073 00074 00075 GWEN_IDMAP_RESULT GWEN_IdMap_Insert(GWEN_IDMAP *map, 00076 uint32_t id, 00077 void *ptr) { 00078 assert(map); 00079 assert(ptr); 00080 assert(map->setPairFn); 00081 return map->setPairFn(map, id, ptr); 00082 } 00083 00084 00085 00086 GWEN_IDMAP_RESULT GWEN_IdMap_Remove(GWEN_IDMAP *map, 00087 uint32_t id) { 00088 assert(map); 00089 assert(map->setPairFn); 00090 return map->setPairFn(map, id, 0); 00091 } 00092 00093 00094 00095 void *GWEN_IdMap_Find(GWEN_IDMAP *map, uint32_t id) { 00096 assert(map); 00097 assert(map->getPairFn); 00098 return map->getPairFn(map, id); 00099 } 00100 00101 00102 00103 GWEN_IDMAP_RESULT GWEN_IdMap_GetFirst(const GWEN_IDMAP *map, 00104 uint32_t *pid) { 00105 assert(map); 00106 assert(map->findFirstFn); 00107 return map->findFirstFn(map, pid); 00108 } 00109 00110 00111 00112 GWEN_IDMAP_RESULT GWEN_IdMap_GetNext(const GWEN_IDMAP *map, 00113 uint32_t *pid) { 00114 assert(map); 00115 assert(map->findNextFn); 00116 return map->findNextFn(map, pid); 00117 } 00118 00119 00120 00121 uint32_t GWEN_IdMap_GetSize(const GWEN_IDMAP *map) { 00122 assert(map); 00123 return map->count; 00124 } 00125 00126 00127 00128 void GWEN_IdMap_Clear(GWEN_IDMAP *map) { 00129 assert(map); 00130 if (map->freeDataFn) 00131 map->freeDataFn(map); 00132 map->algoData=0; 00133 00134 switch(map->algo) { 00135 case GWEN_IdMapAlgo_Hex4: 00136 GWEN_IdMapHex4_Extend(map); 00137 break; 00138 case GWEN_IdMapAlgo_Unknown: 00139 default: 00140 DBG_ERROR(GWEN_LOGDOMAIN, "Unknown algo %d", map->algo); 00141 } 00142 } 00143 00144 00145 00146 void GWEN_IdMap_Dump(GWEN_IDMAP *map, FILE *f, int indent) { 00147 assert(map); 00148 if (map->dumpFn) 00149 map->dumpFn(map, f, indent); 00150 else { 00151 DBG_ERROR(GWEN_LOGDOMAIN, "No dump fn"); 00152 } 00153 } 00154 00155 00156 00157 00158 00159 /* _________________________________________________________________________ 00160 * AAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAA 00161 * Algo: HEX4 00162 * YYYYYYYYYYYYYYYYYYYYYYYYYYYYYYYYYYYYYYYYYYYYYYYYYYYYYYYYYYYYYYYYYYYYYYYYY 00163 */ 00164 00165 00166 void GWEN_IdMapHex4_Extend(GWEN_IDMAP *map) { 00167 GWEN_IDMAP_HEX4 *xmap; 00168 00169 GWEN_NEW_OBJECT(GWEN_IDMAP_HEX4, xmap); 00170 xmap->table=GWEN_IdMapHex4Map_new(0, 0); 00171 map->algoData=(void*)xmap; 00172 map->setPairFn=GWEN_IdMapHex4_Insert; 00173 map->getPairFn=GWEN_IdMapHex4_Find; 00174 map->findFirstFn=GWEN_IdMapHex4_FindFirst; 00175 map->findNextFn=GWEN_IdMapHex4_FindNext; 00176 map->freeDataFn=GWEN_IdMapHex4_free; 00177 map->dumpFn=GWEN_IdMapHex4_Dump; 00178 } 00179 00180 00181 00182 void GWEN_IdMapHex4_free(GWEN_IDMAP *map) { 00183 GWEN_IDMAP_HEX4 *xmap; 00184 00185 xmap=(GWEN_IDMAP_HEX4*)map->algoData; 00186 GWEN_IdMapHex4Map_free(xmap->table); 00187 GWEN_FREE_OBJECT(xmap); 00188 } 00189 00190 00191 00192 GWEN_IDMAP_HEX4_TABLE *GWEN_IdMapHex4Map_new(GWEN_IDMAP_HEX4_TABLE *p, 00193 int isPtrTable) { 00194 GWEN_IDMAP_HEX4_TABLE *t; 00195 00196 GWEN_NEW_OBJECT(GWEN_IDMAP_HEX4_TABLE, t); 00197 t->parent=p; 00198 t->isPtrTable=isPtrTable; 00199 return t; 00200 } 00201 00202 00203 00204 void GWEN_IdMapHex4Map_free(GWEN_IDMAP_HEX4_TABLE *t) { 00205 if (t) { 00206 if (!(t->isPtrTable)) { 00207 int i; 00208 00209 for(i=0; i<16; i++) { 00210 if (t->ptrs[i]) 00211 GWEN_IdMapHex4Map_free(t->ptrs[i]); 00212 } 00213 } 00214 GWEN_FREE_OBJECT(t); 00215 } 00216 } 00217 00218 00219 00220 GWEN_IDMAP_RESULT GWEN_IdMapHex4_Insert(GWEN_IDMAP *map, 00221 uint32_t id, 00222 void *ptr) { 00223 GWEN_IDMAP_HEX4 *xmap; 00224 void **p; 00225 GWEN_IDMAP_HEX4_TABLE *t; 00226 00227 xmap=(GWEN_IDMAP_HEX4*)map->algoData; 00228 00229 t=xmap->table; 00230 p=&(t->ptrs[(id>>28) & 0xf]); 00231 if (!*p) { 00232 if (ptr==0) 00233 return GWEN_IdMapResult_NotFound; 00234 *p=(void*)GWEN_IdMapHex4Map_new(t, 0); 00235 } 00236 t=(GWEN_IDMAP_HEX4_TABLE*) *p; 00237 00238 p=&(t->ptrs[(id>>24) & 0xf]); 00239 if (!*p) { 00240 if (ptr==0) 00241 return GWEN_IdMapResult_NotFound; 00242 *p=(void*)GWEN_IdMapHex4Map_new(t, 0); 00243 } 00244 t=(GWEN_IDMAP_HEX4_TABLE*) *p; 00245 00246 p=&(t->ptrs[(id>>20) & 0xf]); 00247 if (!*p) { 00248 if (ptr==0) 00249 return GWEN_IdMapResult_NotFound; 00250 *p=(void*)GWEN_IdMapHex4Map_new(t, 0); 00251 } 00252 t=(GWEN_IDMAP_HEX4_TABLE*) *p; 00253 00254 p=&(t->ptrs[(id>>16) & 0xf]); 00255 if (!*p) { 00256 if (ptr==0) 00257 return GWEN_IdMapResult_NotFound; 00258 *p=(void*)GWEN_IdMapHex4Map_new(t, 0); 00259 } 00260 t=(GWEN_IDMAP_HEX4_TABLE*) *p; 00261 00262 p=&(t->ptrs[(id>>12) & 0xf]); 00263 if (!*p) { 00264 if (ptr==0) 00265 return GWEN_IdMapResult_NotFound; 00266 *p=(void*)GWEN_IdMapHex4Map_new(t, 0); 00267 } 00268 t=(GWEN_IDMAP_HEX4_TABLE*) *p; 00269 00270 p=&(t->ptrs[(id>>8) & 0xf]); 00271 if (!*p) { 00272 if (ptr==0) 00273 return GWEN_IdMapResult_NotFound; 00274 *p=(void*)GWEN_IdMapHex4Map_new(t, 0); 00275 } 00276 t=(GWEN_IDMAP_HEX4_TABLE*) *p; 00277 00278 p=&(t->ptrs[(id>>4) & 0xf]); 00279 if (!*p) { 00280 if (ptr==0) 00281 return GWEN_IdMapResult_NotFound; 00282 *p=(void*)GWEN_IdMapHex4Map_new(t, 1); 00283 } 00284 t=(GWEN_IDMAP_HEX4_TABLE*) *p; 00285 00286 p=&(t->ptrs[id & 0xf]); 00287 *p=ptr; 00288 00289 if (ptr==0) { 00290 assert(map->count); 00291 map->count--; 00292 /* do some cleanup */ 00293 for (;;) { 00294 GWEN_IDMAP_HEX4_TABLE *parent; 00295 int i; 00296 00297 parent=t->parent; 00298 id>>=4; 00299 if (parent==0) 00300 break; 00301 for (i=0; i<16; i++) { 00302 if (t->ptrs[i]!=0) 00303 break; 00304 } 00305 if (i<16) 00306 break; 00307 /* DBG_ERROR(0, "Deleting table %x", id); */ 00308 GWEN_IdMapHex4Map_free(t); 00309 parent->ptrs[id & 0xf]=0; 00310 t=parent; 00311 } 00312 } 00313 else 00314 map->count++; 00315 00316 return GWEN_IdMapResult_Ok; 00317 } 00318 00319 00320 00321 void *GWEN_IdMapHex4_Find(GWEN_IDMAP *map, uint32_t id) { 00322 GWEN_IDMAP_HEX4 *xmap; 00323 GWEN_IDMAP_HEX4_TABLE *t; 00324 00325 xmap=(GWEN_IDMAP_HEX4*)map->algoData; 00326 00327 t=xmap->table; 00328 if (!t) 00329 return 0; 00330 t=(GWEN_IDMAP_HEX4_TABLE*)(t->ptrs[(id>>28)&0xf]); 00331 if (!t) 00332 return 0; 00333 t=(GWEN_IDMAP_HEX4_TABLE*)(t->ptrs[(id>>24)&0xf]); 00334 if (!t) 00335 return 0; 00336 t=(GWEN_IDMAP_HEX4_TABLE*)(t->ptrs[(id>>20)&0xf]); 00337 if (!t) 00338 return 0; 00339 t=(GWEN_IDMAP_HEX4_TABLE*)(t->ptrs[(id>>16)&0xf]); 00340 if (!t) 00341 return 0; 00342 t=(GWEN_IDMAP_HEX4_TABLE*)(t->ptrs[(id>>12)&0xf]); 00343 if (!t) 00344 return 0; 00345 t=(GWEN_IDMAP_HEX4_TABLE*)(t->ptrs[(id>>8)&0xf]); 00346 if (!t) 00347 return 0; 00348 t=(GWEN_IDMAP_HEX4_TABLE*)(t->ptrs[(id>>4)&0xf]); 00349 if (!t) 00350 return 0; 00351 00352 return (t->ptrs[id & 0xf]); 00353 } 00354 00355 00356 00357 GWEN_IDMAP_HEX4_TABLE *GWEN_IdMapHex4__GetTable(GWEN_IDMAP_HEX4_TABLE *t, 00358 uint32_t id) { 00359 void **p; 00360 00361 p=&(t->ptrs[(id>>28) & 0xf]); 00362 if (!*p) 00363 return 0; 00364 t=(GWEN_IDMAP_HEX4_TABLE*) *p; 00365 00366 p=&(t->ptrs[(id>>24) & 0xf]); 00367 if (!*p) 00368 return 0; 00369 t=(GWEN_IDMAP_HEX4_TABLE*) *p; 00370 00371 p=&(t->ptrs[(id>>20) & 0xf]); 00372 if (!*p) 00373 return 0; 00374 t=(GWEN_IDMAP_HEX4_TABLE*) *p; 00375 00376 p=&(t->ptrs[(id>>16) & 0xf]); 00377 if (!*p) 00378 return 0; 00379 t=(GWEN_IDMAP_HEX4_TABLE*) *p; 00380 00381 p=&(t->ptrs[(id>>12) & 0xf]); 00382 if (!*p) 00383 return 0; 00384 t=(GWEN_IDMAP_HEX4_TABLE*) *p; 00385 00386 p=&(t->ptrs[(id>>8) & 0xf]); 00387 if (!*p) 00388 return 0; 00389 t=(GWEN_IDMAP_HEX4_TABLE*) *p; 00390 00391 p=&(t->ptrs[(id>>4) & 0xf]); 00392 if (!*p) 00393 return 0; 00394 t=(GWEN_IDMAP_HEX4_TABLE*) *p; 00395 00396 return t; 00397 } 00398 00399 00400 00401 GWEN_IDMAP_HEX4_TABLE *GWEN_IdMapHex4__GetFirstTable(GWEN_IDMAP_HEX4_TABLE *t, 00402 uint32_t *pid) { 00403 uint32_t id; 00404 int i; 00405 00406 /* id=*pid; */ 00407 id=0; 00408 for (i=0; i<16; i++) { 00409 if (t->ptrs[i]) { 00410 uint32_t lid; 00411 00412 lid=(id<<4) | i; 00413 if (t->isPtrTable) { 00414 *pid=lid; 00415 return t; 00416 } 00417 else { 00418 GWEN_IDMAP_HEX4_TABLE *dt; 00419 00420 dt=GWEN_IdMapHex4__GetFirstTable((GWEN_IDMAP_HEX4_TABLE*)(t->ptrs[i]), 00421 &lid); 00422 if (dt) { 00423 *pid=lid; 00424 return dt; 00425 } 00426 } 00427 } 00428 } 00429 return 0; 00430 } 00431 00432 00433 00434 GWEN_IDMAP_HEX4_TABLE *GWEN_IdMapHex4__GetNextTable(GWEN_IDMAP_HEX4_TABLE *t, 00435 uint32_t *pid, 00436 int incr) { 00437 uint32_t id; 00438 00439 id=*pid; 00440 while (t) { 00441 int i; 00442 00443 if (incr) { 00444 while (t && (id & 0xf)==0xf) { 00445 t=t->parent; 00446 id>>=4; 00447 } 00448 if (!t) 00449 return 0; 00450 id++; 00451 } 00452 00453 for (i=id & 0xf; i<16; i++) { 00454 if (t->ptrs[i]) { 00455 uint32_t lid; 00456 00457 lid=((id & 0xfffffff0) | i); 00458 if (t->isPtrTable) { 00459 *pid=lid; 00460 return t; 00461 } 00462 else { 00463 GWEN_IDMAP_HEX4_TABLE *dt; 00464 00465 lid=lid<<4; 00466 dt=GWEN_IdMapHex4__GetNextTable((GWEN_IDMAP_HEX4_TABLE*)(t->ptrs[i]), 00467 &lid, 0); 00468 if (dt) { 00469 *pid=lid; 00470 return dt; 00471 } 00472 } 00473 } 00474 } 00475 00476 id>>=4; 00477 t=t->parent; 00478 } 00479 return 0; 00480 } 00481 00482 00483 00484 GWEN_IDMAP_RESULT GWEN_IdMapHex4_FindFirst(const GWEN_IDMAP *map, 00485 uint32_t *pid) { 00486 00487 GWEN_IDMAP_HEX4_TABLE *t; 00488 GWEN_IDMAP_HEX4 *xmap; 00489 uint32_t id; 00490 00491 xmap=(GWEN_IDMAP_HEX4*)map->algoData; 00492 00493 t=GWEN_IdMapHex4__GetFirstTable(xmap->table, &id); 00494 if (t) { 00495 *pid=id; 00496 return GWEN_IdMapResult_Ok; 00497 } 00498 00499 return GWEN_IdMapResult_NotFound; 00500 } 00501 00502 00503 00504 GWEN_IDMAP_RESULT GWEN_IdMapHex4_FindNext(const GWEN_IDMAP *map, 00505 uint32_t *pid) { 00506 GWEN_IDMAP_HEX4_TABLE *t; 00507 GWEN_IDMAP_HEX4 *xmap; 00508 uint32_t id; 00509 00510 xmap=(GWEN_IDMAP_HEX4*)map->algoData; 00511 00512 id=*pid; 00513 00514 t=GWEN_IdMapHex4__GetTable(xmap->table, id); 00515 assert(t); 00516 00517 t=GWEN_IdMapHex4__GetNextTable(t, &id, 1); 00518 if (t) { 00519 *pid=id; 00520 return GWEN_IdMapResult_Ok; 00521 } 00522 00523 return GWEN_IdMapResult_NotFound; 00524 } 00525 00526 00527 00528 void GWEN_IdMapHex4__Dump(GWEN_IDMAP_HEX4_TABLE *tbl, FILE *f, int indent) { 00529 int i; 00530 00531 for (i=0; i<16; i++) { 00532 int j; 00533 00534 if (tbl->ptrs[i]) { 00535 for (j=0; j<indent; j++) 00536 fprintf(f, " "); 00537 fprintf(f, "Id: %01x Ptr: %p\n", 00538 i, tbl->ptrs[i]); 00539 if (!(tbl->isPtrTable)) 00540 GWEN_IdMapHex4__Dump(tbl->ptrs[i], f, indent+2); 00541 } 00542 } 00543 } 00544 00545 00546 00547 void GWEN_IdMapHex4_Dump(GWEN_IDMAP *map, FILE *f, int indent) { 00548 GWEN_IDMAP_HEX4 *xmap; 00549 00550 xmap=(GWEN_IDMAP_HEX4*)map->algoData; 00551 GWEN_IdMapHex4__Dump(xmap->table, f, indent); 00552 } 00553 00554 00555 00556 00557 00558