4 * Created on: 16 mars 2011
10 #include "xbt/misc.h" /* SG_BEGIN_DECL */
11 #include "xbt/mallocator.h"
14 #include "xbt_modinter.h"
17 #define DJB2_HASH_FUNCTION
18 //#define FNV_HASH_FUNCTION
20 XBT_LOG_NEW_DEFAULT_SUBCATEGORY(xbt_lib, xbt,
21 "Libraries provide the same functionalities than hash tables");
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);
28 static void xbt_lib_set_ext(xbt_lib_t lib,const char *key,
29 int key_len, int level, void *data);
31 static unsigned int xbt_lib_hash_ext(const char *str,
33 static unsigned int xbt_lib_hash(const char *str);
34 static void xbt_lib_rehash(xbt_lib_t lib);
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);
41 /*####[ Code ]###############################################################*/
43 unsigned int xbt_lib_size(xbt_lib_t lib)
45 return (lib ? (unsigned int) lib->count : (unsigned int) 0);
48 static xbt_libelm_t xbt_libelm_new(const char *key,
50 unsigned int hash_code,
51 void *content,int level, int level_numbers)
53 xbt_libelm_t element = xbt_malloc0(sizeof (s_xbt_libelm_t) + sizeof(void *)*(level_numbers-1));
55 element->key = xbt_new(char, key_len + 1);
56 memcpy((void *) element->key, (void *) key, key_len);
57 element->key[key_len] = '\0';
59 element->key_len = key_len;
60 element->hash_code = hash_code;
62 (&(element->content))[level] = content;
68 xbt_lib_t xbt_lib_new(void)
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);
82 void xbt_lib_free(xbt_lib_t * lib)
85 xbt_libelm_t current, previous;
91 table_size = l->table_size;
94 for (i = 0; l->count && i <= table_size; i++) {
96 while (current != NULL) {
98 current = current->next;
99 xbt_free(previous->key);
100 for(j=0; j< l->levels; j++)
101 if((&(previous->content))[j])
102 l->free_f[j]( (&(previous->content))[j]);
114 int xbt_lib_add_level(xbt_lib_t lib, void_f_pvoid_t free_f)
116 XBT_DEBUG("xbt_lib_add_level");
118 lib->free_f = realloc(lib->free_f,sizeof(void_f_pvoid_t)*(lib->levels+1));
119 lib->free_f[lib->levels]=free_f;
120 return lib->levels++;
123 void xbt_lib_set(xbt_lib_t lib, const char *name, int level, void *obj)
125 XBT_DEBUG("xbt_lib_set key '%s' with object '%p'",name,obj);
126 xbt_lib_set_ext(lib, name, strlen(name),level, obj);
129 void *xbt_lib_get_or_null(xbt_lib_t lib, const char *key, int level)
131 unsigned int hash_code = xbt_lib_hash(key);
132 xbt_libelm_t current;
134 if(!lib) xbt_die("Lib is NULL!");
136 current = lib->table[hash_code & lib->table_size];
137 while (current != NULL &&
138 (hash_code != current->hash_code || strcmp(key, current->key)))
139 current = current->next;
144 return (&(current->content))[level];
147 static void *lib_mallocator_new_f(void)
149 return xbt_new(s_xbt_lib_t, 1);
152 static void lib_mallocator_free_f(void *lib)
157 static void lib_mallocator_reset_f(void *lib)
159 /* nothing to do because all fields are
160 * initialized in xbt_dict_new
164 void xbt_lib_reset(xbt_lib_t *lib)
166 XBT_DEBUG("xbt_lib_reset");
168 xbt_libelm_t current, next;
170 int levels = l->levels;
171 if(!l) xbt_die("Lib is NULL!");
176 for (i = 0; i <= l->table_size; i++) {
177 current = l->table[i];
179 next = current->next;
180 xbt_free(current->key);
181 for(j=0; j< levels; j++)
182 if((&(current->content))[j] && (l->free_f[j]))
183 l->free_f[j]((&(current->content))[j]);
196 int xbt_lib_length(xbt_lib_t lib)
198 if(!lib) xbt_die("Lib is NULL!");
202 static void xbt_lib_set_ext(xbt_lib_t lib,
209 unsigned int hash_code = xbt_lib_hash_ext(key, key_len);
211 xbt_libelm_t current, previous = NULL;
212 if(!lib) xbt_die("Lib is NULL!");
214 XBT_DEBUG("ADD '%.*s' hash = '%d', size = '%d', & = '%d' to level : %d",
219 hash_code & lib->table_size,
222 current = lib->table[hash_code & lib->table_size];
223 while (current != NULL &&
224 (hash_code != current->hash_code || key_len != current->key_len
225 || memcmp(key, current->key, key_len))) {
227 current = current->next;
230 if (current == NULL) {/* this key doesn't exist yet */
231 current = xbt_libelm_new(key, key_len, hash_code, data,level,lib->levels);
233 if (previous == NULL) {
234 lib->table[hash_code & lib->table_size] = current;
236 if ((lib->fill * 100) / (lib->table_size + 1) > MAX_FILL_PERCENT)
239 previous->next = current;
243 if( (&(current->content))[level] == NULL )/* this key exist but level is empty */
245 (&(current->content))[level] = data;
248 {/* there is already an element with the same key: overwrite it */
249 XBT_DEBUG("Replace %.*s by %.*s under key %.*s",
250 key_len, (char *) (&(current->content))[level],
251 key_len, (char *) data, key_len, (char *) key);
252 if (current->content != NULL) {
253 free((&(current->content))[level]);
255 (&(current->content))[level] = data;
260 * Returns the hash code of a string.
262 static unsigned int xbt_lib_hash_ext(const char *str,
267 #ifdef DJB2_HASH_FUNCTION
268 /* fast implementation of djb2 algorithm */
270 register unsigned int hash = 5381;
274 hash = ((hash << 5) + hash) + c; /* hash * 33 + c */
276 # elif defined(FNV_HASH_FUNCTION)
277 register unsigned int hash = 0x811c9dc5;
278 unsigned char *bp = (unsigned char *) str; /* start of buffer */
279 unsigned char *be = bp + str_len; /* beyond end of buffer */
282 /* multiply by the 32 bit FNV magic prime mod 2^32 */
284 (hash << 1) + (hash << 4) + (hash << 7) + (hash << 8) +
287 /* xor the bottom with the current octet */
288 hash ^= (unsigned int) *bp++;
292 register unsigned int hash = 0;
295 hash += (*str) * (*str);
303 static unsigned int xbt_lib_hash(const char *str)
305 #ifdef DJB2_HASH_FUNCTION
306 /* fast implementation of djb2 algorithm */
308 register unsigned int hash = 5381;
310 while ((c = *str++)) {
311 hash = ((hash << 5) + hash) + c; /* hash * 33 + c */
314 # elif defined(FNV_HASH_FUNCTION)
315 register unsigned int hash = 0x811c9dc5;
318 /* multiply by the 32 bit FNV magic prime mod 2^32 */
320 (hash << 1) + (hash << 4) + (hash << 7) + (hash << 8) +
323 /* xor the bottom with the current byte */
324 hash ^= (unsigned int) *str++;
328 register unsigned int hash = 0;
331 hash += (*str) * (*str);
338 static void xbt_lib_rehash(xbt_lib_t lib)
340 const int oldsize = lib->table_size + 1;
341 register int newsize = oldsize * 2;
343 register xbt_libelm_t *currcell;
344 register xbt_libelm_t *twincell;
345 register xbt_libelm_t bucklet;
346 register xbt_libelm_t *pprev;
349 (xbt_libelm_t *) xbt_realloc((char *) lib->table,
350 newsize * (sizeof(xbt_libelm_t) + sizeof(void*)*(lib->levels - 1)));
351 memset(&currcell[oldsize], 0, oldsize * (sizeof(xbt_libelm_t) + sizeof(void*)*(lib->levels - 1))); /* zero second half */
352 lib->table_size = --newsize;
353 lib->table = currcell;
354 XBT_DEBUG("REHASH (%d->%d)", oldsize, newsize);
356 for (i = 0; i < oldsize; i++, currcell++) {
357 if (!*currcell) /* empty cell */
359 twincell = currcell + oldsize;
360 for (pprev = currcell, bucklet = *currcell; bucklet; bucklet = *pprev) {
361 /* Since we use "& size" instead of "%size" and since the size was doubled,
362 each bucklet of this cell must either :
363 - stay in cell i (ie, currcell)
364 - go to the cell i+oldsize (ie, twincell) */
365 if ((bucklet->hash_code & newsize) != i) { /* Move to b */
366 *pprev = bucklet->next;
367 bucklet->next = *twincell;
373 pprev = &bucklet->next;
378 if (!*currcell) /* everything moved */
384 void xbt_lib_cursor_first(const xbt_lib_t lib,
385 xbt_lib_cursor_t * cursor)
387 XBT_DEBUG("xbt_lib_cursor_first");
389 XBT_DEBUG("Create the cursor on first use");
390 *cursor = xbt_lib_cursor_new(lib);
392 xbt_lib_cursor_rewind(*cursor);
394 if (lib != NULL && (*cursor)->current == NULL) {
395 xbt_lib_cursor_step(*cursor); /* find the first element */
399 static xbt_lib_cursor_t xbt_lib_cursor_new(const xbt_lib_t lib)
401 xbt_lib_cursor_t res = NULL;
403 res = xbt_new(s_xbt_lib_cursor_t, 1);
406 xbt_lib_cursor_rewind(res);
411 static void xbt_lib_cursor_rewind(xbt_lib_cursor_t cursor)
413 XBT_DEBUG("xbt_lib_cursor_rewind");
417 if (cursor->lib != NULL) {
418 cursor->current = cursor->lib->table[0];
420 cursor->current = NULL;
424 int xbt_lib_cursor_get_or_free(xbt_lib_cursor_t * cursor,
425 char **key, void **data)
428 xbt_libelm_t current;
430 XBT_DEBUG("xbt_lib_get_or_free");
432 if (!cursor || !(*cursor))
435 current = (*cursor)->current;
436 if (current == NULL) { /* no data left */
437 xbt_lib_cursor_free(cursor);
442 *data = &(current->content);
446 static void xbt_lib_cursor_free(xbt_lib_cursor_t * cursor)
454 void xbt_lib_cursor_step(xbt_lib_cursor_t cursor)
456 xbt_libelm_t current;
459 XBT_DEBUG("xbt_lib_cursor_step");
462 current = cursor->current;
465 if (cursor->lib != NULL) {
467 if (current != NULL) {
468 XBT_DEBUG("current is not null, take the next element");
469 current = current->next;
470 XBT_DEBUG("next element: %p", current);
473 while (current == NULL && ++line <= cursor->lib->table_size) {
474 XBT_DEBUG("current is NULL, take the next line");
475 current = cursor->lib->table[line];
476 XBT_DEBUG("element in the next line: %p", current);
478 XBT_DEBUG("search finished, current = %p, line = %d", current, line);
480 cursor->current = current;