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   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 

Generated on Thu Aug 20 13:54:38 2009 for gwenhywfar by  doxygen 1.5.9