fluid_hash.c
上传用户:tjmskj2
上传日期:2020-08-17
资源大小:577k
文件大小:37k
源码类别:

midi

开发平台:

C/C++

  1. /* GLIB - Library of useful routines for C programming
  2.  * Copyright (C) 1995-1997  Peter Mattis, Spencer Kimball and Josh MacDonald
  3.  *
  4.  * This library is free software; you can redistribute it and/or
  5.  * modify it under the terms of the GNU Lesser General Public
  6.  * License as published by the Free Software Foundation; either
  7.  * version 2 of the License, or (at your option) any later version.
  8.  *
  9.  * This library is distributed in the hope that it will be useful,
  10.  * but WITHOUT ANY WARRANTY; without even the implied warranty of
  11.  * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the GNU
  12.  * Lesser General Public License for more details.
  13.  *
  14.  * You should have received a copy of the GNU Lesser General Public
  15.  * License along with this library; if not, write to the
  16.  * Free Software Foundation, Inc., 59 Temple Place - Suite 330,
  17.  * Boston, MA 02111-1307, USA.
  18.  */
  19. /*
  20.  * Modified by the GLib Team and others 1997-2000.  See the AUTHORS
  21.  * file for a list of people on the GLib Team.  See the ChangeLog
  22.  * files for a list of changes.  These files are distributed with
  23.  * GLib at ftp://ftp.gtk.org/pub/gtk/.
  24.  *
  25.  * Adapted for FluidSynth use by Josh Green <jgreen@users.sourceforge.net>
  26.  * September 8, 2009 from glib 2.18.4
  27.  */
  28. /*
  29.  * MT safe
  30.  */
  31. #include "fluidsynth_priv.h"
  32. #include "fluid_hash.h"
  33. #include "fluid_list.h"
  34. #define HASH_TABLE_MIN_SIZE 11
  35. #define HASH_TABLE_MAX_SIZE 13845163
  36. typedef struct
  37. {
  38.   fluid_hashtable_t *hashtable;
  39.   fluid_hashnode_t *prev_node;
  40.   fluid_hashnode_t *node;
  41.   int position;
  42.   int pre_advanced; // Boolean
  43.   int version;
  44. } RealIter;
  45. /* Excerpt from glib gprimes.c */
  46. static const guint primes[] =
  47. {
  48.   11,
  49.   19,
  50.   37,
  51.   73,
  52.   109,
  53.   163,
  54.   251,
  55.   367,
  56.   557,
  57.   823,
  58.   1237,
  59.   1861,
  60.   2777,
  61.   4177,
  62.   6247,
  63.   9371,
  64.   14057,
  65.   21089,
  66.   31627,
  67.   47431,
  68.   71143,
  69.   106721,
  70.   160073,
  71.   240101,
  72.   360163,
  73.   540217,
  74.   810343,
  75.   1215497,
  76.   1823231,
  77.   2734867,
  78.   4102283,
  79.   6153409,
  80.   9230113,
  81.   13845163,
  82. };
  83. static const unsigned int nprimes = sizeof (primes) / sizeof (primes[0]);
  84. unsigned int
  85. spaced_primes_closest (unsigned int num)
  86. {
  87.   unsigned int i;
  88.   for (i = 0; i < nprimes; i++)
  89.     if (primes[i] > num)
  90.       return primes[i];
  91.   return primes[nprimes - 1];
  92. }
  93. /* End excerpt from glib gprimes.c */
  94. /*
  95.  * @hashtable: our #fluid_hashtable_t
  96.  * @key: the key to lookup against
  97.  * @hash_return: optional key hash return location
  98.  * Return value: a pointer to the described #fluid_hashnode_t pointer
  99.  *
  100.  * Performs a lookup in the hash table.  Virtually all hash operations
  101.  * will use this function internally.
  102.  *
  103.  * This function first computes the hash value of the key using the
  104.  * user's hash function.
  105.  *
  106.  * If an entry in the table matching @key is found then this function
  107.  * returns a pointer to the pointer to that entry in the table.  In
  108.  * the case that the entry is at the head of a chain, this pointer
  109.  * will be an item in the nodes[] array.  In the case that the entry
  110.  * is not at the head of a chain, this pointer will be the ->next
  111.  * pointer on the node that preceeds it.
  112.  *
  113.  * In the case that no matching entry exists in the table, a pointer
  114.  * to a %NULL pointer will be returned.  To insert a item, this %NULL
  115.  * pointer should be updated to point to the new #fluid_hashnode_t.
  116.  *
  117.  * If @hash_return is a pass-by-reference parameter.  If it is
  118.  * non-%NULL then the computed hash value is returned.  This is to
  119.  * save insertions from having to compute the hash record again for
  120.  * the new record.
  121.  */
  122. static inline fluid_hashnode_t **
  123. fluid_hashtable_lookup_node (fluid_hashtable_t *hashtable, const void *key,
  124.                              unsigned int *hash_return)
  125. {
  126.   fluid_hashnode_t **node_ptr, *node;
  127.   unsigned int hash_value;
  128.   hash_value = (* hashtable->hash_func)(key);
  129.   node_ptr = &hashtable->nodes[hash_value % hashtable->size];
  130.   if (hash_return)
  131.     *hash_return = hash_value;
  132.   /* Hash table lookup needs to be fast.
  133.    *  We therefore remove the extra conditional of testing
  134.    *  whether to call the key_equal_func or not from
  135.    *  the inner loop.
  136.    *
  137.    *  Additional optimisation: first check if our full hash
  138.    *  values are equal so we can avoid calling the full-blown
  139.    *  key equality function in most cases.
  140.    */
  141.   if (hashtable->key_equal_func)
  142.     {
  143.       while ((node = *node_ptr))
  144.         {
  145.           if (node->key_hash == hash_value &&
  146.               hashtable->key_equal_func (node->key, key))
  147.             break;
  148.           node_ptr = &(*node_ptr)->next;
  149.         }
  150.     }
  151.   else
  152.     {
  153.       while ((node = *node_ptr))
  154.         {
  155.           if (node->key == key)
  156.             break;
  157.           node_ptr = &(*node_ptr)->next;
  158.         }
  159.     }
  160.   return node_ptr;
  161. }
  162. /*
  163.  * @hashtable: our #fluid_hashtable_t
  164.  * @node_ptr_ptr: a pointer to the return value from
  165.  *   fluid_hashtable_lookup_node()
  166.  * @notify: %TRUE if the destroy notify handlers are to be called
  167.  *
  168.  * Removes a node from the hash table and updates the node count.  The
  169.  * node is freed.  No table resize is performed.
  170.  *
  171.  * If @notify is %TRUE then the destroy notify functions are called
  172.  * for the key and value of the hash node.
  173.  *
  174.  * @node_ptr_ptr is a pass-by-reference in/out parameter.  When the
  175.  * function is called, it should point to the pointer to the node to
  176.  * remove.  This level of indirection is required so that the pointer
  177.  * may be updated appropriately once the node has been removed.
  178.  *
  179.  * Before the function returns, the pointer at @node_ptr_ptr will be
  180.  * updated to point to the position in the table that contains the
  181.  * pointer to the "next" node in the chain.  This makes this function
  182.  * convenient to use from functions that iterate over the entire
  183.  * table.  If there is no further item in the chain then the
  184.  * #fluid_hashnode_t pointer will be %NULL (ie: **node_ptr_ptr == %NULL).
  185.  *
  186.  * Since the pointer in the table to the removed node is replaced with
  187.  * either a pointer to the next node or a %NULL pointer as
  188.  * appropriate, the pointer at the end of @node_ptr_ptr will never be
  189.  * modified at all.  Stay tuned. :)
  190.  */
  191. static void
  192. fluid_hashtable_remove_node (fluid_hashtable_t *hashtable,
  193.                              fluid_hashnode_t  ***node_ptr_ptr, int notify)
  194. {
  195.   fluid_hashnode_t **node_ptr, *node;
  196.   node_ptr = *node_ptr_ptr;
  197.   node = *node_ptr;
  198.   *node_ptr = node->next;
  199.   if (notify && hashtable->key_destroy_func)
  200.     hashtable->key_destroy_func (node->key);
  201.   if (notify && hashtable->value_destroy_func)
  202.     hashtable->value_destroy_func (node->value);
  203.   FLUID_FREE (node);
  204.   hashtable->nnodes--;
  205. }
  206. /*
  207.  * fluid_hashtable_remove_all_nodes:
  208.  * @hashtable: our #fluid_hashtable_t
  209.  * @notify: %TRUE if the destroy notify handlers are to be called
  210.  *
  211.  * Removes all nodes from the table.  Since this may be a precursor to
  212.  * freeing the table entirely, no resize is performed.
  213.  *
  214.  * If @notify is %TRUE then the destroy notify functions are called
  215.  * for the key and value of the hash node.
  216.  */
  217. static void
  218. fluid_hashtable_remove_all_nodes (fluid_hashtable_t *hashtable, int notify)
  219. {
  220.   fluid_hashnode_t **node_ptr;
  221.   int i;
  222.   for (i = 0; i < hashtable->size; i++)
  223.     for (node_ptr = &hashtable->nodes[i]; *node_ptr != NULL;)
  224.       fluid_hashtable_remove_node (hashtable, &node_ptr, notify);
  225.   hashtable->nnodes = 0;
  226. }
  227. /*
  228.  * fluid_hashtable_resize:
  229.  * @hashtable: our #fluid_hashtable_t
  230.  *
  231.  * Resizes the hash table to the optimal size based on the number of
  232.  * nodes currently held.  If you call this function then a resize will
  233.  * occur, even if one does not need to occur.  Use
  234.  * fluid_hashtable_maybe_resize() instead.
  235.  */
  236. static void
  237. fluid_hashtable_resize (fluid_hashtable_t *hashtable)
  238. {
  239.   fluid_hashnode_t **new_nodes;
  240.   fluid_hashnode_t *node;
  241.   fluid_hashnode_t *next;
  242.   unsigned int hash_val;
  243.   int new_size;
  244.   int i;
  245.   new_size = spaced_primes_closest (hashtable->nnodes);
  246.   new_size = (new_size < HASH_TABLE_MIN_SIZE) ? HASH_TABLE_MIN_SIZE :
  247.     ((new_size > HASH_TABLE_MAX_SIZE) ? HASH_TABLE_MAX_SIZE : new_size);
  248.   new_nodes = FLUID_ARRAY (fluid_hashnode_t *, new_size);
  249.   if (!new_nodes)
  250.   {
  251.     FLUID_LOG (FLUID_ERR, "Out of memory");
  252.     return;
  253.   }
  254.   FLUID_MEMSET (new_nodes, 0, new_size * sizeof (fluid_hashnode_t *));
  255.   for (i = 0; i < hashtable->size; i++)
  256.     for (node = hashtable->nodes[i]; node; node = next)
  257.       {
  258. next = node->next;
  259. hash_val = node->key_hash % new_size;
  260. node->next = new_nodes[hash_val];
  261. new_nodes[hash_val] = node;
  262.       }
  263.   FLUID_FREE (hashtable->nodes);
  264.   hashtable->nodes = new_nodes;
  265.   hashtable->size = new_size;
  266. }
  267. /*
  268.  * fluid_hashtable_maybe_resize:
  269.  * @hashtable: our #fluid_hashtable_t
  270.  *
  271.  * Resizes the hash table, if needed.
  272.  *
  273.  * Essentially, calls fluid_hashtable_resize() if the table has strayed
  274.  * too far from its ideal size for its number of nodes.
  275.  */
  276. static inline void
  277. fluid_hashtable_maybe_resize (fluid_hashtable_t *hashtable)
  278. {
  279.   int nnodes = hashtable->nnodes;
  280.   int size = hashtable->size;
  281.   if ((size >= 3 * nnodes && size > HASH_TABLE_MIN_SIZE) ||
  282.       (3 * size <= nnodes && size < HASH_TABLE_MAX_SIZE))
  283.     fluid_hashtable_resize (hashtable);
  284. }
  285. /**
  286.  * new_fluid_hashtable:
  287.  * @hash_func: a function to create a hash value from a key.
  288.  *   Hash values are used to determine where keys are stored within the
  289.  *   #fluid_hashtable_t data structure. The fluid_direct_hash(), fluid_int_hash() and
  290.  *   fluid_str_hash() functions are provided for some common types of keys.
  291.  *   If hash_func is %NULL, fluid_direct_hash() is used.
  292.  * @key_equal_func: a function to check two keys for equality.  This is
  293.  *   used when looking up keys in the #fluid_hashtable_t.  The fluid_direct_equal(),
  294.  *   fluid_int_equal() and fluid_str_equal() functions are provided for the most
  295.  *   common types of keys. If @key_equal_func is %NULL, keys are compared
  296.  *   directly in a similar fashion to fluid_direct_equal(), but without the
  297.  *   overhead of a function call.
  298.  *
  299.  * Creates a new #fluid_hashtable_t with a reference count of 1.
  300.  *
  301.  * Return value: a new #fluid_hashtable_t.
  302.  **/
  303. fluid_hashtable_t*
  304. new_fluid_hashtable (fluid_hash_func_t hash_func, fluid_equal_func_t key_equal_func)
  305. {
  306.   return new_fluid_hashtable_full (hash_func, key_equal_func, NULL, NULL);
  307. }
  308. /**
  309.  * new_fluid_hashtable_full:
  310.  * @hash_func: a function to create a hash value from a key.
  311.  * @key_equal_func: a function to check two keys for equality.
  312.  * @key_destroy_func: a function to free the memory allocated for the key
  313.  *   used when removing the entry from the #fluid_hashtable_t or %NULL if you
  314.  *   don't want to supply such a function.
  315.  * @value_destroy_func: a function to free the memory allocated for the
  316.  *   value used when removing the entry from the #fluid_hashtable_t or %NULL if
  317.  *   you don't want to supply such a function.
  318.  *
  319.  * Creates a new #fluid_hashtable_t like fluid_hashtable_new() with a reference count
  320.  * of 1 and allows to specify functions to free the memory allocated for the
  321.  * key and value that get called when removing the entry from the #fluid_hashtable_t.
  322.  *
  323.  * Return value: a new #fluid_hashtable_t.
  324.  **/
  325. fluid_hashtable_t*
  326. new_fluid_hashtable_full (fluid_hash_func_t hash_func,
  327.                           fluid_equal_func_t key_equal_func,
  328.                           fluid_destroy_notify_t key_destroy_func,
  329.                           fluid_destroy_notify_t value_destroy_func)
  330. {
  331.   fluid_hashtable_t *hashtable;
  332.   hashtable = FLUID_NEW (fluid_hashtable_t);
  333.   if (!hashtable)
  334.   {
  335.     FLUID_LOG (FLUID_ERR, "Out of memory");
  336.     return NULL;
  337.   }
  338.   hashtable->size               = HASH_TABLE_MIN_SIZE;
  339.   hashtable->nnodes             = 0;
  340.   hashtable->hash_func          = hash_func ? hash_func : fluid_direct_hash;
  341.   hashtable->key_equal_func     = key_equal_func;
  342.   hashtable->ref_count          = 1;
  343.   hashtable->key_destroy_func   = key_destroy_func;
  344.   hashtable->value_destroy_func = value_destroy_func;
  345.   hashtable->nodes              = FLUID_ARRAY (fluid_hashnode_t*, hashtable->size);
  346.   FLUID_MEMSET (hashtable->nodes, 0, hashtable->size * sizeof (fluid_hashnode_t *));
  347.   return hashtable;
  348. }
  349. /**
  350.  * fluid_hashtable_iter_init:
  351.  * @iter: an uninitialized #fluid_hashtable_iter_t.
  352.  * @hashtable: a #fluid_hashtable_t.
  353.  *
  354.  * Initializes a key/value pair iterator and associates it with
  355.  * @hashtable. Modifying the hash table after calling this function
  356.  * invalidates the returned iterator.
  357.  * |[
  358.  * fluid_hashtable_iter_t iter;
  359.  * gpointer key, value;
  360.  *
  361.  * fluid_hashtable_iter_init (&iter, hashtable);
  362.  * while (fluid_hashtable_iter_next (&iter, &key, &value)) 
  363.  *   {
  364.  *     /&ast; do something with key and value &ast;/
  365.  *   }
  366.  * ]|
  367.  *
  368.  * Since: 2.16
  369.  **/
  370. void
  371. fluid_hashtable_iter_init (fluid_hashtable_iter_t *iter,
  372.                            fluid_hashtable_t *hashtable)
  373. {
  374.   RealIter *ri = (RealIter *) iter;
  375.   fluid_return_if_fail (iter != NULL);
  376.   fluid_return_if_fail (hashtable != NULL);
  377.   ri->hashtable = hashtable;
  378.   ri->prev_node = NULL;
  379.   ri->node = NULL;
  380.   ri->position = -1;
  381.   ri->pre_advanced = FALSE;
  382. }
  383. /**
  384.  * fluid_hashtable_iter_next:
  385.  * @iter: an initialized #fluid_hashtable_iter_t.
  386.  * @key: a location to store the key, or %NULL.
  387.  * @value: a location to store the value, or %NULL.
  388.  *
  389.  * Advances @iter and retrieves the key and/or value that are now
  390.  * pointed to as a result of this advancement. If %FALSE is returned,
  391.  * @key and @value are not set, and the iterator becomes invalid.
  392.  *
  393.  * Return value: %FALSE if the end of the #fluid_hashtable_t has been reached.
  394.  *
  395.  * Since: 2.16
  396.  **/
  397. int
  398. fluid_hashtable_iter_next (fluid_hashtable_iter_t *iter, void **key,
  399.                            void **value)
  400. {
  401.   RealIter *ri = (RealIter *) iter;
  402.   fluid_return_val_if_fail (iter != NULL, FALSE);
  403.   if (ri->pre_advanced)
  404.     {
  405.       ri->pre_advanced = FALSE;
  406.       if (ri->node == NULL)
  407. return FALSE;
  408.     }
  409.   else
  410.     {
  411.       if (ri->node != NULL)
  412. {
  413.   ri->prev_node = ri->node;
  414.   ri->node = ri->node->next;
  415. }
  416.       while (ri->node == NULL)
  417. {
  418.   ri->position++;
  419.   if (ri->position >= ri->hashtable->size)
  420.     return FALSE;
  421.   ri->prev_node = NULL;
  422.   ri->node = ri->hashtable->nodes[ri->position];
  423. }
  424.     }
  425.   if (key != NULL)
  426.     *key = ri->node->key;
  427.   if (value != NULL)
  428.     *value = ri->node->value;
  429.   return TRUE;
  430. }
  431. /**
  432.  * fluid_hashtable_iter_get_hash_table:
  433.  * @iter: an initialized #fluid_hashtable_iter_t.
  434.  *
  435.  * Returns the #fluid_hashtable_t associated with @iter.
  436.  *
  437.  * Return value: the #fluid_hashtable_t associated with @iter.
  438.  *
  439.  * Since: 2.16
  440.  **/
  441. fluid_hashtable_t *
  442. fluid_hashtable_iter_get_hash_table (fluid_hashtable_iter_t *iter)
  443. {
  444.   fluid_return_val_if_fail (iter != NULL, NULL);
  445.   return ((RealIter *) iter)->hashtable;
  446. }
  447. static void
  448. iter_remove_or_steal (RealIter *ri, int notify)
  449. {
  450.   fluid_hashnode_t *prev;
  451.   fluid_hashnode_t *node;
  452.   int position;
  453.   fluid_return_if_fail (ri != NULL);
  454.   fluid_return_if_fail (ri->node != NULL);
  455.   prev = ri->prev_node;
  456.   node = ri->node;
  457.   position = ri->position;
  458.   /* pre-advance the iterator since we will remove the node */
  459.   ri->node = ri->node->next;
  460.   /* ri->prev_node is still the correct previous node */
  461.   while (ri->node == NULL)
  462.     {
  463.       ri->position++;
  464.       if (ri->position >= ri->hashtable->size)
  465. break;
  466.       ri->prev_node = NULL;
  467.       ri->node = ri->hashtable->nodes[ri->position];
  468.     }
  469.   ri->pre_advanced = TRUE;
  470.   /* remove the node */
  471.   if (prev != NULL)
  472.     prev->next = node->next;
  473.   else
  474.     ri->hashtable->nodes[position] = node->next;
  475.   if (notify)
  476.     {
  477.       if (ri->hashtable->key_destroy_func)
  478. ri->hashtable->key_destroy_func(node->key);
  479.       if (ri->hashtable->value_destroy_func)
  480. ri->hashtable->value_destroy_func(node->value);
  481.     }
  482.   FLUID_FREE (node);
  483.   ri->hashtable->nnodes--;
  484. }
  485. /**
  486.  * fluid_hashtable_iter_remove():
  487.  * @iter: an initialized #fluid_hashtable_iter_t.
  488.  *
  489.  * Removes the key/value pair currently pointed to by the iterator
  490.  * from its associated #fluid_hashtable_t. Can only be called after
  491.  * fluid_hashtable_iter_next() returned %TRUE, and cannot be called more
  492.  * than once for the same key/value pair.
  493.  *
  494.  * If the #fluid_hashtable_t was created using fluid_hashtable_new_full(), the
  495.  * key and value are freed using the supplied destroy functions, otherwise
  496.  * you have to make sure that any dynamically allocated values are freed 
  497.  * yourself.
  498.  *
  499.  * Since: 2.16
  500.  **/
  501. void
  502. fluid_hashtable_iter_remove (fluid_hashtable_iter_t *iter)
  503. {
  504.   iter_remove_or_steal ((RealIter *) iter, TRUE);
  505. }
  506. /**
  507.  * fluid_hashtable_iter_steal():
  508.  * @iter: an initialized #fluid_hashtable_iter_t.
  509.  *
  510.  * Removes the key/value pair currently pointed to by the iterator
  511.  * from its associated #fluid_hashtable_t, without calling the key and value
  512.  * destroy functions. Can only be called after
  513.  * fluid_hashtable_iter_next() returned %TRUE, and cannot be called more
  514.  * than once for the same key/value pair.
  515.  *
  516.  * Since: 2.16
  517.  **/
  518. void
  519. fluid_hashtable_iter_steal (fluid_hashtable_iter_t *iter)
  520. {
  521.   iter_remove_or_steal ((RealIter *) iter, FALSE);
  522. }
  523. /**
  524.  * fluid_hashtable_ref:
  525.  * @hashtable: a valid #fluid_hashtable_t.
  526.  *
  527.  * Atomically increments the reference count of @hashtable by one.
  528.  * This function is MT-safe and may be called from any thread.
  529.  *
  530.  * Return value: the passed in #fluid_hashtable_t.
  531.  *
  532.  * Since: 2.10
  533.  **/
  534. fluid_hashtable_t*
  535. fluid_hashtable_ref (fluid_hashtable_t *hashtable)
  536. {
  537.   fluid_return_val_if_fail (hashtable != NULL, NULL);
  538.   fluid_return_val_if_fail (hashtable->ref_count > 0, hashtable);
  539.   fluid_atomic_int_add (&hashtable->ref_count, 1);
  540.   return hashtable;
  541. }
  542. /**
  543.  * fluid_hashtable_unref:
  544.  * @hashtable: a valid #fluid_hashtable_t.
  545.  *
  546.  * Atomically decrements the reference count of @hashtable by one.
  547.  * If the reference count drops to 0, all keys and values will be
  548.  * destroyed, and all memory allocated by the hash table is released.
  549.  * This function is MT-safe and may be called from any thread.
  550.  *
  551.  * Since: 2.10
  552.  **/
  553. void
  554. fluid_hashtable_unref (fluid_hashtable_t *hashtable)
  555. {
  556.   fluid_return_if_fail (hashtable != NULL);
  557.   fluid_return_if_fail (hashtable->ref_count > 0);
  558.   if (fluid_atomic_int_exchange_and_add (&hashtable->ref_count, -1) - 1 == 0)
  559.     {
  560.       fluid_hashtable_remove_all_nodes (hashtable, TRUE);
  561.       FLUID_FREE (hashtable->nodes);
  562.       FLUID_FREE (hashtable);
  563.     }
  564. }
  565. /**
  566.  * delete_fluid_hashtable:
  567.  * @hashtable: a #fluid_hashtable_t.
  568.  *
  569.  * Destroys all keys and values in the #fluid_hashtable_t and decrements its
  570.  * reference count by 1. If keys and/or values are dynamically allocated,
  571.  * you should either free them first or create the #fluid_hashtable_t with destroy
  572.  * notifiers using fluid_hashtable_new_full(). In the latter case the destroy
  573.  * functions you supplied will be called on all keys and values during the
  574.  * destruction phase.
  575.  **/
  576. void
  577. delete_fluid_hashtable (fluid_hashtable_t *hashtable)
  578. {
  579.   fluid_return_if_fail (hashtable != NULL);
  580.   fluid_return_if_fail (hashtable->ref_count > 0);
  581.   fluid_hashtable_remove_all (hashtable);
  582.   fluid_hashtable_unref (hashtable);
  583. }
  584. /**
  585.  * fluid_hashtable_lookup:
  586.  * @hashtable: a #fluid_hashtable_t.
  587.  * @key: the key to look up.
  588.  *
  589.  * Looks up a key in a #fluid_hashtable_t. Note that this function cannot
  590.  * distinguish between a key that is not present and one which is present
  591.  * and has the value %NULL. If you need this distinction, use
  592.  * fluid_hashtable_lookup_extended().
  593.  *
  594.  * Return value: the associated value, or %NULL if the key is not found.
  595.  **/
  596. void *
  597. fluid_hashtable_lookup (fluid_hashtable_t *hashtable, const void *key)
  598. {
  599.   fluid_hashnode_t *node;
  600.   fluid_return_val_if_fail (hashtable != NULL, NULL);
  601.   node = *fluid_hashtable_lookup_node (hashtable, key, NULL);
  602.   return node ? node->value : NULL;
  603. }
  604. /**
  605.  * fluid_hashtable_lookup_extended:
  606.  * @hashtable: a #fluid_hashtable_t.
  607.  * @lookup_key: the key to look up.
  608.  * @orig_key: returns the original key.
  609.  * @value: returns the value associated with the key.
  610.  *
  611.  * Looks up a key in the #fluid_hashtable_t, returning the original key and the
  612.  * associated value and a #gboolean which is %TRUE if the key was found. This
  613.  * is useful if you need to free the memory allocated for the original key,
  614.  * for example before calling fluid_hashtable_remove().
  615.  *
  616.  * Return value: %TRUE if the key was found in the #fluid_hashtable_t.
  617.  **/
  618. int
  619. fluid_hashtable_lookup_extended (fluid_hashtable_t *hashtable,
  620.                                  const void *lookup_key,
  621.                                  void **orig_key, void **value)
  622. {
  623.   fluid_hashnode_t *node;
  624.   fluid_return_val_if_fail (hashtable != NULL, FALSE);
  625.   node = *fluid_hashtable_lookup_node (hashtable, lookup_key, NULL);
  626.   if (node == NULL)
  627.     return FALSE;
  628.   if (orig_key)
  629.     *orig_key = node->key;
  630.   if (value)
  631.     *value = node->value;
  632.   return TRUE;
  633. }
  634. /*
  635.  * fluid_hashtable_insert_internal:
  636.  * @hashtable: our #fluid_hashtable_t
  637.  * @key: the key to insert
  638.  * @value: the value to insert
  639.  * @keep_new_key: if %TRUE and this key already exists in the table
  640.  *   then call the destroy notify function on the old key.  If %FALSE
  641.  *   then call the destroy notify function on the new key.
  642.  *
  643.  * Implements the common logic for the fluid_hashtable_insert() and
  644.  * fluid_hashtable_replace() functions.
  645.  *
  646.  * Do a lookup of @key.  If it is found, replace it with the new
  647.  * @value (and perhaps the new @key).  If it is not found, create a
  648.  * new node.
  649.  */
  650. static void
  651. fluid_hashtable_insert_internal (fluid_hashtable_t *hashtable, void *key,
  652.                                  void *value, int keep_new_key)
  653. {
  654.   fluid_hashnode_t **node_ptr, *node;
  655.   unsigned int key_hash;
  656.   fluid_return_if_fail (hashtable != NULL);
  657.   fluid_return_if_fail (hashtable->ref_count > 0);
  658.   node_ptr = fluid_hashtable_lookup_node (hashtable, key, &key_hash);
  659.   if ((node = *node_ptr))
  660.     {
  661.       if (keep_new_key)
  662.         {
  663.           if (hashtable->key_destroy_func)
  664.             hashtable->key_destroy_func (node->key);
  665.           node->key = key;
  666.         }
  667.       else
  668.         {
  669.           if (hashtable->key_destroy_func)
  670.             hashtable->key_destroy_func (key);
  671.         }
  672.       if (hashtable->value_destroy_func)
  673.         hashtable->value_destroy_func (node->value);
  674.       node->value = value;
  675.     }
  676.   else
  677.     {
  678.       node = FLUID_NEW (fluid_hashnode_t);
  679.       if (!node)
  680.       {
  681.         FLUID_LOG (FLUID_ERR, "Out of memory");
  682.         return;
  683.       }
  684.       node->key = key;
  685.       node->value = value;
  686.       node->key_hash = key_hash;
  687.       node->next = NULL;
  688.       *node_ptr = node;
  689.       hashtable->nnodes++;
  690.       fluid_hashtable_maybe_resize (hashtable);
  691.     }
  692. }
  693. /**
  694.  * fluid_hashtable_insert:
  695.  * @hashtable: a #fluid_hashtable_t.
  696.  * @key: a key to insert.
  697.  * @value: the value to associate with the key.
  698.  *
  699.  * Inserts a new key and value into a #fluid_hashtable_t.
  700.  *
  701.  * If the key already exists in the #fluid_hashtable_t its current value is replaced
  702.  * with the new value. If you supplied a @value_destroy_func when creating the
  703.  * #fluid_hashtable_t, the old value is freed using that function. If you supplied
  704.  * a @key_destroy_func when creating the #fluid_hashtable_t, the passed key is freed
  705.  * using that function.
  706.  **/
  707. void
  708. fluid_hashtable_insert (fluid_hashtable_t *hashtable, void *key, void *value)
  709. {
  710.   fluid_hashtable_insert_internal (hashtable, key, value, FALSE);
  711. }
  712. /**
  713.  * fluid_hashtable_replace:
  714.  * @hashtable: a #fluid_hashtable_t.
  715.  * @key: a key to insert.
  716.  * @value: the value to associate with the key.
  717.  *
  718.  * Inserts a new key and value into a #fluid_hashtable_t similar to
  719.  * fluid_hashtable_insert(). The difference is that if the key already exists
  720.  * in the #fluid_hashtable_t, it gets replaced by the new key. If you supplied a
  721.  * @value_destroy_func when creating the #fluid_hashtable_t, the old value is freed
  722.  * using that function. If you supplied a @key_destroy_func when creating the
  723.  * #fluid_hashtable_t, the old key is freed using that function.
  724.  **/
  725. void
  726. fluid_hashtable_replace (fluid_hashtable_t *hashtable, void *key, void *value)
  727. {
  728.   fluid_hashtable_insert_internal (hashtable, key, value, TRUE);
  729. }
  730. /*
  731.  * fluid_hashtable_remove_internal:
  732.  * @hashtable: our #fluid_hashtable_t
  733.  * @key: the key to remove
  734.  * @notify: %TRUE if the destroy notify handlers are to be called
  735.  * Return value: %TRUE if a node was found and removed, else %FALSE
  736.  *
  737.  * Implements the common logic for the fluid_hashtable_remove() and
  738.  * fluid_hashtable_steal() functions.
  739.  *
  740.  * Do a lookup of @key and remove it if it is found, calling the
  741.  * destroy notify handlers only if @notify is %TRUE.
  742.  */
  743. static int
  744. fluid_hashtable_remove_internal (fluid_hashtable_t *hashtable, const void *key,
  745.                                  int notify)
  746. {
  747.   fluid_hashnode_t **node_ptr;
  748.   fluid_return_val_if_fail (hashtable != NULL, FALSE);
  749.   node_ptr = fluid_hashtable_lookup_node (hashtable, key, NULL);
  750.   if (*node_ptr == NULL)
  751.     return FALSE;
  752.   fluid_hashtable_remove_node (hashtable, &node_ptr, notify);
  753.   fluid_hashtable_maybe_resize (hashtable);
  754.   return TRUE;
  755. }
  756. /**
  757.  * fluid_hashtable_remove:
  758.  * @hashtable: a #fluid_hashtable_t.
  759.  * @key: the key to remove.
  760.  *
  761.  * Removes a key and its associated value from a #fluid_hashtable_t.
  762.  *
  763.  * If the #fluid_hashtable_t was created using fluid_hashtable_new_full(), the
  764.  * key and value are freed using the supplied destroy functions, otherwise
  765.  * you have to make sure that any dynamically allocated values are freed
  766.  * yourself.
  767.  *
  768.  * Return value: %TRUE if the key was found and removed from the #fluid_hashtable_t.
  769.  **/
  770. int
  771. fluid_hashtable_remove (fluid_hashtable_t *hashtable, const void *key)
  772. {
  773.   return fluid_hashtable_remove_internal (hashtable, key, TRUE);
  774. }
  775. /**
  776.  * fluid_hashtable_steal:
  777.  * @hashtable: a #fluid_hashtable_t.
  778.  * @key: the key to remove.
  779.  *
  780.  * Removes a key and its associated value from a #fluid_hashtable_t without
  781.  * calling the key and value destroy functions.
  782.  *
  783.  * Return value: %TRUE if the key was found and removed from the #fluid_hashtable_t.
  784.  **/
  785. int
  786. fluid_hashtable_steal (fluid_hashtable_t *hashtable, const void *key)
  787. {
  788.   return fluid_hashtable_remove_internal (hashtable, key, FALSE);
  789. }
  790. /**
  791.  * fluid_hashtable_remove_all:
  792.  * @hashtable: a #fluid_hashtable_t
  793.  *
  794.  * Removes all keys and their associated values from a #fluid_hashtable_t.
  795.  *
  796.  * If the #fluid_hashtable_t was created using fluid_hashtable_new_full(), the keys
  797.  * and values are freed using the supplied destroy functions, otherwise you
  798.  * have to make sure that any dynamically allocated values are freed
  799.  * yourself.
  800.  *
  801.  * Since: 2.12
  802.  **/
  803. void
  804. fluid_hashtable_remove_all (fluid_hashtable_t *hashtable)
  805. {
  806.   fluid_return_if_fail (hashtable != NULL);
  807.   fluid_hashtable_remove_all_nodes (hashtable, TRUE);
  808.   fluid_hashtable_maybe_resize (hashtable);
  809. }
  810. /**
  811.  * fluid_hashtable_steal_all:
  812.  * @hashtable: a #fluid_hashtable_t.
  813.  *
  814.  * Removes all keys and their associated values from a #fluid_hashtable_t
  815.  * without calling the key and value destroy functions.
  816.  *
  817.  * Since: 2.12
  818.  **/
  819. void
  820. fluid_hashtable_steal_all (fluid_hashtable_t *hashtable)
  821. {
  822.   fluid_return_if_fail (hashtable != NULL);
  823.   fluid_hashtable_remove_all_nodes (hashtable, FALSE);
  824.   fluid_hashtable_maybe_resize (hashtable);
  825. }
  826. /*
  827.  * fluid_hashtable_foreach_remove_or_steal:
  828.  * @hashtable: our #fluid_hashtable_t
  829.  * @func: the user's callback function
  830.  * @user_data: data for @func
  831.  * @notify: %TRUE if the destroy notify handlers are to be called
  832.  *
  833.  * Implements the common logic for fluid_hashtable_foreach_remove() and
  834.  * fluid_hashtable_foreach_steal().
  835.  *
  836.  * Iterates over every node in the table, calling @func with the key
  837.  * and value of the node (and @user_data).  If @func returns %TRUE the
  838.  * node is removed from the table.
  839.  *
  840.  * If @notify is true then the destroy notify handlers will be called
  841.  * for each removed node.
  842.  */
  843. static unsigned int
  844. fluid_hashtable_foreach_remove_or_steal (fluid_hashtable_t *hashtable,
  845.                                          fluid_hr_func_t func, void *user_data,
  846.                                          int notify)
  847. {
  848.   fluid_hashnode_t *node, **node_ptr;
  849.   unsigned int deleted = 0;
  850.   int i;
  851.   for (i = 0; i < hashtable->size; i++)
  852.     for (node_ptr = &hashtable->nodes[i]; (node = *node_ptr) != NULL;)
  853.       if ((* func) (node->key, node->value, user_data))
  854.         {
  855.           fluid_hashtable_remove_node (hashtable, &node_ptr, notify);
  856.           deleted++;
  857.         }
  858.       else
  859.         node_ptr = &node->next;
  860.   fluid_hashtable_maybe_resize (hashtable);
  861.   return deleted;
  862. }
  863. /**
  864.  * fluid_hashtable_foreach_remove:
  865.  * @hashtable: a #fluid_hashtable_t.
  866.  * @func: the function to call for each key/value pair.
  867.  * @user_data: user data to pass to the function.
  868.  *
  869.  * Calls the given function for each key/value pair in the #fluid_hashtable_t.
  870.  * If the function returns %TRUE, then the key/value pair is removed from the
  871.  * #fluid_hashtable_t. If you supplied key or value destroy functions when creating
  872.  * the #fluid_hashtable_t, they are used to free the memory allocated for the removed
  873.  * keys and values.
  874.  *
  875.  * See #fluid_hashtable_iter_t for an alternative way to loop over the 
  876.  * key/value pairs in the hash table.
  877.  *
  878.  * Return value: the number of key/value pairs removed.
  879.  **/
  880. unsigned int
  881. fluid_hashtable_foreach_remove (fluid_hashtable_t *hashtable,
  882.                                 fluid_hr_func_t func, void *user_data)
  883. {
  884.   fluid_return_val_if_fail (hashtable != NULL, 0);
  885.   fluid_return_val_if_fail (func != NULL, 0);
  886.   return fluid_hashtable_foreach_remove_or_steal (hashtable, func, user_data, TRUE);
  887. }
  888. /**
  889.  * fluid_hashtable_foreach_steal:
  890.  * @hashtable: a #fluid_hashtable_t.
  891.  * @func: the function to call for each key/value pair.
  892.  * @user_data: user data to pass to the function.
  893.  *
  894.  * Calls the given function for each key/value pair in the #fluid_hashtable_t.
  895.  * If the function returns %TRUE, then the key/value pair is removed from the
  896.  * #fluid_hashtable_t, but no key or value destroy functions are called.
  897.  *
  898.  * See #fluid_hashtable_iter_t for an alternative way to loop over the 
  899.  * key/value pairs in the hash table.
  900.  *
  901.  * Return value: the number of key/value pairs removed.
  902.  **/
  903. unsigned int
  904. fluid_hashtable_foreach_steal (fluid_hashtable_t *hashtable,
  905.                                fluid_hr_func_t func, void *user_data)
  906. {
  907.   fluid_return_val_if_fail (hashtable != NULL, 0);
  908.   fluid_return_val_if_fail (func != NULL, 0);
  909.   return fluid_hashtable_foreach_remove_or_steal (hashtable, func, user_data, FALSE);
  910. }
  911. /**
  912.  * fluid_hashtable_foreach:
  913.  * @hashtable: a #fluid_hashtable_t.
  914.  * @func: the function to call for each key/value pair.
  915.  * @user_data: user data to pass to the function.
  916.  *
  917.  * Calls the given function for each of the key/value pairs in the
  918.  * #fluid_hashtable_t.  The function is passed the key and value of each
  919.  * pair, and the given @user_data parameter.  The hash table may not
  920.  * be modified while iterating over it (you can't add/remove
  921.  * items). To remove all items matching a predicate, use
  922.  * fluid_hashtable_foreach_remove().
  923.  *
  924.  * See fluid_hashtable_find() for performance caveats for linear
  925.  * order searches in contrast to fluid_hashtable_lookup().
  926.  **/
  927. void
  928. fluid_hashtable_foreach (fluid_hashtable_t *hashtable, fluid_hr_func_t func,
  929.                          void *user_data)
  930. {
  931.   fluid_hashnode_t *node;
  932.   int i;
  933.   fluid_return_if_fail (hashtable != NULL);
  934.   fluid_return_if_fail (func != NULL);
  935.   for (i = 0; i < hashtable->size; i++)
  936.     for (node = hashtable->nodes[i]; node; node = node->next)
  937.       (* func) (node->key, node->value, user_data);
  938. }
  939. /**
  940.  * fluid_hashtable_find:
  941.  * @hashtable: a #fluid_hashtable_t.
  942.  * @predicate:  function to test the key/value pairs for a certain property.
  943.  * @user_data:  user data to pass to the function.
  944.  *
  945.  * Calls the given function for key/value pairs in the #fluid_hashtable_t until
  946.  * @predicate returns %TRUE.  The function is passed the key and value of
  947.  * each pair, and the given @user_data parameter. The hash table may not
  948.  * be modified while iterating over it (you can't add/remove items).
  949.  *
  950.  * Note, that hash tables are really only optimized for forward lookups,
  951.  * i.e. fluid_hashtable_lookup().
  952.  * So code that frequently issues fluid_hashtable_find() or
  953.  * fluid_hashtable_foreach() (e.g. in the order of once per every entry in a
  954.  * hash table) should probably be reworked to use additional or different
  955.  * data structures for reverse lookups (keep in mind that an O(n) find/foreach
  956.  * operation issued for all n values in a hash table ends up needing O(n*n)
  957.  * operations).
  958.  *
  959.  * Return value: The value of the first key/value pair is returned, for which
  960.  * func evaluates to %TRUE. If no pair with the requested property is found,
  961.  * %NULL is returned.
  962.  *
  963.  * Since: 2.4
  964.  **/
  965. void *
  966. fluid_hashtable_find (fluid_hashtable_t *hashtable, fluid_hr_func_t predicate,
  967.                       void *user_data)
  968. {
  969.   fluid_hashnode_t *node;
  970.   int i;
  971.   fluid_return_val_if_fail (hashtable != NULL, NULL);
  972.   fluid_return_val_if_fail (predicate != NULL, NULL);
  973.   for (i = 0; i < hashtable->size; i++)
  974.     for (node = hashtable->nodes[i]; node; node = node->next)
  975.       if (predicate (node->key, node->value, user_data))
  976.         return node->value;
  977.   return NULL;
  978. }
  979. /**
  980.  * fluid_hashtable_size:
  981.  * @hashtable: a #fluid_hashtable_t.
  982.  *
  983.  * Returns the number of elements contained in the #fluid_hashtable_t.
  984.  *
  985.  * Return value: the number of key/value pairs in the #fluid_hashtable_t.
  986.  **/
  987. unsigned int
  988. fluid_hashtable_size (fluid_hashtable_t *hashtable)
  989. {
  990.   fluid_return_val_if_fail (hashtable != NULL, 0);
  991.   return hashtable->nnodes;
  992. }
  993. /**
  994.  * fluid_hashtable_get_keys:
  995.  * @hashtable: a #fluid_hashtable_t
  996.  *
  997.  * Retrieves every key inside @hashtable. The returned data is valid
  998.  * until @hashtable is modified.
  999.  *
  1000.  * Return value: a #GList containing all the keys inside the hash
  1001.  *   table. The content of the list is owned by the hash table and
  1002.  *   should not be modified or freed. Use delete_fluid_list() when done
  1003.  *   using the list.
  1004.  *
  1005.  * Since: 2.14
  1006.  */
  1007. fluid_list_t *
  1008. fluid_hashtable_get_keys (fluid_hashtable_t *hashtable)
  1009. {
  1010.   fluid_hashnode_t *node;
  1011.   int i;
  1012.   fluid_list_t *retval;
  1013.   fluid_return_val_if_fail (hashtable != NULL, NULL);
  1014.   retval = NULL;
  1015.   for (i = 0; i < hashtable->size; i++)
  1016.     for (node = hashtable->nodes[i]; node; node = node->next)
  1017.       retval = fluid_list_prepend (retval, node->key);
  1018.   return retval;
  1019. }
  1020. /**
  1021.  * fluid_hashtable_get_values:
  1022.  * @hashtable: a #fluid_hashtable_t
  1023.  *
  1024.  * Retrieves every value inside @hashtable. The returned data is
  1025.  * valid until @hashtable is modified.
  1026.  *
  1027.  * Return value: a #GList containing all the values inside the hash
  1028.  *   table. The content of the list is owned by the hash table and
  1029.  *   should not be modified or freed. Use delete_fluid_list() when done
  1030.  *   using the list.
  1031.  *
  1032.  * Since: 2.14
  1033.  */
  1034. fluid_list_t *
  1035. fluid_hashtable_get_values (fluid_hashtable_t *hashtable)
  1036. {
  1037.   fluid_hashnode_t *node;
  1038.   int i;
  1039.   fluid_list_t *retval;
  1040.   fluid_return_val_if_fail (hashtable != NULL, NULL);
  1041.   retval = NULL;
  1042.   for (i = 0; i < hashtable->size; i++)
  1043.     for (node = hashtable->nodes[i]; node; node = node->next)
  1044.       retval = fluid_list_prepend (retval, node->value);
  1045.   return retval;
  1046. }
  1047. /* Extracted from glib/gstring.c */
  1048. /**
  1049.  * fluid_str_equal:
  1050.  * @v1: a key
  1051.  * @v2: a key to compare with @v1
  1052.  * 
  1053.  * Compares two strings for byte-by-byte equality and returns %TRUE 
  1054.  * if they are equal. It can be passed to new_fluid_hashtable() as the 
  1055.  * @key_equal_func parameter, when using strings as keys in a #Ghashtable.
  1056.  *
  1057.  * Returns: %TRUE if the two keys match
  1058.  */
  1059. int
  1060. fluid_str_equal (const void *v1, const void *v2)
  1061. {
  1062.   const char *string1 = v1;
  1063.   const char *string2 = v2;
  1064.   
  1065.   return strcmp (string1, string2) == 0;
  1066. }
  1067. /**
  1068.  * fluid_str_hash:
  1069.  * @v: a string key
  1070.  *
  1071.  * Converts a string to a hash value.
  1072.  * It can be passed to new_fluid_hashtable() as the @hash_func 
  1073.  * parameter, when using strings as keys in a #fluid_hashtable_t.
  1074.  *
  1075.  * Returns: a hash value corresponding to the key
  1076.  */
  1077. unsigned int
  1078. fluid_str_hash (const void *v)
  1079. {
  1080.   /* 31 bit hash function */
  1081.   const signed char *p = v;
  1082.   uint32 h = *p;
  1083.   if (h)
  1084.     for (p += 1; *p != ''; p++)
  1085.       h = (h << 5) - h + *p;
  1086.   return h;
  1087. }
  1088. /* Extracted from glib/gutils.c */
  1089. /**
  1090.  * fluid_direct_equal:
  1091.  * @v1: a key.
  1092.  * @v2: a key to compare with @v1.
  1093.  *
  1094.  * Compares two #gpointer arguments and returns %TRUE if they are equal.
  1095.  * It can be passed to new_fluid_hashtable() as the @key_equal_func
  1096.  * parameter, when using pointers as keys in a #fluid_hashtable_t.
  1097.  * 
  1098.  * Returns: %TRUE if the two keys match.
  1099.  */
  1100. int
  1101. fluid_direct_equal (const void *v1, const void *v2)
  1102. {
  1103.   return v1 == v2;
  1104. }
  1105. /**
  1106.  * fluid_direct_hash:
  1107.  * @v: a void * key
  1108.  *
  1109.  * Converts a gpointer to a hash value.
  1110.  * It can be passed to g_hashtable_new() as the @hash_func parameter, 
  1111.  * when using pointers as keys in a #fluid_hashtable_t.
  1112.  *
  1113.  * Returns: a hash value corresponding to the key.
  1114.  */
  1115. unsigned int
  1116. fluid_direct_hash (const void *v)
  1117. {
  1118.   return FLUID_POINTER_TO_UINT (v);
  1119. }
  1120. /**
  1121.  * fluid_int_equal:
  1122.  * @v1: a pointer to a int key.
  1123.  * @v2: a pointer to a int key to compare with @v1.
  1124.  *
  1125.  * Compares the two #gint values being pointed to and returns 
  1126.  * %TRUE if they are equal.
  1127.  * It can be passed to g_hashtable_new() as the @key_equal_func
  1128.  * parameter, when using pointers to integers as keys in a #fluid_hashtable_t.
  1129.  * 
  1130.  * Returns: %TRUE if the two keys match.
  1131.  */
  1132. int
  1133. fluid_int_equal (const void *v1, const void *v2)
  1134. {
  1135.   return *((const int*) v1) == *((const int*) v2);
  1136. }
  1137. /**
  1138.  * fluid_int_hash:
  1139.  * @v: a pointer to a int key
  1140.  *
  1141.  * Converts a pointer to a #gint to a hash value.
  1142.  * It can be passed to g_hashtable_new() as the @hash_func parameter, 
  1143.  * when using pointers to integers values as keys in a #fluid_hashtable_t.
  1144.  *
  1145.  * Returns: a hash value corresponding to the key.
  1146.  */
  1147. unsigned int
  1148. fluid_int_hash (const void *v)
  1149. {
  1150.   return *(const int*) v;
  1151. }