ghash.c revision 00c2db4e4b992a4fa667d49289c55b9d5f3fcf04
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 118eed88b24e86f16021d94d9b16f7a2bc895d9239Ryan Lortie * 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 248eed88b24e86f16021d94d9b16f7a2bc895d9239Ryan Lortie * GLib at ftp://ftp.gtk.org/pub/gtk/. 25b9ef2b41db975061960e2217220668c2a5d563daCST */ 26b9ef2b41db975061960e2217220668c2a5d563daCST 278eed88b24e86f16021d94d9b16f7a2bc895d9239Ryan Lortie/* 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 63a2b269bae3315a2ea772b741fb62f683c1db5770Sven Neumannstatic void g_hash_table_resize (GHashTable *hash_table); 64a2b269bae3315a2ea772b741fb62f683c1db5770Sven Neumannstatic GHashNode** g_hash_table_lookup_node (GHashTable *hash_table, 65e6b78c9af1d6416f93311b98e1e6d802e2fe0617Ryan Lortie gconstpointer key, 66e6b78c9af1d6416f93311b98e1e6d802e2fe0617Ryan Lortie guint *hash_return); 67a2b269bae3315a2ea772b741fb62f683c1db5770Sven Neumannstatic GHashNode* g_hash_node_new (gpointer key, 68e6b78c9af1d6416f93311b98e1e6d802e2fe0617Ryan Lortie gpointer value, 69e6b78c9af1d6416f93311b98e1e6d802e2fe0617Ryan Lortie guint key_hash); 70a2b269bae3315a2ea772b741fb62f683c1db5770Sven Neumannstatic guint g_hash_table_foreach_remove_or_steal (GHashTable *hash_table, 71a2b269bae3315a2ea772b741fb62f683c1db5770Sven Neumann GHRFunc func, 72a2b269bae3315a2ea772b741fb62f683c1db5770Sven Neumann gpointer user_data, 73a2b269bae3315a2ea772b741fb62f683c1db5770Sven Neumann gboolean notify); 7472ed8191afd8ff124a45285b420625e1342e35cfRyan Lortiestatic void g_hash_table_remove_all_nodes (GHashTable *hash_table, 7572ed8191afd8ff124a45285b420625e1342e35cfRyan Lortie gboolean notify); 762e0320d57e417f7d1c838d729a99545db2228e9Owen Taylor 7700c2db4e4b992a4fa667d49289c55b9d5f3fcf04Ryan Lortiestatic inline void 7800c2db4e4b992a4fa667d49289c55b9d5f3fcf04Ryan Lortieg_hash_table_maybe_resize (GHashTable *hash_table) 7900c2db4e4b992a4fa667d49289c55b9d5f3fcf04Ryan Lortie{ 8000c2db4e4b992a4fa667d49289c55b9d5f3fcf04Ryan Lortie gint nnodes = hash_table->nnodes; 8100c2db4e4b992a4fa667d49289c55b9d5f3fcf04Ryan Lortie gint size = hash_table->size; 8200c2db4e4b992a4fa667d49289c55b9d5f3fcf04Ryan Lortie 8300c2db4e4b992a4fa667d49289c55b9d5f3fcf04Ryan Lortie if ((size >= 3 * nnodes && size > HASH_TABLE_MIN_SIZE) || 8400c2db4e4b992a4fa667d49289c55b9d5f3fcf04Ryan Lortie (3 * size <= nnodes && size < HASH_TABLE_MAX_SIZE)) 8500c2db4e4b992a4fa667d49289c55b9d5f3fcf04Ryan Lortie g_hash_table_resize (hash_table); 8600c2db4e4b992a4fa667d49289c55b9d5f3fcf04Ryan Lortie} 872e0320d57e417f7d1c838d729a99545db2228e9Owen Taylor 88a2b269bae3315a2ea772b741fb62f683c1db5770Sven Neumann/** 89a2b269bae3315a2ea772b741fb62f683c1db5770Sven Neumann * g_hash_table_new: 90a2b269bae3315a2ea772b741fb62f683c1db5770Sven Neumann * @hash_func: a function to create a hash value from a key. 91a2b269bae3315a2ea772b741fb62f683c1db5770Sven Neumann * Hash values are used to determine where keys are stored within the 928eed88b24e86f16021d94d9b16f7a2bc895d9239Ryan Lortie * #GHashTable data structure. The g_direct_hash(), g_int_hash() and 938eed88b24e86f16021d94d9b16f7a2bc895d9239Ryan Lortie * g_str_hash() functions are provided for some common types of keys. 94a52e2986cd4a2147cfc8d41ae23d98907caaf3a0Matthias Clasen * If hash_func is %NULL, g_direct_hash() is used. 95a2b269bae3315a2ea772b741fb62f683c1db5770Sven Neumann * @key_equal_func: a function to check two keys for equality. This is 96a2b269bae3315a2ea772b741fb62f683c1db5770Sven Neumann * used when looking up keys in the #GHashTable. The g_direct_equal(), 97a2b269bae3315a2ea772b741fb62f683c1db5770Sven Neumann * g_int_equal() and g_str_equal() functions are provided for the most 98a52e2986cd4a2147cfc8d41ae23d98907caaf3a0Matthias Clasen * common types of keys. If @key_equal_func is %NULL, keys are compared 99a2b269bae3315a2ea772b741fb62f683c1db5770Sven Neumann * directly in a similar fashion to g_direct_equal(), but without the 100a2b269bae3315a2ea772b741fb62f683c1db5770Sven Neumann * overhead of a function call. 101a2b269bae3315a2ea772b741fb62f683c1db5770Sven Neumann * 1023e847a090cfd8495add631d43388c461b1a85716Tim Janik * Creates a new #GHashTable with a reference count of 1. 1038eed88b24e86f16021d94d9b16f7a2bc895d9239Ryan Lortie * 104a2b269bae3315a2ea772b741fb62f683c1db5770Sven Neumann * Return value: a new #GHashTable. 105a2b269bae3315a2ea772b741fb62f683c1db5770Sven Neumann **/ 1062e0320d57e417f7d1c838d729a99545db2228e9Owen TaylorGHashTable* 1072e0320d57e417f7d1c838d729a99545db2228e9Owen Taylorg_hash_table_new (GHashFunc hash_func, 1088eed88b24e86f16021d94d9b16f7a2bc895d9239Ryan Lortie GEqualFunc key_equal_func) 1092e0320d57e417f7d1c838d729a99545db2228e9Owen Taylor{ 110a2b269bae3315a2ea772b741fb62f683c1db5770Sven Neumann return g_hash_table_new_full (hash_func, key_equal_func, NULL, NULL); 111a2b269bae3315a2ea772b741fb62f683c1db5770Sven Neumann} 112a2b269bae3315a2ea772b741fb62f683c1db5770Sven Neumann 113a2b269bae3315a2ea772b741fb62f683c1db5770Sven Neumann 114a2b269bae3315a2ea772b741fb62f683c1db5770Sven Neumann/** 115a2b269bae3315a2ea772b741fb62f683c1db5770Sven Neumann * g_hash_table_new_full: 116a2b269bae3315a2ea772b741fb62f683c1db5770Sven Neumann * @hash_func: a function to create a hash value from a key. 117a2b269bae3315a2ea772b741fb62f683c1db5770Sven Neumann * @key_equal_func: a function to check two keys for equality. 1188eed88b24e86f16021d94d9b16f7a2bc895d9239Ryan Lortie * @key_destroy_func: a function to free the memory allocated for the key 1198eed88b24e86f16021d94d9b16f7a2bc895d9239Ryan Lortie * used when removing the entry from the #GHashTable or %NULL if you 120d18b364dd774087555f036fec2c6ec9fe838368fSven Neumann * don't want to supply such a function. 1218eed88b24e86f16021d94d9b16f7a2bc895d9239Ryan Lortie * @value_destroy_func: a function to free the memory allocated for the 1228eed88b24e86f16021d94d9b16f7a2bc895d9239Ryan Lortie * value used when removing the entry from the #GHashTable or %NULL if 123a2b269bae3315a2ea772b741fb62f683c1db5770Sven Neumann * you don't want to supply such a function. 1248eed88b24e86f16021d94d9b16f7a2bc895d9239Ryan Lortie * 1253e847a090cfd8495add631d43388c461b1a85716Tim Janik * Creates a new #GHashTable like g_hash_table_new() with a reference count 1263e847a090cfd8495add631d43388c461b1a85716Tim Janik * of 1 and allows to specify functions to free the memory allocated for the 1273e847a090cfd8495add631d43388c461b1a85716Tim Janik * key and value that get called when removing the entry from the #GHashTable. 1288eed88b24e86f16021d94d9b16f7a2bc895d9239Ryan Lortie * 129a2b269bae3315a2ea772b741fb62f683c1db5770Sven Neumann * Return value: a new #GHashTable. 130a2b269bae3315a2ea772b741fb62f683c1db5770Sven Neumann **/ 131a2b269bae3315a2ea772b741fb62f683c1db5770Sven NeumannGHashTable* 132a2b269bae3315a2ea772b741fb62f683c1db5770Sven Neumanng_hash_table_new_full (GHashFunc hash_func, 1338eed88b24e86f16021d94d9b16f7a2bc895d9239Ryan Lortie GEqualFunc key_equal_func, 1348eed88b24e86f16021d94d9b16f7a2bc895d9239Ryan Lortie GDestroyNotify key_destroy_func, 1358eed88b24e86f16021d94d9b16f7a2bc895d9239Ryan Lortie GDestroyNotify value_destroy_func) 136a2b269bae3315a2ea772b741fb62f683c1db5770Sven Neumann{ 1377519c2338ae484135b44bbb7eb49719aea8c4ca3Lauri Alanko GHashTable *hash_table; 1388eed88b24e86f16021d94d9b16f7a2bc895d9239Ryan Lortie 1390cba1b531d5d28890fa4f48359d4e7adacf2a603Tim Janik hash_table = g_slice_new (GHashTable); 140a2b269bae3315a2ea772b741fb62f683c1db5770Sven Neumann hash_table->size = HASH_TABLE_MIN_SIZE; 141a2b269bae3315a2ea772b741fb62f683c1db5770Sven Neumann hash_table->nnodes = 0; 142a2b269bae3315a2ea772b741fb62f683c1db5770Sven Neumann hash_table->hash_func = hash_func ? hash_func : g_direct_hash; 143a2b269bae3315a2ea772b741fb62f683c1db5770Sven Neumann hash_table->key_equal_func = key_equal_func; 1443e847a090cfd8495add631d43388c461b1a85716Tim Janik hash_table->ref_count = 1; 145a2b269bae3315a2ea772b741fb62f683c1db5770Sven Neumann hash_table->key_destroy_func = key_destroy_func; 146a2b269bae3315a2ea772b741fb62f683c1db5770Sven Neumann hash_table->value_destroy_func = value_destroy_func; 1473e847a090cfd8495add631d43388c461b1a85716Tim Janik hash_table->nodes = g_new0 (GHashNode*, hash_table->size); 1488eed88b24e86f16021d94d9b16f7a2bc895d9239Ryan Lortie 1497519c2338ae484135b44bbb7eb49719aea8c4ca3Lauri Alanko return hash_table; 1502e0320d57e417f7d1c838d729a99545db2228e9Owen Taylor} 1512e0320d57e417f7d1c838d729a99545db2228e9Owen Taylor 1523e847a090cfd8495add631d43388c461b1a85716Tim Janik 1533e847a090cfd8495add631d43388c461b1a85716Tim Janik/** 1543e847a090cfd8495add631d43388c461b1a85716Tim Janik * g_hash_table_ref: 1553e847a090cfd8495add631d43388c461b1a85716Tim Janik * @hash_table: a valid #GHashTable. 1568eed88b24e86f16021d94d9b16f7a2bc895d9239Ryan Lortie * 1573e847a090cfd8495add631d43388c461b1a85716Tim Janik * Atomically increments the reference count of @hash_table by one. 1583e847a090cfd8495add631d43388c461b1a85716Tim Janik * This function is MT-safe and may be called from any thread. 1598eed88b24e86f16021d94d9b16f7a2bc895d9239Ryan Lortie * 1603e847a090cfd8495add631d43388c461b1a85716Tim Janik * Return value: the passed in #GHashTable. 1618eed88b24e86f16021d94d9b16f7a2bc895d9239Ryan Lortie * 162fe749cbd3b058512e36d79203cac3c00c7f40571Matthias Clasen * Since: 2.10 1633e847a090cfd8495add631d43388c461b1a85716Tim Janik **/ 1643e847a090cfd8495add631d43388c461b1a85716Tim JanikGHashTable* 1653e847a090cfd8495add631d43388c461b1a85716Tim Janikg_hash_table_ref (GHashTable *hash_table) 1663e847a090cfd8495add631d43388c461b1a85716Tim Janik{ 1673e847a090cfd8495add631d43388c461b1a85716Tim Janik g_return_val_if_fail (hash_table != NULL, NULL); 1683e847a090cfd8495add631d43388c461b1a85716Tim Janik g_return_val_if_fail (hash_table->ref_count > 0, hash_table); 1693e847a090cfd8495add631d43388c461b1a85716Tim Janik 1703e847a090cfd8495add631d43388c461b1a85716Tim Janik g_atomic_int_add (&hash_table->ref_count, 1); 1713e847a090cfd8495add631d43388c461b1a85716Tim Janik return hash_table; 1723e847a090cfd8495add631d43388c461b1a85716Tim Janik} 1733e847a090cfd8495add631d43388c461b1a85716Tim Janik 1743e847a090cfd8495add631d43388c461b1a85716Tim Janik/** 1753e847a090cfd8495add631d43388c461b1a85716Tim Janik * g_hash_table_unref: 1763e847a090cfd8495add631d43388c461b1a85716Tim Janik * @hash_table: a valid #GHashTable. 1778eed88b24e86f16021d94d9b16f7a2bc895d9239Ryan Lortie * 1783e847a090cfd8495add631d43388c461b1a85716Tim Janik * Atomically decrements the reference count of @hash_table by one. 1793e847a090cfd8495add631d43388c461b1a85716Tim Janik * If the reference count drops to 0, all keys and values will be 1803e847a090cfd8495add631d43388c461b1a85716Tim Janik * destroyed, and all memory allocated by the hash table is released. 1813e847a090cfd8495add631d43388c461b1a85716Tim Janik * This function is MT-safe and may be called from any thread. 1828eed88b24e86f16021d94d9b16f7a2bc895d9239Ryan Lortie * 183fe749cbd3b058512e36d79203cac3c00c7f40571Matthias Clasen * Since: 2.10 1843e847a090cfd8495add631d43388c461b1a85716Tim Janik **/ 1853e847a090cfd8495add631d43388c461b1a85716Tim Janikvoid 1863e847a090cfd8495add631d43388c461b1a85716Tim Janikg_hash_table_unref (GHashTable *hash_table) 1873e847a090cfd8495add631d43388c461b1a85716Tim Janik{ 1883e847a090cfd8495add631d43388c461b1a85716Tim Janik g_return_if_fail (hash_table != NULL); 1893e847a090cfd8495add631d43388c461b1a85716Tim Janik g_return_if_fail (hash_table->ref_count > 0); 1903e847a090cfd8495add631d43388c461b1a85716Tim Janik 1913e847a090cfd8495add631d43388c461b1a85716Tim Janik if (g_atomic_int_exchange_and_add (&hash_table->ref_count, -1) - 1 == 0) 1923e847a090cfd8495add631d43388c461b1a85716Tim Janik { 19372ed8191afd8ff124a45285b420625e1342e35cfRyan Lortie g_hash_table_remove_all_nodes (hash_table, FALSE); 1943e847a090cfd8495add631d43388c461b1a85716Tim Janik g_free (hash_table->nodes); 1953e847a090cfd8495add631d43388c461b1a85716Tim Janik g_slice_free (GHashTable, hash_table); 1963e847a090cfd8495add631d43388c461b1a85716Tim Janik } 1973e847a090cfd8495add631d43388c461b1a85716Tim Janik} 1983e847a090cfd8495add631d43388c461b1a85716Tim Janik 199a2b269bae3315a2ea772b741fb62f683c1db5770Sven Neumann/** 200a2b269bae3315a2ea772b741fb62f683c1db5770Sven Neumann * g_hash_table_destroy: 201a2b269bae3315a2ea772b741fb62f683c1db5770Sven Neumann * @hash_table: a #GHashTable. 2028eed88b24e86f16021d94d9b16f7a2bc895d9239Ryan Lortie * 20324dec3cd490fa4dc057a0186c6b870160022268eMorten Welinder * Destroys all keys and values in the #GHashTable and decrements its 2043e847a090cfd8495add631d43388c461b1a85716Tim Janik * reference count by 1. If keys and/or values are dynamically allocated, 2053e847a090cfd8495add631d43388c461b1a85716Tim Janik * you should either free them first or create the #GHashTable with destroy 2063e847a090cfd8495add631d43388c461b1a85716Tim Janik * notifiers using g_hash_table_new_full(). In the latter case the destroy 2073e847a090cfd8495add631d43388c461b1a85716Tim Janik * functions you supplied will be called on all keys and values during the 2083e847a090cfd8495add631d43388c461b1a85716Tim Janik * destruction phase. 209a2b269bae3315a2ea772b741fb62f683c1db5770Sven Neumann **/ 2102e0320d57e417f7d1c838d729a99545db2228e9Owen Taylorvoid 2112e0320d57e417f7d1c838d729a99545db2228e9Owen Taylorg_hash_table_destroy (GHashTable *hash_table) 2122e0320d57e417f7d1c838d729a99545db2228e9Owen Taylor{ 2132d68cbbb7d37d3f265bf1087e6ddedcc58bc62beTim Janik g_return_if_fail (hash_table != NULL); 2143e847a090cfd8495add631d43388c461b1a85716Tim Janik g_return_if_fail (hash_table->ref_count > 0); 2158eed88b24e86f16021d94d9b16f7a2bc895d9239Ryan Lortie 216a5b4b8bfb18838454d99bdee60294da07e5ef0d2Matthias Clasen g_hash_table_remove_all (hash_table); 2173e847a090cfd8495add631d43388c461b1a85716Tim Janik g_hash_table_unref (hash_table); 2182e0320d57e417f7d1c838d729a99545db2228e9Owen Taylor} 2192e0320d57e417f7d1c838d729a99545db2228e9Owen Taylor 220d5492a983cfa048658af8b03f833ddb3c0cf355eESTstatic inline GHashNode** 2218eed88b24e86f16021d94d9b16f7a2bc895d9239Ryan Lortieg_hash_table_lookup_node (GHashTable *hash_table, 2228eed88b24e86f16021d94d9b16f7a2bc895d9239Ryan Lortie gconstpointer key, 2238eed88b24e86f16021d94d9b16f7a2bc895d9239Ryan Lortie guint *hash_return) 2242e0320d57e417f7d1c838d729a99545db2228e9Owen Taylor{ 225d5492a983cfa048658af8b03f833ddb3c0cf355eEST GHashNode **node; 226e6b78c9af1d6416f93311b98e1e6d802e2fe0617Ryan Lortie guint hash_value; 227e6b78c9af1d6416f93311b98e1e6d802e2fe0617Ryan Lortie 228e6b78c9af1d6416f93311b98e1e6d802e2fe0617Ryan Lortie hash_value = (* hash_table->hash_func) (key); 229e6b78c9af1d6416f93311b98e1e6d802e2fe0617Ryan Lortie node = &hash_table->nodes[hash_value % hash_table->size]; 2308eed88b24e86f16021d94d9b16f7a2bc895d9239Ryan Lortie 231e6b78c9af1d6416f93311b98e1e6d802e2fe0617Ryan Lortie if (hash_return) 232e6b78c9af1d6416f93311b98e1e6d802e2fe0617Ryan Lortie *hash_return = hash_value; 2338eed88b24e86f16021d94d9b16f7a2bc895d9239Ryan Lortie 2342d68cbbb7d37d3f265bf1087e6ddedcc58bc62beTim Janik /* Hash table lookup needs to be fast. 2352d68cbbb7d37d3f265bf1087e6ddedcc58bc62beTim Janik * We therefore remove the extra conditional of testing 236267b6813703e24ef60d0e8ba42557c414f9dd52eSebastian Wilhelmi * whether to call the key_equal_func or not from 2372d68cbbb7d37d3f265bf1087e6ddedcc58bc62beTim Janik * the inner loop. 238e6b78c9af1d6416f93311b98e1e6d802e2fe0617Ryan Lortie * 239e6b78c9af1d6416f93311b98e1e6d802e2fe0617Ryan Lortie * Additional optimisation: first check if our full hash 240e6b78c9af1d6416f93311b98e1e6d802e2fe0617Ryan Lortie * values are equal so we can avoid calling the full-blown 241e6b78c9af1d6416f93311b98e1e6d802e2fe0617Ryan Lortie * key equality function in most cases. 2422d68cbbb7d37d3f265bf1087e6ddedcc58bc62beTim Janik */ 243267b6813703e24ef60d0e8ba42557c414f9dd52eSebastian Wilhelmi if (hash_table->key_equal_func) 244e6b78c9af1d6416f93311b98e1e6d802e2fe0617Ryan Lortie while (*node && (((*node)->key_hash != hash_value) || 245e6b78c9af1d6416f93311b98e1e6d802e2fe0617Ryan Lortie !(*hash_table->key_equal_func) ((*node)->key, key))) 246d5492a983cfa048658af8b03f833ddb3c0cf355eEST node = &(*node)->next; 2472d68cbbb7d37d3f265bf1087e6ddedcc58bc62beTim Janik else 248d5492a983cfa048658af8b03f833ddb3c0cf355eEST while (*node && (*node)->key != key) 249d5492a983cfa048658af8b03f833ddb3c0cf355eEST node = &(*node)->next; 250e6b78c9af1d6416f93311b98e1e6d802e2fe0617Ryan Lortie 2512d68cbbb7d37d3f265bf1087e6ddedcc58bc62beTim Janik return node; 2522d68cbbb7d37d3f265bf1087e6ddedcc58bc62beTim Janik} 2532e0320d57e417f7d1c838d729a99545db2228e9Owen Taylor 254a2b269bae3315a2ea772b741fb62f683c1db5770Sven Neumann/** 255a2b269bae3315a2ea772b741fb62f683c1db5770Sven Neumann * g_hash_table_lookup: 256a2b269bae3315a2ea772b741fb62f683c1db5770Sven Neumann * @hash_table: a #GHashTable. 257a2b269bae3315a2ea772b741fb62f683c1db5770Sven Neumann * @key: the key to look up. 2588eed88b24e86f16021d94d9b16f7a2bc895d9239Ryan Lortie * 259fd92ac8f5280ccb936a534a14f5c9cbdb24302e5Matthias Clasen * Looks up a key in a #GHashTable. Note that this function cannot 260fd92ac8f5280ccb936a534a14f5c9cbdb24302e5Matthias Clasen * distinguish between a key that is not present and one which is present 261fd92ac8f5280ccb936a534a14f5c9cbdb24302e5Matthias Clasen * and has the value %NULL. If you need this distinction, use 262fd92ac8f5280ccb936a534a14f5c9cbdb24302e5Matthias Clasen * g_hash_table_lookup_extended(). 2638eed88b24e86f16021d94d9b16f7a2bc895d9239Ryan Lortie * 264a52e2986cd4a2147cfc8d41ae23d98907caaf3a0Matthias Clasen * Return value: the associated value, or %NULL if the key is not found. 265a2b269bae3315a2ea772b741fb62f683c1db5770Sven Neumann **/ 2662d68cbbb7d37d3f265bf1087e6ddedcc58bc62beTim Janikgpointer 2678eed88b24e86f16021d94d9b16f7a2bc895d9239Ryan Lortieg_hash_table_lookup (GHashTable *hash_table, 2688eed88b24e86f16021d94d9b16f7a2bc895d9239Ryan Lortie gconstpointer key) 2692d68cbbb7d37d3f265bf1087e6ddedcc58bc62beTim Janik{ 2702d68cbbb7d37d3f265bf1087e6ddedcc58bc62beTim Janik GHashNode *node; 2718eed88b24e86f16021d94d9b16f7a2bc895d9239Ryan Lortie 2722d68cbbb7d37d3f265bf1087e6ddedcc58bc62beTim Janik g_return_val_if_fail (hash_table != NULL, NULL); 2738eed88b24e86f16021d94d9b16f7a2bc895d9239Ryan Lortie 274e6b78c9af1d6416f93311b98e1e6d802e2fe0617Ryan Lortie node = *g_hash_table_lookup_node (hash_table, key, NULL); 2758eed88b24e86f16021d94d9b16f7a2bc895d9239Ryan Lortie 2762d68cbbb7d37d3f265bf1087e6ddedcc58bc62beTim Janik return node ? node->value : NULL; 2772d68cbbb7d37d3f265bf1087e6ddedcc58bc62beTim Janik} 2787401460a60504dad7b77219d0ba3d93112e12444Manish Singh 279a2b269bae3315a2ea772b741fb62f683c1db5770Sven Neumann/** 280a2b269bae3315a2ea772b741fb62f683c1db5770Sven Neumann * g_hash_table_lookup_extended: 281a2b269bae3315a2ea772b741fb62f683c1db5770Sven Neumann * @hash_table: a #GHashTable. 282a2b269bae3315a2ea772b741fb62f683c1db5770Sven Neumann * @lookup_key: the key to look up. 283a2b269bae3315a2ea772b741fb62f683c1db5770Sven Neumann * @orig_key: returns the original key. 284a2b269bae3315a2ea772b741fb62f683c1db5770Sven Neumann * @value: returns the value associated with the key. 2858eed88b24e86f16021d94d9b16f7a2bc895d9239Ryan Lortie * 286a2b269bae3315a2ea772b741fb62f683c1db5770Sven Neumann * Looks up a key in the #GHashTable, returning the original key and the 2878eed88b24e86f16021d94d9b16f7a2bc895d9239Ryan Lortie * associated value and a #gboolean which is %TRUE if the key was found. This 2888eed88b24e86f16021d94d9b16f7a2bc895d9239Ryan Lortie * is useful if you need to free the memory allocated for the original key, 289a2b269bae3315a2ea772b741fb62f683c1db5770Sven Neumann * for example before calling g_hash_table_remove(). 2908eed88b24e86f16021d94d9b16f7a2bc895d9239Ryan Lortie * 2913fa33317b7e9866793ce1ea32d069e8c9270caa2Matthias Clasen * Return value: %TRUE if the key was found in the #GHashTable. 292a2b269bae3315a2ea772b741fb62f683c1db5770Sven Neumann **/ 293a2b269bae3315a2ea772b741fb62f683c1db5770Sven Neumanngboolean 294a2b269bae3315a2ea772b741fb62f683c1db5770Sven Neumanng_hash_table_lookup_extended (GHashTable *hash_table, 2958eed88b24e86f16021d94d9b16f7a2bc895d9239Ryan Lortie gconstpointer lookup_key, 2968eed88b24e86f16021d94d9b16f7a2bc895d9239Ryan Lortie gpointer *orig_key, 2978eed88b24e86f16021d94d9b16f7a2bc895d9239Ryan Lortie gpointer *value) 298a2b269bae3315a2ea772b741fb62f683c1db5770Sven Neumann{ 299a2b269bae3315a2ea772b741fb62f683c1db5770Sven Neumann GHashNode *node; 3008eed88b24e86f16021d94d9b16f7a2bc895d9239Ryan Lortie 301a2b269bae3315a2ea772b741fb62f683c1db5770Sven Neumann g_return_val_if_fail (hash_table != NULL, FALSE); 3028eed88b24e86f16021d94d9b16f7a2bc895d9239Ryan Lortie 303e6b78c9af1d6416f93311b98e1e6d802e2fe0617Ryan Lortie node = *g_hash_table_lookup_node (hash_table, lookup_key, NULL); 3048eed88b24e86f16021d94d9b16f7a2bc895d9239Ryan Lortie 305a2b269bae3315a2ea772b741fb62f683c1db5770Sven Neumann if (node) 306a2b269bae3315a2ea772b741fb62f683c1db5770Sven Neumann { 307a2b269bae3315a2ea772b741fb62f683c1db5770Sven Neumann if (orig_key) 3088eed88b24e86f16021d94d9b16f7a2bc895d9239Ryan Lortie *orig_key = node->key; 309a2b269bae3315a2ea772b741fb62f683c1db5770Sven Neumann if (value) 3108eed88b24e86f16021d94d9b16f7a2bc895d9239Ryan Lortie *value = node->value; 311a2b269bae3315a2ea772b741fb62f683c1db5770Sven Neumann return TRUE; 312a2b269bae3315a2ea772b741fb62f683c1db5770Sven Neumann } 313a2b269bae3315a2ea772b741fb62f683c1db5770Sven Neumann else 314a2b269bae3315a2ea772b741fb62f683c1db5770Sven Neumann return FALSE; 315a2b269bae3315a2ea772b741fb62f683c1db5770Sven Neumann} 316a2b269bae3315a2ea772b741fb62f683c1db5770Sven Neumann 3170adbacbff90cdab1b96e3409b6d510a00916b586Ryan Lortiestatic void 3180adbacbff90cdab1b96e3409b6d510a00916b586Ryan Lortieg_hash_table_insert_internal (GHashTable *hash_table, 3190adbacbff90cdab1b96e3409b6d510a00916b586Ryan Lortie gpointer key, 3200adbacbff90cdab1b96e3409b6d510a00916b586Ryan Lortie gpointer value, 3210adbacbff90cdab1b96e3409b6d510a00916b586Ryan Lortie gboolean keep_new_key) 3222d68cbbb7d37d3f265bf1087e6ddedcc58bc62beTim Janik{ 323d5492a983cfa048658af8b03f833ddb3c0cf355eEST GHashNode **node; 324e6b78c9af1d6416f93311b98e1e6d802e2fe0617Ryan Lortie guint key_hash; 3258eed88b24e86f16021d94d9b16f7a2bc895d9239Ryan Lortie 3262d68cbbb7d37d3f265bf1087e6ddedcc58bc62beTim Janik g_return_if_fail (hash_table != NULL); 3273e847a090cfd8495add631d43388c461b1a85716Tim Janik g_return_if_fail (hash_table->ref_count > 0); 3288eed88b24e86f16021d94d9b16f7a2bc895d9239Ryan Lortie 329e6b78c9af1d6416f93311b98e1e6d802e2fe0617Ryan Lortie node = g_hash_table_lookup_node (hash_table, key, &key_hash); 3308eed88b24e86f16021d94d9b16f7a2bc895d9239Ryan Lortie 331d5492a983cfa048658af8b03f833ddb3c0cf355eEST if (*node) 3327519c2338ae484135b44bbb7eb49719aea8c4ca3Lauri Alanko { 3335e02b01b210513c19b76731d303a7256d2db273cRyan Lortie if (keep_new_key) 3340adbacbff90cdab1b96e3409b6d510a00916b586Ryan Lortie { 3355e02b01b210513c19b76731d303a7256d2db273cRyan Lortie if (hash_table->key_destroy_func) 3360adbacbff90cdab1b96e3409b6d510a00916b586Ryan Lortie hash_table->key_destroy_func ((*node)->key); 3375e02b01b210513c19b76731d303a7256d2db273cRyan Lortie (*node)->key = key; 3385e02b01b210513c19b76731d303a7256d2db273cRyan Lortie } 3395e02b01b210513c19b76731d303a7256d2db273cRyan Lortie else 3405e02b01b210513c19b76731d303a7256d2db273cRyan Lortie { 3415e02b01b210513c19b76731d303a7256d2db273cRyan Lortie if (hash_table->key_destroy_func) 3420adbacbff90cdab1b96e3409b6d510a00916b586Ryan Lortie hash_table->key_destroy_func (key); 3430adbacbff90cdab1b96e3409b6d510a00916b586Ryan Lortie } 3448eed88b24e86f16021d94d9b16f7a2bc895d9239Ryan Lortie 345a2b269bae3315a2ea772b741fb62f683c1db5770Sven Neumann if (hash_table->value_destroy_func) 3468eed88b24e86f16021d94d9b16f7a2bc895d9239Ryan Lortie hash_table->value_destroy_func ((*node)->value); 347a2b269bae3315a2ea772b741fb62f683c1db5770Sven Neumann 348a2b269bae3315a2ea772b741fb62f683c1db5770Sven Neumann (*node)->value = value; 349a2b269bae3315a2ea772b741fb62f683c1db5770Sven Neumann } 350a2b269bae3315a2ea772b741fb62f683c1db5770Sven Neumann else 351a2b269bae3315a2ea772b741fb62f683c1db5770Sven Neumann { 352e6b78c9af1d6416f93311b98e1e6d802e2fe0617Ryan Lortie *node = g_hash_node_new (key, value, key_hash); 353a2b269bae3315a2ea772b741fb62f683c1db5770Sven Neumann hash_table->nnodes++; 35400c2db4e4b992a4fa667d49289c55b9d5f3fcf04Ryan Lortie g_hash_table_maybe_resize (hash_table); 355a2b269bae3315a2ea772b741fb62f683c1db5770Sven Neumann } 356a2b269bae3315a2ea772b741fb62f683c1db5770Sven Neumann} 357a2b269bae3315a2ea772b741fb62f683c1db5770Sven Neumann 358a2b269bae3315a2ea772b741fb62f683c1db5770Sven Neumann/** 3590adbacbff90cdab1b96e3409b6d510a00916b586Ryan Lortie * g_hash_table_insert: 3600adbacbff90cdab1b96e3409b6d510a00916b586Ryan Lortie * @hash_table: a #GHashTable. 3610adbacbff90cdab1b96e3409b6d510a00916b586Ryan Lortie * @key: a key to insert. 3620adbacbff90cdab1b96e3409b6d510a00916b586Ryan Lortie * @value: the value to associate with the key. 3638eed88b24e86f16021d94d9b16f7a2bc895d9239Ryan Lortie * 3640adbacbff90cdab1b96e3409b6d510a00916b586Ryan Lortie * Inserts a new key and value into a #GHashTable. 3658eed88b24e86f16021d94d9b16f7a2bc895d9239Ryan Lortie * 3660adbacbff90cdab1b96e3409b6d510a00916b586Ryan Lortie * If the key already exists in the #GHashTable its current value is replaced 3678eed88b24e86f16021d94d9b16f7a2bc895d9239Ryan Lortie * with the new value. If you supplied a @value_destroy_func when creating the 3680adbacbff90cdab1b96e3409b6d510a00916b586Ryan Lortie * #GHashTable, the old value is freed using that function. If you supplied 3698eed88b24e86f16021d94d9b16f7a2bc895d9239Ryan Lortie * a @key_destroy_func when creating the #GHashTable, the passed key is freed 3700adbacbff90cdab1b96e3409b6d510a00916b586Ryan Lortie * using that function. 3710adbacbff90cdab1b96e3409b6d510a00916b586Ryan Lortie **/ 3720adbacbff90cdab1b96e3409b6d510a00916b586Ryan Lortievoid 3730adbacbff90cdab1b96e3409b6d510a00916b586Ryan Lortieg_hash_table_insert (GHashTable *hash_table, 3748eed88b24e86f16021d94d9b16f7a2bc895d9239Ryan Lortie gpointer key, 3758eed88b24e86f16021d94d9b16f7a2bc895d9239Ryan Lortie gpointer value) 3760adbacbff90cdab1b96e3409b6d510a00916b586Ryan Lortie{ 3770adbacbff90cdab1b96e3409b6d510a00916b586Ryan Lortie return g_hash_table_insert_internal (hash_table, key, value, FALSE); 3780adbacbff90cdab1b96e3409b6d510a00916b586Ryan Lortie} 3790adbacbff90cdab1b96e3409b6d510a00916b586Ryan Lortie 3800adbacbff90cdab1b96e3409b6d510a00916b586Ryan Lortie/** 381a2b269bae3315a2ea772b741fb62f683c1db5770Sven Neumann * g_hash_table_replace: 382a2b269bae3315a2ea772b741fb62f683c1db5770Sven Neumann * @hash_table: a #GHashTable. 383a2b269bae3315a2ea772b741fb62f683c1db5770Sven Neumann * @key: a key to insert. 384a2b269bae3315a2ea772b741fb62f683c1db5770Sven Neumann * @value: the value to associate with the key. 3858eed88b24e86f16021d94d9b16f7a2bc895d9239Ryan Lortie * 3868eed88b24e86f16021d94d9b16f7a2bc895d9239Ryan Lortie * Inserts a new key and value into a #GHashTable similar to 3878eed88b24e86f16021d94d9b16f7a2bc895d9239Ryan Lortie * g_hash_table_insert(). The difference is that if the key already exists 3888eed88b24e86f16021d94d9b16f7a2bc895d9239Ryan Lortie * in the #GHashTable, it gets replaced by the new key. If you supplied a 3898eed88b24e86f16021d94d9b16f7a2bc895d9239Ryan Lortie * @value_destroy_func when creating the #GHashTable, the old value is freed 3908eed88b24e86f16021d94d9b16f7a2bc895d9239Ryan Lortie * using that function. If you supplied a @key_destroy_func when creating the 3918eed88b24e86f16021d94d9b16f7a2bc895d9239Ryan Lortie * #GHashTable, the old key is freed using that function. 392a2b269bae3315a2ea772b741fb62f683c1db5770Sven Neumann **/ 393a2b269bae3315a2ea772b741fb62f683c1db5770Sven Neumannvoid 394a2b269bae3315a2ea772b741fb62f683c1db5770Sven Neumanng_hash_table_replace (GHashTable *hash_table, 3958eed88b24e86f16021d94d9b16f7a2bc895d9239Ryan Lortie gpointer key, 3968eed88b24e86f16021d94d9b16f7a2bc895d9239Ryan Lortie gpointer value) 397a2b269bae3315a2ea772b741fb62f683c1db5770Sven Neumann{ 3980adbacbff90cdab1b96e3409b6d510a00916b586Ryan Lortie return g_hash_table_insert_internal (hash_table, key, value, TRUE); 3992e0320d57e417f7d1c838d729a99545db2228e9Owen Taylor} 4002e0320d57e417f7d1c838d729a99545db2228e9Owen Taylor 401e9010a86f763e6b7cb1fd5520985c929339f5523Ryan Lortiestatic void 402e9010a86f763e6b7cb1fd5520985c929339f5523Ryan Lortieg_hash_table_remove_node (GHashTable *hash_table, 403e9010a86f763e6b7cb1fd5520985c929339f5523Ryan Lortie GHashNode ***node_ptr_ptr, 404e9010a86f763e6b7cb1fd5520985c929339f5523Ryan Lortie gboolean notify) 405e9010a86f763e6b7cb1fd5520985c929339f5523Ryan Lortie{ 406e9010a86f763e6b7cb1fd5520985c929339f5523Ryan Lortie GHashNode **node_ptr, *node; 407e9010a86f763e6b7cb1fd5520985c929339f5523Ryan Lortie 408e9010a86f763e6b7cb1fd5520985c929339f5523Ryan Lortie node_ptr = *node_ptr_ptr; 409e9010a86f763e6b7cb1fd5520985c929339f5523Ryan Lortie node = *node_ptr; 410e9010a86f763e6b7cb1fd5520985c929339f5523Ryan Lortie 411e9010a86f763e6b7cb1fd5520985c929339f5523Ryan Lortie *node_ptr = node->next; 412e9010a86f763e6b7cb1fd5520985c929339f5523Ryan Lortie 41372ed8191afd8ff124a45285b420625e1342e35cfRyan Lortie if (notify && hash_table->key_destroy_func) 41472ed8191afd8ff124a45285b420625e1342e35cfRyan Lortie hash_table->key_destroy_func (node->key); 41572ed8191afd8ff124a45285b420625e1342e35cfRyan Lortie 41672ed8191afd8ff124a45285b420625e1342e35cfRyan Lortie if (notify && hash_table->value_destroy_func) 41772ed8191afd8ff124a45285b420625e1342e35cfRyan Lortie hash_table->value_destroy_func (node->value); 41872ed8191afd8ff124a45285b420625e1342e35cfRyan Lortie 41972ed8191afd8ff124a45285b420625e1342e35cfRyan Lortie g_slice_free (GHashNode, node); 420e9010a86f763e6b7cb1fd5520985c929339f5523Ryan Lortie 421e9010a86f763e6b7cb1fd5520985c929339f5523Ryan Lortie hash_table->nnodes--; 422e9010a86f763e6b7cb1fd5520985c929339f5523Ryan Lortie} 423e9010a86f763e6b7cb1fd5520985c929339f5523Ryan Lortie 42472ed8191afd8ff124a45285b420625e1342e35cfRyan Lortiestatic void 42572ed8191afd8ff124a45285b420625e1342e35cfRyan Lortieg_hash_table_remove_all_nodes (GHashTable *hash_table, 42672ed8191afd8ff124a45285b420625e1342e35cfRyan Lortie gboolean notify) 42772ed8191afd8ff124a45285b420625e1342e35cfRyan Lortie{ 42872ed8191afd8ff124a45285b420625e1342e35cfRyan Lortie GHashNode **node_ptr; 42972ed8191afd8ff124a45285b420625e1342e35cfRyan Lortie int i; 43072ed8191afd8ff124a45285b420625e1342e35cfRyan Lortie 43172ed8191afd8ff124a45285b420625e1342e35cfRyan Lortie for (i = 0; i < hash_table->size; i++) 43272ed8191afd8ff124a45285b420625e1342e35cfRyan Lortie for (node_ptr = &hash_table->nodes[i]; *node_ptr != NULL;) 43372ed8191afd8ff124a45285b420625e1342e35cfRyan Lortie g_hash_table_remove_node (hash_table, &node_ptr, notify); 43472ed8191afd8ff124a45285b420625e1342e35cfRyan Lortie 43572ed8191afd8ff124a45285b420625e1342e35cfRyan Lortie hash_table->nnodes = 0; 43672ed8191afd8ff124a45285b420625e1342e35cfRyan Lortie} 43772ed8191afd8ff124a45285b420625e1342e35cfRyan Lortie 438e9010a86f763e6b7cb1fd5520985c929339f5523Ryan Lortiestatic gboolean 439e9010a86f763e6b7cb1fd5520985c929339f5523Ryan Lortieg_hash_table_remove_internal (GHashTable *hash_table, 440e9010a86f763e6b7cb1fd5520985c929339f5523Ryan Lortie gconstpointer key, 441e9010a86f763e6b7cb1fd5520985c929339f5523Ryan Lortie gboolean notify) 442e9010a86f763e6b7cb1fd5520985c929339f5523Ryan Lortie{ 443e9010a86f763e6b7cb1fd5520985c929339f5523Ryan Lortie GHashNode **node_ptr; 4448eed88b24e86f16021d94d9b16f7a2bc895d9239Ryan Lortie 445e9010a86f763e6b7cb1fd5520985c929339f5523Ryan Lortie g_return_val_if_fail (hash_table != NULL, FALSE); 4468eed88b24e86f16021d94d9b16f7a2bc895d9239Ryan Lortie 447e9010a86f763e6b7cb1fd5520985c929339f5523Ryan Lortie node_ptr = g_hash_table_lookup_node (hash_table, key, NULL); 448e9010a86f763e6b7cb1fd5520985c929339f5523Ryan Lortie if (*node_ptr == NULL) 449e9010a86f763e6b7cb1fd5520985c929339f5523Ryan Lortie return FALSE; 450e9010a86f763e6b7cb1fd5520985c929339f5523Ryan Lortie 45172ed8191afd8ff124a45285b420625e1342e35cfRyan Lortie g_hash_table_remove_node (hash_table, &node_ptr, notify); 45200c2db4e4b992a4fa667d49289c55b9d5f3fcf04Ryan Lortie g_hash_table_maybe_resize (hash_table); 453e9010a86f763e6b7cb1fd5520985c929339f5523Ryan Lortie 454e9010a86f763e6b7cb1fd5520985c929339f5523Ryan Lortie return TRUE; 455e9010a86f763e6b7cb1fd5520985c929339f5523Ryan Lortie} 456e9010a86f763e6b7cb1fd5520985c929339f5523Ryan Lortie 457a2b269bae3315a2ea772b741fb62f683c1db5770Sven Neumann/** 458a2b269bae3315a2ea772b741fb62f683c1db5770Sven Neumann * g_hash_table_remove: 459a2b269bae3315a2ea772b741fb62f683c1db5770Sven Neumann * @hash_table: a #GHashTable. 460a2b269bae3315a2ea772b741fb62f683c1db5770Sven Neumann * @key: the key to remove. 4618eed88b24e86f16021d94d9b16f7a2bc895d9239Ryan Lortie * 462a2b269bae3315a2ea772b741fb62f683c1db5770Sven Neumann * Removes a key and its associated value from a #GHashTable. 463a2b269bae3315a2ea772b741fb62f683c1db5770Sven Neumann * 464a2b269bae3315a2ea772b741fb62f683c1db5770Sven Neumann * If the #GHashTable was created using g_hash_table_new_full(), the 465a52e2986cd4a2147cfc8d41ae23d98907caaf3a0Matthias Clasen * key and value are freed using the supplied destroy functions, otherwise 4668eed88b24e86f16021d94d9b16f7a2bc895d9239Ryan Lortie * you have to make sure that any dynamically allocated values are freed 467a2b269bae3315a2ea772b741fb62f683c1db5770Sven Neumann * yourself. 4688eed88b24e86f16021d94d9b16f7a2bc895d9239Ryan Lortie * 4693fa33317b7e9866793ce1ea32d069e8c9270caa2Matthias Clasen * Return value: %TRUE if the key was found and removed from the #GHashTable. 470a2b269bae3315a2ea772b741fb62f683c1db5770Sven Neumann **/ 4719a8c33db5cc37bc3c6bd4794a03f4b99a847ff4aTim Janikgboolean 4728eed88b24e86f16021d94d9b16f7a2bc895d9239Ryan Lortieg_hash_table_remove (GHashTable *hash_table, 473e9010a86f763e6b7cb1fd5520985c929339f5523Ryan Lortie gconstpointer key) 4742e0320d57e417f7d1c838d729a99545db2228e9Owen Taylor{ 475e9010a86f763e6b7cb1fd5520985c929339f5523Ryan Lortie return g_hash_table_remove_internal (hash_table, key, TRUE); 4762e0320d57e417f7d1c838d729a99545db2228e9Owen Taylor} 4772e0320d57e417f7d1c838d729a99545db2228e9Owen Taylor 478a2b269bae3315a2ea772b741fb62f683c1db5770Sven Neumann/** 479a5b4b8bfb18838454d99bdee60294da07e5ef0d2Matthias Clasen * g_hash_table_remove_all: 480a5b4b8bfb18838454d99bdee60294da07e5ef0d2Matthias Clasen * @hash_table: a #GHashTable 481a5b4b8bfb18838454d99bdee60294da07e5ef0d2Matthias Clasen * 482a5b4b8bfb18838454d99bdee60294da07e5ef0d2Matthias Clasen * Removes all keys and their associated values from a #GHashTable. 483a5b4b8bfb18838454d99bdee60294da07e5ef0d2Matthias Clasen * 484a5b4b8bfb18838454d99bdee60294da07e5ef0d2Matthias Clasen * If the #GHashTable was created using g_hash_table_new_full(), the keys 485a5b4b8bfb18838454d99bdee60294da07e5ef0d2Matthias Clasen * and values are freed using the supplied destroy functions, otherwise you 486a5b4b8bfb18838454d99bdee60294da07e5ef0d2Matthias Clasen * have to make sure that any dynamically allocated values are freed 487a5b4b8bfb18838454d99bdee60294da07e5ef0d2Matthias Clasen * yourself. 488a5b4b8bfb18838454d99bdee60294da07e5ef0d2Matthias Clasen * 489a5b4b8bfb18838454d99bdee60294da07e5ef0d2Matthias Clasen * Since: 2.12 490a5b4b8bfb18838454d99bdee60294da07e5ef0d2Matthias Clasen **/ 491a5b4b8bfb18838454d99bdee60294da07e5ef0d2Matthias Clasenvoid 492a5b4b8bfb18838454d99bdee60294da07e5ef0d2Matthias Claseng_hash_table_remove_all (GHashTable *hash_table) 493a5b4b8bfb18838454d99bdee60294da07e5ef0d2Matthias Clasen{ 494a5b4b8bfb18838454d99bdee60294da07e5ef0d2Matthias Clasen g_return_if_fail (hash_table != NULL); 495a5b4b8bfb18838454d99bdee60294da07e5ef0d2Matthias Clasen 49672ed8191afd8ff124a45285b420625e1342e35cfRyan Lortie g_hash_table_remove_all_nodes (hash_table, TRUE); 49700c2db4e4b992a4fa667d49289c55b9d5f3fcf04Ryan Lortie g_hash_table_maybe_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. 5048eed88b24e86f16021d94d9b16f7a2bc895d9239Ryan Lortie * 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 * 5218eed88b24e86f16021d94d9b16f7a2bc895d9239Ryan Lortie * 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 g_return_if_fail (hash_table != NULL); 530a5b4b8bfb18838454d99bdee60294da07e5ef0d2Matthias Clasen 53172ed8191afd8ff124a45285b420625e1342e35cfRyan Lortie g_hash_table_remove_all_nodes (hash_table, FALSE); 53200c2db4e4b992a4fa667d49289c55b9d5f3fcf04Ryan Lortie g_hash_table_maybe_resize (hash_table); 533a5b4b8bfb18838454d99bdee60294da07e5ef0d2Matthias Clasen} 534a5b4b8bfb18838454d99bdee60294da07e5ef0d2Matthias Clasen 535a5b4b8bfb18838454d99bdee60294da07e5ef0d2Matthias Clasen/** 536a2b269bae3315a2ea772b741fb62f683c1db5770Sven Neumann * g_hash_table_foreach_remove: 537a2b269bae3315a2ea772b741fb62f683c1db5770Sven Neumann * @hash_table: a #GHashTable. 538a2b269bae3315a2ea772b741fb62f683c1db5770Sven Neumann * @func: the function to call for each key/value pair. 539a2b269bae3315a2ea772b741fb62f683c1db5770Sven Neumann * @user_data: user data to pass to the function. 5408eed88b24e86f16021d94d9b16f7a2bc895d9239Ryan Lortie * 541a2b269bae3315a2ea772b741fb62f683c1db5770Sven Neumann * Calls the given function for each key/value pair in the #GHashTable. 542a52e2986cd4a2147cfc8d41ae23d98907caaf3a0Matthias Clasen * If the function returns %TRUE, then the key/value pair is removed from the 543a2b269bae3315a2ea772b741fb62f683c1db5770Sven Neumann * #GHashTable. If you supplied key or value destroy functions when creating 544a2b269bae3315a2ea772b741fb62f683c1db5770Sven Neumann * the #GHashTable, they are used to free the memory allocated for the removed 545a2b269bae3315a2ea772b741fb62f683c1db5770Sven Neumann * keys and values. 5468eed88b24e86f16021d94d9b16f7a2bc895d9239Ryan Lortie * 547a2b269bae3315a2ea772b741fb62f683c1db5770Sven Neumann * Return value: the number of key/value pairs removed. 548a2b269bae3315a2ea772b741fb62f683c1db5770Sven Neumann **/ 549a2b269bae3315a2ea772b741fb62f683c1db5770Sven Neumannguint 5508eed88b24e86f16021d94d9b16f7a2bc895d9239Ryan Lortieg_hash_table_foreach_remove (GHashTable *hash_table, 5518eed88b24e86f16021d94d9b16f7a2bc895d9239Ryan Lortie GHRFunc func, 5528eed88b24e86f16021d94d9b16f7a2bc895d9239Ryan Lortie gpointer user_data) 5532e0320d57e417f7d1c838d729a99545db2228e9Owen Taylor{ 554a2b269bae3315a2ea772b741fb62f683c1db5770Sven Neumann g_return_val_if_fail (hash_table != NULL, 0); 555a2b269bae3315a2ea772b741fb62f683c1db5770Sven Neumann g_return_val_if_fail (func != NULL, 0); 5568eed88b24e86f16021d94d9b16f7a2bc895d9239Ryan Lortie 557a2b269bae3315a2ea772b741fb62f683c1db5770Sven Neumann return g_hash_table_foreach_remove_or_steal (hash_table, func, user_data, TRUE); 5582e0320d57e417f7d1c838d729a99545db2228e9Owen Taylor} 5592e0320d57e417f7d1c838d729a99545db2228e9Owen Taylor 560a2b269bae3315a2ea772b741fb62f683c1db5770Sven Neumann/** 561a2b269bae3315a2ea772b741fb62f683c1db5770Sven Neumann * g_hash_table_foreach_steal: 562a2b269bae3315a2ea772b741fb62f683c1db5770Sven Neumann * @hash_table: a #GHashTable. 563a2b269bae3315a2ea772b741fb62f683c1db5770Sven Neumann * @func: the function to call for each key/value pair. 564a2b269bae3315a2ea772b741fb62f683c1db5770Sven Neumann * @user_data: user data to pass to the function. 5658eed88b24e86f16021d94d9b16f7a2bc895d9239Ryan Lortie * 566a2b269bae3315a2ea772b741fb62f683c1db5770Sven Neumann * Calls the given function for each key/value pair in the #GHashTable. 567a52e2986cd4a2147cfc8d41ae23d98907caaf3a0Matthias Clasen * If the function returns %TRUE, then the key/value pair is removed from the 568a2b269bae3315a2ea772b741fb62f683c1db5770Sven Neumann * #GHashTable, but no key or value destroy functions are called. 5698eed88b24e86f16021d94d9b16f7a2bc895d9239Ryan Lortie * 570a2b269bae3315a2ea772b741fb62f683c1db5770Sven Neumann * Return value: the number of key/value pairs removed. 571a2b269bae3315a2ea772b741fb62f683c1db5770Sven Neumann **/ 572a2b269bae3315a2ea772b741fb62f683c1db5770Sven Neumannguint 573a2b269bae3315a2ea772b741fb62f683c1db5770Sven Neumanng_hash_table_foreach_steal (GHashTable *hash_table, 5748eed88b24e86f16021d94d9b16f7a2bc895d9239Ryan Lortie GHRFunc func, 5758eed88b24e86f16021d94d9b16f7a2bc895d9239Ryan Lortie gpointer user_data) 5762e0320d57e417f7d1c838d729a99545db2228e9Owen Taylor{ 577a2b269bae3315a2ea772b741fb62f683c1db5770Sven Neumann g_return_val_if_fail (hash_table != NULL, 0); 578a2b269bae3315a2ea772b741fb62f683c1db5770Sven Neumann g_return_val_if_fail (func != NULL, 0); 5798eed88b24e86f16021d94d9b16f7a2bc895d9239Ryan Lortie 580a2b269bae3315a2ea772b741fb62f683c1db5770Sven Neumann return g_hash_table_foreach_remove_or_steal (hash_table, func, user_data, FALSE); 5812e0320d57e417f7d1c838d729a99545db2228e9Owen Taylor} 5822e0320d57e417f7d1c838d729a99545db2228e9Owen Taylor 583a2b269bae3315a2ea772b741fb62f683c1db5770Sven Neumannstatic guint 584a2b269bae3315a2ea772b741fb62f683c1db5770Sven Neumanng_hash_table_foreach_remove_or_steal (GHashTable *hash_table, 585a2b269bae3315a2ea772b741fb62f683c1db5770Sven Neumann GHRFunc func, 5868eed88b24e86f16021d94d9b16f7a2bc895d9239Ryan Lortie gpointer user_data, 587a2b269bae3315a2ea772b741fb62f683c1db5770Sven Neumann gboolean notify) 588034e7c0339f64d4d52a53f2324daa2fca0332addManish Singh{ 589e9010a86f763e6b7cb1fd5520985c929339f5523Ryan Lortie GHashNode *node, **node_ptr; 590d31ba84c8ea40b6f0199318e43cc2bb2e816c586Tim Janik guint deleted = 0; 591e9010a86f763e6b7cb1fd5520985c929339f5523Ryan Lortie gint i; 592e9010a86f763e6b7cb1fd5520985c929339f5523Ryan Lortie 593034e7c0339f64d4d52a53f2324daa2fca0332addManish Singh for (i = 0; i < hash_table->size; i++) 594e9010a86f763e6b7cb1fd5520985c929339f5523Ryan Lortie for (node_ptr = &hash_table->nodes[i]; (node = *node_ptr) != NULL;) 595e9010a86f763e6b7cb1fd5520985c929339f5523Ryan Lortie if ((* func) (node->key, node->value, user_data)) 596e9010a86f763e6b7cb1fd5520985c929339f5523Ryan Lortie { 597e9010a86f763e6b7cb1fd5520985c929339f5523Ryan Lortie g_hash_table_remove_node (hash_table, &node_ptr, notify); 598e9010a86f763e6b7cb1fd5520985c929339f5523Ryan Lortie deleted++; 599e9010a86f763e6b7cb1fd5520985c929339f5523Ryan Lortie } 600e9010a86f763e6b7cb1fd5520985c929339f5523Ryan Lortie else 601e9010a86f763e6b7cb1fd5520985c929339f5523Ryan Lortie node_ptr = &node->next; 602e9010a86f763e6b7cb1fd5520985c929339f5523Ryan Lortie 60300c2db4e4b992a4fa667d49289c55b9d5f3fcf04Ryan Lortie g_hash_table_maybe_resize (hash_table); 604e9010a86f763e6b7cb1fd5520985c929339f5523Ryan Lortie 605034e7c0339f64d4d52a53f2324daa2fca0332addManish Singh return deleted; 606034e7c0339f64d4d52a53f2324daa2fca0332addManish Singh} 607034e7c0339f64d4d52a53f2324daa2fca0332addManish Singh 608a2b269bae3315a2ea772b741fb62f683c1db5770Sven Neumann/** 609a2b269bae3315a2ea772b741fb62f683c1db5770Sven Neumann * g_hash_table_foreach: 610a2b269bae3315a2ea772b741fb62f683c1db5770Sven Neumann * @hash_table: a #GHashTable. 611a2b269bae3315a2ea772b741fb62f683c1db5770Sven Neumann * @func: the function to call for each key/value pair. 612a2b269bae3315a2ea772b741fb62f683c1db5770Sven Neumann * @user_data: user data to pass to the function. 6138eed88b24e86f16021d94d9b16f7a2bc895d9239Ryan Lortie * 614eb2f6f6fc1052abfa05f016ab2aed0cd0c338992Havoc Pennington * Calls the given function for each of the key/value pairs in the 615eb2f6f6fc1052abfa05f016ab2aed0cd0c338992Havoc Pennington * #GHashTable. The function is passed the key and value of each 616eb2f6f6fc1052abfa05f016ab2aed0cd0c338992Havoc Pennington * pair, and the given @user_data parameter. The hash table may not 617eb2f6f6fc1052abfa05f016ab2aed0cd0c338992Havoc Pennington * be modified while iterating over it (you can't add/remove 618eb2f6f6fc1052abfa05f016ab2aed0cd0c338992Havoc Pennington * items). To remove all items matching a predicate, use 61927096aedb58342fc8a25c17fa7d6647209425f4eMatthias Clasen * g_hash_table_foreach_remove(). 6202ef43de2af9dbb1b1ea583639c7339afe9c09af0Tim Janik * 6212ef43de2af9dbb1b1ea583639c7339afe9c09af0Tim Janik * See g_hash_table_find() for performance caveats for linear 6222ef43de2af9dbb1b1ea583639c7339afe9c09af0Tim Janik * order searches in contrast to g_hash_table_lookup(). 623a2b269bae3315a2ea772b741fb62f683c1db5770Sven Neumann **/ 6242e0320d57e417f7d1c838d729a99545db2228e9Owen Taylorvoid 6252e0320d57e417f7d1c838d729a99545db2228e9Owen Taylorg_hash_table_foreach (GHashTable *hash_table, 6268eed88b24e86f16021d94d9b16f7a2bc895d9239Ryan Lortie GHFunc func, 6278eed88b24e86f16021d94d9b16f7a2bc895d9239Ryan Lortie gpointer user_data) 6282e0320d57e417f7d1c838d729a99545db2228e9Owen Taylor{ 6292e0320d57e417f7d1c838d729a99545db2228e9Owen Taylor GHashNode *node; 6302e0320d57e417f7d1c838d729a99545db2228e9Owen Taylor gint i; 6318eed88b24e86f16021d94d9b16f7a2bc895d9239Ryan Lortie 6322d68cbbb7d37d3f265bf1087e6ddedcc58bc62beTim Janik g_return_if_fail (hash_table != NULL); 6332d68cbbb7d37d3f265bf1087e6ddedcc58bc62beTim Janik g_return_if_fail (func != NULL); 6348eed88b24e86f16021d94d9b16f7a2bc895d9239Ryan Lortie 6357519c2338ae484135b44bbb7eb49719aea8c4ca3Lauri Alanko for (i = 0; i < hash_table->size; i++) 6367519c2338ae484135b44bbb7eb49719aea8c4ca3Lauri Alanko for (node = hash_table->nodes[i]; node; node = node->next) 6377519c2338ae484135b44bbb7eb49719aea8c4ca3Lauri Alanko (* func) (node->key, node->value, user_data); 6382e0320d57e417f7d1c838d729a99545db2228e9Owen Taylor} 6392e0320d57e417f7d1c838d729a99545db2228e9Owen Taylor 640a2b269bae3315a2ea772b741fb62f683c1db5770Sven Neumann/** 641ee4e622d3724a6dfee8ce9463eccb31081cf852fTim Janik * g_hash_table_find: 642ee4e622d3724a6dfee8ce9463eccb31081cf852fTim Janik * @hash_table: a #GHashTable. 643ee4e622d3724a6dfee8ce9463eccb31081cf852fTim Janik * @predicate: function to test the key/value pairs for a certain property. 644ee4e622d3724a6dfee8ce9463eccb31081cf852fTim Janik * @user_data: user data to pass to the function. 6458eed88b24e86f16021d94d9b16f7a2bc895d9239Ryan Lortie * 6468eed88b24e86f16021d94d9b16f7a2bc895d9239Ryan Lortie * Calls the given function for key/value pairs in the #GHashTable until 6478eed88b24e86f16021d94d9b16f7a2bc895d9239Ryan Lortie * @predicate returns %TRUE. The function is passed the key and value of 6483ce97fa284cbefdc2eb957f50a3a76d6ef923464Matthias Clasen * each pair, and the given @user_data parameter. The hash table may not 6492ef43de2af9dbb1b1ea583639c7339afe9c09af0Tim Janik * be modified while iterating over it (you can't add/remove items). 6502ef43de2af9dbb1b1ea583639c7339afe9c09af0Tim Janik * 6512ef43de2af9dbb1b1ea583639c7339afe9c09af0Tim Janik * Note, that hash tables are really only optimized for forward lookups, 6522ef43de2af9dbb1b1ea583639c7339afe9c09af0Tim Janik * i.e. g_hash_table_lookup(). 6532ef43de2af9dbb1b1ea583639c7339afe9c09af0Tim Janik * So code that frequently issues g_hash_table_find() or 6542ef43de2af9dbb1b1ea583639c7339afe9c09af0Tim Janik * g_hash_table_foreach() (e.g. in the order of once per every entry in a 6552ef43de2af9dbb1b1ea583639c7339afe9c09af0Tim Janik * hash table) should probably be reworked to use additional or different 6562ef43de2af9dbb1b1ea583639c7339afe9c09af0Tim Janik * data structures for reverse lookups (keep in mind that an O(n) find/foreach 6572ef43de2af9dbb1b1ea583639c7339afe9c09af0Tim Janik * operation issued for all n values in a hash table ends up needing O(n*n) 6582ef43de2af9dbb1b1ea583639c7339afe9c09af0Tim Janik * operations). 6593ce97fa284cbefdc2eb957f50a3a76d6ef923464Matthias Clasen * 6602ef43de2af9dbb1b1ea583639c7339afe9c09af0Tim Janik * Return value: The value of the first key/value pair is returned, for which 6612ef43de2af9dbb1b1ea583639c7339afe9c09af0Tim Janik * func evaluates to %TRUE. If no pair with the requested property is found, 6623ce97fa284cbefdc2eb957f50a3a76d6ef923464Matthias Clasen * %NULL is returned. 6633ce97fa284cbefdc2eb957f50a3a76d6ef923464Matthias Clasen * 6643ce97fa284cbefdc2eb957f50a3a76d6ef923464Matthias Clasen * Since: 2.4 665ee4e622d3724a6dfee8ce9463eccb31081cf852fTim Janik **/ 666ee4e622d3724a6dfee8ce9463eccb31081cf852fTim Janikgpointer 6678eed88b24e86f16021d94d9b16f7a2bc895d9239Ryan Lortieg_hash_table_find (GHashTable *hash_table, 6688eed88b24e86f16021d94d9b16f7a2bc895d9239Ryan Lortie GHRFunc predicate, 6698eed88b24e86f16021d94d9b16f7a2bc895d9239Ryan Lortie gpointer user_data) 670ee4e622d3724a6dfee8ce9463eccb31081cf852fTim Janik{ 671ee4e622d3724a6dfee8ce9463eccb31081cf852fTim Janik GHashNode *node; 672ee4e622d3724a6dfee8ce9463eccb31081cf852fTim Janik gint i; 6738eed88b24e86f16021d94d9b16f7a2bc895d9239Ryan Lortie 674ee4e622d3724a6dfee8ce9463eccb31081cf852fTim Janik g_return_val_if_fail (hash_table != NULL, NULL); 675ee4e622d3724a6dfee8ce9463eccb31081cf852fTim Janik g_return_val_if_fail (predicate != NULL, NULL); 6768eed88b24e86f16021d94d9b16f7a2bc895d9239Ryan Lortie 677ee4e622d3724a6dfee8ce9463eccb31081cf852fTim Janik for (i = 0; i < hash_table->size; i++) 678ee4e622d3724a6dfee8ce9463eccb31081cf852fTim Janik for (node = hash_table->nodes[i]; node; node = node->next) 679ee4e622d3724a6dfee8ce9463eccb31081cf852fTim Janik if (predicate (node->key, node->value, user_data)) 6808eed88b24e86f16021d94d9b16f7a2bc895d9239Ryan Lortie return node->value; 681ee4e622d3724a6dfee8ce9463eccb31081cf852fTim Janik return NULL; 682ee4e622d3724a6dfee8ce9463eccb31081cf852fTim Janik} 683ee4e622d3724a6dfee8ce9463eccb31081cf852fTim Janik 684ee4e622d3724a6dfee8ce9463eccb31081cf852fTim Janik/** 685a2b269bae3315a2ea772b741fb62f683c1db5770Sven Neumann * g_hash_table_size: 686a2b269bae3315a2ea772b741fb62f683c1db5770Sven Neumann * @hash_table: a #GHashTable. 6878eed88b24e86f16021d94d9b16f7a2bc895d9239Ryan Lortie * 688a2b269bae3315a2ea772b741fb62f683c1db5770Sven Neumann * Returns the number of elements contained in the #GHashTable. 6898eed88b24e86f16021d94d9b16f7a2bc895d9239Ryan Lortie * 690a2b269bae3315a2ea772b741fb62f683c1db5770Sven Neumann * Return value: the number of key/value pairs in the #GHashTable. 691a2b269bae3315a2ea772b741fb62f683c1db5770Sven Neumann **/ 692d31ba84c8ea40b6f0199318e43cc2bb2e816c586Tim Janikguint 6932d68cbbb7d37d3f265bf1087e6ddedcc58bc62beTim Janikg_hash_table_size (GHashTable *hash_table) 6947519c2338ae484135b44bbb7eb49719aea8c4ca3Lauri Alanko{ 6952d68cbbb7d37d3f265bf1087e6ddedcc58bc62beTim Janik g_return_val_if_fail (hash_table != NULL, 0); 6968eed88b24e86f16021d94d9b16f7a2bc895d9239Ryan Lortie 6977519c2338ae484135b44bbb7eb49719aea8c4ca3Lauri Alanko return hash_table->nnodes; 6987519c2338ae484135b44bbb7eb49719aea8c4ca3Lauri Alanko} 6992e0320d57e417f7d1c838d729a99545db2228e9Owen Taylor 700db8642a56c0436aeb730ead593140bc01b82d4acEmmanuele Bassi/** 701db8642a56c0436aeb730ead593140bc01b82d4acEmmanuele Bassi * g_hash_table_get_keys: 702db8642a56c0436aeb730ead593140bc01b82d4acEmmanuele Bassi * @hash_table: a #GHashTable 703db8642a56c0436aeb730ead593140bc01b82d4acEmmanuele Bassi * 704db8642a56c0436aeb730ead593140bc01b82d4acEmmanuele Bassi * Retrieves every key inside @hash_table. The returned data is valid 705db8642a56c0436aeb730ead593140bc01b82d4acEmmanuele Bassi * until @hash_table is modified. 706db8642a56c0436aeb730ead593140bc01b82d4acEmmanuele Bassi * 707db8642a56c0436aeb730ead593140bc01b82d4acEmmanuele Bassi * Return value: a #GList containing all the keys inside the hash 708db8642a56c0436aeb730ead593140bc01b82d4acEmmanuele Bassi * table. The content of the list is owned by the hash table and 709db8642a56c0436aeb730ead593140bc01b82d4acEmmanuele Bassi * should not be modified or freed. Use g_list_free() when done 710db8642a56c0436aeb730ead593140bc01b82d4acEmmanuele Bassi * using the list. 711db8642a56c0436aeb730ead593140bc01b82d4acEmmanuele Bassi * 712db8642a56c0436aeb730ead593140bc01b82d4acEmmanuele Bassi * Since: 2.14 713db8642a56c0436aeb730ead593140bc01b82d4acEmmanuele Bassi */ 714db8642a56c0436aeb730ead593140bc01b82d4acEmmanuele BassiGList * 715db8642a56c0436aeb730ead593140bc01b82d4acEmmanuele Bassig_hash_table_get_keys (GHashTable *hash_table) 716db8642a56c0436aeb730ead593140bc01b82d4acEmmanuele Bassi{ 717db8642a56c0436aeb730ead593140bc01b82d4acEmmanuele Bassi GHashNode *node; 718db8642a56c0436aeb730ead593140bc01b82d4acEmmanuele Bassi gint i; 719db8642a56c0436aeb730ead593140bc01b82d4acEmmanuele Bassi GList *retval; 7208eed88b24e86f16021d94d9b16f7a2bc895d9239Ryan Lortie 721db8642a56c0436aeb730ead593140bc01b82d4acEmmanuele Bassi g_return_val_if_fail (hash_table != NULL, NULL); 7228eed88b24e86f16021d94d9b16f7a2bc895d9239Ryan Lortie 723db8642a56c0436aeb730ead593140bc01b82d4acEmmanuele Bassi retval = NULL; 724db8642a56c0436aeb730ead593140bc01b82d4acEmmanuele Bassi for (i = 0; i < hash_table->size; i++) 725db8642a56c0436aeb730ead593140bc01b82d4acEmmanuele Bassi for (node = hash_table->nodes[i]; node; node = node->next) 726db8642a56c0436aeb730ead593140bc01b82d4acEmmanuele Bassi retval = g_list_prepend (retval, node->key); 7278eed88b24e86f16021d94d9b16f7a2bc895d9239Ryan Lortie 728db8642a56c0436aeb730ead593140bc01b82d4acEmmanuele Bassi return retval; 729db8642a56c0436aeb730ead593140bc01b82d4acEmmanuele Bassi} 730db8642a56c0436aeb730ead593140bc01b82d4acEmmanuele Bassi 731db8642a56c0436aeb730ead593140bc01b82d4acEmmanuele Bassi/** 732db8642a56c0436aeb730ead593140bc01b82d4acEmmanuele Bassi * g_hash_table_get_values: 733db8642a56c0436aeb730ead593140bc01b82d4acEmmanuele Bassi * @hash_table: a #GHashTable 734db8642a56c0436aeb730ead593140bc01b82d4acEmmanuele Bassi * 735db8642a56c0436aeb730ead593140bc01b82d4acEmmanuele Bassi * Retrieves every value inside @hash_table. The returned data is 736db8642a56c0436aeb730ead593140bc01b82d4acEmmanuele Bassi * valid until @hash_table is modified. 737db8642a56c0436aeb730ead593140bc01b82d4acEmmanuele Bassi * 738db8642a56c0436aeb730ead593140bc01b82d4acEmmanuele Bassi * Return value: a #GList containing all the values inside the hash 739db8642a56c0436aeb730ead593140bc01b82d4acEmmanuele Bassi * table. The content of the list is owned by the hash table and 740db8642a56c0436aeb730ead593140bc01b82d4acEmmanuele Bassi * should not be modified or freed. Use g_list_free() when done 741db8642a56c0436aeb730ead593140bc01b82d4acEmmanuele Bassi * using the list. 742db8642a56c0436aeb730ead593140bc01b82d4acEmmanuele Bassi * 743db8642a56c0436aeb730ead593140bc01b82d4acEmmanuele Bassi * Since: 2.14 744db8642a56c0436aeb730ead593140bc01b82d4acEmmanuele Bassi */ 745db8642a56c0436aeb730ead593140bc01b82d4acEmmanuele BassiGList * 746db8642a56c0436aeb730ead593140bc01b82d4acEmmanuele Bassig_hash_table_get_values (GHashTable *hash_table) 747db8642a56c0436aeb730ead593140bc01b82d4acEmmanuele Bassi{ 748db8642a56c0436aeb730ead593140bc01b82d4acEmmanuele Bassi GHashNode *node; 749db8642a56c0436aeb730ead593140bc01b82d4acEmmanuele Bassi gint i; 750db8642a56c0436aeb730ead593140bc01b82d4acEmmanuele Bassi GList *retval; 7518eed88b24e86f16021d94d9b16f7a2bc895d9239Ryan Lortie 752db8642a56c0436aeb730ead593140bc01b82d4acEmmanuele Bassi g_return_val_if_fail (hash_table != NULL, NULL); 7538eed88b24e86f16021d94d9b16f7a2bc895d9239Ryan Lortie 754db8642a56c0436aeb730ead593140bc01b82d4acEmmanuele Bassi retval = NULL; 755db8642a56c0436aeb730ead593140bc01b82d4acEmmanuele Bassi for (i = 0; i < hash_table->size; i++) 756db8642a56c0436aeb730ead593140bc01b82d4acEmmanuele Bassi for (node = hash_table->nodes[i]; node; node = node->next) 757db8642a56c0436aeb730ead593140bc01b82d4acEmmanuele Bassi retval = g_list_prepend (retval, node->value); 7588eed88b24e86f16021d94d9b16f7a2bc895d9239Ryan Lortie 759db8642a56c0436aeb730ead593140bc01b82d4acEmmanuele Bassi return retval; 760db8642a56c0436aeb730ead593140bc01b82d4acEmmanuele Bassi} 761db8642a56c0436aeb730ead593140bc01b82d4acEmmanuele Bassi 7622e0320d57e417f7d1c838d729a99545db2228e9Owen Taylorstatic void 7632e0320d57e417f7d1c838d729a99545db2228e9Owen Taylorg_hash_table_resize (GHashTable *hash_table) 7642e0320d57e417f7d1c838d729a99545db2228e9Owen Taylor{ 7652e0320d57e417f7d1c838d729a99545db2228e9Owen Taylor GHashNode **new_nodes; 7662e0320d57e417f7d1c838d729a99545db2228e9Owen Taylor GHashNode *node; 7672e0320d57e417f7d1c838d729a99545db2228e9Owen Taylor GHashNode *next; 7682e0320d57e417f7d1c838d729a99545db2228e9Owen Taylor guint hash_val; 7692e0320d57e417f7d1c838d729a99545db2228e9Owen Taylor gint new_size; 7702e0320d57e417f7d1c838d729a99545db2228e9Owen Taylor gint i; 7718079eb3456914a03618b92b48f75a71b25331acbOwen Taylor 77273e6da92b298d48e3de9d775b5adc97cbff7b0aaSven Neumann new_size = g_spaced_primes_closest (hash_table->nnodes); 77373e6da92b298d48e3de9d775b5adc97cbff7b0aaSven Neumann new_size = CLAMP (new_size, HASH_TABLE_MIN_SIZE, HASH_TABLE_MAX_SIZE); 7748eed88b24e86f16021d94d9b16f7a2bc895d9239Ryan Lortie 775448e792b0a9b092f9593eaa51e16acd8abe54c76Jeff Garzik new_nodes = g_new0 (GHashNode*, new_size); 7768eed88b24e86f16021d94d9b16f7a2bc895d9239Ryan Lortie 7777519c2338ae484135b44bbb7eb49719aea8c4ca3Lauri Alanko for (i = 0; i < hash_table->size; i++) 7787519c2338ae484135b44bbb7eb49719aea8c4ca3Lauri Alanko for (node = hash_table->nodes[i]; node; node = next) 7797519c2338ae484135b44bbb7eb49719aea8c4ca3Lauri Alanko { 7807519c2338ae484135b44bbb7eb49719aea8c4ca3Lauri Alanko next = node->next; 781448e792b0a9b092f9593eaa51e16acd8abe54c76Jeff Garzik 782e6b78c9af1d6416f93311b98e1e6d802e2fe0617Ryan Lortie hash_val = node->key_hash % new_size; 783448e792b0a9b092f9593eaa51e16acd8abe54c76Jeff Garzik 7847519c2338ae484135b44bbb7eb49719aea8c4ca3Lauri Alanko node->next = new_nodes[hash_val]; 7857519c2338ae484135b44bbb7eb49719aea8c4ca3Lauri Alanko new_nodes[hash_val] = node; 7867519c2338ae484135b44bbb7eb49719aea8c4ca3Lauri Alanko } 7878eed88b24e86f16021d94d9b16f7a2bc895d9239Ryan Lortie 7887519c2338ae484135b44bbb7eb49719aea8c4ca3Lauri Alanko g_free (hash_table->nodes); 7897519c2338ae484135b44bbb7eb49719aea8c4ca3Lauri Alanko hash_table->nodes = new_nodes; 7907519c2338ae484135b44bbb7eb49719aea8c4ca3Lauri Alanko hash_table->size = new_size; 7917519c2338ae484135b44bbb7eb49719aea8c4ca3Lauri Alanko} 7927519c2338ae484135b44bbb7eb49719aea8c4ca3Lauri Alanko 7932e0320d57e417f7d1c838d729a99545db2228e9Owen Taylorstatic GHashNode* 7942e0320d57e417f7d1c838d729a99545db2228e9Owen Taylorg_hash_node_new (gpointer key, 795e6b78c9af1d6416f93311b98e1e6d802e2fe0617Ryan Lortie gpointer value, 796e6b78c9af1d6416f93311b98e1e6d802e2fe0617Ryan Lortie guint key_hash) 7972e0320d57e417f7d1c838d729a99545db2228e9Owen Taylor{ 7980cba1b531d5d28890fa4f48359d4e7adacf2a603Tim Janik GHashNode *hash_node = g_slice_new (GHashNode); 7998eed88b24e86f16021d94d9b16f7a2bc895d9239Ryan Lortie 8002e0320d57e417f7d1c838d729a99545db2228e9Owen Taylor hash_node->key = key; 8012e0320d57e417f7d1c838d729a99545db2228e9Owen Taylor hash_node->value = value; 802e6b78c9af1d6416f93311b98e1e6d802e2fe0617Ryan Lortie hash_node->key_hash = key_hash; 8032e0320d57e417f7d1c838d729a99545db2228e9Owen Taylor hash_node->next = NULL; 8048eed88b24e86f16021d94d9b16f7a2bc895d9239Ryan Lortie 8052e0320d57e417f7d1c838d729a99545db2228e9Owen Taylor return hash_node; 8062e0320d57e417f7d1c838d729a99545db2228e9Owen Taylor} 8072e0320d57e417f7d1c838d729a99545db2228e9Owen Taylor 808608a31b98e1420f487190871ee7312db2643d93dMatthias Clasen#define __G_HASH_C__ 809608a31b98e1420f487190871ee7312db2643d93dMatthias Clasen#include "galiasdef.c" 810