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 }