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