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;
89 // if ( *dict ) xbt_dict_dump_sizes(*dict);
91 if (lib != NULL && *lib != NULL) {
92 table_size = (*lib)->table_size;
93 table = (*lib)->table;
95 for (i = 0; (*lib)->count && i <= table_size; i++) {
97 while (current != NULL) {
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]);
109 xbt_free((*lib)->free_f);
115 int xbt_lib_add_level(xbt_lib_t lib, void_f_pvoid_t free_f)
117 XBT_DEBUG("xbt_lib_add_level");
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++;
124 void xbt_lib_set(xbt_lib_t lib, const char *name, int level, void *obj)
126 XBT_DEBUG("xbt_lib_set key '%s' with object '%p'",name,obj);
127 xbt_lib_set_ext(lib, name, strlen(name),level, obj);
130 void *xbt_lib_get_or_null(xbt_lib_t lib, const char *key, int level)
132 unsigned int hash_code = xbt_lib_hash(key);
133 xbt_libelm_t current;
135 if(!lib) xbt_die("Lib is NULL!");
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;
145 return (&(current->content))[level];
148 static void *lib_mallocator_new_f(void)
150 return xbt_new(s_xbt_lib_t, 1);
153 static void lib_mallocator_free_f(void *lib)
158 static void lib_mallocator_reset_f(void *lib)
160 /* nothing to do because all fields are
161 * initialized in xbt_dict_new
165 void xbt_lib_reset(xbt_lib_t *lib)
167 XBT_DEBUG("xbt_lib_reset");
169 xbt_libelm_t current, next;
171 int levels = l->levels;
172 if(!(*lib)) xbt_die("Lib is NULL!");
177 for (i = 0; i <= l->table_size; i++) {
178 current = l->table[i];
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]);
197 int xbt_lib_length(xbt_lib_t lib)
199 if(!lib) xbt_die("Lib is NULL!");
203 static void xbt_lib_set_ext(xbt_lib_t lib,
210 unsigned int hash_code = xbt_lib_hash_ext(key, key_len);
212 xbt_libelm_t current, previous = NULL;
213 if(!lib) xbt_die("Lib is NULL!");
215 XBT_DEBUG("ADD '%.*s' hash = '%d', size = '%d', & = '%d' to level : %d",
220 hash_code & lib->table_size,
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))) {
228 current = current->next;
231 if (current == NULL) {/* this key doesn't exist yet */
232 current = xbt_libelm_new(key, key_len, hash_code, data,level,lib->levels);
234 if (previous == NULL) {
235 lib->table[hash_code & lib->table_size] = current;
237 if ((lib->fill * 100) / (lib->table_size + 1) > MAX_FILL_PERCENT)
240 previous->next = current;
244 if( (&(current->content))[level] == NULL )/* this key exist but level is empty */
246 (&(current->content))[level] = data;
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]);
256 (&(current->content))[level] = data;
261 * Returns the hash code of a string.
263 static unsigned int xbt_lib_hash_ext(const char *str,
268 #ifdef DJB2_HASH_FUNCTION
269 /* fast implementation of djb2 algorithm */
271 register unsigned int hash = 5381;
275 hash = ((hash << 5) + hash) + c; /* hash * 33 + c */
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 */
283 /* multiply by the 32 bit FNV magic prime mod 2^32 */
285 (hash << 1) + (hash << 4) + (hash << 7) + (hash << 8) +
288 /* xor the bottom with the current octet */
289 hash ^= (unsigned int) *bp++;
293 register unsigned int hash = 0;
296 hash += (*str) * (*str);
304 static unsigned int xbt_lib_hash(const char *str)
306 #ifdef DJB2_HASH_FUNCTION
307 /* fast implementation of djb2 algorithm */
309 register unsigned int hash = 5381;
311 while ((c = *str++)) {
312 hash = ((hash << 5) + hash) + c; /* hash * 33 + c */
315 # elif defined(FNV_HASH_FUNCTION)
316 register unsigned int hash = 0x811c9dc5;
319 /* multiply by the 32 bit FNV magic prime mod 2^32 */
321 (hash << 1) + (hash << 4) + (hash << 7) + (hash << 8) +
324 /* xor the bottom with the current byte */
325 hash ^= (unsigned int) *str++;
329 register unsigned int hash = 0;
332 hash += (*str) * (*str);
339 static void xbt_lib_rehash(xbt_lib_t lib)
341 const int oldsize = lib->table_size + 1;
342 register int newsize = oldsize * 2;
344 register xbt_libelm_t *currcell;
345 register xbt_libelm_t *twincell;
346 register xbt_libelm_t bucklet;
347 register xbt_libelm_t *pprev;
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);
357 for (i = 0; i < oldsize; i++, currcell++) {
358 if (!*currcell) /* empty cell */
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;
374 pprev = &bucklet->next;
379 if (!*currcell) /* everything moved */
385 void xbt_lib_cursor_first(const xbt_lib_t lib,
386 xbt_lib_cursor_t * cursor)
388 XBT_DEBUG("xbt_lib_cursor_first");
390 XBT_DEBUG("Create the cursor on first use");
391 *cursor = xbt_lib_cursor_new(lib);
393 xbt_lib_cursor_rewind(*cursor);
395 if (lib != NULL && (*cursor)->current == NULL) {
396 xbt_lib_cursor_step(*cursor); /* find the first element */
400 static xbt_lib_cursor_t xbt_lib_cursor_new(const xbt_lib_t lib)
402 xbt_lib_cursor_t res = NULL;
404 res = xbt_new(s_xbt_lib_cursor_t, 1);
407 xbt_lib_cursor_rewind(res);
412 static void xbt_lib_cursor_rewind(xbt_lib_cursor_t cursor)
414 XBT_DEBUG("xbt_lib_cursor_rewind");
418 if (cursor->lib != NULL) {
419 cursor->current = cursor->lib->table[0];
421 cursor->current = NULL;
425 int xbt_lib_cursor_get_or_free(xbt_lib_cursor_t * cursor,
426 char **key, void **data)
429 xbt_libelm_t current;
431 XBT_DEBUG("xbt_lib_get_or_free");
433 if (!cursor || !(*cursor))
436 current = (*cursor)->current;
437 if (current == NULL) { /* no data left */
438 xbt_lib_cursor_free(cursor);
443 *data = &(current->content);
447 static void xbt_lib_cursor_free(xbt_lib_cursor_t * cursor)
455 void xbt_lib_cursor_step(xbt_lib_cursor_t cursor)
457 xbt_libelm_t current;
460 XBT_DEBUG("xbt_lib_cursor_step");
463 current = cursor->current;
466 if (cursor->lib != NULL) {
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);
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);
479 XBT_DEBUG("search finished, current = %p, line = %d", current, line);
481 cursor->current = current;