ghash.c revision 2fb47703e2929d300a3f804268a36d50543b4a2c
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 312fb47703e2929d300a3f804268a36d50543b4a2cSebastian Wilhelmi#ifdef HAVE_CONFIG_H 322fb47703e2929d300a3f804268a36d50543b4a2cSebastian Wilhelmi#include <config.h> 332fb47703e2929d300a3f804268a36d50543b4a2cSebastian Wilhelmi#endif 342fb47703e2929d300a3f804268a36d50543b4a2cSebastian Wilhelmi 352e0320d57e417f7d1c838d729a99545db2228e9Owen Taylor#include "glib.h" 362e0320d57e417f7d1c838d729a99545db2228e9Owen Taylor 372e0320d57e417f7d1c838d729a99545db2228e9Owen Taylor 382e0320d57e417f7d1c838d729a99545db2228e9Owen Taylor#define HASH_TABLE_MIN_SIZE 11 392e0320d57e417f7d1c838d729a99545db2228e9Owen Taylor#define HASH_TABLE_MAX_SIZE 13845163 402e0320d57e417f7d1c838d729a99545db2228e9Owen Taylor 412e0320d57e417f7d1c838d729a99545db2228e9Owen Taylor 422e0320d57e417f7d1c838d729a99545db2228e9Owen Taylortypedef struct _GHashNode GHashNode; 432e0320d57e417f7d1c838d729a99545db2228e9Owen Taylor 442e0320d57e417f7d1c838d729a99545db2228e9Owen Taylorstruct _GHashNode 452e0320d57e417f7d1c838d729a99545db2228e9Owen Taylor{ 462e0320d57e417f7d1c838d729a99545db2228e9Owen Taylor gpointer key; 472e0320d57e417f7d1c838d729a99545db2228e9Owen Taylor gpointer value; 482e0320d57e417f7d1c838d729a99545db2228e9Owen Taylor GHashNode *next; 492e0320d57e417f7d1c838d729a99545db2228e9Owen Taylor}; 502e0320d57e417f7d1c838d729a99545db2228e9Owen Taylor 517519c2338ae484135b44bbb7eb49719aea8c4ca3Lauri Alankostruct _GHashTable 522e0320d57e417f7d1c838d729a99545db2228e9Owen Taylor{ 532e0320d57e417f7d1c838d729a99545db2228e9Owen Taylor gint size; 542e0320d57e417f7d1c838d729a99545db2228e9Owen Taylor gint nnodes; 552e0320d57e417f7d1c838d729a99545db2228e9Owen Taylor GHashNode **nodes; 562e0320d57e417f7d1c838d729a99545db2228e9Owen Taylor GHashFunc hash_func; 57267b6813703e24ef60d0e8ba42557c414f9dd52eSebastian Wilhelmi GEqualFunc key_equal_func; 582e0320d57e417f7d1c838d729a99545db2228e9Owen Taylor}; 592e0320d57e417f7d1c838d729a99545db2228e9Owen Taylor 602e0320d57e417f7d1c838d729a99545db2228e9Owen Taylor 612d68cbbb7d37d3f265bf1087e6ddedcc58bc62beTim Janikstatic void g_hash_table_resize (GHashTable *hash_table); 62d5492a983cfa048658af8b03f833ddb3c0cf355eESTstatic GHashNode** g_hash_table_lookup_node (GHashTable *hash_table, 63d5492a983cfa048658af8b03f833ddb3c0cf355eEST gconstpointer key); 642d68cbbb7d37d3f265bf1087e6ddedcc58bc62beTim Janikstatic GHashNode* g_hash_node_new (gpointer key, 652d68cbbb7d37d3f265bf1087e6ddedcc58bc62beTim Janik gpointer value); 663a14f25fdfa715f1a79b74bcf3916885053ff307Tim Janikstatic void g_hash_node_destroy (GHashNode *hash_node); 673a14f25fdfa715f1a79b74bcf3916885053ff307Tim Janikstatic void g_hash_nodes_destroy (GHashNode *hash_node); 682e0320d57e417f7d1c838d729a99545db2228e9Owen Taylor 692e0320d57e417f7d1c838d729a99545db2228e9Owen Taylor 70b37e032581c44135b480dc74ae0355e72eef1372Sebastian WilhelmiG_LOCK_DEFINE_STATIC (g_hash_global); 71931ea952650b013b834041b91b0c37a748ffd449Owen Taylor 722e0320d57e417f7d1c838d729a99545db2228e9Owen Taylorstatic GMemChunk *node_mem_chunk = NULL; 732e0320d57e417f7d1c838d729a99545db2228e9Owen Taylorstatic GHashNode *node_free_list = NULL; 742e0320d57e417f7d1c838d729a99545db2228e9Owen Taylor 752e0320d57e417f7d1c838d729a99545db2228e9Owen Taylor 762e0320d57e417f7d1c838d729a99545db2228e9Owen TaylorGHashTable* 772e0320d57e417f7d1c838d729a99545db2228e9Owen Taylorg_hash_table_new (GHashFunc hash_func, 78267b6813703e24ef60d0e8ba42557c414f9dd52eSebastian Wilhelmi GEqualFunc key_equal_func) 792e0320d57e417f7d1c838d729a99545db2228e9Owen Taylor{ 807519c2338ae484135b44bbb7eb49719aea8c4ca3Lauri Alanko GHashTable *hash_table; 812d68cbbb7d37d3f265bf1087e6ddedcc58bc62beTim Janik guint i; 822d68cbbb7d37d3f265bf1087e6ddedcc58bc62beTim Janik 837519c2338ae484135b44bbb7eb49719aea8c4ca3Lauri Alanko hash_table = g_new (GHashTable, 1); 847519c2338ae484135b44bbb7eb49719aea8c4ca3Lauri Alanko hash_table->size = HASH_TABLE_MIN_SIZE; 852e0320d57e417f7d1c838d729a99545db2228e9Owen Taylor hash_table->nnodes = 0; 867519c2338ae484135b44bbb7eb49719aea8c4ca3Lauri Alanko hash_table->hash_func = hash_func ? hash_func : g_direct_hash; 87267b6813703e24ef60d0e8ba42557c414f9dd52eSebastian Wilhelmi hash_table->key_equal_func = key_equal_func; 887519c2338ae484135b44bbb7eb49719aea8c4ca3Lauri Alanko hash_table->nodes = g_new (GHashNode*, hash_table->size); 892d68cbbb7d37d3f265bf1087e6ddedcc58bc62beTim Janik 907519c2338ae484135b44bbb7eb49719aea8c4ca3Lauri Alanko for (i = 0; i < hash_table->size; i++) 917519c2338ae484135b44bbb7eb49719aea8c4ca3Lauri Alanko hash_table->nodes[i] = NULL; 922d68cbbb7d37d3f265bf1087e6ddedcc58bc62beTim Janik 937519c2338ae484135b44bbb7eb49719aea8c4ca3Lauri Alanko return hash_table; 942e0320d57e417f7d1c838d729a99545db2228e9Owen Taylor} 952e0320d57e417f7d1c838d729a99545db2228e9Owen Taylor 962e0320d57e417f7d1c838d729a99545db2228e9Owen Taylorvoid 972e0320d57e417f7d1c838d729a99545db2228e9Owen Taylorg_hash_table_destroy (GHashTable *hash_table) 982e0320d57e417f7d1c838d729a99545db2228e9Owen Taylor{ 992d68cbbb7d37d3f265bf1087e6ddedcc58bc62beTim Janik guint i; 1002d68cbbb7d37d3f265bf1087e6ddedcc58bc62beTim Janik 1012d68cbbb7d37d3f265bf1087e6ddedcc58bc62beTim Janik g_return_if_fail (hash_table != NULL); 1022d68cbbb7d37d3f265bf1087e6ddedcc58bc62beTim Janik 1037519c2338ae484135b44bbb7eb49719aea8c4ca3Lauri Alanko for (i = 0; i < hash_table->size; i++) 1043a14f25fdfa715f1a79b74bcf3916885053ff307Tim Janik g_hash_nodes_destroy (hash_table->nodes[i]); 1052d68cbbb7d37d3f265bf1087e6ddedcc58bc62beTim Janik 1067519c2338ae484135b44bbb7eb49719aea8c4ca3Lauri Alanko g_free (hash_table->nodes); 1077519c2338ae484135b44bbb7eb49719aea8c4ca3Lauri Alanko g_free (hash_table); 1082e0320d57e417f7d1c838d729a99545db2228e9Owen Taylor} 1092e0320d57e417f7d1c838d729a99545db2228e9Owen Taylor 110d5492a983cfa048658af8b03f833ddb3c0cf355eESTstatic inline GHashNode** 111d5492a983cfa048658af8b03f833ddb3c0cf355eESTg_hash_table_lookup_node (GHashTable *hash_table, 112d5492a983cfa048658af8b03f833ddb3c0cf355eEST gconstpointer key) 1132e0320d57e417f7d1c838d729a99545db2228e9Owen Taylor{ 114d5492a983cfa048658af8b03f833ddb3c0cf355eEST GHashNode **node; 1152d68cbbb7d37d3f265bf1087e6ddedcc58bc62beTim Janik 116d5492a983cfa048658af8b03f833ddb3c0cf355eEST node = &hash_table->nodes 117d5492a983cfa048658af8b03f833ddb3c0cf355eEST [(* hash_table->hash_func) (key) % hash_table->size]; 1182d68cbbb7d37d3f265bf1087e6ddedcc58bc62beTim Janik 1192d68cbbb7d37d3f265bf1087e6ddedcc58bc62beTim Janik /* Hash table lookup needs to be fast. 1202d68cbbb7d37d3f265bf1087e6ddedcc58bc62beTim Janik * We therefore remove the extra conditional of testing 121267b6813703e24ef60d0e8ba42557c414f9dd52eSebastian Wilhelmi * whether to call the key_equal_func or not from 1222d68cbbb7d37d3f265bf1087e6ddedcc58bc62beTim Janik * the inner loop. 1232d68cbbb7d37d3f265bf1087e6ddedcc58bc62beTim Janik */ 124267b6813703e24ef60d0e8ba42557c414f9dd52eSebastian Wilhelmi if (hash_table->key_equal_func) 125267b6813703e24ef60d0e8ba42557c414f9dd52eSebastian Wilhelmi while (*node && !(*hash_table->key_equal_func) ((*node)->key, key)) 126d5492a983cfa048658af8b03f833ddb3c0cf355eEST node = &(*node)->next; 1272d68cbbb7d37d3f265bf1087e6ddedcc58bc62beTim Janik else 128d5492a983cfa048658af8b03f833ddb3c0cf355eEST while (*node && (*node)->key != key) 129d5492a983cfa048658af8b03f833ddb3c0cf355eEST node = &(*node)->next; 1302d68cbbb7d37d3f265bf1087e6ddedcc58bc62beTim Janik 1312d68cbbb7d37d3f265bf1087e6ddedcc58bc62beTim Janik return node; 1322d68cbbb7d37d3f265bf1087e6ddedcc58bc62beTim Janik} 1332e0320d57e417f7d1c838d729a99545db2228e9Owen Taylor 1342d68cbbb7d37d3f265bf1087e6ddedcc58bc62beTim Janikgpointer 1352d68cbbb7d37d3f265bf1087e6ddedcc58bc62beTim Janikg_hash_table_lookup (GHashTable *hash_table, 1362d68cbbb7d37d3f265bf1087e6ddedcc58bc62beTim Janik gconstpointer key) 1372d68cbbb7d37d3f265bf1087e6ddedcc58bc62beTim Janik{ 1382d68cbbb7d37d3f265bf1087e6ddedcc58bc62beTim Janik GHashNode *node; 1392d68cbbb7d37d3f265bf1087e6ddedcc58bc62beTim Janik 1402d68cbbb7d37d3f265bf1087e6ddedcc58bc62beTim Janik g_return_val_if_fail (hash_table != NULL, NULL); 1412d68cbbb7d37d3f265bf1087e6ddedcc58bc62beTim Janik 142d5492a983cfa048658af8b03f833ddb3c0cf355eEST node = *g_hash_table_lookup_node (hash_table, key); 1432d68cbbb7d37d3f265bf1087e6ddedcc58bc62beTim Janik 1442d68cbbb7d37d3f265bf1087e6ddedcc58bc62beTim Janik return node ? node->value : NULL; 1452d68cbbb7d37d3f265bf1087e6ddedcc58bc62beTim Janik} 1467401460a60504dad7b77219d0ba3d93112e12444Manish Singh 1472d68cbbb7d37d3f265bf1087e6ddedcc58bc62beTim Janikvoid 1482d68cbbb7d37d3f265bf1087e6ddedcc58bc62beTim Janikg_hash_table_insert (GHashTable *hash_table, 1492d68cbbb7d37d3f265bf1087e6ddedcc58bc62beTim Janik gpointer key, 1502d68cbbb7d37d3f265bf1087e6ddedcc58bc62beTim Janik gpointer value) 1512d68cbbb7d37d3f265bf1087e6ddedcc58bc62beTim Janik{ 152d5492a983cfa048658af8b03f833ddb3c0cf355eEST GHashNode **node; 1532d68cbbb7d37d3f265bf1087e6ddedcc58bc62beTim Janik 1542d68cbbb7d37d3f265bf1087e6ddedcc58bc62beTim Janik g_return_if_fail (hash_table != NULL); 1552d68cbbb7d37d3f265bf1087e6ddedcc58bc62beTim Janik 156d5492a983cfa048658af8b03f833ddb3c0cf355eEST node = g_hash_table_lookup_node (hash_table, key); 157d5492a983cfa048658af8b03f833ddb3c0cf355eEST 158d5492a983cfa048658af8b03f833ddb3c0cf355eEST if (*node) 1597519c2338ae484135b44bbb7eb49719aea8c4ca3Lauri Alanko { 1607519c2338ae484135b44bbb7eb49719aea8c4ca3Lauri Alanko /* do not reset node->key in this place, keeping 1617519c2338ae484135b44bbb7eb49719aea8c4ca3Lauri Alanko * the old key might be intended. 1627519c2338ae484135b44bbb7eb49719aea8c4ca3Lauri Alanko * a g_hash_table_remove/g_hash_table_insert pair 1637519c2338ae484135b44bbb7eb49719aea8c4ca3Lauri Alanko * can be used otherwise. 1647519c2338ae484135b44bbb7eb49719aea8c4ca3Lauri Alanko * 1657519c2338ae484135b44bbb7eb49719aea8c4ca3Lauri Alanko * node->key = key; */ 166d5492a983cfa048658af8b03f833ddb3c0cf355eEST (*node)->value = value; 167d5492a983cfa048658af8b03f833ddb3c0cf355eEST } 168d5492a983cfa048658af8b03f833ddb3c0cf355eEST else 169d5492a983cfa048658af8b03f833ddb3c0cf355eEST { 170d5492a983cfa048658af8b03f833ddb3c0cf355eEST *node = g_hash_node_new (key, value); 171d5492a983cfa048658af8b03f833ddb3c0cf355eEST hash_table->nnodes++; 17284114c5321e4d7e4701f77f7f0e2b9b739d4035cSebastian Wilhelmi g_hash_table_resize (hash_table); 1732e0320d57e417f7d1c838d729a99545db2228e9Owen Taylor } 1742e0320d57e417f7d1c838d729a99545db2228e9Owen Taylor} 1752e0320d57e417f7d1c838d729a99545db2228e9Owen Taylor 1769a8c33db5cc37bc3c6bd4794a03f4b99a847ff4aTim Janikgboolean 1779a8c33db5cc37bc3c6bd4794a03f4b99a847ff4aTim Janikg_hash_table_remove (GHashTable *hash_table, 1789a8c33db5cc37bc3c6bd4794a03f4b99a847ff4aTim Janik gconstpointer key) 1792e0320d57e417f7d1c838d729a99545db2228e9Owen Taylor{ 180d5492a983cfa048658af8b03f833ddb3c0cf355eEST GHashNode **node, *dest; 1812d68cbbb7d37d3f265bf1087e6ddedcc58bc62beTim Janik 1829a8c33db5cc37bc3c6bd4794a03f4b99a847ff4aTim Janik g_return_val_if_fail (hash_table != NULL, FALSE); 1832d68cbbb7d37d3f265bf1087e6ddedcc58bc62beTim Janik 184d5492a983cfa048658af8b03f833ddb3c0cf355eEST node = g_hash_table_lookup_node (hash_table, key); 185d5492a983cfa048658af8b03f833ddb3c0cf355eEST if (*node) 1862e0320d57e417f7d1c838d729a99545db2228e9Owen Taylor { 187d5492a983cfa048658af8b03f833ddb3c0cf355eEST dest = *node; 188d5492a983cfa048658af8b03f833ddb3c0cf355eEST (*node) = dest->next; 189d5492a983cfa048658af8b03f833ddb3c0cf355eEST g_hash_node_destroy (dest); 1907519c2338ae484135b44bbb7eb49719aea8c4ca3Lauri Alanko hash_table->nnodes--; 1912d68cbbb7d37d3f265bf1087e6ddedcc58bc62beTim Janik 19284114c5321e4d7e4701f77f7f0e2b9b739d4035cSebastian Wilhelmi g_hash_table_resize (hash_table); 1939a8c33db5cc37bc3c6bd4794a03f4b99a847ff4aTim Janik 1949a8c33db5cc37bc3c6bd4794a03f4b99a847ff4aTim Janik return TRUE; 195448e792b0a9b092f9593eaa51e16acd8abe54c76Jeff Garzik } 1969a8c33db5cc37bc3c6bd4794a03f4b99a847ff4aTim Janik 1979a8c33db5cc37bc3c6bd4794a03f4b99a847ff4aTim Janik return FALSE; 1982e0320d57e417f7d1c838d729a99545db2228e9Owen Taylor} 1992e0320d57e417f7d1c838d729a99545db2228e9Owen Taylor 2007519c2338ae484135b44bbb7eb49719aea8c4ca3Lauri Alankogboolean 2015b52f015356729919cfd3b68cd5ac3c27a35e147Lauri Alankog_hash_table_lookup_extended (GHashTable *hash_table, 2025b52f015356729919cfd3b68cd5ac3c27a35e147Lauri Alanko gconstpointer lookup_key, 2035b52f015356729919cfd3b68cd5ac3c27a35e147Lauri Alanko gpointer *orig_key, 2045b52f015356729919cfd3b68cd5ac3c27a35e147Lauri Alanko gpointer *value) 2057519c2338ae484135b44bbb7eb49719aea8c4ca3Lauri Alanko{ 2067519c2338ae484135b44bbb7eb49719aea8c4ca3Lauri Alanko GHashNode *node; 2072d68cbbb7d37d3f265bf1087e6ddedcc58bc62beTim Janik 2082d68cbbb7d37d3f265bf1087e6ddedcc58bc62beTim Janik g_return_val_if_fail (hash_table != NULL, FALSE); 2092d68cbbb7d37d3f265bf1087e6ddedcc58bc62beTim Janik 210d5492a983cfa048658af8b03f833ddb3c0cf355eEST node = *g_hash_table_lookup_node (hash_table, lookup_key); 2112d68cbbb7d37d3f265bf1087e6ddedcc58bc62beTim Janik 2127519c2338ae484135b44bbb7eb49719aea8c4ca3Lauri Alanko if (node) 2132e0320d57e417f7d1c838d729a99545db2228e9Owen Taylor { 2147519c2338ae484135b44bbb7eb49719aea8c4ca3Lauri Alanko if (orig_key) 2157519c2338ae484135b44bbb7eb49719aea8c4ca3Lauri Alanko *orig_key = node->key; 2167519c2338ae484135b44bbb7eb49719aea8c4ca3Lauri Alanko if (value) 2177519c2338ae484135b44bbb7eb49719aea8c4ca3Lauri Alanko *value = node->value; 2187519c2338ae484135b44bbb7eb49719aea8c4ca3Lauri Alanko return TRUE; 2192e0320d57e417f7d1c838d729a99545db2228e9Owen Taylor } 2207519c2338ae484135b44bbb7eb49719aea8c4ca3Lauri Alanko else 2217519c2338ae484135b44bbb7eb49719aea8c4ca3Lauri Alanko return FALSE; 2222e0320d57e417f7d1c838d729a99545db2228e9Owen Taylor} 2232e0320d57e417f7d1c838d729a99545db2228e9Owen Taylor 2242e0320d57e417f7d1c838d729a99545db2228e9Owen Taylorvoid 2252e0320d57e417f7d1c838d729a99545db2228e9Owen Taylorg_hash_table_freeze (GHashTable *hash_table) 2262e0320d57e417f7d1c838d729a99545db2228e9Owen Taylor{ 22784114c5321e4d7e4701f77f7f0e2b9b739d4035cSebastian Wilhelmi#ifdef G_ENABLE_DEBUG 22884114c5321e4d7e4701f77f7f0e2b9b739d4035cSebastian Wilhelmi static gboolean first_call = TRUE; 22984114c5321e4d7e4701f77f7f0e2b9b739d4035cSebastian Wilhelmi 23084114c5321e4d7e4701f77f7f0e2b9b739d4035cSebastian Wilhelmi if (first_call) 23184114c5321e4d7e4701f77f7f0e2b9b739d4035cSebastian Wilhelmi { 23284114c5321e4d7e4701f77f7f0e2b9b739d4035cSebastian Wilhelmi g_warning("g_hash_table_freeze and g_hash_table_thaw are deprecated."); 23384114c5321e4d7e4701f77f7f0e2b9b739d4035cSebastian Wilhelmi first_call = FALSE; 23484114c5321e4d7e4701f77f7f0e2b9b739d4035cSebastian Wilhelmi } 23584114c5321e4d7e4701f77f7f0e2b9b739d4035cSebastian Wilhelmi#endif /* G_ENABLE_DEBUG */ 2362e0320d57e417f7d1c838d729a99545db2228e9Owen Taylor} 2372e0320d57e417f7d1c838d729a99545db2228e9Owen Taylor 2382e0320d57e417f7d1c838d729a99545db2228e9Owen Taylorvoid 2392e0320d57e417f7d1c838d729a99545db2228e9Owen Taylorg_hash_table_thaw (GHashTable *hash_table) 2402e0320d57e417f7d1c838d729a99545db2228e9Owen Taylor{ 2412e0320d57e417f7d1c838d729a99545db2228e9Owen Taylor} 2422e0320d57e417f7d1c838d729a99545db2228e9Owen Taylor 243d31ba84c8ea40b6f0199318e43cc2bb2e816c586Tim Janikguint 2442d68cbbb7d37d3f265bf1087e6ddedcc58bc62beTim Janikg_hash_table_foreach_remove (GHashTable *hash_table, 2452d68cbbb7d37d3f265bf1087e6ddedcc58bc62beTim Janik GHRFunc func, 2462d68cbbb7d37d3f265bf1087e6ddedcc58bc62beTim Janik gpointer user_data) 247034e7c0339f64d4d52a53f2324daa2fca0332addManish Singh{ 248034e7c0339f64d4d52a53f2324daa2fca0332addManish Singh GHashNode *node, *prev; 2492d68cbbb7d37d3f265bf1087e6ddedcc58bc62beTim Janik guint i; 250d31ba84c8ea40b6f0199318e43cc2bb2e816c586Tim Janik guint deleted = 0; 2512d68cbbb7d37d3f265bf1087e6ddedcc58bc62beTim Janik 2522d68cbbb7d37d3f265bf1087e6ddedcc58bc62beTim Janik g_return_val_if_fail (hash_table != NULL, 0); 2532d68cbbb7d37d3f265bf1087e6ddedcc58bc62beTim Janik g_return_val_if_fail (func != NULL, 0); 2542d68cbbb7d37d3f265bf1087e6ddedcc58bc62beTim Janik 255034e7c0339f64d4d52a53f2324daa2fca0332addManish Singh for (i = 0; i < hash_table->size; i++) 256034e7c0339f64d4d52a53f2324daa2fca0332addManish Singh { 257034e7c0339f64d4d52a53f2324daa2fca0332addManish Singh restart: 2582d68cbbb7d37d3f265bf1087e6ddedcc58bc62beTim Janik 259034e7c0339f64d4d52a53f2324daa2fca0332addManish Singh prev = NULL; 2602d68cbbb7d37d3f265bf1087e6ddedcc58bc62beTim Janik 261034e7c0339f64d4d52a53f2324daa2fca0332addManish Singh for (node = hash_table->nodes[i]; node; prev = node, node = node->next) 262034e7c0339f64d4d52a53f2324daa2fca0332addManish Singh { 263034e7c0339f64d4d52a53f2324daa2fca0332addManish Singh if ((* func) (node->key, node->value, user_data)) 264034e7c0339f64d4d52a53f2324daa2fca0332addManish Singh { 265034e7c0339f64d4d52a53f2324daa2fca0332addManish Singh deleted += 1; 2662d68cbbb7d37d3f265bf1087e6ddedcc58bc62beTim Janik 267034e7c0339f64d4d52a53f2324daa2fca0332addManish Singh hash_table->nnodes -= 1; 2682d68cbbb7d37d3f265bf1087e6ddedcc58bc62beTim Janik 269034e7c0339f64d4d52a53f2324daa2fca0332addManish Singh if (prev) 270034e7c0339f64d4d52a53f2324daa2fca0332addManish Singh { 271034e7c0339f64d4d52a53f2324daa2fca0332addManish Singh prev->next = node->next; 2723a14f25fdfa715f1a79b74bcf3916885053ff307Tim Janik g_hash_node_destroy (node); 273034e7c0339f64d4d52a53f2324daa2fca0332addManish Singh node = prev; 274034e7c0339f64d4d52a53f2324daa2fca0332addManish Singh } 275034e7c0339f64d4d52a53f2324daa2fca0332addManish Singh else 276034e7c0339f64d4d52a53f2324daa2fca0332addManish Singh { 277034e7c0339f64d4d52a53f2324daa2fca0332addManish Singh hash_table->nodes[i] = node->next; 2783a14f25fdfa715f1a79b74bcf3916885053ff307Tim Janik g_hash_node_destroy (node); 279034e7c0339f64d4d52a53f2324daa2fca0332addManish Singh goto restart; 280034e7c0339f64d4d52a53f2324daa2fca0332addManish Singh } 281034e7c0339f64d4d52a53f2324daa2fca0332addManish Singh } 282034e7c0339f64d4d52a53f2324daa2fca0332addManish Singh } 283034e7c0339f64d4d52a53f2324daa2fca0332addManish Singh } 2842d68cbbb7d37d3f265bf1087e6ddedcc58bc62beTim Janik 28584114c5321e4d7e4701f77f7f0e2b9b739d4035cSebastian Wilhelmi g_hash_table_resize (hash_table); 2862d68cbbb7d37d3f265bf1087e6ddedcc58bc62beTim Janik 287034e7c0339f64d4d52a53f2324daa2fca0332addManish Singh return deleted; 288034e7c0339f64d4d52a53f2324daa2fca0332addManish Singh} 289034e7c0339f64d4d52a53f2324daa2fca0332addManish Singh 2902e0320d57e417f7d1c838d729a99545db2228e9Owen Taylorvoid 2912e0320d57e417f7d1c838d729a99545db2228e9Owen Taylorg_hash_table_foreach (GHashTable *hash_table, 2922d68cbbb7d37d3f265bf1087e6ddedcc58bc62beTim Janik GHFunc func, 2932d68cbbb7d37d3f265bf1087e6ddedcc58bc62beTim Janik gpointer user_data) 2942e0320d57e417f7d1c838d729a99545db2228e9Owen Taylor{ 2952e0320d57e417f7d1c838d729a99545db2228e9Owen Taylor GHashNode *node; 2962e0320d57e417f7d1c838d729a99545db2228e9Owen Taylor gint i; 2972d68cbbb7d37d3f265bf1087e6ddedcc58bc62beTim Janik 2982d68cbbb7d37d3f265bf1087e6ddedcc58bc62beTim Janik g_return_if_fail (hash_table != NULL); 2992d68cbbb7d37d3f265bf1087e6ddedcc58bc62beTim Janik g_return_if_fail (func != NULL); 3002d68cbbb7d37d3f265bf1087e6ddedcc58bc62beTim Janik 3017519c2338ae484135b44bbb7eb49719aea8c4ca3Lauri Alanko for (i = 0; i < hash_table->size; i++) 3027519c2338ae484135b44bbb7eb49719aea8c4ca3Lauri Alanko for (node = hash_table->nodes[i]; node; node = node->next) 3037519c2338ae484135b44bbb7eb49719aea8c4ca3Lauri Alanko (* func) (node->key, node->value, user_data); 3042e0320d57e417f7d1c838d729a99545db2228e9Owen Taylor} 3052e0320d57e417f7d1c838d729a99545db2228e9Owen Taylor 3067519c2338ae484135b44bbb7eb49719aea8c4ca3Lauri Alanko/* Returns the number of elements contained in the hash table. */ 307d31ba84c8ea40b6f0199318e43cc2bb2e816c586Tim Janikguint 3082d68cbbb7d37d3f265bf1087e6ddedcc58bc62beTim Janikg_hash_table_size (GHashTable *hash_table) 3097519c2338ae484135b44bbb7eb49719aea8c4ca3Lauri Alanko{ 3102d68cbbb7d37d3f265bf1087e6ddedcc58bc62beTim Janik g_return_val_if_fail (hash_table != NULL, 0); 3112d68cbbb7d37d3f265bf1087e6ddedcc58bc62beTim Janik 3127519c2338ae484135b44bbb7eb49719aea8c4ca3Lauri Alanko return hash_table->nnodes; 3137519c2338ae484135b44bbb7eb49719aea8c4ca3Lauri Alanko} 3142e0320d57e417f7d1c838d729a99545db2228e9Owen Taylor 3152e0320d57e417f7d1c838d729a99545db2228e9Owen Taylorstatic void 3162e0320d57e417f7d1c838d729a99545db2228e9Owen Taylorg_hash_table_resize (GHashTable *hash_table) 3172e0320d57e417f7d1c838d729a99545db2228e9Owen Taylor{ 3182e0320d57e417f7d1c838d729a99545db2228e9Owen Taylor GHashNode **new_nodes; 3192e0320d57e417f7d1c838d729a99545db2228e9Owen Taylor GHashNode *node; 3202e0320d57e417f7d1c838d729a99545db2228e9Owen Taylor GHashNode *next; 3212e0320d57e417f7d1c838d729a99545db2228e9Owen Taylor gfloat nodes_per_list; 3222e0320d57e417f7d1c838d729a99545db2228e9Owen Taylor guint hash_val; 3232e0320d57e417f7d1c838d729a99545db2228e9Owen Taylor gint new_size; 3242e0320d57e417f7d1c838d729a99545db2228e9Owen Taylor gint i; 3252d68cbbb7d37d3f265bf1087e6ddedcc58bc62beTim Janik 3267519c2338ae484135b44bbb7eb49719aea8c4ca3Lauri Alanko nodes_per_list = (gfloat) hash_table->nnodes / (gfloat) hash_table->size; 3272d68cbbb7d37d3f265bf1087e6ddedcc58bc62beTim Janik 3287519c2338ae484135b44bbb7eb49719aea8c4ca3Lauri Alanko if ((nodes_per_list > 0.3 || hash_table->size <= HASH_TABLE_MIN_SIZE) && 3297519c2338ae484135b44bbb7eb49719aea8c4ca3Lauri Alanko (nodes_per_list < 3.0 || hash_table->size >= HASH_TABLE_MAX_SIZE)) 3307519c2338ae484135b44bbb7eb49719aea8c4ca3Lauri Alanko return; 3312d68cbbb7d37d3f265bf1087e6ddedcc58bc62beTim Janik 3327401460a60504dad7b77219d0ba3d93112e12444Manish Singh new_size = CLAMP(g_spaced_primes_closest (hash_table->nnodes), 3337519c2338ae484135b44bbb7eb49719aea8c4ca3Lauri Alanko HASH_TABLE_MIN_SIZE, 3347519c2338ae484135b44bbb7eb49719aea8c4ca3Lauri Alanko HASH_TABLE_MAX_SIZE); 335448e792b0a9b092f9593eaa51e16acd8abe54c76Jeff Garzik new_nodes = g_new0 (GHashNode*, new_size); 3362d68cbbb7d37d3f265bf1087e6ddedcc58bc62beTim Janik 3377519c2338ae484135b44bbb7eb49719aea8c4ca3Lauri Alanko for (i = 0; i < hash_table->size; i++) 3387519c2338ae484135b44bbb7eb49719aea8c4ca3Lauri Alanko for (node = hash_table->nodes[i]; node; node = next) 3397519c2338ae484135b44bbb7eb49719aea8c4ca3Lauri Alanko { 3407519c2338ae484135b44bbb7eb49719aea8c4ca3Lauri Alanko next = node->next; 341448e792b0a9b092f9593eaa51e16acd8abe54c76Jeff Garzik 3427519c2338ae484135b44bbb7eb49719aea8c4ca3Lauri Alanko hash_val = (* hash_table->hash_func) (node->key) % new_size; 343448e792b0a9b092f9593eaa51e16acd8abe54c76Jeff Garzik 3447519c2338ae484135b44bbb7eb49719aea8c4ca3Lauri Alanko node->next = new_nodes[hash_val]; 3457519c2338ae484135b44bbb7eb49719aea8c4ca3Lauri Alanko new_nodes[hash_val] = node; 3467519c2338ae484135b44bbb7eb49719aea8c4ca3Lauri Alanko } 3472d68cbbb7d37d3f265bf1087e6ddedcc58bc62beTim Janik 3487519c2338ae484135b44bbb7eb49719aea8c4ca3Lauri Alanko g_free (hash_table->nodes); 3497519c2338ae484135b44bbb7eb49719aea8c4ca3Lauri Alanko hash_table->nodes = new_nodes; 3507519c2338ae484135b44bbb7eb49719aea8c4ca3Lauri Alanko hash_table->size = new_size; 3517519c2338ae484135b44bbb7eb49719aea8c4ca3Lauri Alanko} 3527519c2338ae484135b44bbb7eb49719aea8c4ca3Lauri Alanko 3532e0320d57e417f7d1c838d729a99545db2228e9Owen Taylorstatic GHashNode* 3542e0320d57e417f7d1c838d729a99545db2228e9Owen Taylorg_hash_node_new (gpointer key, 3552e0320d57e417f7d1c838d729a99545db2228e9Owen Taylor gpointer value) 3562e0320d57e417f7d1c838d729a99545db2228e9Owen Taylor{ 3572e0320d57e417f7d1c838d729a99545db2228e9Owen Taylor GHashNode *hash_node; 3582d68cbbb7d37d3f265bf1087e6ddedcc58bc62beTim Janik 359b2e318ff3ecc50d72121a4e8561442a6d79a7a84Tim Janik G_LOCK (g_hash_global); 3602e0320d57e417f7d1c838d729a99545db2228e9Owen Taylor if (node_free_list) 3612e0320d57e417f7d1c838d729a99545db2228e9Owen Taylor { 3622e0320d57e417f7d1c838d729a99545db2228e9Owen Taylor hash_node = node_free_list; 3632e0320d57e417f7d1c838d729a99545db2228e9Owen Taylor node_free_list = node_free_list->next; 3642e0320d57e417f7d1c838d729a99545db2228e9Owen Taylor } 3652e0320d57e417f7d1c838d729a99545db2228e9Owen Taylor else 3662e0320d57e417f7d1c838d729a99545db2228e9Owen Taylor { 3672e0320d57e417f7d1c838d729a99545db2228e9Owen Taylor if (!node_mem_chunk) 3682e0320d57e417f7d1c838d729a99545db2228e9Owen Taylor node_mem_chunk = g_mem_chunk_new ("hash node mem chunk", 3692e0320d57e417f7d1c838d729a99545db2228e9Owen Taylor sizeof (GHashNode), 3702e0320d57e417f7d1c838d729a99545db2228e9Owen Taylor 1024, G_ALLOC_ONLY); 3712d68cbbb7d37d3f265bf1087e6ddedcc58bc62beTim Janik 3722e0320d57e417f7d1c838d729a99545db2228e9Owen Taylor hash_node = g_chunk_new (GHashNode, node_mem_chunk); 3732e0320d57e417f7d1c838d729a99545db2228e9Owen Taylor } 374b2e318ff3ecc50d72121a4e8561442a6d79a7a84Tim Janik G_UNLOCK (g_hash_global); 3752d68cbbb7d37d3f265bf1087e6ddedcc58bc62beTim Janik 3762e0320d57e417f7d1c838d729a99545db2228e9Owen Taylor hash_node->key = key; 3772e0320d57e417f7d1c838d729a99545db2228e9Owen Taylor hash_node->value = value; 3782e0320d57e417f7d1c838d729a99545db2228e9Owen Taylor hash_node->next = NULL; 3792d68cbbb7d37d3f265bf1087e6ddedcc58bc62beTim Janik 3802e0320d57e417f7d1c838d729a99545db2228e9Owen Taylor return hash_node; 3812e0320d57e417f7d1c838d729a99545db2228e9Owen Taylor} 3822e0320d57e417f7d1c838d729a99545db2228e9Owen Taylor 3832e0320d57e417f7d1c838d729a99545db2228e9Owen Taylorstatic void 3843a14f25fdfa715f1a79b74bcf3916885053ff307Tim Janikg_hash_node_destroy (GHashNode *hash_node) 3852e0320d57e417f7d1c838d729a99545db2228e9Owen Taylor{ 3868c90d7766b1708a8bcb3cb96988b6b7fc92c2e59Sebastian Wilhelmi 3878c90d7766b1708a8bcb3cb96988b6b7fc92c2e59Sebastian Wilhelmi#ifdef ENABLE_GC_FRIENDLY 3888c90d7766b1708a8bcb3cb96988b6b7fc92c2e59Sebastian Wilhelmi hash_node->key = NULL; 3898c90d7766b1708a8bcb3cb96988b6b7fc92c2e59Sebastian Wilhelmi hash_node->value = NULL; 3908c90d7766b1708a8bcb3cb96988b6b7fc92c2e59Sebastian Wilhelmi#endif /* ENABLE_GC_FRIENDLY */ 3918c90d7766b1708a8bcb3cb96988b6b7fc92c2e59Sebastian Wilhelmi 392b2e318ff3ecc50d72121a4e8561442a6d79a7a84Tim Janik G_LOCK (g_hash_global); 3937519c2338ae484135b44bbb7eb49719aea8c4ca3Lauri Alanko hash_node->next = node_free_list; 3947519c2338ae484135b44bbb7eb49719aea8c4ca3Lauri Alanko node_free_list = hash_node; 395b2e318ff3ecc50d72121a4e8561442a6d79a7a84Tim Janik G_UNLOCK (g_hash_global); 3962e0320d57e417f7d1c838d729a99545db2228e9Owen Taylor} 3972e0320d57e417f7d1c838d729a99545db2228e9Owen Taylor 3982e0320d57e417f7d1c838d729a99545db2228e9Owen Taylorstatic void 3993a14f25fdfa715f1a79b74bcf3916885053ff307Tim Janikg_hash_nodes_destroy (GHashNode *hash_node) 4002e0320d57e417f7d1c838d729a99545db2228e9Owen Taylor{ 401448e792b0a9b092f9593eaa51e16acd8abe54c76Jeff Garzik if (hash_node) 402448e792b0a9b092f9593eaa51e16acd8abe54c76Jeff Garzik { 403448e792b0a9b092f9593eaa51e16acd8abe54c76Jeff Garzik GHashNode *node = hash_node; 4042d68cbbb7d37d3f265bf1087e6ddedcc58bc62beTim Janik 405448e792b0a9b092f9593eaa51e16acd8abe54c76Jeff Garzik while (node->next) 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 node = node->next; 4128c90d7766b1708a8bcb3cb96988b6b7fc92c2e59Sebastian Wilhelmi } 4138c90d7766b1708a8bcb3cb96988b6b7fc92c2e59Sebastian Wilhelmi 4148c90d7766b1708a8bcb3cb96988b6b7fc92c2e59Sebastian Wilhelmi#ifdef ENABLE_GC_FRIENDLY 4158c90d7766b1708a8bcb3cb96988b6b7fc92c2e59Sebastian Wilhelmi node->key = NULL; 4168c90d7766b1708a8bcb3cb96988b6b7fc92c2e59Sebastian Wilhelmi node->value = NULL; 4178c90d7766b1708a8bcb3cb96988b6b7fc92c2e59Sebastian Wilhelmi#endif /* ENABLE_GC_FRIENDLY */ 4188c90d7766b1708a8bcb3cb96988b6b7fc92c2e59Sebastian Wilhelmi 419448e792b0a9b092f9593eaa51e16acd8abe54c76Jeff Garzik G_LOCK (g_hash_global); 420448e792b0a9b092f9593eaa51e16acd8abe54c76Jeff Garzik node->next = node_free_list; 421448e792b0a9b092f9593eaa51e16acd8abe54c76Jeff Garzik node_free_list = hash_node; 422448e792b0a9b092f9593eaa51e16acd8abe54c76Jeff Garzik G_UNLOCK (g_hash_global); 423448e792b0a9b092f9593eaa51e16acd8abe54c76Jeff Garzik } 424df9a49ec3cbb19e58be929548cfba12452c55d83Josh MacDonald} 425