gwenhywfar  4.8.0beta
idmap.c
Go to the documentation of this file.
1 /***************************************************************************
2  $RCSfile$
3  -------------------
4  cvs : $Id: idlist.c 705 2005-02-23 02:16:57Z aquamaniac $
5  begin : Mon Mar 01 2004
6  copyright : (C) 2004 by Martin Preuss
7  email : martin@libchipcard.de
8 
9  ***************************************************************************
10  * *
11  * This library is free software; you can redistribute it and/or *
12  * modify it under the terms of the GNU Lesser General Public *
13  * License as published by the Free Software Foundation; either *
14  * version 2.1 of the License, or (at your option) any later version. *
15  * *
16  * This library is distributed in the hope that it will be useful, *
17  * but WITHOUT ANY WARRANTY; without even the implied warranty of *
18  * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the GNU *
19  * Lesser General Public License for more details. *
20  * *
21  * You should have received a copy of the GNU Lesser General Public *
22  * License along with this library; if not, write to the Free Software *
23  * Foundation, Inc., 59 Temple Place, Suite 330, Boston, *
24  * MA 02111-1307 USA *
25  * *
26  ***************************************************************************/
27 
28 #ifdef HAVE_CONFIG_H
29 # include <config.h>
30 #endif
31 
32 
33 #include "idmap_p.h"
34 
35 #include <gwenhywfar/misc.h>
36 #include <gwenhywfar/debug.h>
37 
38 
39 #include <stdlib.h>
40 #include <assert.h>
41 #include <string.h>
42 
43 
44 
46  GWEN_IDMAP *map;
47 
49  map->algo=algo;
50  switch(algo) {
53  break;
55  default:
56  DBG_ERROR(GWEN_LOGDOMAIN, "Unknown algo %d", algo);
57  GWEN_IdMap_free(map);
58  return 0;
59  }
60 
61  return map;
62 }
63 
64 
65 
67  assert(map);
68  if (map->freeDataFn)
69  map->freeDataFn(map);
70  GWEN_FREE_OBJECT(map);
71 }
72 
73 
74 
76  uint32_t id,
77  void *ptr) {
78  assert(map);
79  assert(ptr);
80  assert(map->setPairFn);
81  return map->setPairFn(map, id, ptr);
82 }
83 
84 
85 
87  uint32_t id) {
88  assert(map);
89  assert(map->setPairFn);
90  return map->setPairFn(map, id, 0);
91 }
92 
93 
94 
95 void *GWEN_IdMap_Find(GWEN_IDMAP *map, uint32_t id) {
96  assert(map);
97  assert(map->getPairFn);
98  return map->getPairFn(map, id);
99 }
100 
101 
102 
104  uint32_t *pid) {
105  assert(map);
106  assert(map->findFirstFn);
107  return map->findFirstFn(map, pid);
108 }
109 
110 
111 
113  uint32_t *pid) {
114  assert(map);
115  assert(map->findNextFn);
116  return map->findNextFn(map, pid);
117 }
118 
119 
120 
121 uint32_t GWEN_IdMap_GetSize(const GWEN_IDMAP *map) {
122  assert(map);
123  return map->count;
124 }
125 
126 
127 
129  assert(map);
130  if (map->freeDataFn)
131  map->freeDataFn(map);
132  map->algoData=0;
133 
134  switch(map->algo) {
135  case GWEN_IdMapAlgo_Hex4:
137  break;
139  default:
140  DBG_ERROR(GWEN_LOGDOMAIN, "Unknown algo %d", map->algo);
141  }
142 }
143 
144 
145 
146 void GWEN_IdMap_Dump(GWEN_IDMAP *map, FILE *f, int indent) {
147  assert(map);
148  if (map->dumpFn)
149  map->dumpFn(map, f, indent);
150  else {
151  DBG_ERROR(GWEN_LOGDOMAIN, "No dump fn");
152  }
153 }
154 
155 
156 
157 
158 
159 /* _________________________________________________________________________
160  * AAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAA
161  * Algo: HEX4
162  * YYYYYYYYYYYYYYYYYYYYYYYYYYYYYYYYYYYYYYYYYYYYYYYYYYYYYYYYYYYYYYYYYYYYYYYYY
163  */
164 
165 
167  GWEN_IDMAP_HEX4 *xmap;
168 
169  GWEN_NEW_OBJECT(GWEN_IDMAP_HEX4, xmap);
170  xmap->table=GWEN_IdMapHex4Map_new(0, 0);
171  map->algoData=(void*)xmap;
172  map->setPairFn=GWEN_IdMapHex4_Insert;
173  map->getPairFn=GWEN_IdMapHex4_Find;
174  map->findFirstFn=GWEN_IdMapHex4_FindFirst;
175  map->findNextFn=GWEN_IdMapHex4_FindNext;
176  map->freeDataFn=GWEN_IdMapHex4_free;
177  map->dumpFn=GWEN_IdMapHex4_Dump;
178 }
179 
180 
181 
183  GWEN_IDMAP_HEX4 *xmap;
184 
185  xmap=(GWEN_IDMAP_HEX4*)map->algoData;
186  GWEN_IdMapHex4Map_free(xmap->table);
187  GWEN_FREE_OBJECT(xmap);
188 }
189 
190 
191 
192 GWEN_IDMAP_HEX4_TABLE *GWEN_IdMapHex4Map_new(GWEN_IDMAP_HEX4_TABLE *p,
193  int isPtrTable) {
194  GWEN_IDMAP_HEX4_TABLE *t;
195 
196  GWEN_NEW_OBJECT(GWEN_IDMAP_HEX4_TABLE, t);
197  t->parent=p;
198  t->isPtrTable=isPtrTable;
199  return t;
200 }
201 
202 
203 
204 void GWEN_IdMapHex4Map_free(GWEN_IDMAP_HEX4_TABLE *t) {
205  if (t) {
206  if (!(t->isPtrTable)) {
207  int i;
208 
209  for(i=0; i<16; i++) {
210  if (t->ptrs[i])
211  GWEN_IdMapHex4Map_free(t->ptrs[i]);
212  }
213  }
214  GWEN_FREE_OBJECT(t);
215  }
216 }
217 
218 
219 
221  uint32_t id,
222  void *ptr) {
223  GWEN_IDMAP_HEX4 *xmap;
224  void **p;
225  GWEN_IDMAP_HEX4_TABLE *t;
226 
227  xmap=(GWEN_IDMAP_HEX4*)map->algoData;
228 
229  t=xmap->table;
230  p=&(t->ptrs[(id>>28) & 0xf]);
231  if (!*p) {
232  if (ptr==0)
234  *p=(void*)GWEN_IdMapHex4Map_new(t, 0);
235  }
236  t=(GWEN_IDMAP_HEX4_TABLE*) *p;
237 
238  p=&(t->ptrs[(id>>24) & 0xf]);
239  if (!*p) {
240  if (ptr==0)
242  *p=(void*)GWEN_IdMapHex4Map_new(t, 0);
243  }
244  t=(GWEN_IDMAP_HEX4_TABLE*) *p;
245 
246  p=&(t->ptrs[(id>>20) & 0xf]);
247  if (!*p) {
248  if (ptr==0)
250  *p=(void*)GWEN_IdMapHex4Map_new(t, 0);
251  }
252  t=(GWEN_IDMAP_HEX4_TABLE*) *p;
253 
254  p=&(t->ptrs[(id>>16) & 0xf]);
255  if (!*p) {
256  if (ptr==0)
258  *p=(void*)GWEN_IdMapHex4Map_new(t, 0);
259  }
260  t=(GWEN_IDMAP_HEX4_TABLE*) *p;
261 
262  p=&(t->ptrs[(id>>12) & 0xf]);
263  if (!*p) {
264  if (ptr==0)
266  *p=(void*)GWEN_IdMapHex4Map_new(t, 0);
267  }
268  t=(GWEN_IDMAP_HEX4_TABLE*) *p;
269 
270  p=&(t->ptrs[(id>>8) & 0xf]);
271  if (!*p) {
272  if (ptr==0)
274  *p=(void*)GWEN_IdMapHex4Map_new(t, 0);
275  }
276  t=(GWEN_IDMAP_HEX4_TABLE*) *p;
277 
278  p=&(t->ptrs[(id>>4) & 0xf]);
279  if (!*p) {
280  if (ptr==0)
282  *p=(void*)GWEN_IdMapHex4Map_new(t, 1);
283  }
284  t=(GWEN_IDMAP_HEX4_TABLE*) *p;
285 
286  p=&(t->ptrs[id & 0xf]);
287  *p=ptr;
288 
289  if (ptr==0) {
290  assert(map->count);
291  map->count--;
292  /* do some cleanup */
293  for (;;) {
294  GWEN_IDMAP_HEX4_TABLE *parent;
295  int i;
296 
297  parent=t->parent;
298  id>>=4;
299  if (parent==0)
300  break;
301  for (i=0; i<16; i++) {
302  if (t->ptrs[i]!=0)
303  break;
304  }
305  if (i<16)
306  break;
307  /* DBG_ERROR(0, "Deleting table %x", id); */
309  parent->ptrs[id & 0xf]=0;
310  t=parent;
311  }
312  }
313  else
314  map->count++;
315 
316  return GWEN_IdMapResult_Ok;
317 }
318 
319 
320 
321 void *GWEN_IdMapHex4_Find(GWEN_IDMAP *map, uint32_t id) {
322  GWEN_IDMAP_HEX4 *xmap;
323  GWEN_IDMAP_HEX4_TABLE *t;
324 
325  xmap=(GWEN_IDMAP_HEX4*)map->algoData;
326 
327  t=xmap->table;
328  if (!t)
329  return 0;
330  t=(GWEN_IDMAP_HEX4_TABLE*)(t->ptrs[(id>>28)&0xf]);
331  if (!t)
332  return 0;
333  t=(GWEN_IDMAP_HEX4_TABLE*)(t->ptrs[(id>>24)&0xf]);
334  if (!t)
335  return 0;
336  t=(GWEN_IDMAP_HEX4_TABLE*)(t->ptrs[(id>>20)&0xf]);
337  if (!t)
338  return 0;
339  t=(GWEN_IDMAP_HEX4_TABLE*)(t->ptrs[(id>>16)&0xf]);
340  if (!t)
341  return 0;
342  t=(GWEN_IDMAP_HEX4_TABLE*)(t->ptrs[(id>>12)&0xf]);
343  if (!t)
344  return 0;
345  t=(GWEN_IDMAP_HEX4_TABLE*)(t->ptrs[(id>>8)&0xf]);
346  if (!t)
347  return 0;
348  t=(GWEN_IDMAP_HEX4_TABLE*)(t->ptrs[(id>>4)&0xf]);
349  if (!t)
350  return 0;
351 
352  return (t->ptrs[id & 0xf]);
353 }
354 
355 
356 
357 GWEN_IDMAP_HEX4_TABLE *GWEN_IdMapHex4__GetTable(GWEN_IDMAP_HEX4_TABLE *t,
358  uint32_t id) {
359  void **p;
360 
361  p=&(t->ptrs[(id>>28) & 0xf]);
362  if (!*p)
363  return 0;
364  t=(GWEN_IDMAP_HEX4_TABLE*) *p;
365 
366  p=&(t->ptrs[(id>>24) & 0xf]);
367  if (!*p)
368  return 0;
369  t=(GWEN_IDMAP_HEX4_TABLE*) *p;
370 
371  p=&(t->ptrs[(id>>20) & 0xf]);
372  if (!*p)
373  return 0;
374  t=(GWEN_IDMAP_HEX4_TABLE*) *p;
375 
376  p=&(t->ptrs[(id>>16) & 0xf]);
377  if (!*p)
378  return 0;
379  t=(GWEN_IDMAP_HEX4_TABLE*) *p;
380 
381  p=&(t->ptrs[(id>>12) & 0xf]);
382  if (!*p)
383  return 0;
384  t=(GWEN_IDMAP_HEX4_TABLE*) *p;
385 
386  p=&(t->ptrs[(id>>8) & 0xf]);
387  if (!*p)
388  return 0;
389  t=(GWEN_IDMAP_HEX4_TABLE*) *p;
390 
391  p=&(t->ptrs[(id>>4) & 0xf]);
392  if (!*p)
393  return 0;
394  t=(GWEN_IDMAP_HEX4_TABLE*) *p;
395 
396  return t;
397 }
398 
399 
400 
401 GWEN_IDMAP_HEX4_TABLE *GWEN_IdMapHex4__GetFirstTable(GWEN_IDMAP_HEX4_TABLE *t,
402  uint32_t *pid) {
403  uint32_t id;
404  int i;
405 
406  /* id=*pid; */
407  id=0;
408  for (i=0; i<16; i++) {
409  if (t->ptrs[i]) {
410  uint32_t lid;
411 
412  lid=(id<<4) | i;
413  if (t->isPtrTable) {
414  *pid=lid;
415  return t;
416  }
417  else {
418  GWEN_IDMAP_HEX4_TABLE *dt;
419 
420  dt=GWEN_IdMapHex4__GetFirstTable((GWEN_IDMAP_HEX4_TABLE*)(t->ptrs[i]),
421  &lid);
422  if (dt) {
423  *pid=lid;
424  return dt;
425  }
426  }
427  }
428  }
429  return 0;
430 }
431 
432 
433 
434 GWEN_IDMAP_HEX4_TABLE *GWEN_IdMapHex4__GetNextTable(GWEN_IDMAP_HEX4_TABLE *t,
435  uint32_t *pid,
436  int incr) {
437  uint32_t id;
438 
439  id=*pid;
440  while (t) {
441  int i;
442 
443  if (incr) {
444  while (t && (id & 0xf)==0xf) {
445  t=t->parent;
446  id>>=4;
447  }
448  if (!t)
449  return 0;
450  id++;
451  }
452 
453  for (i=id & 0xf; i<16; i++) {
454  if (t->ptrs[i]) {
455  uint32_t lid;
456 
457  lid=((id & 0xfffffff0) | i);
458  if (t->isPtrTable) {
459  *pid=lid;
460  return t;
461  }
462  else {
463  GWEN_IDMAP_HEX4_TABLE *dt;
464 
465  lid=lid<<4;
466  dt=GWEN_IdMapHex4__GetNextTable((GWEN_IDMAP_HEX4_TABLE*)(t->ptrs[i]),
467  &lid, 0);
468  if (dt) {
469  *pid=lid;
470  return dt;
471  }
472  }
473  }
474  }
475 
476  id>>=4;
477  t=t->parent;
478  }
479  return 0;
480 }
481 
482 
483 
485  uint32_t *pid) {
486 
487  GWEN_IDMAP_HEX4_TABLE *t;
488  GWEN_IDMAP_HEX4 *xmap;
489  uint32_t id;
490 
491  xmap=(GWEN_IDMAP_HEX4*)map->algoData;
492 
493  t=GWEN_IdMapHex4__GetFirstTable(xmap->table, &id);
494  if (t) {
495  *pid=id;
496  return GWEN_IdMapResult_Ok;
497  }
498 
500 }
501 
502 
503 
505  uint32_t *pid) {
506  GWEN_IDMAP_HEX4_TABLE *t;
507  GWEN_IDMAP_HEX4 *xmap;
508  uint32_t id;
509 
510  xmap=(GWEN_IDMAP_HEX4*)map->algoData;
511 
512  id=*pid;
513 
514  t=GWEN_IdMapHex4__GetTable(xmap->table, id);
515  assert(t);
516 
517  t=GWEN_IdMapHex4__GetNextTable(t, &id, 1);
518  if (t) {
519  *pid=id;
520  return GWEN_IdMapResult_Ok;
521  }
522 
524 }
525 
526 
527 
528 void GWEN_IdMapHex4__Dump(GWEN_IDMAP_HEX4_TABLE *tbl, FILE *f, int indent) {
529  int i;
530 
531  for (i=0; i<16; i++) {
532  int j;
533 
534  if (tbl->ptrs[i]) {
535  for (j=0; j<indent; j++)
536  fprintf(f, " ");
537  fprintf(f, "Id: %01x Ptr: %p\n",
538  i, tbl->ptrs[i]);
539  if (!(tbl->isPtrTable))
540  GWEN_IdMapHex4__Dump(tbl->ptrs[i], f, indent+2);
541  }
542  }
543 }
544 
545 
546 
547 void GWEN_IdMapHex4_Dump(GWEN_IDMAP *map, FILE *f, int indent) {
548  GWEN_IDMAP_HEX4 *xmap;
549 
550  xmap=(GWEN_IDMAP_HEX4*)map->algoData;
551  GWEN_IdMapHex4__Dump(xmap->table, f, indent);
552 }
553 
554 
555 
556 
557 
558