1 /* GLIB - Library of useful routines for C programming
2 * Copyright (C) 1995-1997 Peter Mattis, Spencer Kimball and Josh MacDonald
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.
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.
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 02110-1301, USA.
21 * Modified by the GLib Team and others 1997-2000. See the AUTHORS
22 * file for a list of people on the GLib Team. See the ChangeLog
23 * files for a list of changes. These files are distributed with
24 * GLib at ftp://ftp.gtk.org/pub/gtk/.
26 * Adapted for FluidSynth use by Josh Green <jgreen@users.sourceforge.net>
27 * September 8, 2009 from glib 2.18.4
34 #include "fluidsynth_priv.h"
35 #include "fluid_hash.h"
36 #include "fluid_list.h"
39 #define HASH_TABLE_MIN_SIZE 11
40 #define HASH_TABLE_MAX_SIZE 13845163
45 fluid_hashtable_t *hashtable;
46 fluid_hashnode_t *prev_node;
47 fluid_hashnode_t *node;
49 int pre_advanced; // Boolean
54 /* Excerpt from glib gprimes.c */
56 static const guint primes[] =
94 static const unsigned int nprimes = sizeof (primes) / sizeof (primes[0]);
97 spaced_primes_closest (unsigned int num)
101 for (i = 0; i < nprimes; i++)
105 return primes[nprimes - 1];
108 /* End excerpt from glib gprimes.c */
112 * @hashtable: our #fluid_hashtable_t
113 * @key: the key to lookup against
114 * @hash_return: optional key hash return location
115 * Return value: a pointer to the described #fluid_hashnode_t pointer
117 * Performs a lookup in the hash table. Virtually all hash operations
118 * will use this function internally.
120 * This function first computes the hash value of the key using the
121 * user's hash function.
123 * If an entry in the table matching @key is found then this function
124 * returns a pointer to the pointer to that entry in the table. In
125 * the case that the entry is at the head of a chain, this pointer
126 * will be an item in the nodes[] array. In the case that the entry
127 * is not at the head of a chain, this pointer will be the ->next
128 * pointer on the node that preceeds it.
130 * In the case that no matching entry exists in the table, a pointer
131 * to a %NULL pointer will be returned. To insert a item, this %NULL
132 * pointer should be updated to point to the new #fluid_hashnode_t.
134 * If @hash_return is a pass-by-reference parameter. If it is
135 * non-%NULL then the computed hash value is returned. This is to
136 * save insertions from having to compute the hash record again for
139 static inline fluid_hashnode_t **
140 fluid_hashtable_lookup_node (fluid_hashtable_t *hashtable, const void *key,
141 unsigned int *hash_return)
143 fluid_hashnode_t **node_ptr, *node;
144 unsigned int hash_value;
146 hash_value = (* hashtable->hash_func)(key);
147 node_ptr = &hashtable->nodes[hash_value % hashtable->size];
150 *hash_return = hash_value;
152 /* Hash table lookup needs to be fast.
153 * We therefore remove the extra conditional of testing
154 * whether to call the key_equal_func or not from
157 * Additional optimisation: first check if our full hash
158 * values are equal so we can avoid calling the full-blown
159 * key equality function in most cases.
161 if (hashtable->key_equal_func)
163 while ((node = *node_ptr))
165 if (node->key_hash == hash_value &&
166 hashtable->key_equal_func (node->key, key))
169 node_ptr = &(*node_ptr)->next;
174 while ((node = *node_ptr))
176 if (node->key == key)
179 node_ptr = &(*node_ptr)->next;
187 * @hashtable: our #fluid_hashtable_t
188 * @node_ptr_ptr: a pointer to the return value from
189 * fluid_hashtable_lookup_node()
190 * @notify: %TRUE if the destroy notify handlers are to be called
192 * Removes a node from the hash table and updates the node count. The
193 * node is freed. No table resize is performed.
195 * If @notify is %TRUE then the destroy notify functions are called
196 * for the key and value of the hash node.
198 * @node_ptr_ptr is a pass-by-reference in/out parameter. When the
199 * function is called, it should point to the pointer to the node to
200 * remove. This level of indirection is required so that the pointer
201 * may be updated appropriately once the node has been removed.
203 * Before the function returns, the pointer at @node_ptr_ptr will be
204 * updated to point to the position in the table that contains the
205 * pointer to the "next" node in the chain. This makes this function
206 * convenient to use from functions that iterate over the entire
207 * table. If there is no further item in the chain then the
208 * #fluid_hashnode_t pointer will be %NULL (ie: **node_ptr_ptr == %NULL).
210 * Since the pointer in the table to the removed node is replaced with
211 * either a pointer to the next node or a %NULL pointer as
212 * appropriate, the pointer at the end of @node_ptr_ptr will never be
213 * modified at all. Stay tuned. :)
216 fluid_hashtable_remove_node (fluid_hashtable_t *hashtable,
217 fluid_hashnode_t ***node_ptr_ptr, int notify)
219 fluid_hashnode_t **node_ptr, *node;
221 node_ptr = *node_ptr_ptr;
224 *node_ptr = node->next;
226 if (notify && hashtable->key_destroy_func)
227 hashtable->key_destroy_func (node->key);
229 if (notify && hashtable->value_destroy_func)
230 hashtable->value_destroy_func (node->value);
238 * fluid_hashtable_remove_all_nodes:
239 * @hashtable: our #fluid_hashtable_t
240 * @notify: %TRUE if the destroy notify handlers are to be called
242 * Removes all nodes from the table. Since this may be a precursor to
243 * freeing the table entirely, no resize is performed.
245 * If @notify is %TRUE then the destroy notify functions are called
246 * for the key and value of the hash node.
249 fluid_hashtable_remove_all_nodes (fluid_hashtable_t *hashtable, int notify)
251 fluid_hashnode_t **node_ptr;
254 for (i = 0; i < hashtable->size; i++)
255 for (node_ptr = &hashtable->nodes[i]; *node_ptr != NULL;)
256 fluid_hashtable_remove_node (hashtable, &node_ptr, notify);
258 hashtable->nnodes = 0;
262 * fluid_hashtable_resize:
263 * @hashtable: our #fluid_hashtable_t
265 * Resizes the hash table to the optimal size based on the number of
266 * nodes currently held. If you call this function then a resize will
267 * occur, even if one does not need to occur. Use
268 * fluid_hashtable_maybe_resize() instead.
271 fluid_hashtable_resize (fluid_hashtable_t *hashtable)
273 fluid_hashnode_t **new_nodes;
274 fluid_hashnode_t *node;
275 fluid_hashnode_t *next;
276 unsigned int hash_val;
280 new_size = spaced_primes_closest (hashtable->nnodes);
281 new_size = (new_size < HASH_TABLE_MIN_SIZE) ? HASH_TABLE_MIN_SIZE :
282 ((new_size > HASH_TABLE_MAX_SIZE) ? HASH_TABLE_MAX_SIZE : new_size);
284 new_nodes = FLUID_ARRAY (fluid_hashnode_t *, new_size);
288 FLUID_LOG (FLUID_ERR, "Out of memory");
292 FLUID_MEMSET (new_nodes, 0, new_size * sizeof (fluid_hashnode_t *));
294 for (i = 0; i < hashtable->size; i++)
295 for (node = hashtable->nodes[i]; node; node = next)
299 hash_val = node->key_hash % new_size;
301 node->next = new_nodes[hash_val];
302 new_nodes[hash_val] = node;
305 FLUID_FREE (hashtable->nodes);
306 hashtable->nodes = new_nodes;
307 hashtable->size = new_size;
311 * fluid_hashtable_maybe_resize:
312 * @hashtable: our #fluid_hashtable_t
314 * Resizes the hash table, if needed.
316 * Essentially, calls fluid_hashtable_resize() if the table has strayed
317 * too far from its ideal size for its number of nodes.
320 fluid_hashtable_maybe_resize (fluid_hashtable_t *hashtable)
322 int nnodes = hashtable->nnodes;
323 int size = hashtable->size;
325 if ((size >= 3 * nnodes && size > HASH_TABLE_MIN_SIZE) ||
326 (3 * size <= nnodes && size < HASH_TABLE_MAX_SIZE))
327 fluid_hashtable_resize (hashtable);
331 * new_fluid_hashtable:
332 * @hash_func: a function to create a hash value from a key.
333 * Hash values are used to determine where keys are stored within the
334 * #fluid_hashtable_t data structure. The fluid_direct_hash(), fluid_int_hash() and
335 * fluid_str_hash() functions are provided for some common types of keys.
336 * If hash_func is %NULL, fluid_direct_hash() is used.
337 * @key_equal_func: a function to check two keys for equality. This is
338 * used when looking up keys in the #fluid_hashtable_t. The fluid_direct_equal(),
339 * fluid_int_equal() and fluid_str_equal() functions are provided for the most
340 * common types of keys. If @key_equal_func is %NULL, keys are compared
341 * directly in a similar fashion to fluid_direct_equal(), but without the
342 * overhead of a function call.
344 * Creates a new #fluid_hashtable_t with a reference count of 1.
346 * Return value: a new #fluid_hashtable_t.
349 new_fluid_hashtable (fluid_hash_func_t hash_func, fluid_equal_func_t key_equal_func)
351 return new_fluid_hashtable_full (hash_func, key_equal_func, NULL, NULL);
356 * new_fluid_hashtable_full:
357 * @hash_func: a function to create a hash value from a key.
358 * @key_equal_func: a function to check two keys for equality.
359 * @key_destroy_func: a function to free the memory allocated for the key
360 * used when removing the entry from the #fluid_hashtable_t or %NULL if you
361 * don't want to supply such a function.
362 * @value_destroy_func: a function to free the memory allocated for the
363 * value used when removing the entry from the #fluid_hashtable_t or %NULL if
364 * you don't want to supply such a function.
366 * Creates a new #fluid_hashtable_t like fluid_hashtable_new() with a reference count
367 * of 1 and allows to specify functions to free the memory allocated for the
368 * key and value that get called when removing the entry from the #fluid_hashtable_t.
370 * Return value: a new #fluid_hashtable_t.
373 new_fluid_hashtable_full (fluid_hash_func_t hash_func,
374 fluid_equal_func_t key_equal_func,
375 fluid_destroy_notify_t key_destroy_func,
376 fluid_destroy_notify_t value_destroy_func)
378 fluid_hashtable_t *hashtable;
380 hashtable = FLUID_NEW (fluid_hashtable_t);
384 FLUID_LOG (FLUID_ERR, "Out of memory");
388 hashtable->size = HASH_TABLE_MIN_SIZE;
389 hashtable->nnodes = 0;
390 hashtable->hash_func = hash_func ? hash_func : fluid_direct_hash;
391 hashtable->key_equal_func = key_equal_func;
392 hashtable->ref_count = 1;
393 hashtable->key_destroy_func = key_destroy_func;
394 hashtable->value_destroy_func = value_destroy_func;
395 hashtable->nodes = FLUID_ARRAY (fluid_hashnode_t*, hashtable->size);
396 FLUID_MEMSET (hashtable->nodes, 0, hashtable->size * sizeof (fluid_hashnode_t *));
402 * fluid_hashtable_iter_init:
403 * @iter: an uninitialized #fluid_hashtable_iter_t.
404 * @hashtable: a #fluid_hashtable_t.
406 * Initializes a key/value pair iterator and associates it with
407 * @hashtable. Modifying the hash table after calling this function
408 * invalidates the returned iterator.
410 * fluid_hashtable_iter_t iter;
411 * gpointer key, value;
413 * fluid_hashtable_iter_init (&iter, hashtable);
414 * while (fluid_hashtable_iter_next (&iter, &key, &value))
416 * /* do something with key and value */
423 fluid_hashtable_iter_init (fluid_hashtable_iter_t *iter,
424 fluid_hashtable_t *hashtable)
426 RealIter *ri = (RealIter *) iter;
428 fluid_return_if_fail (iter != NULL);
429 fluid_return_if_fail (hashtable != NULL);
431 ri->hashtable = hashtable;
432 ri->prev_node = NULL;
435 ri->pre_advanced = FALSE;
439 * fluid_hashtable_iter_next:
440 * @iter: an initialized #fluid_hashtable_iter_t.
441 * @key: a location to store the key, or %NULL.
442 * @value: a location to store the value, or %NULL.
444 * Advances @iter and retrieves the key and/or value that are now
445 * pointed to as a result of this advancement. If %FALSE is returned,
446 * @key and @value are not set, and the iterator becomes invalid.
448 * Return value: %FALSE if the end of the #fluid_hashtable_t has been reached.
453 fluid_hashtable_iter_next (fluid_hashtable_iter_t *iter, void **key,
456 RealIter *ri = (RealIter *) iter;
458 fluid_return_val_if_fail (iter != NULL, FALSE);
460 if (ri->pre_advanced)
462 ri->pre_advanced = FALSE;
464 if (ri->node == NULL)
469 if (ri->node != NULL)
471 ri->prev_node = ri->node;
472 ri->node = ri->node->next;
475 while (ri->node == NULL)
478 if (ri->position >= ri->hashtable->size)
481 ri->prev_node = NULL;
482 ri->node = ri->hashtable->nodes[ri->position];
487 *key = ri->node->key;
489 *value = ri->node->value;
495 * fluid_hashtable_iter_get_hash_table:
496 * @iter: an initialized #fluid_hashtable_iter_t.
498 * Returns the #fluid_hashtable_t associated with @iter.
500 * Return value: the #fluid_hashtable_t associated with @iter.
505 fluid_hashtable_iter_get_hash_table (fluid_hashtable_iter_t *iter)
507 fluid_return_val_if_fail (iter != NULL, NULL);
509 return ((RealIter *) iter)->hashtable;
513 iter_remove_or_steal (RealIter *ri, int notify)
515 fluid_hashnode_t *prev;
516 fluid_hashnode_t *node;
519 fluid_return_if_fail (ri != NULL);
520 fluid_return_if_fail (ri->node != NULL);
522 prev = ri->prev_node;
524 position = ri->position;
526 /* pre-advance the iterator since we will remove the node */
528 ri->node = ri->node->next;
529 /* ri->prev_node is still the correct previous node */
531 while (ri->node == NULL)
534 if (ri->position >= ri->hashtable->size)
537 ri->prev_node = NULL;
538 ri->node = ri->hashtable->nodes[ri->position];
541 ri->pre_advanced = TRUE;
543 /* remove the node */
546 prev->next = node->next;
548 ri->hashtable->nodes[position] = node->next;
552 if (ri->hashtable->key_destroy_func)
553 ri->hashtable->key_destroy_func(node->key);
554 if (ri->hashtable->value_destroy_func)
555 ri->hashtable->value_destroy_func(node->value);
560 ri->hashtable->nnodes--;
564 * fluid_hashtable_iter_remove():
565 * @iter: an initialized #fluid_hashtable_iter_t.
567 * Removes the key/value pair currently pointed to by the iterator
568 * from its associated #fluid_hashtable_t. Can only be called after
569 * fluid_hashtable_iter_next() returned %TRUE, and cannot be called more
570 * than once for the same key/value pair.
572 * If the #fluid_hashtable_t was created using fluid_hashtable_new_full(), the
573 * key and value are freed using the supplied destroy functions, otherwise
574 * you have to make sure that any dynamically allocated values are freed
580 fluid_hashtable_iter_remove (fluid_hashtable_iter_t *iter)
582 iter_remove_or_steal ((RealIter *) iter, TRUE);
586 * fluid_hashtable_iter_steal():
587 * @iter: an initialized #fluid_hashtable_iter_t.
589 * Removes the key/value pair currently pointed to by the iterator
590 * from its associated #fluid_hashtable_t, without calling the key and value
591 * destroy functions. Can only be called after
592 * fluid_hashtable_iter_next() returned %TRUE, and cannot be called more
593 * than once for the same key/value pair.
598 fluid_hashtable_iter_steal (fluid_hashtable_iter_t *iter)
600 iter_remove_or_steal ((RealIter *) iter, FALSE);
605 * fluid_hashtable_ref:
606 * @hashtable: a valid #fluid_hashtable_t.
608 * Atomically increments the reference count of @hashtable by one.
609 * This function is MT-safe and may be called from any thread.
611 * Return value: the passed in #fluid_hashtable_t.
616 fluid_hashtable_ref (fluid_hashtable_t *hashtable)
618 fluid_return_val_if_fail (hashtable != NULL, NULL);
619 fluid_return_val_if_fail (hashtable->ref_count > 0, hashtable);
621 fluid_atomic_int_add (&hashtable->ref_count, 1);
626 * fluid_hashtable_unref:
627 * @hashtable: a valid #fluid_hashtable_t.
629 * Atomically decrements the reference count of @hashtable by one.
630 * If the reference count drops to 0, all keys and values will be
631 * destroyed, and all memory allocated by the hash table is released.
632 * This function is MT-safe and may be called from any thread.
637 fluid_hashtable_unref (fluid_hashtable_t *hashtable)
639 fluid_return_if_fail (hashtable != NULL);
640 fluid_return_if_fail (hashtable->ref_count > 0);
642 if (fluid_atomic_int_exchange_and_add (&hashtable->ref_count, -1) - 1 == 0)
644 fluid_hashtable_remove_all_nodes (hashtable, TRUE);
645 FLUID_FREE (hashtable->nodes);
646 FLUID_FREE (hashtable);
651 * delete_fluid_hashtable:
652 * @hashtable: a #fluid_hashtable_t.
654 * Destroys all keys and values in the #fluid_hashtable_t and decrements its
655 * reference count by 1. If keys and/or values are dynamically allocated,
656 * you should either free them first or create the #fluid_hashtable_t with destroy
657 * notifiers using fluid_hashtable_new_full(). In the latter case the destroy
658 * functions you supplied will be called on all keys and values during the
662 delete_fluid_hashtable (fluid_hashtable_t *hashtable)
664 fluid_return_if_fail (hashtable != NULL);
665 fluid_return_if_fail (hashtable->ref_count > 0);
667 fluid_hashtable_remove_all (hashtable);
668 fluid_hashtable_unref (hashtable);
672 * fluid_hashtable_lookup:
673 * @hashtable: a #fluid_hashtable_t.
674 * @key: the key to look up.
676 * Looks up a key in a #fluid_hashtable_t. Note that this function cannot
677 * distinguish between a key that is not present and one which is present
678 * and has the value %NULL. If you need this distinction, use
679 * fluid_hashtable_lookup_extended().
681 * Return value: the associated value, or %NULL if the key is not found.
684 fluid_hashtable_lookup (fluid_hashtable_t *hashtable, const void *key)
686 fluid_hashnode_t *node;
688 fluid_return_val_if_fail (hashtable != NULL, NULL);
690 node = *fluid_hashtable_lookup_node (hashtable, key, NULL);
692 return node ? node->value : NULL;
696 * fluid_hashtable_lookup_extended:
697 * @hashtable: a #fluid_hashtable_t.
698 * @lookup_key: the key to look up.
699 * @orig_key: returns the original key.
700 * @value: returns the value associated with the key.
702 * Looks up a key in the #fluid_hashtable_t, returning the original key and the
703 * associated value and a #gboolean which is %TRUE if the key was found. This
704 * is useful if you need to free the memory allocated for the original key,
705 * for example before calling fluid_hashtable_remove().
707 * Return value: %TRUE if the key was found in the #fluid_hashtable_t.
710 fluid_hashtable_lookup_extended (fluid_hashtable_t *hashtable,
711 const void *lookup_key,
712 void **orig_key, void **value)
714 fluid_hashnode_t *node;
716 fluid_return_val_if_fail (hashtable != NULL, FALSE);
718 node = *fluid_hashtable_lookup_node (hashtable, lookup_key, NULL);
724 *orig_key = node->key;
727 *value = node->value;
733 * fluid_hashtable_insert_internal:
734 * @hashtable: our #fluid_hashtable_t
735 * @key: the key to insert
736 * @value: the value to insert
737 * @keep_new_key: if %TRUE and this key already exists in the table
738 * then call the destroy notify function on the old key. If %FALSE
739 * then call the destroy notify function on the new key.
741 * Implements the common logic for the fluid_hashtable_insert() and
742 * fluid_hashtable_replace() functions.
744 * Do a lookup of @key. If it is found, replace it with the new
745 * @value (and perhaps the new @key). If it is not found, create a
749 fluid_hashtable_insert_internal (fluid_hashtable_t *hashtable, void *key,
750 void *value, int keep_new_key)
752 fluid_hashnode_t **node_ptr, *node;
753 unsigned int key_hash;
755 fluid_return_if_fail (hashtable != NULL);
756 fluid_return_if_fail (hashtable->ref_count > 0);
758 node_ptr = fluid_hashtable_lookup_node (hashtable, key, &key_hash);
760 if ((node = *node_ptr))
764 if (hashtable->key_destroy_func)
765 hashtable->key_destroy_func (node->key);
770 if (hashtable->key_destroy_func)
771 hashtable->key_destroy_func (key);
774 if (hashtable->value_destroy_func)
775 hashtable->value_destroy_func (node->value);
781 node = FLUID_NEW (fluid_hashnode_t);
785 FLUID_LOG (FLUID_ERR, "Out of memory");
791 node->key_hash = key_hash;
796 fluid_hashtable_maybe_resize (hashtable);
801 * fluid_hashtable_insert:
802 * @hashtable: a #fluid_hashtable_t.
803 * @key: a key to insert.
804 * @value: the value to associate with the key.
806 * Inserts a new key and value into a #fluid_hashtable_t.
808 * If the key already exists in the #fluid_hashtable_t its current value is replaced
809 * with the new value. If you supplied a @value_destroy_func when creating the
810 * #fluid_hashtable_t, the old value is freed using that function. If you supplied
811 * a @key_destroy_func when creating the #fluid_hashtable_t, the passed key is freed
812 * using that function.
815 fluid_hashtable_insert (fluid_hashtable_t *hashtable, void *key, void *value)
817 fluid_hashtable_insert_internal (hashtable, key, value, FALSE);
821 * fluid_hashtable_replace:
822 * @hashtable: a #fluid_hashtable_t.
823 * @key: a key to insert.
824 * @value: the value to associate with the key.
826 * Inserts a new key and value into a #fluid_hashtable_t similar to
827 * fluid_hashtable_insert(). The difference is that if the key already exists
828 * in the #fluid_hashtable_t, it gets replaced by the new key. If you supplied a
829 * @value_destroy_func when creating the #fluid_hashtable_t, the old value is freed
830 * using that function. If you supplied a @key_destroy_func when creating the
831 * #fluid_hashtable_t, the old key is freed using that function.
834 fluid_hashtable_replace (fluid_hashtable_t *hashtable, void *key, void *value)
836 fluid_hashtable_insert_internal (hashtable, key, value, TRUE);
840 * fluid_hashtable_remove_internal:
841 * @hashtable: our #fluid_hashtable_t
842 * @key: the key to remove
843 * @notify: %TRUE if the destroy notify handlers are to be called
844 * Return value: %TRUE if a node was found and removed, else %FALSE
846 * Implements the common logic for the fluid_hashtable_remove() and
847 * fluid_hashtable_steal() functions.
849 * Do a lookup of @key and remove it if it is found, calling the
850 * destroy notify handlers only if @notify is %TRUE.
853 fluid_hashtable_remove_internal (fluid_hashtable_t *hashtable, const void *key,
856 fluid_hashnode_t **node_ptr;
858 fluid_return_val_if_fail (hashtable != NULL, FALSE);
860 node_ptr = fluid_hashtable_lookup_node (hashtable, key, NULL);
861 if (*node_ptr == NULL)
864 fluid_hashtable_remove_node (hashtable, &node_ptr, notify);
865 fluid_hashtable_maybe_resize (hashtable);
871 * fluid_hashtable_remove:
872 * @hashtable: a #fluid_hashtable_t.
873 * @key: the key to remove.
875 * Removes a key and its associated value from a #fluid_hashtable_t.
877 * If the #fluid_hashtable_t was created using fluid_hashtable_new_full(), the
878 * key and value are freed using the supplied destroy functions, otherwise
879 * you have to make sure that any dynamically allocated values are freed
882 * Return value: %TRUE if the key was found and removed from the #fluid_hashtable_t.
885 fluid_hashtable_remove (fluid_hashtable_t *hashtable, const void *key)
887 return fluid_hashtable_remove_internal (hashtable, key, TRUE);
891 * fluid_hashtable_steal:
892 * @hashtable: a #fluid_hashtable_t.
893 * @key: the key to remove.
895 * Removes a key and its associated value from a #fluid_hashtable_t without
896 * calling the key and value destroy functions.
898 * Return value: %TRUE if the key was found and removed from the #fluid_hashtable_t.
901 fluid_hashtable_steal (fluid_hashtable_t *hashtable, const void *key)
903 return fluid_hashtable_remove_internal (hashtable, key, FALSE);
907 * fluid_hashtable_remove_all:
908 * @hashtable: a #fluid_hashtable_t
910 * Removes all keys and their associated values from a #fluid_hashtable_t.
912 * If the #fluid_hashtable_t was created using fluid_hashtable_new_full(), the keys
913 * and values are freed using the supplied destroy functions, otherwise you
914 * have to make sure that any dynamically allocated values are freed
920 fluid_hashtable_remove_all (fluid_hashtable_t *hashtable)
922 fluid_return_if_fail (hashtable != NULL);
924 fluid_hashtable_remove_all_nodes (hashtable, TRUE);
925 fluid_hashtable_maybe_resize (hashtable);
929 * fluid_hashtable_steal_all:
930 * @hashtable: a #fluid_hashtable_t.
932 * Removes all keys and their associated values from a #fluid_hashtable_t
933 * without calling the key and value destroy functions.
938 fluid_hashtable_steal_all (fluid_hashtable_t *hashtable)
940 fluid_return_if_fail (hashtable != NULL);
942 fluid_hashtable_remove_all_nodes (hashtable, FALSE);
943 fluid_hashtable_maybe_resize (hashtable);
947 * fluid_hashtable_foreach_remove_or_steal:
948 * @hashtable: our #fluid_hashtable_t
949 * @func: the user's callback function
950 * @user_data: data for @func
951 * @notify: %TRUE if the destroy notify handlers are to be called
953 * Implements the common logic for fluid_hashtable_foreach_remove() and
954 * fluid_hashtable_foreach_steal().
956 * Iterates over every node in the table, calling @func with the key
957 * and value of the node (and @user_data). If @func returns %TRUE the
958 * node is removed from the table.
960 * If @notify is true then the destroy notify handlers will be called
961 * for each removed node.
964 fluid_hashtable_foreach_remove_or_steal (fluid_hashtable_t *hashtable,
965 fluid_hr_func_t func, void *user_data,
968 fluid_hashnode_t *node, **node_ptr;
969 unsigned int deleted = 0;
972 for (i = 0; i < hashtable->size; i++)
973 for (node_ptr = &hashtable->nodes[i]; (node = *node_ptr) != NULL;)
974 if ((* func) (node->key, node->value, user_data))
976 fluid_hashtable_remove_node (hashtable, &node_ptr, notify);
980 node_ptr = &node->next;
982 fluid_hashtable_maybe_resize (hashtable);
989 * fluid_hashtable_foreach_remove:
990 * @hashtable: a #fluid_hashtable_t.
991 * @func: the function to call for each key/value pair.
992 * @user_data: user data to pass to the function.
994 * Calls the given function for each key/value pair in the #fluid_hashtable_t.
995 * If the function returns %TRUE, then the key/value pair is removed from the
996 * #fluid_hashtable_t. If you supplied key or value destroy functions when creating
997 * the #fluid_hashtable_t, they are used to free the memory allocated for the removed
1000 * See #fluid_hashtable_iter_t for an alternative way to loop over the
1001 * key/value pairs in the hash table.
1003 * Return value: the number of key/value pairs removed.
1006 fluid_hashtable_foreach_remove (fluid_hashtable_t *hashtable,
1007 fluid_hr_func_t func, void *user_data)
1009 fluid_return_val_if_fail (hashtable != NULL, 0);
1010 fluid_return_val_if_fail (func != NULL, 0);
1012 return fluid_hashtable_foreach_remove_or_steal (hashtable, func, user_data, TRUE);
1017 * fluid_hashtable_foreach_steal:
1018 * @hashtable: a #fluid_hashtable_t.
1019 * @func: the function to call for each key/value pair.
1020 * @user_data: user data to pass to the function.
1022 * Calls the given function for each key/value pair in the #fluid_hashtable_t.
1023 * If the function returns %TRUE, then the key/value pair is removed from the
1024 * #fluid_hashtable_t, but no key or value destroy functions are called.
1026 * See #fluid_hashtable_iter_t for an alternative way to loop over the
1027 * key/value pairs in the hash table.
1029 * Return value: the number of key/value pairs removed.
1032 fluid_hashtable_foreach_steal (fluid_hashtable_t *hashtable,
1033 fluid_hr_func_t func, void *user_data)
1035 fluid_return_val_if_fail (hashtable != NULL, 0);
1036 fluid_return_val_if_fail (func != NULL, 0);
1038 return fluid_hashtable_foreach_remove_or_steal (hashtable, func, user_data, FALSE);
1042 * fluid_hashtable_foreach:
1043 * @hashtable: a #fluid_hashtable_t.
1044 * @func: the function to call for each key/value pair.
1045 * @user_data: user data to pass to the function.
1047 * Calls the given function for each of the key/value pairs in the
1048 * #fluid_hashtable_t. The function is passed the key and value of each
1049 * pair, and the given @user_data parameter. The hash table may not
1050 * be modified while iterating over it (you can't add/remove
1051 * items). To remove all items matching a predicate, use
1052 * fluid_hashtable_foreach_remove().
1054 * See fluid_hashtable_find() for performance caveats for linear
1055 * order searches in contrast to fluid_hashtable_lookup().
1058 fluid_hashtable_foreach (fluid_hashtable_t *hashtable, fluid_hr_func_t func,
1061 fluid_hashnode_t *node;
1064 fluid_return_if_fail (hashtable != NULL);
1065 fluid_return_if_fail (func != NULL);
1067 for (i = 0; i < hashtable->size; i++)
1068 for (node = hashtable->nodes[i]; node; node = node->next)
1069 (* func) (node->key, node->value, user_data);
1073 * fluid_hashtable_find:
1074 * @hashtable: a #fluid_hashtable_t.
1075 * @predicate: function to test the key/value pairs for a certain property.
1076 * @user_data: user data to pass to the function.
1078 * Calls the given function for key/value pairs in the #fluid_hashtable_t until
1079 * @predicate returns %TRUE. The function is passed the key and value of
1080 * each pair, and the given @user_data parameter. The hash table may not
1081 * be modified while iterating over it (you can't add/remove items).
1083 * Note, that hash tables are really only optimized for forward lookups,
1084 * i.e. fluid_hashtable_lookup().
1085 * So code that frequently issues fluid_hashtable_find() or
1086 * fluid_hashtable_foreach() (e.g. in the order of once per every entry in a
1087 * hash table) should probably be reworked to use additional or different
1088 * data structures for reverse lookups (keep in mind that an O(n) find/foreach
1089 * operation issued for all n values in a hash table ends up needing O(n*n)
1092 * Return value: The value of the first key/value pair is returned, for which
1093 * func evaluates to %TRUE. If no pair with the requested property is found,
1094 * %NULL is returned.
1099 fluid_hashtable_find (fluid_hashtable_t *hashtable, fluid_hr_func_t predicate,
1102 fluid_hashnode_t *node;
1105 fluid_return_val_if_fail (hashtable != NULL, NULL);
1106 fluid_return_val_if_fail (predicate != NULL, NULL);
1108 for (i = 0; i < hashtable->size; i++)
1109 for (node = hashtable->nodes[i]; node; node = node->next)
1110 if (predicate (node->key, node->value, user_data))
1116 * fluid_hashtable_size:
1117 * @hashtable: a #fluid_hashtable_t.
1119 * Returns the number of elements contained in the #fluid_hashtable_t.
1121 * Return value: the number of key/value pairs in the #fluid_hashtable_t.
1124 fluid_hashtable_size (fluid_hashtable_t *hashtable)
1126 fluid_return_val_if_fail (hashtable != NULL, 0);
1128 return hashtable->nnodes;
1132 * fluid_hashtable_get_keys:
1133 * @hashtable: a #fluid_hashtable_t
1135 * Retrieves every key inside @hashtable. The returned data is valid
1136 * until @hashtable is modified.
1138 * Return value: a #GList containing all the keys inside the hash
1139 * table. The content of the list is owned by the hash table and
1140 * should not be modified or freed. Use delete_fluid_list() when done
1146 fluid_hashtable_get_keys (fluid_hashtable_t *hashtable)
1148 fluid_hashnode_t *node;
1150 fluid_list_t *retval;
1152 fluid_return_val_if_fail (hashtable != NULL, NULL);
1155 for (i = 0; i < hashtable->size; i++)
1156 for (node = hashtable->nodes[i]; node; node = node->next)
1157 retval = fluid_list_prepend (retval, node->key);
1163 * fluid_hashtable_get_values:
1164 * @hashtable: a #fluid_hashtable_t
1166 * Retrieves every value inside @hashtable. The returned data is
1167 * valid until @hashtable is modified.
1169 * Return value: a #GList containing all the values inside the hash
1170 * table. The content of the list is owned by the hash table and
1171 * should not be modified or freed. Use delete_fluid_list() when done
1177 fluid_hashtable_get_values (fluid_hashtable_t *hashtable)
1179 fluid_hashnode_t *node;
1181 fluid_list_t *retval;
1183 fluid_return_val_if_fail (hashtable != NULL, NULL);
1186 for (i = 0; i < hashtable->size; i++)
1187 for (node = hashtable->nodes[i]; node; node = node->next)
1188 retval = fluid_list_prepend (retval, node->value);
1194 /* Extracted from glib/gstring.c */
1200 * @v2: a key to compare with @v1
1202 * Compares two strings for byte-by-byte equality and returns %TRUE
1203 * if they are equal. It can be passed to new_fluid_hashtable() as the
1204 * @key_equal_func parameter, when using strings as keys in a #Ghashtable.
1206 * Returns: %TRUE if the two keys match
1209 fluid_str_equal (const void *v1, const void *v2)
1211 const char *string1 = v1;
1212 const char *string2 = v2;
1214 return strcmp (string1, string2) == 0;
1221 * Converts a string to a hash value.
1222 * It can be passed to new_fluid_hashtable() as the @hash_func
1223 * parameter, when using strings as keys in a #fluid_hashtable_t.
1225 * Returns: a hash value corresponding to the key
1228 fluid_str_hash (const void *v)
1230 /* 31 bit hash function */
1231 const signed char *p = v;
1235 for (p += 1; *p != '\0'; p++)
1236 h = (h << 5) - h + *p;
1242 /* Extracted from glib/gutils.c */
1246 * fluid_direct_equal:
1248 * @v2: a key to compare with @v1.
1250 * Compares two #gpointer arguments and returns %TRUE if they are equal.
1251 * It can be passed to new_fluid_hashtable() as the @key_equal_func
1252 * parameter, when using pointers as keys in a #fluid_hashtable_t.
1254 * Returns: %TRUE if the two keys match.
1257 fluid_direct_equal (const void *v1, const void *v2)
1263 * fluid_direct_hash:
1266 * Converts a gpointer to a hash value.
1267 * It can be passed to g_hashtable_new() as the @hash_func parameter,
1268 * when using pointers as keys in a #fluid_hashtable_t.
1270 * Returns: a hash value corresponding to the key.
1273 fluid_direct_hash (const void *v)
1275 return FLUID_POINTER_TO_UINT (v);
1280 * @v1: a pointer to a int key.
1281 * @v2: a pointer to a int key to compare with @v1.
1283 * Compares the two #gint values being pointed to and returns
1284 * %TRUE if they are equal.
1285 * It can be passed to g_hashtable_new() as the @key_equal_func
1286 * parameter, when using pointers to integers as keys in a #fluid_hashtable_t.
1288 * Returns: %TRUE if the two keys match.
1291 fluid_int_equal (const void *v1, const void *v2)
1293 return *((const int*) v1) == *((const int*) v2);
1298 * @v: a pointer to a int key
1300 * Converts a pointer to a #gint to a hash value.
1301 * It can be passed to g_hashtable_new() as the @hash_func parameter,
1302 * when using pointers to integers values as keys in a #fluid_hashtable_t.
1304 * Returns: a hash value corresponding to the key.
1307 fluid_int_hash (const void *v)
1309 return *(const int*) v;