ghash.c revision a5b4b8bfb18838454d99bdee60294da07e5ef0d2
12e0320d57e417f7d1c838d729a99545db2228e9Owen Taylor/* GLIB - Library of useful routines for C programming 22e0320d57e417f7d1c838d729a99545db2228e9Owen Taylor * Copyright (C) 1995-1997 Peter Mattis, Spencer Kimball and Josh MacDonald 32e0320d57e417f7d1c838d729a99545db2228e9Owen Taylor * 42e0320d57e417f7d1c838d729a99545db2228e9Owen Taylor * This library is free software; you can redistribute it and/or 5c9bd7542e1a28ba9de60048361c0a97d251833e7Tim Janik * modify it under the terms of the GNU Lesser General Public 62e0320d57e417f7d1c838d729a99545db2228e9Owen Taylor * License as published by the Free Software Foundation; either 72e0320d57e417f7d1c838d729a99545db2228e9Owen Taylor * version 2 of the License, or (at your option) any later version. 82e0320d57e417f7d1c838d729a99545db2228e9Owen Taylor * 92e0320d57e417f7d1c838d729a99545db2228e9Owen Taylor * This library is distributed in the hope that it will be useful, 102e0320d57e417f7d1c838d729a99545db2228e9Owen Taylor * but WITHOUT ANY WARRANTY; without even the implied warranty of 112d68cbbb7d37d3f265bf1087e6ddedcc58bc62beTim Janik * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the GNU 12c9bd7542e1a28ba9de60048361c0a97d251833e7Tim Janik * Lesser General Public License for more details. 132e0320d57e417f7d1c838d729a99545db2228e9Owen Taylor * 14c9bd7542e1a28ba9de60048361c0a97d251833e7Tim Janik * You should have received a copy of the GNU Lesser General Public 152e0320d57e417f7d1c838d729a99545db2228e9Owen Taylor * License along with this library; if not, write to the 162e0320d57e417f7d1c838d729a99545db2228e9Owen Taylor * Free Software Foundation, Inc., 59 Temple Place - Suite 330, 172e0320d57e417f7d1c838d729a99545db2228e9Owen Taylor * Boston, MA 02111-1307, USA. 182e0320d57e417f7d1c838d729a99545db2228e9Owen Taylor */ 19931ea952650b013b834041b91b0c37a748ffd449Owen Taylor 20b9ef2b41db975061960e2217220668c2a5d563daCST/* 21c9bd7542e1a28ba9de60048361c0a97d251833e7Tim Janik * Modified by the GLib Team and others 1997-2000. See the AUTHORS 22b9ef2b41db975061960e2217220668c2a5d563daCST * file for a list of people on the GLib Team. See the ChangeLog 23b9ef2b41db975061960e2217220668c2a5d563daCST * files for a list of changes. These files are distributed with 24b9ef2b41db975061960e2217220668c2a5d563daCST * GLib at ftp://ftp.gtk.org/pub/gtk/. 25b9ef2b41db975061960e2217220668c2a5d563daCST */ 26b9ef2b41db975061960e2217220668c2a5d563daCST 27931ea952650b013b834041b91b0c37a748ffd449Owen Taylor/* 28931ea952650b013b834041b91b0c37a748ffd449Owen Taylor * MT safe 29931ea952650b013b834041b91b0c37a748ffd449Owen Taylor */ 30931ea952650b013b834041b91b0c37a748ffd449Owen Taylor 31bbbd329ff5bd634b4e1d4fb43b13538779e44a78Owen Taylor#include "config.h" 322fb47703e2929d300a3f804268a36d50543b4a2cSebastian Wilhelmi 332e0320d57e417f7d1c838d729a99545db2228e9Owen Taylor#include "glib.h" 34608a31b98e1420f487190871ee7312db2643d93dMatthias Clasen#include "galias.h" 352e0320d57e417f7d1c838d729a99545db2228e9Owen Taylor 362e0320d57e417f7d1c838d729a99545db2228e9Owen Taylor 372e0320d57e417f7d1c838d729a99545db2228e9Owen Taylor#define HASH_TABLE_MIN_SIZE 11 382e0320d57e417f7d1c838d729a99545db2228e9Owen Taylor#define HASH_TABLE_MAX_SIZE 13845163 392e0320d57e417f7d1c838d729a99545db2228e9Owen Taylor 402e0320d57e417f7d1c838d729a99545db2228e9Owen Taylor 412e0320d57e417f7d1c838d729a99545db2228e9Owen Taylortypedef struct _GHashNode GHashNode; 422e0320d57e417f7d1c838d729a99545db2228e9Owen Taylor 432e0320d57e417f7d1c838d729a99545db2228e9Owen Taylorstruct _GHashNode 442e0320d57e417f7d1c838d729a99545db2228e9Owen Taylor{ 45a2b269bae3315a2ea772b741fb62f683c1db5770Sven Neumann gpointer key; 46a2b269bae3315a2ea772b741fb62f683c1db5770Sven Neumann gpointer value; 472e0320d57e417f7d1c838d729a99545db2228e9Owen Taylor GHashNode *next; 482e0320d57e417f7d1c838d729a99545db2228e9Owen Taylor}; 492e0320d57e417f7d1c838d729a99545db2228e9Owen Taylor 507519c2338ae484135b44bbb7eb49719aea8c4ca3Lauri Alankostruct _GHashTable 512e0320d57e417f7d1c838d729a99545db2228e9Owen Taylor{ 52a2b269bae3315a2ea772b741fb62f683c1db5770Sven Neumann gint size; 53a2b269bae3315a2ea772b741fb62f683c1db5770Sven Neumann gint nnodes; 54a2b269bae3315a2ea772b741fb62f683c1db5770Sven Neumann GHashNode **nodes; 55a2b269bae3315a2ea772b741fb62f683c1db5770Sven Neumann GHashFunc hash_func; 56a2b269bae3315a2ea772b741fb62f683c1db5770Sven Neumann GEqualFunc key_equal_func; 573e847a090cfd8495add631d43388c461b1a85716Tim Janik volatile guint ref_count; 58a2b269bae3315a2ea772b741fb62f683c1db5770Sven Neumann GDestroyNotify key_destroy_func; 59a2b269bae3315a2ea772b741fb62f683c1db5770Sven Neumann GDestroyNotify value_destroy_func; 602e0320d57e417f7d1c838d729a99545db2228e9Owen Taylor}; 612e0320d57e417f7d1c838d729a99545db2228e9Owen Taylor 628079eb3456914a03618b92b48f75a71b25331acbOwen Taylor#define G_HASH_TABLE_RESIZE(hash_table) \ 638079eb3456914a03618b92b48f75a71b25331acbOwen Taylor G_STMT_START { \ 648079eb3456914a03618b92b48f75a71b25331acbOwen Taylor if ((hash_table->size >= 3 * hash_table->nnodes && \ 658079eb3456914a03618b92b48f75a71b25331acbOwen Taylor hash_table->size > HASH_TABLE_MIN_SIZE) || \ 668079eb3456914a03618b92b48f75a71b25331acbOwen Taylor (3 * hash_table->size <= hash_table->nnodes && \ 678079eb3456914a03618b92b48f75a71b25331acbOwen Taylor hash_table->size < HASH_TABLE_MAX_SIZE)) \ 688079eb3456914a03618b92b48f75a71b25331acbOwen Taylor g_hash_table_resize (hash_table); \ 698079eb3456914a03618b92b48f75a71b25331acbOwen Taylor } G_STMT_END 702e0320d57e417f7d1c838d729a99545db2228e9Owen Taylor 71a2b269bae3315a2ea772b741fb62f683c1db5770Sven Neumannstatic void g_hash_table_resize (GHashTable *hash_table); 72a2b269bae3315a2ea772b741fb62f683c1db5770Sven Neumannstatic GHashNode** g_hash_table_lookup_node (GHashTable *hash_table, 73a2b269bae3315a2ea772b741fb62f683c1db5770Sven Neumann gconstpointer key); 74a2b269bae3315a2ea772b741fb62f683c1db5770Sven Neumannstatic GHashNode* g_hash_node_new (gpointer key, 75a2b269bae3315a2ea772b741fb62f683c1db5770Sven Neumann gpointer value); 76a2b269bae3315a2ea772b741fb62f683c1db5770Sven Neumannstatic void g_hash_node_destroy (GHashNode *hash_node, 77a2b269bae3315a2ea772b741fb62f683c1db5770Sven Neumann GDestroyNotify key_destroy_func, 78a2b269bae3315a2ea772b741fb62f683c1db5770Sven Neumann GDestroyNotify value_destroy_func); 79a2b269bae3315a2ea772b741fb62f683c1db5770Sven Neumannstatic void g_hash_nodes_destroy (GHashNode *hash_node, 80a2b269bae3315a2ea772b741fb62f683c1db5770Sven Neumann GDestroyNotify key_destroy_func, 81a2b269bae3315a2ea772b741fb62f683c1db5770Sven Neumann GDestroyNotify value_destroy_func); 82a2b269bae3315a2ea772b741fb62f683c1db5770Sven Neumannstatic guint g_hash_table_foreach_remove_or_steal (GHashTable *hash_table, 83a2b269bae3315a2ea772b741fb62f683c1db5770Sven Neumann GHRFunc func, 84a2b269bae3315a2ea772b741fb62f683c1db5770Sven Neumann gpointer user_data, 85a2b269bae3315a2ea772b741fb62f683c1db5770Sven Neumann gboolean notify); 862e0320d57e417f7d1c838d729a99545db2228e9Owen Taylor 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 92a2b269bae3315a2ea772b741fb62f683c1db5770Sven Neumann * #GHashTable data structure. The g_direct_hash(), g_int_hash() and 93a2b269bae3315a2ea772b741fb62f683c1db5770Sven Neumann * 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. 103a2b269bae3315a2ea772b741fb62f683c1db5770Sven Neumann * 104a2b269bae3315a2ea772b741fb62f683c1db5770Sven Neumann * Return value: a new #GHashTable. 105a2b269bae3315a2ea772b741fb62f683c1db5770Sven Neumann **/ 1062e0320d57e417f7d1c838d729a99545db2228e9Owen TaylorGHashTable* 1072e0320d57e417f7d1c838d729a99545db2228e9Owen Taylorg_hash_table_new (GHashFunc hash_func, 108267b6813703e24ef60d0e8ba42557c414f9dd52eSebastian Wilhelmi 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. 118a2b269bae3315a2ea772b741fb62f683c1db5770Sven Neumann * @key_destroy_func: a function to free the memory allocated for the key 119a52e2986cd4a2147cfc8d41ae23d98907caaf3a0Matthias Clasen * used when removing the entry from the #GHashTable or %NULL if you 120d18b364dd774087555f036fec2c6ec9fe838368fSven Neumann * don't want to supply such a function. 121a2b269bae3315a2ea772b741fb62f683c1db5770Sven Neumann * @value_destroy_func: a function to free the memory allocated for the 122a52e2986cd4a2147cfc8d41ae23d98907caaf3a0Matthias Clasen * value used when removing the entry from the #GHashTable or %NULL if 123a2b269bae3315a2ea772b741fb62f683c1db5770Sven Neumann * you don't want to supply such a function. 124a2b269bae3315a2ea772b741fb62f683c1db5770Sven Neumann * 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. 128a2b269bae3315a2ea772b741fb62f683c1db5770Sven Neumann * 129a2b269bae3315a2ea772b741fb62f683c1db5770Sven Neumann * Return value: a new #GHashTable. 130a2b269bae3315a2ea772b741fb62f683c1db5770Sven Neumann **/ 131a2b269bae3315a2ea772b741fb62f683c1db5770Sven NeumannGHashTable* 132a2b269bae3315a2ea772b741fb62f683c1db5770Sven Neumanng_hash_table_new_full (GHashFunc hash_func, 133a2b269bae3315a2ea772b741fb62f683c1db5770Sven Neumann GEqualFunc key_equal_func, 134a2b269bae3315a2ea772b741fb62f683c1db5770Sven Neumann GDestroyNotify key_destroy_func, 135a2b269bae3315a2ea772b741fb62f683c1db5770Sven Neumann GDestroyNotify value_destroy_func) 136a2b269bae3315a2ea772b741fb62f683c1db5770Sven Neumann{ 1377519c2338ae484135b44bbb7eb49719aea8c4ca3Lauri Alanko GHashTable *hash_table; 1382d68cbbb7d37d3f265bf1087e6ddedcc58bc62beTim Janik 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); 1482d68cbbb7d37d3f265bf1087e6ddedcc58bc62beTim Janik 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. 1563e847a090cfd8495add631d43388c461b1a85716Tim Janik * 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. 1593e847a090cfd8495add631d43388c461b1a85716Tim Janik * 1603e847a090cfd8495add631d43388c461b1a85716Tim Janik * Return value: the passed in #GHashTable. 161fe749cbd3b058512e36d79203cac3c00c7f40571Matthias Clasen * 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. 1773e847a090cfd8495add631d43388c461b1a85716Tim Janik * 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. 182fe749cbd3b058512e36d79203cac3c00c7f40571Matthias Clasen * 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 { 19309b118f462fabb228ba26a498001f7c4e72bdde8Matthias Clasen gint i; 19409b118f462fabb228ba26a498001f7c4e72bdde8Matthias Clasen 1953e847a090cfd8495add631d43388c461b1a85716Tim Janik for (i = 0; i < hash_table->size; i++) 1963e847a090cfd8495add631d43388c461b1a85716Tim Janik g_hash_nodes_destroy (hash_table->nodes[i], 1973e847a090cfd8495add631d43388c461b1a85716Tim Janik hash_table->key_destroy_func, 1983e847a090cfd8495add631d43388c461b1a85716Tim Janik hash_table->value_destroy_func); 1993e847a090cfd8495add631d43388c461b1a85716Tim Janik g_free (hash_table->nodes); 2003e847a090cfd8495add631d43388c461b1a85716Tim Janik g_slice_free (GHashTable, hash_table); 2013e847a090cfd8495add631d43388c461b1a85716Tim Janik } 2023e847a090cfd8495add631d43388c461b1a85716Tim Janik} 2033e847a090cfd8495add631d43388c461b1a85716Tim Janik 204a2b269bae3315a2ea772b741fb62f683c1db5770Sven Neumann/** 205a2b269bae3315a2ea772b741fb62f683c1db5770Sven Neumann * g_hash_table_destroy: 206a2b269bae3315a2ea772b741fb62f683c1db5770Sven Neumann * @hash_table: a #GHashTable. 207a2b269bae3315a2ea772b741fb62f683c1db5770Sven Neumann * 20824dec3cd490fa4dc057a0186c6b870160022268eMorten Welinder * Destroys all keys and values in the #GHashTable and decrements its 2093e847a090cfd8495add631d43388c461b1a85716Tim Janik * reference count by 1. If keys and/or values are dynamically allocated, 2103e847a090cfd8495add631d43388c461b1a85716Tim Janik * you should either free them first or create the #GHashTable with destroy 2113e847a090cfd8495add631d43388c461b1a85716Tim Janik * notifiers using g_hash_table_new_full(). In the latter case the destroy 2123e847a090cfd8495add631d43388c461b1a85716Tim Janik * functions you supplied will be called on all keys and values during the 2133e847a090cfd8495add631d43388c461b1a85716Tim Janik * destruction phase. 214a2b269bae3315a2ea772b741fb62f683c1db5770Sven Neumann **/ 2152e0320d57e417f7d1c838d729a99545db2228e9Owen Taylorvoid 2162e0320d57e417f7d1c838d729a99545db2228e9Owen Taylorg_hash_table_destroy (GHashTable *hash_table) 2172e0320d57e417f7d1c838d729a99545db2228e9Owen Taylor{ 2182d68cbbb7d37d3f265bf1087e6ddedcc58bc62beTim Janik g_return_if_fail (hash_table != NULL); 2193e847a090cfd8495add631d43388c461b1a85716Tim Janik g_return_if_fail (hash_table->ref_count > 0); 2202d68cbbb7d37d3f265bf1087e6ddedcc58bc62beTim Janik 221a5b4b8bfb18838454d99bdee60294da07e5ef0d2Matthias Clasen g_hash_table_remove_all (hash_table); 2223e847a090cfd8495add631d43388c461b1a85716Tim Janik g_hash_table_unref (hash_table); 2232e0320d57e417f7d1c838d729a99545db2228e9Owen Taylor} 2242e0320d57e417f7d1c838d729a99545db2228e9Owen Taylor 225d5492a983cfa048658af8b03f833ddb3c0cf355eESTstatic inline GHashNode** 226d5492a983cfa048658af8b03f833ddb3c0cf355eESTg_hash_table_lookup_node (GHashTable *hash_table, 227d5492a983cfa048658af8b03f833ddb3c0cf355eEST gconstpointer key) 2282e0320d57e417f7d1c838d729a99545db2228e9Owen Taylor{ 229d5492a983cfa048658af8b03f833ddb3c0cf355eEST GHashNode **node; 2302d68cbbb7d37d3f265bf1087e6ddedcc58bc62beTim Janik 231d5492a983cfa048658af8b03f833ddb3c0cf355eEST node = &hash_table->nodes 232d5492a983cfa048658af8b03f833ddb3c0cf355eEST [(* hash_table->hash_func) (key) % hash_table->size]; 2332d68cbbb7d37d3f265bf1087e6ddedcc58bc62beTim Janik 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. 2382d68cbbb7d37d3f265bf1087e6ddedcc58bc62beTim Janik */ 239267b6813703e24ef60d0e8ba42557c414f9dd52eSebastian Wilhelmi if (hash_table->key_equal_func) 240267b6813703e24ef60d0e8ba42557c414f9dd52eSebastian Wilhelmi while (*node && !(*hash_table->key_equal_func) ((*node)->key, key)) 241d5492a983cfa048658af8b03f833ddb3c0cf355eEST node = &(*node)->next; 2422d68cbbb7d37d3f265bf1087e6ddedcc58bc62beTim Janik else 243d5492a983cfa048658af8b03f833ddb3c0cf355eEST while (*node && (*node)->key != key) 244d5492a983cfa048658af8b03f833ddb3c0cf355eEST node = &(*node)->next; 2452d68cbbb7d37d3f265bf1087e6ddedcc58bc62beTim Janik 2462d68cbbb7d37d3f265bf1087e6ddedcc58bc62beTim Janik return node; 2472d68cbbb7d37d3f265bf1087e6ddedcc58bc62beTim Janik} 2482e0320d57e417f7d1c838d729a99545db2228e9Owen Taylor 249a2b269bae3315a2ea772b741fb62f683c1db5770Sven Neumann/** 250a2b269bae3315a2ea772b741fb62f683c1db5770Sven Neumann * g_hash_table_lookup: 251a2b269bae3315a2ea772b741fb62f683c1db5770Sven Neumann * @hash_table: a #GHashTable. 252a2b269bae3315a2ea772b741fb62f683c1db5770Sven Neumann * @key: the key to look up. 253a2b269bae3315a2ea772b741fb62f683c1db5770Sven Neumann * 254fd92ac8f5280ccb936a534a14f5c9cbdb24302e5Matthias Clasen * Looks up a key in a #GHashTable. Note that this function cannot 255fd92ac8f5280ccb936a534a14f5c9cbdb24302e5Matthias Clasen * distinguish between a key that is not present and one which is present 256fd92ac8f5280ccb936a534a14f5c9cbdb24302e5Matthias Clasen * and has the value %NULL. If you need this distinction, use 257fd92ac8f5280ccb936a534a14f5c9cbdb24302e5Matthias Clasen * g_hash_table_lookup_extended(). 258a2b269bae3315a2ea772b741fb62f683c1db5770Sven Neumann * 259a52e2986cd4a2147cfc8d41ae23d98907caaf3a0Matthias Clasen * Return value: the associated value, or %NULL if the key is not found. 260a2b269bae3315a2ea772b741fb62f683c1db5770Sven Neumann **/ 2612d68cbbb7d37d3f265bf1087e6ddedcc58bc62beTim Janikgpointer 2622d68cbbb7d37d3f265bf1087e6ddedcc58bc62beTim Janikg_hash_table_lookup (GHashTable *hash_table, 2632d68cbbb7d37d3f265bf1087e6ddedcc58bc62beTim Janik gconstpointer key) 2642d68cbbb7d37d3f265bf1087e6ddedcc58bc62beTim Janik{ 2652d68cbbb7d37d3f265bf1087e6ddedcc58bc62beTim Janik GHashNode *node; 2662d68cbbb7d37d3f265bf1087e6ddedcc58bc62beTim Janik 2672d68cbbb7d37d3f265bf1087e6ddedcc58bc62beTim Janik g_return_val_if_fail (hash_table != NULL, NULL); 2682d68cbbb7d37d3f265bf1087e6ddedcc58bc62beTim Janik 269d5492a983cfa048658af8b03f833ddb3c0cf355eEST node = *g_hash_table_lookup_node (hash_table, key); 2702d68cbbb7d37d3f265bf1087e6ddedcc58bc62beTim Janik 2712d68cbbb7d37d3f265bf1087e6ddedcc58bc62beTim Janik return node ? node->value : NULL; 2722d68cbbb7d37d3f265bf1087e6ddedcc58bc62beTim Janik} 2737401460a60504dad7b77219d0ba3d93112e12444Manish Singh 274a2b269bae3315a2ea772b741fb62f683c1db5770Sven Neumann/** 275a2b269bae3315a2ea772b741fb62f683c1db5770Sven Neumann * g_hash_table_lookup_extended: 276a2b269bae3315a2ea772b741fb62f683c1db5770Sven Neumann * @hash_table: a #GHashTable. 277a2b269bae3315a2ea772b741fb62f683c1db5770Sven Neumann * @lookup_key: the key to look up. 278a2b269bae3315a2ea772b741fb62f683c1db5770Sven Neumann * @orig_key: returns the original key. 279a2b269bae3315a2ea772b741fb62f683c1db5770Sven Neumann * @value: returns the value associated with the key. 280a2b269bae3315a2ea772b741fb62f683c1db5770Sven Neumann * 281a2b269bae3315a2ea772b741fb62f683c1db5770Sven Neumann * Looks up a key in the #GHashTable, returning the original key and the 282a52e2986cd4a2147cfc8d41ae23d98907caaf3a0Matthias Clasen * associated value and a #gboolean which is %TRUE if the key was found. This 283a2b269bae3315a2ea772b741fb62f683c1db5770Sven Neumann * is useful if you need to free the memory allocated for the original key, 284a2b269bae3315a2ea772b741fb62f683c1db5770Sven Neumann * for example before calling g_hash_table_remove(). 285a2b269bae3315a2ea772b741fb62f683c1db5770Sven Neumann * 2863fa33317b7e9866793ce1ea32d069e8c9270caa2Matthias Clasen * Return value: %TRUE if the key was found in the #GHashTable. 287a2b269bae3315a2ea772b741fb62f683c1db5770Sven Neumann **/ 288a2b269bae3315a2ea772b741fb62f683c1db5770Sven Neumanngboolean 289a2b269bae3315a2ea772b741fb62f683c1db5770Sven Neumanng_hash_table_lookup_extended (GHashTable *hash_table, 290a2b269bae3315a2ea772b741fb62f683c1db5770Sven Neumann gconstpointer lookup_key, 291a2b269bae3315a2ea772b741fb62f683c1db5770Sven Neumann gpointer *orig_key, 292a2b269bae3315a2ea772b741fb62f683c1db5770Sven Neumann gpointer *value) 293a2b269bae3315a2ea772b741fb62f683c1db5770Sven Neumann{ 294a2b269bae3315a2ea772b741fb62f683c1db5770Sven Neumann GHashNode *node; 295a2b269bae3315a2ea772b741fb62f683c1db5770Sven Neumann 296a2b269bae3315a2ea772b741fb62f683c1db5770Sven Neumann g_return_val_if_fail (hash_table != NULL, FALSE); 297a2b269bae3315a2ea772b741fb62f683c1db5770Sven Neumann 298a2b269bae3315a2ea772b741fb62f683c1db5770Sven Neumann node = *g_hash_table_lookup_node (hash_table, lookup_key); 299a2b269bae3315a2ea772b741fb62f683c1db5770Sven Neumann 300a2b269bae3315a2ea772b741fb62f683c1db5770Sven Neumann if (node) 301a2b269bae3315a2ea772b741fb62f683c1db5770Sven Neumann { 302a2b269bae3315a2ea772b741fb62f683c1db5770Sven Neumann if (orig_key) 303a2b269bae3315a2ea772b741fb62f683c1db5770Sven Neumann *orig_key = node->key; 304a2b269bae3315a2ea772b741fb62f683c1db5770Sven Neumann if (value) 305a2b269bae3315a2ea772b741fb62f683c1db5770Sven Neumann *value = node->value; 306a2b269bae3315a2ea772b741fb62f683c1db5770Sven Neumann return TRUE; 307a2b269bae3315a2ea772b741fb62f683c1db5770Sven Neumann } 308a2b269bae3315a2ea772b741fb62f683c1db5770Sven Neumann else 309a2b269bae3315a2ea772b741fb62f683c1db5770Sven Neumann return FALSE; 310a2b269bae3315a2ea772b741fb62f683c1db5770Sven Neumann} 311a2b269bae3315a2ea772b741fb62f683c1db5770Sven Neumann 312a2b269bae3315a2ea772b741fb62f683c1db5770Sven Neumann/** 313a2b269bae3315a2ea772b741fb62f683c1db5770Sven Neumann * g_hash_table_insert: 314a2b269bae3315a2ea772b741fb62f683c1db5770Sven Neumann * @hash_table: a #GHashTable. 315a2b269bae3315a2ea772b741fb62f683c1db5770Sven Neumann * @key: a key to insert. 316a2b269bae3315a2ea772b741fb62f683c1db5770Sven Neumann * @value: the value to associate with the key. 317a2b269bae3315a2ea772b741fb62f683c1db5770Sven Neumann * 318a2b269bae3315a2ea772b741fb62f683c1db5770Sven Neumann * Inserts a new key and value into a #GHashTable. 319a2b269bae3315a2ea772b741fb62f683c1db5770Sven Neumann * 320a2b269bae3315a2ea772b741fb62f683c1db5770Sven Neumann * If the key already exists in the #GHashTable its current value is replaced 321a52e2986cd4a2147cfc8d41ae23d98907caaf3a0Matthias Clasen * with the new value. If you supplied a @value_destroy_func when creating the 322a2b269bae3315a2ea772b741fb62f683c1db5770Sven Neumann * #GHashTable, the old value is freed using that function. If you supplied 323a52e2986cd4a2147cfc8d41ae23d98907caaf3a0Matthias Clasen * a @key_destroy_func when creating the #GHashTable, the passed key is freed 324a2b269bae3315a2ea772b741fb62f683c1db5770Sven Neumann * using that function. 325a2b269bae3315a2ea772b741fb62f683c1db5770Sven Neumann **/ 3262d68cbbb7d37d3f265bf1087e6ddedcc58bc62beTim Janikvoid 3272d68cbbb7d37d3f265bf1087e6ddedcc58bc62beTim Janikg_hash_table_insert (GHashTable *hash_table, 3282d68cbbb7d37d3f265bf1087e6ddedcc58bc62beTim Janik gpointer key, 3292d68cbbb7d37d3f265bf1087e6ddedcc58bc62beTim Janik gpointer value) 3302d68cbbb7d37d3f265bf1087e6ddedcc58bc62beTim Janik{ 331d5492a983cfa048658af8b03f833ddb3c0cf355eEST GHashNode **node; 3322d68cbbb7d37d3f265bf1087e6ddedcc58bc62beTim Janik 3332d68cbbb7d37d3f265bf1087e6ddedcc58bc62beTim Janik g_return_if_fail (hash_table != NULL); 3343e847a090cfd8495add631d43388c461b1a85716Tim Janik g_return_if_fail (hash_table->ref_count > 0); 3352d68cbbb7d37d3f265bf1087e6ddedcc58bc62beTim Janik 336d5492a983cfa048658af8b03f833ddb3c0cf355eEST node = g_hash_table_lookup_node (hash_table, key); 337d5492a983cfa048658af8b03f833ddb3c0cf355eEST 338d5492a983cfa048658af8b03f833ddb3c0cf355eEST if (*node) 3397519c2338ae484135b44bbb7eb49719aea8c4ca3Lauri Alanko { 3407519c2338ae484135b44bbb7eb49719aea8c4ca3Lauri Alanko /* do not reset node->key in this place, keeping 341a2b269bae3315a2ea772b741fb62f683c1db5770Sven Neumann * the old key is the intended behaviour. 342a2b269bae3315a2ea772b741fb62f683c1db5770Sven Neumann * g_hash_table_replace() can be used instead. 343a2b269bae3315a2ea772b741fb62f683c1db5770Sven Neumann */ 344a2b269bae3315a2ea772b741fb62f683c1db5770Sven Neumann 345a2b269bae3315a2ea772b741fb62f683c1db5770Sven Neumann /* free the passed key */ 346a2b269bae3315a2ea772b741fb62f683c1db5770Sven Neumann if (hash_table->key_destroy_func) 347a2b269bae3315a2ea772b741fb62f683c1db5770Sven Neumann hash_table->key_destroy_func (key); 348a2b269bae3315a2ea772b741fb62f683c1db5770Sven Neumann 349a2b269bae3315a2ea772b741fb62f683c1db5770Sven Neumann if (hash_table->value_destroy_func) 350a2b269bae3315a2ea772b741fb62f683c1db5770Sven Neumann hash_table->value_destroy_func ((*node)->value); 351a2b269bae3315a2ea772b741fb62f683c1db5770Sven Neumann 352a2b269bae3315a2ea772b741fb62f683c1db5770Sven Neumann (*node)->value = value; 353a2b269bae3315a2ea772b741fb62f683c1db5770Sven Neumann } 354a2b269bae3315a2ea772b741fb62f683c1db5770Sven Neumann else 355a2b269bae3315a2ea772b741fb62f683c1db5770Sven Neumann { 356a2b269bae3315a2ea772b741fb62f683c1db5770Sven Neumann *node = g_hash_node_new (key, value); 357a2b269bae3315a2ea772b741fb62f683c1db5770Sven Neumann hash_table->nnodes++; 3588079eb3456914a03618b92b48f75a71b25331acbOwen Taylor G_HASH_TABLE_RESIZE (hash_table); 359a2b269bae3315a2ea772b741fb62f683c1db5770Sven Neumann } 360a2b269bae3315a2ea772b741fb62f683c1db5770Sven Neumann} 361a2b269bae3315a2ea772b741fb62f683c1db5770Sven Neumann 362a2b269bae3315a2ea772b741fb62f683c1db5770Sven Neumann/** 363a2b269bae3315a2ea772b741fb62f683c1db5770Sven Neumann * g_hash_table_replace: 364a2b269bae3315a2ea772b741fb62f683c1db5770Sven Neumann * @hash_table: a #GHashTable. 365a2b269bae3315a2ea772b741fb62f683c1db5770Sven Neumann * @key: a key to insert. 366a2b269bae3315a2ea772b741fb62f683c1db5770Sven Neumann * @value: the value to associate with the key. 367a2b269bae3315a2ea772b741fb62f683c1db5770Sven Neumann * 368a2b269bae3315a2ea772b741fb62f683c1db5770Sven Neumann * Inserts a new key and value into a #GHashTable similar to 369a2b269bae3315a2ea772b741fb62f683c1db5770Sven Neumann * g_hash_table_insert(). The difference is that if the key already exists 370a2b269bae3315a2ea772b741fb62f683c1db5770Sven Neumann * in the #GHashTable, it gets replaced by the new key. If you supplied a 371a52e2986cd4a2147cfc8d41ae23d98907caaf3a0Matthias Clasen * @value_destroy_func when creating the #GHashTable, the old value is freed 372a52e2986cd4a2147cfc8d41ae23d98907caaf3a0Matthias Clasen * using that function. If you supplied a @key_destroy_func when creating the 373a2b269bae3315a2ea772b741fb62f683c1db5770Sven Neumann * #GHashTable, the old key is freed using that function. 374a2b269bae3315a2ea772b741fb62f683c1db5770Sven Neumann **/ 375a2b269bae3315a2ea772b741fb62f683c1db5770Sven Neumannvoid 376a2b269bae3315a2ea772b741fb62f683c1db5770Sven Neumanng_hash_table_replace (GHashTable *hash_table, 377a2b269bae3315a2ea772b741fb62f683c1db5770Sven Neumann gpointer key, 378a2b269bae3315a2ea772b741fb62f683c1db5770Sven Neumann gpointer value) 379a2b269bae3315a2ea772b741fb62f683c1db5770Sven Neumann{ 380a2b269bae3315a2ea772b741fb62f683c1db5770Sven Neumann GHashNode **node; 381a2b269bae3315a2ea772b741fb62f683c1db5770Sven Neumann 382a2b269bae3315a2ea772b741fb62f683c1db5770Sven Neumann g_return_if_fail (hash_table != NULL); 3833e847a090cfd8495add631d43388c461b1a85716Tim Janik g_return_if_fail (hash_table->ref_count > 0); 384a2b269bae3315a2ea772b741fb62f683c1db5770Sven Neumann 385a2b269bae3315a2ea772b741fb62f683c1db5770Sven Neumann node = g_hash_table_lookup_node (hash_table, key); 386a2b269bae3315a2ea772b741fb62f683c1db5770Sven Neumann 387a2b269bae3315a2ea772b741fb62f683c1db5770Sven Neumann if (*node) 388a2b269bae3315a2ea772b741fb62f683c1db5770Sven Neumann { 389a2b269bae3315a2ea772b741fb62f683c1db5770Sven Neumann if (hash_table->key_destroy_func) 390a2b269bae3315a2ea772b741fb62f683c1db5770Sven Neumann hash_table->key_destroy_func ((*node)->key); 391a2b269bae3315a2ea772b741fb62f683c1db5770Sven Neumann 392a2b269bae3315a2ea772b741fb62f683c1db5770Sven Neumann if (hash_table->value_destroy_func) 393a2b269bae3315a2ea772b741fb62f683c1db5770Sven Neumann hash_table->value_destroy_func ((*node)->value); 394a2b269bae3315a2ea772b741fb62f683c1db5770Sven Neumann 395a2b269bae3315a2ea772b741fb62f683c1db5770Sven Neumann (*node)->key = key; 396d5492a983cfa048658af8b03f833ddb3c0cf355eEST (*node)->value = value; 397d5492a983cfa048658af8b03f833ddb3c0cf355eEST } 398d5492a983cfa048658af8b03f833ddb3c0cf355eEST else 399d5492a983cfa048658af8b03f833ddb3c0cf355eEST { 400d5492a983cfa048658af8b03f833ddb3c0cf355eEST *node = g_hash_node_new (key, value); 401d5492a983cfa048658af8b03f833ddb3c0cf355eEST hash_table->nnodes++; 4028079eb3456914a03618b92b48f75a71b25331acbOwen Taylor G_HASH_TABLE_RESIZE (hash_table); 4032e0320d57e417f7d1c838d729a99545db2228e9Owen Taylor } 4042e0320d57e417f7d1c838d729a99545db2228e9Owen Taylor} 4052e0320d57e417f7d1c838d729a99545db2228e9Owen Taylor 406a2b269bae3315a2ea772b741fb62f683c1db5770Sven Neumann/** 407a2b269bae3315a2ea772b741fb62f683c1db5770Sven Neumann * g_hash_table_remove: 408a2b269bae3315a2ea772b741fb62f683c1db5770Sven Neumann * @hash_table: a #GHashTable. 409a2b269bae3315a2ea772b741fb62f683c1db5770Sven Neumann * @key: the key to remove. 410a2b269bae3315a2ea772b741fb62f683c1db5770Sven Neumann * 411a2b269bae3315a2ea772b741fb62f683c1db5770Sven Neumann * Removes a key and its associated value from a #GHashTable. 412a2b269bae3315a2ea772b741fb62f683c1db5770Sven Neumann * 413a2b269bae3315a2ea772b741fb62f683c1db5770Sven Neumann * If the #GHashTable was created using g_hash_table_new_full(), the 414a52e2986cd4a2147cfc8d41ae23d98907caaf3a0Matthias Clasen * key and value are freed using the supplied destroy functions, otherwise 415a2b269bae3315a2ea772b741fb62f683c1db5770Sven Neumann * you have to make sure that any dynamically allocated values are freed 416a2b269bae3315a2ea772b741fb62f683c1db5770Sven Neumann * yourself. 417a2b269bae3315a2ea772b741fb62f683c1db5770Sven Neumann * 4183fa33317b7e9866793ce1ea32d069e8c9270caa2Matthias Clasen * Return value: %TRUE if the key was found and removed from the #GHashTable. 419a2b269bae3315a2ea772b741fb62f683c1db5770Sven Neumann **/ 4209a8c33db5cc37bc3c6bd4794a03f4b99a847ff4aTim Janikgboolean 421a2b269bae3315a2ea772b741fb62f683c1db5770Sven Neumanng_hash_table_remove (GHashTable *hash_table, 422a2b269bae3315a2ea772b741fb62f683c1db5770Sven Neumann gconstpointer key) 4232e0320d57e417f7d1c838d729a99545db2228e9Owen Taylor{ 424d5492a983cfa048658af8b03f833ddb3c0cf355eEST GHashNode **node, *dest; 4252d68cbbb7d37d3f265bf1087e6ddedcc58bc62beTim Janik 4269a8c33db5cc37bc3c6bd4794a03f4b99a847ff4aTim Janik g_return_val_if_fail (hash_table != NULL, FALSE); 4272d68cbbb7d37d3f265bf1087e6ddedcc58bc62beTim Janik 428d5492a983cfa048658af8b03f833ddb3c0cf355eEST node = g_hash_table_lookup_node (hash_table, key); 429d5492a983cfa048658af8b03f833ddb3c0cf355eEST if (*node) 4302e0320d57e417f7d1c838d729a99545db2228e9Owen Taylor { 431d5492a983cfa048658af8b03f833ddb3c0cf355eEST dest = *node; 432d5492a983cfa048658af8b03f833ddb3c0cf355eEST (*node) = dest->next; 433a2b269bae3315a2ea772b741fb62f683c1db5770Sven Neumann g_hash_node_destroy (dest, 434a2b269bae3315a2ea772b741fb62f683c1db5770Sven Neumann hash_table->key_destroy_func, 435a2b269bae3315a2ea772b741fb62f683c1db5770Sven Neumann hash_table->value_destroy_func); 4367519c2338ae484135b44bbb7eb49719aea8c4ca3Lauri Alanko hash_table->nnodes--; 4372d68cbbb7d37d3f265bf1087e6ddedcc58bc62beTim Janik 4388079eb3456914a03618b92b48f75a71b25331acbOwen Taylor G_HASH_TABLE_RESIZE (hash_table); 4399a8c33db5cc37bc3c6bd4794a03f4b99a847ff4aTim Janik 4409a8c33db5cc37bc3c6bd4794a03f4b99a847ff4aTim Janik return TRUE; 441448e792b0a9b092f9593eaa51e16acd8abe54c76Jeff Garzik } 4429a8c33db5cc37bc3c6bd4794a03f4b99a847ff4aTim Janik 4439a8c33db5cc37bc3c6bd4794a03f4b99a847ff4aTim Janik return FALSE; 4442e0320d57e417f7d1c838d729a99545db2228e9Owen Taylor} 4452e0320d57e417f7d1c838d729a99545db2228e9Owen Taylor 446a2b269bae3315a2ea772b741fb62f683c1db5770Sven Neumann/** 447a5b4b8bfb18838454d99bdee60294da07e5ef0d2Matthias Clasen * g_hash_table_remove_all: 448a5b4b8bfb18838454d99bdee60294da07e5ef0d2Matthias Clasen * @hash_table: a #GHashTable 449a5b4b8bfb18838454d99bdee60294da07e5ef0d2Matthias Clasen * 450a5b4b8bfb18838454d99bdee60294da07e5ef0d2Matthias Clasen * Removes all keys and their associated values from a #GHashTable. 451a5b4b8bfb18838454d99bdee60294da07e5ef0d2Matthias Clasen * 452a5b4b8bfb18838454d99bdee60294da07e5ef0d2Matthias Clasen * If the #GHashTable was created using g_hash_table_new_full(), the keys 453a5b4b8bfb18838454d99bdee60294da07e5ef0d2Matthias Clasen * and values are freed using the supplied destroy functions, otherwise you 454a5b4b8bfb18838454d99bdee60294da07e5ef0d2Matthias Clasen * have to make sure that any dynamically allocated values are freed 455a5b4b8bfb18838454d99bdee60294da07e5ef0d2Matthias Clasen * yourself. 456a5b4b8bfb18838454d99bdee60294da07e5ef0d2Matthias Clasen * 457a5b4b8bfb18838454d99bdee60294da07e5ef0d2Matthias Clasen * Since: 2.12 458a5b4b8bfb18838454d99bdee60294da07e5ef0d2Matthias Clasen **/ 459a5b4b8bfb18838454d99bdee60294da07e5ef0d2Matthias Clasenvoid 460a5b4b8bfb18838454d99bdee60294da07e5ef0d2Matthias Claseng_hash_table_remove_all (GHashTable *hash_table) 461a5b4b8bfb18838454d99bdee60294da07e5ef0d2Matthias Clasen{ 462a5b4b8bfb18838454d99bdee60294da07e5ef0d2Matthias Clasen guint i; 463a5b4b8bfb18838454d99bdee60294da07e5ef0d2Matthias Clasen 464a5b4b8bfb18838454d99bdee60294da07e5ef0d2Matthias Clasen g_return_if_fail (hash_table != NULL); 465a5b4b8bfb18838454d99bdee60294da07e5ef0d2Matthias Clasen 466a5b4b8bfb18838454d99bdee60294da07e5ef0d2Matthias Clasen for (i = 0; i < hash_table->size; i++) 467a5b4b8bfb18838454d99bdee60294da07e5ef0d2Matthias Clasen { 468a5b4b8bfb18838454d99bdee60294da07e5ef0d2Matthias Clasen g_hash_nodes_destroy (hash_table->nodes[i], 469a5b4b8bfb18838454d99bdee60294da07e5ef0d2Matthias Clasen hash_table->key_destroy_func, 470a5b4b8bfb18838454d99bdee60294da07e5ef0d2Matthias Clasen hash_table->value_destroy_func); 471a5b4b8bfb18838454d99bdee60294da07e5ef0d2Matthias Clasen hash_table->nodes[i] = NULL; 472a5b4b8bfb18838454d99bdee60294da07e5ef0d2Matthias Clasen } 473a5b4b8bfb18838454d99bdee60294da07e5ef0d2Matthias Clasen hash_table->nnodes = 0; 474a5b4b8bfb18838454d99bdee60294da07e5ef0d2Matthias Clasen 475a5b4b8bfb18838454d99bdee60294da07e5ef0d2Matthias Clasen G_HASH_TABLE_RESIZE (hash_table); 476a5b4b8bfb18838454d99bdee60294da07e5ef0d2Matthias Clasen} 477a5b4b8bfb18838454d99bdee60294da07e5ef0d2Matthias Clasen 478a5b4b8bfb18838454d99bdee60294da07e5ef0d2Matthias Clasen/** 479a2b269bae3315a2ea772b741fb62f683c1db5770Sven Neumann * g_hash_table_steal: 480a2b269bae3315a2ea772b741fb62f683c1db5770Sven Neumann * @hash_table: a #GHashTable. 481a2b269bae3315a2ea772b741fb62f683c1db5770Sven Neumann * @key: the key to remove. 482a2b269bae3315a2ea772b741fb62f683c1db5770Sven Neumann * 483a2b269bae3315a2ea772b741fb62f683c1db5770Sven Neumann * Removes a key and its associated value from a #GHashTable without 484a2b269bae3315a2ea772b741fb62f683c1db5770Sven Neumann * calling the key and value destroy functions. 485a2b269bae3315a2ea772b741fb62f683c1db5770Sven Neumann * 4863fa33317b7e9866793ce1ea32d069e8c9270caa2Matthias Clasen * Return value: %TRUE if the key was found and removed from the #GHashTable. 487a2b269bae3315a2ea772b741fb62f683c1db5770Sven Neumann **/ 4887519c2338ae484135b44bbb7eb49719aea8c4ca3Lauri Alankogboolean 489a2b269bae3315a2ea772b741fb62f683c1db5770Sven Neumanng_hash_table_steal (GHashTable *hash_table, 490a2b269bae3315a2ea772b741fb62f683c1db5770Sven Neumann gconstpointer key) 4917519c2338ae484135b44bbb7eb49719aea8c4ca3Lauri Alanko{ 492a2b269bae3315a2ea772b741fb62f683c1db5770Sven Neumann GHashNode **node, *dest; 4932d68cbbb7d37d3f265bf1087e6ddedcc58bc62beTim Janik 4942d68cbbb7d37d3f265bf1087e6ddedcc58bc62beTim Janik g_return_val_if_fail (hash_table != NULL, FALSE); 4952d68cbbb7d37d3f265bf1087e6ddedcc58bc62beTim Janik 496a2b269bae3315a2ea772b741fb62f683c1db5770Sven Neumann node = g_hash_table_lookup_node (hash_table, key); 497a2b269bae3315a2ea772b741fb62f683c1db5770Sven Neumann if (*node) 4982e0320d57e417f7d1c838d729a99545db2228e9Owen Taylor { 499a2b269bae3315a2ea772b741fb62f683c1db5770Sven Neumann dest = *node; 500a2b269bae3315a2ea772b741fb62f683c1db5770Sven Neumann (*node) = dest->next; 501a2b269bae3315a2ea772b741fb62f683c1db5770Sven Neumann g_hash_node_destroy (dest, NULL, NULL); 502a2b269bae3315a2ea772b741fb62f683c1db5770Sven Neumann hash_table->nnodes--; 503a2b269bae3315a2ea772b741fb62f683c1db5770Sven Neumann 5048079eb3456914a03618b92b48f75a71b25331acbOwen Taylor G_HASH_TABLE_RESIZE (hash_table); 505a2b269bae3315a2ea772b741fb62f683c1db5770Sven Neumann 5067519c2338ae484135b44bbb7eb49719aea8c4ca3Lauri Alanko return TRUE; 5072e0320d57e417f7d1c838d729a99545db2228e9Owen Taylor } 508a2b269bae3315a2ea772b741fb62f683c1db5770Sven Neumann 509a2b269bae3315a2ea772b741fb62f683c1db5770Sven Neumann return FALSE; 5102e0320d57e417f7d1c838d729a99545db2228e9Owen Taylor} 5112e0320d57e417f7d1c838d729a99545db2228e9Owen Taylor 512a2b269bae3315a2ea772b741fb62f683c1db5770Sven Neumann/** 513a5b4b8bfb18838454d99bdee60294da07e5ef0d2Matthias Clasen * g_hash_table_steal_all: 514a5b4b8bfb18838454d99bdee60294da07e5ef0d2Matthias Clasen * @hash_table: a #GHashTable. 515a5b4b8bfb18838454d99bdee60294da07e5ef0d2Matthias Clasen * 516a5b4b8bfb18838454d99bdee60294da07e5ef0d2Matthias Clasen * Removes all keys and their associated values from a #GHashTable 517a5b4b8bfb18838454d99bdee60294da07e5ef0d2Matthias Clasen * without calling the key and value destroy functions. 518a5b4b8bfb18838454d99bdee60294da07e5ef0d2Matthias Clasen * 519a5b4b8bfb18838454d99bdee60294da07e5ef0d2Matthias Clasen * Since: 2.12 520a5b4b8bfb18838454d99bdee60294da07e5ef0d2Matthias Clasen **/ 521a5b4b8bfb18838454d99bdee60294da07e5ef0d2Matthias Clasenvoid 522a5b4b8bfb18838454d99bdee60294da07e5ef0d2Matthias Claseng_hash_table_steal_all (GHashTable *hash_table) 523a5b4b8bfb18838454d99bdee60294da07e5ef0d2Matthias Clasen{ 524a5b4b8bfb18838454d99bdee60294da07e5ef0d2Matthias Clasen guint i; 525a5b4b8bfb18838454d99bdee60294da07e5ef0d2Matthias Clasen 526a5b4b8bfb18838454d99bdee60294da07e5ef0d2Matthias Clasen g_return_if_fail (hash_table != NULL); 527a5b4b8bfb18838454d99bdee60294da07e5ef0d2Matthias Clasen 528a5b4b8bfb18838454d99bdee60294da07e5ef0d2Matthias Clasen for (i = 0; i < hash_table->size; i++) 529a5b4b8bfb18838454d99bdee60294da07e5ef0d2Matthias Clasen { 530a5b4b8bfb18838454d99bdee60294da07e5ef0d2Matthias Clasen g_hash_nodes_destroy (hash_table->nodes[i], NULL, NULL); 531a5b4b8bfb18838454d99bdee60294da07e5ef0d2Matthias Clasen hash_table->nodes[i] = NULL; 532a5b4b8bfb18838454d99bdee60294da07e5ef0d2Matthias Clasen } 533a5b4b8bfb18838454d99bdee60294da07e5ef0d2Matthias Clasen 534a5b4b8bfb18838454d99bdee60294da07e5ef0d2Matthias Clasen hash_table->nnodes = 0; 535a5b4b8bfb18838454d99bdee60294da07e5ef0d2Matthias Clasen 536a5b4b8bfb18838454d99bdee60294da07e5ef0d2Matthias Clasen G_HASH_TABLE_RESIZE (hash_table); 537a5b4b8bfb18838454d99bdee60294da07e5ef0d2Matthias Clasen} 538a5b4b8bfb18838454d99bdee60294da07e5ef0d2Matthias Clasen 539a5b4b8bfb18838454d99bdee60294da07e5ef0d2Matthias Clasen/** 540a2b269bae3315a2ea772b741fb62f683c1db5770Sven Neumann * g_hash_table_foreach_remove: 541a2b269bae3315a2ea772b741fb62f683c1db5770Sven Neumann * @hash_table: a #GHashTable. 542a2b269bae3315a2ea772b741fb62f683c1db5770Sven Neumann * @func: the function to call for each key/value pair. 543a2b269bae3315a2ea772b741fb62f683c1db5770Sven Neumann * @user_data: user data to pass to the function. 544a2b269bae3315a2ea772b741fb62f683c1db5770Sven Neumann * 545a2b269bae3315a2ea772b741fb62f683c1db5770Sven Neumann * Calls the given function for each key/value pair in the #GHashTable. 546a52e2986cd4a2147cfc8d41ae23d98907caaf3a0Matthias Clasen * If the function returns %TRUE, then the key/value pair is removed from the 547a2b269bae3315a2ea772b741fb62f683c1db5770Sven Neumann * #GHashTable. If you supplied key or value destroy functions when creating 548a2b269bae3315a2ea772b741fb62f683c1db5770Sven Neumann * the #GHashTable, they are used to free the memory allocated for the removed 549a2b269bae3315a2ea772b741fb62f683c1db5770Sven Neumann * keys and values. 550a2b269bae3315a2ea772b741fb62f683c1db5770Sven Neumann * 551a2b269bae3315a2ea772b741fb62f683c1db5770Sven Neumann * Return value: the number of key/value pairs removed. 552a2b269bae3315a2ea772b741fb62f683c1db5770Sven Neumann **/ 553a2b269bae3315a2ea772b741fb62f683c1db5770Sven Neumannguint 554a2b269bae3315a2ea772b741fb62f683c1db5770Sven Neumanng_hash_table_foreach_remove (GHashTable *hash_table, 555a2b269bae3315a2ea772b741fb62f683c1db5770Sven Neumann GHRFunc func, 556a2b269bae3315a2ea772b741fb62f683c1db5770Sven Neumann gpointer user_data) 5572e0320d57e417f7d1c838d729a99545db2228e9Owen Taylor{ 558a2b269bae3315a2ea772b741fb62f683c1db5770Sven Neumann g_return_val_if_fail (hash_table != NULL, 0); 559a2b269bae3315a2ea772b741fb62f683c1db5770Sven Neumann g_return_val_if_fail (func != NULL, 0); 560a2b269bae3315a2ea772b741fb62f683c1db5770Sven Neumann 561a2b269bae3315a2ea772b741fb62f683c1db5770Sven Neumann return g_hash_table_foreach_remove_or_steal (hash_table, func, user_data, TRUE); 5622e0320d57e417f7d1c838d729a99545db2228e9Owen Taylor} 5632e0320d57e417f7d1c838d729a99545db2228e9Owen Taylor 564a2b269bae3315a2ea772b741fb62f683c1db5770Sven Neumann/** 565a2b269bae3315a2ea772b741fb62f683c1db5770Sven Neumann * g_hash_table_foreach_steal: 566a2b269bae3315a2ea772b741fb62f683c1db5770Sven Neumann * @hash_table: a #GHashTable. 567a2b269bae3315a2ea772b741fb62f683c1db5770Sven Neumann * @func: the function to call for each key/value pair. 568a2b269bae3315a2ea772b741fb62f683c1db5770Sven Neumann * @user_data: user data to pass to the function. 569a2b269bae3315a2ea772b741fb62f683c1db5770Sven Neumann * 570a2b269bae3315a2ea772b741fb62f683c1db5770Sven Neumann * Calls the given function for each key/value pair in the #GHashTable. 571a52e2986cd4a2147cfc8d41ae23d98907caaf3a0Matthias Clasen * If the function returns %TRUE, then the key/value pair is removed from the 572a2b269bae3315a2ea772b741fb62f683c1db5770Sven Neumann * #GHashTable, but no key or value destroy functions are called. 573a2b269bae3315a2ea772b741fb62f683c1db5770Sven Neumann * 574a2b269bae3315a2ea772b741fb62f683c1db5770Sven Neumann * Return value: the number of key/value pairs removed. 575a2b269bae3315a2ea772b741fb62f683c1db5770Sven Neumann **/ 576a2b269bae3315a2ea772b741fb62f683c1db5770Sven Neumannguint 577a2b269bae3315a2ea772b741fb62f683c1db5770Sven Neumanng_hash_table_foreach_steal (GHashTable *hash_table, 578a2b269bae3315a2ea772b741fb62f683c1db5770Sven Neumann GHRFunc func, 579a2b269bae3315a2ea772b741fb62f683c1db5770Sven Neumann gpointer user_data) 5802e0320d57e417f7d1c838d729a99545db2228e9Owen Taylor{ 581a2b269bae3315a2ea772b741fb62f683c1db5770Sven Neumann g_return_val_if_fail (hash_table != NULL, 0); 582a2b269bae3315a2ea772b741fb62f683c1db5770Sven Neumann g_return_val_if_fail (func != NULL, 0); 583a2b269bae3315a2ea772b741fb62f683c1db5770Sven Neumann 584a2b269bae3315a2ea772b741fb62f683c1db5770Sven Neumann return g_hash_table_foreach_remove_or_steal (hash_table, func, user_data, FALSE); 5852e0320d57e417f7d1c838d729a99545db2228e9Owen Taylor} 5862e0320d57e417f7d1c838d729a99545db2228e9Owen Taylor 587a2b269bae3315a2ea772b741fb62f683c1db5770Sven Neumannstatic guint 588a2b269bae3315a2ea772b741fb62f683c1db5770Sven Neumanng_hash_table_foreach_remove_or_steal (GHashTable *hash_table, 589a2b269bae3315a2ea772b741fb62f683c1db5770Sven Neumann GHRFunc func, 590a2b269bae3315a2ea772b741fb62f683c1db5770Sven Neumann gpointer user_data, 591a2b269bae3315a2ea772b741fb62f683c1db5770Sven Neumann gboolean notify) 592034e7c0339f64d4d52a53f2324daa2fca0332addManish Singh{ 593034e7c0339f64d4d52a53f2324daa2fca0332addManish Singh GHashNode *node, *prev; 59409b118f462fabb228ba26a498001f7c4e72bdde8Matthias Clasen gint i; 595d31ba84c8ea40b6f0199318e43cc2bb2e816c586Tim Janik guint deleted = 0; 5962d68cbbb7d37d3f265bf1087e6ddedcc58bc62beTim Janik 597034e7c0339f64d4d52a53f2324daa2fca0332addManish Singh for (i = 0; i < hash_table->size; i++) 598034e7c0339f64d4d52a53f2324daa2fca0332addManish Singh { 599034e7c0339f64d4d52a53f2324daa2fca0332addManish Singh restart: 6002d68cbbb7d37d3f265bf1087e6ddedcc58bc62beTim Janik 601034e7c0339f64d4d52a53f2324daa2fca0332addManish Singh prev = NULL; 6022d68cbbb7d37d3f265bf1087e6ddedcc58bc62beTim Janik 603034e7c0339f64d4d52a53f2324daa2fca0332addManish Singh for (node = hash_table->nodes[i]; node; prev = node, node = node->next) 604034e7c0339f64d4d52a53f2324daa2fca0332addManish Singh { 605034e7c0339f64d4d52a53f2324daa2fca0332addManish Singh if ((* func) (node->key, node->value, user_data)) 606034e7c0339f64d4d52a53f2324daa2fca0332addManish Singh { 607034e7c0339f64d4d52a53f2324daa2fca0332addManish Singh deleted += 1; 6082d68cbbb7d37d3f265bf1087e6ddedcc58bc62beTim Janik 609034e7c0339f64d4d52a53f2324daa2fca0332addManish Singh hash_table->nnodes -= 1; 6102d68cbbb7d37d3f265bf1087e6ddedcc58bc62beTim Janik 611034e7c0339f64d4d52a53f2324daa2fca0332addManish Singh if (prev) 612034e7c0339f64d4d52a53f2324daa2fca0332addManish Singh { 613034e7c0339f64d4d52a53f2324daa2fca0332addManish Singh prev->next = node->next; 614a2b269bae3315a2ea772b741fb62f683c1db5770Sven Neumann g_hash_node_destroy (node, 615faca80d619fb89332d25d32369c80026ef37ac2fOwen Taylor notify ? hash_table->key_destroy_func : NULL, 616faca80d619fb89332d25d32369c80026ef37ac2fOwen Taylor notify ? hash_table->value_destroy_func : NULL); 617034e7c0339f64d4d52a53f2324daa2fca0332addManish Singh node = prev; 618034e7c0339f64d4d52a53f2324daa2fca0332addManish Singh } 619034e7c0339f64d4d52a53f2324daa2fca0332addManish Singh else 620034e7c0339f64d4d52a53f2324daa2fca0332addManish Singh { 621034e7c0339f64d4d52a53f2324daa2fca0332addManish Singh hash_table->nodes[i] = node->next; 622a2b269bae3315a2ea772b741fb62f683c1db5770Sven Neumann g_hash_node_destroy (node, 623faca80d619fb89332d25d32369c80026ef37ac2fOwen Taylor notify ? hash_table->key_destroy_func : NULL, 624faca80d619fb89332d25d32369c80026ef37ac2fOwen Taylor notify ? hash_table->value_destroy_func : NULL); 625034e7c0339f64d4d52a53f2324daa2fca0332addManish Singh goto restart; 626034e7c0339f64d4d52a53f2324daa2fca0332addManish Singh } 627034e7c0339f64d4d52a53f2324daa2fca0332addManish Singh } 628034e7c0339f64d4d52a53f2324daa2fca0332addManish Singh } 629034e7c0339f64d4d52a53f2324daa2fca0332addManish Singh } 6302d68cbbb7d37d3f265bf1087e6ddedcc58bc62beTim Janik 6318079eb3456914a03618b92b48f75a71b25331acbOwen Taylor G_HASH_TABLE_RESIZE (hash_table); 6322d68cbbb7d37d3f265bf1087e6ddedcc58bc62beTim Janik 633034e7c0339f64d4d52a53f2324daa2fca0332addManish Singh return deleted; 634034e7c0339f64d4d52a53f2324daa2fca0332addManish Singh} 635034e7c0339f64d4d52a53f2324daa2fca0332addManish Singh 636a2b269bae3315a2ea772b741fb62f683c1db5770Sven Neumann/** 637a2b269bae3315a2ea772b741fb62f683c1db5770Sven Neumann * g_hash_table_foreach: 638a2b269bae3315a2ea772b741fb62f683c1db5770Sven Neumann * @hash_table: a #GHashTable. 639a2b269bae3315a2ea772b741fb62f683c1db5770Sven Neumann * @func: the function to call for each key/value pair. 640a2b269bae3315a2ea772b741fb62f683c1db5770Sven Neumann * @user_data: user data to pass to the function. 641a2b269bae3315a2ea772b741fb62f683c1db5770Sven Neumann * 642eb2f6f6fc1052abfa05f016ab2aed0cd0c338992Havoc Pennington * Calls the given function for each of the key/value pairs in the 643eb2f6f6fc1052abfa05f016ab2aed0cd0c338992Havoc Pennington * #GHashTable. The function is passed the key and value of each 644eb2f6f6fc1052abfa05f016ab2aed0cd0c338992Havoc Pennington * pair, and the given @user_data parameter. The hash table may not 645eb2f6f6fc1052abfa05f016ab2aed0cd0c338992Havoc Pennington * be modified while iterating over it (you can't add/remove 646eb2f6f6fc1052abfa05f016ab2aed0cd0c338992Havoc Pennington * items). To remove all items matching a predicate, use 64727096aedb58342fc8a25c17fa7d6647209425f4eMatthias Clasen * g_hash_table_foreach_remove(). 648a2b269bae3315a2ea772b741fb62f683c1db5770Sven Neumann **/ 6492e0320d57e417f7d1c838d729a99545db2228e9Owen Taylorvoid 6502e0320d57e417f7d1c838d729a99545db2228e9Owen Taylorg_hash_table_foreach (GHashTable *hash_table, 6512d68cbbb7d37d3f265bf1087e6ddedcc58bc62beTim Janik GHFunc func, 6522d68cbbb7d37d3f265bf1087e6ddedcc58bc62beTim Janik gpointer user_data) 6532e0320d57e417f7d1c838d729a99545db2228e9Owen Taylor{ 6542e0320d57e417f7d1c838d729a99545db2228e9Owen Taylor GHashNode *node; 6552e0320d57e417f7d1c838d729a99545db2228e9Owen Taylor gint i; 6562d68cbbb7d37d3f265bf1087e6ddedcc58bc62beTim Janik 6572d68cbbb7d37d3f265bf1087e6ddedcc58bc62beTim Janik g_return_if_fail (hash_table != NULL); 6582d68cbbb7d37d3f265bf1087e6ddedcc58bc62beTim Janik g_return_if_fail (func != NULL); 6592d68cbbb7d37d3f265bf1087e6ddedcc58bc62beTim Janik 6607519c2338ae484135b44bbb7eb49719aea8c4ca3Lauri Alanko for (i = 0; i < hash_table->size; i++) 6617519c2338ae484135b44bbb7eb49719aea8c4ca3Lauri Alanko for (node = hash_table->nodes[i]; node; node = node->next) 6627519c2338ae484135b44bbb7eb49719aea8c4ca3Lauri Alanko (* func) (node->key, node->value, user_data); 6632e0320d57e417f7d1c838d729a99545db2228e9Owen Taylor} 6642e0320d57e417f7d1c838d729a99545db2228e9Owen Taylor 665a2b269bae3315a2ea772b741fb62f683c1db5770Sven Neumann/** 666ee4e622d3724a6dfee8ce9463eccb31081cf852fTim Janik * g_hash_table_find: 667ee4e622d3724a6dfee8ce9463eccb31081cf852fTim Janik * @hash_table: a #GHashTable. 668ee4e622d3724a6dfee8ce9463eccb31081cf852fTim Janik * @predicate: function to test the key/value pairs for a certain property. 669ee4e622d3724a6dfee8ce9463eccb31081cf852fTim Janik * @user_data: user data to pass to the function. 670ee4e622d3724a6dfee8ce9463eccb31081cf852fTim Janik * 6713ce97fa284cbefdc2eb957f50a3a76d6ef923464Matthias Clasen * Calls the given function for key/value pairs in the #GHashTable until 6723ce97fa284cbefdc2eb957f50a3a76d6ef923464Matthias Clasen * @predicate returns %TRUE. The function is passed the key and value of 6733ce97fa284cbefdc2eb957f50a3a76d6ef923464Matthias Clasen * each pair, and the given @user_data parameter. The hash table may not 6743ce97fa284cbefdc2eb957f50a3a76d6ef923464Matthias Clasen * be modified while iterating over it (you can't add/remove items). 6753ce97fa284cbefdc2eb957f50a3a76d6ef923464Matthias Clasen * 676ee4e622d3724a6dfee8ce9463eccb31081cf852fTim Janik * Return value: The value of the first key/value pair is returned, for which 677ee4e622d3724a6dfee8ce9463eccb31081cf852fTim Janik * func evaluates to %TRUE. If no pair with the requested property is found, 6783ce97fa284cbefdc2eb957f50a3a76d6ef923464Matthias Clasen * %NULL is returned. 6793ce97fa284cbefdc2eb957f50a3a76d6ef923464Matthias Clasen * 6803ce97fa284cbefdc2eb957f50a3a76d6ef923464Matthias Clasen * Since: 2.4 681ee4e622d3724a6dfee8ce9463eccb31081cf852fTim Janik **/ 682ee4e622d3724a6dfee8ce9463eccb31081cf852fTim Janikgpointer 683ee4e622d3724a6dfee8ce9463eccb31081cf852fTim Janikg_hash_table_find (GHashTable *hash_table, 684ee4e622d3724a6dfee8ce9463eccb31081cf852fTim Janik GHRFunc predicate, 685ee4e622d3724a6dfee8ce9463eccb31081cf852fTim Janik gpointer user_data) 686ee4e622d3724a6dfee8ce9463eccb31081cf852fTim Janik{ 687ee4e622d3724a6dfee8ce9463eccb31081cf852fTim Janik GHashNode *node; 688ee4e622d3724a6dfee8ce9463eccb31081cf852fTim Janik gint i; 689ee4e622d3724a6dfee8ce9463eccb31081cf852fTim Janik 690ee4e622d3724a6dfee8ce9463eccb31081cf852fTim Janik g_return_val_if_fail (hash_table != NULL, NULL); 691ee4e622d3724a6dfee8ce9463eccb31081cf852fTim Janik g_return_val_if_fail (predicate != NULL, NULL); 692ee4e622d3724a6dfee8ce9463eccb31081cf852fTim Janik 693ee4e622d3724a6dfee8ce9463eccb31081cf852fTim Janik for (i = 0; i < hash_table->size; i++) 694ee4e622d3724a6dfee8ce9463eccb31081cf852fTim Janik for (node = hash_table->nodes[i]; node; node = node->next) 695ee4e622d3724a6dfee8ce9463eccb31081cf852fTim Janik if (predicate (node->key, node->value, user_data)) 696ee4e622d3724a6dfee8ce9463eccb31081cf852fTim Janik return node->value; 697ee4e622d3724a6dfee8ce9463eccb31081cf852fTim Janik return NULL; 698ee4e622d3724a6dfee8ce9463eccb31081cf852fTim Janik} 699ee4e622d3724a6dfee8ce9463eccb31081cf852fTim Janik 700ee4e622d3724a6dfee8ce9463eccb31081cf852fTim Janik/** 701a2b269bae3315a2ea772b741fb62f683c1db5770Sven Neumann * g_hash_table_size: 702a2b269bae3315a2ea772b741fb62f683c1db5770Sven Neumann * @hash_table: a #GHashTable. 703a2b269bae3315a2ea772b741fb62f683c1db5770Sven Neumann * 704a2b269bae3315a2ea772b741fb62f683c1db5770Sven Neumann * Returns the number of elements contained in the #GHashTable. 705a2b269bae3315a2ea772b741fb62f683c1db5770Sven Neumann * 706a2b269bae3315a2ea772b741fb62f683c1db5770Sven Neumann * Return value: the number of key/value pairs in the #GHashTable. 707a2b269bae3315a2ea772b741fb62f683c1db5770Sven Neumann **/ 708d31ba84c8ea40b6f0199318e43cc2bb2e816c586Tim Janikguint 7092d68cbbb7d37d3f265bf1087e6ddedcc58bc62beTim Janikg_hash_table_size (GHashTable *hash_table) 7107519c2338ae484135b44bbb7eb49719aea8c4ca3Lauri Alanko{ 7112d68cbbb7d37d3f265bf1087e6ddedcc58bc62beTim Janik g_return_val_if_fail (hash_table != NULL, 0); 7122d68cbbb7d37d3f265bf1087e6ddedcc58bc62beTim Janik 7137519c2338ae484135b44bbb7eb49719aea8c4ca3Lauri Alanko return hash_table->nnodes; 7147519c2338ae484135b44bbb7eb49719aea8c4ca3Lauri Alanko} 7152e0320d57e417f7d1c838d729a99545db2228e9Owen Taylor 7162e0320d57e417f7d1c838d729a99545db2228e9Owen Taylorstatic void 7172e0320d57e417f7d1c838d729a99545db2228e9Owen Taylorg_hash_table_resize (GHashTable *hash_table) 7182e0320d57e417f7d1c838d729a99545db2228e9Owen Taylor{ 7192e0320d57e417f7d1c838d729a99545db2228e9Owen Taylor GHashNode **new_nodes; 7202e0320d57e417f7d1c838d729a99545db2228e9Owen Taylor GHashNode *node; 7212e0320d57e417f7d1c838d729a99545db2228e9Owen Taylor GHashNode *next; 7222e0320d57e417f7d1c838d729a99545db2228e9Owen Taylor guint hash_val; 7232e0320d57e417f7d1c838d729a99545db2228e9Owen Taylor gint new_size; 7242e0320d57e417f7d1c838d729a99545db2228e9Owen Taylor gint i; 7258079eb3456914a03618b92b48f75a71b25331acbOwen Taylor 72673e6da92b298d48e3de9d775b5adc97cbff7b0aaSven Neumann new_size = g_spaced_primes_closest (hash_table->nnodes); 72773e6da92b298d48e3de9d775b5adc97cbff7b0aaSven Neumann new_size = CLAMP (new_size, HASH_TABLE_MIN_SIZE, HASH_TABLE_MAX_SIZE); 72873e6da92b298d48e3de9d775b5adc97cbff7b0aaSven Neumann 729448e792b0a9b092f9593eaa51e16acd8abe54c76Jeff Garzik new_nodes = g_new0 (GHashNode*, new_size); 7302d68cbbb7d37d3f265bf1087e6ddedcc58bc62beTim Janik 7317519c2338ae484135b44bbb7eb49719aea8c4ca3Lauri Alanko for (i = 0; i < hash_table->size; i++) 7327519c2338ae484135b44bbb7eb49719aea8c4ca3Lauri Alanko for (node = hash_table->nodes[i]; node; node = next) 7337519c2338ae484135b44bbb7eb49719aea8c4ca3Lauri Alanko { 7347519c2338ae484135b44bbb7eb49719aea8c4ca3Lauri Alanko next = node->next; 735448e792b0a9b092f9593eaa51e16acd8abe54c76Jeff Garzik 7367519c2338ae484135b44bbb7eb49719aea8c4ca3Lauri Alanko hash_val = (* hash_table->hash_func) (node->key) % new_size; 737448e792b0a9b092f9593eaa51e16acd8abe54c76Jeff Garzik 7387519c2338ae484135b44bbb7eb49719aea8c4ca3Lauri Alanko node->next = new_nodes[hash_val]; 7397519c2338ae484135b44bbb7eb49719aea8c4ca3Lauri Alanko new_nodes[hash_val] = node; 7407519c2338ae484135b44bbb7eb49719aea8c4ca3Lauri Alanko } 7412d68cbbb7d37d3f265bf1087e6ddedcc58bc62beTim Janik 7427519c2338ae484135b44bbb7eb49719aea8c4ca3Lauri Alanko g_free (hash_table->nodes); 7437519c2338ae484135b44bbb7eb49719aea8c4ca3Lauri Alanko hash_table->nodes = new_nodes; 7447519c2338ae484135b44bbb7eb49719aea8c4ca3Lauri Alanko hash_table->size = new_size; 7457519c2338ae484135b44bbb7eb49719aea8c4ca3Lauri Alanko} 7467519c2338ae484135b44bbb7eb49719aea8c4ca3Lauri Alanko 7472e0320d57e417f7d1c838d729a99545db2228e9Owen Taylorstatic GHashNode* 7482e0320d57e417f7d1c838d729a99545db2228e9Owen Taylorg_hash_node_new (gpointer key, 7492e0320d57e417f7d1c838d729a99545db2228e9Owen Taylor gpointer value) 7502e0320d57e417f7d1c838d729a99545db2228e9Owen Taylor{ 7510cba1b531d5d28890fa4f48359d4e7adacf2a603Tim Janik GHashNode *hash_node = g_slice_new (GHashNode); 7522d68cbbb7d37d3f265bf1087e6ddedcc58bc62beTim Janik 7532e0320d57e417f7d1c838d729a99545db2228e9Owen Taylor hash_node->key = key; 7542e0320d57e417f7d1c838d729a99545db2228e9Owen Taylor hash_node->value = value; 7552e0320d57e417f7d1c838d729a99545db2228e9Owen Taylor hash_node->next = NULL; 7562d68cbbb7d37d3f265bf1087e6ddedcc58bc62beTim Janik 7572e0320d57e417f7d1c838d729a99545db2228e9Owen Taylor return hash_node; 7582e0320d57e417f7d1c838d729a99545db2228e9Owen Taylor} 7592e0320d57e417f7d1c838d729a99545db2228e9Owen Taylor 7602e0320d57e417f7d1c838d729a99545db2228e9Owen Taylorstatic void 761a2b269bae3315a2ea772b741fb62f683c1db5770Sven Neumanng_hash_node_destroy (GHashNode *hash_node, 762a2b269bae3315a2ea772b741fb62f683c1db5770Sven Neumann GDestroyNotify key_destroy_func, 763a2b269bae3315a2ea772b741fb62f683c1db5770Sven Neumann GDestroyNotify value_destroy_func) 7642e0320d57e417f7d1c838d729a99545db2228e9Owen Taylor{ 765a2b269bae3315a2ea772b741fb62f683c1db5770Sven Neumann if (key_destroy_func) 766a2b269bae3315a2ea772b741fb62f683c1db5770Sven Neumann key_destroy_func (hash_node->key); 767a2b269bae3315a2ea772b741fb62f683c1db5770Sven Neumann if (value_destroy_func) 768a2b269bae3315a2ea772b741fb62f683c1db5770Sven Neumann value_destroy_func (hash_node->value); 7690cba1b531d5d28890fa4f48359d4e7adacf2a603Tim Janik g_slice_free (GHashNode, hash_node); 7702e0320d57e417f7d1c838d729a99545db2228e9Owen Taylor} 7712e0320d57e417f7d1c838d729a99545db2228e9Owen Taylor 7722e0320d57e417f7d1c838d729a99545db2228e9Owen Taylorstatic void 773a2b269bae3315a2ea772b741fb62f683c1db5770Sven Neumanng_hash_nodes_destroy (GHashNode *hash_node, 774a2b269bae3315a2ea772b741fb62f683c1db5770Sven Neumann GFreeFunc key_destroy_func, 775a2b269bae3315a2ea772b741fb62f683c1db5770Sven Neumann GFreeFunc value_destroy_func) 7762e0320d57e417f7d1c838d729a99545db2228e9Owen Taylor{ 777a436817718f7d4436c3ed1da4022f062dcb81c54Owen Taylor while (hash_node) 778a436817718f7d4436c3ed1da4022f062dcb81c54Owen Taylor { 779a436817718f7d4436c3ed1da4022f062dcb81c54Owen Taylor GHashNode *next = hash_node->next; 780a436817718f7d4436c3ed1da4022f062dcb81c54Owen Taylor if (key_destroy_func) 781a436817718f7d4436c3ed1da4022f062dcb81c54Owen Taylor key_destroy_func (hash_node->key); 782a436817718f7d4436c3ed1da4022f062dcb81c54Owen Taylor if (value_destroy_func) 783a436817718f7d4436c3ed1da4022f062dcb81c54Owen Taylor value_destroy_func (hash_node->value); 7840cba1b531d5d28890fa4f48359d4e7adacf2a603Tim Janik g_slice_free (GHashNode, hash_node); 785a436817718f7d4436c3ed1da4022f062dcb81c54Owen Taylor hash_node = next; 786448e792b0a9b092f9593eaa51e16acd8abe54c76Jeff Garzik } 787df9a49ec3cbb19e58be929548cfba12452c55d83Josh MacDonald} 788608a31b98e1420f487190871ee7312db2643d93dMatthias Clasen 7893e847a090cfd8495add631d43388c461b1a85716Tim Janik 790608a31b98e1420f487190871ee7312db2643d93dMatthias Clasen#define __G_HASH_C__ 791608a31b98e1420f487190871ee7312db2643d93dMatthias Clasen#include "galiasdef.c" 792