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   xbt_lib_t l = *lib;
  89
  90   if (l) {
  91     table_size = l->table_size;
  92     table = l->table;
  93
  94     for (i = 0; l->count && i <= table_size; i++) {
  95       current = table[i];
  96       while (current != NULL) {
  97                         previous = current;
  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]);
 103                 xbt_free(previous);
 104                         l->count--;
 105       }
 106     }
 107     xbt_free(table);
 108     xbt_free(l->free_f);
 109     xbt_free(l);
 110     l = NULL;
 111   }
 112 }
 113
 114 int xbt_lib_add_level(xbt_lib_t lib, void_f_pvoid_t free_f)
 115 {
 116         XBT_DEBUG("xbt_lib_add_level");
 117
 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++;
 121 }
 122
 123 void xbt_lib_set(xbt_lib_t lib, const char *name, int level, void *obj)
 124 {
 125         XBT_DEBUG("xbt_lib_set key '%s' with object '%p'",name,obj);
 126         xbt_lib_set_ext(lib, name, strlen(name),level, obj);
 127 }
 128
 129 void *xbt_lib_get_or_null(xbt_lib_t lib, const char *key, int level)
 130 {
 131         unsigned int hash_code = xbt_lib_hash(key);
 132         xbt_libelm_t current;
 133
 134         if(!lib) xbt_die("Lib is NULL!");
 135
 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;
 140
 141         if (current == NULL)
 142         return NULL;
 143
 144         return (&(current->content))[level];
 145 }
 146
 147 static void *lib_mallocator_new_f(void)
 148 {
 149   return xbt_new(s_xbt_lib_t, 1);
 150 }
 151
 152 static void lib_mallocator_free_f(void *lib)
 153 {
 154   xbt_free(lib);
 155 }
 156
 157 static void lib_mallocator_reset_f(void *lib)
 158 {
 159   /* nothing to do because all fields are
 160    * initialized in xbt_dict_new
 161    */
 162 }
 163
 164 void xbt_lib_reset(xbt_lib_t *lib)
 165 {
 166   XBT_DEBUG("xbt_lib_reset");
 167   int i,j;
 168   xbt_libelm_t current, next;
 169   xbt_lib_t l = *lib;
 170   int levels = l->levels;
 171   if(!l) xbt_die("Lib is NULL!");
 172
 173   if (l->count == 0)
 174     return;
 175
 176   for (i = 0; i <= l->table_size; i++) {
 177     current = l->table[i];
 178     while (current) {
 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]);
 184         xbt_free(current);
 185         current = next;
 186     }
 187     l->table[i] = NULL;
 188   }
 189   xbt_free(l->free_f);
 190   l->count = 0;
 191   l->fill = 0;
 192   l->levels = 0;
 193   l->free_f = NULL;
 194 }
 195
 196 int xbt_lib_length(xbt_lib_t lib)
 197 {
 198   if(!lib) xbt_die("Lib is NULL!");
 199   return lib->count;
 200 }
 201
 202 static void xbt_lib_set_ext(xbt_lib_t lib,
 203                             const char *key,
 204                             int key_len,
 205                             int level,
 206                             void *data)
 207 {
 208
 209   unsigned int hash_code = xbt_lib_hash_ext(key, key_len);
 210
 211   xbt_libelm_t current, previous = NULL;
 212   if(!lib) xbt_die("Lib is NULL!");
 213
 214   XBT_DEBUG("ADD '%.*s' hash = '%d', size = '%d', & = '%d' to level : %d",
 215                   key_len,
 216                   key,
 217                   hash_code,
 218           lib->table_size,
 219           hash_code & lib->table_size,
 220           level);
 221
 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))) {
 226     previous = current;
 227     current = current->next;
 228   }
 229
 230   if (current == NULL) {/* this key doesn't exist yet */
 231                 current = xbt_libelm_new(key, key_len, hash_code, data,level,lib->levels);
 232                 lib->count++;
 233                 if (previous == NULL) {
 234                 lib->table[hash_code & lib->table_size] = current;
 235                 lib->fill++;
 236                 if ((lib->fill * 100) / (lib->table_size + 1) > MAX_FILL_PERCENT)
 237                   xbt_lib_rehash(lib);
 238                 } else {
 239                 previous->next = current;
 240                 }
 241   }
 242   else
 243           if( (&(current->content))[level] == NULL )/* this key exist but level is empty */
 244           {
 245                   (&(current->content))[level] = data;
 246           }
 247           else
 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]);
 254                         }
 255                         (&(current->content))[level] = data;
 256           }
 257 }
 258
 259 /**
 260  * Returns the hash code of a string.
 261  */
 262 static unsigned int xbt_lib_hash_ext(const char *str,
 263                                                  int str_len)
 264 {
 265
 266
 267 #ifdef DJB2_HASH_FUNCTION
 268   /* fast implementation of djb2 algorithm */
 269   int c;
 270   register unsigned int hash = 5381;
 271
 272   while (str_len--) {
 273     c = *str++;
 274     hash = ((hash << 5) + hash) + c;    /* hash * 33 + c */
 275   }
 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 */
 280
 281   while (bp < be) {
 282     /* multiply by the 32 bit FNV magic prime mod 2^32 */
 283     hash +=
 284         (hash << 1) + (hash << 4) + (hash << 7) + (hash << 8) +
 285         (hash << 24);
 286
 287     /* xor the bottom with the current octet */
 288     hash ^= (unsigned int) *bp++;
 289   }
 290
 291 # else
 292   register unsigned int hash = 0;
 293
 294   while (str_len--) {
 295     hash += (*str) * (*str);
 296     str++;
 297   }
 298 #endif
 299
 300   return hash;
 301 }
 302
 303 static unsigned int xbt_lib_hash(const char *str)
 304 {
 305 #ifdef DJB2_HASH_FUNCTION
 306   /* fast implementation of djb2 algorithm */
 307   int c;
 308   register unsigned int hash = 5381;
 309
 310   while ((c = *str++)) {
 311     hash = ((hash << 5) + hash) + c;    /* hash * 33 + c */
 312   }
 313
 314 # elif defined(FNV_HASH_FUNCTION)
 315   register unsigned int hash = 0x811c9dc5;
 316
 317   while (*str) {
 318     /* multiply by the 32 bit FNV magic prime mod 2^32 */
 319     hash +=
 320         (hash << 1) + (hash << 4) + (hash << 7) + (hash << 8) +
 321         (hash << 24);
 322
 323     /* xor the bottom with the current byte */
 324     hash ^= (unsigned int) *str++;
 325   }
 326
 327 # else
 328   register unsigned int hash = 0;
 329
 330   while (*str) {
 331     hash += (*str) * (*str);
 332     str++;
 333   }
 334 #endif
 335   return hash;
 336 }
 337
 338 static void xbt_lib_rehash(xbt_lib_t lib)
 339 {
 340         const int oldsize = lib->table_size + 1;
 341         register int newsize = oldsize * 2;
 342         register int i;
 343         register xbt_libelm_t *currcell;
 344         register xbt_libelm_t *twincell;
 345         register xbt_libelm_t bucklet;
 346         register xbt_libelm_t *pprev;
 347
 348         currcell =
 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);
 355
 356         for (i = 0; i < oldsize; i++, currcell++) {
 357         if (!*currcell)             /* empty cell */
 358           continue;
 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;
 368                 if (!*twincell)
 369                   lib->fill++;
 370                 *twincell = bucklet;
 371                 continue;
 372           } else {
 373                 pprev = &bucklet->next;
 374           }
 375
 376         }
 377
 378         if (!*currcell)             /* everything moved */
 379           lib->fill--;
 380         }
 381
 382 }
 383
 384 void xbt_lib_cursor_first(const xbt_lib_t lib,
 385                                       xbt_lib_cursor_t * cursor)
 386 {
 387   XBT_DEBUG("xbt_lib_cursor_first");
 388   if (!*cursor) {
 389     XBT_DEBUG("Create the cursor on first use");
 390     *cursor = xbt_lib_cursor_new(lib);
 391   } else {
 392     xbt_lib_cursor_rewind(*cursor);
 393   }
 394   if (lib != NULL && (*cursor)->current == NULL) {
 395     xbt_lib_cursor_step(*cursor);      /* find the first element */
 396   }
 397 }
 398
 399 static xbt_lib_cursor_t xbt_lib_cursor_new(const xbt_lib_t lib)
 400 {
 401   xbt_lib_cursor_t res = NULL;
 402
 403   res = xbt_new(s_xbt_lib_cursor_t, 1);
 404   res->lib = lib;
 405
 406   xbt_lib_cursor_rewind(res);
 407
 408   return res;
 409 }
 410
 411 static void xbt_lib_cursor_rewind(xbt_lib_cursor_t cursor)
 412 {
 413   XBT_DEBUG("xbt_lib_cursor_rewind");
 414   xbt_assert(cursor);
 415
 416   cursor->line = 0;
 417   if (cursor->lib != NULL) {
 418     cursor->current = cursor->lib->table[0];
 419   } else {
 420     cursor->current = NULL;
 421   }
 422 }
 423
 424 int xbt_lib_cursor_get_or_free(xbt_lib_cursor_t * cursor,
 425                                            char **key, void **data)
 426 {
 427
 428   xbt_libelm_t current;
 429
 430   XBT_DEBUG("xbt_lib_get_or_free");
 431
 432   if (!cursor || !(*cursor))
 433     return FALSE;
 434
 435   current = (*cursor)->current;
 436   if (current == NULL) {        /* no data left */
 437     xbt_lib_cursor_free(cursor);
 438     return FALSE;
 439   }
 440
 441   *key = current->key;
 442   *data = &(current->content);
 443   return TRUE;
 444 }
 445
 446 static void xbt_lib_cursor_free(xbt_lib_cursor_t * cursor)
 447 {
 448   if (*cursor) {
 449     xbt_free(*cursor);
 450     *cursor = NULL;
 451   }
 452 }
 453
 454 void xbt_lib_cursor_step(xbt_lib_cursor_t cursor)
 455 {
 456   xbt_libelm_t current;
 457   int line;
 458
 459   XBT_DEBUG("xbt_lib_cursor_step");
 460   xbt_assert(cursor);
 461
 462   current = cursor->current;
 463   line = cursor->line;
 464
 465   if (cursor->lib != NULL) {
 466
 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);
 471     }
 472
 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);
 477     }
 478     XBT_DEBUG("search finished, current = %p, line = %d", current, line);
 479
 480     cursor->current = current;
 481     cursor->line = line;
 482   }
 483 }