idmap.c

Go to the documentation of this file.
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   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  * AAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAA
00159  *                             Algo: HEX4
00160  * YYYYYYYYYYYYYYYYYYYYYYYYYYYYYYYYYYYYYYYYYYYYYYYYYYYYYYYYYYYYYYYYYYYYYYYYY
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     /* do some cleanup */
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       /* DBG_ERROR(0, "Deleting table %x", id); */
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 

Generated on Wed Sep 3 15:21:58 2008 for gwenhywfar by  doxygen 1.5.6