Logo AND Algorithmique Numérique Distribuée

Public GIT Repository
Add xbt_lib_size and xbt_lib_rehash
[simgrid.git] / src / xbt / lib.c
1 /*
2  * lib.c
3  *
4  *  Created on: 16 mars 2011
5  *      Author: navarrop
6  */
7
8 #include <string.h>
9 #include <stdio.h>
10 #include "xbt/misc.h"           /* SG_BEGIN_DECL */
11 #include "xbt/mallocator.h"
12 #include "xbt/ex.h"
13 #include "xbt/log.h"
14 #include "xbt_modinter.h"
15 #include "xbt/lib.h"
16
17 #define DJB2_HASH_FUNCTION
18 //#define FNV_HASH_FUNCTION
19
20 XBT_LOG_NEW_DEFAULT_SUBCATEGORY(xbt_lib, xbt,
21                                 "Libraries provide the same functionalities than hash tables");
22
23 /*####[ Private prototypes ]#################################################*/
24 static void *lib_mallocator_new_f(void);
25 static void lib_mallocator_free_f(void *dict);
26 static void lib_mallocator_reset_f(void *dict);
27
28 static void xbt_lib_set_ext(xbt_lib_t lib,const char *key,
29                             int key_len, int level, void *data);
30
31 static unsigned int xbt_lib_hash_ext(const char *str,
32                                                  int str_len);
33 static unsigned int xbt_lib_hash(const char *str);
34 static void xbt_lib_rehash(xbt_lib_t lib);
35
36
37 static xbt_lib_cursor_t xbt_lib_cursor_new(const xbt_lib_t lib);
38 static void xbt_lib_cursor_rewind(xbt_lib_cursor_t cursor);
39 static void xbt_lib_cursor_free(xbt_lib_cursor_t * cursor);
40
41 /*####[ Code ]###############################################################*/
42
43 unsigned int xbt_lib_size(xbt_lib_t lib)
44 {
45   return (lib ? (unsigned int) lib->count : (unsigned int) 0);
46 }
47
48 static xbt_libelm_t xbt_libelm_new(const char *key,
49                               int key_len,
50                               unsigned int hash_code,
51                               void *content,int level, int level_numbers)
52 {
53   xbt_libelm_t element = xbt_malloc0(sizeof (s_xbt_libelm_t) + sizeof(void *)*(level_numbers-1));
54
55   element->key = xbt_new(char, key_len + 1);
56   memcpy((void *) element->key, (void *) key, key_len);
57   element->key[key_len] = '\0';
58
59   element->key_len = key_len;
60   element->hash_code = hash_code;
61
62   (&(element->content))[level] = content;
63   element->next = NULL;
64
65   return element;
66 }
67
68 xbt_lib_t xbt_lib_new(void)
69 {
70   xbt_lib_t lib;
71   lib = xbt_new0(s_xbt_lib_t, 1);
72   lib->table_size = 127;
73   lib->table = xbt_new0(xbt_libelm_t, lib->table_size + 1);
74   lib->count = 0;
75   lib->fill = 0;
76   lib->levels = 0;
77   lib->free_f = NULL;
78
79   return lib;
80 }
81
82 void xbt_lib_free(xbt_lib_t * lib)
83 {
84   int i,j;
85   xbt_libelm_t current, previous;
86   int table_size;
87   xbt_libelm_t *table;
88
89   //  if ( *dict )  xbt_dict_dump_sizes(*dict);
90
91   if (lib != NULL && *lib != NULL) {
92     table_size = (*lib)->table_size;
93     table = (*lib)->table;
94
95     for (i = 0; (*lib)->count && i <= table_size; i++) {
96       current = table[i];
97       while (current != NULL) {
98                         previous = current;
99                         current = current->next;
100                         xbt_free(previous->key);
101                         for(j=0; j< (*lib)->levels; j++)
102                           if((&(previous->content))[j])
103                                   (*lib)->free_f[j]( (&(previous->content))[j]);
104                 xbt_free(previous);
105                         (*lib)->count--;
106       }
107     }
108     xbt_free(table);
109     xbt_free((*lib)->free_f);
110     xbt_free(*lib);
111     *lib = NULL;
112   }
113 }
114
115 int xbt_lib_add_level(xbt_lib_t lib, void_f_pvoid_t free_f)
116 {
117         XBT_DEBUG("xbt_lib_add_level");
118
119         lib->free_f = realloc(lib->free_f,sizeof(void_f_pvoid_t)*(lib->levels+1));
120         lib->free_f[lib->levels]=free_f;
121         return lib->levels++;
122 }
123
124 void xbt_lib_set(xbt_lib_t lib, const char *name, int level, void *obj)
125 {
126         XBT_DEBUG("xbt_lib_set key '%s' with object '%p'",name,obj);
127         xbt_lib_set_ext(lib, name, strlen(name),level, obj);
128 }
129
130 void *xbt_lib_get_or_null(xbt_lib_t lib, const char *key, int level)
131 {
132         unsigned int hash_code = xbt_lib_hash(key);
133         xbt_libelm_t current;
134
135         if(!lib) xbt_die("Lib is NULL!");
136
137         current = lib->table[hash_code & lib->table_size];
138         while (current != NULL &&
139                  (hash_code != current->hash_code || strcmp(key, current->key)))
140         current = current->next;
141
142         if (current == NULL)
143         return NULL;
144
145         return (&(current->content))[level];
146 }
147
148 static void *lib_mallocator_new_f(void)
149 {
150   return xbt_new(s_xbt_lib_t, 1);
151 }
152
153 static void lib_mallocator_free_f(void *lib)
154 {
155   xbt_free(lib);
156 }
157
158 static void lib_mallocator_reset_f(void *lib)
159 {
160   /* nothing to do because all fields are
161    * initialized in xbt_dict_new
162    */
163 }
164
165 void xbt_lib_reset(xbt_lib_t *lib)
166 {
167   XBT_DEBUG("xbt_lib_reset");
168   int i,j;
169   xbt_libelm_t current, next;
170   xbt_lib_t l = *lib;
171   int levels = l->levels;
172   if(!(*lib)) xbt_die("Lib is NULL!");
173
174   if (l->count == 0)
175     return;
176
177   for (i = 0; i <= l->table_size; i++) {
178     current = l->table[i];
179     while (current) {
180         next = current->next;
181         xbt_free(current->key);
182         for(j=0; j< levels; j++)
183                 if((&(current->content))[j] && (l->free_f[j]))
184                         l->free_f[j]((&(current->content))[j]);
185         xbt_free(current);
186         current = next;
187     }
188     l->table[i] = NULL;
189   }
190   xbt_free(l->free_f);
191   l->count = 0;
192   l->fill = 0;
193   l->levels = 0;
194   l->free_f = NULL;
195 }
196
197 int xbt_lib_length(xbt_lib_t lib)
198 {
199   if(!lib) xbt_die("Lib is NULL!");
200   return lib->count;
201 }
202
203 static void xbt_lib_set_ext(xbt_lib_t lib,
204                             const char *key,
205                             int key_len,
206                             int level,
207                             void *data)
208 {
209
210   unsigned int hash_code = xbt_lib_hash_ext(key, key_len);
211
212   xbt_libelm_t current, previous = NULL;
213   if(!lib) xbt_die("Lib is NULL!");
214
215   XBT_DEBUG("ADD '%.*s' hash = '%d', size = '%d', & = '%d' to level : %d",
216                   key_len,
217                   key,
218                   hash_code,
219           lib->table_size,
220           hash_code & lib->table_size,
221           level);
222
223   current = lib->table[hash_code & lib->table_size];
224   while (current != NULL &&
225          (hash_code != current->hash_code || key_len != current->key_len
226           || memcmp(key, current->key, key_len))) {
227     previous = current;
228     current = current->next;
229   }
230
231   if (current == NULL) {/* this key doesn't exist yet */
232                 current = xbt_libelm_new(key, key_len, hash_code, data,level,lib->levels);
233                 lib->count++;
234                 if (previous == NULL) {
235                 lib->table[hash_code & lib->table_size] = current;
236                 lib->fill++;
237                 if ((lib->fill * 100) / (lib->table_size + 1) > MAX_FILL_PERCENT)
238                   xbt_lib_rehash(lib);
239                 } else {
240                 previous->next = current;
241                 }
242   }
243   else
244           if( (&(current->content))[level] == NULL )/* this key exist but level is empty */
245           {
246                   (&(current->content))[level] = data;
247           }
248           else
249           {/* there is already an element with the same key: overwrite it */
250                         XBT_DEBUG("Replace %.*s by %.*s under key %.*s",
251                                    key_len, (char *) (&(current->content))[level],
252                                    key_len, (char *) data, key_len, (char *) key);
253                         if (current->content != NULL) {
254                           free((&(current->content))[level]);
255                         }
256                         (&(current->content))[level] = data;
257           }
258 }
259
260 /**
261  * Returns the hash code of a string.
262  */
263 static unsigned int xbt_lib_hash_ext(const char *str,
264                                                  int str_len)
265 {
266
267
268 #ifdef DJB2_HASH_FUNCTION
269   /* fast implementation of djb2 algorithm */
270   int c;
271   register unsigned int hash = 5381;
272
273   while (str_len--) {
274     c = *str++;
275     hash = ((hash << 5) + hash) + c;    /* hash * 33 + c */
276   }
277 # elif defined(FNV_HASH_FUNCTION)
278   register unsigned int hash = 0x811c9dc5;
279   unsigned char *bp = (unsigned char *) str;    /* start of buffer */
280   unsigned char *be = bp + str_len;     /* beyond end of buffer */
281
282   while (bp < be) {
283     /* multiply by the 32 bit FNV magic prime mod 2^32 */
284     hash +=
285         (hash << 1) + (hash << 4) + (hash << 7) + (hash << 8) +
286         (hash << 24);
287
288     /* xor the bottom with the current octet */
289     hash ^= (unsigned int) *bp++;
290   }
291
292 # else
293   register unsigned int hash = 0;
294
295   while (str_len--) {
296     hash += (*str) * (*str);
297     str++;
298   }
299 #endif
300
301   return hash;
302 }
303
304 static unsigned int xbt_lib_hash(const char *str)
305 {
306 #ifdef DJB2_HASH_FUNCTION
307   /* fast implementation of djb2 algorithm */
308   int c;
309   register unsigned int hash = 5381;
310
311   while ((c = *str++)) {
312     hash = ((hash << 5) + hash) + c;    /* hash * 33 + c */
313   }
314
315 # elif defined(FNV_HASH_FUNCTION)
316   register unsigned int hash = 0x811c9dc5;
317
318   while (*str) {
319     /* multiply by the 32 bit FNV magic prime mod 2^32 */
320     hash +=
321         (hash << 1) + (hash << 4) + (hash << 7) + (hash << 8) +
322         (hash << 24);
323
324     /* xor the bottom with the current byte */
325     hash ^= (unsigned int) *str++;
326   }
327
328 # else
329   register unsigned int hash = 0;
330
331   while (*str) {
332     hash += (*str) * (*str);
333     str++;
334   }
335 #endif
336   return hash;
337 }
338
339 static void xbt_lib_rehash(xbt_lib_t lib)
340 {
341         const int oldsize = lib->table_size + 1;
342         register int newsize = oldsize * 2;
343         register int i;
344         register xbt_libelm_t *currcell;
345         register xbt_libelm_t *twincell;
346         register xbt_libelm_t bucklet;
347         register xbt_libelm_t *pprev;
348
349         currcell =
350           (xbt_libelm_t *) xbt_realloc((char *) lib->table,
351                                                                         newsize * (sizeof(xbt_libelm_t) + sizeof(void*)*(lib->levels - 1)));
352         memset(&currcell[oldsize], 0, oldsize * (sizeof(xbt_libelm_t) + sizeof(void*)*(lib->levels - 1)));       /* zero second half */
353         lib->table_size = --newsize;
354         lib->table = currcell;
355         XBT_DEBUG("REHASH (%d->%d)", oldsize, newsize);
356
357         for (i = 0; i < oldsize; i++, currcell++) {
358         if (!*currcell)             /* empty cell */
359           continue;
360         twincell = currcell + oldsize;
361         for (pprev = currcell, bucklet = *currcell; bucklet; bucklet = *pprev) {
362           /* Since we use "& size" instead of "%size" and since the size was doubled,
363                  each bucklet of this cell must either :
364                  - stay  in  cell i (ie, currcell)
365                  - go to the cell i+oldsize (ie, twincell) */
366           if ((bucklet->hash_code & newsize) != i) {        /* Move to b */
367                 *pprev = bucklet->next;
368                 bucklet->next = *twincell;
369                 if (!*twincell)
370                   lib->fill++;
371                 *twincell = bucklet;
372                 continue;
373           } else {
374                 pprev = &bucklet->next;
375           }
376
377         }
378
379         if (!*currcell)             /* everything moved */
380           lib->fill--;
381         }
382
383 }
384
385 void xbt_lib_cursor_first(const xbt_lib_t lib,
386                                       xbt_lib_cursor_t * cursor)
387 {
388   XBT_DEBUG("xbt_lib_cursor_first");
389   if (!*cursor) {
390     XBT_DEBUG("Create the cursor on first use");
391     *cursor = xbt_lib_cursor_new(lib);
392   } else {
393     xbt_lib_cursor_rewind(*cursor);
394   }
395   if (lib != NULL && (*cursor)->current == NULL) {
396     xbt_lib_cursor_step(*cursor);      /* find the first element */
397   }
398 }
399
400 static xbt_lib_cursor_t xbt_lib_cursor_new(const xbt_lib_t lib)
401 {
402   xbt_lib_cursor_t res = NULL;
403
404   res = xbt_new(s_xbt_lib_cursor_t, 1);
405   res->lib = lib;
406
407   xbt_lib_cursor_rewind(res);
408
409   return res;
410 }
411
412 static void xbt_lib_cursor_rewind(xbt_lib_cursor_t cursor)
413 {
414   XBT_DEBUG("xbt_lib_cursor_rewind");
415   xbt_assert(cursor);
416
417   cursor->line = 0;
418   if (cursor->lib != NULL) {
419     cursor->current = cursor->lib->table[0];
420   } else {
421     cursor->current = NULL;
422   }
423 }
424
425 int xbt_lib_cursor_get_or_free(xbt_lib_cursor_t * cursor,
426                                            char **key, void **data)
427 {
428
429   xbt_libelm_t current;
430
431   XBT_DEBUG("xbt_lib_get_or_free");
432
433   if (!cursor || !(*cursor))
434     return FALSE;
435
436   current = (*cursor)->current;
437   if (current == NULL) {        /* no data left */
438     xbt_lib_cursor_free(cursor);
439     return FALSE;
440   }
441
442   *key = current->key;
443   *data = &(current->content);
444   return TRUE;
445 }
446
447 static void xbt_lib_cursor_free(xbt_lib_cursor_t * cursor)
448 {
449   if (*cursor) {
450     xbt_free(*cursor);
451     *cursor = NULL;
452   }
453 }
454
455 void xbt_lib_cursor_step(xbt_lib_cursor_t cursor)
456 {
457   xbt_libelm_t current;
458   int line;
459
460   XBT_DEBUG("xbt_lib_cursor_step");
461   xbt_assert(cursor);
462
463   current = cursor->current;
464   line = cursor->line;
465
466   if (cursor->lib != NULL) {
467
468     if (current != NULL) {
469       XBT_DEBUG("current is not null, take the next element");
470       current = current->next;
471       XBT_DEBUG("next element: %p", current);
472     }
473
474     while (current == NULL && ++line <= cursor->lib->table_size) {
475       XBT_DEBUG("current is NULL, take the next line");
476       current = cursor->lib->table[line];
477       XBT_DEBUG("element in the next line: %p", current);
478     }
479     XBT_DEBUG("search finished, current = %p, line = %d", current, line);
480
481     cursor->current = current;
482     cursor->line = line;
483   }
484 }