ghash.c revision b37e032581c44135b480dc74ae0355e72eef1372
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 52e0320d57e417f7d1c838d729a99545db2228e9Owen Taylor * modify it under the terms of the GNU Library 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 122e0320d57e417f7d1c838d729a99545db2228e9Owen Taylor * Library General Public License for more details. 132e0320d57e417f7d1c838d729a99545db2228e9Owen Taylor * 142e0320d57e417f7d1c838d729a99545db2228e9Owen Taylor * You should have received a copy of the GNU Library 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 20931ea952650b013b834041b91b0c37a748ffd449Owen Taylor/* 21931ea952650b013b834041b91b0c37a748ffd449Owen Taylor * MT safe 22931ea952650b013b834041b91b0c37a748ffd449Owen Taylor */ 23931ea952650b013b834041b91b0c37a748ffd449Owen Taylor 242e0320d57e417f7d1c838d729a99545db2228e9Owen Taylor#include "glib.h" 252e0320d57e417f7d1c838d729a99545db2228e9Owen Taylor 262e0320d57e417f7d1c838d729a99545db2228e9Owen Taylor 272e0320d57e417f7d1c838d729a99545db2228e9Owen Taylor#define HASH_TABLE_MIN_SIZE 11 282e0320d57e417f7d1c838d729a99545db2228e9Owen Taylor#define HASH_TABLE_MAX_SIZE 13845163 292e0320d57e417f7d1c838d729a99545db2228e9Owen Taylor 302e0320d57e417f7d1c838d729a99545db2228e9Owen Taylor 312e0320d57e417f7d1c838d729a99545db2228e9Owen Taylortypedef struct _GHashNode GHashNode; 322e0320d57e417f7d1c838d729a99545db2228e9Owen Taylor 332e0320d57e417f7d1c838d729a99545db2228e9Owen Taylorstruct _GHashNode 342e0320d57e417f7d1c838d729a99545db2228e9Owen Taylor{ 352e0320d57e417f7d1c838d729a99545db2228e9Owen Taylor gpointer key; 362e0320d57e417f7d1c838d729a99545db2228e9Owen Taylor gpointer value; 372e0320d57e417f7d1c838d729a99545db2228e9Owen Taylor GHashNode *next; 382e0320d57e417f7d1c838d729a99545db2228e9Owen Taylor}; 392e0320d57e417f7d1c838d729a99545db2228e9Owen Taylor 407519c2338ae484135b44bbb7eb49719aea8c4ca3Lauri Alankostruct _GHashTable 412e0320d57e417f7d1c838d729a99545db2228e9Owen Taylor{ 422e0320d57e417f7d1c838d729a99545db2228e9Owen Taylor gint size; 432e0320d57e417f7d1c838d729a99545db2228e9Owen Taylor gint nnodes; 44e666e8125f823c75ab0a89e68d73773f24542947Tim Janik guint frozen; 452e0320d57e417f7d1c838d729a99545db2228e9Owen Taylor GHashNode **nodes; 462e0320d57e417f7d1c838d729a99545db2228e9Owen Taylor GHashFunc hash_func; 472e0320d57e417f7d1c838d729a99545db2228e9Owen Taylor GCompareFunc key_compare_func; 482e0320d57e417f7d1c838d729a99545db2228e9Owen Taylor}; 492e0320d57e417f7d1c838d729a99545db2228e9Owen Taylor 502e0320d57e417f7d1c838d729a99545db2228e9Owen Taylor 512d68cbbb7d37d3f265bf1087e6ddedcc58bc62beTim Janikstatic void g_hash_table_resize (GHashTable *hash_table); 52d5492a983cfa048658af8b03f833ddb3c0cf355eESTstatic GHashNode** g_hash_table_lookup_node (GHashTable *hash_table, 53d5492a983cfa048658af8b03f833ddb3c0cf355eEST gconstpointer key); 542d68cbbb7d37d3f265bf1087e6ddedcc58bc62beTim Janikstatic GHashNode* g_hash_node_new (gpointer key, 552d68cbbb7d37d3f265bf1087e6ddedcc58bc62beTim Janik gpointer value); 563a14f25fdfa715f1a79b74bcf3916885053ff307Tim Janikstatic void g_hash_node_destroy (GHashNode *hash_node); 573a14f25fdfa715f1a79b74bcf3916885053ff307Tim Janikstatic void g_hash_nodes_destroy (GHashNode *hash_node); 582e0320d57e417f7d1c838d729a99545db2228e9Owen Taylor 592e0320d57e417f7d1c838d729a99545db2228e9Owen Taylor 60b37e032581c44135b480dc74ae0355e72eef1372Sebastian WilhelmiG_LOCK_DEFINE_STATIC (g_hash_global); 61931ea952650b013b834041b91b0c37a748ffd449Owen Taylor 622e0320d57e417f7d1c838d729a99545db2228e9Owen Taylorstatic GMemChunk *node_mem_chunk = NULL; 632e0320d57e417f7d1c838d729a99545db2228e9Owen Taylorstatic GHashNode *node_free_list = NULL; 642e0320d57e417f7d1c838d729a99545db2228e9Owen Taylor 652e0320d57e417f7d1c838d729a99545db2228e9Owen Taylor 662e0320d57e417f7d1c838d729a99545db2228e9Owen TaylorGHashTable* 672e0320d57e417f7d1c838d729a99545db2228e9Owen Taylorg_hash_table_new (GHashFunc hash_func, 682e0320d57e417f7d1c838d729a99545db2228e9Owen Taylor GCompareFunc key_compare_func) 692e0320d57e417f7d1c838d729a99545db2228e9Owen Taylor{ 707519c2338ae484135b44bbb7eb49719aea8c4ca3Lauri Alanko GHashTable *hash_table; 712d68cbbb7d37d3f265bf1087e6ddedcc58bc62beTim Janik guint i; 722d68cbbb7d37d3f265bf1087e6ddedcc58bc62beTim Janik 737519c2338ae484135b44bbb7eb49719aea8c4ca3Lauri Alanko hash_table = g_new (GHashTable, 1); 747519c2338ae484135b44bbb7eb49719aea8c4ca3Lauri Alanko hash_table->size = HASH_TABLE_MIN_SIZE; 752e0320d57e417f7d1c838d729a99545db2228e9Owen Taylor hash_table->nnodes = 0; 762e0320d57e417f7d1c838d729a99545db2228e9Owen Taylor hash_table->frozen = FALSE; 777519c2338ae484135b44bbb7eb49719aea8c4ca3Lauri Alanko hash_table->hash_func = hash_func ? hash_func : g_direct_hash; 782e0320d57e417f7d1c838d729a99545db2228e9Owen Taylor hash_table->key_compare_func = key_compare_func; 797519c2338ae484135b44bbb7eb49719aea8c4ca3Lauri Alanko hash_table->nodes = g_new (GHashNode*, hash_table->size); 802d68cbbb7d37d3f265bf1087e6ddedcc58bc62beTim Janik 817519c2338ae484135b44bbb7eb49719aea8c4ca3Lauri Alanko for (i = 0; i < hash_table->size; i++) 827519c2338ae484135b44bbb7eb49719aea8c4ca3Lauri Alanko hash_table->nodes[i] = NULL; 832d68cbbb7d37d3f265bf1087e6ddedcc58bc62beTim Janik 847519c2338ae484135b44bbb7eb49719aea8c4ca3Lauri Alanko return hash_table; 852e0320d57e417f7d1c838d729a99545db2228e9Owen Taylor} 862e0320d57e417f7d1c838d729a99545db2228e9Owen Taylor 872e0320d57e417f7d1c838d729a99545db2228e9Owen Taylorvoid 882e0320d57e417f7d1c838d729a99545db2228e9Owen Taylorg_hash_table_destroy (GHashTable *hash_table) 892e0320d57e417f7d1c838d729a99545db2228e9Owen Taylor{ 902d68cbbb7d37d3f265bf1087e6ddedcc58bc62beTim Janik guint i; 912d68cbbb7d37d3f265bf1087e6ddedcc58bc62beTim Janik 922d68cbbb7d37d3f265bf1087e6ddedcc58bc62beTim Janik g_return_if_fail (hash_table != NULL); 932d68cbbb7d37d3f265bf1087e6ddedcc58bc62beTim Janik 947519c2338ae484135b44bbb7eb49719aea8c4ca3Lauri Alanko for (i = 0; i < hash_table->size; i++) 953a14f25fdfa715f1a79b74bcf3916885053ff307Tim Janik g_hash_nodes_destroy (hash_table->nodes[i]); 962d68cbbb7d37d3f265bf1087e6ddedcc58bc62beTim Janik 977519c2338ae484135b44bbb7eb49719aea8c4ca3Lauri Alanko g_free (hash_table->nodes); 987519c2338ae484135b44bbb7eb49719aea8c4ca3Lauri Alanko g_free (hash_table); 992e0320d57e417f7d1c838d729a99545db2228e9Owen Taylor} 1002e0320d57e417f7d1c838d729a99545db2228e9Owen Taylor 101d5492a983cfa048658af8b03f833ddb3c0cf355eESTstatic inline GHashNode** 102d5492a983cfa048658af8b03f833ddb3c0cf355eESTg_hash_table_lookup_node (GHashTable *hash_table, 103d5492a983cfa048658af8b03f833ddb3c0cf355eEST gconstpointer key) 1042e0320d57e417f7d1c838d729a99545db2228e9Owen Taylor{ 105d5492a983cfa048658af8b03f833ddb3c0cf355eEST GHashNode **node; 1062d68cbbb7d37d3f265bf1087e6ddedcc58bc62beTim Janik 107d5492a983cfa048658af8b03f833ddb3c0cf355eEST node = &hash_table->nodes 108d5492a983cfa048658af8b03f833ddb3c0cf355eEST [(* hash_table->hash_func) (key) % hash_table->size]; 1092d68cbbb7d37d3f265bf1087e6ddedcc58bc62beTim Janik 1102d68cbbb7d37d3f265bf1087e6ddedcc58bc62beTim Janik /* Hash table lookup needs to be fast. 1112d68cbbb7d37d3f265bf1087e6ddedcc58bc62beTim Janik * We therefore remove the extra conditional of testing 1122d68cbbb7d37d3f265bf1087e6ddedcc58bc62beTim Janik * whether to call the key_compare_func or not from 1132d68cbbb7d37d3f265bf1087e6ddedcc58bc62beTim Janik * the inner loop. 1142d68cbbb7d37d3f265bf1087e6ddedcc58bc62beTim Janik */ 1152d68cbbb7d37d3f265bf1087e6ddedcc58bc62beTim Janik if (hash_table->key_compare_func) 116d5492a983cfa048658af8b03f833ddb3c0cf355eEST while (*node && !(*hash_table->key_compare_func) ((*node)->key, key)) 117d5492a983cfa048658af8b03f833ddb3c0cf355eEST node = &(*node)->next; 1182d68cbbb7d37d3f265bf1087e6ddedcc58bc62beTim Janik else 119d5492a983cfa048658af8b03f833ddb3c0cf355eEST while (*node && (*node)->key != key) 120d5492a983cfa048658af8b03f833ddb3c0cf355eEST node = &(*node)->next; 1212d68cbbb7d37d3f265bf1087e6ddedcc58bc62beTim Janik 1222d68cbbb7d37d3f265bf1087e6ddedcc58bc62beTim Janik return node; 1232d68cbbb7d37d3f265bf1087e6ddedcc58bc62beTim Janik} 1242e0320d57e417f7d1c838d729a99545db2228e9Owen Taylor 1252d68cbbb7d37d3f265bf1087e6ddedcc58bc62beTim Janikgpointer 1262d68cbbb7d37d3f265bf1087e6ddedcc58bc62beTim Janikg_hash_table_lookup (GHashTable *hash_table, 1272d68cbbb7d37d3f265bf1087e6ddedcc58bc62beTim Janik gconstpointer key) 1282d68cbbb7d37d3f265bf1087e6ddedcc58bc62beTim Janik{ 1292d68cbbb7d37d3f265bf1087e6ddedcc58bc62beTim Janik GHashNode *node; 1302d68cbbb7d37d3f265bf1087e6ddedcc58bc62beTim Janik 1312d68cbbb7d37d3f265bf1087e6ddedcc58bc62beTim Janik g_return_val_if_fail (hash_table != NULL, NULL); 1322d68cbbb7d37d3f265bf1087e6ddedcc58bc62beTim Janik 133d5492a983cfa048658af8b03f833ddb3c0cf355eEST node = *g_hash_table_lookup_node (hash_table, key); 1342d68cbbb7d37d3f265bf1087e6ddedcc58bc62beTim Janik 1352d68cbbb7d37d3f265bf1087e6ddedcc58bc62beTim Janik return node ? node->value : NULL; 1362d68cbbb7d37d3f265bf1087e6ddedcc58bc62beTim Janik} 1377401460a60504dad7b77219d0ba3d93112e12444Manish Singh 1382d68cbbb7d37d3f265bf1087e6ddedcc58bc62beTim Janikvoid 1392d68cbbb7d37d3f265bf1087e6ddedcc58bc62beTim Janikg_hash_table_insert (GHashTable *hash_table, 1402d68cbbb7d37d3f265bf1087e6ddedcc58bc62beTim Janik gpointer key, 1412d68cbbb7d37d3f265bf1087e6ddedcc58bc62beTim Janik gpointer value) 1422d68cbbb7d37d3f265bf1087e6ddedcc58bc62beTim Janik{ 143d5492a983cfa048658af8b03f833ddb3c0cf355eEST GHashNode **node; 1442d68cbbb7d37d3f265bf1087e6ddedcc58bc62beTim Janik 1452d68cbbb7d37d3f265bf1087e6ddedcc58bc62beTim Janik g_return_if_fail (hash_table != NULL); 1462d68cbbb7d37d3f265bf1087e6ddedcc58bc62beTim Janik 147d5492a983cfa048658af8b03f833ddb3c0cf355eEST node = g_hash_table_lookup_node (hash_table, key); 148d5492a983cfa048658af8b03f833ddb3c0cf355eEST 149d5492a983cfa048658af8b03f833ddb3c0cf355eEST if (*node) 1507519c2338ae484135b44bbb7eb49719aea8c4ca3Lauri Alanko { 1517519c2338ae484135b44bbb7eb49719aea8c4ca3Lauri Alanko /* do not reset node->key in this place, keeping 1527519c2338ae484135b44bbb7eb49719aea8c4ca3Lauri Alanko * the old key might be intended. 1537519c2338ae484135b44bbb7eb49719aea8c4ca3Lauri Alanko * a g_hash_table_remove/g_hash_table_insert pair 1547519c2338ae484135b44bbb7eb49719aea8c4ca3Lauri Alanko * can be used otherwise. 1557519c2338ae484135b44bbb7eb49719aea8c4ca3Lauri Alanko * 1567519c2338ae484135b44bbb7eb49719aea8c4ca3Lauri Alanko * node->key = key; */ 157d5492a983cfa048658af8b03f833ddb3c0cf355eEST (*node)->value = value; 158d5492a983cfa048658af8b03f833ddb3c0cf355eEST } 159d5492a983cfa048658af8b03f833ddb3c0cf355eEST else 160d5492a983cfa048658af8b03f833ddb3c0cf355eEST { 161d5492a983cfa048658af8b03f833ddb3c0cf355eEST *node = g_hash_node_new (key, value); 162d5492a983cfa048658af8b03f833ddb3c0cf355eEST hash_table->nnodes++; 163d5492a983cfa048658af8b03f833ddb3c0cf355eEST if (!hash_table->frozen) 164d5492a983cfa048658af8b03f833ddb3c0cf355eEST g_hash_table_resize (hash_table); 1652e0320d57e417f7d1c838d729a99545db2228e9Owen Taylor } 1662e0320d57e417f7d1c838d729a99545db2228e9Owen Taylor} 1672e0320d57e417f7d1c838d729a99545db2228e9Owen Taylor 1682e0320d57e417f7d1c838d729a99545db2228e9Owen Taylorvoid 1692d68cbbb7d37d3f265bf1087e6ddedcc58bc62beTim Janikg_hash_table_remove (GHashTable *hash_table, 1702e0320d57e417f7d1c838d729a99545db2228e9Owen Taylor gconstpointer key) 1712e0320d57e417f7d1c838d729a99545db2228e9Owen Taylor{ 172d5492a983cfa048658af8b03f833ddb3c0cf355eEST GHashNode **node, *dest; 1732d68cbbb7d37d3f265bf1087e6ddedcc58bc62beTim Janik 1742d68cbbb7d37d3f265bf1087e6ddedcc58bc62beTim Janik g_return_if_fail (hash_table != NULL); 1752d68cbbb7d37d3f265bf1087e6ddedcc58bc62beTim Janik 176d5492a983cfa048658af8b03f833ddb3c0cf355eEST node = g_hash_table_lookup_node (hash_table, key); 177448e792b0a9b092f9593eaa51e16acd8abe54c76Jeff Garzik 178d5492a983cfa048658af8b03f833ddb3c0cf355eEST if (*node) 1792e0320d57e417f7d1c838d729a99545db2228e9Owen Taylor { 180d5492a983cfa048658af8b03f833ddb3c0cf355eEST dest = *node; 181d5492a983cfa048658af8b03f833ddb3c0cf355eEST (*node) = dest->next; 182d5492a983cfa048658af8b03f833ddb3c0cf355eEST g_hash_node_destroy (dest); 1837519c2338ae484135b44bbb7eb49719aea8c4ca3Lauri Alanko hash_table->nnodes--; 1842d68cbbb7d37d3f265bf1087e6ddedcc58bc62beTim Janik 185448e792b0a9b092f9593eaa51e16acd8abe54c76Jeff Garzik if (!hash_table->frozen) 186448e792b0a9b092f9593eaa51e16acd8abe54c76Jeff Garzik g_hash_table_resize (hash_table); 187448e792b0a9b092f9593eaa51e16acd8abe54c76Jeff Garzik } 1882e0320d57e417f7d1c838d729a99545db2228e9Owen Taylor} 1892e0320d57e417f7d1c838d729a99545db2228e9Owen Taylor 1907519c2338ae484135b44bbb7eb49719aea8c4ca3Lauri Alankogboolean 1915b52f015356729919cfd3b68cd5ac3c27a35e147Lauri Alankog_hash_table_lookup_extended (GHashTable *hash_table, 1925b52f015356729919cfd3b68cd5ac3c27a35e147Lauri Alanko gconstpointer lookup_key, 1935b52f015356729919cfd3b68cd5ac3c27a35e147Lauri Alanko gpointer *orig_key, 1945b52f015356729919cfd3b68cd5ac3c27a35e147Lauri Alanko gpointer *value) 1957519c2338ae484135b44bbb7eb49719aea8c4ca3Lauri Alanko{ 1967519c2338ae484135b44bbb7eb49719aea8c4ca3Lauri Alanko GHashNode *node; 1972d68cbbb7d37d3f265bf1087e6ddedcc58bc62beTim Janik 1982d68cbbb7d37d3f265bf1087e6ddedcc58bc62beTim Janik g_return_val_if_fail (hash_table != NULL, FALSE); 1992d68cbbb7d37d3f265bf1087e6ddedcc58bc62beTim Janik 200d5492a983cfa048658af8b03f833ddb3c0cf355eEST node = *g_hash_table_lookup_node (hash_table, lookup_key); 2012d68cbbb7d37d3f265bf1087e6ddedcc58bc62beTim Janik 2027519c2338ae484135b44bbb7eb49719aea8c4ca3Lauri Alanko if (node) 2032e0320d57e417f7d1c838d729a99545db2228e9Owen Taylor { 2047519c2338ae484135b44bbb7eb49719aea8c4ca3Lauri Alanko if (orig_key) 2057519c2338ae484135b44bbb7eb49719aea8c4ca3Lauri Alanko *orig_key = node->key; 2067519c2338ae484135b44bbb7eb49719aea8c4ca3Lauri Alanko if (value) 2077519c2338ae484135b44bbb7eb49719aea8c4ca3Lauri Alanko *value = node->value; 2087519c2338ae484135b44bbb7eb49719aea8c4ca3Lauri Alanko return TRUE; 2092e0320d57e417f7d1c838d729a99545db2228e9Owen Taylor } 2107519c2338ae484135b44bbb7eb49719aea8c4ca3Lauri Alanko else 2117519c2338ae484135b44bbb7eb49719aea8c4ca3Lauri Alanko return FALSE; 2122e0320d57e417f7d1c838d729a99545db2228e9Owen Taylor} 2132e0320d57e417f7d1c838d729a99545db2228e9Owen Taylor 2142e0320d57e417f7d1c838d729a99545db2228e9Owen Taylorvoid 2152e0320d57e417f7d1c838d729a99545db2228e9Owen Taylorg_hash_table_freeze (GHashTable *hash_table) 2162e0320d57e417f7d1c838d729a99545db2228e9Owen Taylor{ 2172d68cbbb7d37d3f265bf1087e6ddedcc58bc62beTim Janik g_return_if_fail (hash_table != NULL); 2182d68cbbb7d37d3f265bf1087e6ddedcc58bc62beTim Janik 219e666e8125f823c75ab0a89e68d73773f24542947Tim Janik hash_table->frozen++; 2202e0320d57e417f7d1c838d729a99545db2228e9Owen Taylor} 2212e0320d57e417f7d1c838d729a99545db2228e9Owen Taylor 2222e0320d57e417f7d1c838d729a99545db2228e9Owen Taylorvoid 2232e0320d57e417f7d1c838d729a99545db2228e9Owen Taylorg_hash_table_thaw (GHashTable *hash_table) 2242e0320d57e417f7d1c838d729a99545db2228e9Owen Taylor{ 2252d68cbbb7d37d3f265bf1087e6ddedcc58bc62beTim Janik g_return_if_fail (hash_table != NULL); 2262d68cbbb7d37d3f265bf1087e6ddedcc58bc62beTim Janik 227e666e8125f823c75ab0a89e68d73773f24542947Tim Janik if (hash_table->frozen) 228e666e8125f823c75ab0a89e68d73773f24542947Tim Janik if (!(--hash_table->frozen)) 229e666e8125f823c75ab0a89e68d73773f24542947Tim Janik g_hash_table_resize (hash_table); 2302e0320d57e417f7d1c838d729a99545db2228e9Owen Taylor} 2312e0320d57e417f7d1c838d729a99545db2228e9Owen Taylor 232034e7c0339f64d4d52a53f2324daa2fca0332addManish Singhgint 2332d68cbbb7d37d3f265bf1087e6ddedcc58bc62beTim Janikg_hash_table_foreach_remove (GHashTable *hash_table, 2342d68cbbb7d37d3f265bf1087e6ddedcc58bc62beTim Janik GHRFunc func, 2352d68cbbb7d37d3f265bf1087e6ddedcc58bc62beTim Janik gpointer user_data) 236034e7c0339f64d4d52a53f2324daa2fca0332addManish Singh{ 237034e7c0339f64d4d52a53f2324daa2fca0332addManish Singh GHashNode *node, *prev; 2382d68cbbb7d37d3f265bf1087e6ddedcc58bc62beTim Janik guint i; 2392d68cbbb7d37d3f265bf1087e6ddedcc58bc62beTim Janik gint deleted = 0; 2402d68cbbb7d37d3f265bf1087e6ddedcc58bc62beTim Janik 2412d68cbbb7d37d3f265bf1087e6ddedcc58bc62beTim Janik g_return_val_if_fail (hash_table != NULL, 0); 2422d68cbbb7d37d3f265bf1087e6ddedcc58bc62beTim Janik g_return_val_if_fail (func != NULL, 0); 2432d68cbbb7d37d3f265bf1087e6ddedcc58bc62beTim Janik 244034e7c0339f64d4d52a53f2324daa2fca0332addManish Singh for (i = 0; i < hash_table->size; i++) 245034e7c0339f64d4d52a53f2324daa2fca0332addManish Singh { 246034e7c0339f64d4d52a53f2324daa2fca0332addManish Singh restart: 2472d68cbbb7d37d3f265bf1087e6ddedcc58bc62beTim Janik 248034e7c0339f64d4d52a53f2324daa2fca0332addManish Singh prev = NULL; 2492d68cbbb7d37d3f265bf1087e6ddedcc58bc62beTim Janik 250034e7c0339f64d4d52a53f2324daa2fca0332addManish Singh for (node = hash_table->nodes[i]; node; prev = node, node = node->next) 251034e7c0339f64d4d52a53f2324daa2fca0332addManish Singh { 252034e7c0339f64d4d52a53f2324daa2fca0332addManish Singh if ((* func) (node->key, node->value, user_data)) 253034e7c0339f64d4d52a53f2324daa2fca0332addManish Singh { 254034e7c0339f64d4d52a53f2324daa2fca0332addManish Singh deleted += 1; 2552d68cbbb7d37d3f265bf1087e6ddedcc58bc62beTim Janik 256034e7c0339f64d4d52a53f2324daa2fca0332addManish Singh hash_table->nnodes -= 1; 2572d68cbbb7d37d3f265bf1087e6ddedcc58bc62beTim Janik 258034e7c0339f64d4d52a53f2324daa2fca0332addManish Singh if (prev) 259034e7c0339f64d4d52a53f2324daa2fca0332addManish Singh { 260034e7c0339f64d4d52a53f2324daa2fca0332addManish Singh prev->next = node->next; 2613a14f25fdfa715f1a79b74bcf3916885053ff307Tim Janik g_hash_node_destroy (node); 262034e7c0339f64d4d52a53f2324daa2fca0332addManish Singh node = prev; 263034e7c0339f64d4d52a53f2324daa2fca0332addManish Singh } 264034e7c0339f64d4d52a53f2324daa2fca0332addManish Singh else 265034e7c0339f64d4d52a53f2324daa2fca0332addManish Singh { 266034e7c0339f64d4d52a53f2324daa2fca0332addManish Singh hash_table->nodes[i] = node->next; 2673a14f25fdfa715f1a79b74bcf3916885053ff307Tim Janik g_hash_node_destroy (node); 268034e7c0339f64d4d52a53f2324daa2fca0332addManish Singh goto restart; 269034e7c0339f64d4d52a53f2324daa2fca0332addManish Singh } 270034e7c0339f64d4d52a53f2324daa2fca0332addManish Singh } 271034e7c0339f64d4d52a53f2324daa2fca0332addManish Singh } 272034e7c0339f64d4d52a53f2324daa2fca0332addManish Singh } 2732d68cbbb7d37d3f265bf1087e6ddedcc58bc62beTim Janik 2742d68cbbb7d37d3f265bf1087e6ddedcc58bc62beTim Janik if (!hash_table->frozen) 275034e7c0339f64d4d52a53f2324daa2fca0332addManish Singh g_hash_table_resize (hash_table); 2762d68cbbb7d37d3f265bf1087e6ddedcc58bc62beTim Janik 277034e7c0339f64d4d52a53f2324daa2fca0332addManish Singh return deleted; 278034e7c0339f64d4d52a53f2324daa2fca0332addManish Singh} 279034e7c0339f64d4d52a53f2324daa2fca0332addManish Singh 2802e0320d57e417f7d1c838d729a99545db2228e9Owen Taylorvoid 2812e0320d57e417f7d1c838d729a99545db2228e9Owen Taylorg_hash_table_foreach (GHashTable *hash_table, 2822d68cbbb7d37d3f265bf1087e6ddedcc58bc62beTim Janik GHFunc func, 2832d68cbbb7d37d3f265bf1087e6ddedcc58bc62beTim Janik gpointer user_data) 2842e0320d57e417f7d1c838d729a99545db2228e9Owen Taylor{ 2852e0320d57e417f7d1c838d729a99545db2228e9Owen Taylor GHashNode *node; 2862e0320d57e417f7d1c838d729a99545db2228e9Owen Taylor gint i; 2872d68cbbb7d37d3f265bf1087e6ddedcc58bc62beTim Janik 2882d68cbbb7d37d3f265bf1087e6ddedcc58bc62beTim Janik g_return_if_fail (hash_table != NULL); 2892d68cbbb7d37d3f265bf1087e6ddedcc58bc62beTim Janik g_return_if_fail (func != NULL); 2902d68cbbb7d37d3f265bf1087e6ddedcc58bc62beTim Janik 2917519c2338ae484135b44bbb7eb49719aea8c4ca3Lauri Alanko for (i = 0; i < hash_table->size; i++) 2927519c2338ae484135b44bbb7eb49719aea8c4ca3Lauri Alanko for (node = hash_table->nodes[i]; node; node = node->next) 2937519c2338ae484135b44bbb7eb49719aea8c4ca3Lauri Alanko (* func) (node->key, node->value, user_data); 2942e0320d57e417f7d1c838d729a99545db2228e9Owen Taylor} 2952e0320d57e417f7d1c838d729a99545db2228e9Owen Taylor 2967519c2338ae484135b44bbb7eb49719aea8c4ca3Lauri Alanko/* Returns the number of elements contained in the hash table. */ 2972d68cbbb7d37d3f265bf1087e6ddedcc58bc62beTim Janikgint 2982d68cbbb7d37d3f265bf1087e6ddedcc58bc62beTim Janikg_hash_table_size (GHashTable *hash_table) 2997519c2338ae484135b44bbb7eb49719aea8c4ca3Lauri Alanko{ 3002d68cbbb7d37d3f265bf1087e6ddedcc58bc62beTim Janik g_return_val_if_fail (hash_table != NULL, 0); 3012d68cbbb7d37d3f265bf1087e6ddedcc58bc62beTim Janik 3027519c2338ae484135b44bbb7eb49719aea8c4ca3Lauri Alanko return hash_table->nnodes; 3037519c2338ae484135b44bbb7eb49719aea8c4ca3Lauri Alanko} 3042e0320d57e417f7d1c838d729a99545db2228e9Owen Taylor 3052e0320d57e417f7d1c838d729a99545db2228e9Owen Taylorstatic void 3062e0320d57e417f7d1c838d729a99545db2228e9Owen Taylorg_hash_table_resize (GHashTable *hash_table) 3072e0320d57e417f7d1c838d729a99545db2228e9Owen Taylor{ 3082e0320d57e417f7d1c838d729a99545db2228e9Owen Taylor GHashNode **new_nodes; 3092e0320d57e417f7d1c838d729a99545db2228e9Owen Taylor GHashNode *node; 3102e0320d57e417f7d1c838d729a99545db2228e9Owen Taylor GHashNode *next; 3112e0320d57e417f7d1c838d729a99545db2228e9Owen Taylor gfloat nodes_per_list; 3122e0320d57e417f7d1c838d729a99545db2228e9Owen Taylor guint hash_val; 3132e0320d57e417f7d1c838d729a99545db2228e9Owen Taylor gint new_size; 3142e0320d57e417f7d1c838d729a99545db2228e9Owen Taylor gint i; 3152d68cbbb7d37d3f265bf1087e6ddedcc58bc62beTim Janik 3167519c2338ae484135b44bbb7eb49719aea8c4ca3Lauri Alanko nodes_per_list = (gfloat) hash_table->nnodes / (gfloat) hash_table->size; 3172d68cbbb7d37d3f265bf1087e6ddedcc58bc62beTim Janik 3187519c2338ae484135b44bbb7eb49719aea8c4ca3Lauri Alanko if ((nodes_per_list > 0.3 || hash_table->size <= HASH_TABLE_MIN_SIZE) && 3197519c2338ae484135b44bbb7eb49719aea8c4ca3Lauri Alanko (nodes_per_list < 3.0 || hash_table->size >= HASH_TABLE_MAX_SIZE)) 3207519c2338ae484135b44bbb7eb49719aea8c4ca3Lauri Alanko return; 3212d68cbbb7d37d3f265bf1087e6ddedcc58bc62beTim Janik 3227401460a60504dad7b77219d0ba3d93112e12444Manish Singh new_size = CLAMP(g_spaced_primes_closest (hash_table->nnodes), 3237519c2338ae484135b44bbb7eb49719aea8c4ca3Lauri Alanko HASH_TABLE_MIN_SIZE, 3247519c2338ae484135b44bbb7eb49719aea8c4ca3Lauri Alanko HASH_TABLE_MAX_SIZE); 325448e792b0a9b092f9593eaa51e16acd8abe54c76Jeff Garzik new_nodes = g_new0 (GHashNode*, new_size); 3262d68cbbb7d37d3f265bf1087e6ddedcc58bc62beTim Janik 3277519c2338ae484135b44bbb7eb49719aea8c4ca3Lauri Alanko for (i = 0; i < hash_table->size; i++) 3287519c2338ae484135b44bbb7eb49719aea8c4ca3Lauri Alanko for (node = hash_table->nodes[i]; node; node = next) 3297519c2338ae484135b44bbb7eb49719aea8c4ca3Lauri Alanko { 3307519c2338ae484135b44bbb7eb49719aea8c4ca3Lauri Alanko next = node->next; 331448e792b0a9b092f9593eaa51e16acd8abe54c76Jeff Garzik 3327519c2338ae484135b44bbb7eb49719aea8c4ca3Lauri Alanko hash_val = (* hash_table->hash_func) (node->key) % new_size; 333448e792b0a9b092f9593eaa51e16acd8abe54c76Jeff Garzik 3347519c2338ae484135b44bbb7eb49719aea8c4ca3Lauri Alanko node->next = new_nodes[hash_val]; 3357519c2338ae484135b44bbb7eb49719aea8c4ca3Lauri Alanko new_nodes[hash_val] = node; 3367519c2338ae484135b44bbb7eb49719aea8c4ca3Lauri Alanko } 3372d68cbbb7d37d3f265bf1087e6ddedcc58bc62beTim Janik 3387519c2338ae484135b44bbb7eb49719aea8c4ca3Lauri Alanko g_free (hash_table->nodes); 3397519c2338ae484135b44bbb7eb49719aea8c4ca3Lauri Alanko hash_table->nodes = new_nodes; 3407519c2338ae484135b44bbb7eb49719aea8c4ca3Lauri Alanko hash_table->size = new_size; 3417519c2338ae484135b44bbb7eb49719aea8c4ca3Lauri Alanko} 3427519c2338ae484135b44bbb7eb49719aea8c4ca3Lauri Alanko 3432e0320d57e417f7d1c838d729a99545db2228e9Owen Taylorstatic GHashNode* 3442e0320d57e417f7d1c838d729a99545db2228e9Owen Taylorg_hash_node_new (gpointer key, 3452e0320d57e417f7d1c838d729a99545db2228e9Owen Taylor gpointer value) 3462e0320d57e417f7d1c838d729a99545db2228e9Owen Taylor{ 3472e0320d57e417f7d1c838d729a99545db2228e9Owen Taylor GHashNode *hash_node; 3482d68cbbb7d37d3f265bf1087e6ddedcc58bc62beTim Janik 349b2e318ff3ecc50d72121a4e8561442a6d79a7a84Tim Janik G_LOCK (g_hash_global); 3502e0320d57e417f7d1c838d729a99545db2228e9Owen Taylor if (node_free_list) 3512e0320d57e417f7d1c838d729a99545db2228e9Owen Taylor { 3522e0320d57e417f7d1c838d729a99545db2228e9Owen Taylor hash_node = node_free_list; 3532e0320d57e417f7d1c838d729a99545db2228e9Owen Taylor node_free_list = node_free_list->next; 3542e0320d57e417f7d1c838d729a99545db2228e9Owen Taylor } 3552e0320d57e417f7d1c838d729a99545db2228e9Owen Taylor else 3562e0320d57e417f7d1c838d729a99545db2228e9Owen Taylor { 3572e0320d57e417f7d1c838d729a99545db2228e9Owen Taylor if (!node_mem_chunk) 3582e0320d57e417f7d1c838d729a99545db2228e9Owen Taylor node_mem_chunk = g_mem_chunk_new ("hash node mem chunk", 3592e0320d57e417f7d1c838d729a99545db2228e9Owen Taylor sizeof (GHashNode), 3602e0320d57e417f7d1c838d729a99545db2228e9Owen Taylor 1024, G_ALLOC_ONLY); 3612d68cbbb7d37d3f265bf1087e6ddedcc58bc62beTim Janik 3622e0320d57e417f7d1c838d729a99545db2228e9Owen Taylor hash_node = g_chunk_new (GHashNode, node_mem_chunk); 3632e0320d57e417f7d1c838d729a99545db2228e9Owen Taylor } 364b2e318ff3ecc50d72121a4e8561442a6d79a7a84Tim Janik G_UNLOCK (g_hash_global); 3652d68cbbb7d37d3f265bf1087e6ddedcc58bc62beTim Janik 3662e0320d57e417f7d1c838d729a99545db2228e9Owen Taylor hash_node->key = key; 3672e0320d57e417f7d1c838d729a99545db2228e9Owen Taylor hash_node->value = value; 3682e0320d57e417f7d1c838d729a99545db2228e9Owen Taylor hash_node->next = NULL; 3692d68cbbb7d37d3f265bf1087e6ddedcc58bc62beTim Janik 3702e0320d57e417f7d1c838d729a99545db2228e9Owen Taylor return hash_node; 3712e0320d57e417f7d1c838d729a99545db2228e9Owen Taylor} 3722e0320d57e417f7d1c838d729a99545db2228e9Owen Taylor 3732e0320d57e417f7d1c838d729a99545db2228e9Owen Taylorstatic void 3743a14f25fdfa715f1a79b74bcf3916885053ff307Tim Janikg_hash_node_destroy (GHashNode *hash_node) 3752e0320d57e417f7d1c838d729a99545db2228e9Owen Taylor{ 376b2e318ff3ecc50d72121a4e8561442a6d79a7a84Tim Janik G_LOCK (g_hash_global); 3777519c2338ae484135b44bbb7eb49719aea8c4ca3Lauri Alanko hash_node->next = node_free_list; 3787519c2338ae484135b44bbb7eb49719aea8c4ca3Lauri Alanko node_free_list = hash_node; 379b2e318ff3ecc50d72121a4e8561442a6d79a7a84Tim Janik G_UNLOCK (g_hash_global); 3802e0320d57e417f7d1c838d729a99545db2228e9Owen Taylor} 3812e0320d57e417f7d1c838d729a99545db2228e9Owen Taylor 3822e0320d57e417f7d1c838d729a99545db2228e9Owen Taylorstatic void 3833a14f25fdfa715f1a79b74bcf3916885053ff307Tim Janikg_hash_nodes_destroy (GHashNode *hash_node) 3842e0320d57e417f7d1c838d729a99545db2228e9Owen Taylor{ 385448e792b0a9b092f9593eaa51e16acd8abe54c76Jeff Garzik if (hash_node) 386448e792b0a9b092f9593eaa51e16acd8abe54c76Jeff Garzik { 387448e792b0a9b092f9593eaa51e16acd8abe54c76Jeff Garzik GHashNode *node = hash_node; 3882d68cbbb7d37d3f265bf1087e6ddedcc58bc62beTim Janik 389448e792b0a9b092f9593eaa51e16acd8abe54c76Jeff Garzik while (node->next) 390448e792b0a9b092f9593eaa51e16acd8abe54c76Jeff Garzik node = node->next; 3912d68cbbb7d37d3f265bf1087e6ddedcc58bc62beTim Janik 392448e792b0a9b092f9593eaa51e16acd8abe54c76Jeff Garzik G_LOCK (g_hash_global); 393448e792b0a9b092f9593eaa51e16acd8abe54c76Jeff Garzik node->next = node_free_list; 394448e792b0a9b092f9593eaa51e16acd8abe54c76Jeff Garzik node_free_list = hash_node; 395448e792b0a9b092f9593eaa51e16acd8abe54c76Jeff Garzik G_UNLOCK (g_hash_global); 396448e792b0a9b092f9593eaa51e16acd8abe54c76Jeff Garzik } 397df9a49ec3cbb19e58be929548cfba12452c55d83Josh MacDonald} 398