ghash.c revision 8eed88b24e86f16021d94d9b16f7a2bc895d9239
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 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 guint g_hash_table_foreach_remove_or_steal (GHashTable *hash_table, 80a2b269bae3315a2ea772b741fb62f683c1db5770Sven Neumann GHRFunc func, 81a2b269bae3315a2ea772b741fb62f683c1db5770Sven Neumann gpointer user_data, 82a2b269bae3315a2ea772b741fb62f683c1db5770Sven Neumann gboolean notify); 8372ed8191afd8ff124a45285b420625e1342e35cfRyan Lortiestatic void g_hash_table_remove_all_nodes (GHashTable *hash_table, 8472ed8191afd8ff124a45285b420625e1342e35cfRyan Lortie gboolean notify); 852e0320d57e417f7d1c838d729a99545db2228e9Owen Taylor 862e0320d57e417f7d1c838d729a99545db2228e9Owen Taylor 87a2b269bae3315a2ea772b741fb62f683c1db5770Sven Neumann/** 88a2b269bae3315a2ea772b741fb62f683c1db5770Sven Neumann * g_hash_table_new: 89a2b269bae3315a2ea772b741fb62f683c1db5770Sven Neumann * @hash_func: a function to create a hash value from a key. 90a2b269bae3315a2ea772b741fb62f683c1db5770Sven Neumann * Hash values are used to determine where keys are stored within the 918eed88b24e86f16021d94d9b16f7a2bc895d9239Ryan Lortie * #GHashTable data structure. The g_direct_hash(), g_int_hash() and 928eed88b24e86f16021d94d9b16f7a2bc895d9239Ryan Lortie * g_str_hash() functions are provided for some common types of keys. 93a52e2986cd4a2147cfc8d41ae23d98907caaf3a0Matthias Clasen * If hash_func is %NULL, g_direct_hash() is used. 94a2b269bae3315a2ea772b741fb62f683c1db5770Sven Neumann * @key_equal_func: a function to check two keys for equality. This is 95a2b269bae3315a2ea772b741fb62f683c1db5770Sven Neumann * used when looking up keys in the #GHashTable. The g_direct_equal(), 96a2b269bae3315a2ea772b741fb62f683c1db5770Sven Neumann * g_int_equal() and g_str_equal() functions are provided for the most 97a52e2986cd4a2147cfc8d41ae23d98907caaf3a0Matthias Clasen * common types of keys. If @key_equal_func is %NULL, keys are compared 98a2b269bae3315a2ea772b741fb62f683c1db5770Sven Neumann * directly in a similar fashion to g_direct_equal(), but without the 99a2b269bae3315a2ea772b741fb62f683c1db5770Sven Neumann * overhead of a function call. 100a2b269bae3315a2ea772b741fb62f683c1db5770Sven Neumann * 1013e847a090cfd8495add631d43388c461b1a85716Tim Janik * Creates a new #GHashTable with a reference count of 1. 1028eed88b24e86f16021d94d9b16f7a2bc895d9239Ryan Lortie * 103a2b269bae3315a2ea772b741fb62f683c1db5770Sven Neumann * Return value: a new #GHashTable. 104a2b269bae3315a2ea772b741fb62f683c1db5770Sven Neumann **/ 1052e0320d57e417f7d1c838d729a99545db2228e9Owen TaylorGHashTable* 1062e0320d57e417f7d1c838d729a99545db2228e9Owen Taylorg_hash_table_new (GHashFunc hash_func, 1078eed88b24e86f16021d94d9b16f7a2bc895d9239Ryan Lortie GEqualFunc key_equal_func) 1082e0320d57e417f7d1c838d729a99545db2228e9Owen Taylor{ 109a2b269bae3315a2ea772b741fb62f683c1db5770Sven Neumann return g_hash_table_new_full (hash_func, key_equal_func, NULL, NULL); 110a2b269bae3315a2ea772b741fb62f683c1db5770Sven Neumann} 111a2b269bae3315a2ea772b741fb62f683c1db5770Sven Neumann 112a2b269bae3315a2ea772b741fb62f683c1db5770Sven Neumann 113a2b269bae3315a2ea772b741fb62f683c1db5770Sven Neumann/** 114a2b269bae3315a2ea772b741fb62f683c1db5770Sven Neumann * g_hash_table_new_full: 115a2b269bae3315a2ea772b741fb62f683c1db5770Sven Neumann * @hash_func: a function to create a hash value from a key. 116a2b269bae3315a2ea772b741fb62f683c1db5770Sven Neumann * @key_equal_func: a function to check two keys for equality. 1178eed88b24e86f16021d94d9b16f7a2bc895d9239Ryan Lortie * @key_destroy_func: a function to free the memory allocated for the key 1188eed88b24e86f16021d94d9b16f7a2bc895d9239Ryan Lortie * used when removing the entry from the #GHashTable or %NULL if you 119d18b364dd774087555f036fec2c6ec9fe838368fSven Neumann * don't want to supply such a function. 1208eed88b24e86f16021d94d9b16f7a2bc895d9239Ryan Lortie * @value_destroy_func: a function to free the memory allocated for the 1218eed88b24e86f16021d94d9b16f7a2bc895d9239Ryan Lortie * value used when removing the entry from the #GHashTable or %NULL if 122a2b269bae3315a2ea772b741fb62f683c1db5770Sven Neumann * you don't want to supply such a function. 1238eed88b24e86f16021d94d9b16f7a2bc895d9239Ryan Lortie * 1243e847a090cfd8495add631d43388c461b1a85716Tim Janik * Creates a new #GHashTable like g_hash_table_new() with a reference count 1253e847a090cfd8495add631d43388c461b1a85716Tim Janik * of 1 and allows to specify functions to free the memory allocated for the 1263e847a090cfd8495add631d43388c461b1a85716Tim Janik * key and value that get called when removing the entry from the #GHashTable. 1278eed88b24e86f16021d94d9b16f7a2bc895d9239Ryan Lortie * 128a2b269bae3315a2ea772b741fb62f683c1db5770Sven Neumann * Return value: a new #GHashTable. 129a2b269bae3315a2ea772b741fb62f683c1db5770Sven Neumann **/ 130a2b269bae3315a2ea772b741fb62f683c1db5770Sven NeumannGHashTable* 131a2b269bae3315a2ea772b741fb62f683c1db5770Sven Neumanng_hash_table_new_full (GHashFunc hash_func, 1328eed88b24e86f16021d94d9b16f7a2bc895d9239Ryan Lortie GEqualFunc key_equal_func, 1338eed88b24e86f16021d94d9b16f7a2bc895d9239Ryan Lortie GDestroyNotify key_destroy_func, 1348eed88b24e86f16021d94d9b16f7a2bc895d9239Ryan Lortie GDestroyNotify value_destroy_func) 135a2b269bae3315a2ea772b741fb62f683c1db5770Sven Neumann{ 1367519c2338ae484135b44bbb7eb49719aea8c4ca3Lauri Alanko GHashTable *hash_table; 1378eed88b24e86f16021d94d9b16f7a2bc895d9239Ryan Lortie 1380cba1b531d5d28890fa4f48359d4e7adacf2a603Tim Janik hash_table = g_slice_new (GHashTable); 139a2b269bae3315a2ea772b741fb62f683c1db5770Sven Neumann hash_table->size = HASH_TABLE_MIN_SIZE; 140a2b269bae3315a2ea772b741fb62f683c1db5770Sven Neumann hash_table->nnodes = 0; 141a2b269bae3315a2ea772b741fb62f683c1db5770Sven Neumann hash_table->hash_func = hash_func ? hash_func : g_direct_hash; 142a2b269bae3315a2ea772b741fb62f683c1db5770Sven Neumann hash_table->key_equal_func = key_equal_func; 1433e847a090cfd8495add631d43388c461b1a85716Tim Janik hash_table->ref_count = 1; 144a2b269bae3315a2ea772b741fb62f683c1db5770Sven Neumann hash_table->key_destroy_func = key_destroy_func; 145a2b269bae3315a2ea772b741fb62f683c1db5770Sven Neumann hash_table->value_destroy_func = value_destroy_func; 1463e847a090cfd8495add631d43388c461b1a85716Tim Janik hash_table->nodes = g_new0 (GHashNode*, hash_table->size); 1478eed88b24e86f16021d94d9b16f7a2bc895d9239Ryan Lortie 1487519c2338ae484135b44bbb7eb49719aea8c4ca3Lauri Alanko return hash_table; 1492e0320d57e417f7d1c838d729a99545db2228e9Owen Taylor} 1502e0320d57e417f7d1c838d729a99545db2228e9Owen Taylor 1513e847a090cfd8495add631d43388c461b1a85716Tim Janik 1523e847a090cfd8495add631d43388c461b1a85716Tim Janik/** 1533e847a090cfd8495add631d43388c461b1a85716Tim Janik * g_hash_table_ref: 1543e847a090cfd8495add631d43388c461b1a85716Tim Janik * @hash_table: a valid #GHashTable. 1558eed88b24e86f16021d94d9b16f7a2bc895d9239Ryan Lortie * 1563e847a090cfd8495add631d43388c461b1a85716Tim Janik * Atomically increments the reference count of @hash_table by one. 1573e847a090cfd8495add631d43388c461b1a85716Tim Janik * This function is MT-safe and may be called from any thread. 1588eed88b24e86f16021d94d9b16f7a2bc895d9239Ryan Lortie * 1593e847a090cfd8495add631d43388c461b1a85716Tim Janik * Return value: the passed in #GHashTable. 1608eed88b24e86f16021d94d9b16f7a2bc895d9239Ryan Lortie * 161fe749cbd3b058512e36d79203cac3c00c7f40571Matthias Clasen * Since: 2.10 1623e847a090cfd8495add631d43388c461b1a85716Tim Janik **/ 1633e847a090cfd8495add631d43388c461b1a85716Tim JanikGHashTable* 1643e847a090cfd8495add631d43388c461b1a85716Tim Janikg_hash_table_ref (GHashTable *hash_table) 1653e847a090cfd8495add631d43388c461b1a85716Tim Janik{ 1663e847a090cfd8495add631d43388c461b1a85716Tim Janik g_return_val_if_fail (hash_table != NULL, NULL); 1673e847a090cfd8495add631d43388c461b1a85716Tim Janik g_return_val_if_fail (hash_table->ref_count > 0, hash_table); 1683e847a090cfd8495add631d43388c461b1a85716Tim Janik 1693e847a090cfd8495add631d43388c461b1a85716Tim Janik g_atomic_int_add (&hash_table->ref_count, 1); 1703e847a090cfd8495add631d43388c461b1a85716Tim Janik return hash_table; 1713e847a090cfd8495add631d43388c461b1a85716Tim Janik} 1723e847a090cfd8495add631d43388c461b1a85716Tim Janik 1733e847a090cfd8495add631d43388c461b1a85716Tim Janik/** 1743e847a090cfd8495add631d43388c461b1a85716Tim Janik * g_hash_table_unref: 1753e847a090cfd8495add631d43388c461b1a85716Tim Janik * @hash_table: a valid #GHashTable. 1768eed88b24e86f16021d94d9b16f7a2bc895d9239Ryan Lortie * 1773e847a090cfd8495add631d43388c461b1a85716Tim Janik * Atomically decrements the reference count of @hash_table by one. 1783e847a090cfd8495add631d43388c461b1a85716Tim Janik * If the reference count drops to 0, all keys and values will be 1793e847a090cfd8495add631d43388c461b1a85716Tim Janik * destroyed, and all memory allocated by the hash table is released. 1803e847a090cfd8495add631d43388c461b1a85716Tim Janik * This function is MT-safe and may be called from any thread. 1818eed88b24e86f16021d94d9b16f7a2bc895d9239Ryan Lortie * 182fe749cbd3b058512e36d79203cac3c00c7f40571Matthias Clasen * Since: 2.10 1833e847a090cfd8495add631d43388c461b1a85716Tim Janik **/ 1843e847a090cfd8495add631d43388c461b1a85716Tim Janikvoid 1853e847a090cfd8495add631d43388c461b1a85716Tim Janikg_hash_table_unref (GHashTable *hash_table) 1863e847a090cfd8495add631d43388c461b1a85716Tim Janik{ 1873e847a090cfd8495add631d43388c461b1a85716Tim Janik g_return_if_fail (hash_table != NULL); 1883e847a090cfd8495add631d43388c461b1a85716Tim Janik g_return_if_fail (hash_table->ref_count > 0); 1893e847a090cfd8495add631d43388c461b1a85716Tim Janik 1903e847a090cfd8495add631d43388c461b1a85716Tim Janik if (g_atomic_int_exchange_and_add (&hash_table->ref_count, -1) - 1 == 0) 1913e847a090cfd8495add631d43388c461b1a85716Tim Janik { 19272ed8191afd8ff124a45285b420625e1342e35cfRyan Lortie g_hash_table_remove_all_nodes (hash_table, FALSE); 1933e847a090cfd8495add631d43388c461b1a85716Tim Janik g_free (hash_table->nodes); 1943e847a090cfd8495add631d43388c461b1a85716Tim Janik g_slice_free (GHashTable, hash_table); 1953e847a090cfd8495add631d43388c461b1a85716Tim Janik } 1963e847a090cfd8495add631d43388c461b1a85716Tim Janik} 1973e847a090cfd8495add631d43388c461b1a85716Tim Janik 198a2b269bae3315a2ea772b741fb62f683c1db5770Sven Neumann/** 199a2b269bae3315a2ea772b741fb62f683c1db5770Sven Neumann * g_hash_table_destroy: 200a2b269bae3315a2ea772b741fb62f683c1db5770Sven Neumann * @hash_table: a #GHashTable. 2018eed88b24e86f16021d94d9b16f7a2bc895d9239Ryan Lortie * 20224dec3cd490fa4dc057a0186c6b870160022268eMorten Welinder * Destroys all keys and values in the #GHashTable and decrements its 2033e847a090cfd8495add631d43388c461b1a85716Tim Janik * reference count by 1. If keys and/or values are dynamically allocated, 2043e847a090cfd8495add631d43388c461b1a85716Tim Janik * you should either free them first or create the #GHashTable with destroy 2053e847a090cfd8495add631d43388c461b1a85716Tim Janik * notifiers using g_hash_table_new_full(). In the latter case the destroy 2063e847a090cfd8495add631d43388c461b1a85716Tim Janik * functions you supplied will be called on all keys and values during the 2073e847a090cfd8495add631d43388c461b1a85716Tim Janik * destruction phase. 208a2b269bae3315a2ea772b741fb62f683c1db5770Sven Neumann **/ 2092e0320d57e417f7d1c838d729a99545db2228e9Owen Taylorvoid 2102e0320d57e417f7d1c838d729a99545db2228e9Owen Taylorg_hash_table_destroy (GHashTable *hash_table) 2112e0320d57e417f7d1c838d729a99545db2228e9Owen Taylor{ 2122d68cbbb7d37d3f265bf1087e6ddedcc58bc62beTim Janik g_return_if_fail (hash_table != NULL); 2133e847a090cfd8495add631d43388c461b1a85716Tim Janik g_return_if_fail (hash_table->ref_count > 0); 2148eed88b24e86f16021d94d9b16f7a2bc895d9239Ryan Lortie 215a5b4b8bfb18838454d99bdee60294da07e5ef0d2Matthias Clasen g_hash_table_remove_all (hash_table); 2163e847a090cfd8495add631d43388c461b1a85716Tim Janik g_hash_table_unref (hash_table); 2172e0320d57e417f7d1c838d729a99545db2228e9Owen Taylor} 2182e0320d57e417f7d1c838d729a99545db2228e9Owen Taylor 219d5492a983cfa048658af8b03f833ddb3c0cf355eESTstatic inline GHashNode** 2208eed88b24e86f16021d94d9b16f7a2bc895d9239Ryan Lortieg_hash_table_lookup_node (GHashTable *hash_table, 2218eed88b24e86f16021d94d9b16f7a2bc895d9239Ryan Lortie gconstpointer key, 2228eed88b24e86f16021d94d9b16f7a2bc895d9239Ryan Lortie guint *hash_return) 2232e0320d57e417f7d1c838d729a99545db2228e9Owen Taylor{ 224d5492a983cfa048658af8b03f833ddb3c0cf355eEST GHashNode **node; 225e6b78c9af1d6416f93311b98e1e6d802e2fe0617Ryan Lortie guint hash_value; 226e6b78c9af1d6416f93311b98e1e6d802e2fe0617Ryan Lortie 227e6b78c9af1d6416f93311b98e1e6d802e2fe0617Ryan Lortie hash_value = (* hash_table->hash_func) (key); 228e6b78c9af1d6416f93311b98e1e6d802e2fe0617Ryan Lortie node = &hash_table->nodes[hash_value % hash_table->size]; 2298eed88b24e86f16021d94d9b16f7a2bc895d9239Ryan Lortie 230e6b78c9af1d6416f93311b98e1e6d802e2fe0617Ryan Lortie if (hash_return) 231e6b78c9af1d6416f93311b98e1e6d802e2fe0617Ryan Lortie *hash_return = hash_value; 2328eed88b24e86f16021d94d9b16f7a2bc895d9239Ryan Lortie 2332d68cbbb7d37d3f265bf1087e6ddedcc58bc62beTim Janik /* Hash table lookup needs to be fast. 2342d68cbbb7d37d3f265bf1087e6ddedcc58bc62beTim Janik * We therefore remove the extra conditional of testing 235267b6813703e24ef60d0e8ba42557c414f9dd52eSebastian Wilhelmi * whether to call the key_equal_func or not from 2362d68cbbb7d37d3f265bf1087e6ddedcc58bc62beTim Janik * the inner loop. 237e6b78c9af1d6416f93311b98e1e6d802e2fe0617Ryan Lortie * 238e6b78c9af1d6416f93311b98e1e6d802e2fe0617Ryan Lortie * Additional optimisation: first check if our full hash 239e6b78c9af1d6416f93311b98e1e6d802e2fe0617Ryan Lortie * values are equal so we can avoid calling the full-blown 240e6b78c9af1d6416f93311b98e1e6d802e2fe0617Ryan Lortie * key equality function in most cases. 2412d68cbbb7d37d3f265bf1087e6ddedcc58bc62beTim Janik */ 242267b6813703e24ef60d0e8ba42557c414f9dd52eSebastian Wilhelmi if (hash_table->key_equal_func) 243e6b78c9af1d6416f93311b98e1e6d802e2fe0617Ryan Lortie while (*node && (((*node)->key_hash != hash_value) || 244e6b78c9af1d6416f93311b98e1e6d802e2fe0617Ryan Lortie !(*hash_table->key_equal_func) ((*node)->key, key))) 245d5492a983cfa048658af8b03f833ddb3c0cf355eEST node = &(*node)->next; 2462d68cbbb7d37d3f265bf1087e6ddedcc58bc62beTim Janik else 247d5492a983cfa048658af8b03f833ddb3c0cf355eEST while (*node && (*node)->key != key) 248d5492a983cfa048658af8b03f833ddb3c0cf355eEST node = &(*node)->next; 249e6b78c9af1d6416f93311b98e1e6d802e2fe0617Ryan Lortie 2502d68cbbb7d37d3f265bf1087e6ddedcc58bc62beTim Janik return node; 2512d68cbbb7d37d3f265bf1087e6ddedcc58bc62beTim Janik} 2522e0320d57e417f7d1c838d729a99545db2228e9Owen Taylor 253a2b269bae3315a2ea772b741fb62f683c1db5770Sven Neumann/** 254a2b269bae3315a2ea772b741fb62f683c1db5770Sven Neumann * g_hash_table_lookup: 255a2b269bae3315a2ea772b741fb62f683c1db5770Sven Neumann * @hash_table: a #GHashTable. 256a2b269bae3315a2ea772b741fb62f683c1db5770Sven Neumann * @key: the key to look up. 2578eed88b24e86f16021d94d9b16f7a2bc895d9239Ryan Lortie * 258fd92ac8f5280ccb936a534a14f5c9cbdb24302e5Matthias Clasen * Looks up a key in a #GHashTable. Note that this function cannot 259fd92ac8f5280ccb936a534a14f5c9cbdb24302e5Matthias Clasen * distinguish between a key that is not present and one which is present 260fd92ac8f5280ccb936a534a14f5c9cbdb24302e5Matthias Clasen * and has the value %NULL. If you need this distinction, use 261fd92ac8f5280ccb936a534a14f5c9cbdb24302e5Matthias Clasen * g_hash_table_lookup_extended(). 2628eed88b24e86f16021d94d9b16f7a2bc895d9239Ryan Lortie * 263a52e2986cd4a2147cfc8d41ae23d98907caaf3a0Matthias Clasen * Return value: the associated value, or %NULL if the key is not found. 264a2b269bae3315a2ea772b741fb62f683c1db5770Sven Neumann **/ 2652d68cbbb7d37d3f265bf1087e6ddedcc58bc62beTim Janikgpointer 2668eed88b24e86f16021d94d9b16f7a2bc895d9239Ryan Lortieg_hash_table_lookup (GHashTable *hash_table, 2678eed88b24e86f16021d94d9b16f7a2bc895d9239Ryan Lortie gconstpointer key) 2682d68cbbb7d37d3f265bf1087e6ddedcc58bc62beTim Janik{ 2692d68cbbb7d37d3f265bf1087e6ddedcc58bc62beTim Janik GHashNode *node; 2708eed88b24e86f16021d94d9b16f7a2bc895d9239Ryan Lortie 2712d68cbbb7d37d3f265bf1087e6ddedcc58bc62beTim Janik g_return_val_if_fail (hash_table != NULL, NULL); 2728eed88b24e86f16021d94d9b16f7a2bc895d9239Ryan Lortie 273e6b78c9af1d6416f93311b98e1e6d802e2fe0617Ryan Lortie node = *g_hash_table_lookup_node (hash_table, key, NULL); 2748eed88b24e86f16021d94d9b16f7a2bc895d9239Ryan Lortie 2752d68cbbb7d37d3f265bf1087e6ddedcc58bc62beTim Janik return node ? node->value : NULL; 2762d68cbbb7d37d3f265bf1087e6ddedcc58bc62beTim Janik} 2777401460a60504dad7b77219d0ba3d93112e12444Manish Singh 278a2b269bae3315a2ea772b741fb62f683c1db5770Sven Neumann/** 279a2b269bae3315a2ea772b741fb62f683c1db5770Sven Neumann * g_hash_table_lookup_extended: 280a2b269bae3315a2ea772b741fb62f683c1db5770Sven Neumann * @hash_table: a #GHashTable. 281a2b269bae3315a2ea772b741fb62f683c1db5770Sven Neumann * @lookup_key: the key to look up. 282a2b269bae3315a2ea772b741fb62f683c1db5770Sven Neumann * @orig_key: returns the original key. 283a2b269bae3315a2ea772b741fb62f683c1db5770Sven Neumann * @value: returns the value associated with the key. 2848eed88b24e86f16021d94d9b16f7a2bc895d9239Ryan Lortie * 285a2b269bae3315a2ea772b741fb62f683c1db5770Sven Neumann * Looks up a key in the #GHashTable, returning the original key and the 2868eed88b24e86f16021d94d9b16f7a2bc895d9239Ryan Lortie * associated value and a #gboolean which is %TRUE if the key was found. This 2878eed88b24e86f16021d94d9b16f7a2bc895d9239Ryan Lortie * is useful if you need to free the memory allocated for the original key, 288a2b269bae3315a2ea772b741fb62f683c1db5770Sven Neumann * for example before calling g_hash_table_remove(). 2898eed88b24e86f16021d94d9b16f7a2bc895d9239Ryan Lortie * 2903fa33317b7e9866793ce1ea32d069e8c9270caa2Matthias Clasen * Return value: %TRUE if the key was found in the #GHashTable. 291a2b269bae3315a2ea772b741fb62f683c1db5770Sven Neumann **/ 292a2b269bae3315a2ea772b741fb62f683c1db5770Sven Neumanngboolean 293a2b269bae3315a2ea772b741fb62f683c1db5770Sven Neumanng_hash_table_lookup_extended (GHashTable *hash_table, 2948eed88b24e86f16021d94d9b16f7a2bc895d9239Ryan Lortie gconstpointer lookup_key, 2958eed88b24e86f16021d94d9b16f7a2bc895d9239Ryan Lortie gpointer *orig_key, 2968eed88b24e86f16021d94d9b16f7a2bc895d9239Ryan Lortie gpointer *value) 297a2b269bae3315a2ea772b741fb62f683c1db5770Sven Neumann{ 298a2b269bae3315a2ea772b741fb62f683c1db5770Sven Neumann GHashNode *node; 2998eed88b24e86f16021d94d9b16f7a2bc895d9239Ryan Lortie 300a2b269bae3315a2ea772b741fb62f683c1db5770Sven Neumann g_return_val_if_fail (hash_table != NULL, FALSE); 3018eed88b24e86f16021d94d9b16f7a2bc895d9239Ryan Lortie 302e6b78c9af1d6416f93311b98e1e6d802e2fe0617Ryan Lortie node = *g_hash_table_lookup_node (hash_table, lookup_key, NULL); 3038eed88b24e86f16021d94d9b16f7a2bc895d9239Ryan Lortie 304a2b269bae3315a2ea772b741fb62f683c1db5770Sven Neumann if (node) 305a2b269bae3315a2ea772b741fb62f683c1db5770Sven Neumann { 306a2b269bae3315a2ea772b741fb62f683c1db5770Sven Neumann if (orig_key) 3078eed88b24e86f16021d94d9b16f7a2bc895d9239Ryan Lortie *orig_key = node->key; 308a2b269bae3315a2ea772b741fb62f683c1db5770Sven Neumann if (value) 3098eed88b24e86f16021d94d9b16f7a2bc895d9239Ryan Lortie *value = node->value; 310a2b269bae3315a2ea772b741fb62f683c1db5770Sven Neumann return TRUE; 311a2b269bae3315a2ea772b741fb62f683c1db5770Sven Neumann } 312a2b269bae3315a2ea772b741fb62f683c1db5770Sven Neumann else 313a2b269bae3315a2ea772b741fb62f683c1db5770Sven Neumann return FALSE; 314a2b269bae3315a2ea772b741fb62f683c1db5770Sven Neumann} 315a2b269bae3315a2ea772b741fb62f683c1db5770Sven Neumann 3160adbacbff90cdab1b96e3409b6d510a00916b586Ryan Lortiestatic void 3170adbacbff90cdab1b96e3409b6d510a00916b586Ryan Lortieg_hash_table_insert_internal (GHashTable *hash_table, 3180adbacbff90cdab1b96e3409b6d510a00916b586Ryan Lortie gpointer key, 3190adbacbff90cdab1b96e3409b6d510a00916b586Ryan Lortie gpointer value, 3200adbacbff90cdab1b96e3409b6d510a00916b586Ryan Lortie gboolean keep_new_key) 3212d68cbbb7d37d3f265bf1087e6ddedcc58bc62beTim Janik{ 322d5492a983cfa048658af8b03f833ddb3c0cf355eEST GHashNode **node; 323e6b78c9af1d6416f93311b98e1e6d802e2fe0617Ryan Lortie guint key_hash; 3248eed88b24e86f16021d94d9b16f7a2bc895d9239Ryan Lortie 3252d68cbbb7d37d3f265bf1087e6ddedcc58bc62beTim Janik g_return_if_fail (hash_table != NULL); 3263e847a090cfd8495add631d43388c461b1a85716Tim Janik g_return_if_fail (hash_table->ref_count > 0); 3278eed88b24e86f16021d94d9b16f7a2bc895d9239Ryan Lortie 328e6b78c9af1d6416f93311b98e1e6d802e2fe0617Ryan Lortie node = g_hash_table_lookup_node (hash_table, key, &key_hash); 3298eed88b24e86f16021d94d9b16f7a2bc895d9239Ryan Lortie 330d5492a983cfa048658af8b03f833ddb3c0cf355eEST if (*node) 3317519c2338ae484135b44bbb7eb49719aea8c4ca3Lauri Alanko { 3325e02b01b210513c19b76731d303a7256d2db273cRyan Lortie if (keep_new_key) 3330adbacbff90cdab1b96e3409b6d510a00916b586Ryan Lortie { 3345e02b01b210513c19b76731d303a7256d2db273cRyan Lortie if (hash_table->key_destroy_func) 3350adbacbff90cdab1b96e3409b6d510a00916b586Ryan Lortie hash_table->key_destroy_func ((*node)->key); 3365e02b01b210513c19b76731d303a7256d2db273cRyan Lortie (*node)->key = key; 3375e02b01b210513c19b76731d303a7256d2db273cRyan Lortie } 3385e02b01b210513c19b76731d303a7256d2db273cRyan Lortie else 3395e02b01b210513c19b76731d303a7256d2db273cRyan Lortie { 3405e02b01b210513c19b76731d303a7256d2db273cRyan Lortie if (hash_table->key_destroy_func) 3410adbacbff90cdab1b96e3409b6d510a00916b586Ryan Lortie hash_table->key_destroy_func (key); 3420adbacbff90cdab1b96e3409b6d510a00916b586Ryan Lortie } 3438eed88b24e86f16021d94d9b16f7a2bc895d9239Ryan Lortie 344a2b269bae3315a2ea772b741fb62f683c1db5770Sven Neumann if (hash_table->value_destroy_func) 3458eed88b24e86f16021d94d9b16f7a2bc895d9239Ryan Lortie hash_table->value_destroy_func ((*node)->value); 346a2b269bae3315a2ea772b741fb62f683c1db5770Sven Neumann 347a2b269bae3315a2ea772b741fb62f683c1db5770Sven Neumann (*node)->value = value; 348a2b269bae3315a2ea772b741fb62f683c1db5770Sven Neumann } 349a2b269bae3315a2ea772b741fb62f683c1db5770Sven Neumann else 350a2b269bae3315a2ea772b741fb62f683c1db5770Sven Neumann { 351e6b78c9af1d6416f93311b98e1e6d802e2fe0617Ryan Lortie *node = g_hash_node_new (key, value, key_hash); 352a2b269bae3315a2ea772b741fb62f683c1db5770Sven Neumann hash_table->nnodes++; 3538079eb3456914a03618b92b48f75a71b25331acbOwen Taylor G_HASH_TABLE_RESIZE (hash_table); 354a2b269bae3315a2ea772b741fb62f683c1db5770Sven Neumann } 355a2b269bae3315a2ea772b741fb62f683c1db5770Sven Neumann} 356a2b269bae3315a2ea772b741fb62f683c1db5770Sven Neumann 357a2b269bae3315a2ea772b741fb62f683c1db5770Sven Neumann/** 3580adbacbff90cdab1b96e3409b6d510a00916b586Ryan Lortie * g_hash_table_insert: 3590adbacbff90cdab1b96e3409b6d510a00916b586Ryan Lortie * @hash_table: a #GHashTable. 3600adbacbff90cdab1b96e3409b6d510a00916b586Ryan Lortie * @key: a key to insert. 3610adbacbff90cdab1b96e3409b6d510a00916b586Ryan Lortie * @value: the value to associate with the key. 3628eed88b24e86f16021d94d9b16f7a2bc895d9239Ryan Lortie * 3630adbacbff90cdab1b96e3409b6d510a00916b586Ryan Lortie * Inserts a new key and value into a #GHashTable. 3648eed88b24e86f16021d94d9b16f7a2bc895d9239Ryan Lortie * 3650adbacbff90cdab1b96e3409b6d510a00916b586Ryan Lortie * If the key already exists in the #GHashTable its current value is replaced 3668eed88b24e86f16021d94d9b16f7a2bc895d9239Ryan Lortie * with the new value. If you supplied a @value_destroy_func when creating the 3670adbacbff90cdab1b96e3409b6d510a00916b586Ryan Lortie * #GHashTable, the old value is freed using that function. If you supplied 3688eed88b24e86f16021d94d9b16f7a2bc895d9239Ryan Lortie * a @key_destroy_func when creating the #GHashTable, the passed key is freed 3690adbacbff90cdab1b96e3409b6d510a00916b586Ryan Lortie * using that function. 3700adbacbff90cdab1b96e3409b6d510a00916b586Ryan Lortie **/ 3710adbacbff90cdab1b96e3409b6d510a00916b586Ryan Lortievoid 3720adbacbff90cdab1b96e3409b6d510a00916b586Ryan Lortieg_hash_table_insert (GHashTable *hash_table, 3738eed88b24e86f16021d94d9b16f7a2bc895d9239Ryan Lortie gpointer key, 3748eed88b24e86f16021d94d9b16f7a2bc895d9239Ryan Lortie gpointer value) 3750adbacbff90cdab1b96e3409b6d510a00916b586Ryan Lortie{ 3760adbacbff90cdab1b96e3409b6d510a00916b586Ryan Lortie return g_hash_table_insert_internal (hash_table, key, value, FALSE); 3770adbacbff90cdab1b96e3409b6d510a00916b586Ryan Lortie} 3780adbacbff90cdab1b96e3409b6d510a00916b586Ryan Lortie 3790adbacbff90cdab1b96e3409b6d510a00916b586Ryan Lortie/** 380a2b269bae3315a2ea772b741fb62f683c1db5770Sven Neumann * g_hash_table_replace: 381a2b269bae3315a2ea772b741fb62f683c1db5770Sven Neumann * @hash_table: a #GHashTable. 382a2b269bae3315a2ea772b741fb62f683c1db5770Sven Neumann * @key: a key to insert. 383a2b269bae3315a2ea772b741fb62f683c1db5770Sven Neumann * @value: the value to associate with the key. 3848eed88b24e86f16021d94d9b16f7a2bc895d9239Ryan Lortie * 3858eed88b24e86f16021d94d9b16f7a2bc895d9239Ryan Lortie * Inserts a new key and value into a #GHashTable similar to 3868eed88b24e86f16021d94d9b16f7a2bc895d9239Ryan Lortie * g_hash_table_insert(). The difference is that if the key already exists 3878eed88b24e86f16021d94d9b16f7a2bc895d9239Ryan Lortie * in the #GHashTable, it gets replaced by the new key. If you supplied a 3888eed88b24e86f16021d94d9b16f7a2bc895d9239Ryan Lortie * @value_destroy_func when creating the #GHashTable, the old value is freed 3898eed88b24e86f16021d94d9b16f7a2bc895d9239Ryan Lortie * using that function. If you supplied a @key_destroy_func when creating the 3908eed88b24e86f16021d94d9b16f7a2bc895d9239Ryan Lortie * #GHashTable, the old key is freed using that function. 391a2b269bae3315a2ea772b741fb62f683c1db5770Sven Neumann **/ 392a2b269bae3315a2ea772b741fb62f683c1db5770Sven Neumannvoid 393a2b269bae3315a2ea772b741fb62f683c1db5770Sven Neumanng_hash_table_replace (GHashTable *hash_table, 3948eed88b24e86f16021d94d9b16f7a2bc895d9239Ryan Lortie gpointer key, 3958eed88b24e86f16021d94d9b16f7a2bc895d9239Ryan Lortie gpointer value) 396a2b269bae3315a2ea772b741fb62f683c1db5770Sven Neumann{ 3970adbacbff90cdab1b96e3409b6d510a00916b586Ryan Lortie return g_hash_table_insert_internal (hash_table, key, value, TRUE); 3982e0320d57e417f7d1c838d729a99545db2228e9Owen Taylor} 3992e0320d57e417f7d1c838d729a99545db2228e9Owen Taylor 400e9010a86f763e6b7cb1fd5520985c929339f5523Ryan Lortiestatic void 401e9010a86f763e6b7cb1fd5520985c929339f5523Ryan Lortieg_hash_table_remove_node (GHashTable *hash_table, 402e9010a86f763e6b7cb1fd5520985c929339f5523Ryan Lortie GHashNode ***node_ptr_ptr, 403e9010a86f763e6b7cb1fd5520985c929339f5523Ryan Lortie gboolean notify) 404e9010a86f763e6b7cb1fd5520985c929339f5523Ryan Lortie{ 405e9010a86f763e6b7cb1fd5520985c929339f5523Ryan Lortie GHashNode **node_ptr, *node; 406e9010a86f763e6b7cb1fd5520985c929339f5523Ryan Lortie 407e9010a86f763e6b7cb1fd5520985c929339f5523Ryan Lortie node_ptr = *node_ptr_ptr; 408e9010a86f763e6b7cb1fd5520985c929339f5523Ryan Lortie node = *node_ptr; 409e9010a86f763e6b7cb1fd5520985c929339f5523Ryan Lortie 410e9010a86f763e6b7cb1fd5520985c929339f5523Ryan Lortie *node_ptr = node->next; 411e9010a86f763e6b7cb1fd5520985c929339f5523Ryan Lortie 41272ed8191afd8ff124a45285b420625e1342e35cfRyan Lortie if (notify && hash_table->key_destroy_func) 41372ed8191afd8ff124a45285b420625e1342e35cfRyan Lortie hash_table->key_destroy_func (node->key); 41472ed8191afd8ff124a45285b420625e1342e35cfRyan Lortie 41572ed8191afd8ff124a45285b420625e1342e35cfRyan Lortie if (notify && hash_table->value_destroy_func) 41672ed8191afd8ff124a45285b420625e1342e35cfRyan Lortie hash_table->value_destroy_func (node->value); 41772ed8191afd8ff124a45285b420625e1342e35cfRyan Lortie 41872ed8191afd8ff124a45285b420625e1342e35cfRyan Lortie g_slice_free (GHashNode, node); 419e9010a86f763e6b7cb1fd5520985c929339f5523Ryan Lortie 420e9010a86f763e6b7cb1fd5520985c929339f5523Ryan Lortie hash_table->nnodes--; 421e9010a86f763e6b7cb1fd5520985c929339f5523Ryan Lortie} 422e9010a86f763e6b7cb1fd5520985c929339f5523Ryan Lortie 42372ed8191afd8ff124a45285b420625e1342e35cfRyan Lortiestatic void 42472ed8191afd8ff124a45285b420625e1342e35cfRyan Lortieg_hash_table_remove_all_nodes (GHashTable *hash_table, 42572ed8191afd8ff124a45285b420625e1342e35cfRyan Lortie gboolean notify) 42672ed8191afd8ff124a45285b420625e1342e35cfRyan Lortie{ 42772ed8191afd8ff124a45285b420625e1342e35cfRyan Lortie GHashNode **node_ptr; 42872ed8191afd8ff124a45285b420625e1342e35cfRyan Lortie int i; 42972ed8191afd8ff124a45285b420625e1342e35cfRyan Lortie 43072ed8191afd8ff124a45285b420625e1342e35cfRyan Lortie for (i = 0; i < hash_table->size; i++) 43172ed8191afd8ff124a45285b420625e1342e35cfRyan Lortie for (node_ptr = &hash_table->nodes[i]; *node_ptr != NULL;) 43272ed8191afd8ff124a45285b420625e1342e35cfRyan Lortie g_hash_table_remove_node (hash_table, &node_ptr, notify); 43372ed8191afd8ff124a45285b420625e1342e35cfRyan Lortie 43472ed8191afd8ff124a45285b420625e1342e35cfRyan Lortie hash_table->nnodes = 0; 43572ed8191afd8ff124a45285b420625e1342e35cfRyan Lortie} 43672ed8191afd8ff124a45285b420625e1342e35cfRyan Lortie 437e9010a86f763e6b7cb1fd5520985c929339f5523Ryan Lortiestatic gboolean 438e9010a86f763e6b7cb1fd5520985c929339f5523Ryan Lortieg_hash_table_remove_internal (GHashTable *hash_table, 439e9010a86f763e6b7cb1fd5520985c929339f5523Ryan Lortie gconstpointer key, 440e9010a86f763e6b7cb1fd5520985c929339f5523Ryan Lortie gboolean notify) 441e9010a86f763e6b7cb1fd5520985c929339f5523Ryan Lortie{ 442e9010a86f763e6b7cb1fd5520985c929339f5523Ryan Lortie GHashNode **node_ptr; 4438eed88b24e86f16021d94d9b16f7a2bc895d9239Ryan Lortie 444e9010a86f763e6b7cb1fd5520985c929339f5523Ryan Lortie g_return_val_if_fail (hash_table != NULL, FALSE); 4458eed88b24e86f16021d94d9b16f7a2bc895d9239Ryan Lortie 446e9010a86f763e6b7cb1fd5520985c929339f5523Ryan Lortie node_ptr = g_hash_table_lookup_node (hash_table, key, NULL); 447e9010a86f763e6b7cb1fd5520985c929339f5523Ryan Lortie if (*node_ptr == NULL) 448e9010a86f763e6b7cb1fd5520985c929339f5523Ryan Lortie return FALSE; 449e9010a86f763e6b7cb1fd5520985c929339f5523Ryan Lortie 45072ed8191afd8ff124a45285b420625e1342e35cfRyan Lortie g_hash_table_remove_node (hash_table, &node_ptr, notify); 451e9010a86f763e6b7cb1fd5520985c929339f5523Ryan Lortie G_HASH_TABLE_RESIZE (hash_table); 452e9010a86f763e6b7cb1fd5520985c929339f5523Ryan Lortie 453e9010a86f763e6b7cb1fd5520985c929339f5523Ryan Lortie return TRUE; 454e9010a86f763e6b7cb1fd5520985c929339f5523Ryan Lortie} 455e9010a86f763e6b7cb1fd5520985c929339f5523Ryan Lortie 456a2b269bae3315a2ea772b741fb62f683c1db5770Sven Neumann/** 457a2b269bae3315a2ea772b741fb62f683c1db5770Sven Neumann * g_hash_table_remove: 458a2b269bae3315a2ea772b741fb62f683c1db5770Sven Neumann * @hash_table: a #GHashTable. 459a2b269bae3315a2ea772b741fb62f683c1db5770Sven Neumann * @key: the key to remove. 4608eed88b24e86f16021d94d9b16f7a2bc895d9239Ryan Lortie * 461a2b269bae3315a2ea772b741fb62f683c1db5770Sven Neumann * Removes a key and its associated value from a #GHashTable. 462a2b269bae3315a2ea772b741fb62f683c1db5770Sven Neumann * 463a2b269bae3315a2ea772b741fb62f683c1db5770Sven Neumann * If the #GHashTable was created using g_hash_table_new_full(), the 464a52e2986cd4a2147cfc8d41ae23d98907caaf3a0Matthias Clasen * key and value are freed using the supplied destroy functions, otherwise 4658eed88b24e86f16021d94d9b16f7a2bc895d9239Ryan Lortie * you have to make sure that any dynamically allocated values are freed 466a2b269bae3315a2ea772b741fb62f683c1db5770Sven Neumann * yourself. 4678eed88b24e86f16021d94d9b16f7a2bc895d9239Ryan Lortie * 4683fa33317b7e9866793ce1ea32d069e8c9270caa2Matthias Clasen * Return value: %TRUE if the key was found and removed from the #GHashTable. 469a2b269bae3315a2ea772b741fb62f683c1db5770Sven Neumann **/ 4709a8c33db5cc37bc3c6bd4794a03f4b99a847ff4aTim Janikgboolean 4718eed88b24e86f16021d94d9b16f7a2bc895d9239Ryan Lortieg_hash_table_remove (GHashTable *hash_table, 472e9010a86f763e6b7cb1fd5520985c929339f5523Ryan Lortie gconstpointer key) 4732e0320d57e417f7d1c838d729a99545db2228e9Owen Taylor{ 474e9010a86f763e6b7cb1fd5520985c929339f5523Ryan Lortie return g_hash_table_remove_internal (hash_table, key, TRUE); 4752e0320d57e417f7d1c838d729a99545db2228e9Owen Taylor} 4762e0320d57e417f7d1c838d729a99545db2228e9Owen Taylor 477a2b269bae3315a2ea772b741fb62f683c1db5770Sven Neumann/** 478a5b4b8bfb18838454d99bdee60294da07e5ef0d2Matthias Clasen * g_hash_table_remove_all: 479a5b4b8bfb18838454d99bdee60294da07e5ef0d2Matthias Clasen * @hash_table: a #GHashTable 480a5b4b8bfb18838454d99bdee60294da07e5ef0d2Matthias Clasen * 481a5b4b8bfb18838454d99bdee60294da07e5ef0d2Matthias Clasen * Removes all keys and their associated values from a #GHashTable. 482a5b4b8bfb18838454d99bdee60294da07e5ef0d2Matthias Clasen * 483a5b4b8bfb18838454d99bdee60294da07e5ef0d2Matthias Clasen * If the #GHashTable was created using g_hash_table_new_full(), the keys 484a5b4b8bfb18838454d99bdee60294da07e5ef0d2Matthias Clasen * and values are freed using the supplied destroy functions, otherwise you 485a5b4b8bfb18838454d99bdee60294da07e5ef0d2Matthias Clasen * have to make sure that any dynamically allocated values are freed 486a5b4b8bfb18838454d99bdee60294da07e5ef0d2Matthias Clasen * yourself. 487a5b4b8bfb18838454d99bdee60294da07e5ef0d2Matthias Clasen * 488a5b4b8bfb18838454d99bdee60294da07e5ef0d2Matthias Clasen * Since: 2.12 489a5b4b8bfb18838454d99bdee60294da07e5ef0d2Matthias Clasen **/ 490a5b4b8bfb18838454d99bdee60294da07e5ef0d2Matthias Clasenvoid 491a5b4b8bfb18838454d99bdee60294da07e5ef0d2Matthias Claseng_hash_table_remove_all (GHashTable *hash_table) 492a5b4b8bfb18838454d99bdee60294da07e5ef0d2Matthias Clasen{ 493a5b4b8bfb18838454d99bdee60294da07e5ef0d2Matthias Clasen g_return_if_fail (hash_table != NULL); 494a5b4b8bfb18838454d99bdee60294da07e5ef0d2Matthias Clasen 49572ed8191afd8ff124a45285b420625e1342e35cfRyan Lortie g_hash_table_remove_all_nodes (hash_table, TRUE); 496a5b4b8bfb18838454d99bdee60294da07e5ef0d2Matthias Clasen G_HASH_TABLE_RESIZE (hash_table); 497a5b4b8bfb18838454d99bdee60294da07e5ef0d2Matthias Clasen} 498a5b4b8bfb18838454d99bdee60294da07e5ef0d2Matthias Clasen 499a5b4b8bfb18838454d99bdee60294da07e5ef0d2Matthias Clasen/** 500a2b269bae3315a2ea772b741fb62f683c1db5770Sven Neumann * g_hash_table_steal: 501a2b269bae3315a2ea772b741fb62f683c1db5770Sven Neumann * @hash_table: a #GHashTable. 502a2b269bae3315a2ea772b741fb62f683c1db5770Sven Neumann * @key: the key to remove. 5038eed88b24e86f16021d94d9b16f7a2bc895d9239Ryan Lortie * 504a2b269bae3315a2ea772b741fb62f683c1db5770Sven Neumann * Removes a key and its associated value from a #GHashTable without 505a2b269bae3315a2ea772b741fb62f683c1db5770Sven Neumann * calling the key and value destroy functions. 506a2b269bae3315a2ea772b741fb62f683c1db5770Sven Neumann * 5073fa33317b7e9866793ce1ea32d069e8c9270caa2Matthias Clasen * Return value: %TRUE if the key was found and removed from the #GHashTable. 508a2b269bae3315a2ea772b741fb62f683c1db5770Sven Neumann **/ 5097519c2338ae484135b44bbb7eb49719aea8c4ca3Lauri Alankogboolean 510a2b269bae3315a2ea772b741fb62f683c1db5770Sven Neumanng_hash_table_steal (GHashTable *hash_table, 511a2b269bae3315a2ea772b741fb62f683c1db5770Sven Neumann gconstpointer key) 5127519c2338ae484135b44bbb7eb49719aea8c4ca3Lauri Alanko{ 513e9010a86f763e6b7cb1fd5520985c929339f5523Ryan Lortie return g_hash_table_remove_internal (hash_table, key, FALSE); 5142e0320d57e417f7d1c838d729a99545db2228e9Owen Taylor} 5152e0320d57e417f7d1c838d729a99545db2228e9Owen Taylor 516a2b269bae3315a2ea772b741fb62f683c1db5770Sven Neumann/** 517a5b4b8bfb18838454d99bdee60294da07e5ef0d2Matthias Clasen * g_hash_table_steal_all: 518a5b4b8bfb18838454d99bdee60294da07e5ef0d2Matthias Clasen * @hash_table: a #GHashTable. 519a5b4b8bfb18838454d99bdee60294da07e5ef0d2Matthias Clasen * 5208eed88b24e86f16021d94d9b16f7a2bc895d9239Ryan Lortie * Removes all keys and their associated values from a #GHashTable 521a5b4b8bfb18838454d99bdee60294da07e5ef0d2Matthias Clasen * without calling the key and value destroy functions. 522a5b4b8bfb18838454d99bdee60294da07e5ef0d2Matthias Clasen * 523a5b4b8bfb18838454d99bdee60294da07e5ef0d2Matthias Clasen * Since: 2.12 524a5b4b8bfb18838454d99bdee60294da07e5ef0d2Matthias Clasen **/ 525a5b4b8bfb18838454d99bdee60294da07e5ef0d2Matthias Clasenvoid 526a5b4b8bfb18838454d99bdee60294da07e5ef0d2Matthias Claseng_hash_table_steal_all (GHashTable *hash_table) 527a5b4b8bfb18838454d99bdee60294da07e5ef0d2Matthias Clasen{ 528a5b4b8bfb18838454d99bdee60294da07e5ef0d2Matthias Clasen g_return_if_fail (hash_table != NULL); 529a5b4b8bfb18838454d99bdee60294da07e5ef0d2Matthias Clasen 53072ed8191afd8ff124a45285b420625e1342e35cfRyan Lortie g_hash_table_remove_all_nodes (hash_table, FALSE); 531a5b4b8bfb18838454d99bdee60294da07e5ef0d2Matthias Clasen G_HASH_TABLE_RESIZE (hash_table); 532a5b4b8bfb18838454d99bdee60294da07e5ef0d2Matthias Clasen} 533a5b4b8bfb18838454d99bdee60294da07e5ef0d2Matthias Clasen 534a5b4b8bfb18838454d99bdee60294da07e5ef0d2Matthias Clasen/** 535a2b269bae3315a2ea772b741fb62f683c1db5770Sven Neumann * g_hash_table_foreach_remove: 536a2b269bae3315a2ea772b741fb62f683c1db5770Sven Neumann * @hash_table: a #GHashTable. 537a2b269bae3315a2ea772b741fb62f683c1db5770Sven Neumann * @func: the function to call for each key/value pair. 538a2b269bae3315a2ea772b741fb62f683c1db5770Sven Neumann * @user_data: user data to pass to the function. 5398eed88b24e86f16021d94d9b16f7a2bc895d9239Ryan Lortie * 540a2b269bae3315a2ea772b741fb62f683c1db5770Sven Neumann * Calls the given function for each key/value pair in the #GHashTable. 541a52e2986cd4a2147cfc8d41ae23d98907caaf3a0Matthias Clasen * If the function returns %TRUE, then the key/value pair is removed from the 542a2b269bae3315a2ea772b741fb62f683c1db5770Sven Neumann * #GHashTable. If you supplied key or value destroy functions when creating 543a2b269bae3315a2ea772b741fb62f683c1db5770Sven Neumann * the #GHashTable, they are used to free the memory allocated for the removed 544a2b269bae3315a2ea772b741fb62f683c1db5770Sven Neumann * keys and values. 5458eed88b24e86f16021d94d9b16f7a2bc895d9239Ryan Lortie * 546a2b269bae3315a2ea772b741fb62f683c1db5770Sven Neumann * Return value: the number of key/value pairs removed. 547a2b269bae3315a2ea772b741fb62f683c1db5770Sven Neumann **/ 548a2b269bae3315a2ea772b741fb62f683c1db5770Sven Neumannguint 5498eed88b24e86f16021d94d9b16f7a2bc895d9239Ryan Lortieg_hash_table_foreach_remove (GHashTable *hash_table, 5508eed88b24e86f16021d94d9b16f7a2bc895d9239Ryan Lortie GHRFunc func, 5518eed88b24e86f16021d94d9b16f7a2bc895d9239Ryan Lortie gpointer user_data) 5522e0320d57e417f7d1c838d729a99545db2228e9Owen Taylor{ 553a2b269bae3315a2ea772b741fb62f683c1db5770Sven Neumann g_return_val_if_fail (hash_table != NULL, 0); 554a2b269bae3315a2ea772b741fb62f683c1db5770Sven Neumann g_return_val_if_fail (func != NULL, 0); 5558eed88b24e86f16021d94d9b16f7a2bc895d9239Ryan Lortie 556a2b269bae3315a2ea772b741fb62f683c1db5770Sven Neumann return g_hash_table_foreach_remove_or_steal (hash_table, func, user_data, TRUE); 5572e0320d57e417f7d1c838d729a99545db2228e9Owen Taylor} 5582e0320d57e417f7d1c838d729a99545db2228e9Owen Taylor 559a2b269bae3315a2ea772b741fb62f683c1db5770Sven Neumann/** 560a2b269bae3315a2ea772b741fb62f683c1db5770Sven Neumann * g_hash_table_foreach_steal: 561a2b269bae3315a2ea772b741fb62f683c1db5770Sven Neumann * @hash_table: a #GHashTable. 562a2b269bae3315a2ea772b741fb62f683c1db5770Sven Neumann * @func: the function to call for each key/value pair. 563a2b269bae3315a2ea772b741fb62f683c1db5770Sven Neumann * @user_data: user data to pass to the function. 5648eed88b24e86f16021d94d9b16f7a2bc895d9239Ryan Lortie * 565a2b269bae3315a2ea772b741fb62f683c1db5770Sven Neumann * Calls the given function for each key/value pair in the #GHashTable. 566a52e2986cd4a2147cfc8d41ae23d98907caaf3a0Matthias Clasen * If the function returns %TRUE, then the key/value pair is removed from the 567a2b269bae3315a2ea772b741fb62f683c1db5770Sven Neumann * #GHashTable, but no key or value destroy functions are called. 5688eed88b24e86f16021d94d9b16f7a2bc895d9239Ryan Lortie * 569a2b269bae3315a2ea772b741fb62f683c1db5770Sven Neumann * Return value: the number of key/value pairs removed. 570a2b269bae3315a2ea772b741fb62f683c1db5770Sven Neumann **/ 571a2b269bae3315a2ea772b741fb62f683c1db5770Sven Neumannguint 572a2b269bae3315a2ea772b741fb62f683c1db5770Sven Neumanng_hash_table_foreach_steal (GHashTable *hash_table, 5738eed88b24e86f16021d94d9b16f7a2bc895d9239Ryan Lortie GHRFunc func, 5748eed88b24e86f16021d94d9b16f7a2bc895d9239Ryan Lortie gpointer user_data) 5752e0320d57e417f7d1c838d729a99545db2228e9Owen Taylor{ 576a2b269bae3315a2ea772b741fb62f683c1db5770Sven Neumann g_return_val_if_fail (hash_table != NULL, 0); 577a2b269bae3315a2ea772b741fb62f683c1db5770Sven Neumann g_return_val_if_fail (func != NULL, 0); 5788eed88b24e86f16021d94d9b16f7a2bc895d9239Ryan Lortie 579a2b269bae3315a2ea772b741fb62f683c1db5770Sven Neumann return g_hash_table_foreach_remove_or_steal (hash_table, func, user_data, FALSE); 5802e0320d57e417f7d1c838d729a99545db2228e9Owen Taylor} 5812e0320d57e417f7d1c838d729a99545db2228e9Owen Taylor 582a2b269bae3315a2ea772b741fb62f683c1db5770Sven Neumannstatic guint 583a2b269bae3315a2ea772b741fb62f683c1db5770Sven Neumanng_hash_table_foreach_remove_or_steal (GHashTable *hash_table, 584a2b269bae3315a2ea772b741fb62f683c1db5770Sven Neumann GHRFunc func, 5858eed88b24e86f16021d94d9b16f7a2bc895d9239Ryan Lortie gpointer user_data, 586a2b269bae3315a2ea772b741fb62f683c1db5770Sven Neumann gboolean notify) 587034e7c0339f64d4d52a53f2324daa2fca0332addManish Singh{ 588e9010a86f763e6b7cb1fd5520985c929339f5523Ryan Lortie GHashNode *node, **node_ptr; 589d31ba84c8ea40b6f0199318e43cc2bb2e816c586Tim Janik guint deleted = 0; 590e9010a86f763e6b7cb1fd5520985c929339f5523Ryan Lortie gint i; 591e9010a86f763e6b7cb1fd5520985c929339f5523Ryan Lortie 592034e7c0339f64d4d52a53f2324daa2fca0332addManish Singh for (i = 0; i < hash_table->size; i++) 593e9010a86f763e6b7cb1fd5520985c929339f5523Ryan Lortie for (node_ptr = &hash_table->nodes[i]; (node = *node_ptr) != NULL;) 594e9010a86f763e6b7cb1fd5520985c929339f5523Ryan Lortie if ((* func) (node->key, node->value, user_data)) 595e9010a86f763e6b7cb1fd5520985c929339f5523Ryan Lortie { 596e9010a86f763e6b7cb1fd5520985c929339f5523Ryan Lortie g_hash_table_remove_node (hash_table, &node_ptr, notify); 597e9010a86f763e6b7cb1fd5520985c929339f5523Ryan Lortie deleted++; 598e9010a86f763e6b7cb1fd5520985c929339f5523Ryan Lortie } 599e9010a86f763e6b7cb1fd5520985c929339f5523Ryan Lortie else 600e9010a86f763e6b7cb1fd5520985c929339f5523Ryan Lortie node_ptr = &node->next; 601e9010a86f763e6b7cb1fd5520985c929339f5523Ryan Lortie 6028079eb3456914a03618b92b48f75a71b25331acbOwen Taylor G_HASH_TABLE_RESIZE (hash_table); 603e9010a86f763e6b7cb1fd5520985c929339f5523Ryan Lortie 604034e7c0339f64d4d52a53f2324daa2fca0332addManish Singh return deleted; 605034e7c0339f64d4d52a53f2324daa2fca0332addManish Singh} 606034e7c0339f64d4d52a53f2324daa2fca0332addManish Singh 607a2b269bae3315a2ea772b741fb62f683c1db5770Sven Neumann/** 608a2b269bae3315a2ea772b741fb62f683c1db5770Sven Neumann * g_hash_table_foreach: 609a2b269bae3315a2ea772b741fb62f683c1db5770Sven Neumann * @hash_table: a #GHashTable. 610a2b269bae3315a2ea772b741fb62f683c1db5770Sven Neumann * @func: the function to call for each key/value pair. 611a2b269bae3315a2ea772b741fb62f683c1db5770Sven Neumann * @user_data: user data to pass to the function. 6128eed88b24e86f16021d94d9b16f7a2bc895d9239Ryan Lortie * 613eb2f6f6fc1052abfa05f016ab2aed0cd0c338992Havoc Pennington * Calls the given function for each of the key/value pairs in the 614eb2f6f6fc1052abfa05f016ab2aed0cd0c338992Havoc Pennington * #GHashTable. The function is passed the key and value of each 615eb2f6f6fc1052abfa05f016ab2aed0cd0c338992Havoc Pennington * pair, and the given @user_data parameter. The hash table may not 616eb2f6f6fc1052abfa05f016ab2aed0cd0c338992Havoc Pennington * be modified while iterating over it (you can't add/remove 617eb2f6f6fc1052abfa05f016ab2aed0cd0c338992Havoc Pennington * items). To remove all items matching a predicate, use 61827096aedb58342fc8a25c17fa7d6647209425f4eMatthias Clasen * g_hash_table_foreach_remove(). 6192ef43de2af9dbb1b1ea583639c7339afe9c09af0Tim Janik * 6202ef43de2af9dbb1b1ea583639c7339afe9c09af0Tim Janik * See g_hash_table_find() for performance caveats for linear 6212ef43de2af9dbb1b1ea583639c7339afe9c09af0Tim Janik * order searches in contrast to g_hash_table_lookup(). 622a2b269bae3315a2ea772b741fb62f683c1db5770Sven Neumann **/ 6232e0320d57e417f7d1c838d729a99545db2228e9Owen Taylorvoid 6242e0320d57e417f7d1c838d729a99545db2228e9Owen Taylorg_hash_table_foreach (GHashTable *hash_table, 6258eed88b24e86f16021d94d9b16f7a2bc895d9239Ryan Lortie GHFunc func, 6268eed88b24e86f16021d94d9b16f7a2bc895d9239Ryan Lortie gpointer user_data) 6272e0320d57e417f7d1c838d729a99545db2228e9Owen Taylor{ 6282e0320d57e417f7d1c838d729a99545db2228e9Owen Taylor GHashNode *node; 6292e0320d57e417f7d1c838d729a99545db2228e9Owen Taylor gint i; 6308eed88b24e86f16021d94d9b16f7a2bc895d9239Ryan Lortie 6312d68cbbb7d37d3f265bf1087e6ddedcc58bc62beTim Janik g_return_if_fail (hash_table != NULL); 6322d68cbbb7d37d3f265bf1087e6ddedcc58bc62beTim Janik g_return_if_fail (func != NULL); 6338eed88b24e86f16021d94d9b16f7a2bc895d9239Ryan Lortie 6347519c2338ae484135b44bbb7eb49719aea8c4ca3Lauri Alanko for (i = 0; i < hash_table->size; i++) 6357519c2338ae484135b44bbb7eb49719aea8c4ca3Lauri Alanko for (node = hash_table->nodes[i]; node; node = node->next) 6367519c2338ae484135b44bbb7eb49719aea8c4ca3Lauri Alanko (* func) (node->key, node->value, user_data); 6372e0320d57e417f7d1c838d729a99545db2228e9Owen Taylor} 6382e0320d57e417f7d1c838d729a99545db2228e9Owen Taylor 639a2b269bae3315a2ea772b741fb62f683c1db5770Sven Neumann/** 640ee4e622d3724a6dfee8ce9463eccb31081cf852fTim Janik * g_hash_table_find: 641ee4e622d3724a6dfee8ce9463eccb31081cf852fTim Janik * @hash_table: a #GHashTable. 642ee4e622d3724a6dfee8ce9463eccb31081cf852fTim Janik * @predicate: function to test the key/value pairs for a certain property. 643ee4e622d3724a6dfee8ce9463eccb31081cf852fTim Janik * @user_data: user data to pass to the function. 6448eed88b24e86f16021d94d9b16f7a2bc895d9239Ryan Lortie * 6458eed88b24e86f16021d94d9b16f7a2bc895d9239Ryan Lortie * Calls the given function for key/value pairs in the #GHashTable until 6468eed88b24e86f16021d94d9b16f7a2bc895d9239Ryan Lortie * @predicate returns %TRUE. The function is passed the key and value of 6473ce97fa284cbefdc2eb957f50a3a76d6ef923464Matthias Clasen * each pair, and the given @user_data parameter. The hash table may not 6482ef43de2af9dbb1b1ea583639c7339afe9c09af0Tim Janik * be modified while iterating over it (you can't add/remove items). 6492ef43de2af9dbb1b1ea583639c7339afe9c09af0Tim Janik * 6502ef43de2af9dbb1b1ea583639c7339afe9c09af0Tim Janik * Note, that hash tables are really only optimized for forward lookups, 6512ef43de2af9dbb1b1ea583639c7339afe9c09af0Tim Janik * i.e. g_hash_table_lookup(). 6522ef43de2af9dbb1b1ea583639c7339afe9c09af0Tim Janik * So code that frequently issues g_hash_table_find() or 6532ef43de2af9dbb1b1ea583639c7339afe9c09af0Tim Janik * g_hash_table_foreach() (e.g. in the order of once per every entry in a 6542ef43de2af9dbb1b1ea583639c7339afe9c09af0Tim Janik * hash table) should probably be reworked to use additional or different 6552ef43de2af9dbb1b1ea583639c7339afe9c09af0Tim Janik * data structures for reverse lookups (keep in mind that an O(n) find/foreach 6562ef43de2af9dbb1b1ea583639c7339afe9c09af0Tim Janik * operation issued for all n values in a hash table ends up needing O(n*n) 6572ef43de2af9dbb1b1ea583639c7339afe9c09af0Tim Janik * operations). 6583ce97fa284cbefdc2eb957f50a3a76d6ef923464Matthias Clasen * 6592ef43de2af9dbb1b1ea583639c7339afe9c09af0Tim Janik * Return value: The value of the first key/value pair is returned, for which 6602ef43de2af9dbb1b1ea583639c7339afe9c09af0Tim Janik * func evaluates to %TRUE. If no pair with the requested property is found, 6613ce97fa284cbefdc2eb957f50a3a76d6ef923464Matthias Clasen * %NULL is returned. 6623ce97fa284cbefdc2eb957f50a3a76d6ef923464Matthias Clasen * 6633ce97fa284cbefdc2eb957f50a3a76d6ef923464Matthias Clasen * Since: 2.4 664ee4e622d3724a6dfee8ce9463eccb31081cf852fTim Janik **/ 665ee4e622d3724a6dfee8ce9463eccb31081cf852fTim Janikgpointer 6668eed88b24e86f16021d94d9b16f7a2bc895d9239Ryan Lortieg_hash_table_find (GHashTable *hash_table, 6678eed88b24e86f16021d94d9b16f7a2bc895d9239Ryan Lortie GHRFunc predicate, 6688eed88b24e86f16021d94d9b16f7a2bc895d9239Ryan Lortie gpointer user_data) 669ee4e622d3724a6dfee8ce9463eccb31081cf852fTim Janik{ 670ee4e622d3724a6dfee8ce9463eccb31081cf852fTim Janik GHashNode *node; 671ee4e622d3724a6dfee8ce9463eccb31081cf852fTim Janik gint i; 6728eed88b24e86f16021d94d9b16f7a2bc895d9239Ryan Lortie 673ee4e622d3724a6dfee8ce9463eccb31081cf852fTim Janik g_return_val_if_fail (hash_table != NULL, NULL); 674ee4e622d3724a6dfee8ce9463eccb31081cf852fTim Janik g_return_val_if_fail (predicate != NULL, NULL); 6758eed88b24e86f16021d94d9b16f7a2bc895d9239Ryan Lortie 676ee4e622d3724a6dfee8ce9463eccb31081cf852fTim Janik for (i = 0; i < hash_table->size; i++) 677ee4e622d3724a6dfee8ce9463eccb31081cf852fTim Janik for (node = hash_table->nodes[i]; node; node = node->next) 678ee4e622d3724a6dfee8ce9463eccb31081cf852fTim Janik if (predicate (node->key, node->value, user_data)) 6798eed88b24e86f16021d94d9b16f7a2bc895d9239Ryan Lortie return node->value; 680ee4e622d3724a6dfee8ce9463eccb31081cf852fTim Janik return NULL; 681ee4e622d3724a6dfee8ce9463eccb31081cf852fTim Janik} 682ee4e622d3724a6dfee8ce9463eccb31081cf852fTim Janik 683ee4e622d3724a6dfee8ce9463eccb31081cf852fTim Janik/** 684a2b269bae3315a2ea772b741fb62f683c1db5770Sven Neumann * g_hash_table_size: 685a2b269bae3315a2ea772b741fb62f683c1db5770Sven Neumann * @hash_table: a #GHashTable. 6868eed88b24e86f16021d94d9b16f7a2bc895d9239Ryan Lortie * 687a2b269bae3315a2ea772b741fb62f683c1db5770Sven Neumann * Returns the number of elements contained in the #GHashTable. 6888eed88b24e86f16021d94d9b16f7a2bc895d9239Ryan Lortie * 689a2b269bae3315a2ea772b741fb62f683c1db5770Sven Neumann * Return value: the number of key/value pairs in the #GHashTable. 690a2b269bae3315a2ea772b741fb62f683c1db5770Sven Neumann **/ 691d31ba84c8ea40b6f0199318e43cc2bb2e816c586Tim Janikguint 6922d68cbbb7d37d3f265bf1087e6ddedcc58bc62beTim Janikg_hash_table_size (GHashTable *hash_table) 6937519c2338ae484135b44bbb7eb49719aea8c4ca3Lauri Alanko{ 6942d68cbbb7d37d3f265bf1087e6ddedcc58bc62beTim Janik g_return_val_if_fail (hash_table != NULL, 0); 6958eed88b24e86f16021d94d9b16f7a2bc895d9239Ryan Lortie 6967519c2338ae484135b44bbb7eb49719aea8c4ca3Lauri Alanko return hash_table->nnodes; 6977519c2338ae484135b44bbb7eb49719aea8c4ca3Lauri Alanko} 6982e0320d57e417f7d1c838d729a99545db2228e9Owen Taylor 699db8642a56c0436aeb730ead593140bc01b82d4acEmmanuele Bassi/** 700db8642a56c0436aeb730ead593140bc01b82d4acEmmanuele Bassi * g_hash_table_get_keys: 701db8642a56c0436aeb730ead593140bc01b82d4acEmmanuele Bassi * @hash_table: a #GHashTable 702db8642a56c0436aeb730ead593140bc01b82d4acEmmanuele Bassi * 703db8642a56c0436aeb730ead593140bc01b82d4acEmmanuele Bassi * Retrieves every key inside @hash_table. The returned data is valid 704db8642a56c0436aeb730ead593140bc01b82d4acEmmanuele Bassi * until @hash_table is modified. 705db8642a56c0436aeb730ead593140bc01b82d4acEmmanuele Bassi * 706db8642a56c0436aeb730ead593140bc01b82d4acEmmanuele Bassi * Return value: a #GList containing all the keys inside the hash 707db8642a56c0436aeb730ead593140bc01b82d4acEmmanuele Bassi * table. The content of the list is owned by the hash table and 708db8642a56c0436aeb730ead593140bc01b82d4acEmmanuele Bassi * should not be modified or freed. Use g_list_free() when done 709db8642a56c0436aeb730ead593140bc01b82d4acEmmanuele Bassi * using the list. 710db8642a56c0436aeb730ead593140bc01b82d4acEmmanuele Bassi * 711db8642a56c0436aeb730ead593140bc01b82d4acEmmanuele Bassi * Since: 2.14 712db8642a56c0436aeb730ead593140bc01b82d4acEmmanuele Bassi */ 713db8642a56c0436aeb730ead593140bc01b82d4acEmmanuele BassiGList * 714db8642a56c0436aeb730ead593140bc01b82d4acEmmanuele Bassig_hash_table_get_keys (GHashTable *hash_table) 715db8642a56c0436aeb730ead593140bc01b82d4acEmmanuele Bassi{ 716db8642a56c0436aeb730ead593140bc01b82d4acEmmanuele Bassi GHashNode *node; 717db8642a56c0436aeb730ead593140bc01b82d4acEmmanuele Bassi gint i; 718db8642a56c0436aeb730ead593140bc01b82d4acEmmanuele Bassi GList *retval; 7198eed88b24e86f16021d94d9b16f7a2bc895d9239Ryan Lortie 720db8642a56c0436aeb730ead593140bc01b82d4acEmmanuele Bassi g_return_val_if_fail (hash_table != NULL, NULL); 7218eed88b24e86f16021d94d9b16f7a2bc895d9239Ryan Lortie 722db8642a56c0436aeb730ead593140bc01b82d4acEmmanuele Bassi retval = NULL; 723db8642a56c0436aeb730ead593140bc01b82d4acEmmanuele Bassi for (i = 0; i < hash_table->size; i++) 724db8642a56c0436aeb730ead593140bc01b82d4acEmmanuele Bassi for (node = hash_table->nodes[i]; node; node = node->next) 725db8642a56c0436aeb730ead593140bc01b82d4acEmmanuele Bassi retval = g_list_prepend (retval, node->key); 7268eed88b24e86f16021d94d9b16f7a2bc895d9239Ryan Lortie 727db8642a56c0436aeb730ead593140bc01b82d4acEmmanuele Bassi return retval; 728db8642a56c0436aeb730ead593140bc01b82d4acEmmanuele Bassi} 729db8642a56c0436aeb730ead593140bc01b82d4acEmmanuele Bassi 730db8642a56c0436aeb730ead593140bc01b82d4acEmmanuele Bassi/** 731db8642a56c0436aeb730ead593140bc01b82d4acEmmanuele Bassi * g_hash_table_get_values: 732db8642a56c0436aeb730ead593140bc01b82d4acEmmanuele Bassi * @hash_table: a #GHashTable 733db8642a56c0436aeb730ead593140bc01b82d4acEmmanuele Bassi * 734db8642a56c0436aeb730ead593140bc01b82d4acEmmanuele Bassi * Retrieves every value inside @hash_table. The returned data is 735db8642a56c0436aeb730ead593140bc01b82d4acEmmanuele Bassi * valid until @hash_table is modified. 736db8642a56c0436aeb730ead593140bc01b82d4acEmmanuele Bassi * 737db8642a56c0436aeb730ead593140bc01b82d4acEmmanuele Bassi * Return value: a #GList containing all the values inside the hash 738db8642a56c0436aeb730ead593140bc01b82d4acEmmanuele Bassi * table. The content of the list is owned by the hash table and 739db8642a56c0436aeb730ead593140bc01b82d4acEmmanuele Bassi * should not be modified or freed. Use g_list_free() when done 740db8642a56c0436aeb730ead593140bc01b82d4acEmmanuele Bassi * using the list. 741db8642a56c0436aeb730ead593140bc01b82d4acEmmanuele Bassi * 742db8642a56c0436aeb730ead593140bc01b82d4acEmmanuele Bassi * Since: 2.14 743db8642a56c0436aeb730ead593140bc01b82d4acEmmanuele Bassi */ 744db8642a56c0436aeb730ead593140bc01b82d4acEmmanuele BassiGList * 745db8642a56c0436aeb730ead593140bc01b82d4acEmmanuele Bassig_hash_table_get_values (GHashTable *hash_table) 746db8642a56c0436aeb730ead593140bc01b82d4acEmmanuele Bassi{ 747db8642a56c0436aeb730ead593140bc01b82d4acEmmanuele Bassi GHashNode *node; 748db8642a56c0436aeb730ead593140bc01b82d4acEmmanuele Bassi gint i; 749db8642a56c0436aeb730ead593140bc01b82d4acEmmanuele Bassi GList *retval; 7508eed88b24e86f16021d94d9b16f7a2bc895d9239Ryan Lortie 751db8642a56c0436aeb730ead593140bc01b82d4acEmmanuele Bassi g_return_val_if_fail (hash_table != NULL, NULL); 7528eed88b24e86f16021d94d9b16f7a2bc895d9239Ryan Lortie 753db8642a56c0436aeb730ead593140bc01b82d4acEmmanuele Bassi retval = NULL; 754db8642a56c0436aeb730ead593140bc01b82d4acEmmanuele Bassi for (i = 0; i < hash_table->size; i++) 755db8642a56c0436aeb730ead593140bc01b82d4acEmmanuele Bassi for (node = hash_table->nodes[i]; node; node = node->next) 756db8642a56c0436aeb730ead593140bc01b82d4acEmmanuele Bassi retval = g_list_prepend (retval, node->value); 7578eed88b24e86f16021d94d9b16f7a2bc895d9239Ryan Lortie 758db8642a56c0436aeb730ead593140bc01b82d4acEmmanuele Bassi return retval; 759db8642a56c0436aeb730ead593140bc01b82d4acEmmanuele Bassi} 760db8642a56c0436aeb730ead593140bc01b82d4acEmmanuele Bassi 7612e0320d57e417f7d1c838d729a99545db2228e9Owen Taylorstatic void 7622e0320d57e417f7d1c838d729a99545db2228e9Owen Taylorg_hash_table_resize (GHashTable *hash_table) 7632e0320d57e417f7d1c838d729a99545db2228e9Owen Taylor{ 7642e0320d57e417f7d1c838d729a99545db2228e9Owen Taylor GHashNode **new_nodes; 7652e0320d57e417f7d1c838d729a99545db2228e9Owen Taylor GHashNode *node; 7662e0320d57e417f7d1c838d729a99545db2228e9Owen Taylor GHashNode *next; 7672e0320d57e417f7d1c838d729a99545db2228e9Owen Taylor guint hash_val; 7682e0320d57e417f7d1c838d729a99545db2228e9Owen Taylor gint new_size; 7692e0320d57e417f7d1c838d729a99545db2228e9Owen Taylor gint i; 7708079eb3456914a03618b92b48f75a71b25331acbOwen Taylor 77173e6da92b298d48e3de9d775b5adc97cbff7b0aaSven Neumann new_size = g_spaced_primes_closest (hash_table->nnodes); 77273e6da92b298d48e3de9d775b5adc97cbff7b0aaSven Neumann new_size = CLAMP (new_size, HASH_TABLE_MIN_SIZE, HASH_TABLE_MAX_SIZE); 7738eed88b24e86f16021d94d9b16f7a2bc895d9239Ryan Lortie 774448e792b0a9b092f9593eaa51e16acd8abe54c76Jeff Garzik new_nodes = g_new0 (GHashNode*, new_size); 7758eed88b24e86f16021d94d9b16f7a2bc895d9239Ryan Lortie 7767519c2338ae484135b44bbb7eb49719aea8c4ca3Lauri Alanko for (i = 0; i < hash_table->size; i++) 7777519c2338ae484135b44bbb7eb49719aea8c4ca3Lauri Alanko for (node = hash_table->nodes[i]; node; node = next) 7787519c2338ae484135b44bbb7eb49719aea8c4ca3Lauri Alanko { 7797519c2338ae484135b44bbb7eb49719aea8c4ca3Lauri Alanko next = node->next; 780448e792b0a9b092f9593eaa51e16acd8abe54c76Jeff Garzik 781e6b78c9af1d6416f93311b98e1e6d802e2fe0617Ryan Lortie hash_val = node->key_hash % new_size; 782448e792b0a9b092f9593eaa51e16acd8abe54c76Jeff Garzik 7837519c2338ae484135b44bbb7eb49719aea8c4ca3Lauri Alanko node->next = new_nodes[hash_val]; 7847519c2338ae484135b44bbb7eb49719aea8c4ca3Lauri Alanko new_nodes[hash_val] = node; 7857519c2338ae484135b44bbb7eb49719aea8c4ca3Lauri Alanko } 7868eed88b24e86f16021d94d9b16f7a2bc895d9239Ryan Lortie 7877519c2338ae484135b44bbb7eb49719aea8c4ca3Lauri Alanko g_free (hash_table->nodes); 7887519c2338ae484135b44bbb7eb49719aea8c4ca3Lauri Alanko hash_table->nodes = new_nodes; 7897519c2338ae484135b44bbb7eb49719aea8c4ca3Lauri Alanko hash_table->size = new_size; 7907519c2338ae484135b44bbb7eb49719aea8c4ca3Lauri Alanko} 7917519c2338ae484135b44bbb7eb49719aea8c4ca3Lauri Alanko 7922e0320d57e417f7d1c838d729a99545db2228e9Owen Taylorstatic GHashNode* 7932e0320d57e417f7d1c838d729a99545db2228e9Owen Taylorg_hash_node_new (gpointer key, 794e6b78c9af1d6416f93311b98e1e6d802e2fe0617Ryan Lortie gpointer value, 795e6b78c9af1d6416f93311b98e1e6d802e2fe0617Ryan Lortie guint key_hash) 7962e0320d57e417f7d1c838d729a99545db2228e9Owen Taylor{ 7970cba1b531d5d28890fa4f48359d4e7adacf2a603Tim Janik GHashNode *hash_node = g_slice_new (GHashNode); 7988eed88b24e86f16021d94d9b16f7a2bc895d9239Ryan Lortie 7992e0320d57e417f7d1c838d729a99545db2228e9Owen Taylor hash_node->key = key; 8002e0320d57e417f7d1c838d729a99545db2228e9Owen Taylor hash_node->value = value; 801e6b78c9af1d6416f93311b98e1e6d802e2fe0617Ryan Lortie hash_node->key_hash = key_hash; 8022e0320d57e417f7d1c838d729a99545db2228e9Owen Taylor hash_node->next = NULL; 8038eed88b24e86f16021d94d9b16f7a2bc895d9239Ryan Lortie 8042e0320d57e417f7d1c838d729a99545db2228e9Owen Taylor return hash_node; 8052e0320d57e417f7d1c838d729a99545db2228e9Owen Taylor} 8062e0320d57e417f7d1c838d729a99545db2228e9Owen Taylor 807608a31b98e1420f487190871ee7312db2643d93dMatthias Clasen#define __G_HASH_C__ 808608a31b98e1420f487190871ee7312db2643d93dMatthias Clasen#include "galiasdef.c" 809