src/lib/data/evas_hash.c

   1 /*
   2  * vim:ts=8:sw=3:sts=8:noexpandtab:cino=>5n-3f0^-2{2
   3  */
   4
   5 #ifdef HAVE_CONFIG_H
   6 # include "config.h"
   7 #endif
   8
   9 #include <stdlib.h>
  10 #include <string.h>
  11
  12 #include "Evas_Data.h"
  13
  14 typedef struct _Evas_Hash_El Evas_Hash_El;
  15
  16 struct _Evas_Hash_El
  17 {
  18    Evas_Object_List  _list_data;
  19    const char       *key;
  20    void             *data;
  21 };
  22
  23 static inline int _evas_hash_gen(const char *key);
  24
  25 static int _evas_hash_alloc_error = 0;
  26
  27 static inline int
  28 _evas_hash_gen(const char *key)
  29 {
  30    unsigned int hash_num = 5381;
  31    const unsigned char *ptr;
  32
  33    if (!key) return 0;
  34    for (ptr = (unsigned char *)key; *ptr; ptr++)
  35      hash_num = (hash_num * 33) ^ *ptr;
  36
  37    hash_num &= 0xff;
  38    return (int)hash_num;
  39 }
  40
  41 /**
  42  * @defgroup Evas_Hash_Data Hash Data Functions
  43  *
  44  * Functions that add, access or remove data from hashes.
  45  *
  46  * The following example shows how to add and then access data in a
  47  * hash table:
  48  * @code
  49  * Evas_Hash *hash = NULL;
  50  * extern void *my_data;
  51  *
  52  * hash = evas_hash_add(hash, "My Data", my_data);
  53  * if (evas_hash_alloc_error())
  54  *   {
  55  *     fprintf(stderr, "ERROR: Memory is low. Hash allocation failed.\n");
  56  *     exit(-1);
  57  *   }
  58  * if (evas_hash_find(hash, "My Data") == my_data)
  59  *   {
  60  *     printf("My Data inserted and successfully found.\n");
  61  *   }
  62  * @endcode
  63  *
  64  * What follows is another example, showing how the @ref evas_hash_del
  65  * function is used:
  66  * @code
  67  * extern Evas_Hash *hash;
  68  * extern void *data;
  69  *
  70  * printf("Insert some data...\n");
  71  * hash = evas_hash_add(hash, "My Data", my_data);
  72  * printf("Removing by key...\n");
  73  * hash = evas_hash_del(hash, "My Data", NULL);
  74  * printf("Insert some more data as a NULL key...\n");
  75  * hash = evas_hash_add(hash, NULL, my_data);
  76  * printf("Removing by data as a NULL key...\n");
  77  * hash = evas_hash_del(hash, NULL, my_data);
  78  * @endcode
  79  */
  80
  81 /**
  82  * Adds an entry to the given hash table.
  83  *
  84  * @p key is expected to be a unique string within the hash table.
  85  * Otherwise, you cannot be sure which inserted data pointer will be
  86  * accessed with @ref evas_hash_find , and removed with
  87  * @ref evas_hash_del .
  88  *
  89  * Key strings are case sensitive.
  90  *
  91  * @ref evas_hash_alloc_error should be used to determine if an
  92  * allocation error occurred during this function.
  93  *
  94  * @param   hash The given hash table.  Can be @c NULL, in which case a
  95  *               new hash table is allocated and returned.
  96  * @param   key  A unique string.  Can be @c NULL.
  97  * @param   data Data to associate with the string given by @p key.
  98  * @return  Either the given hash table, or if the given value for @p
  99  *          hash is @c NULL, then a new one.  @c NULL will be returned
 100  *          if memory could not be allocated for a new table.
 101  * @ingroup Evas_Hash_Data
 102  */
 103 EAPI Evas_Hash *
 104 evas_hash_add(Evas_Hash *hash, const char *key, const void *data)
 105 {
 106    int hash_num;
 107    Evas_Hash_El *el;
 108
 109    if ((!key) || (!data)) return hash;
 110    _evas_hash_alloc_error = 0;
 111    if (!hash)
 112      {
 113         hash = calloc(1, sizeof(struct _Evas_Hash));
 114         if (!hash)
 115           {
 116              _evas_hash_alloc_error = 1;
 117              return NULL;
 118           }
 119      }
 120    if (!(el = malloc(sizeof(struct _Evas_Hash_El) + strlen(key) + 1)))
 121      {
 122         if (hash->population <= 0)
 123           {
 124              free(hash);
 125              hash = NULL;
 126           }
 127         _evas_hash_alloc_error = 1;
 128         return hash;
 129      };
 130    el->key = ((char *)el) + sizeof(struct _Evas_Hash_El);
 131    strcpy((char *) el->key, key);
 132    el->data = (void *)data;
 133    hash_num = _evas_hash_gen(key);
 134    hash->buckets[hash_num] = evas_object_list_prepend(hash->buckets[hash_num], el);
 135    hash->population++;
 136    return hash;
 137 }
 138
 139 /**
 140  * Adds an entry to the given hash table and does not duplicate the string key.
 141  *
 142  * @p key is expected to be a unique string within the hash table.
 143  * Otherwise, you cannot be sure which inserted data pointer will be
 144  * accessed with @ref evas_hash_find , and removed with
 145  * @ref evas_hash_del . This call does not make a copy of the key so it must
 146  * be a string constant or stored elsewhere (in the object being added) etc.
 147  *
 148  * Key strings are case sensitive.
 149  *
 150  * @ref evas_hash_alloc_error should be used to determine if an
 151  * allocation error occurred during this function.
 152  *
 153  * @param   hash The given hash table.  Can be @c NULL, in which case a
 154  *               new hash table is allocated and returned.
 155  * @param   key  A unique string.  Can be @c NULL.
 156  * @param   data Data to associate with the string given by @p key.
 157  * @return  Either the given hash table, or if the given value for @p
 158  *          hash is @c NULL, then a new one.  @c NULL will be returned
 159  *          if memory could not be allocated for a new table.
 160  * @ingroup Evas_Hash_Data
 161  */
 162 EAPI Evas_Hash *
 163 evas_hash_direct_add(Evas_Hash *hash, const char *key, const void *data)
 164 {
 165    int hash_num;
 166    Evas_Hash_El *el;
 167
 168    if ((!key) || (!data)) return hash;
 169    _evas_hash_alloc_error = 0;
 170    if (!hash)
 171      {
 172         hash = calloc(1, sizeof(struct _Evas_Hash));
 173         if (!hash)
 174           {
 175              _evas_hash_alloc_error = 1;
 176              return NULL;
 177           }
 178      }
 179    if (!(el = malloc(sizeof(struct _Evas_Hash_El))))
 180      {
 181         if (hash->population <= 0)
 182           {
 183              free(hash);
 184              hash = NULL;
 185           }
 186         _evas_hash_alloc_error = 1;
 187         return hash;
 188      };
 189    el->key = key;
 190    el->data = (void *)data;
 191    hash_num = _evas_hash_gen(key);
 192    hash->buckets[hash_num] = evas_object_list_prepend(hash->buckets[hash_num], el);
 193    hash->population++;
 194    return hash;
 195 }
 196
 197 /**
 198  * Removes the entry identified by @p key or @p data from the given
 199  * hash table.
 200  *
 201  * If @p key is @c NULL, then @p data is used to find a match to
 202  * remove.
 203  *
 204  * @param   hash The given hash table.
 205  * @param   key  The key string.  Can be @c NULL.
 206  * @param   data The data pointer to remove if @p key is @c NULL.
 207  *               Otherwise, not required and can be @c NULL.
 208  * @return  The modified hash table.  If there are no entries left, the
 209  *          hash table will be freed and @c NULL will be returned.
 210  * @ingroup Evas_Hash_Data
 211  */
 212 EAPI Evas_Hash *
 213 evas_hash_del(Evas_Hash *hash, const char *key, const void *data)
 214 {
 215    int hash_num;
 216    Evas_Hash_El *el;
 217    Evas_Object_List *l;
 218
 219    if (!hash) return NULL;
 220    if (!key)
 221      {
 222         int hash_num;
 223
 224         for (hash_num = 0; hash_num < 256; hash_num++)
 225           {
 226              for (l = hash->buckets[hash_num]; l; l = l->next)
 227                {
 228                   el = (Evas_Hash_El *)l;
 229                   if (el->data == data)
 230                     {
 231                        hash->buckets[hash_num] = evas_object_list_remove(hash->buckets[hash_num], el);
 232                        free(el);
 233                        hash->population--;
 234                        if (hash->population <= 0)
 235                          {
 236                             free(hash);
 237                             hash = NULL;
 238                          }
 239                        return hash;
 240                     }
 241                }
 242           }
 243      }
 244    else
 245      {
 246         hash_num = _evas_hash_gen(key);
 247         for (l = hash->buckets[hash_num]; l; l = l->next)
 248           {
 249              el = (Evas_Hash_El *)l;
 250              if (!strcmp(el->key, key))
 251                {
 252                   hash->buckets[hash_num] = evas_object_list_remove(hash->buckets[hash_num], el);
 253                   free(el);
 254                   hash->population--;
 255                   if (hash->population <= 0)
 256                     {
 257                        free(hash);
 258                        hash = NULL;
 259                     }
 260                   return hash;
 261                }
 262           }
 263      }
 264    return hash;
 265 }
 266
 267 /**
 268  * Retrieves a specific entry in the given hash table.
 269  * @param   hash The given hash table.
 270  * @param   key  The key string of the entry to find.
 271  * @return  The data pointer for the stored entry, or @c NULL if not
 272  *          found.
 273  * @ingroup Evas_Hash_Data
 274  */
 275 EAPI void *
 276 evas_hash_find(const Evas_Hash *hash, const char *key)
 277 {
 278    int hash_num;
 279    Evas_Hash_El *el;
 280    Evas_Object_List *l;
 281
 282    _evas_hash_alloc_error = 0;
 283    if ((!hash) || (!key)) return NULL;
 284    hash_num = _evas_hash_gen(key);
 285    for (l = hash->buckets[hash_num]; l; l = l->next)
 286      {
 287         el = (Evas_Hash_El *)l;
 288         if (!strcmp(el->key, key))
 289           {
 290              if (l != hash->buckets[hash_num])
 291                {
 292                   Evas_Object_List *bucket;
 293
 294                   bucket = hash->buckets[hash_num];
 295                   bucket = evas_object_list_remove(bucket, el);
 296                   bucket = evas_object_list_prepend(bucket, el);
 297                   ((Evas_Hash *)hash)->buckets[hash_num] = bucket;
 298                }
 299              return el->data;
 300           }
 301      }
 302    return NULL;
 303 }
 304
 305 /**
 306  * Modifies the entry pointer at the specified key and returns the old entry
 307  * @param   hash The given hash table.
 308  * @param   key  The key string of the entry to modify.
 309  * @param   data The data to replace the old entry, if it exists.
 310  * @return  The data pointer for the old stored entry, or @c NULL if not
 311  *          found. If an existing entry is not found, nothing is added to the
 312  *          hash.
 313  * @ingroup Evas_Hash_Data
 314  */
 315 EAPI void *
 316 evas_hash_modify(Evas_Hash *hash, const char *key, const void *data)
 317 {
 318    int hash_num;
 319    Evas_Hash_El *el;
 320    Evas_Object_List *l;
 321
 322    _evas_hash_alloc_error = 0;
 323    if (!hash) return NULL;
 324    hash_num = _evas_hash_gen(key);
 325    for (l = hash->buckets[hash_num]; l; l = l->next)
 326      {
 327         el = (Evas_Hash_El *)l;
 328         if ((key) && (!strcmp(el->key, key)))
 329           {
 330              void *old_data;
 331
 332              if (l != hash->buckets[hash_num])
 333                {
 334                   hash->buckets[hash_num] = evas_object_list_remove(hash->buckets[hash_num], el);
 335                   hash->buckets[hash_num] = evas_object_list_prepend(hash->buckets[hash_num], el);
 336                }
 337              old_data = el->data;
 338              el->data = (void *) data;
 339              return old_data;
 340           }
 341      }
 342    return NULL;
 343 }
 344
 345 /**
 346  * @defgroup Evas_Hash_General_Group Hash General Functions
 347  *
 348  * Miscellaneous functions that operate on hash objects.
 349  */
 350
 351 /**
 352  * Retrieves the number of buckets available in the given hash table.
 353  * @param hash The given hash table.
 354  * @return @c 256 if @p hash is not @c NULL.  @c 0 otherwise.
 355  * @ingroup Evas_Hash_General_Group
 356  */
 357 EAPI int
 358 evas_hash_size(const Evas_Hash *hash)
 359 {
 360    if (!hash) return 0;
 361    return 256;
 362 }
 363
 364 /**
 365  * @todo Complete polishing documentation for evas_hash.c. The
 366  * functions' docs may be grouped, but they need some simplification.
 367  */
 368
 369 /**
 370  * Free an entire hash table
 371  * @param hash The hash table to be freed
 372  *
 373  * This function frees up all the memory allocated to storing the specified
 374  * hash tale pointed to by @p hash. Any entries in the table that the program
 375  * has no more pointers for elsewhere may now be lost, so this should only be
 376  * called if the program has lready freed any allocated data in the hash table
 377  * or has the pointers for data in teh table stored elswehere as well.
 378  *
 379  * Example:
 380  * @code
 381  * extern Evas_Hash *hash;
 382  *
 383  * evas_hash_free(hash);
 384  * hash = NULL;
 385  * @endcode
 386  * @ingroup Evas_Hash_General_Group
 387  */
 388 EAPI void
 389 evas_hash_free(Evas_Hash *hash)
 390 {
 391    int i, size;
 392
 393    if (!hash) return;
 394    size = evas_hash_size(hash);
 395    for (i = 0; i < size; i++)
 396      {
 397         while (hash->buckets[i])
 398           {
 399              Evas_Hash_El *el;
 400
 401              el = (Evas_Hash_El *)hash->buckets[i];
 402              hash->buckets[i] = evas_object_list_remove(hash->buckets[i], el);
 403              free(el);
 404           }
 405      }
 406    free(hash);
 407 }
 408
 409 /**
 410  * Call a function on every member stored in the hash table
 411  * @param hash The hash table whose members will be walked
 412  * @param func The function to call on each parameter
 413  * @param fdata The data pointer to pass to the function being called
 414  *
 415  * This function goes through every entry in the hash table @p hash and calls
 416  * the function @p func on each member. The function should NOT modify the
 417  * hash table contents if it returns 1. IF the hash table contents are
 418  * modified by this function or the function wishes to stop processing it must
 419  * return 0, otherwise return 1 to keep processing.
 420  *
 421  * Example:
 422  * @code
 423  * extern Evas_Hash *hash;
 424  *
 425  * Evas_Bool hash_fn(Evas_Hash *hash, const char *key, void *data, void *fdata)
 426  * {
 427  *   printf("Func data: %s, Hash entry: %s / %p\n", fdata, key, data);
 428  *   return 1;
 429  * }
 430  *
 431  * int main(int argc, char **argv)
 432  * {
 433  *   char *hash_fn_data;
 434  *
 435  *   hash_fn_data = strdup("Hello World");
 436  *   evas_hash_foreach(hash, hash_fn, hash_fn_data);
 437  *   free(hash_fn_data);
 438  * }
 439  * @endcode
 440  * @ingroup Evas_Hash_General_Group
 441  */
 442 EAPI void
 443 evas_hash_foreach(const Evas_Hash *hash, Evas_Bool (*func) (const Evas_Hash *hash, const char *key, void *data, void *fdata), const void *fdata)
 444 {
 445    int i, size;
 446
 447    if (!hash) return;
 448    size = evas_hash_size(hash);
 449    for (i = 0; i < size; i++)
 450      {
 451         Evas_Object_List *l, *next_l;
 452
 453         for (l = hash->buckets[i]; l;)
 454           {
 455              Evas_Hash_El *el;
 456
 457              next_l = l->next;
 458              el = (Evas_Hash_El *)l;
 459              if (!func(hash, el->key, el->data, (void *)fdata)) return;
 460              l = next_l;
 461           }
 462      }
 463 }
 464
 465 /**
 466  * Return memory allocation failure flag after an function requiring allocation
 467  * @return The state of the allocation flag
 468  *
 469  * This function returns the state of the memory allocation flag. This flag is
 470  * set if memory allocations fail during evas_hash_add() calls. If they do, 1
 471  * will be returned, otherwise 0 will be returned. The flag will remain in its
 472  * current state until the next call that requires allocation is called, and
 473  * is then reset.
 474  *
 475  * Example:
 476  * @code
 477  * Evas_Hash *hash = NULL;
 478  * extern void *my_data;
 479  *
 480  * hash = evas_hash_add(hash, "My Data", my_data);
 481  * if (evas_hash_alloc_error())
 482  *   {
 483  *     fprintf(stderr, "ERROR: Memory is low. Hash allocation failed.\n");
 484  *     exit(-1);
 485  *   }
 486  * if (evas_hash_find(hash, "My Data") == my_data)
 487  *   {
 488  *     printf("My Data inserted and successfully found.\n");
 489  *   }
 490  * @endcode
 491  * @ingroup Evas_Hash_General_Group
 492  */
 493 EAPI int
 494 evas_hash_alloc_error(void)
 495 {
 496    return _evas_hash_alloc_error;
 497 }