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 #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
00161
00162
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
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
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
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