ghash.c revision c9bd7542e1a28ba9de60048361c0a97d251833e7
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 312e0320d57e417f7d1c838d729a99545db2228e9Owen Taylor#include "glib.h" 322e0320d57e417f7d1c838d729a99545db2228e9Owen Taylor 332e0320d57e417f7d1c838d729a99545db2228e9Owen Taylor 342e0320d57e417f7d1c838d729a99545db2228e9Owen Taylor#define HASH_TABLE_MIN_SIZE 11 352e0320d57e417f7d1c838d729a99545db2228e9Owen Taylor#define HASH_TABLE_MAX_SIZE 13845163 362e0320d57e417f7d1c838d729a99545db2228e9Owen Taylor 372e0320d57e417f7d1c838d729a99545db2228e9Owen Taylor 382e0320d57e417f7d1c838d729a99545db2228e9Owen Taylortypedef struct _GHashNode GHashNode; 392e0320d57e417f7d1c838d729a99545db2228e9Owen Taylor 402e0320d57e417f7d1c838d729a99545db2228e9Owen Taylorstruct _GHashNode 412e0320d57e417f7d1c838d729a99545db2228e9Owen Taylor{ 422e0320d57e417f7d1c838d729a99545db2228e9Owen Taylor gpointer key; 432e0320d57e417f7d1c838d729a99545db2228e9Owen Taylor gpointer value; 442e0320d57e417f7d1c838d729a99545db2228e9Owen Taylor GHashNode *next; 452e0320d57e417f7d1c838d729a99545db2228e9Owen Taylor}; 462e0320d57e417f7d1c838d729a99545db2228e9Owen Taylor 477519c2338ae484135b44bbb7eb49719aea8c4ca3Lauri Alankostruct _GHashTable 482e0320d57e417f7d1c838d729a99545db2228e9Owen Taylor{ 492e0320d57e417f7d1c838d729a99545db2228e9Owen Taylor gint size; 502e0320d57e417f7d1c838d729a99545db2228e9Owen Taylor gint nnodes; 512e0320d57e417f7d1c838d729a99545db2228e9Owen Taylor GHashNode **nodes; 522e0320d57e417f7d1c838d729a99545db2228e9Owen Taylor GHashFunc hash_func; 532e0320d57e417f7d1c838d729a99545db2228e9Owen Taylor GCompareFunc key_compare_func; 542e0320d57e417f7d1c838d729a99545db2228e9Owen Taylor}; 552e0320d57e417f7d1c838d729a99545db2228e9Owen Taylor 562e0320d57e417f7d1c838d729a99545db2228e9Owen Taylor 572d68cbbb7d37d3f265bf1087e6ddedcc58bc62beTim Janikstatic void g_hash_table_resize (GHashTable *hash_table); 58d5492a983cfa048658af8b03f833ddb3c0cf355eESTstatic GHashNode** g_hash_table_lookup_node (GHashTable *hash_table, 59d5492a983cfa048658af8b03f833ddb3c0cf355eEST gconstpointer key); 602d68cbbb7d37d3f265bf1087e6ddedcc58bc62beTim Janikstatic GHashNode* g_hash_node_new (gpointer key, 612d68cbbb7d37d3f265bf1087e6ddedcc58bc62beTim Janik gpointer value); 623a14f25fdfa715f1a79b74bcf3916885053ff307Tim Janikstatic void g_hash_node_destroy (GHashNode *hash_node); 633a14f25fdfa715f1a79b74bcf3916885053ff307Tim Janikstatic void g_hash_nodes_destroy (GHashNode *hash_node); 642e0320d57e417f7d1c838d729a99545db2228e9Owen Taylor 652e0320d57e417f7d1c838d729a99545db2228e9Owen Taylor 66b37e032581c44135b480dc74ae0355e72eef1372Sebastian WilhelmiG_LOCK_DEFINE_STATIC (g_hash_global); 67931ea952650b013b834041b91b0c37a748ffd449Owen Taylor 682e0320d57e417f7d1c838d729a99545db2228e9Owen Taylorstatic GMemChunk *node_mem_chunk = NULL; 692e0320d57e417f7d1c838d729a99545db2228e9Owen Taylorstatic GHashNode *node_free_list = NULL; 702e0320d57e417f7d1c838d729a99545db2228e9Owen Taylor 712e0320d57e417f7d1c838d729a99545db2228e9Owen Taylor 722e0320d57e417f7d1c838d729a99545db2228e9Owen TaylorGHashTable* 732e0320d57e417f7d1c838d729a99545db2228e9Owen Taylorg_hash_table_new (GHashFunc hash_func, 742e0320d57e417f7d1c838d729a99545db2228e9Owen Taylor GCompareFunc key_compare_func) 752e0320d57e417f7d1c838d729a99545db2228e9Owen Taylor{ 767519c2338ae484135b44bbb7eb49719aea8c4ca3Lauri Alanko GHashTable *hash_table; 772d68cbbb7d37d3f265bf1087e6ddedcc58bc62beTim Janik guint i; 782d68cbbb7d37d3f265bf1087e6ddedcc58bc62beTim Janik 797519c2338ae484135b44bbb7eb49719aea8c4ca3Lauri Alanko hash_table = g_new (GHashTable, 1); 807519c2338ae484135b44bbb7eb49719aea8c4ca3Lauri Alanko hash_table->size = HASH_TABLE_MIN_SIZE; 812e0320d57e417f7d1c838d729a99545db2228e9Owen Taylor hash_table->nnodes = 0; 827519c2338ae484135b44bbb7eb49719aea8c4ca3Lauri Alanko hash_table->hash_func = hash_func ? hash_func : g_direct_hash; 832e0320d57e417f7d1c838d729a99545db2228e9Owen Taylor hash_table->key_compare_func = key_compare_func; 847519c2338ae484135b44bbb7eb49719aea8c4ca3Lauri Alanko hash_table->nodes = g_new (GHashNode*, hash_table->size); 852d68cbbb7d37d3f265bf1087e6ddedcc58bc62beTim Janik 867519c2338ae484135b44bbb7eb49719aea8c4ca3Lauri Alanko for (i = 0; i < hash_table->size; i++) 877519c2338ae484135b44bbb7eb49719aea8c4ca3Lauri Alanko hash_table->nodes[i] = NULL; 882d68cbbb7d37d3f265bf1087e6ddedcc58bc62beTim Janik 897519c2338ae484135b44bbb7eb49719aea8c4ca3Lauri Alanko return hash_table; 902e0320d57e417f7d1c838d729a99545db2228e9Owen Taylor} 912e0320d57e417f7d1c838d729a99545db2228e9Owen Taylor 922e0320d57e417f7d1c838d729a99545db2228e9Owen Taylorvoid 932e0320d57e417f7d1c838d729a99545db2228e9Owen Taylorg_hash_table_destroy (GHashTable *hash_table) 942e0320d57e417f7d1c838d729a99545db2228e9Owen Taylor{ 952d68cbbb7d37d3f265bf1087e6ddedcc58bc62beTim Janik guint i; 962d68cbbb7d37d3f265bf1087e6ddedcc58bc62beTim Janik 972d68cbbb7d37d3f265bf1087e6ddedcc58bc62beTim Janik g_return_if_fail (hash_table != NULL); 982d68cbbb7d37d3f265bf1087e6ddedcc58bc62beTim Janik 997519c2338ae484135b44bbb7eb49719aea8c4ca3Lauri Alanko for (i = 0; i < hash_table->size; i++) 1003a14f25fdfa715f1a79b74bcf3916885053ff307Tim Janik g_hash_nodes_destroy (hash_table->nodes[i]); 1012d68cbbb7d37d3f265bf1087e6ddedcc58bc62beTim Janik 1027519c2338ae484135b44bbb7eb49719aea8c4ca3Lauri Alanko g_free (hash_table->nodes); 1037519c2338ae484135b44bbb7eb49719aea8c4ca3Lauri Alanko g_free (hash_table); 1042e0320d57e417f7d1c838d729a99545db2228e9Owen Taylor} 1052e0320d57e417f7d1c838d729a99545db2228e9Owen Taylor 106d5492a983cfa048658af8b03f833ddb3c0cf355eESTstatic inline GHashNode** 107d5492a983cfa048658af8b03f833ddb3c0cf355eESTg_hash_table_lookup_node (GHashTable *hash_table, 108d5492a983cfa048658af8b03f833ddb3c0cf355eEST gconstpointer key) 1092e0320d57e417f7d1c838d729a99545db2228e9Owen Taylor{ 110d5492a983cfa048658af8b03f833ddb3c0cf355eEST GHashNode **node; 1112d68cbbb7d37d3f265bf1087e6ddedcc58bc62beTim Janik 112d5492a983cfa048658af8b03f833ddb3c0cf355eEST node = &hash_table->nodes 113d5492a983cfa048658af8b03f833ddb3c0cf355eEST [(* hash_table->hash_func) (key) % hash_table->size]; 1142d68cbbb7d37d3f265bf1087e6ddedcc58bc62beTim Janik 1152d68cbbb7d37d3f265bf1087e6ddedcc58bc62beTim Janik /* Hash table lookup needs to be fast. 1162d68cbbb7d37d3f265bf1087e6ddedcc58bc62beTim Janik * We therefore remove the extra conditional of testing 1172d68cbbb7d37d3f265bf1087e6ddedcc58bc62beTim Janik * whether to call the key_compare_func or not from 1182d68cbbb7d37d3f265bf1087e6ddedcc58bc62beTim Janik * the inner loop. 1192d68cbbb7d37d3f265bf1087e6ddedcc58bc62beTim Janik */ 1202d68cbbb7d37d3f265bf1087e6ddedcc58bc62beTim Janik if (hash_table->key_compare_func) 121d5492a983cfa048658af8b03f833ddb3c0cf355eEST while (*node && !(*hash_table->key_compare_func) ((*node)->key, key)) 122d5492a983cfa048658af8b03f833ddb3c0cf355eEST node = &(*node)->next; 1232d68cbbb7d37d3f265bf1087e6ddedcc58bc62beTim Janik else 124d5492a983cfa048658af8b03f833ddb3c0cf355eEST while (*node && (*node)->key != key) 125d5492a983cfa048658af8b03f833ddb3c0cf355eEST node = &(*node)->next; 1262d68cbbb7d37d3f265bf1087e6ddedcc58bc62beTim Janik 1272d68cbbb7d37d3f265bf1087e6ddedcc58bc62beTim Janik return node; 1282d68cbbb7d37d3f265bf1087e6ddedcc58bc62beTim Janik} 1292e0320d57e417f7d1c838d729a99545db2228e9Owen Taylor 1302d68cbbb7d37d3f265bf1087e6ddedcc58bc62beTim Janikgpointer 1312d68cbbb7d37d3f265bf1087e6ddedcc58bc62beTim Janikg_hash_table_lookup (GHashTable *hash_table, 1322d68cbbb7d37d3f265bf1087e6ddedcc58bc62beTim Janik gconstpointer key) 1332d68cbbb7d37d3f265bf1087e6ddedcc58bc62beTim Janik{ 1342d68cbbb7d37d3f265bf1087e6ddedcc58bc62beTim Janik GHashNode *node; 1352d68cbbb7d37d3f265bf1087e6ddedcc58bc62beTim Janik 1362d68cbbb7d37d3f265bf1087e6ddedcc58bc62beTim Janik g_return_val_if_fail (hash_table != NULL, NULL); 1372d68cbbb7d37d3f265bf1087e6ddedcc58bc62beTim Janik 138d5492a983cfa048658af8b03f833ddb3c0cf355eEST node = *g_hash_table_lookup_node (hash_table, key); 1392d68cbbb7d37d3f265bf1087e6ddedcc58bc62beTim Janik 1402d68cbbb7d37d3f265bf1087e6ddedcc58bc62beTim Janik return node ? node->value : NULL; 1412d68cbbb7d37d3f265bf1087e6ddedcc58bc62beTim Janik} 1427401460a60504dad7b77219d0ba3d93112e12444Manish Singh 1432d68cbbb7d37d3f265bf1087e6ddedcc58bc62beTim Janikvoid 1442d68cbbb7d37d3f265bf1087e6ddedcc58bc62beTim Janikg_hash_table_insert (GHashTable *hash_table, 1452d68cbbb7d37d3f265bf1087e6ddedcc58bc62beTim Janik gpointer key, 1462d68cbbb7d37d3f265bf1087e6ddedcc58bc62beTim Janik gpointer value) 1472d68cbbb7d37d3f265bf1087e6ddedcc58bc62beTim Janik{ 148d5492a983cfa048658af8b03f833ddb3c0cf355eEST GHashNode **node; 1492d68cbbb7d37d3f265bf1087e6ddedcc58bc62beTim Janik 1502d68cbbb7d37d3f265bf1087e6ddedcc58bc62beTim Janik g_return_if_fail (hash_table != NULL); 1512d68cbbb7d37d3f265bf1087e6ddedcc58bc62beTim Janik 152d5492a983cfa048658af8b03f833ddb3c0cf355eEST node = g_hash_table_lookup_node (hash_table, key); 153d5492a983cfa048658af8b03f833ddb3c0cf355eEST 154d5492a983cfa048658af8b03f833ddb3c0cf355eEST if (*node) 1557519c2338ae484135b44bbb7eb49719aea8c4ca3Lauri Alanko { 1567519c2338ae484135b44bbb7eb49719aea8c4ca3Lauri Alanko /* do not reset node->key in this place, keeping 1577519c2338ae484135b44bbb7eb49719aea8c4ca3Lauri Alanko * the old key might be intended. 1587519c2338ae484135b44bbb7eb49719aea8c4ca3Lauri Alanko * a g_hash_table_remove/g_hash_table_insert pair 1597519c2338ae484135b44bbb7eb49719aea8c4ca3Lauri Alanko * can be used otherwise. 1607519c2338ae484135b44bbb7eb49719aea8c4ca3Lauri Alanko * 1617519c2338ae484135b44bbb7eb49719aea8c4ca3Lauri Alanko * node->key = key; */ 162d5492a983cfa048658af8b03f833ddb3c0cf355eEST (*node)->value = value; 163d5492a983cfa048658af8b03f833ddb3c0cf355eEST } 164d5492a983cfa048658af8b03f833ddb3c0cf355eEST else 165d5492a983cfa048658af8b03f833ddb3c0cf355eEST { 166d5492a983cfa048658af8b03f833ddb3c0cf355eEST *node = g_hash_node_new (key, value); 167d5492a983cfa048658af8b03f833ddb3c0cf355eEST hash_table->nnodes++; 16884114c5321e4d7e4701f77f7f0e2b9b739d4035cSebastian Wilhelmi g_hash_table_resize (hash_table); 1692e0320d57e417f7d1c838d729a99545db2228e9Owen Taylor } 1702e0320d57e417f7d1c838d729a99545db2228e9Owen Taylor} 1712e0320d57e417f7d1c838d729a99545db2228e9Owen Taylor 1722e0320d57e417f7d1c838d729a99545db2228e9Owen Taylorvoid 1732d68cbbb7d37d3f265bf1087e6ddedcc58bc62beTim Janikg_hash_table_remove (GHashTable *hash_table, 1742e0320d57e417f7d1c838d729a99545db2228e9Owen Taylor gconstpointer key) 1752e0320d57e417f7d1c838d729a99545db2228e9Owen Taylor{ 176d5492a983cfa048658af8b03f833ddb3c0cf355eEST GHashNode **node, *dest; 1772d68cbbb7d37d3f265bf1087e6ddedcc58bc62beTim Janik 1782d68cbbb7d37d3f265bf1087e6ddedcc58bc62beTim Janik g_return_if_fail (hash_table != NULL); 1792d68cbbb7d37d3f265bf1087e6ddedcc58bc62beTim Janik 180d5492a983cfa048658af8b03f833ddb3c0cf355eEST node = g_hash_table_lookup_node (hash_table, key); 181448e792b0a9b092f9593eaa51e16acd8abe54c76Jeff Garzik 182d5492a983cfa048658af8b03f833ddb3c0cf355eEST if (*node) 1832e0320d57e417f7d1c838d729a99545db2228e9Owen Taylor { 184d5492a983cfa048658af8b03f833ddb3c0cf355eEST dest = *node; 185d5492a983cfa048658af8b03f833ddb3c0cf355eEST (*node) = dest->next; 186d5492a983cfa048658af8b03f833ddb3c0cf355eEST g_hash_node_destroy (dest); 1877519c2338ae484135b44bbb7eb49719aea8c4ca3Lauri Alanko hash_table->nnodes--; 1882d68cbbb7d37d3f265bf1087e6ddedcc58bc62beTim Janik 18984114c5321e4d7e4701f77f7f0e2b9b739d4035cSebastian Wilhelmi g_hash_table_resize (hash_table); 190448e792b0a9b092f9593eaa51e16acd8abe54c76Jeff Garzik } 1912e0320d57e417f7d1c838d729a99545db2228e9Owen Taylor} 1922e0320d57e417f7d1c838d729a99545db2228e9Owen Taylor 1937519c2338ae484135b44bbb7eb49719aea8c4ca3Lauri Alankogboolean 1945b52f015356729919cfd3b68cd5ac3c27a35e147Lauri Alankog_hash_table_lookup_extended (GHashTable *hash_table, 1955b52f015356729919cfd3b68cd5ac3c27a35e147Lauri Alanko gconstpointer lookup_key, 1965b52f015356729919cfd3b68cd5ac3c27a35e147Lauri Alanko gpointer *orig_key, 1975b52f015356729919cfd3b68cd5ac3c27a35e147Lauri Alanko gpointer *value) 1987519c2338ae484135b44bbb7eb49719aea8c4ca3Lauri Alanko{ 1997519c2338ae484135b44bbb7eb49719aea8c4ca3Lauri Alanko GHashNode *node; 2002d68cbbb7d37d3f265bf1087e6ddedcc58bc62beTim Janik 2012d68cbbb7d37d3f265bf1087e6ddedcc58bc62beTim Janik g_return_val_if_fail (hash_table != NULL, FALSE); 2022d68cbbb7d37d3f265bf1087e6ddedcc58bc62beTim Janik 203d5492a983cfa048658af8b03f833ddb3c0cf355eEST node = *g_hash_table_lookup_node (hash_table, lookup_key); 2042d68cbbb7d37d3f265bf1087e6ddedcc58bc62beTim Janik 2057519c2338ae484135b44bbb7eb49719aea8c4ca3Lauri Alanko if (node) 2062e0320d57e417f7d1c838d729a99545db2228e9Owen Taylor { 2077519c2338ae484135b44bbb7eb49719aea8c4ca3Lauri Alanko if (orig_key) 2087519c2338ae484135b44bbb7eb49719aea8c4ca3Lauri Alanko *orig_key = node->key; 2097519c2338ae484135b44bbb7eb49719aea8c4ca3Lauri Alanko if (value) 2107519c2338ae484135b44bbb7eb49719aea8c4ca3Lauri Alanko *value = node->value; 2117519c2338ae484135b44bbb7eb49719aea8c4ca3Lauri Alanko return TRUE; 2122e0320d57e417f7d1c838d729a99545db2228e9Owen Taylor } 2137519c2338ae484135b44bbb7eb49719aea8c4ca3Lauri Alanko else 2147519c2338ae484135b44bbb7eb49719aea8c4ca3Lauri Alanko return FALSE; 2152e0320d57e417f7d1c838d729a99545db2228e9Owen Taylor} 2162e0320d57e417f7d1c838d729a99545db2228e9Owen Taylor 2172e0320d57e417f7d1c838d729a99545db2228e9Owen Taylorvoid 2182e0320d57e417f7d1c838d729a99545db2228e9Owen Taylorg_hash_table_freeze (GHashTable *hash_table) 2192e0320d57e417f7d1c838d729a99545db2228e9Owen Taylor{ 22084114c5321e4d7e4701f77f7f0e2b9b739d4035cSebastian Wilhelmi#ifdef G_ENABLE_DEBUG 22184114c5321e4d7e4701f77f7f0e2b9b739d4035cSebastian Wilhelmi static gboolean first_call = TRUE; 22284114c5321e4d7e4701f77f7f0e2b9b739d4035cSebastian Wilhelmi 22384114c5321e4d7e4701f77f7f0e2b9b739d4035cSebastian Wilhelmi if (first_call) 22484114c5321e4d7e4701f77f7f0e2b9b739d4035cSebastian Wilhelmi { 22584114c5321e4d7e4701f77f7f0e2b9b739d4035cSebastian Wilhelmi g_warning("g_hash_table_freeze and g_hash_table_thaw are deprecated."); 22684114c5321e4d7e4701f77f7f0e2b9b739d4035cSebastian Wilhelmi first_call = FALSE; 22784114c5321e4d7e4701f77f7f0e2b9b739d4035cSebastian Wilhelmi } 22884114c5321e4d7e4701f77f7f0e2b9b739d4035cSebastian Wilhelmi#endif /* G_ENABLE_DEBUG */ 2292e0320d57e417f7d1c838d729a99545db2228e9Owen Taylor} 2302e0320d57e417f7d1c838d729a99545db2228e9Owen Taylor 2312e0320d57e417f7d1c838d729a99545db2228e9Owen Taylorvoid 2322e0320d57e417f7d1c838d729a99545db2228e9Owen Taylorg_hash_table_thaw (GHashTable *hash_table) 2332e0320d57e417f7d1c838d729a99545db2228e9Owen Taylor{ 2342e0320d57e417f7d1c838d729a99545db2228e9Owen Taylor} 2352e0320d57e417f7d1c838d729a99545db2228e9Owen Taylor 236d31ba84c8ea40b6f0199318e43cc2bb2e816c586Tim Janikguint 2372d68cbbb7d37d3f265bf1087e6ddedcc58bc62beTim Janikg_hash_table_foreach_remove (GHashTable *hash_table, 2382d68cbbb7d37d3f265bf1087e6ddedcc58bc62beTim Janik GHRFunc func, 2392d68cbbb7d37d3f265bf1087e6ddedcc58bc62beTim Janik gpointer user_data) 240034e7c0339f64d4d52a53f2324daa2fca0332addManish Singh{ 241034e7c0339f64d4d52a53f2324daa2fca0332addManish Singh GHashNode *node, *prev; 2422d68cbbb7d37d3f265bf1087e6ddedcc58bc62beTim Janik guint i; 243d31ba84c8ea40b6f0199318e43cc2bb2e816c586Tim Janik guint deleted = 0; 2442d68cbbb7d37d3f265bf1087e6ddedcc58bc62beTim Janik 2452d68cbbb7d37d3f265bf1087e6ddedcc58bc62beTim Janik g_return_val_if_fail (hash_table != NULL, 0); 2462d68cbbb7d37d3f265bf1087e6ddedcc58bc62beTim Janik g_return_val_if_fail (func != NULL, 0); 2472d68cbbb7d37d3f265bf1087e6ddedcc58bc62beTim Janik 248034e7c0339f64d4d52a53f2324daa2fca0332addManish Singh for (i = 0; i < hash_table->size; i++) 249034e7c0339f64d4d52a53f2324daa2fca0332addManish Singh { 250034e7c0339f64d4d52a53f2324daa2fca0332addManish Singh restart: 2512d68cbbb7d37d3f265bf1087e6ddedcc58bc62beTim Janik 252034e7c0339f64d4d52a53f2324daa2fca0332addManish Singh prev = NULL; 2532d68cbbb7d37d3f265bf1087e6ddedcc58bc62beTim Janik 254034e7c0339f64d4d52a53f2324daa2fca0332addManish Singh for (node = hash_table->nodes[i]; node; prev = node, node = node->next) 255034e7c0339f64d4d52a53f2324daa2fca0332addManish Singh { 256034e7c0339f64d4d52a53f2324daa2fca0332addManish Singh if ((* func) (node->key, node->value, user_data)) 257034e7c0339f64d4d52a53f2324daa2fca0332addManish Singh { 258034e7c0339f64d4d52a53f2324daa2fca0332addManish Singh deleted += 1; 2592d68cbbb7d37d3f265bf1087e6ddedcc58bc62beTim Janik 260034e7c0339f64d4d52a53f2324daa2fca0332addManish Singh hash_table->nnodes -= 1; 2612d68cbbb7d37d3f265bf1087e6ddedcc58bc62beTim Janik 262034e7c0339f64d4d52a53f2324daa2fca0332addManish Singh if (prev) 263034e7c0339f64d4d52a53f2324daa2fca0332addManish Singh { 264034e7c0339f64d4d52a53f2324daa2fca0332addManish Singh prev->next = node->next; 2653a14f25fdfa715f1a79b74bcf3916885053ff307Tim Janik g_hash_node_destroy (node); 266034e7c0339f64d4d52a53f2324daa2fca0332addManish Singh node = prev; 267034e7c0339f64d4d52a53f2324daa2fca0332addManish Singh } 268034e7c0339f64d4d52a53f2324daa2fca0332addManish Singh else 269034e7c0339f64d4d52a53f2324daa2fca0332addManish Singh { 270034e7c0339f64d4d52a53f2324daa2fca0332addManish Singh hash_table->nodes[i] = node->next; 2713a14f25fdfa715f1a79b74bcf3916885053ff307Tim Janik g_hash_node_destroy (node); 272034e7c0339f64d4d52a53f2324daa2fca0332addManish Singh goto restart; 273034e7c0339f64d4d52a53f2324daa2fca0332addManish Singh } 274034e7c0339f64d4d52a53f2324daa2fca0332addManish Singh } 275034e7c0339f64d4d52a53f2324daa2fca0332addManish Singh } 276034e7c0339f64d4d52a53f2324daa2fca0332addManish Singh } 2772d68cbbb7d37d3f265bf1087e6ddedcc58bc62beTim Janik 27884114c5321e4d7e4701f77f7f0e2b9b739d4035cSebastian Wilhelmi g_hash_table_resize (hash_table); 2792d68cbbb7d37d3f265bf1087e6ddedcc58bc62beTim Janik 280034e7c0339f64d4d52a53f2324daa2fca0332addManish Singh return deleted; 281034e7c0339f64d4d52a53f2324daa2fca0332addManish Singh} 282034e7c0339f64d4d52a53f2324daa2fca0332addManish Singh 2832e0320d57e417f7d1c838d729a99545db2228e9Owen Taylorvoid 2842e0320d57e417f7d1c838d729a99545db2228e9Owen Taylorg_hash_table_foreach (GHashTable *hash_table, 2852d68cbbb7d37d3f265bf1087e6ddedcc58bc62beTim Janik GHFunc func, 2862d68cbbb7d37d3f265bf1087e6ddedcc58bc62beTim Janik gpointer user_data) 2872e0320d57e417f7d1c838d729a99545db2228e9Owen Taylor{ 2882e0320d57e417f7d1c838d729a99545db2228e9Owen Taylor GHashNode *node; 2892e0320d57e417f7d1c838d729a99545db2228e9Owen Taylor gint i; 2902d68cbbb7d37d3f265bf1087e6ddedcc58bc62beTim Janik 2912d68cbbb7d37d3f265bf1087e6ddedcc58bc62beTim Janik g_return_if_fail (hash_table != NULL); 2922d68cbbb7d37d3f265bf1087e6ddedcc58bc62beTim Janik g_return_if_fail (func != NULL); 2932d68cbbb7d37d3f265bf1087e6ddedcc58bc62beTim Janik 2947519c2338ae484135b44bbb7eb49719aea8c4ca3Lauri Alanko for (i = 0; i < hash_table->size; i++) 2957519c2338ae484135b44bbb7eb49719aea8c4ca3Lauri Alanko for (node = hash_table->nodes[i]; node; node = node->next) 2967519c2338ae484135b44bbb7eb49719aea8c4ca3Lauri Alanko (* func) (node->key, node->value, user_data); 2972e0320d57e417f7d1c838d729a99545db2228e9Owen Taylor} 2982e0320d57e417f7d1c838d729a99545db2228e9Owen Taylor 2997519c2338ae484135b44bbb7eb49719aea8c4ca3Lauri Alanko/* Returns the number of elements contained in the hash table. */ 300d31ba84c8ea40b6f0199318e43cc2bb2e816c586Tim Janikguint 3012d68cbbb7d37d3f265bf1087e6ddedcc58bc62beTim Janikg_hash_table_size (GHashTable *hash_table) 3027519c2338ae484135b44bbb7eb49719aea8c4ca3Lauri Alanko{ 3032d68cbbb7d37d3f265bf1087e6ddedcc58bc62beTim Janik g_return_val_if_fail (hash_table != NULL, 0); 3042d68cbbb7d37d3f265bf1087e6ddedcc58bc62beTim Janik 3057519c2338ae484135b44bbb7eb49719aea8c4ca3Lauri Alanko return hash_table->nnodes; 3067519c2338ae484135b44bbb7eb49719aea8c4ca3Lauri Alanko} 3072e0320d57e417f7d1c838d729a99545db2228e9Owen Taylor 3082e0320d57e417f7d1c838d729a99545db2228e9Owen Taylorstatic void 3092e0320d57e417f7d1c838d729a99545db2228e9Owen Taylorg_hash_table_resize (GHashTable *hash_table) 3102e0320d57e417f7d1c838d729a99545db2228e9Owen Taylor{ 3112e0320d57e417f7d1c838d729a99545db2228e9Owen Taylor GHashNode **new_nodes; 3122e0320d57e417f7d1c838d729a99545db2228e9Owen Taylor GHashNode *node; 3132e0320d57e417f7d1c838d729a99545db2228e9Owen Taylor GHashNode *next; 3142e0320d57e417f7d1c838d729a99545db2228e9Owen Taylor gfloat nodes_per_list; 3152e0320d57e417f7d1c838d729a99545db2228e9Owen Taylor guint hash_val; 3162e0320d57e417f7d1c838d729a99545db2228e9Owen Taylor gint new_size; 3172e0320d57e417f7d1c838d729a99545db2228e9Owen Taylor gint i; 3182d68cbbb7d37d3f265bf1087e6ddedcc58bc62beTim Janik 3197519c2338ae484135b44bbb7eb49719aea8c4ca3Lauri Alanko nodes_per_list = (gfloat) hash_table->nnodes / (gfloat) hash_table->size; 3202d68cbbb7d37d3f265bf1087e6ddedcc58bc62beTim Janik 3217519c2338ae484135b44bbb7eb49719aea8c4ca3Lauri Alanko if ((nodes_per_list > 0.3 || hash_table->size <= HASH_TABLE_MIN_SIZE) && 3227519c2338ae484135b44bbb7eb49719aea8c4ca3Lauri Alanko (nodes_per_list < 3.0 || hash_table->size >= HASH_TABLE_MAX_SIZE)) 3237519c2338ae484135b44bbb7eb49719aea8c4ca3Lauri Alanko return; 3242d68cbbb7d37d3f265bf1087e6ddedcc58bc62beTim Janik 3257401460a60504dad7b77219d0ba3d93112e12444Manish Singh new_size = CLAMP(g_spaced_primes_closest (hash_table->nnodes), 3267519c2338ae484135b44bbb7eb49719aea8c4ca3Lauri Alanko HASH_TABLE_MIN_SIZE, 3277519c2338ae484135b44bbb7eb49719aea8c4ca3Lauri Alanko HASH_TABLE_MAX_SIZE); 328448e792b0a9b092f9593eaa51e16acd8abe54c76Jeff Garzik new_nodes = g_new0 (GHashNode*, new_size); 3292d68cbbb7d37d3f265bf1087e6ddedcc58bc62beTim Janik 3307519c2338ae484135b44bbb7eb49719aea8c4ca3Lauri Alanko for (i = 0; i < hash_table->size; i++) 3317519c2338ae484135b44bbb7eb49719aea8c4ca3Lauri Alanko for (node = hash_table->nodes[i]; node; node = next) 3327519c2338ae484135b44bbb7eb49719aea8c4ca3Lauri Alanko { 3337519c2338ae484135b44bbb7eb49719aea8c4ca3Lauri Alanko next = node->next; 334448e792b0a9b092f9593eaa51e16acd8abe54c76Jeff Garzik 3357519c2338ae484135b44bbb7eb49719aea8c4ca3Lauri Alanko hash_val = (* hash_table->hash_func) (node->key) % new_size; 336448e792b0a9b092f9593eaa51e16acd8abe54c76Jeff Garzik 3377519c2338ae484135b44bbb7eb49719aea8c4ca3Lauri Alanko node->next = new_nodes[hash_val]; 3387519c2338ae484135b44bbb7eb49719aea8c4ca3Lauri Alanko new_nodes[hash_val] = node; 3397519c2338ae484135b44bbb7eb49719aea8c4ca3Lauri Alanko } 3402d68cbbb7d37d3f265bf1087e6ddedcc58bc62beTim Janik 3417519c2338ae484135b44bbb7eb49719aea8c4ca3Lauri Alanko g_free (hash_table->nodes); 3427519c2338ae484135b44bbb7eb49719aea8c4ca3Lauri Alanko hash_table->nodes = new_nodes; 3437519c2338ae484135b44bbb7eb49719aea8c4ca3Lauri Alanko hash_table->size = new_size; 3447519c2338ae484135b44bbb7eb49719aea8c4ca3Lauri Alanko} 3457519c2338ae484135b44bbb7eb49719aea8c4ca3Lauri Alanko 3462e0320d57e417f7d1c838d729a99545db2228e9Owen Taylorstatic GHashNode* 3472e0320d57e417f7d1c838d729a99545db2228e9Owen Taylorg_hash_node_new (gpointer key, 3482e0320d57e417f7d1c838d729a99545db2228e9Owen Taylor gpointer value) 3492e0320d57e417f7d1c838d729a99545db2228e9Owen Taylor{ 3502e0320d57e417f7d1c838d729a99545db2228e9Owen Taylor GHashNode *hash_node; 3512d68cbbb7d37d3f265bf1087e6ddedcc58bc62beTim Janik 352b2e318ff3ecc50d72121a4e8561442a6d79a7a84Tim Janik G_LOCK (g_hash_global); 3532e0320d57e417f7d1c838d729a99545db2228e9Owen Taylor if (node_free_list) 3542e0320d57e417f7d1c838d729a99545db2228e9Owen Taylor { 3552e0320d57e417f7d1c838d729a99545db2228e9Owen Taylor hash_node = node_free_list; 3562e0320d57e417f7d1c838d729a99545db2228e9Owen Taylor node_free_list = node_free_list->next; 3572e0320d57e417f7d1c838d729a99545db2228e9Owen Taylor } 3582e0320d57e417f7d1c838d729a99545db2228e9Owen Taylor else 3592e0320d57e417f7d1c838d729a99545db2228e9Owen Taylor { 3602e0320d57e417f7d1c838d729a99545db2228e9Owen Taylor if (!node_mem_chunk) 3612e0320d57e417f7d1c838d729a99545db2228e9Owen Taylor node_mem_chunk = g_mem_chunk_new ("hash node mem chunk", 3622e0320d57e417f7d1c838d729a99545db2228e9Owen Taylor sizeof (GHashNode), 3632e0320d57e417f7d1c838d729a99545db2228e9Owen Taylor 1024, G_ALLOC_ONLY); 3642d68cbbb7d37d3f265bf1087e6ddedcc58bc62beTim Janik 3652e0320d57e417f7d1c838d729a99545db2228e9Owen Taylor hash_node = g_chunk_new (GHashNode, node_mem_chunk); 3662e0320d57e417f7d1c838d729a99545db2228e9Owen Taylor } 367b2e318ff3ecc50d72121a4e8561442a6d79a7a84Tim Janik G_UNLOCK (g_hash_global); 3682d68cbbb7d37d3f265bf1087e6ddedcc58bc62beTim Janik 3692e0320d57e417f7d1c838d729a99545db2228e9Owen Taylor hash_node->key = key; 3702e0320d57e417f7d1c838d729a99545db2228e9Owen Taylor hash_node->value = value; 3712e0320d57e417f7d1c838d729a99545db2228e9Owen Taylor hash_node->next = NULL; 3722d68cbbb7d37d3f265bf1087e6ddedcc58bc62beTim Janik 3732e0320d57e417f7d1c838d729a99545db2228e9Owen Taylor return hash_node; 3742e0320d57e417f7d1c838d729a99545db2228e9Owen Taylor} 3752e0320d57e417f7d1c838d729a99545db2228e9Owen Taylor 3762e0320d57e417f7d1c838d729a99545db2228e9Owen Taylorstatic void 3773a14f25fdfa715f1a79b74bcf3916885053ff307Tim Janikg_hash_node_destroy (GHashNode *hash_node) 3782e0320d57e417f7d1c838d729a99545db2228e9Owen Taylor{ 3798c90d7766b1708a8bcb3cb96988b6b7fc92c2e59Sebastian Wilhelmi 3808c90d7766b1708a8bcb3cb96988b6b7fc92c2e59Sebastian Wilhelmi#ifdef ENABLE_GC_FRIENDLY 3818c90d7766b1708a8bcb3cb96988b6b7fc92c2e59Sebastian Wilhelmi hash_node->key = NULL; 3828c90d7766b1708a8bcb3cb96988b6b7fc92c2e59Sebastian Wilhelmi hash_node->value = NULL; 3838c90d7766b1708a8bcb3cb96988b6b7fc92c2e59Sebastian Wilhelmi#endif /* ENABLE_GC_FRIENDLY */ 3848c90d7766b1708a8bcb3cb96988b6b7fc92c2e59Sebastian Wilhelmi 385b2e318ff3ecc50d72121a4e8561442a6d79a7a84Tim Janik G_LOCK (g_hash_global); 3867519c2338ae484135b44bbb7eb49719aea8c4ca3Lauri Alanko hash_node->next = node_free_list; 3877519c2338ae484135b44bbb7eb49719aea8c4ca3Lauri Alanko node_free_list = hash_node; 388b2e318ff3ecc50d72121a4e8561442a6d79a7a84Tim Janik G_UNLOCK (g_hash_global); 3892e0320d57e417f7d1c838d729a99545db2228e9Owen Taylor} 3902e0320d57e417f7d1c838d729a99545db2228e9Owen Taylor 3912e0320d57e417f7d1c838d729a99545db2228e9Owen Taylorstatic void 3923a14f25fdfa715f1a79b74bcf3916885053ff307Tim Janikg_hash_nodes_destroy (GHashNode *hash_node) 3932e0320d57e417f7d1c838d729a99545db2228e9Owen Taylor{ 394448e792b0a9b092f9593eaa51e16acd8abe54c76Jeff Garzik if (hash_node) 395448e792b0a9b092f9593eaa51e16acd8abe54c76Jeff Garzik { 396448e792b0a9b092f9593eaa51e16acd8abe54c76Jeff Garzik GHashNode *node = hash_node; 3972d68cbbb7d37d3f265bf1087e6ddedcc58bc62beTim Janik 398448e792b0a9b092f9593eaa51e16acd8abe54c76Jeff Garzik while (node->next) 3998c90d7766b1708a8bcb3cb96988b6b7fc92c2e59Sebastian Wilhelmi { 4008c90d7766b1708a8bcb3cb96988b6b7fc92c2e59Sebastian Wilhelmi#ifdef ENABLE_GC_FRIENDLY 4018c90d7766b1708a8bcb3cb96988b6b7fc92c2e59Sebastian Wilhelmi node->key = NULL; 4028c90d7766b1708a8bcb3cb96988b6b7fc92c2e59Sebastian Wilhelmi node->value = NULL; 4038c90d7766b1708a8bcb3cb96988b6b7fc92c2e59Sebastian Wilhelmi#endif /* ENABLE_GC_FRIENDLY */ 4048c90d7766b1708a8bcb3cb96988b6b7fc92c2e59Sebastian Wilhelmi node = node->next; 4058c90d7766b1708a8bcb3cb96988b6b7fc92c2e59Sebastian Wilhelmi } 4068c90d7766b1708a8bcb3cb96988b6b7fc92c2e59Sebastian Wilhelmi 4078c90d7766b1708a8bcb3cb96988b6b7fc92c2e59Sebastian Wilhelmi#ifdef ENABLE_GC_FRIENDLY 4088c90d7766b1708a8bcb3cb96988b6b7fc92c2e59Sebastian Wilhelmi node->key = NULL; 4098c90d7766b1708a8bcb3cb96988b6b7fc92c2e59Sebastian Wilhelmi node->value = NULL; 4108c90d7766b1708a8bcb3cb96988b6b7fc92c2e59Sebastian Wilhelmi#endif /* ENABLE_GC_FRIENDLY */ 4118c90d7766b1708a8bcb3cb96988b6b7fc92c2e59Sebastian Wilhelmi 412448e792b0a9b092f9593eaa51e16acd8abe54c76Jeff Garzik G_LOCK (g_hash_global); 413448e792b0a9b092f9593eaa51e16acd8abe54c76Jeff Garzik node->next = node_free_list; 414448e792b0a9b092f9593eaa51e16acd8abe54c76Jeff Garzik node_free_list = hash_node; 415448e792b0a9b092f9593eaa51e16acd8abe54c76Jeff Garzik G_UNLOCK (g_hash_global); 416448e792b0a9b092f9593eaa51e16acd8abe54c76Jeff Garzik } 417df9a49ec3cbb19e58be929548cfba12452c55d83Josh MacDonald} 418