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