src/tests/evas_hash.c

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