ghash.c revision e9010a86f763e6b7cb1fd5520985c929339f5523
12e0320d57e417f7d1c838d729a99545db2228e9Owen Taylor/* GLIB - Library of useful routines for C programming 22e0320d57e417f7d1c838d729a99545db2228e9Owen Taylor * Copyright (C) 1995-1997 Peter Mattis, Spencer Kimball and Josh MacDonald 32e0320d57e417f7d1c838d729a99545db2228e9Owen Taylor * 42e0320d57e417f7d1c838d729a99545db2228e9Owen Taylor * This library is free software; you can redistribute it and/or 5c9bd7542e1a28ba9de60048361c0a97d251833e7Tim Janik * modify it under the terms of the GNU Lesser General Public 62e0320d57e417f7d1c838d729a99545db2228e9Owen Taylor * License as published by the Free Software Foundation; either 72e0320d57e417f7d1c838d729a99545db2228e9Owen Taylor * version 2 of the License, or (at your option) any later version. 82e0320d57e417f7d1c838d729a99545db2228e9Owen Taylor * 92e0320d57e417f7d1c838d729a99545db2228e9Owen Taylor * This library is distributed in the hope that it will be useful, 102e0320d57e417f7d1c838d729a99545db2228e9Owen Taylor * but WITHOUT ANY WARRANTY; without even the implied warranty of 112d68cbbb7d37d3f265bf1087e6ddedcc58bc62beTim Janik * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the GNU 12c9bd7542e1a28ba9de60048361c0a97d251833e7Tim Janik * Lesser General Public License for more details. 132e0320d57e417f7d1c838d729a99545db2228e9Owen Taylor * 14c9bd7542e1a28ba9de60048361c0a97d251833e7Tim Janik * You should have received a copy of the GNU Lesser General Public 152e0320d57e417f7d1c838d729a99545db2228e9Owen Taylor * License along with this library; if not, write to the 162e0320d57e417f7d1c838d729a99545db2228e9Owen Taylor * Free Software Foundation, Inc., 59 Temple Place - Suite 330, 172e0320d57e417f7d1c838d729a99545db2228e9Owen Taylor * Boston, MA 02111-1307, USA. 182e0320d57e417f7d1c838d729a99545db2228e9Owen Taylor */ 19931ea952650b013b834041b91b0c37a748ffd449Owen Taylor 20b9ef2b41db975061960e2217220668c2a5d563daCST/* 21c9bd7542e1a28ba9de60048361c0a97d251833e7Tim Janik * Modified by the GLib Team and others 1997-2000. See the AUTHORS 22b9ef2b41db975061960e2217220668c2a5d563daCST * file for a list of people on the GLib Team. See the ChangeLog 23b9ef2b41db975061960e2217220668c2a5d563daCST * files for a list of changes. These files are distributed with 24b9ef2b41db975061960e2217220668c2a5d563daCST * GLib at ftp://ftp.gtk.org/pub/gtk/. 25b9ef2b41db975061960e2217220668c2a5d563daCST */ 26b9ef2b41db975061960e2217220668c2a5d563daCST 27931ea952650b013b834041b91b0c37a748ffd449Owen Taylor/* 28931ea952650b013b834041b91b0c37a748ffd449Owen Taylor * MT safe 29931ea952650b013b834041b91b0c37a748ffd449Owen Taylor */ 30931ea952650b013b834041b91b0c37a748ffd449Owen Taylor 31bbbd329ff5bd634b4e1d4fb43b13538779e44a78Owen Taylor#include "config.h" 322fb47703e2929d300a3f804268a36d50543b4a2cSebastian Wilhelmi 332e0320d57e417f7d1c838d729a99545db2228e9Owen Taylor#include "glib.h" 34608a31b98e1420f487190871ee7312db2643d93dMatthias Clasen#include "galias.h" 352e0320d57e417f7d1c838d729a99545db2228e9Owen Taylor 362e0320d57e417f7d1c838d729a99545db2228e9Owen Taylor 372e0320d57e417f7d1c838d729a99545db2228e9Owen Taylor#define HASH_TABLE_MIN_SIZE 11 382e0320d57e417f7d1c838d729a99545db2228e9Owen Taylor#define HASH_TABLE_MAX_SIZE 13845163 392e0320d57e417f7d1c838d729a99545db2228e9Owen Taylor 402e0320d57e417f7d1c838d729a99545db2228e9Owen Taylor 412e0320d57e417f7d1c838d729a99545db2228e9Owen Taylortypedef struct _GHashNode GHashNode; 422e0320d57e417f7d1c838d729a99545db2228e9Owen Taylor 432e0320d57e417f7d1c838d729a99545db2228e9Owen Taylorstruct _GHashNode 442e0320d57e417f7d1c838d729a99545db2228e9Owen Taylor{ 45a2b269bae3315a2ea772b741fb62f683c1db5770Sven Neumann gpointer key; 46a2b269bae3315a2ea772b741fb62f683c1db5770Sven Neumann gpointer value; 472e0320d57e417f7d1c838d729a99545db2228e9Owen Taylor GHashNode *next; 481bd89934513921526da2d9e6463faeda8e4d76a7Tim Janik guint key_hash; 492e0320d57e417f7d1c838d729a99545db2228e9Owen Taylor}; 502e0320d57e417f7d1c838d729a99545db2228e9Owen Taylor 517519c2338ae484135b44bbb7eb49719aea8c4ca3Lauri Alankostruct _GHashTable 522e0320d57e417f7d1c838d729a99545db2228e9Owen Taylor{ 53a2b269bae3315a2ea772b741fb62f683c1db5770Sven Neumann gint size; 54a2b269bae3315a2ea772b741fb62f683c1db5770Sven Neumann gint nnodes; 55a2b269bae3315a2ea772b741fb62f683c1db5770Sven Neumann GHashNode **nodes; 56a2b269bae3315a2ea772b741fb62f683c1db5770Sven Neumann GHashFunc hash_func; 57a2b269bae3315a2ea772b741fb62f683c1db5770Sven Neumann GEqualFunc key_equal_func; 58b8bcb2b8391b6c21457d83d485c754b01cb276bdMatthias Clasen volatile gint ref_count; 59a2b269bae3315a2ea772b741fb62f683c1db5770Sven Neumann GDestroyNotify key_destroy_func; 60a2b269bae3315a2ea772b741fb62f683c1db5770Sven Neumann GDestroyNotify value_destroy_func; 612e0320d57e417f7d1c838d729a99545db2228e9Owen Taylor}; 622e0320d57e417f7d1c838d729a99545db2228e9Owen Taylor 638079eb3456914a03618b92b48f75a71b25331acbOwen Taylor#define G_HASH_TABLE_RESIZE(hash_table) \ 648079eb3456914a03618b92b48f75a71b25331acbOwen Taylor G_STMT_START { \ 658079eb3456914a03618b92b48f75a71b25331acbOwen Taylor if ((hash_table->size >= 3 * hash_table->nnodes && \ 668079eb3456914a03618b92b48f75a71b25331acbOwen Taylor hash_table->size > HASH_TABLE_MIN_SIZE) || \ 678079eb3456914a03618b92b48f75a71b25331acbOwen Taylor (3 * hash_table->size <= hash_table->nnodes && \ 688079eb3456914a03618b92b48f75a71b25331acbOwen Taylor hash_table->size < HASH_TABLE_MAX_SIZE)) \ 698079eb3456914a03618b92b48f75a71b25331acbOwen Taylor g_hash_table_resize (hash_table); \ 708079eb3456914a03618b92b48f75a71b25331acbOwen Taylor } G_STMT_END 712e0320d57e417f7d1c838d729a99545db2228e9Owen Taylor 72a2b269bae3315a2ea772b741fb62f683c1db5770Sven Neumannstatic void g_hash_table_resize (GHashTable *hash_table); 73a2b269bae3315a2ea772b741fb62f683c1db5770Sven Neumannstatic GHashNode** g_hash_table_lookup_node (GHashTable *hash_table, 74e6b78c9af1d6416f93311b98e1e6d802e2fe0617Ryan Lortie gconstpointer key, 75e6b78c9af1d6416f93311b98e1e6d802e2fe0617Ryan Lortie guint *hash_return); 76a2b269bae3315a2ea772b741fb62f683c1db5770Sven Neumannstatic GHashNode* g_hash_node_new (gpointer key, 77e6b78c9af1d6416f93311b98e1e6d802e2fe0617Ryan Lortie gpointer value, 78e6b78c9af1d6416f93311b98e1e6d802e2fe0617Ryan Lortie guint key_hash); 79a2b269bae3315a2ea772b741fb62f683c1db5770Sven Neumannstatic void g_hash_node_destroy (GHashNode *hash_node, 80a2b269bae3315a2ea772b741fb62f683c1db5770Sven Neumann GDestroyNotify key_destroy_func, 81a2b269bae3315a2ea772b741fb62f683c1db5770Sven Neumann GDestroyNotify value_destroy_func); 82a2b269bae3315a2ea772b741fb62f683c1db5770Sven Neumannstatic void g_hash_nodes_destroy (GHashNode *hash_node, 83a2b269bae3315a2ea772b741fb62f683c1db5770Sven Neumann GDestroyNotify key_destroy_func, 84a2b269bae3315a2ea772b741fb62f683c1db5770Sven Neumann GDestroyNotify value_destroy_func); 85a2b269bae3315a2ea772b741fb62f683c1db5770Sven Neumannstatic guint g_hash_table_foreach_remove_or_steal (GHashTable *hash_table, 86a2b269bae3315a2ea772b741fb62f683c1db5770Sven Neumann GHRFunc func, 87a2b269bae3315a2ea772b741fb62f683c1db5770Sven Neumann gpointer user_data, 88a2b269bae3315a2ea772b741fb62f683c1db5770Sven Neumann gboolean notify); 892e0320d57e417f7d1c838d729a99545db2228e9Owen Taylor 902e0320d57e417f7d1c838d729a99545db2228e9Owen Taylor 91a2b269bae3315a2ea772b741fb62f683c1db5770Sven Neumann/** 92a2b269bae3315a2ea772b741fb62f683c1db5770Sven Neumann * g_hash_table_new: 93a2b269bae3315a2ea772b741fb62f683c1db5770Sven Neumann * @hash_func: a function to create a hash value from a key. 94a2b269bae3315a2ea772b741fb62f683c1db5770Sven Neumann * Hash values are used to determine where keys are stored within the 95a2b269bae3315a2ea772b741fb62f683c1db5770Sven Neumann * #GHashTable data structure. The g_direct_hash(), g_int_hash() and 96a2b269bae3315a2ea772b741fb62f683c1db5770Sven Neumann * g_str_hash() functions are provided for some common types of keys. 97a52e2986cd4a2147cfc8d41ae23d98907caaf3a0Matthias Clasen * If hash_func is %NULL, g_direct_hash() is used. 98a2b269bae3315a2ea772b741fb62f683c1db5770Sven Neumann * @key_equal_func: a function to check two keys for equality. This is 99a2b269bae3315a2ea772b741fb62f683c1db5770Sven Neumann * used when looking up keys in the #GHashTable. The g_direct_equal(), 100a2b269bae3315a2ea772b741fb62f683c1db5770Sven Neumann * g_int_equal() and g_str_equal() functions are provided for the most 101a52e2986cd4a2147cfc8d41ae23d98907caaf3a0Matthias Clasen * common types of keys. If @key_equal_func is %NULL, keys are compared 102a2b269bae3315a2ea772b741fb62f683c1db5770Sven Neumann * directly in a similar fashion to g_direct_equal(), but without the 103a2b269bae3315a2ea772b741fb62f683c1db5770Sven Neumann * overhead of a function call. 104a2b269bae3315a2ea772b741fb62f683c1db5770Sven Neumann * 1053e847a090cfd8495add631d43388c461b1a85716Tim Janik * Creates a new #GHashTable with a reference count of 1. 106a2b269bae3315a2ea772b741fb62f683c1db5770Sven Neumann * 107a2b269bae3315a2ea772b741fb62f683c1db5770Sven Neumann * Return value: a new #GHashTable. 108a2b269bae3315a2ea772b741fb62f683c1db5770Sven Neumann **/ 1092e0320d57e417f7d1c838d729a99545db2228e9Owen TaylorGHashTable* 1102e0320d57e417f7d1c838d729a99545db2228e9Owen Taylorg_hash_table_new (GHashFunc hash_func, 111267b6813703e24ef60d0e8ba42557c414f9dd52eSebastian Wilhelmi GEqualFunc key_equal_func) 1122e0320d57e417f7d1c838d729a99545db2228e9Owen Taylor{ 113a2b269bae3315a2ea772b741fb62f683c1db5770Sven Neumann return g_hash_table_new_full (hash_func, key_equal_func, NULL, NULL); 114a2b269bae3315a2ea772b741fb62f683c1db5770Sven Neumann} 115a2b269bae3315a2ea772b741fb62f683c1db5770Sven Neumann 116a2b269bae3315a2ea772b741fb62f683c1db5770Sven Neumann 117a2b269bae3315a2ea772b741fb62f683c1db5770Sven Neumann/** 118a2b269bae3315a2ea772b741fb62f683c1db5770Sven Neumann * g_hash_table_new_full: 119a2b269bae3315a2ea772b741fb62f683c1db5770Sven Neumann * @hash_func: a function to create a hash value from a key. 120a2b269bae3315a2ea772b741fb62f683c1db5770Sven Neumann * @key_equal_func: a function to check two keys for equality. 121a2b269bae3315a2ea772b741fb62f683c1db5770Sven Neumann * @key_destroy_func: a function to free the memory allocated for the key 122a52e2986cd4a2147cfc8d41ae23d98907caaf3a0Matthias Clasen * used when removing the entry from the #GHashTable or %NULL if you 123d18b364dd774087555f036fec2c6ec9fe838368fSven Neumann * don't want to supply such a function. 124a2b269bae3315a2ea772b741fb62f683c1db5770Sven Neumann * @value_destroy_func: a function to free the memory allocated for the 125a52e2986cd4a2147cfc8d41ae23d98907caaf3a0Matthias Clasen * value used when removing the entry from the #GHashTable or %NULL if 126a2b269bae3315a2ea772b741fb62f683c1db5770Sven Neumann * you don't want to supply such a function. 127a2b269bae3315a2ea772b741fb62f683c1db5770Sven Neumann * 1283e847a090cfd8495add631d43388c461b1a85716Tim Janik * Creates a new #GHashTable like g_hash_table_new() with a reference count 1293e847a090cfd8495add631d43388c461b1a85716Tim Janik * of 1 and allows to specify functions to free the memory allocated for the 1303e847a090cfd8495add631d43388c461b1a85716Tim Janik * key and value that get called when removing the entry from the #GHashTable. 131a2b269bae3315a2ea772b741fb62f683c1db5770Sven Neumann * 132a2b269bae3315a2ea772b741fb62f683c1db5770Sven Neumann * Return value: a new #GHashTable. 133a2b269bae3315a2ea772b741fb62f683c1db5770Sven Neumann **/ 134a2b269bae3315a2ea772b741fb62f683c1db5770Sven NeumannGHashTable* 135a2b269bae3315a2ea772b741fb62f683c1db5770Sven Neumanng_hash_table_new_full (GHashFunc hash_func, 136a2b269bae3315a2ea772b741fb62f683c1db5770Sven Neumann GEqualFunc key_equal_func, 137a2b269bae3315a2ea772b741fb62f683c1db5770Sven Neumann GDestroyNotify key_destroy_func, 138a2b269bae3315a2ea772b741fb62f683c1db5770Sven Neumann GDestroyNotify value_destroy_func) 139a2b269bae3315a2ea772b741fb62f683c1db5770Sven Neumann{ 1407519c2338ae484135b44bbb7eb49719aea8c4ca3Lauri Alanko GHashTable *hash_table; 1412d68cbbb7d37d3f265bf1087e6ddedcc58bc62beTim Janik 1420cba1b531d5d28890fa4f48359d4e7adacf2a603Tim Janik hash_table = g_slice_new (GHashTable); 143a2b269bae3315a2ea772b741fb62f683c1db5770Sven Neumann hash_table->size = HASH_TABLE_MIN_SIZE; 144a2b269bae3315a2ea772b741fb62f683c1db5770Sven Neumann hash_table->nnodes = 0; 145a2b269bae3315a2ea772b741fb62f683c1db5770Sven Neumann hash_table->hash_func = hash_func ? hash_func : g_direct_hash; 146a2b269bae3315a2ea772b741fb62f683c1db5770Sven Neumann hash_table->key_equal_func = key_equal_func; 1473e847a090cfd8495add631d43388c461b1a85716Tim Janik hash_table->ref_count = 1; 148a2b269bae3315a2ea772b741fb62f683c1db5770Sven Neumann hash_table->key_destroy_func = key_destroy_func; 149a2b269bae3315a2ea772b741fb62f683c1db5770Sven Neumann hash_table->value_destroy_func = value_destroy_func; 1503e847a090cfd8495add631d43388c461b1a85716Tim Janik hash_table->nodes = g_new0 (GHashNode*, hash_table->size); 1512d68cbbb7d37d3f265bf1087e6ddedcc58bc62beTim Janik 1527519c2338ae484135b44bbb7eb49719aea8c4ca3Lauri Alanko return hash_table; 1532e0320d57e417f7d1c838d729a99545db2228e9Owen Taylor} 1542e0320d57e417f7d1c838d729a99545db2228e9Owen Taylor 1553e847a090cfd8495add631d43388c461b1a85716Tim Janik 1563e847a090cfd8495add631d43388c461b1a85716Tim Janik/** 1573e847a090cfd8495add631d43388c461b1a85716Tim Janik * g_hash_table_ref: 1583e847a090cfd8495add631d43388c461b1a85716Tim Janik * @hash_table: a valid #GHashTable. 1593e847a090cfd8495add631d43388c461b1a85716Tim Janik * 1603e847a090cfd8495add631d43388c461b1a85716Tim Janik * Atomically increments the reference count of @hash_table by one. 1613e847a090cfd8495add631d43388c461b1a85716Tim Janik * This function is MT-safe and may be called from any thread. 1623e847a090cfd8495add631d43388c461b1a85716Tim Janik * 1633e847a090cfd8495add631d43388c461b1a85716Tim Janik * Return value: the passed in #GHashTable. 164fe749cbd3b058512e36d79203cac3c00c7f40571Matthias Clasen * 165fe749cbd3b058512e36d79203cac3c00c7f40571Matthias Clasen * Since: 2.10 1663e847a090cfd8495add631d43388c461b1a85716Tim Janik **/ 1673e847a090cfd8495add631d43388c461b1a85716Tim JanikGHashTable* 1683e847a090cfd8495add631d43388c461b1a85716Tim Janikg_hash_table_ref (GHashTable *hash_table) 1693e847a090cfd8495add631d43388c461b1a85716Tim Janik{ 1703e847a090cfd8495add631d43388c461b1a85716Tim Janik g_return_val_if_fail (hash_table != NULL, NULL); 1713e847a090cfd8495add631d43388c461b1a85716Tim Janik g_return_val_if_fail (hash_table->ref_count > 0, hash_table); 1723e847a090cfd8495add631d43388c461b1a85716Tim Janik 1733e847a090cfd8495add631d43388c461b1a85716Tim Janik g_atomic_int_add (&hash_table->ref_count, 1); 1743e847a090cfd8495add631d43388c461b1a85716Tim Janik return hash_table; 1753e847a090cfd8495add631d43388c461b1a85716Tim Janik} 1763e847a090cfd8495add631d43388c461b1a85716Tim Janik 1773e847a090cfd8495add631d43388c461b1a85716Tim Janik/** 1783e847a090cfd8495add631d43388c461b1a85716Tim Janik * g_hash_table_unref: 1793e847a090cfd8495add631d43388c461b1a85716Tim Janik * @hash_table: a valid #GHashTable. 1803e847a090cfd8495add631d43388c461b1a85716Tim Janik * 1813e847a090cfd8495add631d43388c461b1a85716Tim Janik * Atomically decrements the reference count of @hash_table by one. 1823e847a090cfd8495add631d43388c461b1a85716Tim Janik * If the reference count drops to 0, all keys and values will be 1833e847a090cfd8495add631d43388c461b1a85716Tim Janik * destroyed, and all memory allocated by the hash table is released. 1843e847a090cfd8495add631d43388c461b1a85716Tim Janik * This function is MT-safe and may be called from any thread. 185fe749cbd3b058512e36d79203cac3c00c7f40571Matthias Clasen * 186fe749cbd3b058512e36d79203cac3c00c7f40571Matthias Clasen * Since: 2.10 1873e847a090cfd8495add631d43388c461b1a85716Tim Janik **/ 1883e847a090cfd8495add631d43388c461b1a85716Tim Janikvoid 1893e847a090cfd8495add631d43388c461b1a85716Tim Janikg_hash_table_unref (GHashTable *hash_table) 1903e847a090cfd8495add631d43388c461b1a85716Tim Janik{ 1913e847a090cfd8495add631d43388c461b1a85716Tim Janik g_return_if_fail (hash_table != NULL); 1923e847a090cfd8495add631d43388c461b1a85716Tim Janik g_return_if_fail (hash_table->ref_count > 0); 1933e847a090cfd8495add631d43388c461b1a85716Tim Janik 1943e847a090cfd8495add631d43388c461b1a85716Tim Janik if (g_atomic_int_exchange_and_add (&hash_table->ref_count, -1) - 1 == 0) 1953e847a090cfd8495add631d43388c461b1a85716Tim Janik { 19609b118f462fabb228ba26a498001f7c4e72bdde8Matthias Clasen gint i; 19709b118f462fabb228ba26a498001f7c4e72bdde8Matthias Clasen 1983e847a090cfd8495add631d43388c461b1a85716Tim Janik for (i = 0; i < hash_table->size; i++) 1993e847a090cfd8495add631d43388c461b1a85716Tim Janik g_hash_nodes_destroy (hash_table->nodes[i], 2003e847a090cfd8495add631d43388c461b1a85716Tim Janik hash_table->key_destroy_func, 2013e847a090cfd8495add631d43388c461b1a85716Tim Janik hash_table->value_destroy_func); 2023e847a090cfd8495add631d43388c461b1a85716Tim Janik g_free (hash_table->nodes); 2033e847a090cfd8495add631d43388c461b1a85716Tim Janik g_slice_free (GHashTable, hash_table); 2043e847a090cfd8495add631d43388c461b1a85716Tim Janik } 2053e847a090cfd8495add631d43388c461b1a85716Tim Janik} 2063e847a090cfd8495add631d43388c461b1a85716Tim Janik 207a2b269bae3315a2ea772b741fb62f683c1db5770Sven Neumann/** 208a2b269bae3315a2ea772b741fb62f683c1db5770Sven Neumann * g_hash_table_destroy: 209a2b269bae3315a2ea772b741fb62f683c1db5770Sven Neumann * @hash_table: a #GHashTable. 210a2b269bae3315a2ea772b741fb62f683c1db5770Sven Neumann * 21124dec3cd490fa4dc057a0186c6b870160022268eMorten Welinder * Destroys all keys and values in the #GHashTable and decrements its 2123e847a090cfd8495add631d43388c461b1a85716Tim Janik * reference count by 1. If keys and/or values are dynamically allocated, 2133e847a090cfd8495add631d43388c461b1a85716Tim Janik * you should either free them first or create the #GHashTable with destroy 2143e847a090cfd8495add631d43388c461b1a85716Tim Janik * notifiers using g_hash_table_new_full(). In the latter case the destroy 2153e847a090cfd8495add631d43388c461b1a85716Tim Janik * functions you supplied will be called on all keys and values during the 2163e847a090cfd8495add631d43388c461b1a85716Tim Janik * destruction phase. 217a2b269bae3315a2ea772b741fb62f683c1db5770Sven Neumann **/ 2182e0320d57e417f7d1c838d729a99545db2228e9Owen Taylorvoid 2192e0320d57e417f7d1c838d729a99545db2228e9Owen Taylorg_hash_table_destroy (GHashTable *hash_table) 2202e0320d57e417f7d1c838d729a99545db2228e9Owen Taylor{ 2212d68cbbb7d37d3f265bf1087e6ddedcc58bc62beTim Janik g_return_if_fail (hash_table != NULL); 2223e847a090cfd8495add631d43388c461b1a85716Tim Janik g_return_if_fail (hash_table->ref_count > 0); 2232d68cbbb7d37d3f265bf1087e6ddedcc58bc62beTim Janik 224a5b4b8bfb18838454d99bdee60294da07e5ef0d2Matthias Clasen g_hash_table_remove_all (hash_table); 2253e847a090cfd8495add631d43388c461b1a85716Tim Janik g_hash_table_unref (hash_table); 2262e0320d57e417f7d1c838d729a99545db2228e9Owen Taylor} 2272e0320d57e417f7d1c838d729a99545db2228e9Owen Taylor 228d5492a983cfa048658af8b03f833ddb3c0cf355eESTstatic inline GHashNode** 229d5492a983cfa048658af8b03f833ddb3c0cf355eESTg_hash_table_lookup_node (GHashTable *hash_table, 230e6b78c9af1d6416f93311b98e1e6d802e2fe0617Ryan Lortie gconstpointer key, 231e6b78c9af1d6416f93311b98e1e6d802e2fe0617Ryan Lortie guint *hash_return) 2322e0320d57e417f7d1c838d729a99545db2228e9Owen Taylor{ 233d5492a983cfa048658af8b03f833ddb3c0cf355eEST GHashNode **node; 234e6b78c9af1d6416f93311b98e1e6d802e2fe0617Ryan Lortie guint hash_value; 235e6b78c9af1d6416f93311b98e1e6d802e2fe0617Ryan Lortie 236e6b78c9af1d6416f93311b98e1e6d802e2fe0617Ryan Lortie hash_value = (* hash_table->hash_func) (key); 237e6b78c9af1d6416f93311b98e1e6d802e2fe0617Ryan Lortie node = &hash_table->nodes[hash_value % hash_table->size]; 2382d68cbbb7d37d3f265bf1087e6ddedcc58bc62beTim Janik 239e6b78c9af1d6416f93311b98e1e6d802e2fe0617Ryan Lortie if (hash_return) 240e6b78c9af1d6416f93311b98e1e6d802e2fe0617Ryan Lortie *hash_return = hash_value; 2412d68cbbb7d37d3f265bf1087e6ddedcc58bc62beTim Janik 2422d68cbbb7d37d3f265bf1087e6ddedcc58bc62beTim Janik /* Hash table lookup needs to be fast. 2432d68cbbb7d37d3f265bf1087e6ddedcc58bc62beTim Janik * We therefore remove the extra conditional of testing 244267b6813703e24ef60d0e8ba42557c414f9dd52eSebastian Wilhelmi * whether to call the key_equal_func or not from 2452d68cbbb7d37d3f265bf1087e6ddedcc58bc62beTim Janik * the inner loop. 246e6b78c9af1d6416f93311b98e1e6d802e2fe0617Ryan Lortie * 247e6b78c9af1d6416f93311b98e1e6d802e2fe0617Ryan Lortie * Additional optimisation: first check if our full hash 248e6b78c9af1d6416f93311b98e1e6d802e2fe0617Ryan Lortie * values are equal so we can avoid calling the full-blown 249e6b78c9af1d6416f93311b98e1e6d802e2fe0617Ryan Lortie * key equality function in most cases. 2502d68cbbb7d37d3f265bf1087e6ddedcc58bc62beTim Janik */ 251267b6813703e24ef60d0e8ba42557c414f9dd52eSebastian Wilhelmi if (hash_table->key_equal_func) 252e6b78c9af1d6416f93311b98e1e6d802e2fe0617Ryan Lortie while (*node && (((*node)->key_hash != hash_value) || 253e6b78c9af1d6416f93311b98e1e6d802e2fe0617Ryan Lortie !(*hash_table->key_equal_func) ((*node)->key, key))) 254d5492a983cfa048658af8b03f833ddb3c0cf355eEST node = &(*node)->next; 2552d68cbbb7d37d3f265bf1087e6ddedcc58bc62beTim Janik else 256d5492a983cfa048658af8b03f833ddb3c0cf355eEST while (*node && (*node)->key != key) 257d5492a983cfa048658af8b03f833ddb3c0cf355eEST node = &(*node)->next; 258e6b78c9af1d6416f93311b98e1e6d802e2fe0617Ryan Lortie 2592d68cbbb7d37d3f265bf1087e6ddedcc58bc62beTim Janik return node; 2602d68cbbb7d37d3f265bf1087e6ddedcc58bc62beTim Janik} 2612e0320d57e417f7d1c838d729a99545db2228e9Owen Taylor 262a2b269bae3315a2ea772b741fb62f683c1db5770Sven Neumann/** 263a2b269bae3315a2ea772b741fb62f683c1db5770Sven Neumann * g_hash_table_lookup: 264a2b269bae3315a2ea772b741fb62f683c1db5770Sven Neumann * @hash_table: a #GHashTable. 265a2b269bae3315a2ea772b741fb62f683c1db5770Sven Neumann * @key: the key to look up. 266a2b269bae3315a2ea772b741fb62f683c1db5770Sven Neumann * 267fd92ac8f5280ccb936a534a14f5c9cbdb24302e5Matthias Clasen * Looks up a key in a #GHashTable. Note that this function cannot 268fd92ac8f5280ccb936a534a14f5c9cbdb24302e5Matthias Clasen * distinguish between a key that is not present and one which is present 269fd92ac8f5280ccb936a534a14f5c9cbdb24302e5Matthias Clasen * and has the value %NULL. If you need this distinction, use 270fd92ac8f5280ccb936a534a14f5c9cbdb24302e5Matthias Clasen * g_hash_table_lookup_extended(). 271a2b269bae3315a2ea772b741fb62f683c1db5770Sven Neumann * 272a52e2986cd4a2147cfc8d41ae23d98907caaf3a0Matthias Clasen * Return value: the associated value, or %NULL if the key is not found. 273a2b269bae3315a2ea772b741fb62f683c1db5770Sven Neumann **/ 2742d68cbbb7d37d3f265bf1087e6ddedcc58bc62beTim Janikgpointer 2752d68cbbb7d37d3f265bf1087e6ddedcc58bc62beTim Janikg_hash_table_lookup (GHashTable *hash_table, 2762d68cbbb7d37d3f265bf1087e6ddedcc58bc62beTim Janik gconstpointer key) 2772d68cbbb7d37d3f265bf1087e6ddedcc58bc62beTim Janik{ 2782d68cbbb7d37d3f265bf1087e6ddedcc58bc62beTim Janik GHashNode *node; 2792d68cbbb7d37d3f265bf1087e6ddedcc58bc62beTim Janik 2802d68cbbb7d37d3f265bf1087e6ddedcc58bc62beTim Janik g_return_val_if_fail (hash_table != NULL, NULL); 2812d68cbbb7d37d3f265bf1087e6ddedcc58bc62beTim Janik 282e6b78c9af1d6416f93311b98e1e6d802e2fe0617Ryan Lortie node = *g_hash_table_lookup_node (hash_table, key, NULL); 2832d68cbbb7d37d3f265bf1087e6ddedcc58bc62beTim Janik 2842d68cbbb7d37d3f265bf1087e6ddedcc58bc62beTim Janik return node ? node->value : NULL; 2852d68cbbb7d37d3f265bf1087e6ddedcc58bc62beTim Janik} 2867401460a60504dad7b77219d0ba3d93112e12444Manish Singh 287a2b269bae3315a2ea772b741fb62f683c1db5770Sven Neumann/** 288a2b269bae3315a2ea772b741fb62f683c1db5770Sven Neumann * g_hash_table_lookup_extended: 289a2b269bae3315a2ea772b741fb62f683c1db5770Sven Neumann * @hash_table: a #GHashTable. 290a2b269bae3315a2ea772b741fb62f683c1db5770Sven Neumann * @lookup_key: the key to look up. 291a2b269bae3315a2ea772b741fb62f683c1db5770Sven Neumann * @orig_key: returns the original key. 292a2b269bae3315a2ea772b741fb62f683c1db5770Sven Neumann * @value: returns the value associated with the key. 293a2b269bae3315a2ea772b741fb62f683c1db5770Sven Neumann * 294a2b269bae3315a2ea772b741fb62f683c1db5770Sven Neumann * Looks up a key in the #GHashTable, returning the original key and the 295a52e2986cd4a2147cfc8d41ae23d98907caaf3a0Matthias Clasen * associated value and a #gboolean which is %TRUE if the key was found. This 296a2b269bae3315a2ea772b741fb62f683c1db5770Sven Neumann * is useful if you need to free the memory allocated for the original key, 297a2b269bae3315a2ea772b741fb62f683c1db5770Sven Neumann * for example before calling g_hash_table_remove(). 298a2b269bae3315a2ea772b741fb62f683c1db5770Sven Neumann * 2993fa33317b7e9866793ce1ea32d069e8c9270caa2Matthias Clasen * Return value: %TRUE if the key was found in the #GHashTable. 300a2b269bae3315a2ea772b741fb62f683c1db5770Sven Neumann **/ 301a2b269bae3315a2ea772b741fb62f683c1db5770Sven Neumanngboolean 302a2b269bae3315a2ea772b741fb62f683c1db5770Sven Neumanng_hash_table_lookup_extended (GHashTable *hash_table, 303a2b269bae3315a2ea772b741fb62f683c1db5770Sven Neumann gconstpointer lookup_key, 304a2b269bae3315a2ea772b741fb62f683c1db5770Sven Neumann gpointer *orig_key, 305a2b269bae3315a2ea772b741fb62f683c1db5770Sven Neumann gpointer *value) 306a2b269bae3315a2ea772b741fb62f683c1db5770Sven Neumann{ 307a2b269bae3315a2ea772b741fb62f683c1db5770Sven Neumann GHashNode *node; 308a2b269bae3315a2ea772b741fb62f683c1db5770Sven Neumann 309a2b269bae3315a2ea772b741fb62f683c1db5770Sven Neumann g_return_val_if_fail (hash_table != NULL, FALSE); 310a2b269bae3315a2ea772b741fb62f683c1db5770Sven Neumann 311e6b78c9af1d6416f93311b98e1e6d802e2fe0617Ryan Lortie node = *g_hash_table_lookup_node (hash_table, lookup_key, NULL); 312a2b269bae3315a2ea772b741fb62f683c1db5770Sven Neumann 313a2b269bae3315a2ea772b741fb62f683c1db5770Sven Neumann if (node) 314a2b269bae3315a2ea772b741fb62f683c1db5770Sven Neumann { 315a2b269bae3315a2ea772b741fb62f683c1db5770Sven Neumann if (orig_key) 316a2b269bae3315a2ea772b741fb62f683c1db5770Sven Neumann *orig_key = node->key; 317a2b269bae3315a2ea772b741fb62f683c1db5770Sven Neumann if (value) 318a2b269bae3315a2ea772b741fb62f683c1db5770Sven Neumann *value = node->value; 319a2b269bae3315a2ea772b741fb62f683c1db5770Sven Neumann return TRUE; 320a2b269bae3315a2ea772b741fb62f683c1db5770Sven Neumann } 321a2b269bae3315a2ea772b741fb62f683c1db5770Sven Neumann else 322a2b269bae3315a2ea772b741fb62f683c1db5770Sven Neumann return FALSE; 323a2b269bae3315a2ea772b741fb62f683c1db5770Sven Neumann} 324a2b269bae3315a2ea772b741fb62f683c1db5770Sven Neumann 3250adbacbff90cdab1b96e3409b6d510a00916b586Ryan Lortiestatic void 3260adbacbff90cdab1b96e3409b6d510a00916b586Ryan Lortieg_hash_table_insert_internal (GHashTable *hash_table, 3270adbacbff90cdab1b96e3409b6d510a00916b586Ryan Lortie gpointer key, 3280adbacbff90cdab1b96e3409b6d510a00916b586Ryan Lortie gpointer value, 3290adbacbff90cdab1b96e3409b6d510a00916b586Ryan Lortie gboolean keep_new_key) 3302d68cbbb7d37d3f265bf1087e6ddedcc58bc62beTim Janik{ 331d5492a983cfa048658af8b03f833ddb3c0cf355eEST GHashNode **node; 332e6b78c9af1d6416f93311b98e1e6d802e2fe0617Ryan Lortie guint key_hash; 3332d68cbbb7d37d3f265bf1087e6ddedcc58bc62beTim Janik 3342d68cbbb7d37d3f265bf1087e6ddedcc58bc62beTim Janik g_return_if_fail (hash_table != NULL); 3353e847a090cfd8495add631d43388c461b1a85716Tim Janik g_return_if_fail (hash_table->ref_count > 0); 3362d68cbbb7d37d3f265bf1087e6ddedcc58bc62beTim Janik 337e6b78c9af1d6416f93311b98e1e6d802e2fe0617Ryan Lortie node = g_hash_table_lookup_node (hash_table, key, &key_hash); 338d5492a983cfa048658af8b03f833ddb3c0cf355eEST 339d5492a983cfa048658af8b03f833ddb3c0cf355eEST if (*node) 3407519c2338ae484135b44bbb7eb49719aea8c4ca3Lauri Alanko { 3415e02b01b210513c19b76731d303a7256d2db273cRyan Lortie if (keep_new_key) 3420adbacbff90cdab1b96e3409b6d510a00916b586Ryan Lortie { 3435e02b01b210513c19b76731d303a7256d2db273cRyan Lortie if (hash_table->key_destroy_func) 3440adbacbff90cdab1b96e3409b6d510a00916b586Ryan Lortie hash_table->key_destroy_func ((*node)->key); 3455e02b01b210513c19b76731d303a7256d2db273cRyan Lortie (*node)->key = key; 3465e02b01b210513c19b76731d303a7256d2db273cRyan Lortie } 3475e02b01b210513c19b76731d303a7256d2db273cRyan Lortie else 3485e02b01b210513c19b76731d303a7256d2db273cRyan Lortie { 3495e02b01b210513c19b76731d303a7256d2db273cRyan Lortie if (hash_table->key_destroy_func) 3500adbacbff90cdab1b96e3409b6d510a00916b586Ryan Lortie hash_table->key_destroy_func (key); 3510adbacbff90cdab1b96e3409b6d510a00916b586Ryan Lortie } 352a2b269bae3315a2ea772b741fb62f683c1db5770Sven Neumann 353a2b269bae3315a2ea772b741fb62f683c1db5770Sven Neumann if (hash_table->value_destroy_func) 354a2b269bae3315a2ea772b741fb62f683c1db5770Sven Neumann hash_table->value_destroy_func ((*node)->value); 355a2b269bae3315a2ea772b741fb62f683c1db5770Sven Neumann 356a2b269bae3315a2ea772b741fb62f683c1db5770Sven Neumann (*node)->value = value; 357a2b269bae3315a2ea772b741fb62f683c1db5770Sven Neumann } 358a2b269bae3315a2ea772b741fb62f683c1db5770Sven Neumann else 359a2b269bae3315a2ea772b741fb62f683c1db5770Sven Neumann { 360e6b78c9af1d6416f93311b98e1e6d802e2fe0617Ryan Lortie *node = g_hash_node_new (key, value, key_hash); 361a2b269bae3315a2ea772b741fb62f683c1db5770Sven Neumann hash_table->nnodes++; 3628079eb3456914a03618b92b48f75a71b25331acbOwen Taylor G_HASH_TABLE_RESIZE (hash_table); 363a2b269bae3315a2ea772b741fb62f683c1db5770Sven Neumann } 364a2b269bae3315a2ea772b741fb62f683c1db5770Sven Neumann} 365a2b269bae3315a2ea772b741fb62f683c1db5770Sven Neumann 366a2b269bae3315a2ea772b741fb62f683c1db5770Sven Neumann/** 3670adbacbff90cdab1b96e3409b6d510a00916b586Ryan Lortie * g_hash_table_insert: 3680adbacbff90cdab1b96e3409b6d510a00916b586Ryan Lortie * @hash_table: a #GHashTable. 3690adbacbff90cdab1b96e3409b6d510a00916b586Ryan Lortie * @key: a key to insert. 3700adbacbff90cdab1b96e3409b6d510a00916b586Ryan Lortie * @value: the value to associate with the key. 3710adbacbff90cdab1b96e3409b6d510a00916b586Ryan Lortie * 3720adbacbff90cdab1b96e3409b6d510a00916b586Ryan Lortie * Inserts a new key and value into a #GHashTable. 3730adbacbff90cdab1b96e3409b6d510a00916b586Ryan Lortie * 3740adbacbff90cdab1b96e3409b6d510a00916b586Ryan Lortie * If the key already exists in the #GHashTable its current value is replaced 3750adbacbff90cdab1b96e3409b6d510a00916b586Ryan Lortie * with the new value. If you supplied a @value_destroy_func when creating the 3760adbacbff90cdab1b96e3409b6d510a00916b586Ryan Lortie * #GHashTable, the old value is freed using that function. If you supplied 3770adbacbff90cdab1b96e3409b6d510a00916b586Ryan Lortie * a @key_destroy_func when creating the #GHashTable, the passed key is freed 3780adbacbff90cdab1b96e3409b6d510a00916b586Ryan Lortie * using that function. 3790adbacbff90cdab1b96e3409b6d510a00916b586Ryan Lortie **/ 3800adbacbff90cdab1b96e3409b6d510a00916b586Ryan Lortievoid 3810adbacbff90cdab1b96e3409b6d510a00916b586Ryan Lortieg_hash_table_insert (GHashTable *hash_table, 3820adbacbff90cdab1b96e3409b6d510a00916b586Ryan Lortie gpointer key, 3830adbacbff90cdab1b96e3409b6d510a00916b586Ryan Lortie gpointer value) 3840adbacbff90cdab1b96e3409b6d510a00916b586Ryan Lortie{ 3850adbacbff90cdab1b96e3409b6d510a00916b586Ryan Lortie return g_hash_table_insert_internal (hash_table, key, value, FALSE); 3860adbacbff90cdab1b96e3409b6d510a00916b586Ryan Lortie} 3870adbacbff90cdab1b96e3409b6d510a00916b586Ryan Lortie 3880adbacbff90cdab1b96e3409b6d510a00916b586Ryan Lortie/** 389a2b269bae3315a2ea772b741fb62f683c1db5770Sven Neumann * g_hash_table_replace: 390a2b269bae3315a2ea772b741fb62f683c1db5770Sven Neumann * @hash_table: a #GHashTable. 391a2b269bae3315a2ea772b741fb62f683c1db5770Sven Neumann * @key: a key to insert. 392a2b269bae3315a2ea772b741fb62f683c1db5770Sven Neumann * @value: the value to associate with the key. 393a2b269bae3315a2ea772b741fb62f683c1db5770Sven Neumann * 394a2b269bae3315a2ea772b741fb62f683c1db5770Sven Neumann * Inserts a new key and value into a #GHashTable similar to 395a2b269bae3315a2ea772b741fb62f683c1db5770Sven Neumann * g_hash_table_insert(). The difference is that if the key already exists 396a2b269bae3315a2ea772b741fb62f683c1db5770Sven Neumann * in the #GHashTable, it gets replaced by the new key. If you supplied a 397a52e2986cd4a2147cfc8d41ae23d98907caaf3a0Matthias Clasen * @value_destroy_func when creating the #GHashTable, the old value is freed 398a52e2986cd4a2147cfc8d41ae23d98907caaf3a0Matthias Clasen * using that function. If you supplied a @key_destroy_func when creating the 399a2b269bae3315a2ea772b741fb62f683c1db5770Sven Neumann * #GHashTable, the old key is freed using that function. 400a2b269bae3315a2ea772b741fb62f683c1db5770Sven Neumann **/ 401a2b269bae3315a2ea772b741fb62f683c1db5770Sven Neumannvoid 402a2b269bae3315a2ea772b741fb62f683c1db5770Sven Neumanng_hash_table_replace (GHashTable *hash_table, 403a2b269bae3315a2ea772b741fb62f683c1db5770Sven Neumann gpointer key, 404a2b269bae3315a2ea772b741fb62f683c1db5770Sven Neumann gpointer value) 405a2b269bae3315a2ea772b741fb62f683c1db5770Sven Neumann{ 4060adbacbff90cdab1b96e3409b6d510a00916b586Ryan Lortie return g_hash_table_insert_internal (hash_table, key, value, TRUE); 4072e0320d57e417f7d1c838d729a99545db2228e9Owen Taylor} 4082e0320d57e417f7d1c838d729a99545db2228e9Owen Taylor 409e9010a86f763e6b7cb1fd5520985c929339f5523Ryan Lortiestatic void 410e9010a86f763e6b7cb1fd5520985c929339f5523Ryan Lortieg_hash_table_remove_node (GHashTable *hash_table, 411e9010a86f763e6b7cb1fd5520985c929339f5523Ryan Lortie GHashNode ***node_ptr_ptr, 412e9010a86f763e6b7cb1fd5520985c929339f5523Ryan Lortie gboolean notify) 413e9010a86f763e6b7cb1fd5520985c929339f5523Ryan Lortie{ 414e9010a86f763e6b7cb1fd5520985c929339f5523Ryan Lortie GHashNode **node_ptr, *node; 415e9010a86f763e6b7cb1fd5520985c929339f5523Ryan Lortie 416e9010a86f763e6b7cb1fd5520985c929339f5523Ryan Lortie node_ptr = *node_ptr_ptr; 417e9010a86f763e6b7cb1fd5520985c929339f5523Ryan Lortie node = *node_ptr; 418e9010a86f763e6b7cb1fd5520985c929339f5523Ryan Lortie 419e9010a86f763e6b7cb1fd5520985c929339f5523Ryan Lortie *node_ptr = node->next; 420e9010a86f763e6b7cb1fd5520985c929339f5523Ryan Lortie 421e9010a86f763e6b7cb1fd5520985c929339f5523Ryan Lortie g_hash_node_destroy (node, 422e9010a86f763e6b7cb1fd5520985c929339f5523Ryan Lortie notify ? hash_table->key_destroy_func : NULL, 423e9010a86f763e6b7cb1fd5520985c929339f5523Ryan Lortie notify ? hash_table->value_destroy_func : NULL); 424e9010a86f763e6b7cb1fd5520985c929339f5523Ryan Lortie 425e9010a86f763e6b7cb1fd5520985c929339f5523Ryan Lortie hash_table->nnodes--; 426e9010a86f763e6b7cb1fd5520985c929339f5523Ryan Lortie} 427e9010a86f763e6b7cb1fd5520985c929339f5523Ryan Lortie 428e9010a86f763e6b7cb1fd5520985c929339f5523Ryan Lortiestatic gboolean 429e9010a86f763e6b7cb1fd5520985c929339f5523Ryan Lortieg_hash_table_remove_internal (GHashTable *hash_table, 430e9010a86f763e6b7cb1fd5520985c929339f5523Ryan Lortie gconstpointer key, 431e9010a86f763e6b7cb1fd5520985c929339f5523Ryan Lortie gboolean notify) 432e9010a86f763e6b7cb1fd5520985c929339f5523Ryan Lortie{ 433e9010a86f763e6b7cb1fd5520985c929339f5523Ryan Lortie GHashNode **node_ptr; 434e9010a86f763e6b7cb1fd5520985c929339f5523Ryan Lortie 435e9010a86f763e6b7cb1fd5520985c929339f5523Ryan Lortie g_return_val_if_fail (hash_table != NULL, FALSE); 436e9010a86f763e6b7cb1fd5520985c929339f5523Ryan Lortie 437e9010a86f763e6b7cb1fd5520985c929339f5523Ryan Lortie node_ptr = g_hash_table_lookup_node (hash_table, key, NULL); 438e9010a86f763e6b7cb1fd5520985c929339f5523Ryan Lortie if (*node_ptr == NULL) 439e9010a86f763e6b7cb1fd5520985c929339f5523Ryan Lortie return FALSE; 440e9010a86f763e6b7cb1fd5520985c929339f5523Ryan Lortie 441e9010a86f763e6b7cb1fd5520985c929339f5523Ryan Lortie g_hash_table_remove_node (hash_table, &node_ptr, FALSE); 442e9010a86f763e6b7cb1fd5520985c929339f5523Ryan Lortie G_HASH_TABLE_RESIZE (hash_table); 443e9010a86f763e6b7cb1fd5520985c929339f5523Ryan Lortie 444e9010a86f763e6b7cb1fd5520985c929339f5523Ryan Lortie return TRUE; 445e9010a86f763e6b7cb1fd5520985c929339f5523Ryan Lortie} 446e9010a86f763e6b7cb1fd5520985c929339f5523Ryan Lortie 447a2b269bae3315a2ea772b741fb62f683c1db5770Sven Neumann/** 448a2b269bae3315a2ea772b741fb62f683c1db5770Sven Neumann * g_hash_table_remove: 449a2b269bae3315a2ea772b741fb62f683c1db5770Sven Neumann * @hash_table: a #GHashTable. 450a2b269bae3315a2ea772b741fb62f683c1db5770Sven Neumann * @key: the key to remove. 451a2b269bae3315a2ea772b741fb62f683c1db5770Sven Neumann * 452a2b269bae3315a2ea772b741fb62f683c1db5770Sven Neumann * Removes a key and its associated value from a #GHashTable. 453a2b269bae3315a2ea772b741fb62f683c1db5770Sven Neumann * 454a2b269bae3315a2ea772b741fb62f683c1db5770Sven Neumann * If the #GHashTable was created using g_hash_table_new_full(), the 455a52e2986cd4a2147cfc8d41ae23d98907caaf3a0Matthias Clasen * key and value are freed using the supplied destroy functions, otherwise 456a2b269bae3315a2ea772b741fb62f683c1db5770Sven Neumann * you have to make sure that any dynamically allocated values are freed 457a2b269bae3315a2ea772b741fb62f683c1db5770Sven Neumann * yourself. 458a2b269bae3315a2ea772b741fb62f683c1db5770Sven Neumann * 4593fa33317b7e9866793ce1ea32d069e8c9270caa2Matthias Clasen * Return value: %TRUE if the key was found and removed from the #GHashTable. 460a2b269bae3315a2ea772b741fb62f683c1db5770Sven Neumann **/ 4619a8c33db5cc37bc3c6bd4794a03f4b99a847ff4aTim Janikgboolean 462a2b269bae3315a2ea772b741fb62f683c1db5770Sven Neumanng_hash_table_remove (GHashTable *hash_table, 463e9010a86f763e6b7cb1fd5520985c929339f5523Ryan Lortie gconstpointer key) 4642e0320d57e417f7d1c838d729a99545db2228e9Owen Taylor{ 465e9010a86f763e6b7cb1fd5520985c929339f5523Ryan Lortie return g_hash_table_remove_internal (hash_table, key, TRUE); 4662e0320d57e417f7d1c838d729a99545db2228e9Owen Taylor} 4672e0320d57e417f7d1c838d729a99545db2228e9Owen Taylor 468a2b269bae3315a2ea772b741fb62f683c1db5770Sven Neumann/** 469a5b4b8bfb18838454d99bdee60294da07e5ef0d2Matthias Clasen * g_hash_table_remove_all: 470a5b4b8bfb18838454d99bdee60294da07e5ef0d2Matthias Clasen * @hash_table: a #GHashTable 471a5b4b8bfb18838454d99bdee60294da07e5ef0d2Matthias Clasen * 472a5b4b8bfb18838454d99bdee60294da07e5ef0d2Matthias Clasen * Removes all keys and their associated values from a #GHashTable. 473a5b4b8bfb18838454d99bdee60294da07e5ef0d2Matthias Clasen * 474a5b4b8bfb18838454d99bdee60294da07e5ef0d2Matthias Clasen * If the #GHashTable was created using g_hash_table_new_full(), the keys 475a5b4b8bfb18838454d99bdee60294da07e5ef0d2Matthias Clasen * and values are freed using the supplied destroy functions, otherwise you 476a5b4b8bfb18838454d99bdee60294da07e5ef0d2Matthias Clasen * have to make sure that any dynamically allocated values are freed 477a5b4b8bfb18838454d99bdee60294da07e5ef0d2Matthias Clasen * yourself. 478a5b4b8bfb18838454d99bdee60294da07e5ef0d2Matthias Clasen * 479a5b4b8bfb18838454d99bdee60294da07e5ef0d2Matthias Clasen * Since: 2.12 480a5b4b8bfb18838454d99bdee60294da07e5ef0d2Matthias Clasen **/ 481a5b4b8bfb18838454d99bdee60294da07e5ef0d2Matthias Clasenvoid 482a5b4b8bfb18838454d99bdee60294da07e5ef0d2Matthias Claseng_hash_table_remove_all (GHashTable *hash_table) 483a5b4b8bfb18838454d99bdee60294da07e5ef0d2Matthias Clasen{ 484a5b4b8bfb18838454d99bdee60294da07e5ef0d2Matthias Clasen guint i; 485a5b4b8bfb18838454d99bdee60294da07e5ef0d2Matthias Clasen 486a5b4b8bfb18838454d99bdee60294da07e5ef0d2Matthias Clasen g_return_if_fail (hash_table != NULL); 487a5b4b8bfb18838454d99bdee60294da07e5ef0d2Matthias Clasen 488a5b4b8bfb18838454d99bdee60294da07e5ef0d2Matthias Clasen for (i = 0; i < hash_table->size; i++) 489a5b4b8bfb18838454d99bdee60294da07e5ef0d2Matthias Clasen { 490a5b4b8bfb18838454d99bdee60294da07e5ef0d2Matthias Clasen g_hash_nodes_destroy (hash_table->nodes[i], 491a5b4b8bfb18838454d99bdee60294da07e5ef0d2Matthias Clasen hash_table->key_destroy_func, 492a5b4b8bfb18838454d99bdee60294da07e5ef0d2Matthias Clasen hash_table->value_destroy_func); 493a5b4b8bfb18838454d99bdee60294da07e5ef0d2Matthias Clasen hash_table->nodes[i] = NULL; 494a5b4b8bfb18838454d99bdee60294da07e5ef0d2Matthias Clasen } 495a5b4b8bfb18838454d99bdee60294da07e5ef0d2Matthias Clasen hash_table->nnodes = 0; 496a5b4b8bfb18838454d99bdee60294da07e5ef0d2Matthias Clasen 497a5b4b8bfb18838454d99bdee60294da07e5ef0d2Matthias Clasen G_HASH_TABLE_RESIZE (hash_table); 498a5b4b8bfb18838454d99bdee60294da07e5ef0d2Matthias Clasen} 499a5b4b8bfb18838454d99bdee60294da07e5ef0d2Matthias Clasen 500a5b4b8bfb18838454d99bdee60294da07e5ef0d2Matthias Clasen/** 501a2b269bae3315a2ea772b741fb62f683c1db5770Sven Neumann * g_hash_table_steal: 502a2b269bae3315a2ea772b741fb62f683c1db5770Sven Neumann * @hash_table: a #GHashTable. 503a2b269bae3315a2ea772b741fb62f683c1db5770Sven Neumann * @key: the key to remove. 504a2b269bae3315a2ea772b741fb62f683c1db5770Sven Neumann * 505a2b269bae3315a2ea772b741fb62f683c1db5770Sven Neumann * Removes a key and its associated value from a #GHashTable without 506a2b269bae3315a2ea772b741fb62f683c1db5770Sven Neumann * calling the key and value destroy functions. 507a2b269bae3315a2ea772b741fb62f683c1db5770Sven Neumann * 5083fa33317b7e9866793ce1ea32d069e8c9270caa2Matthias Clasen * Return value: %TRUE if the key was found and removed from the #GHashTable. 509a2b269bae3315a2ea772b741fb62f683c1db5770Sven Neumann **/ 5107519c2338ae484135b44bbb7eb49719aea8c4ca3Lauri Alankogboolean 511a2b269bae3315a2ea772b741fb62f683c1db5770Sven Neumanng_hash_table_steal (GHashTable *hash_table, 512a2b269bae3315a2ea772b741fb62f683c1db5770Sven Neumann gconstpointer key) 5137519c2338ae484135b44bbb7eb49719aea8c4ca3Lauri Alanko{ 514e9010a86f763e6b7cb1fd5520985c929339f5523Ryan Lortie return g_hash_table_remove_internal (hash_table, key, FALSE); 5152e0320d57e417f7d1c838d729a99545db2228e9Owen Taylor} 5162e0320d57e417f7d1c838d729a99545db2228e9Owen Taylor 517a2b269bae3315a2ea772b741fb62f683c1db5770Sven Neumann/** 518a5b4b8bfb18838454d99bdee60294da07e5ef0d2Matthias Clasen * g_hash_table_steal_all: 519a5b4b8bfb18838454d99bdee60294da07e5ef0d2Matthias Clasen * @hash_table: a #GHashTable. 520a5b4b8bfb18838454d99bdee60294da07e5ef0d2Matthias Clasen * 521a5b4b8bfb18838454d99bdee60294da07e5ef0d2Matthias Clasen * Removes all keys and their associated values from a #GHashTable 522a5b4b8bfb18838454d99bdee60294da07e5ef0d2Matthias Clasen * without calling the key and value destroy functions. 523a5b4b8bfb18838454d99bdee60294da07e5ef0d2Matthias Clasen * 524a5b4b8bfb18838454d99bdee60294da07e5ef0d2Matthias Clasen * Since: 2.12 525a5b4b8bfb18838454d99bdee60294da07e5ef0d2Matthias Clasen **/ 526a5b4b8bfb18838454d99bdee60294da07e5ef0d2Matthias Clasenvoid 527a5b4b8bfb18838454d99bdee60294da07e5ef0d2Matthias Claseng_hash_table_steal_all (GHashTable *hash_table) 528a5b4b8bfb18838454d99bdee60294da07e5ef0d2Matthias Clasen{ 529a5b4b8bfb18838454d99bdee60294da07e5ef0d2Matthias Clasen guint i; 530a5b4b8bfb18838454d99bdee60294da07e5ef0d2Matthias Clasen 531a5b4b8bfb18838454d99bdee60294da07e5ef0d2Matthias Clasen g_return_if_fail (hash_table != NULL); 532a5b4b8bfb18838454d99bdee60294da07e5ef0d2Matthias Clasen 533a5b4b8bfb18838454d99bdee60294da07e5ef0d2Matthias Clasen for (i = 0; i < hash_table->size; i++) 534a5b4b8bfb18838454d99bdee60294da07e5ef0d2Matthias Clasen { 535a5b4b8bfb18838454d99bdee60294da07e5ef0d2Matthias Clasen g_hash_nodes_destroy (hash_table->nodes[i], NULL, NULL); 536a5b4b8bfb18838454d99bdee60294da07e5ef0d2Matthias Clasen hash_table->nodes[i] = NULL; 537a5b4b8bfb18838454d99bdee60294da07e5ef0d2Matthias Clasen } 538a5b4b8bfb18838454d99bdee60294da07e5ef0d2Matthias Clasen 539a5b4b8bfb18838454d99bdee60294da07e5ef0d2Matthias Clasen hash_table->nnodes = 0; 540a5b4b8bfb18838454d99bdee60294da07e5ef0d2Matthias Clasen 541a5b4b8bfb18838454d99bdee60294da07e5ef0d2Matthias Clasen G_HASH_TABLE_RESIZE (hash_table); 542a5b4b8bfb18838454d99bdee60294da07e5ef0d2Matthias Clasen} 543a5b4b8bfb18838454d99bdee60294da07e5ef0d2Matthias Clasen 544a5b4b8bfb18838454d99bdee60294da07e5ef0d2Matthias Clasen/** 545a2b269bae3315a2ea772b741fb62f683c1db5770Sven Neumann * g_hash_table_foreach_remove: 546a2b269bae3315a2ea772b741fb62f683c1db5770Sven Neumann * @hash_table: a #GHashTable. 547a2b269bae3315a2ea772b741fb62f683c1db5770Sven Neumann * @func: the function to call for each key/value pair. 548a2b269bae3315a2ea772b741fb62f683c1db5770Sven Neumann * @user_data: user data to pass to the function. 549a2b269bae3315a2ea772b741fb62f683c1db5770Sven Neumann * 550a2b269bae3315a2ea772b741fb62f683c1db5770Sven Neumann * Calls the given function for each key/value pair in the #GHashTable. 551a52e2986cd4a2147cfc8d41ae23d98907caaf3a0Matthias Clasen * If the function returns %TRUE, then the key/value pair is removed from the 552a2b269bae3315a2ea772b741fb62f683c1db5770Sven Neumann * #GHashTable. If you supplied key or value destroy functions when creating 553a2b269bae3315a2ea772b741fb62f683c1db5770Sven Neumann * the #GHashTable, they are used to free the memory allocated for the removed 554a2b269bae3315a2ea772b741fb62f683c1db5770Sven Neumann * keys and values. 555a2b269bae3315a2ea772b741fb62f683c1db5770Sven Neumann * 556a2b269bae3315a2ea772b741fb62f683c1db5770Sven Neumann * Return value: the number of key/value pairs removed. 557a2b269bae3315a2ea772b741fb62f683c1db5770Sven Neumann **/ 558a2b269bae3315a2ea772b741fb62f683c1db5770Sven Neumannguint 559a2b269bae3315a2ea772b741fb62f683c1db5770Sven Neumanng_hash_table_foreach_remove (GHashTable *hash_table, 560a2b269bae3315a2ea772b741fb62f683c1db5770Sven Neumann GHRFunc func, 561a2b269bae3315a2ea772b741fb62f683c1db5770Sven Neumann gpointer user_data) 5622e0320d57e417f7d1c838d729a99545db2228e9Owen Taylor{ 563a2b269bae3315a2ea772b741fb62f683c1db5770Sven Neumann g_return_val_if_fail (hash_table != NULL, 0); 564a2b269bae3315a2ea772b741fb62f683c1db5770Sven Neumann g_return_val_if_fail (func != NULL, 0); 565a2b269bae3315a2ea772b741fb62f683c1db5770Sven Neumann 566a2b269bae3315a2ea772b741fb62f683c1db5770Sven Neumann return g_hash_table_foreach_remove_or_steal (hash_table, func, user_data, TRUE); 5672e0320d57e417f7d1c838d729a99545db2228e9Owen Taylor} 5682e0320d57e417f7d1c838d729a99545db2228e9Owen Taylor 569a2b269bae3315a2ea772b741fb62f683c1db5770Sven Neumann/** 570a2b269bae3315a2ea772b741fb62f683c1db5770Sven Neumann * g_hash_table_foreach_steal: 571a2b269bae3315a2ea772b741fb62f683c1db5770Sven Neumann * @hash_table: a #GHashTable. 572a2b269bae3315a2ea772b741fb62f683c1db5770Sven Neumann * @func: the function to call for each key/value pair. 573a2b269bae3315a2ea772b741fb62f683c1db5770Sven Neumann * @user_data: user data to pass to the function. 574a2b269bae3315a2ea772b741fb62f683c1db5770Sven Neumann * 575a2b269bae3315a2ea772b741fb62f683c1db5770Sven Neumann * Calls the given function for each key/value pair in the #GHashTable. 576a52e2986cd4a2147cfc8d41ae23d98907caaf3a0Matthias Clasen * If the function returns %TRUE, then the key/value pair is removed from the 577a2b269bae3315a2ea772b741fb62f683c1db5770Sven Neumann * #GHashTable, but no key or value destroy functions are called. 578a2b269bae3315a2ea772b741fb62f683c1db5770Sven Neumann * 579a2b269bae3315a2ea772b741fb62f683c1db5770Sven Neumann * Return value: the number of key/value pairs removed. 580a2b269bae3315a2ea772b741fb62f683c1db5770Sven Neumann **/ 581a2b269bae3315a2ea772b741fb62f683c1db5770Sven Neumannguint 582a2b269bae3315a2ea772b741fb62f683c1db5770Sven Neumanng_hash_table_foreach_steal (GHashTable *hash_table, 583a2b269bae3315a2ea772b741fb62f683c1db5770Sven Neumann GHRFunc func, 584a2b269bae3315a2ea772b741fb62f683c1db5770Sven Neumann gpointer user_data) 5852e0320d57e417f7d1c838d729a99545db2228e9Owen Taylor{ 586a2b269bae3315a2ea772b741fb62f683c1db5770Sven Neumann g_return_val_if_fail (hash_table != NULL, 0); 587a2b269bae3315a2ea772b741fb62f683c1db5770Sven Neumann g_return_val_if_fail (func != NULL, 0); 588a2b269bae3315a2ea772b741fb62f683c1db5770Sven Neumann 589a2b269bae3315a2ea772b741fb62f683c1db5770Sven Neumann return g_hash_table_foreach_remove_or_steal (hash_table, func, user_data, FALSE); 5902e0320d57e417f7d1c838d729a99545db2228e9Owen Taylor} 5912e0320d57e417f7d1c838d729a99545db2228e9Owen Taylor 592a2b269bae3315a2ea772b741fb62f683c1db5770Sven Neumannstatic guint 593a2b269bae3315a2ea772b741fb62f683c1db5770Sven Neumanng_hash_table_foreach_remove_or_steal (GHashTable *hash_table, 594a2b269bae3315a2ea772b741fb62f683c1db5770Sven Neumann GHRFunc func, 595a2b269bae3315a2ea772b741fb62f683c1db5770Sven Neumann gpointer user_data, 596a2b269bae3315a2ea772b741fb62f683c1db5770Sven Neumann gboolean notify) 597034e7c0339f64d4d52a53f2324daa2fca0332addManish Singh{ 598e9010a86f763e6b7cb1fd5520985c929339f5523Ryan Lortie GHashNode *node, **node_ptr; 599d31ba84c8ea40b6f0199318e43cc2bb2e816c586Tim Janik guint deleted = 0; 600e9010a86f763e6b7cb1fd5520985c929339f5523Ryan Lortie gint i; 601e9010a86f763e6b7cb1fd5520985c929339f5523Ryan Lortie 602034e7c0339f64d4d52a53f2324daa2fca0332addManish Singh for (i = 0; i < hash_table->size; i++) 603e9010a86f763e6b7cb1fd5520985c929339f5523Ryan Lortie for (node_ptr = &hash_table->nodes[i]; (node = *node_ptr) != NULL;) 604e9010a86f763e6b7cb1fd5520985c929339f5523Ryan Lortie if ((* func) (node->key, node->value, user_data)) 605e9010a86f763e6b7cb1fd5520985c929339f5523Ryan Lortie { 606e9010a86f763e6b7cb1fd5520985c929339f5523Ryan Lortie g_hash_table_remove_node (hash_table, &node_ptr, notify); 607e9010a86f763e6b7cb1fd5520985c929339f5523Ryan Lortie deleted++; 608e9010a86f763e6b7cb1fd5520985c929339f5523Ryan Lortie } 609e9010a86f763e6b7cb1fd5520985c929339f5523Ryan Lortie else 610e9010a86f763e6b7cb1fd5520985c929339f5523Ryan Lortie node_ptr = &node->next; 611e9010a86f763e6b7cb1fd5520985c929339f5523Ryan Lortie 6128079eb3456914a03618b92b48f75a71b25331acbOwen Taylor G_HASH_TABLE_RESIZE (hash_table); 613e9010a86f763e6b7cb1fd5520985c929339f5523Ryan Lortie 614034e7c0339f64d4d52a53f2324daa2fca0332addManish Singh return deleted; 615034e7c0339f64d4d52a53f2324daa2fca0332addManish Singh} 616034e7c0339f64d4d52a53f2324daa2fca0332addManish Singh 617a2b269bae3315a2ea772b741fb62f683c1db5770Sven Neumann/** 618a2b269bae3315a2ea772b741fb62f683c1db5770Sven Neumann * g_hash_table_foreach: 619a2b269bae3315a2ea772b741fb62f683c1db5770Sven Neumann * @hash_table: a #GHashTable. 620a2b269bae3315a2ea772b741fb62f683c1db5770Sven Neumann * @func: the function to call for each key/value pair. 621a2b269bae3315a2ea772b741fb62f683c1db5770Sven Neumann * @user_data: user data to pass to the function. 622a2b269bae3315a2ea772b741fb62f683c1db5770Sven Neumann * 623eb2f6f6fc1052abfa05f016ab2aed0cd0c338992Havoc Pennington * Calls the given function for each of the key/value pairs in the 624eb2f6f6fc1052abfa05f016ab2aed0cd0c338992Havoc Pennington * #GHashTable. The function is passed the key and value of each 625eb2f6f6fc1052abfa05f016ab2aed0cd0c338992Havoc Pennington * pair, and the given @user_data parameter. The hash table may not 626eb2f6f6fc1052abfa05f016ab2aed0cd0c338992Havoc Pennington * be modified while iterating over it (you can't add/remove 627eb2f6f6fc1052abfa05f016ab2aed0cd0c338992Havoc Pennington * items). To remove all items matching a predicate, use 62827096aedb58342fc8a25c17fa7d6647209425f4eMatthias Clasen * g_hash_table_foreach_remove(). 6292ef43de2af9dbb1b1ea583639c7339afe9c09af0Tim Janik * 6302ef43de2af9dbb1b1ea583639c7339afe9c09af0Tim Janik * See g_hash_table_find() for performance caveats for linear 6312ef43de2af9dbb1b1ea583639c7339afe9c09af0Tim Janik * order searches in contrast to g_hash_table_lookup(). 632a2b269bae3315a2ea772b741fb62f683c1db5770Sven Neumann **/ 6332e0320d57e417f7d1c838d729a99545db2228e9Owen Taylorvoid 6342e0320d57e417f7d1c838d729a99545db2228e9Owen Taylorg_hash_table_foreach (GHashTable *hash_table, 6352d68cbbb7d37d3f265bf1087e6ddedcc58bc62beTim Janik GHFunc func, 6362d68cbbb7d37d3f265bf1087e6ddedcc58bc62beTim Janik gpointer user_data) 6372e0320d57e417f7d1c838d729a99545db2228e9Owen Taylor{ 6382e0320d57e417f7d1c838d729a99545db2228e9Owen Taylor GHashNode *node; 6392e0320d57e417f7d1c838d729a99545db2228e9Owen Taylor gint i; 6402d68cbbb7d37d3f265bf1087e6ddedcc58bc62beTim Janik 6412d68cbbb7d37d3f265bf1087e6ddedcc58bc62beTim Janik g_return_if_fail (hash_table != NULL); 6422d68cbbb7d37d3f265bf1087e6ddedcc58bc62beTim Janik g_return_if_fail (func != NULL); 6432d68cbbb7d37d3f265bf1087e6ddedcc58bc62beTim Janik 6447519c2338ae484135b44bbb7eb49719aea8c4ca3Lauri Alanko for (i = 0; i < hash_table->size; i++) 6457519c2338ae484135b44bbb7eb49719aea8c4ca3Lauri Alanko for (node = hash_table->nodes[i]; node; node = node->next) 6467519c2338ae484135b44bbb7eb49719aea8c4ca3Lauri Alanko (* func) (node->key, node->value, user_data); 6472e0320d57e417f7d1c838d729a99545db2228e9Owen Taylor} 6482e0320d57e417f7d1c838d729a99545db2228e9Owen Taylor 649a2b269bae3315a2ea772b741fb62f683c1db5770Sven Neumann/** 650ee4e622d3724a6dfee8ce9463eccb31081cf852fTim Janik * g_hash_table_find: 651ee4e622d3724a6dfee8ce9463eccb31081cf852fTim Janik * @hash_table: a #GHashTable. 652ee4e622d3724a6dfee8ce9463eccb31081cf852fTim Janik * @predicate: function to test the key/value pairs for a certain property. 653ee4e622d3724a6dfee8ce9463eccb31081cf852fTim Janik * @user_data: user data to pass to the function. 654ee4e622d3724a6dfee8ce9463eccb31081cf852fTim Janik * 6553ce97fa284cbefdc2eb957f50a3a76d6ef923464Matthias Clasen * Calls the given function for key/value pairs in the #GHashTable until 6563ce97fa284cbefdc2eb957f50a3a76d6ef923464Matthias Clasen * @predicate returns %TRUE. The function is passed the key and value of 6573ce97fa284cbefdc2eb957f50a3a76d6ef923464Matthias Clasen * each pair, and the given @user_data parameter. The hash table may not 6582ef43de2af9dbb1b1ea583639c7339afe9c09af0Tim Janik * be modified while iterating over it (you can't add/remove items). 6592ef43de2af9dbb1b1ea583639c7339afe9c09af0Tim Janik * 6602ef43de2af9dbb1b1ea583639c7339afe9c09af0Tim Janik * Note, that hash tables are really only optimized for forward lookups, 6612ef43de2af9dbb1b1ea583639c7339afe9c09af0Tim Janik * i.e. g_hash_table_lookup(). 6622ef43de2af9dbb1b1ea583639c7339afe9c09af0Tim Janik * So code that frequently issues g_hash_table_find() or 6632ef43de2af9dbb1b1ea583639c7339afe9c09af0Tim Janik * g_hash_table_foreach() (e.g. in the order of once per every entry in a 6642ef43de2af9dbb1b1ea583639c7339afe9c09af0Tim Janik * hash table) should probably be reworked to use additional or different 6652ef43de2af9dbb1b1ea583639c7339afe9c09af0Tim Janik * data structures for reverse lookups (keep in mind that an O(n) find/foreach 6662ef43de2af9dbb1b1ea583639c7339afe9c09af0Tim Janik * operation issued for all n values in a hash table ends up needing O(n*n) 6672ef43de2af9dbb1b1ea583639c7339afe9c09af0Tim Janik * operations). 6683ce97fa284cbefdc2eb957f50a3a76d6ef923464Matthias Clasen * 6692ef43de2af9dbb1b1ea583639c7339afe9c09af0Tim Janik * Return value: The value of the first key/value pair is returned, for which 6702ef43de2af9dbb1b1ea583639c7339afe9c09af0Tim Janik * func evaluates to %TRUE. If no pair with the requested property is found, 6713ce97fa284cbefdc2eb957f50a3a76d6ef923464Matthias Clasen * %NULL is returned. 6723ce97fa284cbefdc2eb957f50a3a76d6ef923464Matthias Clasen * 6733ce97fa284cbefdc2eb957f50a3a76d6ef923464Matthias Clasen * Since: 2.4 674ee4e622d3724a6dfee8ce9463eccb31081cf852fTim Janik **/ 675ee4e622d3724a6dfee8ce9463eccb31081cf852fTim Janikgpointer 676ee4e622d3724a6dfee8ce9463eccb31081cf852fTim Janikg_hash_table_find (GHashTable *hash_table, 677ee4e622d3724a6dfee8ce9463eccb31081cf852fTim Janik GHRFunc predicate, 678ee4e622d3724a6dfee8ce9463eccb31081cf852fTim Janik gpointer user_data) 679ee4e622d3724a6dfee8ce9463eccb31081cf852fTim Janik{ 680ee4e622d3724a6dfee8ce9463eccb31081cf852fTim Janik GHashNode *node; 681ee4e622d3724a6dfee8ce9463eccb31081cf852fTim Janik gint i; 682ee4e622d3724a6dfee8ce9463eccb31081cf852fTim Janik 683ee4e622d3724a6dfee8ce9463eccb31081cf852fTim Janik g_return_val_if_fail (hash_table != NULL, NULL); 684ee4e622d3724a6dfee8ce9463eccb31081cf852fTim Janik g_return_val_if_fail (predicate != NULL, NULL); 685ee4e622d3724a6dfee8ce9463eccb31081cf852fTim Janik 686ee4e622d3724a6dfee8ce9463eccb31081cf852fTim Janik for (i = 0; i < hash_table->size; i++) 687ee4e622d3724a6dfee8ce9463eccb31081cf852fTim Janik for (node = hash_table->nodes[i]; node; node = node->next) 688ee4e622d3724a6dfee8ce9463eccb31081cf852fTim Janik if (predicate (node->key, node->value, user_data)) 689ee4e622d3724a6dfee8ce9463eccb31081cf852fTim Janik return node->value; 690ee4e622d3724a6dfee8ce9463eccb31081cf852fTim Janik return NULL; 691ee4e622d3724a6dfee8ce9463eccb31081cf852fTim Janik} 692ee4e622d3724a6dfee8ce9463eccb31081cf852fTim Janik 693ee4e622d3724a6dfee8ce9463eccb31081cf852fTim Janik/** 694a2b269bae3315a2ea772b741fb62f683c1db5770Sven Neumann * g_hash_table_size: 695a2b269bae3315a2ea772b741fb62f683c1db5770Sven Neumann * @hash_table: a #GHashTable. 696a2b269bae3315a2ea772b741fb62f683c1db5770Sven Neumann * 697a2b269bae3315a2ea772b741fb62f683c1db5770Sven Neumann * Returns the number of elements contained in the #GHashTable. 698a2b269bae3315a2ea772b741fb62f683c1db5770Sven Neumann * 699a2b269bae3315a2ea772b741fb62f683c1db5770Sven Neumann * Return value: the number of key/value pairs in the #GHashTable. 700a2b269bae3315a2ea772b741fb62f683c1db5770Sven Neumann **/ 701d31ba84c8ea40b6f0199318e43cc2bb2e816c586Tim Janikguint 7022d68cbbb7d37d3f265bf1087e6ddedcc58bc62beTim Janikg_hash_table_size (GHashTable *hash_table) 7037519c2338ae484135b44bbb7eb49719aea8c4ca3Lauri Alanko{ 7042d68cbbb7d37d3f265bf1087e6ddedcc58bc62beTim Janik g_return_val_if_fail (hash_table != NULL, 0); 7052d68cbbb7d37d3f265bf1087e6ddedcc58bc62beTim Janik 7067519c2338ae484135b44bbb7eb49719aea8c4ca3Lauri Alanko return hash_table->nnodes; 7077519c2338ae484135b44bbb7eb49719aea8c4ca3Lauri Alanko} 7082e0320d57e417f7d1c838d729a99545db2228e9Owen Taylor 709db8642a56c0436aeb730ead593140bc01b82d4acEmmanuele Bassi/** 710db8642a56c0436aeb730ead593140bc01b82d4acEmmanuele Bassi * g_hash_table_get_keys: 711db8642a56c0436aeb730ead593140bc01b82d4acEmmanuele Bassi * @hash_table: a #GHashTable 712db8642a56c0436aeb730ead593140bc01b82d4acEmmanuele Bassi * 713db8642a56c0436aeb730ead593140bc01b82d4acEmmanuele Bassi * Retrieves every key inside @hash_table. The returned data is valid 714db8642a56c0436aeb730ead593140bc01b82d4acEmmanuele Bassi * until @hash_table is modified. 715db8642a56c0436aeb730ead593140bc01b82d4acEmmanuele Bassi * 716db8642a56c0436aeb730ead593140bc01b82d4acEmmanuele Bassi * Return value: a #GList containing all the keys inside the hash 717db8642a56c0436aeb730ead593140bc01b82d4acEmmanuele Bassi * table. The content of the list is owned by the hash table and 718db8642a56c0436aeb730ead593140bc01b82d4acEmmanuele Bassi * should not be modified or freed. Use g_list_free() when done 719db8642a56c0436aeb730ead593140bc01b82d4acEmmanuele Bassi * using the list. 720db8642a56c0436aeb730ead593140bc01b82d4acEmmanuele Bassi * 721db8642a56c0436aeb730ead593140bc01b82d4acEmmanuele Bassi * Since: 2.14 722db8642a56c0436aeb730ead593140bc01b82d4acEmmanuele Bassi */ 723db8642a56c0436aeb730ead593140bc01b82d4acEmmanuele BassiGList * 724db8642a56c0436aeb730ead593140bc01b82d4acEmmanuele Bassig_hash_table_get_keys (GHashTable *hash_table) 725db8642a56c0436aeb730ead593140bc01b82d4acEmmanuele Bassi{ 726db8642a56c0436aeb730ead593140bc01b82d4acEmmanuele Bassi GHashNode *node; 727db8642a56c0436aeb730ead593140bc01b82d4acEmmanuele Bassi gint i; 728db8642a56c0436aeb730ead593140bc01b82d4acEmmanuele Bassi GList *retval; 729db8642a56c0436aeb730ead593140bc01b82d4acEmmanuele Bassi 730db8642a56c0436aeb730ead593140bc01b82d4acEmmanuele Bassi g_return_val_if_fail (hash_table != NULL, NULL); 731db8642a56c0436aeb730ead593140bc01b82d4acEmmanuele Bassi 732db8642a56c0436aeb730ead593140bc01b82d4acEmmanuele Bassi retval = NULL; 733db8642a56c0436aeb730ead593140bc01b82d4acEmmanuele Bassi for (i = 0; i < hash_table->size; i++) 734db8642a56c0436aeb730ead593140bc01b82d4acEmmanuele Bassi for (node = hash_table->nodes[i]; node; node = node->next) 735db8642a56c0436aeb730ead593140bc01b82d4acEmmanuele Bassi retval = g_list_prepend (retval, node->key); 736db8642a56c0436aeb730ead593140bc01b82d4acEmmanuele Bassi 737db8642a56c0436aeb730ead593140bc01b82d4acEmmanuele Bassi return retval; 738db8642a56c0436aeb730ead593140bc01b82d4acEmmanuele Bassi} 739db8642a56c0436aeb730ead593140bc01b82d4acEmmanuele Bassi 740db8642a56c0436aeb730ead593140bc01b82d4acEmmanuele Bassi/** 741db8642a56c0436aeb730ead593140bc01b82d4acEmmanuele Bassi * g_hash_table_get_values: 742db8642a56c0436aeb730ead593140bc01b82d4acEmmanuele Bassi * @hash_table: a #GHashTable 743db8642a56c0436aeb730ead593140bc01b82d4acEmmanuele Bassi * 744db8642a56c0436aeb730ead593140bc01b82d4acEmmanuele Bassi * Retrieves every value inside @hash_table. The returned data is 745db8642a56c0436aeb730ead593140bc01b82d4acEmmanuele Bassi * valid until @hash_table is modified. 746db8642a56c0436aeb730ead593140bc01b82d4acEmmanuele Bassi * 747db8642a56c0436aeb730ead593140bc01b82d4acEmmanuele Bassi * Return value: a #GList containing all the values inside the hash 748db8642a56c0436aeb730ead593140bc01b82d4acEmmanuele Bassi * table. The content of the list is owned by the hash table and 749db8642a56c0436aeb730ead593140bc01b82d4acEmmanuele Bassi * should not be modified or freed. Use g_list_free() when done 750db8642a56c0436aeb730ead593140bc01b82d4acEmmanuele Bassi * using the list. 751db8642a56c0436aeb730ead593140bc01b82d4acEmmanuele Bassi * 752db8642a56c0436aeb730ead593140bc01b82d4acEmmanuele Bassi * Since: 2.14 753db8642a56c0436aeb730ead593140bc01b82d4acEmmanuele Bassi */ 754db8642a56c0436aeb730ead593140bc01b82d4acEmmanuele BassiGList * 755db8642a56c0436aeb730ead593140bc01b82d4acEmmanuele Bassig_hash_table_get_values (GHashTable *hash_table) 756db8642a56c0436aeb730ead593140bc01b82d4acEmmanuele Bassi{ 757db8642a56c0436aeb730ead593140bc01b82d4acEmmanuele Bassi GHashNode *node; 758db8642a56c0436aeb730ead593140bc01b82d4acEmmanuele Bassi gint i; 759db8642a56c0436aeb730ead593140bc01b82d4acEmmanuele Bassi GList *retval; 760db8642a56c0436aeb730ead593140bc01b82d4acEmmanuele Bassi 761db8642a56c0436aeb730ead593140bc01b82d4acEmmanuele Bassi g_return_val_if_fail (hash_table != NULL, NULL); 762db8642a56c0436aeb730ead593140bc01b82d4acEmmanuele Bassi 763db8642a56c0436aeb730ead593140bc01b82d4acEmmanuele Bassi retval = NULL; 764db8642a56c0436aeb730ead593140bc01b82d4acEmmanuele Bassi for (i = 0; i < hash_table->size; i++) 765db8642a56c0436aeb730ead593140bc01b82d4acEmmanuele Bassi for (node = hash_table->nodes[i]; node; node = node->next) 766db8642a56c0436aeb730ead593140bc01b82d4acEmmanuele Bassi retval = g_list_prepend (retval, node->value); 767db8642a56c0436aeb730ead593140bc01b82d4acEmmanuele Bassi 768db8642a56c0436aeb730ead593140bc01b82d4acEmmanuele Bassi return retval; 769db8642a56c0436aeb730ead593140bc01b82d4acEmmanuele Bassi} 770db8642a56c0436aeb730ead593140bc01b82d4acEmmanuele Bassi 7712e0320d57e417f7d1c838d729a99545db2228e9Owen Taylorstatic void 7722e0320d57e417f7d1c838d729a99545db2228e9Owen Taylorg_hash_table_resize (GHashTable *hash_table) 7732e0320d57e417f7d1c838d729a99545db2228e9Owen Taylor{ 7742e0320d57e417f7d1c838d729a99545db2228e9Owen Taylor GHashNode **new_nodes; 7752e0320d57e417f7d1c838d729a99545db2228e9Owen Taylor GHashNode *node; 7762e0320d57e417f7d1c838d729a99545db2228e9Owen Taylor GHashNode *next; 7772e0320d57e417f7d1c838d729a99545db2228e9Owen Taylor guint hash_val; 7782e0320d57e417f7d1c838d729a99545db2228e9Owen Taylor gint new_size; 7792e0320d57e417f7d1c838d729a99545db2228e9Owen Taylor gint i; 7808079eb3456914a03618b92b48f75a71b25331acbOwen Taylor 78173e6da92b298d48e3de9d775b5adc97cbff7b0aaSven Neumann new_size = g_spaced_primes_closest (hash_table->nnodes); 78273e6da92b298d48e3de9d775b5adc97cbff7b0aaSven Neumann new_size = CLAMP (new_size, HASH_TABLE_MIN_SIZE, HASH_TABLE_MAX_SIZE); 78373e6da92b298d48e3de9d775b5adc97cbff7b0aaSven Neumann 784448e792b0a9b092f9593eaa51e16acd8abe54c76Jeff Garzik new_nodes = g_new0 (GHashNode*, new_size); 7852d68cbbb7d37d3f265bf1087e6ddedcc58bc62beTim Janik 7867519c2338ae484135b44bbb7eb49719aea8c4ca3Lauri Alanko for (i = 0; i < hash_table->size; i++) 7877519c2338ae484135b44bbb7eb49719aea8c4ca3Lauri Alanko for (node = hash_table->nodes[i]; node; node = next) 7887519c2338ae484135b44bbb7eb49719aea8c4ca3Lauri Alanko { 7897519c2338ae484135b44bbb7eb49719aea8c4ca3Lauri Alanko next = node->next; 790448e792b0a9b092f9593eaa51e16acd8abe54c76Jeff Garzik 791e6b78c9af1d6416f93311b98e1e6d802e2fe0617Ryan Lortie hash_val = node->key_hash % new_size; 792448e792b0a9b092f9593eaa51e16acd8abe54c76Jeff Garzik 7937519c2338ae484135b44bbb7eb49719aea8c4ca3Lauri Alanko node->next = new_nodes[hash_val]; 7947519c2338ae484135b44bbb7eb49719aea8c4ca3Lauri Alanko new_nodes[hash_val] = node; 7957519c2338ae484135b44bbb7eb49719aea8c4ca3Lauri Alanko } 7962d68cbbb7d37d3f265bf1087e6ddedcc58bc62beTim Janik 7977519c2338ae484135b44bbb7eb49719aea8c4ca3Lauri Alanko g_free (hash_table->nodes); 7987519c2338ae484135b44bbb7eb49719aea8c4ca3Lauri Alanko hash_table->nodes = new_nodes; 7997519c2338ae484135b44bbb7eb49719aea8c4ca3Lauri Alanko hash_table->size = new_size; 8007519c2338ae484135b44bbb7eb49719aea8c4ca3Lauri Alanko} 8017519c2338ae484135b44bbb7eb49719aea8c4ca3Lauri Alanko 8022e0320d57e417f7d1c838d729a99545db2228e9Owen Taylorstatic GHashNode* 8032e0320d57e417f7d1c838d729a99545db2228e9Owen Taylorg_hash_node_new (gpointer key, 804e6b78c9af1d6416f93311b98e1e6d802e2fe0617Ryan Lortie gpointer value, 805e6b78c9af1d6416f93311b98e1e6d802e2fe0617Ryan Lortie guint key_hash) 8062e0320d57e417f7d1c838d729a99545db2228e9Owen Taylor{ 8070cba1b531d5d28890fa4f48359d4e7adacf2a603Tim Janik GHashNode *hash_node = g_slice_new (GHashNode); 8082d68cbbb7d37d3f265bf1087e6ddedcc58bc62beTim Janik 8092e0320d57e417f7d1c838d729a99545db2228e9Owen Taylor hash_node->key = key; 8102e0320d57e417f7d1c838d729a99545db2228e9Owen Taylor hash_node->value = value; 811e6b78c9af1d6416f93311b98e1e6d802e2fe0617Ryan Lortie hash_node->key_hash = key_hash; 8122e0320d57e417f7d1c838d729a99545db2228e9Owen Taylor hash_node->next = NULL; 8132d68cbbb7d37d3f265bf1087e6ddedcc58bc62beTim Janik 8142e0320d57e417f7d1c838d729a99545db2228e9Owen Taylor return hash_node; 8152e0320d57e417f7d1c838d729a99545db2228e9Owen Taylor} 8162e0320d57e417f7d1c838d729a99545db2228e9Owen Taylor 8172e0320d57e417f7d1c838d729a99545db2228e9Owen Taylorstatic void 818a2b269bae3315a2ea772b741fb62f683c1db5770Sven Neumanng_hash_node_destroy (GHashNode *hash_node, 819a2b269bae3315a2ea772b741fb62f683c1db5770Sven Neumann GDestroyNotify key_destroy_func, 820a2b269bae3315a2ea772b741fb62f683c1db5770Sven Neumann GDestroyNotify value_destroy_func) 8212e0320d57e417f7d1c838d729a99545db2228e9Owen Taylor{ 822a2b269bae3315a2ea772b741fb62f683c1db5770Sven Neumann if (key_destroy_func) 823a2b269bae3315a2ea772b741fb62f683c1db5770Sven Neumann key_destroy_func (hash_node->key); 824a2b269bae3315a2ea772b741fb62f683c1db5770Sven Neumann if (value_destroy_func) 825a2b269bae3315a2ea772b741fb62f683c1db5770Sven Neumann value_destroy_func (hash_node->value); 8260cba1b531d5d28890fa4f48359d4e7adacf2a603Tim Janik g_slice_free (GHashNode, hash_node); 8272e0320d57e417f7d1c838d729a99545db2228e9Owen Taylor} 8282e0320d57e417f7d1c838d729a99545db2228e9Owen Taylor 8292e0320d57e417f7d1c838d729a99545db2228e9Owen Taylorstatic void 830a2b269bae3315a2ea772b741fb62f683c1db5770Sven Neumanng_hash_nodes_destroy (GHashNode *hash_node, 831a2b269bae3315a2ea772b741fb62f683c1db5770Sven Neumann GFreeFunc key_destroy_func, 832a2b269bae3315a2ea772b741fb62f683c1db5770Sven Neumann GFreeFunc value_destroy_func) 8332e0320d57e417f7d1c838d729a99545db2228e9Owen Taylor{ 834a436817718f7d4436c3ed1da4022f062dcb81c54Owen Taylor while (hash_node) 835a436817718f7d4436c3ed1da4022f062dcb81c54Owen Taylor { 836a436817718f7d4436c3ed1da4022f062dcb81c54Owen Taylor GHashNode *next = hash_node->next; 837a436817718f7d4436c3ed1da4022f062dcb81c54Owen Taylor if (key_destroy_func) 838a436817718f7d4436c3ed1da4022f062dcb81c54Owen Taylor key_destroy_func (hash_node->key); 839a436817718f7d4436c3ed1da4022f062dcb81c54Owen Taylor if (value_destroy_func) 840a436817718f7d4436c3ed1da4022f062dcb81c54Owen Taylor value_destroy_func (hash_node->value); 8410cba1b531d5d28890fa4f48359d4e7adacf2a603Tim Janik g_slice_free (GHashNode, hash_node); 842a436817718f7d4436c3ed1da4022f062dcb81c54Owen Taylor hash_node = next; 843448e792b0a9b092f9593eaa51e16acd8abe54c76Jeff Garzik } 844df9a49ec3cbb19e58be929548cfba12452c55d83Josh MacDonald} 845608a31b98e1420f487190871ee7312db2643d93dMatthias Clasen 8463e847a090cfd8495add631d43388c461b1a85716Tim Janik 847608a31b98e1420f487190871ee7312db2643d93dMatthias Clasen#define __G_HASH_C__ 848608a31b98e1420f487190871ee7312db2643d93dMatthias Clasen#include "galiasdef.c" 849