12e0320d57e417f7d1c838d729a99545db2228e9Owen Taylor/* GLIB - Library of useful routines for C programming 22e0320d57e417f7d1c838d729a99545db2228e9Owen Taylor * Copyright (C) 1995-1997 Peter Mattis, Spencer Kimball and Josh MacDonald 32e0320d57e417f7d1c838d729a99545db2228e9Owen Taylor * 42e0320d57e417f7d1c838d729a99545db2228e9Owen Taylor * This library is free software; you can redistribute it and/or 5c9bd7542e1a28ba9de60048361c0a97d251833e7Tim Janik * modify it under the terms of the GNU Lesser General Public 62e0320d57e417f7d1c838d729a99545db2228e9Owen Taylor * License as published by the Free Software Foundation; either 72e0320d57e417f7d1c838d729a99545db2228e9Owen Taylor * version 2 of the License, or (at your option) any later version. 82e0320d57e417f7d1c838d729a99545db2228e9Owen Taylor * 92e0320d57e417f7d1c838d729a99545db2228e9Owen Taylor * This library is distributed in the hope that it will be useful, 102e0320d57e417f7d1c838d729a99545db2228e9Owen Taylor * but WITHOUT ANY WARRANTY; without even the implied warranty of 118eed88b24e86f16021d94d9b16f7a2bc895d9239Ryan Lortie * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the GNU 12c9bd7542e1a28ba9de60048361c0a97d251833e7Tim Janik * Lesser General Public License for more details. 132e0320d57e417f7d1c838d729a99545db2228e9Owen Taylor * 14c9bd7542e1a28ba9de60048361c0a97d251833e7Tim Janik * You should have received a copy of the GNU Lesser General Public 152e0320d57e417f7d1c838d729a99545db2228e9Owen Taylor * License along with this library; if not, write to the 162e0320d57e417f7d1c838d729a99545db2228e9Owen Taylor * Free Software Foundation, Inc., 59 Temple Place - Suite 330, 172e0320d57e417f7d1c838d729a99545db2228e9Owen Taylor * Boston, MA 02111-1307, USA. 182e0320d57e417f7d1c838d729a99545db2228e9Owen Taylor */ 19931ea952650b013b834041b91b0c37a748ffd449Owen Taylor 20b9ef2b41db975061960e2217220668c2a5d563daCST/* 21c9bd7542e1a28ba9de60048361c0a97d251833e7Tim Janik * Modified by the GLib Team and others 1997-2000. See the AUTHORS 22b9ef2b41db975061960e2217220668c2a5d563daCST * file for a list of people on the GLib Team. See the ChangeLog 23b9ef2b41db975061960e2217220668c2a5d563daCST * files for a list of changes. These files are distributed with 248eed88b24e86f16021d94d9b16f7a2bc895d9239Ryan Lortie * GLib at ftp://ftp.gtk.org/pub/gtk/. 25b9ef2b41db975061960e2217220668c2a5d563daCST */ 26b9ef2b41db975061960e2217220668c2a5d563daCST 278eed88b24e86f16021d94d9b16f7a2bc895d9239Ryan Lortie/* 28931ea952650b013b834041b91b0c37a748ffd449Owen Taylor * MT safe 29931ea952650b013b834041b91b0c37a748ffd449Owen Taylor */ 30931ea952650b013b834041b91b0c37a748ffd449Owen Taylor 31bbbd329ff5bd634b4e1d4fb43b13538779e44a78Owen Taylor#include "config.h" 322fb47703e2929d300a3f804268a36d50543b4a2cSebastian Wilhelmi 33991b625aea5a8fbd7971b17154a0e01366027babHans Petter Jansson#include <string.h> /* memset */ 34991b625aea5a8fbd7971b17154a0e01366027babHans Petter Jansson 352e0320d57e417f7d1c838d729a99545db2228e9Owen Taylor#include "glib.h" 36608a31b98e1420f487190871ee7312db2643d93dMatthias Clasen#include "galias.h" 372e0320d57e417f7d1c838d729a99545db2228e9Owen Taylor 38991b625aea5a8fbd7971b17154a0e01366027babHans Petter Jansson#define HASH_TABLE_MIN_SHIFT 3 /* 1 << 3 == 8 buckets */ 392e0320d57e417f7d1c838d729a99545db2228e9Owen Taylor 402e0320d57e417f7d1c838d729a99545db2228e9Owen Taylortypedef struct _GHashNode GHashNode; 412e0320d57e417f7d1c838d729a99545db2228e9Owen Taylor 422e0320d57e417f7d1c838d729a99545db2228e9Owen Taylorstruct _GHashNode 432e0320d57e417f7d1c838d729a99545db2228e9Owen Taylor{ 44a2b269bae3315a2ea772b741fb62f683c1db5770Sven Neumann gpointer key; 45a2b269bae3315a2ea772b741fb62f683c1db5770Sven Neumann gpointer value; 46991b625aea5a8fbd7971b17154a0e01366027babHans Petter Jansson 47991b625aea5a8fbd7971b17154a0e01366027babHans Petter Jansson /* If key_hash == 0, node is not in use 48991b625aea5a8fbd7971b17154a0e01366027babHans Petter Jansson * If key_hash == 1, node is a tombstone 49991b625aea5a8fbd7971b17154a0e01366027babHans Petter Jansson * If key_hash >= 2, node contains data */ 501bd89934513921526da2d9e6463faeda8e4d76a7Tim Janik guint key_hash; 512e0320d57e417f7d1c838d729a99545db2228e9Owen Taylor}; 522e0320d57e417f7d1c838d729a99545db2228e9Owen Taylor 537519c2338ae484135b44bbb7eb49719aea8c4ca3Lauri Alankostruct _GHashTable 542e0320d57e417f7d1c838d729a99545db2228e9Owen Taylor{ 55a2b269bae3315a2ea772b741fb62f683c1db5770Sven Neumann gint size; 56991b625aea5a8fbd7971b17154a0e01366027babHans Petter Jansson gint mod; 57991b625aea5a8fbd7971b17154a0e01366027babHans Petter Jansson guint mask; 58a2b269bae3315a2ea772b741fb62f683c1db5770Sven Neumann gint nnodes; 59991b625aea5a8fbd7971b17154a0e01366027babHans Petter Jansson gint noccupied; /* nnodes + tombstones */ 60991b625aea5a8fbd7971b17154a0e01366027babHans Petter Jansson GHashNode *nodes; 61a2b269bae3315a2ea772b741fb62f683c1db5770Sven Neumann GHashFunc hash_func; 62a2b269bae3315a2ea772b741fb62f683c1db5770Sven Neumann GEqualFunc key_equal_func; 63b8bcb2b8391b6c21457d83d485c754b01cb276bdMatthias Clasen volatile gint ref_count; 64d741d3e7a344622e5a534c34e9e2c0488b2fea4dMatthias Clasen#ifndef G_DISABLE_ASSERT 65d741d3e7a344622e5a534c34e9e2c0488b2fea4dMatthias Clasen /* 66d741d3e7a344622e5a534c34e9e2c0488b2fea4dMatthias Clasen * Tracks the structure of the hash table, not its contents: is only 67d741d3e7a344622e5a534c34e9e2c0488b2fea4dMatthias Clasen * incremented when a node is added or removed (is not incremented 68d741d3e7a344622e5a534c34e9e2c0488b2fea4dMatthias Clasen * when the key or data of a node is modified). 69d741d3e7a344622e5a534c34e9e2c0488b2fea4dMatthias Clasen */ 70d741d3e7a344622e5a534c34e9e2c0488b2fea4dMatthias Clasen int version; 71d741d3e7a344622e5a534c34e9e2c0488b2fea4dMatthias Clasen#endif 72a2b269bae3315a2ea772b741fb62f683c1db5770Sven Neumann GDestroyNotify key_destroy_func; 73a2b269bae3315a2ea772b741fb62f683c1db5770Sven Neumann GDestroyNotify value_destroy_func; 742e0320d57e417f7d1c838d729a99545db2228e9Owen Taylor}; 752e0320d57e417f7d1c838d729a99545db2228e9Owen Taylor 76d741d3e7a344622e5a534c34e9e2c0488b2fea4dMatthias Clasentypedef struct 77d741d3e7a344622e5a534c34e9e2c0488b2fea4dMatthias Clasen{ 78991b625aea5a8fbd7971b17154a0e01366027babHans Petter Jansson GHashTable *hash_table; 79991b625aea5a8fbd7971b17154a0e01366027babHans Petter Jansson gpointer dummy1; 80991b625aea5a8fbd7971b17154a0e01366027babHans Petter Jansson gpointer dummy2; 81991b625aea5a8fbd7971b17154a0e01366027babHans Petter Jansson int position; 82991b625aea5a8fbd7971b17154a0e01366027babHans Petter Jansson gboolean dummy3; 83991b625aea5a8fbd7971b17154a0e01366027babHans Petter Jansson int version; 84d741d3e7a344622e5a534c34e9e2c0488b2fea4dMatthias Clasen} RealIter; 85d741d3e7a344622e5a534c34e9e2c0488b2fea4dMatthias Clasen 86991b625aea5a8fbd7971b17154a0e01366027babHans Petter Jansson/* Each table size has an associated prime modulo (the first prime 87991b625aea5a8fbd7971b17154a0e01366027babHans Petter Jansson * lower than the table size) used to find the initial bucket. Probing 88991b625aea5a8fbd7971b17154a0e01366027babHans Petter Jansson * then works modulo 2^n. The prime modulo is necessary to get a 89991b625aea5a8fbd7971b17154a0e01366027babHans Petter Jansson * good distribution with poor hash functions. */ 90991b625aea5a8fbd7971b17154a0e01366027babHans Petter Janssonstatic const gint prime_mod [] = 91991b625aea5a8fbd7971b17154a0e01366027babHans Petter Jansson{ 92991b625aea5a8fbd7971b17154a0e01366027babHans Petter Jansson 1, /* For 1 << 0 */ 93991b625aea5a8fbd7971b17154a0e01366027babHans Petter Jansson 2, 94991b625aea5a8fbd7971b17154a0e01366027babHans Petter Jansson 3, 95991b625aea5a8fbd7971b17154a0e01366027babHans Petter Jansson 7, 96991b625aea5a8fbd7971b17154a0e01366027babHans Petter Jansson 13, 97991b625aea5a8fbd7971b17154a0e01366027babHans Petter Jansson 31, 98991b625aea5a8fbd7971b17154a0e01366027babHans Petter Jansson 61, 99991b625aea5a8fbd7971b17154a0e01366027babHans Petter Jansson 127, 100991b625aea5a8fbd7971b17154a0e01366027babHans Petter Jansson 251, 101991b625aea5a8fbd7971b17154a0e01366027babHans Petter Jansson 509, 102991b625aea5a8fbd7971b17154a0e01366027babHans Petter Jansson 1021, 103991b625aea5a8fbd7971b17154a0e01366027babHans Petter Jansson 2039, 104991b625aea5a8fbd7971b17154a0e01366027babHans Petter Jansson 4093, 105991b625aea5a8fbd7971b17154a0e01366027babHans Petter Jansson 8191, 106991b625aea5a8fbd7971b17154a0e01366027babHans Petter Jansson 16381, 107991b625aea5a8fbd7971b17154a0e01366027babHans Petter Jansson 32749, 108991b625aea5a8fbd7971b17154a0e01366027babHans Petter Jansson 65521, /* For 1 << 16 */ 109991b625aea5a8fbd7971b17154a0e01366027babHans Petter Jansson 131071, 110991b625aea5a8fbd7971b17154a0e01366027babHans Petter Jansson 262139, 111991b625aea5a8fbd7971b17154a0e01366027babHans Petter Jansson 524287, 112991b625aea5a8fbd7971b17154a0e01366027babHans Petter Jansson 1048573, 113991b625aea5a8fbd7971b17154a0e01366027babHans Petter Jansson 2097143, 114991b625aea5a8fbd7971b17154a0e01366027babHans Petter Jansson 4194301, 115991b625aea5a8fbd7971b17154a0e01366027babHans Petter Jansson 8388593, 116991b625aea5a8fbd7971b17154a0e01366027babHans Petter Jansson 16777213, 117991b625aea5a8fbd7971b17154a0e01366027babHans Petter Jansson 33554393, 118991b625aea5a8fbd7971b17154a0e01366027babHans Petter Jansson 67108859, 119991b625aea5a8fbd7971b17154a0e01366027babHans Petter Jansson 134217689, 120991b625aea5a8fbd7971b17154a0e01366027babHans Petter Jansson 268435399, 121991b625aea5a8fbd7971b17154a0e01366027babHans Petter Jansson 536870909, 122991b625aea5a8fbd7971b17154a0e01366027babHans Petter Jansson 1073741789, 123991b625aea5a8fbd7971b17154a0e01366027babHans Petter Jansson 2147483647 /* For 1 << 31 */ 124991b625aea5a8fbd7971b17154a0e01366027babHans Petter Jansson}; 125991b625aea5a8fbd7971b17154a0e01366027babHans Petter Jansson 126991b625aea5a8fbd7971b17154a0e01366027babHans Petter Janssonstatic void 127991b625aea5a8fbd7971b17154a0e01366027babHans Petter Janssong_hash_table_set_shift (GHashTable *hash_table, gint shift) 128991b625aea5a8fbd7971b17154a0e01366027babHans Petter Jansson{ 129991b625aea5a8fbd7971b17154a0e01366027babHans Petter Jansson gint i; 130991b625aea5a8fbd7971b17154a0e01366027babHans Petter Jansson guint mask = 0; 131991b625aea5a8fbd7971b17154a0e01366027babHans Petter Jansson 132991b625aea5a8fbd7971b17154a0e01366027babHans Petter Jansson hash_table->size = 1 << shift; 133991b625aea5a8fbd7971b17154a0e01366027babHans Petter Jansson hash_table->mod = prime_mod [shift]; 134991b625aea5a8fbd7971b17154a0e01366027babHans Petter Jansson 135991b625aea5a8fbd7971b17154a0e01366027babHans Petter Jansson for (i = 0; i < shift; i++) 136991b625aea5a8fbd7971b17154a0e01366027babHans Petter Jansson { 137991b625aea5a8fbd7971b17154a0e01366027babHans Petter Jansson mask <<= 1; 138991b625aea5a8fbd7971b17154a0e01366027babHans Petter Jansson mask |= 1; 139991b625aea5a8fbd7971b17154a0e01366027babHans Petter Jansson } 140991b625aea5a8fbd7971b17154a0e01366027babHans Petter Jansson 141991b625aea5a8fbd7971b17154a0e01366027babHans Petter Jansson hash_table->mask = mask; 142991b625aea5a8fbd7971b17154a0e01366027babHans Petter Jansson} 143991b625aea5a8fbd7971b17154a0e01366027babHans Petter Jansson 144991b625aea5a8fbd7971b17154a0e01366027babHans Petter Janssonstatic gint 145991b625aea5a8fbd7971b17154a0e01366027babHans Petter Janssong_hash_table_find_closest_shift (gint n) 146991b625aea5a8fbd7971b17154a0e01366027babHans Petter Jansson{ 147991b625aea5a8fbd7971b17154a0e01366027babHans Petter Jansson gint i; 148991b625aea5a8fbd7971b17154a0e01366027babHans Petter Jansson 149991b625aea5a8fbd7971b17154a0e01366027babHans Petter Jansson for (i = 0; n; i++) 150991b625aea5a8fbd7971b17154a0e01366027babHans Petter Jansson n >>= 1; 151991b625aea5a8fbd7971b17154a0e01366027babHans Petter Jansson 152991b625aea5a8fbd7971b17154a0e01366027babHans Petter Jansson return i; 153991b625aea5a8fbd7971b17154a0e01366027babHans Petter Jansson} 154991b625aea5a8fbd7971b17154a0e01366027babHans Petter Jansson 155991b625aea5a8fbd7971b17154a0e01366027babHans Petter Janssonstatic void 156991b625aea5a8fbd7971b17154a0e01366027babHans Petter Janssong_hash_table_set_shift_from_size (GHashTable *hash_table, gint size) 157991b625aea5a8fbd7971b17154a0e01366027babHans Petter Jansson{ 158991b625aea5a8fbd7971b17154a0e01366027babHans Petter Jansson gint shift; 159991b625aea5a8fbd7971b17154a0e01366027babHans Petter Jansson 160991b625aea5a8fbd7971b17154a0e01366027babHans Petter Jansson shift = g_hash_table_find_closest_shift (size); 161991b625aea5a8fbd7971b17154a0e01366027babHans Petter Jansson shift = MAX (shift, HASH_TABLE_MIN_SHIFT); 162991b625aea5a8fbd7971b17154a0e01366027babHans Petter Jansson 163991b625aea5a8fbd7971b17154a0e01366027babHans Petter Jansson g_hash_table_set_shift (hash_table, shift); 164991b625aea5a8fbd7971b17154a0e01366027babHans Petter Jansson} 165991b625aea5a8fbd7971b17154a0e01366027babHans Petter Jansson 1664c78fb8faa88e94d6d348770e05467223832206eRyan Lortie/* 1670b89fa790abd7fcdd8a2b06c60a5327343526dd8Ryan Lortie * g_hash_table_lookup_node: 1680b89fa790abd7fcdd8a2b06c60a5327343526dd8Ryan Lortie * @hash_table: our #GHashTable 1690b89fa790abd7fcdd8a2b06c60a5327343526dd8Ryan Lortie * @key: the key to lookup against 1700b89fa790abd7fcdd8a2b06c60a5327343526dd8Ryan Lortie * @hash_return: optional key hash return location 171991b625aea5a8fbd7971b17154a0e01366027babHans Petter Jansson * Return value: index of the described #GHashNode 1720b89fa790abd7fcdd8a2b06c60a5327343526dd8Ryan Lortie * 1730b89fa790abd7fcdd8a2b06c60a5327343526dd8Ryan Lortie * Performs a lookup in the hash table. Virtually all hash operations 1740b89fa790abd7fcdd8a2b06c60a5327343526dd8Ryan Lortie * will use this function internally. 1750b89fa790abd7fcdd8a2b06c60a5327343526dd8Ryan Lortie * 1760b89fa790abd7fcdd8a2b06c60a5327343526dd8Ryan Lortie * This function first computes the hash value of the key using the 1770b89fa790abd7fcdd8a2b06c60a5327343526dd8Ryan Lortie * user's hash function. 1780b89fa790abd7fcdd8a2b06c60a5327343526dd8Ryan Lortie * 1790b89fa790abd7fcdd8a2b06c60a5327343526dd8Ryan Lortie * If an entry in the table matching @key is found then this function 180991b625aea5a8fbd7971b17154a0e01366027babHans Petter Jansson * returns the index of that entry in the table, and if not, the 181991b625aea5a8fbd7971b17154a0e01366027babHans Petter Jansson * index of an empty node (never a tombstone). 1824c78fb8faa88e94d6d348770e05467223832206eRyan Lortie */ 183991b625aea5a8fbd7971b17154a0e01366027babHans Petter Janssonstatic inline guint 184ac44f9cb5aad7a678d057875774ce9c4ca64754eRyan Lortieg_hash_table_lookup_node (GHashTable *hash_table, 185991b625aea5a8fbd7971b17154a0e01366027babHans Petter Jansson gconstpointer key) 186ac44f9cb5aad7a678d057875774ce9c4ca64754eRyan Lortie{ 187991b625aea5a8fbd7971b17154a0e01366027babHans Petter Jansson GHashNode *node; 188991b625aea5a8fbd7971b17154a0e01366027babHans Petter Jansson guint node_index; 189ac44f9cb5aad7a678d057875774ce9c4ca64754eRyan Lortie guint hash_value; 190991b625aea5a8fbd7971b17154a0e01366027babHans Petter Jansson guint step = 0; 191991b625aea5a8fbd7971b17154a0e01366027babHans Petter Jansson 192991b625aea5a8fbd7971b17154a0e01366027babHans Petter Jansson /* Empty buckets have hash_value set to 0, and for tombstones, it's 1. 193991b625aea5a8fbd7971b17154a0e01366027babHans Petter Jansson * We need to make sure our hash value is not one of these. */ 194ac44f9cb5aad7a678d057875774ce9c4ca64754eRyan Lortie 195ac44f9cb5aad7a678d057875774ce9c4ca64754eRyan Lortie hash_value = (* hash_table->hash_func) (key); 196991b625aea5a8fbd7971b17154a0e01366027babHans Petter Jansson if (G_UNLIKELY (hash_value <= 1)) 197991b625aea5a8fbd7971b17154a0e01366027babHans Petter Jansson hash_value = 2; 198991b625aea5a8fbd7971b17154a0e01366027babHans Petter Jansson 199991b625aea5a8fbd7971b17154a0e01366027babHans Petter Jansson node_index = hash_value % hash_table->mod; 200991b625aea5a8fbd7971b17154a0e01366027babHans Petter Jansson node = &hash_table->nodes [node_index]; 201991b625aea5a8fbd7971b17154a0e01366027babHans Petter Jansson 202991b625aea5a8fbd7971b17154a0e01366027babHans Petter Jansson while (node->key_hash) 203ac44f9cb5aad7a678d057875774ce9c4ca64754eRyan Lortie { 204991b625aea5a8fbd7971b17154a0e01366027babHans Petter Jansson /* We first check if our full hash values 205991b625aea5a8fbd7971b17154a0e01366027babHans Petter Jansson * are equal so we can avoid calling the full-blown 206991b625aea5a8fbd7971b17154a0e01366027babHans Petter Jansson * key equality function in most cases. 207991b625aea5a8fbd7971b17154a0e01366027babHans Petter Jansson */ 208ac44f9cb5aad7a678d057875774ce9c4ca64754eRyan Lortie 209991b625aea5a8fbd7971b17154a0e01366027babHans Petter Jansson if (node->key_hash == hash_value) 210991b625aea5a8fbd7971b17154a0e01366027babHans Petter Jansson { 211991b625aea5a8fbd7971b17154a0e01366027babHans Petter Jansson if (hash_table->key_equal_func) 212991b625aea5a8fbd7971b17154a0e01366027babHans Petter Jansson { 213991b625aea5a8fbd7971b17154a0e01366027babHans Petter Jansson if (hash_table->key_equal_func (node->key, key)) 214991b625aea5a8fbd7971b17154a0e01366027babHans Petter Jansson break; 215991b625aea5a8fbd7971b17154a0e01366027babHans Petter Jansson } 216991b625aea5a8fbd7971b17154a0e01366027babHans Petter Jansson else if (node->key == key) 217991b625aea5a8fbd7971b17154a0e01366027babHans Petter Jansson { 218991b625aea5a8fbd7971b17154a0e01366027babHans Petter Jansson break; 219991b625aea5a8fbd7971b17154a0e01366027babHans Petter Jansson } 220ac44f9cb5aad7a678d057875774ce9c4ca64754eRyan Lortie } 221991b625aea5a8fbd7971b17154a0e01366027babHans Petter Jansson 222991b625aea5a8fbd7971b17154a0e01366027babHans Petter Jansson step++; 223991b625aea5a8fbd7971b17154a0e01366027babHans Petter Jansson node_index += step; 224991b625aea5a8fbd7971b17154a0e01366027babHans Petter Jansson node_index &= hash_table->mask; 225991b625aea5a8fbd7971b17154a0e01366027babHans Petter Jansson node = &hash_table->nodes [node_index]; 226ac44f9cb5aad7a678d057875774ce9c4ca64754eRyan Lortie } 227991b625aea5a8fbd7971b17154a0e01366027babHans Petter Jansson 228991b625aea5a8fbd7971b17154a0e01366027babHans Petter Jansson return node_index; 229991b625aea5a8fbd7971b17154a0e01366027babHans Petter Jansson} 230991b625aea5a8fbd7971b17154a0e01366027babHans Petter Jansson 231991b625aea5a8fbd7971b17154a0e01366027babHans Petter Jansson/* 232991b625aea5a8fbd7971b17154a0e01366027babHans Petter Jansson * g_hash_table_lookup_node_for_insertion: 233991b625aea5a8fbd7971b17154a0e01366027babHans Petter Jansson * @hash_table: our #GHashTable 234991b625aea5a8fbd7971b17154a0e01366027babHans Petter Jansson * @key: the key to lookup against 235991b625aea5a8fbd7971b17154a0e01366027babHans Petter Jansson * @hash_return: key hash return location 236991b625aea5a8fbd7971b17154a0e01366027babHans Petter Jansson * Return value: index of the described #GHashNode 237991b625aea5a8fbd7971b17154a0e01366027babHans Petter Jansson * 238991b625aea5a8fbd7971b17154a0e01366027babHans Petter Jansson * Performs a lookup in the hash table, preserving extra information 239991b625aea5a8fbd7971b17154a0e01366027babHans Petter Jansson * usually needed for insertion. 240991b625aea5a8fbd7971b17154a0e01366027babHans Petter Jansson * 241991b625aea5a8fbd7971b17154a0e01366027babHans Petter Jansson * This function first computes the hash value of the key using the 242991b625aea5a8fbd7971b17154a0e01366027babHans Petter Jansson * user's hash function. 243991b625aea5a8fbd7971b17154a0e01366027babHans Petter Jansson * 244991b625aea5a8fbd7971b17154a0e01366027babHans Petter Jansson * If an entry in the table matching @key is found then this function 245991b625aea5a8fbd7971b17154a0e01366027babHans Petter Jansson * returns the index of that entry in the table, and if not, the 246991b625aea5a8fbd7971b17154a0e01366027babHans Petter Jansson * index of an unused node (empty or tombstone) where the key can be 247991b625aea5a8fbd7971b17154a0e01366027babHans Petter Jansson * inserted. 248991b625aea5a8fbd7971b17154a0e01366027babHans Petter Jansson * 249991b625aea5a8fbd7971b17154a0e01366027babHans Petter Jansson * The computed hash value is returned in the variable pointed to 250991b625aea5a8fbd7971b17154a0e01366027babHans Petter Jansson * by @hash_return. This is to save insertions from having to compute 251991b625aea5a8fbd7971b17154a0e01366027babHans Petter Jansson * the hash record again for the new record. 252991b625aea5a8fbd7971b17154a0e01366027babHans Petter Jansson */ 253991b625aea5a8fbd7971b17154a0e01366027babHans Petter Janssonstatic inline guint 254991b625aea5a8fbd7971b17154a0e01366027babHans Petter Janssong_hash_table_lookup_node_for_insertion (GHashTable *hash_table, 255991b625aea5a8fbd7971b17154a0e01366027babHans Petter Jansson gconstpointer key, 256991b625aea5a8fbd7971b17154a0e01366027babHans Petter Jansson guint *hash_return) 257991b625aea5a8fbd7971b17154a0e01366027babHans Petter Jansson{ 258991b625aea5a8fbd7971b17154a0e01366027babHans Petter Jansson GHashNode *node; 259991b625aea5a8fbd7971b17154a0e01366027babHans Petter Jansson guint node_index; 260991b625aea5a8fbd7971b17154a0e01366027babHans Petter Jansson guint hash_value; 261991b625aea5a8fbd7971b17154a0e01366027babHans Petter Jansson guint first_tombstone; 262991b625aea5a8fbd7971b17154a0e01366027babHans Petter Jansson gboolean have_tombstone = FALSE; 263991b625aea5a8fbd7971b17154a0e01366027babHans Petter Jansson guint step = 0; 264991b625aea5a8fbd7971b17154a0e01366027babHans Petter Jansson 265991b625aea5a8fbd7971b17154a0e01366027babHans Petter Jansson /* Empty buckets have hash_value set to 0, and for tombstones, it's 1. 266991b625aea5a8fbd7971b17154a0e01366027babHans Petter Jansson * We need to make sure our hash value is not one of these. */ 267991b625aea5a8fbd7971b17154a0e01366027babHans Petter Jansson 268991b625aea5a8fbd7971b17154a0e01366027babHans Petter Jansson hash_value = (* hash_table->hash_func) (key); 269991b625aea5a8fbd7971b17154a0e01366027babHans Petter Jansson if (G_UNLIKELY (hash_value <= 1)) 270991b625aea5a8fbd7971b17154a0e01366027babHans Petter Jansson hash_value = 2; 271991b625aea5a8fbd7971b17154a0e01366027babHans Petter Jansson 272991b625aea5a8fbd7971b17154a0e01366027babHans Petter Jansson *hash_return = hash_value; 273991b625aea5a8fbd7971b17154a0e01366027babHans Petter Jansson 274991b625aea5a8fbd7971b17154a0e01366027babHans Petter Jansson node_index = hash_value % hash_table->mod; 275991b625aea5a8fbd7971b17154a0e01366027babHans Petter Jansson node = &hash_table->nodes [node_index]; 276991b625aea5a8fbd7971b17154a0e01366027babHans Petter Jansson 277991b625aea5a8fbd7971b17154a0e01366027babHans Petter Jansson while (node->key_hash) 278ac44f9cb5aad7a678d057875774ce9c4ca64754eRyan Lortie { 279991b625aea5a8fbd7971b17154a0e01366027babHans Petter Jansson /* We first check if our full hash values 280991b625aea5a8fbd7971b17154a0e01366027babHans Petter Jansson * are equal so we can avoid calling the full-blown 281991b625aea5a8fbd7971b17154a0e01366027babHans Petter Jansson * key equality function in most cases. 282991b625aea5a8fbd7971b17154a0e01366027babHans Petter Jansson */ 283ac44f9cb5aad7a678d057875774ce9c4ca64754eRyan Lortie 284991b625aea5a8fbd7971b17154a0e01366027babHans Petter Jansson if (node->key_hash == hash_value) 285991b625aea5a8fbd7971b17154a0e01366027babHans Petter Jansson { 286991b625aea5a8fbd7971b17154a0e01366027babHans Petter Jansson if (hash_table->key_equal_func) 287991b625aea5a8fbd7971b17154a0e01366027babHans Petter Jansson { 288991b625aea5a8fbd7971b17154a0e01366027babHans Petter Jansson if (hash_table->key_equal_func (node->key, key)) 289991b625aea5a8fbd7971b17154a0e01366027babHans Petter Jansson return node_index; 290991b625aea5a8fbd7971b17154a0e01366027babHans Petter Jansson } 291991b625aea5a8fbd7971b17154a0e01366027babHans Petter Jansson else if (node->key == key) 292991b625aea5a8fbd7971b17154a0e01366027babHans Petter Jansson { 293991b625aea5a8fbd7971b17154a0e01366027babHans Petter Jansson return node_index; 294991b625aea5a8fbd7971b17154a0e01366027babHans Petter Jansson } 295991b625aea5a8fbd7971b17154a0e01366027babHans Petter Jansson } 296991b625aea5a8fbd7971b17154a0e01366027babHans Petter Jansson else if (node->key_hash == 1 && !have_tombstone) 297991b625aea5a8fbd7971b17154a0e01366027babHans Petter Jansson { 298991b625aea5a8fbd7971b17154a0e01366027babHans Petter Jansson first_tombstone = node_index; 299991b625aea5a8fbd7971b17154a0e01366027babHans Petter Jansson have_tombstone = TRUE; 300ac44f9cb5aad7a678d057875774ce9c4ca64754eRyan Lortie } 301991b625aea5a8fbd7971b17154a0e01366027babHans Petter Jansson 302991b625aea5a8fbd7971b17154a0e01366027babHans Petter Jansson step++; 303991b625aea5a8fbd7971b17154a0e01366027babHans Petter Jansson node_index += step; 304991b625aea5a8fbd7971b17154a0e01366027babHans Petter Jansson node_index &= hash_table->mask; 305991b625aea5a8fbd7971b17154a0e01366027babHans Petter Jansson node = &hash_table->nodes [node_index]; 306ac44f9cb5aad7a678d057875774ce9c4ca64754eRyan Lortie } 307ac44f9cb5aad7a678d057875774ce9c4ca64754eRyan Lortie 308991b625aea5a8fbd7971b17154a0e01366027babHans Petter Jansson if (have_tombstone) 309991b625aea5a8fbd7971b17154a0e01366027babHans Petter Jansson return first_tombstone; 310991b625aea5a8fbd7971b17154a0e01366027babHans Petter Jansson 311991b625aea5a8fbd7971b17154a0e01366027babHans Petter Jansson return node_index; 312ac44f9cb5aad7a678d057875774ce9c4ca64754eRyan Lortie} 313ac44f9cb5aad7a678d057875774ce9c4ca64754eRyan Lortie 3144c78fb8faa88e94d6d348770e05467223832206eRyan Lortie/* 3150b89fa790abd7fcdd8a2b06c60a5327343526dd8Ryan Lortie * g_hash_table_remove_node: 3160b89fa790abd7fcdd8a2b06c60a5327343526dd8Ryan Lortie * @hash_table: our #GHashTable 317991b625aea5a8fbd7971b17154a0e01366027babHans Petter Jansson * @node: pointer to node to remove 3180b89fa790abd7fcdd8a2b06c60a5327343526dd8Ryan Lortie * @notify: %TRUE if the destroy notify handlers are to be called 3190b89fa790abd7fcdd8a2b06c60a5327343526dd8Ryan Lortie * 320991b625aea5a8fbd7971b17154a0e01366027babHans Petter Jansson * Removes a node from the hash table and updates the node count. 321991b625aea5a8fbd7971b17154a0e01366027babHans Petter Jansson * The node is replaced by a tombstone. No table resize is performed. 3220b89fa790abd7fcdd8a2b06c60a5327343526dd8Ryan Lortie * 3230b89fa790abd7fcdd8a2b06c60a5327343526dd8Ryan Lortie * If @notify is %TRUE then the destroy notify functions are called 3240b89fa790abd7fcdd8a2b06c60a5327343526dd8Ryan Lortie * for the key and value of the hash node. 3254c78fb8faa88e94d6d348770e05467223832206eRyan Lortie */ 326ac44f9cb5aad7a678d057875774ce9c4ca64754eRyan Lortiestatic void 327ac44f9cb5aad7a678d057875774ce9c4ca64754eRyan Lortieg_hash_table_remove_node (GHashTable *hash_table, 328991b625aea5a8fbd7971b17154a0e01366027babHans Petter Jansson GHashNode *node, 329ac44f9cb5aad7a678d057875774ce9c4ca64754eRyan Lortie gboolean notify) 330ac44f9cb5aad7a678d057875774ce9c4ca64754eRyan Lortie{ 331ac44f9cb5aad7a678d057875774ce9c4ca64754eRyan Lortie if (notify && hash_table->key_destroy_func) 332ac44f9cb5aad7a678d057875774ce9c4ca64754eRyan Lortie hash_table->key_destroy_func (node->key); 333ac44f9cb5aad7a678d057875774ce9c4ca64754eRyan Lortie 334ac44f9cb5aad7a678d057875774ce9c4ca64754eRyan Lortie if (notify && hash_table->value_destroy_func) 335ac44f9cb5aad7a678d057875774ce9c4ca64754eRyan Lortie hash_table->value_destroy_func (node->value); 336ac44f9cb5aad7a678d057875774ce9c4ca64754eRyan Lortie 337991b625aea5a8fbd7971b17154a0e01366027babHans Petter Jansson /* Erect tombstone */ 338991b625aea5a8fbd7971b17154a0e01366027babHans Petter Jansson node->key_hash = 1; 339991b625aea5a8fbd7971b17154a0e01366027babHans Petter Jansson 340991b625aea5a8fbd7971b17154a0e01366027babHans Petter Jansson /* Be GC friendly */ 341991b625aea5a8fbd7971b17154a0e01366027babHans Petter Jansson node->key = NULL; 342991b625aea5a8fbd7971b17154a0e01366027babHans Petter Jansson node->value = NULL; 343ac44f9cb5aad7a678d057875774ce9c4ca64754eRyan Lortie 344ac44f9cb5aad7a678d057875774ce9c4ca64754eRyan Lortie hash_table->nnodes--; 345ac44f9cb5aad7a678d057875774ce9c4ca64754eRyan Lortie} 346ac44f9cb5aad7a678d057875774ce9c4ca64754eRyan Lortie 3474c78fb8faa88e94d6d348770e05467223832206eRyan Lortie/* 3480b89fa790abd7fcdd8a2b06c60a5327343526dd8Ryan Lortie * g_hash_table_remove_all_nodes: 3490b89fa790abd7fcdd8a2b06c60a5327343526dd8Ryan Lortie * @hash_table: our #GHashTable 3500b89fa790abd7fcdd8a2b06c60a5327343526dd8Ryan Lortie * @notify: %TRUE if the destroy notify handlers are to be called 3510b89fa790abd7fcdd8a2b06c60a5327343526dd8Ryan Lortie * 3520b89fa790abd7fcdd8a2b06c60a5327343526dd8Ryan Lortie * Removes all nodes from the table. Since this may be a precursor to 3530b89fa790abd7fcdd8a2b06c60a5327343526dd8Ryan Lortie * freeing the table entirely, no resize is performed. 3540b89fa790abd7fcdd8a2b06c60a5327343526dd8Ryan Lortie * 3550b89fa790abd7fcdd8a2b06c60a5327343526dd8Ryan Lortie * If @notify is %TRUE then the destroy notify functions are called 3560b89fa790abd7fcdd8a2b06c60a5327343526dd8Ryan Lortie * for the key and value of the hash node. 3574c78fb8faa88e94d6d348770e05467223832206eRyan Lortie */ 358ac44f9cb5aad7a678d057875774ce9c4ca64754eRyan Lortiestatic void 359ac44f9cb5aad7a678d057875774ce9c4ca64754eRyan Lortieg_hash_table_remove_all_nodes (GHashTable *hash_table, 360ac44f9cb5aad7a678d057875774ce9c4ca64754eRyan Lortie gboolean notify) 361ac44f9cb5aad7a678d057875774ce9c4ca64754eRyan Lortie{ 362ac44f9cb5aad7a678d057875774ce9c4ca64754eRyan Lortie int i; 363ac44f9cb5aad7a678d057875774ce9c4ca64754eRyan Lortie 364ac44f9cb5aad7a678d057875774ce9c4ca64754eRyan Lortie for (i = 0; i < hash_table->size; i++) 365991b625aea5a8fbd7971b17154a0e01366027babHans Petter Jansson { 366991b625aea5a8fbd7971b17154a0e01366027babHans Petter Jansson GHashNode *node = &hash_table->nodes [i]; 367991b625aea5a8fbd7971b17154a0e01366027babHans Petter Jansson 368991b625aea5a8fbd7971b17154a0e01366027babHans Petter Jansson if (node->key_hash > 1) 369991b625aea5a8fbd7971b17154a0e01366027babHans Petter Jansson { 370991b625aea5a8fbd7971b17154a0e01366027babHans Petter Jansson if (notify && hash_table->key_destroy_func) 371991b625aea5a8fbd7971b17154a0e01366027babHans Petter Jansson hash_table->key_destroy_func (node->key); 372991b625aea5a8fbd7971b17154a0e01366027babHans Petter Jansson 373991b625aea5a8fbd7971b17154a0e01366027babHans Petter Jansson if (notify && hash_table->value_destroy_func) 374991b625aea5a8fbd7971b17154a0e01366027babHans Petter Jansson hash_table->value_destroy_func (node->value); 375991b625aea5a8fbd7971b17154a0e01366027babHans Petter Jansson } 376991b625aea5a8fbd7971b17154a0e01366027babHans Petter Jansson } 377991b625aea5a8fbd7971b17154a0e01366027babHans Petter Jansson 378991b625aea5a8fbd7971b17154a0e01366027babHans Petter Jansson /* We need to set node->key_hash = 0 for all nodes - might as well be GC 379991b625aea5a8fbd7971b17154a0e01366027babHans Petter Jansson * friendly and clear everything */ 380991b625aea5a8fbd7971b17154a0e01366027babHans Petter Jansson memset (hash_table->nodes, 0, hash_table->size * sizeof (GHashNode)); 381ac44f9cb5aad7a678d057875774ce9c4ca64754eRyan Lortie 382ac44f9cb5aad7a678d057875774ce9c4ca64754eRyan Lortie hash_table->nnodes = 0; 383991b625aea5a8fbd7971b17154a0e01366027babHans Petter Jansson hash_table->noccupied = 0; 384ac44f9cb5aad7a678d057875774ce9c4ca64754eRyan Lortie} 385ac44f9cb5aad7a678d057875774ce9c4ca64754eRyan Lortie 3864c78fb8faa88e94d6d348770e05467223832206eRyan Lortie/* 3870b89fa790abd7fcdd8a2b06c60a5327343526dd8Ryan Lortie * g_hash_table_resize: 3880b89fa790abd7fcdd8a2b06c60a5327343526dd8Ryan Lortie * @hash_table: our #GHashTable 3890b89fa790abd7fcdd8a2b06c60a5327343526dd8Ryan Lortie * 3900b89fa790abd7fcdd8a2b06c60a5327343526dd8Ryan Lortie * Resizes the hash table to the optimal size based on the number of 3910b89fa790abd7fcdd8a2b06c60a5327343526dd8Ryan Lortie * nodes currently held. If you call this function then a resize will 3920b89fa790abd7fcdd8a2b06c60a5327343526dd8Ryan Lortie * occur, even if one does not need to occur. Use 3930b89fa790abd7fcdd8a2b06c60a5327343526dd8Ryan Lortie * g_hash_table_maybe_resize() instead. 394991b625aea5a8fbd7971b17154a0e01366027babHans Petter Jansson * 395991b625aea5a8fbd7971b17154a0e01366027babHans Petter Jansson * This function may "resize" the hash table to its current size, with 396991b625aea5a8fbd7971b17154a0e01366027babHans Petter Jansson * the side effect of cleaning up tombstones and otherwise optimizing 397991b625aea5a8fbd7971b17154a0e01366027babHans Petter Jansson * the probe sequences. 3984c78fb8faa88e94d6d348770e05467223832206eRyan Lortie */ 399ac44f9cb5aad7a678d057875774ce9c4ca64754eRyan Lortiestatic void 400ac44f9cb5aad7a678d057875774ce9c4ca64754eRyan Lortieg_hash_table_resize (GHashTable *hash_table) 401ac44f9cb5aad7a678d057875774ce9c4ca64754eRyan Lortie{ 402991b625aea5a8fbd7971b17154a0e01366027babHans Petter Jansson GHashNode *new_nodes; 403991b625aea5a8fbd7971b17154a0e01366027babHans Petter Jansson gint old_size; 404ac44f9cb5aad7a678d057875774ce9c4ca64754eRyan Lortie gint i; 405ac44f9cb5aad7a678d057875774ce9c4ca64754eRyan Lortie 406991b625aea5a8fbd7971b17154a0e01366027babHans Petter Jansson old_size = hash_table->size; 407991b625aea5a8fbd7971b17154a0e01366027babHans Petter Jansson g_hash_table_set_shift_from_size (hash_table, hash_table->nnodes * 2); 408ac44f9cb5aad7a678d057875774ce9c4ca64754eRyan Lortie 409991b625aea5a8fbd7971b17154a0e01366027babHans Petter Jansson new_nodes = g_new0 (GHashNode, hash_table->size); 410ac44f9cb5aad7a678d057875774ce9c4ca64754eRyan Lortie 411991b625aea5a8fbd7971b17154a0e01366027babHans Petter Jansson for (i = 0; i < old_size; i++) 412991b625aea5a8fbd7971b17154a0e01366027babHans Petter Jansson { 413991b625aea5a8fbd7971b17154a0e01366027babHans Petter Jansson GHashNode *node = &hash_table->nodes [i]; 414991b625aea5a8fbd7971b17154a0e01366027babHans Petter Jansson GHashNode *new_node; 415991b625aea5a8fbd7971b17154a0e01366027babHans Petter Jansson guint hash_val; 416991b625aea5a8fbd7971b17154a0e01366027babHans Petter Jansson guint step = 0; 417991b625aea5a8fbd7971b17154a0e01366027babHans Petter Jansson 418991b625aea5a8fbd7971b17154a0e01366027babHans Petter Jansson if (node->key_hash <= 1) 419991b625aea5a8fbd7971b17154a0e01366027babHans Petter Jansson continue; 420ac44f9cb5aad7a678d057875774ce9c4ca64754eRyan Lortie 421991b625aea5a8fbd7971b17154a0e01366027babHans Petter Jansson hash_val = node->key_hash % hash_table->mod; 422991b625aea5a8fbd7971b17154a0e01366027babHans Petter Jansson new_node = &new_nodes [hash_val]; 423ac44f9cb5aad7a678d057875774ce9c4ca64754eRyan Lortie 424991b625aea5a8fbd7971b17154a0e01366027babHans Petter Jansson while (new_node->key_hash) 425991b625aea5a8fbd7971b17154a0e01366027babHans Petter Jansson { 426991b625aea5a8fbd7971b17154a0e01366027babHans Petter Jansson step++; 427991b625aea5a8fbd7971b17154a0e01366027babHans Petter Jansson hash_val += step; 428991b625aea5a8fbd7971b17154a0e01366027babHans Petter Jansson hash_val &= hash_table->mask; 429991b625aea5a8fbd7971b17154a0e01366027babHans Petter Jansson new_node = &new_nodes [hash_val]; 430991b625aea5a8fbd7971b17154a0e01366027babHans Petter Jansson } 431991b625aea5a8fbd7971b17154a0e01366027babHans Petter Jansson 432991b625aea5a8fbd7971b17154a0e01366027babHans Petter Jansson *new_node = *node; 433991b625aea5a8fbd7971b17154a0e01366027babHans Petter Jansson } 434ac44f9cb5aad7a678d057875774ce9c4ca64754eRyan Lortie 435ac44f9cb5aad7a678d057875774ce9c4ca64754eRyan Lortie g_free (hash_table->nodes); 436ac44f9cb5aad7a678d057875774ce9c4ca64754eRyan Lortie hash_table->nodes = new_nodes; 437991b625aea5a8fbd7971b17154a0e01366027babHans Petter Jansson hash_table->noccupied = hash_table->nnodes; 438ac44f9cb5aad7a678d057875774ce9c4ca64754eRyan Lortie} 4392e0320d57e417f7d1c838d729a99545db2228e9Owen Taylor 4404c78fb8faa88e94d6d348770e05467223832206eRyan Lortie/* 4410b89fa790abd7fcdd8a2b06c60a5327343526dd8Ryan Lortie * g_hash_table_maybe_resize: 4420b89fa790abd7fcdd8a2b06c60a5327343526dd8Ryan Lortie * @hash_table: our #GHashTable 4430b89fa790abd7fcdd8a2b06c60a5327343526dd8Ryan Lortie * 4440b89fa790abd7fcdd8a2b06c60a5327343526dd8Ryan Lortie * Resizes the hash table, if needed. 4450b89fa790abd7fcdd8a2b06c60a5327343526dd8Ryan Lortie * 4460b89fa790abd7fcdd8a2b06c60a5327343526dd8Ryan Lortie * Essentially, calls g_hash_table_resize() if the table has strayed 4470b89fa790abd7fcdd8a2b06c60a5327343526dd8Ryan Lortie * too far from its ideal size for its number of nodes. 4484c78fb8faa88e94d6d348770e05467223832206eRyan Lortie */ 44900c2db4e4b992a4fa667d49289c55b9d5f3fcf04Ryan Lortiestatic inline void 45000c2db4e4b992a4fa667d49289c55b9d5f3fcf04Ryan Lortieg_hash_table_maybe_resize (GHashTable *hash_table) 45100c2db4e4b992a4fa667d49289c55b9d5f3fcf04Ryan Lortie{ 452991b625aea5a8fbd7971b17154a0e01366027babHans Petter Jansson gint noccupied = hash_table->noccupied; 45300c2db4e4b992a4fa667d49289c55b9d5f3fcf04Ryan Lortie gint size = hash_table->size; 45400c2db4e4b992a4fa667d49289c55b9d5f3fcf04Ryan Lortie 455991b625aea5a8fbd7971b17154a0e01366027babHans Petter Jansson if ((size > hash_table->nnodes * 4 && size > 1 << HASH_TABLE_MIN_SHIFT) || 456991b625aea5a8fbd7971b17154a0e01366027babHans Petter Jansson (size <= noccupied + (noccupied / 16))) 45700c2db4e4b992a4fa667d49289c55b9d5f3fcf04Ryan Lortie g_hash_table_resize (hash_table); 45800c2db4e4b992a4fa667d49289c55b9d5f3fcf04Ryan Lortie} 4592e0320d57e417f7d1c838d729a99545db2228e9Owen Taylor 460a2b269bae3315a2ea772b741fb62f683c1db5770Sven Neumann/** 461a2b269bae3315a2ea772b741fb62f683c1db5770Sven Neumann * g_hash_table_new: 462a2b269bae3315a2ea772b741fb62f683c1db5770Sven Neumann * @hash_func: a function to create a hash value from a key. 463a2b269bae3315a2ea772b741fb62f683c1db5770Sven Neumann * Hash values are used to determine where keys are stored within the 4648eed88b24e86f16021d94d9b16f7a2bc895d9239Ryan Lortie * #GHashTable data structure. The g_direct_hash(), g_int_hash() and 4658eed88b24e86f16021d94d9b16f7a2bc895d9239Ryan Lortie * g_str_hash() functions are provided for some common types of keys. 466a52e2986cd4a2147cfc8d41ae23d98907caaf3a0Matthias Clasen * If hash_func is %NULL, g_direct_hash() is used. 467a2b269bae3315a2ea772b741fb62f683c1db5770Sven Neumann * @key_equal_func: a function to check two keys for equality. This is 468a2b269bae3315a2ea772b741fb62f683c1db5770Sven Neumann * used when looking up keys in the #GHashTable. The g_direct_equal(), 469a2b269bae3315a2ea772b741fb62f683c1db5770Sven Neumann * g_int_equal() and g_str_equal() functions are provided for the most 470a52e2986cd4a2147cfc8d41ae23d98907caaf3a0Matthias Clasen * common types of keys. If @key_equal_func is %NULL, keys are compared 471a2b269bae3315a2ea772b741fb62f683c1db5770Sven Neumann * directly in a similar fashion to g_direct_equal(), but without the 472a2b269bae3315a2ea772b741fb62f683c1db5770Sven Neumann * overhead of a function call. 473a2b269bae3315a2ea772b741fb62f683c1db5770Sven Neumann * 4743e847a090cfd8495add631d43388c461b1a85716Tim Janik * Creates a new #GHashTable with a reference count of 1. 4758eed88b24e86f16021d94d9b16f7a2bc895d9239Ryan Lortie * 476a2b269bae3315a2ea772b741fb62f683c1db5770Sven Neumann * Return value: a new #GHashTable. 477a2b269bae3315a2ea772b741fb62f683c1db5770Sven Neumann **/ 4782e0320d57e417f7d1c838d729a99545db2228e9Owen TaylorGHashTable* 4792e0320d57e417f7d1c838d729a99545db2228e9Owen Taylorg_hash_table_new (GHashFunc hash_func, 4808eed88b24e86f16021d94d9b16f7a2bc895d9239Ryan Lortie GEqualFunc key_equal_func) 4812e0320d57e417f7d1c838d729a99545db2228e9Owen Taylor{ 482a2b269bae3315a2ea772b741fb62f683c1db5770Sven Neumann return g_hash_table_new_full (hash_func, key_equal_func, NULL, NULL); 483a2b269bae3315a2ea772b741fb62f683c1db5770Sven Neumann} 484a2b269bae3315a2ea772b741fb62f683c1db5770Sven Neumann 485a2b269bae3315a2ea772b741fb62f683c1db5770Sven Neumann 486a2b269bae3315a2ea772b741fb62f683c1db5770Sven Neumann/** 487a2b269bae3315a2ea772b741fb62f683c1db5770Sven Neumann * g_hash_table_new_full: 488a2b269bae3315a2ea772b741fb62f683c1db5770Sven Neumann * @hash_func: a function to create a hash value from a key. 489a2b269bae3315a2ea772b741fb62f683c1db5770Sven Neumann * @key_equal_func: a function to check two keys for equality. 4908eed88b24e86f16021d94d9b16f7a2bc895d9239Ryan Lortie * @key_destroy_func: a function to free the memory allocated for the key 4918eed88b24e86f16021d94d9b16f7a2bc895d9239Ryan Lortie * used when removing the entry from the #GHashTable or %NULL if you 492d18b364dd774087555f036fec2c6ec9fe838368fSven Neumann * don't want to supply such a function. 4938eed88b24e86f16021d94d9b16f7a2bc895d9239Ryan Lortie * @value_destroy_func: a function to free the memory allocated for the 4948eed88b24e86f16021d94d9b16f7a2bc895d9239Ryan Lortie * value used when removing the entry from the #GHashTable or %NULL if 495a2b269bae3315a2ea772b741fb62f683c1db5770Sven Neumann * you don't want to supply such a function. 4968eed88b24e86f16021d94d9b16f7a2bc895d9239Ryan Lortie * 4973e847a090cfd8495add631d43388c461b1a85716Tim Janik * Creates a new #GHashTable like g_hash_table_new() with a reference count 4983e847a090cfd8495add631d43388c461b1a85716Tim Janik * of 1 and allows to specify functions to free the memory allocated for the 4993e847a090cfd8495add631d43388c461b1a85716Tim Janik * key and value that get called when removing the entry from the #GHashTable. 5008eed88b24e86f16021d94d9b16f7a2bc895d9239Ryan Lortie * 501a2b269bae3315a2ea772b741fb62f683c1db5770Sven Neumann * Return value: a new #GHashTable. 502a2b269bae3315a2ea772b741fb62f683c1db5770Sven Neumann **/ 503a2b269bae3315a2ea772b741fb62f683c1db5770Sven NeumannGHashTable* 504a2b269bae3315a2ea772b741fb62f683c1db5770Sven Neumanng_hash_table_new_full (GHashFunc hash_func, 5058eed88b24e86f16021d94d9b16f7a2bc895d9239Ryan Lortie GEqualFunc key_equal_func, 5068eed88b24e86f16021d94d9b16f7a2bc895d9239Ryan Lortie GDestroyNotify key_destroy_func, 5078eed88b24e86f16021d94d9b16f7a2bc895d9239Ryan Lortie GDestroyNotify value_destroy_func) 508a2b269bae3315a2ea772b741fb62f683c1db5770Sven Neumann{ 5097519c2338ae484135b44bbb7eb49719aea8c4ca3Lauri Alanko GHashTable *hash_table; 5108eed88b24e86f16021d94d9b16f7a2bc895d9239Ryan Lortie 5110cba1b531d5d28890fa4f48359d4e7adacf2a603Tim Janik hash_table = g_slice_new (GHashTable); 512991b625aea5a8fbd7971b17154a0e01366027babHans Petter Jansson g_hash_table_set_shift (hash_table, HASH_TABLE_MIN_SHIFT); 513a2b269bae3315a2ea772b741fb62f683c1db5770Sven Neumann hash_table->nnodes = 0; 514991b625aea5a8fbd7971b17154a0e01366027babHans Petter Jansson hash_table->noccupied = 0; 515a2b269bae3315a2ea772b741fb62f683c1db5770Sven Neumann hash_table->hash_func = hash_func ? hash_func : g_direct_hash; 516a2b269bae3315a2ea772b741fb62f683c1db5770Sven Neumann hash_table->key_equal_func = key_equal_func; 5173e847a090cfd8495add631d43388c461b1a85716Tim Janik hash_table->ref_count = 1; 518d741d3e7a344622e5a534c34e9e2c0488b2fea4dMatthias Clasen#ifndef G_DISABLE_ASSERT 519d741d3e7a344622e5a534c34e9e2c0488b2fea4dMatthias Clasen hash_table->version = 0; 520d741d3e7a344622e5a534c34e9e2c0488b2fea4dMatthias Clasen#endif 521a2b269bae3315a2ea772b741fb62f683c1db5770Sven Neumann hash_table->key_destroy_func = key_destroy_func; 522a2b269bae3315a2ea772b741fb62f683c1db5770Sven Neumann hash_table->value_destroy_func = value_destroy_func; 523991b625aea5a8fbd7971b17154a0e01366027babHans Petter Jansson hash_table->nodes = g_new0 (GHashNode, hash_table->size); 5248eed88b24e86f16021d94d9b16f7a2bc895d9239Ryan Lortie 5257519c2338ae484135b44bbb7eb49719aea8c4ca3Lauri Alanko return hash_table; 5262e0320d57e417f7d1c838d729a99545db2228e9Owen Taylor} 5272e0320d57e417f7d1c838d729a99545db2228e9Owen Taylor 528d741d3e7a344622e5a534c34e9e2c0488b2fea4dMatthias Clasen/** 529d741d3e7a344622e5a534c34e9e2c0488b2fea4dMatthias Clasen * g_hash_table_iter_init: 530d741d3e7a344622e5a534c34e9e2c0488b2fea4dMatthias Clasen * @iter: an uninitialized #GHashTableIter. 531d741d3e7a344622e5a534c34e9e2c0488b2fea4dMatthias Clasen * @hash_table: a #GHashTable. 532d741d3e7a344622e5a534c34e9e2c0488b2fea4dMatthias Clasen * 533d741d3e7a344622e5a534c34e9e2c0488b2fea4dMatthias Clasen * Initializes a key/value pair iterator and associates it with 534d741d3e7a344622e5a534c34e9e2c0488b2fea4dMatthias Clasen * @hash_table. Modifying the hash table after calling this function 535d741d3e7a344622e5a534c34e9e2c0488b2fea4dMatthias Clasen * invalidates the returned iterator. 5361f7e7f84f42232c04b11a11c9738b465db7d6ad2Matthias Clasen * |[ 537d741d3e7a344622e5a534c34e9e2c0488b2fea4dMatthias Clasen * GHashTableIter iter; 538d741d3e7a344622e5a534c34e9e2c0488b2fea4dMatthias Clasen * gpointer key, value; 539d741d3e7a344622e5a534c34e9e2c0488b2fea4dMatthias Clasen * 5401f7e7f84f42232c04b11a11c9738b465db7d6ad2Matthias Clasen * g_hash_table_iter_init (&iter, hash_table); 5411f7e7f84f42232c04b11a11c9738b465db7d6ad2Matthias Clasen * while (g_hash_table_iter_next (&iter, &key, &value)) 5421f7e7f84f42232c04b11a11c9738b465db7d6ad2Matthias Clasen * { 5431f7e7f84f42232c04b11a11c9738b465db7d6ad2Matthias Clasen * /* do something with key and value */ 5441f7e7f84f42232c04b11a11c9738b465db7d6ad2Matthias Clasen * } 5451f7e7f84f42232c04b11a11c9738b465db7d6ad2Matthias Clasen * ]| 546d741d3e7a344622e5a534c34e9e2c0488b2fea4dMatthias Clasen * 547d741d3e7a344622e5a534c34e9e2c0488b2fea4dMatthias Clasen * Since: 2.16 548d741d3e7a344622e5a534c34e9e2c0488b2fea4dMatthias Clasen **/ 549d741d3e7a344622e5a534c34e9e2c0488b2fea4dMatthias Clasenvoid 550d741d3e7a344622e5a534c34e9e2c0488b2fea4dMatthias Claseng_hash_table_iter_init (GHashTableIter *iter, 551d741d3e7a344622e5a534c34e9e2c0488b2fea4dMatthias Clasen GHashTable *hash_table) 552d741d3e7a344622e5a534c34e9e2c0488b2fea4dMatthias Clasen{ 553d741d3e7a344622e5a534c34e9e2c0488b2fea4dMatthias Clasen RealIter *ri = (RealIter *) iter; 554d741d3e7a344622e5a534c34e9e2c0488b2fea4dMatthias Clasen 555d741d3e7a344622e5a534c34e9e2c0488b2fea4dMatthias Clasen g_return_if_fail (iter != NULL); 556d741d3e7a344622e5a534c34e9e2c0488b2fea4dMatthias Clasen g_return_if_fail (hash_table != NULL); 557d741d3e7a344622e5a534c34e9e2c0488b2fea4dMatthias Clasen 558d741d3e7a344622e5a534c34e9e2c0488b2fea4dMatthias Clasen ri->hash_table = hash_table; 559d741d3e7a344622e5a534c34e9e2c0488b2fea4dMatthias Clasen ri->position = -1; 560d741d3e7a344622e5a534c34e9e2c0488b2fea4dMatthias Clasen#ifndef G_DISABLE_ASSERT 561d741d3e7a344622e5a534c34e9e2c0488b2fea4dMatthias Clasen ri->version = hash_table->version; 562d741d3e7a344622e5a534c34e9e2c0488b2fea4dMatthias Clasen#endif 563d741d3e7a344622e5a534c34e9e2c0488b2fea4dMatthias Clasen} 564d741d3e7a344622e5a534c34e9e2c0488b2fea4dMatthias Clasen 565d741d3e7a344622e5a534c34e9e2c0488b2fea4dMatthias Clasen/** 566d741d3e7a344622e5a534c34e9e2c0488b2fea4dMatthias Clasen * g_hash_table_iter_next: 567d741d3e7a344622e5a534c34e9e2c0488b2fea4dMatthias Clasen * @iter: an initialized #GHashTableIter. 568d741d3e7a344622e5a534c34e9e2c0488b2fea4dMatthias Clasen * @key: a location to store the key, or %NULL. 569d741d3e7a344622e5a534c34e9e2c0488b2fea4dMatthias Clasen * @value: a location to store the value, or %NULL. 570d741d3e7a344622e5a534c34e9e2c0488b2fea4dMatthias Clasen * 571d741d3e7a344622e5a534c34e9e2c0488b2fea4dMatthias Clasen * Advances @iter and retrieves the key and/or value that are now 572d741d3e7a344622e5a534c34e9e2c0488b2fea4dMatthias Clasen * pointed to as a result of this advancement. If %FALSE is returned, 573d741d3e7a344622e5a534c34e9e2c0488b2fea4dMatthias Clasen * @key and @value are not set, and the iterator becomes invalid. 574d741d3e7a344622e5a534c34e9e2c0488b2fea4dMatthias Clasen * 575d741d3e7a344622e5a534c34e9e2c0488b2fea4dMatthias Clasen * Return value: %FALSE if the end of the #GHashTable has been reached. 576d741d3e7a344622e5a534c34e9e2c0488b2fea4dMatthias Clasen * 577d741d3e7a344622e5a534c34e9e2c0488b2fea4dMatthias Clasen * Since: 2.16 578d741d3e7a344622e5a534c34e9e2c0488b2fea4dMatthias Clasen **/ 579d741d3e7a344622e5a534c34e9e2c0488b2fea4dMatthias Clasengboolean 580d741d3e7a344622e5a534c34e9e2c0488b2fea4dMatthias Claseng_hash_table_iter_next (GHashTableIter *iter, 581d741d3e7a344622e5a534c34e9e2c0488b2fea4dMatthias Clasen gpointer *key, 582d741d3e7a344622e5a534c34e9e2c0488b2fea4dMatthias Clasen gpointer *value) 583d741d3e7a344622e5a534c34e9e2c0488b2fea4dMatthias Clasen{ 584d741d3e7a344622e5a534c34e9e2c0488b2fea4dMatthias Clasen RealIter *ri = (RealIter *) iter; 585991b625aea5a8fbd7971b17154a0e01366027babHans Petter Jansson GHashNode *node; 586991b625aea5a8fbd7971b17154a0e01366027babHans Petter Jansson gint position; 587d741d3e7a344622e5a534c34e9e2c0488b2fea4dMatthias Clasen 588d741d3e7a344622e5a534c34e9e2c0488b2fea4dMatthias Clasen g_return_val_if_fail (iter != NULL, FALSE); 5897250e1dafd477d189d711f221af70c508a0ad232Matthias Clasen#ifndef G_DISABLE_ASSERT 590d741d3e7a344622e5a534c34e9e2c0488b2fea4dMatthias Clasen g_return_val_if_fail (ri->version == ri->hash_table->version, FALSE); 5917250e1dafd477d189d711f221af70c508a0ad232Matthias Clasen#endif 592991b625aea5a8fbd7971b17154a0e01366027babHans Petter Jansson g_return_val_if_fail (ri->position < ri->hash_table->size, FALSE); 593d741d3e7a344622e5a534c34e9e2c0488b2fea4dMatthias Clasen 594991b625aea5a8fbd7971b17154a0e01366027babHans Petter Jansson position = ri->position; 595d741d3e7a344622e5a534c34e9e2c0488b2fea4dMatthias Clasen 596991b625aea5a8fbd7971b17154a0e01366027babHans Petter Jansson do 597d741d3e7a344622e5a534c34e9e2c0488b2fea4dMatthias Clasen { 598991b625aea5a8fbd7971b17154a0e01366027babHans Petter Jansson position++; 599991b625aea5a8fbd7971b17154a0e01366027babHans Petter Jansson if (position >= ri->hash_table->size) 600991b625aea5a8fbd7971b17154a0e01366027babHans Petter Jansson { 601991b625aea5a8fbd7971b17154a0e01366027babHans Petter Jansson ri->position = position; 602991b625aea5a8fbd7971b17154a0e01366027babHans Petter Jansson return FALSE; 603991b625aea5a8fbd7971b17154a0e01366027babHans Petter Jansson } 604991b625aea5a8fbd7971b17154a0e01366027babHans Petter Jansson 605991b625aea5a8fbd7971b17154a0e01366027babHans Petter Jansson node = &ri->hash_table->nodes [position]; 606d741d3e7a344622e5a534c34e9e2c0488b2fea4dMatthias Clasen } 607991b625aea5a8fbd7971b17154a0e01366027babHans Petter Jansson while (node->key_hash <= 1); 608d741d3e7a344622e5a534c34e9e2c0488b2fea4dMatthias Clasen 609d741d3e7a344622e5a534c34e9e2c0488b2fea4dMatthias Clasen if (key != NULL) 610991b625aea5a8fbd7971b17154a0e01366027babHans Petter Jansson *key = node->key; 611d741d3e7a344622e5a534c34e9e2c0488b2fea4dMatthias Clasen if (value != NULL) 612991b625aea5a8fbd7971b17154a0e01366027babHans Petter Jansson *value = node->value; 613d741d3e7a344622e5a534c34e9e2c0488b2fea4dMatthias Clasen 614991b625aea5a8fbd7971b17154a0e01366027babHans Petter Jansson ri->position = position; 615d741d3e7a344622e5a534c34e9e2c0488b2fea4dMatthias Clasen return TRUE; 616d741d3e7a344622e5a534c34e9e2c0488b2fea4dMatthias Clasen} 617d741d3e7a344622e5a534c34e9e2c0488b2fea4dMatthias Clasen 618d741d3e7a344622e5a534c34e9e2c0488b2fea4dMatthias Clasen/** 619d741d3e7a344622e5a534c34e9e2c0488b2fea4dMatthias Clasen * g_hash_table_iter_get_hash_table: 620d741d3e7a344622e5a534c34e9e2c0488b2fea4dMatthias Clasen * @iter: an initialized #GHashTableIter. 621d741d3e7a344622e5a534c34e9e2c0488b2fea4dMatthias Clasen * 622d741d3e7a344622e5a534c34e9e2c0488b2fea4dMatthias Clasen * Returns the #GHashTable associated with @iter. 623d741d3e7a344622e5a534c34e9e2c0488b2fea4dMatthias Clasen * 624d741d3e7a344622e5a534c34e9e2c0488b2fea4dMatthias Clasen * Return value: the #GHashTable associated with @iter. 625d741d3e7a344622e5a534c34e9e2c0488b2fea4dMatthias Clasen * 626d741d3e7a344622e5a534c34e9e2c0488b2fea4dMatthias Clasen * Since: 2.16 627d741d3e7a344622e5a534c34e9e2c0488b2fea4dMatthias Clasen **/ 628d741d3e7a344622e5a534c34e9e2c0488b2fea4dMatthias ClasenGHashTable * 629d741d3e7a344622e5a534c34e9e2c0488b2fea4dMatthias Claseng_hash_table_iter_get_hash_table (GHashTableIter *iter) 630d741d3e7a344622e5a534c34e9e2c0488b2fea4dMatthias Clasen{ 631d741d3e7a344622e5a534c34e9e2c0488b2fea4dMatthias Clasen g_return_val_if_fail (iter != NULL, NULL); 632d741d3e7a344622e5a534c34e9e2c0488b2fea4dMatthias Clasen 633d741d3e7a344622e5a534c34e9e2c0488b2fea4dMatthias Clasen return ((RealIter *) iter)->hash_table; 634d741d3e7a344622e5a534c34e9e2c0488b2fea4dMatthias Clasen} 635d741d3e7a344622e5a534c34e9e2c0488b2fea4dMatthias Clasen 636d741d3e7a344622e5a534c34e9e2c0488b2fea4dMatthias Clasenstatic void 637d741d3e7a344622e5a534c34e9e2c0488b2fea4dMatthias Claseniter_remove_or_steal (RealIter *ri, gboolean notify) 638d741d3e7a344622e5a534c34e9e2c0488b2fea4dMatthias Clasen{ 639d741d3e7a344622e5a534c34e9e2c0488b2fea4dMatthias Clasen g_return_if_fail (ri != NULL); 6407250e1dafd477d189d711f221af70c508a0ad232Matthias Clasen#ifndef G_DISABLE_ASSERT 641d741d3e7a344622e5a534c34e9e2c0488b2fea4dMatthias Clasen g_return_if_fail (ri->version == ri->hash_table->version); 6427250e1dafd477d189d711f221af70c508a0ad232Matthias Clasen#endif 643991b625aea5a8fbd7971b17154a0e01366027babHans Petter Jansson g_return_if_fail (ri->position >= 0); 644991b625aea5a8fbd7971b17154a0e01366027babHans Petter Jansson g_return_if_fail (ri->position < ri->hash_table->size); 645d741d3e7a344622e5a534c34e9e2c0488b2fea4dMatthias Clasen 646991b625aea5a8fbd7971b17154a0e01366027babHans Petter Jansson g_hash_table_remove_node (ri->hash_table, &ri->hash_table->nodes [ri->position], notify); 647cc1ad36f9904ef2c4f0615810564607d7ddcc842Matthias Clasen 648cc1ad36f9904ef2c4f0615810564607d7ddcc842Matthias Clasen#ifndef G_DISABLE_ASSERT 649cc1ad36f9904ef2c4f0615810564607d7ddcc842Matthias Clasen ri->version++; 650cc1ad36f9904ef2c4f0615810564607d7ddcc842Matthias Clasen ri->hash_table->version++; 651cc1ad36f9904ef2c4f0615810564607d7ddcc842Matthias Clasen#endif 652d741d3e7a344622e5a534c34e9e2c0488b2fea4dMatthias Clasen} 653d741d3e7a344622e5a534c34e9e2c0488b2fea4dMatthias Clasen 654d741d3e7a344622e5a534c34e9e2c0488b2fea4dMatthias Clasen/** 655d741d3e7a344622e5a534c34e9e2c0488b2fea4dMatthias Clasen * g_hash_table_iter_remove(): 656d741d3e7a344622e5a534c34e9e2c0488b2fea4dMatthias Clasen * @iter: an initialized #GHashTableIter. 657d741d3e7a344622e5a534c34e9e2c0488b2fea4dMatthias Clasen * 658d741d3e7a344622e5a534c34e9e2c0488b2fea4dMatthias Clasen * Removes the key/value pair currently pointed to by the iterator 659d741d3e7a344622e5a534c34e9e2c0488b2fea4dMatthias Clasen * from its associated #GHashTable. Can only be called after 660d741d3e7a344622e5a534c34e9e2c0488b2fea4dMatthias Clasen * g_hash_table_iter_next() returned %TRUE, and cannot be called more 661d741d3e7a344622e5a534c34e9e2c0488b2fea4dMatthias Clasen * than once for the same key/value pair. 662d741d3e7a344622e5a534c34e9e2c0488b2fea4dMatthias Clasen * 663d741d3e7a344622e5a534c34e9e2c0488b2fea4dMatthias Clasen * If the #GHashTable was created using g_hash_table_new_full(), the 664d741d3e7a344622e5a534c34e9e2c0488b2fea4dMatthias Clasen * key and value are freed using the supplied destroy functions, otherwise 665d741d3e7a344622e5a534c34e9e2c0488b2fea4dMatthias Clasen * you have to make sure that any dynamically allocated values are freed 666d741d3e7a344622e5a534c34e9e2c0488b2fea4dMatthias Clasen * yourself. 667d741d3e7a344622e5a534c34e9e2c0488b2fea4dMatthias Clasen * 668d741d3e7a344622e5a534c34e9e2c0488b2fea4dMatthias Clasen * Since: 2.16 669d741d3e7a344622e5a534c34e9e2c0488b2fea4dMatthias Clasen **/ 670d741d3e7a344622e5a534c34e9e2c0488b2fea4dMatthias Clasenvoid 671d741d3e7a344622e5a534c34e9e2c0488b2fea4dMatthias Claseng_hash_table_iter_remove (GHashTableIter *iter) 672d741d3e7a344622e5a534c34e9e2c0488b2fea4dMatthias Clasen{ 673d741d3e7a344622e5a534c34e9e2c0488b2fea4dMatthias Clasen iter_remove_or_steal ((RealIter *) iter, TRUE); 674d741d3e7a344622e5a534c34e9e2c0488b2fea4dMatthias Clasen} 675d741d3e7a344622e5a534c34e9e2c0488b2fea4dMatthias Clasen 676d741d3e7a344622e5a534c34e9e2c0488b2fea4dMatthias Clasen/** 677d741d3e7a344622e5a534c34e9e2c0488b2fea4dMatthias Clasen * g_hash_table_iter_steal(): 678d741d3e7a344622e5a534c34e9e2c0488b2fea4dMatthias Clasen * @iter: an initialized #GHashTableIter. 679d741d3e7a344622e5a534c34e9e2c0488b2fea4dMatthias Clasen * 680d741d3e7a344622e5a534c34e9e2c0488b2fea4dMatthias Clasen * Removes the key/value pair currently pointed to by the iterator 681d741d3e7a344622e5a534c34e9e2c0488b2fea4dMatthias Clasen * from its associated #GHashTable, without calling the key and value 682d741d3e7a344622e5a534c34e9e2c0488b2fea4dMatthias Clasen * destroy functions. Can only be called after 683d741d3e7a344622e5a534c34e9e2c0488b2fea4dMatthias Clasen * g_hash_table_iter_next() returned %TRUE, and cannot be called more 684d741d3e7a344622e5a534c34e9e2c0488b2fea4dMatthias Clasen * than once for the same key/value pair. 685d741d3e7a344622e5a534c34e9e2c0488b2fea4dMatthias Clasen * 686d741d3e7a344622e5a534c34e9e2c0488b2fea4dMatthias Clasen * Since: 2.16 687d741d3e7a344622e5a534c34e9e2c0488b2fea4dMatthias Clasen **/ 688d741d3e7a344622e5a534c34e9e2c0488b2fea4dMatthias Clasenvoid 689d741d3e7a344622e5a534c34e9e2c0488b2fea4dMatthias Claseng_hash_table_iter_steal (GHashTableIter *iter) 690d741d3e7a344622e5a534c34e9e2c0488b2fea4dMatthias Clasen{ 691d741d3e7a344622e5a534c34e9e2c0488b2fea4dMatthias Clasen iter_remove_or_steal ((RealIter *) iter, FALSE); 692d741d3e7a344622e5a534c34e9e2c0488b2fea4dMatthias Clasen} 693d741d3e7a344622e5a534c34e9e2c0488b2fea4dMatthias Clasen 6943e847a090cfd8495add631d43388c461b1a85716Tim Janik 6953e847a090cfd8495add631d43388c461b1a85716Tim Janik/** 6963e847a090cfd8495add631d43388c461b1a85716Tim Janik * g_hash_table_ref: 6973e847a090cfd8495add631d43388c461b1a85716Tim Janik * @hash_table: a valid #GHashTable. 6988eed88b24e86f16021d94d9b16f7a2bc895d9239Ryan Lortie * 6993e847a090cfd8495add631d43388c461b1a85716Tim Janik * Atomically increments the reference count of @hash_table by one. 7003e847a090cfd8495add631d43388c461b1a85716Tim Janik * This function is MT-safe and may be called from any thread. 7018eed88b24e86f16021d94d9b16f7a2bc895d9239Ryan Lortie * 7023e847a090cfd8495add631d43388c461b1a85716Tim Janik * Return value: the passed in #GHashTable. 7038eed88b24e86f16021d94d9b16f7a2bc895d9239Ryan Lortie * 704fe749cbd3b058512e36d79203cac3c00c7f40571Matthias Clasen * Since: 2.10 7053e847a090cfd8495add631d43388c461b1a85716Tim Janik **/ 7063e847a090cfd8495add631d43388c461b1a85716Tim JanikGHashTable* 7073e847a090cfd8495add631d43388c461b1a85716Tim Janikg_hash_table_ref (GHashTable *hash_table) 7083e847a090cfd8495add631d43388c461b1a85716Tim Janik{ 7093e847a090cfd8495add631d43388c461b1a85716Tim Janik g_return_val_if_fail (hash_table != NULL, NULL); 7103e847a090cfd8495add631d43388c461b1a85716Tim Janik g_return_val_if_fail (hash_table->ref_count > 0, hash_table); 7113e847a090cfd8495add631d43388c461b1a85716Tim Janik 7123e847a090cfd8495add631d43388c461b1a85716Tim Janik g_atomic_int_add (&hash_table->ref_count, 1); 7133e847a090cfd8495add631d43388c461b1a85716Tim Janik return hash_table; 7143e847a090cfd8495add631d43388c461b1a85716Tim Janik} 7153e847a090cfd8495add631d43388c461b1a85716Tim Janik 7163e847a090cfd8495add631d43388c461b1a85716Tim Janik/** 7173e847a090cfd8495add631d43388c461b1a85716Tim Janik * g_hash_table_unref: 7183e847a090cfd8495add631d43388c461b1a85716Tim Janik * @hash_table: a valid #GHashTable. 7198eed88b24e86f16021d94d9b16f7a2bc895d9239Ryan Lortie * 7203e847a090cfd8495add631d43388c461b1a85716Tim Janik * Atomically decrements the reference count of @hash_table by one. 7213e847a090cfd8495add631d43388c461b1a85716Tim Janik * If the reference count drops to 0, all keys and values will be 7223e847a090cfd8495add631d43388c461b1a85716Tim Janik * destroyed, and all memory allocated by the hash table is released. 7233e847a090cfd8495add631d43388c461b1a85716Tim Janik * This function is MT-safe and may be called from any thread. 7248eed88b24e86f16021d94d9b16f7a2bc895d9239Ryan Lortie * 725fe749cbd3b058512e36d79203cac3c00c7f40571Matthias Clasen * Since: 2.10 7263e847a090cfd8495add631d43388c461b1a85716Tim Janik **/ 7273e847a090cfd8495add631d43388c461b1a85716Tim Janikvoid 7283e847a090cfd8495add631d43388c461b1a85716Tim Janikg_hash_table_unref (GHashTable *hash_table) 7293e847a090cfd8495add631d43388c461b1a85716Tim Janik{ 7303e847a090cfd8495add631d43388c461b1a85716Tim Janik g_return_if_fail (hash_table != NULL); 7313e847a090cfd8495add631d43388c461b1a85716Tim Janik g_return_if_fail (hash_table->ref_count > 0); 7323e847a090cfd8495add631d43388c461b1a85716Tim Janik 7333e847a090cfd8495add631d43388c461b1a85716Tim Janik if (g_atomic_int_exchange_and_add (&hash_table->ref_count, -1) - 1 == 0) 7343e847a090cfd8495add631d43388c461b1a85716Tim Janik { 735bb10169eb41a736c1d109682c43f47cb18521d8bMathias Hasselmann g_hash_table_remove_all_nodes (hash_table, TRUE); 7363e847a090cfd8495add631d43388c461b1a85716Tim Janik g_free (hash_table->nodes); 7373e847a090cfd8495add631d43388c461b1a85716Tim Janik g_slice_free (GHashTable, hash_table); 7383e847a090cfd8495add631d43388c461b1a85716Tim Janik } 7393e847a090cfd8495add631d43388c461b1a85716Tim Janik} 7403e847a090cfd8495add631d43388c461b1a85716Tim Janik 741a2b269bae3315a2ea772b741fb62f683c1db5770Sven Neumann/** 742a2b269bae3315a2ea772b741fb62f683c1db5770Sven Neumann * g_hash_table_destroy: 743a2b269bae3315a2ea772b741fb62f683c1db5770Sven Neumann * @hash_table: a #GHashTable. 7448eed88b24e86f16021d94d9b16f7a2bc895d9239Ryan Lortie * 74524dec3cd490fa4dc057a0186c6b870160022268eMorten Welinder * Destroys all keys and values in the #GHashTable and decrements its 7463e847a090cfd8495add631d43388c461b1a85716Tim Janik * reference count by 1. If keys and/or values are dynamically allocated, 7473e847a090cfd8495add631d43388c461b1a85716Tim Janik * you should either free them first or create the #GHashTable with destroy 7483e847a090cfd8495add631d43388c461b1a85716Tim Janik * notifiers using g_hash_table_new_full(). In the latter case the destroy 7493e847a090cfd8495add631d43388c461b1a85716Tim Janik * functions you supplied will be called on all keys and values during the 7503e847a090cfd8495add631d43388c461b1a85716Tim Janik * destruction phase. 751a2b269bae3315a2ea772b741fb62f683c1db5770Sven Neumann **/ 7522e0320d57e417f7d1c838d729a99545db2228e9Owen Taylorvoid 7532e0320d57e417f7d1c838d729a99545db2228e9Owen Taylorg_hash_table_destroy (GHashTable *hash_table) 7542e0320d57e417f7d1c838d729a99545db2228e9Owen Taylor{ 7552d68cbbb7d37d3f265bf1087e6ddedcc58bc62beTim Janik g_return_if_fail (hash_table != NULL); 7563e847a090cfd8495add631d43388c461b1a85716Tim Janik g_return_if_fail (hash_table->ref_count > 0); 7578eed88b24e86f16021d94d9b16f7a2bc895d9239Ryan Lortie 758a5b4b8bfb18838454d99bdee60294da07e5ef0d2Matthias Clasen g_hash_table_remove_all (hash_table); 7593e847a090cfd8495add631d43388c461b1a85716Tim Janik g_hash_table_unref (hash_table); 7602e0320d57e417f7d1c838d729a99545db2228e9Owen Taylor} 7612e0320d57e417f7d1c838d729a99545db2228e9Owen Taylor 762a2b269bae3315a2ea772b741fb62f683c1db5770Sven Neumann/** 763a2b269bae3315a2ea772b741fb62f683c1db5770Sven Neumann * g_hash_table_lookup: 764a2b269bae3315a2ea772b741fb62f683c1db5770Sven Neumann * @hash_table: a #GHashTable. 765a2b269bae3315a2ea772b741fb62f683c1db5770Sven Neumann * @key: the key to look up. 7668eed88b24e86f16021d94d9b16f7a2bc895d9239Ryan Lortie * 767fd92ac8f5280ccb936a534a14f5c9cbdb24302e5Matthias Clasen * Looks up a key in a #GHashTable. Note that this function cannot 768fd92ac8f5280ccb936a534a14f5c9cbdb24302e5Matthias Clasen * distinguish between a key that is not present and one which is present 769fd92ac8f5280ccb936a534a14f5c9cbdb24302e5Matthias Clasen * and has the value %NULL. If you need this distinction, use 770fd92ac8f5280ccb936a534a14f5c9cbdb24302e5Matthias Clasen * g_hash_table_lookup_extended(). 7718eed88b24e86f16021d94d9b16f7a2bc895d9239Ryan Lortie * 772a52e2986cd4a2147cfc8d41ae23d98907caaf3a0Matthias Clasen * Return value: the associated value, or %NULL if the key is not found. 773a2b269bae3315a2ea772b741fb62f683c1db5770Sven Neumann **/ 7742d68cbbb7d37d3f265bf1087e6ddedcc58bc62beTim Janikgpointer 7758eed88b24e86f16021d94d9b16f7a2bc895d9239Ryan Lortieg_hash_table_lookup (GHashTable *hash_table, 7768eed88b24e86f16021d94d9b16f7a2bc895d9239Ryan Lortie gconstpointer key) 7772d68cbbb7d37d3f265bf1087e6ddedcc58bc62beTim Janik{ 7782d68cbbb7d37d3f265bf1087e6ddedcc58bc62beTim Janik GHashNode *node; 779991b625aea5a8fbd7971b17154a0e01366027babHans Petter Jansson guint node_index; 7808eed88b24e86f16021d94d9b16f7a2bc895d9239Ryan Lortie 7812d68cbbb7d37d3f265bf1087e6ddedcc58bc62beTim Janik g_return_val_if_fail (hash_table != NULL, NULL); 7828eed88b24e86f16021d94d9b16f7a2bc895d9239Ryan Lortie 783991b625aea5a8fbd7971b17154a0e01366027babHans Petter Jansson node_index = g_hash_table_lookup_node (hash_table, key); 784991b625aea5a8fbd7971b17154a0e01366027babHans Petter Jansson node = &hash_table->nodes [node_index]; 7858eed88b24e86f16021d94d9b16f7a2bc895d9239Ryan Lortie 786991b625aea5a8fbd7971b17154a0e01366027babHans Petter Jansson return node->key_hash ? node->value : NULL; 7872d68cbbb7d37d3f265bf1087e6ddedcc58bc62beTim Janik} 7887401460a60504dad7b77219d0ba3d93112e12444Manish Singh 789a2b269bae3315a2ea772b741fb62f683c1db5770Sven Neumann/** 790a2b269bae3315a2ea772b741fb62f683c1db5770Sven Neumann * g_hash_table_lookup_extended: 79100769cf7f1648cf375f9ef9137cd9a76bf64969eChristian Dywan * @hash_table: a #GHashTable 79200769cf7f1648cf375f9ef9137cd9a76bf64969eChristian Dywan * @lookup_key: the key to look up 79300769cf7f1648cf375f9ef9137cd9a76bf64969eChristian Dywan * @orig_key: return location for the original key, or %NULL 79400769cf7f1648cf375f9ef9137cd9a76bf64969eChristian Dywan * @value: return location for the value associated with the key, or %NULL 7958eed88b24e86f16021d94d9b16f7a2bc895d9239Ryan Lortie * 796a2b269bae3315a2ea772b741fb62f683c1db5770Sven Neumann * Looks up a key in the #GHashTable, returning the original key and the 7978eed88b24e86f16021d94d9b16f7a2bc895d9239Ryan Lortie * associated value and a #gboolean which is %TRUE if the key was found. This 7988eed88b24e86f16021d94d9b16f7a2bc895d9239Ryan Lortie * is useful if you need to free the memory allocated for the original key, 799a2b269bae3315a2ea772b741fb62f683c1db5770Sven Neumann * for example before calling g_hash_table_remove(). 8008eed88b24e86f16021d94d9b16f7a2bc895d9239Ryan Lortie * 80100769cf7f1648cf375f9ef9137cd9a76bf64969eChristian Dywan * You can actually pass %NULL for @lookup_key to test 80200769cf7f1648cf375f9ef9137cd9a76bf64969eChristian Dywan * whether the %NULL key exists. 80300769cf7f1648cf375f9ef9137cd9a76bf64969eChristian Dywan * 8043fa33317b7e9866793ce1ea32d069e8c9270caa2Matthias Clasen * Return value: %TRUE if the key was found in the #GHashTable. 805a2b269bae3315a2ea772b741fb62f683c1db5770Sven Neumann **/ 806a2b269bae3315a2ea772b741fb62f683c1db5770Sven Neumanngboolean 807a2b269bae3315a2ea772b741fb62f683c1db5770Sven Neumanng_hash_table_lookup_extended (GHashTable *hash_table, 8088eed88b24e86f16021d94d9b16f7a2bc895d9239Ryan Lortie gconstpointer lookup_key, 8098eed88b24e86f16021d94d9b16f7a2bc895d9239Ryan Lortie gpointer *orig_key, 8108eed88b24e86f16021d94d9b16f7a2bc895d9239Ryan Lortie gpointer *value) 811a2b269bae3315a2ea772b741fb62f683c1db5770Sven Neumann{ 812a2b269bae3315a2ea772b741fb62f683c1db5770Sven Neumann GHashNode *node; 813991b625aea5a8fbd7971b17154a0e01366027babHans Petter Jansson guint node_index; 8148eed88b24e86f16021d94d9b16f7a2bc895d9239Ryan Lortie 815a2b269bae3315a2ea772b741fb62f683c1db5770Sven Neumann g_return_val_if_fail (hash_table != NULL, FALSE); 8168eed88b24e86f16021d94d9b16f7a2bc895d9239Ryan Lortie 817991b625aea5a8fbd7971b17154a0e01366027babHans Petter Jansson node_index = g_hash_table_lookup_node (hash_table, lookup_key); 818991b625aea5a8fbd7971b17154a0e01366027babHans Petter Jansson node = &hash_table->nodes [node_index]; 8198eed88b24e86f16021d94d9b16f7a2bc895d9239Ryan Lortie 820991b625aea5a8fbd7971b17154a0e01366027babHans Petter Jansson if (!node->key_hash) 821a2b269bae3315a2ea772b741fb62f683c1db5770Sven Neumann return FALSE; 822d72c02686bd69ae9c4c6a97d878cae56eb1bcba7Ryan Lortie 823d72c02686bd69ae9c4c6a97d878cae56eb1bcba7Ryan Lortie if (orig_key) 824d72c02686bd69ae9c4c6a97d878cae56eb1bcba7Ryan Lortie *orig_key = node->key; 825d72c02686bd69ae9c4c6a97d878cae56eb1bcba7Ryan Lortie 826d72c02686bd69ae9c4c6a97d878cae56eb1bcba7Ryan Lortie if (value) 827d72c02686bd69ae9c4c6a97d878cae56eb1bcba7Ryan Lortie *value = node->value; 828d72c02686bd69ae9c4c6a97d878cae56eb1bcba7Ryan Lortie 829d72c02686bd69ae9c4c6a97d878cae56eb1bcba7Ryan Lortie return TRUE; 830a2b269bae3315a2ea772b741fb62f683c1db5770Sven Neumann} 831a2b269bae3315a2ea772b741fb62f683c1db5770Sven Neumann 8324c78fb8faa88e94d6d348770e05467223832206eRyan Lortie/* 8330b89fa790abd7fcdd8a2b06c60a5327343526dd8Ryan Lortie * g_hash_table_insert_internal: 8340b89fa790abd7fcdd8a2b06c60a5327343526dd8Ryan Lortie * @hash_table: our #GHashTable 8350b89fa790abd7fcdd8a2b06c60a5327343526dd8Ryan Lortie * @key: the key to insert 8360b89fa790abd7fcdd8a2b06c60a5327343526dd8Ryan Lortie * @value: the value to insert 8370b89fa790abd7fcdd8a2b06c60a5327343526dd8Ryan Lortie * @keep_new_key: if %TRUE and this key already exists in the table 8380b89fa790abd7fcdd8a2b06c60a5327343526dd8Ryan Lortie * then call the destroy notify function on the old key. If %FALSE 8390b89fa790abd7fcdd8a2b06c60a5327343526dd8Ryan Lortie * then call the destroy notify function on the new key. 8400b89fa790abd7fcdd8a2b06c60a5327343526dd8Ryan Lortie * 8410b89fa790abd7fcdd8a2b06c60a5327343526dd8Ryan Lortie * Implements the common logic for the g_hash_table_insert() and 8420b89fa790abd7fcdd8a2b06c60a5327343526dd8Ryan Lortie * g_hash_table_replace() functions. 8430b89fa790abd7fcdd8a2b06c60a5327343526dd8Ryan Lortie * 8440b89fa790abd7fcdd8a2b06c60a5327343526dd8Ryan Lortie * Do a lookup of @key. If it is found, replace it with the new 8450b89fa790abd7fcdd8a2b06c60a5327343526dd8Ryan Lortie * @value (and perhaps the new @key). If it is not found, create a 8460b89fa790abd7fcdd8a2b06c60a5327343526dd8Ryan Lortie * new node. 8474c78fb8faa88e94d6d348770e05467223832206eRyan Lortie */ 8480adbacbff90cdab1b96e3409b6d510a00916b586Ryan Lortiestatic void 8490adbacbff90cdab1b96e3409b6d510a00916b586Ryan Lortieg_hash_table_insert_internal (GHashTable *hash_table, 8500adbacbff90cdab1b96e3409b6d510a00916b586Ryan Lortie gpointer key, 8510adbacbff90cdab1b96e3409b6d510a00916b586Ryan Lortie gpointer value, 8520adbacbff90cdab1b96e3409b6d510a00916b586Ryan Lortie gboolean keep_new_key) 8532d68cbbb7d37d3f265bf1087e6ddedcc58bc62beTim Janik{ 854991b625aea5a8fbd7971b17154a0e01366027babHans Petter Jansson GHashNode *node; 855991b625aea5a8fbd7971b17154a0e01366027babHans Petter Jansson guint node_index; 856e6b78c9af1d6416f93311b98e1e6d802e2fe0617Ryan Lortie guint key_hash; 857991b625aea5a8fbd7971b17154a0e01366027babHans Petter Jansson guint old_hash; 8588eed88b24e86f16021d94d9b16f7a2bc895d9239Ryan Lortie 8592d68cbbb7d37d3f265bf1087e6ddedcc58bc62beTim Janik g_return_if_fail (hash_table != NULL); 8603e847a090cfd8495add631d43388c461b1a85716Tim Janik g_return_if_fail (hash_table->ref_count > 0); 8618eed88b24e86f16021d94d9b16f7a2bc895d9239Ryan Lortie 862991b625aea5a8fbd7971b17154a0e01366027babHans Petter Jansson node_index = g_hash_table_lookup_node_for_insertion (hash_table, key, &key_hash); 863991b625aea5a8fbd7971b17154a0e01366027babHans Petter Jansson node = &hash_table->nodes [node_index]; 864991b625aea5a8fbd7971b17154a0e01366027babHans Petter Jansson 865991b625aea5a8fbd7971b17154a0e01366027babHans Petter Jansson old_hash = node->key_hash; 8668eed88b24e86f16021d94d9b16f7a2bc895d9239Ryan Lortie 867991b625aea5a8fbd7971b17154a0e01366027babHans Petter Jansson if (old_hash > 1) 8687519c2338ae484135b44bbb7eb49719aea8c4ca3Lauri Alanko { 8695e02b01b210513c19b76731d303a7256d2db273cRyan Lortie if (keep_new_key) 8700adbacbff90cdab1b96e3409b6d510a00916b586Ryan Lortie { 8715e02b01b210513c19b76731d303a7256d2db273cRyan Lortie if (hash_table->key_destroy_func) 872d72c02686bd69ae9c4c6a97d878cae56eb1bcba7Ryan Lortie hash_table->key_destroy_func (node->key); 873d72c02686bd69ae9c4c6a97d878cae56eb1bcba7Ryan Lortie node->key = key; 8745e02b01b210513c19b76731d303a7256d2db273cRyan Lortie } 8755e02b01b210513c19b76731d303a7256d2db273cRyan Lortie else 8765e02b01b210513c19b76731d303a7256d2db273cRyan Lortie { 8775e02b01b210513c19b76731d303a7256d2db273cRyan Lortie if (hash_table->key_destroy_func) 8780adbacbff90cdab1b96e3409b6d510a00916b586Ryan Lortie hash_table->key_destroy_func (key); 8790adbacbff90cdab1b96e3409b6d510a00916b586Ryan Lortie } 8808eed88b24e86f16021d94d9b16f7a2bc895d9239Ryan Lortie 881a2b269bae3315a2ea772b741fb62f683c1db5770Sven Neumann if (hash_table->value_destroy_func) 882d72c02686bd69ae9c4c6a97d878cae56eb1bcba7Ryan Lortie hash_table->value_destroy_func (node->value); 883a2b269bae3315a2ea772b741fb62f683c1db5770Sven Neumann 884d72c02686bd69ae9c4c6a97d878cae56eb1bcba7Ryan Lortie node->value = value; 885a2b269bae3315a2ea772b741fb62f683c1db5770Sven Neumann } 886a2b269bae3315a2ea772b741fb62f683c1db5770Sven Neumann else 887a2b269bae3315a2ea772b741fb62f683c1db5770Sven Neumann { 888d72c02686bd69ae9c4c6a97d878cae56eb1bcba7Ryan Lortie node->key = key; 889d72c02686bd69ae9c4c6a97d878cae56eb1bcba7Ryan Lortie node->value = value; 890d72c02686bd69ae9c4c6a97d878cae56eb1bcba7Ryan Lortie node->key_hash = key_hash; 891d72c02686bd69ae9c4c6a97d878cae56eb1bcba7Ryan Lortie 892a2b269bae3315a2ea772b741fb62f683c1db5770Sven Neumann hash_table->nnodes++; 893991b625aea5a8fbd7971b17154a0e01366027babHans Petter Jansson 894991b625aea5a8fbd7971b17154a0e01366027babHans Petter Jansson if (old_hash == 0) 895991b625aea5a8fbd7971b17154a0e01366027babHans Petter Jansson { 896991b625aea5a8fbd7971b17154a0e01366027babHans Petter Jansson /* We replaced an empty node, and not a tombstone */ 897991b625aea5a8fbd7971b17154a0e01366027babHans Petter Jansson hash_table->noccupied++; 898991b625aea5a8fbd7971b17154a0e01366027babHans Petter Jansson g_hash_table_maybe_resize (hash_table); 899991b625aea5a8fbd7971b17154a0e01366027babHans Petter Jansson } 900d741d3e7a344622e5a534c34e9e2c0488b2fea4dMatthias Clasen 901d741d3e7a344622e5a534c34e9e2c0488b2fea4dMatthias Clasen#ifndef G_DISABLE_ASSERT 902d741d3e7a344622e5a534c34e9e2c0488b2fea4dMatthias Clasen hash_table->version++; 903d741d3e7a344622e5a534c34e9e2c0488b2fea4dMatthias Clasen#endif 904a2b269bae3315a2ea772b741fb62f683c1db5770Sven Neumann } 905a2b269bae3315a2ea772b741fb62f683c1db5770Sven Neumann} 906a2b269bae3315a2ea772b741fb62f683c1db5770Sven Neumann 907a2b269bae3315a2ea772b741fb62f683c1db5770Sven Neumann/** 9080adbacbff90cdab1b96e3409b6d510a00916b586Ryan Lortie * g_hash_table_insert: 9090adbacbff90cdab1b96e3409b6d510a00916b586Ryan Lortie * @hash_table: a #GHashTable. 9100adbacbff90cdab1b96e3409b6d510a00916b586Ryan Lortie * @key: a key to insert. 9110adbacbff90cdab1b96e3409b6d510a00916b586Ryan Lortie * @value: the value to associate with the key. 9128eed88b24e86f16021d94d9b16f7a2bc895d9239Ryan Lortie * 9130adbacbff90cdab1b96e3409b6d510a00916b586Ryan Lortie * Inserts a new key and value into a #GHashTable. 9148eed88b24e86f16021d94d9b16f7a2bc895d9239Ryan Lortie * 9150adbacbff90cdab1b96e3409b6d510a00916b586Ryan Lortie * If the key already exists in the #GHashTable its current value is replaced 9168eed88b24e86f16021d94d9b16f7a2bc895d9239Ryan Lortie * with the new value. If you supplied a @value_destroy_func when creating the 9170adbacbff90cdab1b96e3409b6d510a00916b586Ryan Lortie * #GHashTable, the old value is freed using that function. If you supplied 9188eed88b24e86f16021d94d9b16f7a2bc895d9239Ryan Lortie * a @key_destroy_func when creating the #GHashTable, the passed key is freed 9190adbacbff90cdab1b96e3409b6d510a00916b586Ryan Lortie * using that function. 9200adbacbff90cdab1b96e3409b6d510a00916b586Ryan Lortie **/ 9210adbacbff90cdab1b96e3409b6d510a00916b586Ryan Lortievoid 9220adbacbff90cdab1b96e3409b6d510a00916b586Ryan Lortieg_hash_table_insert (GHashTable *hash_table, 9238eed88b24e86f16021d94d9b16f7a2bc895d9239Ryan Lortie gpointer key, 9248eed88b24e86f16021d94d9b16f7a2bc895d9239Ryan Lortie gpointer value) 9250adbacbff90cdab1b96e3409b6d510a00916b586Ryan Lortie{ 926ed670989f41b014ba72a1180d0207c79a7a6e1ddAlvaro Lopez Ortega g_hash_table_insert_internal (hash_table, key, value, FALSE); 9270adbacbff90cdab1b96e3409b6d510a00916b586Ryan Lortie} 9280adbacbff90cdab1b96e3409b6d510a00916b586Ryan Lortie 9290adbacbff90cdab1b96e3409b6d510a00916b586Ryan Lortie/** 930a2b269bae3315a2ea772b741fb62f683c1db5770Sven Neumann * g_hash_table_replace: 931a2b269bae3315a2ea772b741fb62f683c1db5770Sven Neumann * @hash_table: a #GHashTable. 932a2b269bae3315a2ea772b741fb62f683c1db5770Sven Neumann * @key: a key to insert. 933a2b269bae3315a2ea772b741fb62f683c1db5770Sven Neumann * @value: the value to associate with the key. 9348eed88b24e86f16021d94d9b16f7a2bc895d9239Ryan Lortie * 9358eed88b24e86f16021d94d9b16f7a2bc895d9239Ryan Lortie * Inserts a new key and value into a #GHashTable similar to 9368eed88b24e86f16021d94d9b16f7a2bc895d9239Ryan Lortie * g_hash_table_insert(). The difference is that if the key already exists 9378eed88b24e86f16021d94d9b16f7a2bc895d9239Ryan Lortie * in the #GHashTable, it gets replaced by the new key. If you supplied a 9388eed88b24e86f16021d94d9b16f7a2bc895d9239Ryan Lortie * @value_destroy_func when creating the #GHashTable, the old value is freed 9398eed88b24e86f16021d94d9b16f7a2bc895d9239Ryan Lortie * using that function. If you supplied a @key_destroy_func when creating the 9408eed88b24e86f16021d94d9b16f7a2bc895d9239Ryan Lortie * #GHashTable, the old key is freed using that function. 941a2b269bae3315a2ea772b741fb62f683c1db5770Sven Neumann **/ 942a2b269bae3315a2ea772b741fb62f683c1db5770Sven Neumannvoid 943a2b269bae3315a2ea772b741fb62f683c1db5770Sven Neumanng_hash_table_replace (GHashTable *hash_table, 9448eed88b24e86f16021d94d9b16f7a2bc895d9239Ryan Lortie gpointer key, 9458eed88b24e86f16021d94d9b16f7a2bc895d9239Ryan Lortie gpointer value) 946a2b269bae3315a2ea772b741fb62f683c1db5770Sven Neumann{ 947ed670989f41b014ba72a1180d0207c79a7a6e1ddAlvaro Lopez Ortega g_hash_table_insert_internal (hash_table, key, value, TRUE); 9482e0320d57e417f7d1c838d729a99545db2228e9Owen Taylor} 9492e0320d57e417f7d1c838d729a99545db2228e9Owen Taylor 9504c78fb8faa88e94d6d348770e05467223832206eRyan Lortie/* 9510b89fa790abd7fcdd8a2b06c60a5327343526dd8Ryan Lortie * g_hash_table_remove_internal: 9520b89fa790abd7fcdd8a2b06c60a5327343526dd8Ryan Lortie * @hash_table: our #GHashTable 9530b89fa790abd7fcdd8a2b06c60a5327343526dd8Ryan Lortie * @key: the key to remove 9540b89fa790abd7fcdd8a2b06c60a5327343526dd8Ryan Lortie * @notify: %TRUE if the destroy notify handlers are to be called 9550b89fa790abd7fcdd8a2b06c60a5327343526dd8Ryan Lortie * Return value: %TRUE if a node was found and removed, else %FALSE 9560b89fa790abd7fcdd8a2b06c60a5327343526dd8Ryan Lortie * 9570b89fa790abd7fcdd8a2b06c60a5327343526dd8Ryan Lortie * Implements the common logic for the g_hash_table_remove() and 9580b89fa790abd7fcdd8a2b06c60a5327343526dd8Ryan Lortie * g_hash_table_steal() functions. 9590b89fa790abd7fcdd8a2b06c60a5327343526dd8Ryan Lortie * 9600b89fa790abd7fcdd8a2b06c60a5327343526dd8Ryan Lortie * Do a lookup of @key and remove it if it is found, calling the 9610b89fa790abd7fcdd8a2b06c60a5327343526dd8Ryan Lortie * destroy notify handlers only if @notify is %TRUE. 9624c78fb8faa88e94d6d348770e05467223832206eRyan Lortie */ 963e9010a86f763e6b7cb1fd5520985c929339f5523Ryan Lortiestatic gboolean 964e9010a86f763e6b7cb1fd5520985c929339f5523Ryan Lortieg_hash_table_remove_internal (GHashTable *hash_table, 965e9010a86f763e6b7cb1fd5520985c929339f5523Ryan Lortie gconstpointer key, 966e9010a86f763e6b7cb1fd5520985c929339f5523Ryan Lortie gboolean notify) 967e9010a86f763e6b7cb1fd5520985c929339f5523Ryan Lortie{ 968991b625aea5a8fbd7971b17154a0e01366027babHans Petter Jansson GHashNode *node; 969991b625aea5a8fbd7971b17154a0e01366027babHans Petter Jansson guint node_index; 9708eed88b24e86f16021d94d9b16f7a2bc895d9239Ryan Lortie 971e9010a86f763e6b7cb1fd5520985c929339f5523Ryan Lortie g_return_val_if_fail (hash_table != NULL, FALSE); 9728eed88b24e86f16021d94d9b16f7a2bc895d9239Ryan Lortie 973991b625aea5a8fbd7971b17154a0e01366027babHans Petter Jansson node_index = g_hash_table_lookup_node (hash_table, key); 974991b625aea5a8fbd7971b17154a0e01366027babHans Petter Jansson node = &hash_table->nodes [node_index]; 975991b625aea5a8fbd7971b17154a0e01366027babHans Petter Jansson 976991b625aea5a8fbd7971b17154a0e01366027babHans Petter Jansson /* g_hash_table_lookup_node() never returns a tombstone, so this is safe */ 977991b625aea5a8fbd7971b17154a0e01366027babHans Petter Jansson if (!node->key_hash) 978e9010a86f763e6b7cb1fd5520985c929339f5523Ryan Lortie return FALSE; 979e9010a86f763e6b7cb1fd5520985c929339f5523Ryan Lortie 980991b625aea5a8fbd7971b17154a0e01366027babHans Petter Jansson g_hash_table_remove_node (hash_table, node, notify); 98100c2db4e4b992a4fa667d49289c55b9d5f3fcf04Ryan Lortie g_hash_table_maybe_resize (hash_table); 982e9010a86f763e6b7cb1fd5520985c929339f5523Ryan Lortie 983d741d3e7a344622e5a534c34e9e2c0488b2fea4dMatthias Clasen#ifndef G_DISABLE_ASSERT 984d741d3e7a344622e5a534c34e9e2c0488b2fea4dMatthias Clasen hash_table->version++; 985d741d3e7a344622e5a534c34e9e2c0488b2fea4dMatthias Clasen#endif 986d741d3e7a344622e5a534c34e9e2c0488b2fea4dMatthias Clasen 987e9010a86f763e6b7cb1fd5520985c929339f5523Ryan Lortie return TRUE; 988e9010a86f763e6b7cb1fd5520985c929339f5523Ryan Lortie} 989e9010a86f763e6b7cb1fd5520985c929339f5523Ryan Lortie 990a2b269bae3315a2ea772b741fb62f683c1db5770Sven Neumann/** 991a2b269bae3315a2ea772b741fb62f683c1db5770Sven Neumann * g_hash_table_remove: 992a2b269bae3315a2ea772b741fb62f683c1db5770Sven Neumann * @hash_table: a #GHashTable. 993a2b269bae3315a2ea772b741fb62f683c1db5770Sven Neumann * @key: the key to remove. 9948eed88b24e86f16021d94d9b16f7a2bc895d9239Ryan Lortie * 995a2b269bae3315a2ea772b741fb62f683c1db5770Sven Neumann * Removes a key and its associated value from a #GHashTable. 996a2b269bae3315a2ea772b741fb62f683c1db5770Sven Neumann * 997a2b269bae3315a2ea772b741fb62f683c1db5770Sven Neumann * If the #GHashTable was created using g_hash_table_new_full(), the 998a52e2986cd4a2147cfc8d41ae23d98907caaf3a0Matthias Clasen * key and value are freed using the supplied destroy functions, otherwise 9998eed88b24e86f16021d94d9b16f7a2bc895d9239Ryan Lortie * you have to make sure that any dynamically allocated values are freed 1000a2b269bae3315a2ea772b741fb62f683c1db5770Sven Neumann * yourself. 10018eed88b24e86f16021d94d9b16f7a2bc895d9239Ryan Lortie * 10023fa33317b7e9866793ce1ea32d069e8c9270caa2Matthias Clasen * Return value: %TRUE if the key was found and removed from the #GHashTable. 1003a2b269bae3315a2ea772b741fb62f683c1db5770Sven Neumann **/ 10049a8c33db5cc37bc3c6bd4794a03f4b99a847ff4aTim Janikgboolean 10058eed88b24e86f16021d94d9b16f7a2bc895d9239Ryan Lortieg_hash_table_remove (GHashTable *hash_table, 1006e9010a86f763e6b7cb1fd5520985c929339f5523Ryan Lortie gconstpointer key) 10072e0320d57e417f7d1c838d729a99545db2228e9Owen Taylor{ 1008e9010a86f763e6b7cb1fd5520985c929339f5523Ryan Lortie return g_hash_table_remove_internal (hash_table, key, TRUE); 10092e0320d57e417f7d1c838d729a99545db2228e9Owen Taylor} 10102e0320d57e417f7d1c838d729a99545db2228e9Owen Taylor 1011a2b269bae3315a2ea772b741fb62f683c1db5770Sven Neumann/** 1012ac44f9cb5aad7a678d057875774ce9c4ca64754eRyan Lortie * g_hash_table_steal: 1013ac44f9cb5aad7a678d057875774ce9c4ca64754eRyan Lortie * @hash_table: a #GHashTable. 1014ac44f9cb5aad7a678d057875774ce9c4ca64754eRyan Lortie * @key: the key to remove. 1015ac44f9cb5aad7a678d057875774ce9c4ca64754eRyan Lortie * 1016ac44f9cb5aad7a678d057875774ce9c4ca64754eRyan Lortie * Removes a key and its associated value from a #GHashTable without 1017ac44f9cb5aad7a678d057875774ce9c4ca64754eRyan Lortie * calling the key and value destroy functions. 1018ac44f9cb5aad7a678d057875774ce9c4ca64754eRyan Lortie * 1019ac44f9cb5aad7a678d057875774ce9c4ca64754eRyan Lortie * Return value: %TRUE if the key was found and removed from the #GHashTable. 1020ac44f9cb5aad7a678d057875774ce9c4ca64754eRyan Lortie **/ 1021ac44f9cb5aad7a678d057875774ce9c4ca64754eRyan Lortiegboolean 1022ac44f9cb5aad7a678d057875774ce9c4ca64754eRyan Lortieg_hash_table_steal (GHashTable *hash_table, 1023ac44f9cb5aad7a678d057875774ce9c4ca64754eRyan Lortie gconstpointer key) 1024ac44f9cb5aad7a678d057875774ce9c4ca64754eRyan Lortie{ 1025ac44f9cb5aad7a678d057875774ce9c4ca64754eRyan Lortie return g_hash_table_remove_internal (hash_table, key, FALSE); 1026ac44f9cb5aad7a678d057875774ce9c4ca64754eRyan Lortie} 1027ac44f9cb5aad7a678d057875774ce9c4ca64754eRyan Lortie 1028ac44f9cb5aad7a678d057875774ce9c4ca64754eRyan Lortie/** 1029a5b4b8bfb18838454d99bdee60294da07e5ef0d2Matthias Clasen * g_hash_table_remove_all: 1030a5b4b8bfb18838454d99bdee60294da07e5ef0d2Matthias Clasen * @hash_table: a #GHashTable 1031a5b4b8bfb18838454d99bdee60294da07e5ef0d2Matthias Clasen * 1032a5b4b8bfb18838454d99bdee60294da07e5ef0d2Matthias Clasen * Removes all keys and their associated values from a #GHashTable. 1033a5b4b8bfb18838454d99bdee60294da07e5ef0d2Matthias Clasen * 1034a5b4b8bfb18838454d99bdee60294da07e5ef0d2Matthias Clasen * If the #GHashTable was created using g_hash_table_new_full(), the keys 1035a5b4b8bfb18838454d99bdee60294da07e5ef0d2Matthias Clasen * and values are freed using the supplied destroy functions, otherwise you 1036a5b4b8bfb18838454d99bdee60294da07e5ef0d2Matthias Clasen * have to make sure that any dynamically allocated values are freed 1037a5b4b8bfb18838454d99bdee60294da07e5ef0d2Matthias Clasen * yourself. 1038a5b4b8bfb18838454d99bdee60294da07e5ef0d2Matthias Clasen * 1039a5b4b8bfb18838454d99bdee60294da07e5ef0d2Matthias Clasen * Since: 2.12 1040a5b4b8bfb18838454d99bdee60294da07e5ef0d2Matthias Clasen **/ 1041a5b4b8bfb18838454d99bdee60294da07e5ef0d2Matthias Clasenvoid 1042a5b4b8bfb18838454d99bdee60294da07e5ef0d2Matthias Claseng_hash_table_remove_all (GHashTable *hash_table) 1043a5b4b8bfb18838454d99bdee60294da07e5ef0d2Matthias Clasen{ 1044a5b4b8bfb18838454d99bdee60294da07e5ef0d2Matthias Clasen g_return_if_fail (hash_table != NULL); 1045a5b4b8bfb18838454d99bdee60294da07e5ef0d2Matthias Clasen 1046d741d3e7a344622e5a534c34e9e2c0488b2fea4dMatthias Clasen#ifndef G_DISABLE_ASSERT 1047d741d3e7a344622e5a534c34e9e2c0488b2fea4dMatthias Clasen if (hash_table->nnodes != 0) 1048d741d3e7a344622e5a534c34e9e2c0488b2fea4dMatthias Clasen hash_table->version++; 1049d741d3e7a344622e5a534c34e9e2c0488b2fea4dMatthias Clasen#endif 1050d741d3e7a344622e5a534c34e9e2c0488b2fea4dMatthias Clasen 105172ed8191afd8ff124a45285b420625e1342e35cfRyan Lortie g_hash_table_remove_all_nodes (hash_table, TRUE); 105200c2db4e4b992a4fa667d49289c55b9d5f3fcf04Ryan Lortie g_hash_table_maybe_resize (hash_table); 1053a5b4b8bfb18838454d99bdee60294da07e5ef0d2Matthias Clasen} 1054a5b4b8bfb18838454d99bdee60294da07e5ef0d2Matthias Clasen 1055a5b4b8bfb18838454d99bdee60294da07e5ef0d2Matthias Clasen/** 1056a5b4b8bfb18838454d99bdee60294da07e5ef0d2Matthias Clasen * g_hash_table_steal_all: 1057a5b4b8bfb18838454d99bdee60294da07e5ef0d2Matthias Clasen * @hash_table: a #GHashTable. 1058a5b4b8bfb18838454d99bdee60294da07e5ef0d2Matthias Clasen * 10598eed88b24e86f16021d94d9b16f7a2bc895d9239Ryan Lortie * Removes all keys and their associated values from a #GHashTable 1060a5b4b8bfb18838454d99bdee60294da07e5ef0d2Matthias Clasen * without calling the key and value destroy functions. 1061a5b4b8bfb18838454d99bdee60294da07e5ef0d2Matthias Clasen * 1062a5b4b8bfb18838454d99bdee60294da07e5ef0d2Matthias Clasen * Since: 2.12 1063a5b4b8bfb18838454d99bdee60294da07e5ef0d2Matthias Clasen **/ 1064a5b4b8bfb18838454d99bdee60294da07e5ef0d2Matthias Clasenvoid 1065a5b4b8bfb18838454d99bdee60294da07e5ef0d2Matthias Claseng_hash_table_steal_all (GHashTable *hash_table) 1066a5b4b8bfb18838454d99bdee60294da07e5ef0d2Matthias Clasen{ 1067a5b4b8bfb18838454d99bdee60294da07e5ef0d2Matthias Clasen g_return_if_fail (hash_table != NULL); 1068a5b4b8bfb18838454d99bdee60294da07e5ef0d2Matthias Clasen 1069d741d3e7a344622e5a534c34e9e2c0488b2fea4dMatthias Clasen#ifndef G_DISABLE_ASSERT 1070d741d3e7a344622e5a534c34e9e2c0488b2fea4dMatthias Clasen if (hash_table->nnodes != 0) 1071d741d3e7a344622e5a534c34e9e2c0488b2fea4dMatthias Clasen hash_table->version++; 1072d741d3e7a344622e5a534c34e9e2c0488b2fea4dMatthias Clasen#endif 1073d741d3e7a344622e5a534c34e9e2c0488b2fea4dMatthias Clasen 107472ed8191afd8ff124a45285b420625e1342e35cfRyan Lortie g_hash_table_remove_all_nodes (hash_table, FALSE); 107500c2db4e4b992a4fa667d49289c55b9d5f3fcf04Ryan Lortie g_hash_table_maybe_resize (hash_table); 1076a5b4b8bfb18838454d99bdee60294da07e5ef0d2Matthias Clasen} 1077a5b4b8bfb18838454d99bdee60294da07e5ef0d2Matthias Clasen 10784c78fb8faa88e94d6d348770e05467223832206eRyan Lortie/* 10790b89fa790abd7fcdd8a2b06c60a5327343526dd8Ryan Lortie * g_hash_table_foreach_remove_or_steal: 10800b89fa790abd7fcdd8a2b06c60a5327343526dd8Ryan Lortie * @hash_table: our #GHashTable 10810b89fa790abd7fcdd8a2b06c60a5327343526dd8Ryan Lortie * @func: the user's callback function 10820b89fa790abd7fcdd8a2b06c60a5327343526dd8Ryan Lortie * @user_data: data for @func 10830b89fa790abd7fcdd8a2b06c60a5327343526dd8Ryan Lortie * @notify: %TRUE if the destroy notify handlers are to be called 10840b89fa790abd7fcdd8a2b06c60a5327343526dd8Ryan Lortie * 10850b89fa790abd7fcdd8a2b06c60a5327343526dd8Ryan Lortie * Implements the common logic for g_hash_table_foreach_remove() and 10860b89fa790abd7fcdd8a2b06c60a5327343526dd8Ryan Lortie * g_hash_table_foreach_steal(). 10870b89fa790abd7fcdd8a2b06c60a5327343526dd8Ryan Lortie * 10880b89fa790abd7fcdd8a2b06c60a5327343526dd8Ryan Lortie * Iterates over every node in the table, calling @func with the key 10890b89fa790abd7fcdd8a2b06c60a5327343526dd8Ryan Lortie * and value of the node (and @user_data). If @func returns %TRUE the 10900b89fa790abd7fcdd8a2b06c60a5327343526dd8Ryan Lortie * node is removed from the table. 10910b89fa790abd7fcdd8a2b06c60a5327343526dd8Ryan Lortie * 10920b89fa790abd7fcdd8a2b06c60a5327343526dd8Ryan Lortie * If @notify is true then the destroy notify handlers will be called 10930b89fa790abd7fcdd8a2b06c60a5327343526dd8Ryan Lortie * for each removed node. 10944c78fb8faa88e94d6d348770e05467223832206eRyan Lortie */ 1095ac44f9cb5aad7a678d057875774ce9c4ca64754eRyan Lortiestatic guint 1096ac44f9cb5aad7a678d057875774ce9c4ca64754eRyan Lortieg_hash_table_foreach_remove_or_steal (GHashTable *hash_table, 1097ac44f9cb5aad7a678d057875774ce9c4ca64754eRyan Lortie GHRFunc func, 1098ac44f9cb5aad7a678d057875774ce9c4ca64754eRyan Lortie gpointer user_data, 1099ac44f9cb5aad7a678d057875774ce9c4ca64754eRyan Lortie gboolean notify) 1100ac44f9cb5aad7a678d057875774ce9c4ca64754eRyan Lortie{ 1101ac44f9cb5aad7a678d057875774ce9c4ca64754eRyan Lortie guint deleted = 0; 1102ac44f9cb5aad7a678d057875774ce9c4ca64754eRyan Lortie gint i; 1103ac44f9cb5aad7a678d057875774ce9c4ca64754eRyan Lortie 1104ac44f9cb5aad7a678d057875774ce9c4ca64754eRyan Lortie for (i = 0; i < hash_table->size; i++) 1105991b625aea5a8fbd7971b17154a0e01366027babHans Petter Jansson { 1106991b625aea5a8fbd7971b17154a0e01366027babHans Petter Jansson GHashNode *node = &hash_table->nodes [i]; 1107991b625aea5a8fbd7971b17154a0e01366027babHans Petter Jansson 1108991b625aea5a8fbd7971b17154a0e01366027babHans Petter Jansson if (node->key_hash > 1 && (* func) (node->key, node->value, user_data)) 1109ac44f9cb5aad7a678d057875774ce9c4ca64754eRyan Lortie { 1110991b625aea5a8fbd7971b17154a0e01366027babHans Petter Jansson g_hash_table_remove_node (hash_table, node, notify); 1111ac44f9cb5aad7a678d057875774ce9c4ca64754eRyan Lortie deleted++; 1112ac44f9cb5aad7a678d057875774ce9c4ca64754eRyan Lortie } 1113991b625aea5a8fbd7971b17154a0e01366027babHans Petter Jansson } 1114ac44f9cb5aad7a678d057875774ce9c4ca64754eRyan Lortie 1115ac44f9cb5aad7a678d057875774ce9c4ca64754eRyan Lortie g_hash_table_maybe_resize (hash_table); 1116ac44f9cb5aad7a678d057875774ce9c4ca64754eRyan Lortie 1117d741d3e7a344622e5a534c34e9e2c0488b2fea4dMatthias Clasen#ifndef G_DISABLE_ASSERT 1118d741d3e7a344622e5a534c34e9e2c0488b2fea4dMatthias Clasen if (deleted > 0) 1119d741d3e7a344622e5a534c34e9e2c0488b2fea4dMatthias Clasen hash_table->version++; 1120d741d3e7a344622e5a534c34e9e2c0488b2fea4dMatthias Clasen#endif 1121d741d3e7a344622e5a534c34e9e2c0488b2fea4dMatthias Clasen 1122ac44f9cb5aad7a678d057875774ce9c4ca64754eRyan Lortie return deleted; 1123ac44f9cb5aad7a678d057875774ce9c4ca64754eRyan Lortie} 1124ac44f9cb5aad7a678d057875774ce9c4ca64754eRyan Lortie 1125a5b4b8bfb18838454d99bdee60294da07e5ef0d2Matthias Clasen/** 1126a2b269bae3315a2ea772b741fb62f683c1db5770Sven Neumann * g_hash_table_foreach_remove: 1127a2b269bae3315a2ea772b741fb62f683c1db5770Sven Neumann * @hash_table: a #GHashTable. 1128a2b269bae3315a2ea772b741fb62f683c1db5770Sven Neumann * @func: the function to call for each key/value pair. 1129a2b269bae3315a2ea772b741fb62f683c1db5770Sven Neumann * @user_data: user data to pass to the function. 11308eed88b24e86f16021d94d9b16f7a2bc895d9239Ryan Lortie * 1131a2b269bae3315a2ea772b741fb62f683c1db5770Sven Neumann * Calls the given function for each key/value pair in the #GHashTable. 1132a52e2986cd4a2147cfc8d41ae23d98907caaf3a0Matthias Clasen * If the function returns %TRUE, then the key/value pair is removed from the 1133a2b269bae3315a2ea772b741fb62f683c1db5770Sven Neumann * #GHashTable. If you supplied key or value destroy functions when creating 1134a2b269bae3315a2ea772b741fb62f683c1db5770Sven Neumann * the #GHashTable, they are used to free the memory allocated for the removed 1135a2b269bae3315a2ea772b741fb62f683c1db5770Sven Neumann * keys and values. 11368eed88b24e86f16021d94d9b16f7a2bc895d9239Ryan Lortie * 1137a73301b3e63ad3e845a898f696a52b7a7c8a2a55Joseph Pingenot * See #GHashTableIter for an alternative way to loop over the 1138d741d3e7a344622e5a534c34e9e2c0488b2fea4dMatthias Clasen * key/value pairs in the hash table. 1139d741d3e7a344622e5a534c34e9e2c0488b2fea4dMatthias Clasen * 1140a2b269bae3315a2ea772b741fb62f683c1db5770Sven Neumann * Return value: the number of key/value pairs removed. 1141a2b269bae3315a2ea772b741fb62f683c1db5770Sven Neumann **/ 1142a2b269bae3315a2ea772b741fb62f683c1db5770Sven Neumannguint 11438eed88b24e86f16021d94d9b16f7a2bc895d9239Ryan Lortieg_hash_table_foreach_remove (GHashTable *hash_table, 11448eed88b24e86f16021d94d9b16f7a2bc895d9239Ryan Lortie GHRFunc func, 11458eed88b24e86f16021d94d9b16f7a2bc895d9239Ryan Lortie gpointer user_data) 11462e0320d57e417f7d1c838d729a99545db2228e9Owen Taylor{ 1147a2b269bae3315a2ea772b741fb62f683c1db5770Sven Neumann g_return_val_if_fail (hash_table != NULL, 0); 1148a2b269bae3315a2ea772b741fb62f683c1db5770Sven Neumann g_return_val_if_fail (func != NULL, 0); 11498eed88b24e86f16021d94d9b16f7a2bc895d9239Ryan Lortie 1150a2b269bae3315a2ea772b741fb62f683c1db5770Sven Neumann return g_hash_table_foreach_remove_or_steal (hash_table, func, user_data, TRUE); 11512e0320d57e417f7d1c838d729a99545db2228e9Owen Taylor} 11522e0320d57e417f7d1c838d729a99545db2228e9Owen Taylor 1153a2b269bae3315a2ea772b741fb62f683c1db5770Sven Neumann/** 1154a2b269bae3315a2ea772b741fb62f683c1db5770Sven Neumann * g_hash_table_foreach_steal: 1155a2b269bae3315a2ea772b741fb62f683c1db5770Sven Neumann * @hash_table: a #GHashTable. 1156a2b269bae3315a2ea772b741fb62f683c1db5770Sven Neumann * @func: the function to call for each key/value pair. 1157a2b269bae3315a2ea772b741fb62f683c1db5770Sven Neumann * @user_data: user data to pass to the function. 11588eed88b24e86f16021d94d9b16f7a2bc895d9239Ryan Lortie * 1159a2b269bae3315a2ea772b741fb62f683c1db5770Sven Neumann * Calls the given function for each key/value pair in the #GHashTable. 1160a52e2986cd4a2147cfc8d41ae23d98907caaf3a0Matthias Clasen * If the function returns %TRUE, then the key/value pair is removed from the 1161a2b269bae3315a2ea772b741fb62f683c1db5770Sven Neumann * #GHashTable, but no key or value destroy functions are called. 11628eed88b24e86f16021d94d9b16f7a2bc895d9239Ryan Lortie * 1163a73301b3e63ad3e845a898f696a52b7a7c8a2a55Joseph Pingenot * See #GHashTableIter for an alternative way to loop over the 1164d741d3e7a344622e5a534c34e9e2c0488b2fea4dMatthias Clasen * key/value pairs in the hash table. 1165d741d3e7a344622e5a534c34e9e2c0488b2fea4dMatthias Clasen * 1166a2b269bae3315a2ea772b741fb62f683c1db5770Sven Neumann * Return value: the number of key/value pairs removed. 1167a2b269bae3315a2ea772b741fb62f683c1db5770Sven Neumann **/ 1168a2b269bae3315a2ea772b741fb62f683c1db5770Sven Neumannguint 1169a2b269bae3315a2ea772b741fb62f683c1db5770Sven Neumanng_hash_table_foreach_steal (GHashTable *hash_table, 11708eed88b24e86f16021d94d9b16f7a2bc895d9239Ryan Lortie GHRFunc func, 11718eed88b24e86f16021d94d9b16f7a2bc895d9239Ryan Lortie gpointer user_data) 11722e0320d57e417f7d1c838d729a99545db2228e9Owen Taylor{ 1173a2b269bae3315a2ea772b741fb62f683c1db5770Sven Neumann g_return_val_if_fail (hash_table != NULL, 0); 1174a2b269bae3315a2ea772b741fb62f683c1db5770Sven Neumann g_return_val_if_fail (func != NULL, 0); 11758eed88b24e86f16021d94d9b16f7a2bc895d9239Ryan Lortie 1176a2b269bae3315a2ea772b741fb62f683c1db5770Sven Neumann return g_hash_table_foreach_remove_or_steal (hash_table, func, user_data, FALSE); 11772e0320d57e417f7d1c838d729a99545db2228e9Owen Taylor} 11782e0320d57e417f7d1c838d729a99545db2228e9Owen Taylor 1179a2b269bae3315a2ea772b741fb62f683c1db5770Sven Neumann/** 1180a2b269bae3315a2ea772b741fb62f683c1db5770Sven Neumann * g_hash_table_foreach: 1181a2b269bae3315a2ea772b741fb62f683c1db5770Sven Neumann * @hash_table: a #GHashTable. 1182a2b269bae3315a2ea772b741fb62f683c1db5770Sven Neumann * @func: the function to call for each key/value pair. 1183a2b269bae3315a2ea772b741fb62f683c1db5770Sven Neumann * @user_data: user data to pass to the function. 11848eed88b24e86f16021d94d9b16f7a2bc895d9239Ryan Lortie * 1185eb2f6f6fc1052abfa05f016ab2aed0cd0c338992Havoc Pennington * Calls the given function for each of the key/value pairs in the 1186eb2f6f6fc1052abfa05f016ab2aed0cd0c338992Havoc Pennington * #GHashTable. The function is passed the key and value of each 1187eb2f6f6fc1052abfa05f016ab2aed0cd0c338992Havoc Pennington * pair, and the given @user_data parameter. The hash table may not 1188eb2f6f6fc1052abfa05f016ab2aed0cd0c338992Havoc Pennington * be modified while iterating over it (you can't add/remove 1189eb2f6f6fc1052abfa05f016ab2aed0cd0c338992Havoc Pennington * items). To remove all items matching a predicate, use 119027096aedb58342fc8a25c17fa7d6647209425f4eMatthias Clasen * g_hash_table_foreach_remove(). 11912ef43de2af9dbb1b1ea583639c7339afe9c09af0Tim Janik * 11922ef43de2af9dbb1b1ea583639c7339afe9c09af0Tim Janik * See g_hash_table_find() for performance caveats for linear 11932ef43de2af9dbb1b1ea583639c7339afe9c09af0Tim Janik * order searches in contrast to g_hash_table_lookup(). 1194a2b269bae3315a2ea772b741fb62f683c1db5770Sven Neumann **/ 11952e0320d57e417f7d1c838d729a99545db2228e9Owen Taylorvoid 11962e0320d57e417f7d1c838d729a99545db2228e9Owen Taylorg_hash_table_foreach (GHashTable *hash_table, 11978eed88b24e86f16021d94d9b16f7a2bc895d9239Ryan Lortie GHFunc func, 11988eed88b24e86f16021d94d9b16f7a2bc895d9239Ryan Lortie gpointer user_data) 11992e0320d57e417f7d1c838d729a99545db2228e9Owen Taylor{ 12002e0320d57e417f7d1c838d729a99545db2228e9Owen Taylor gint i; 12018eed88b24e86f16021d94d9b16f7a2bc895d9239Ryan Lortie 12022d68cbbb7d37d3f265bf1087e6ddedcc58bc62beTim Janik g_return_if_fail (hash_table != NULL); 12032d68cbbb7d37d3f265bf1087e6ddedcc58bc62beTim Janik g_return_if_fail (func != NULL); 12048eed88b24e86f16021d94d9b16f7a2bc895d9239Ryan Lortie 12057519c2338ae484135b44bbb7eb49719aea8c4ca3Lauri Alanko for (i = 0; i < hash_table->size; i++) 1206991b625aea5a8fbd7971b17154a0e01366027babHans Petter Jansson { 1207991b625aea5a8fbd7971b17154a0e01366027babHans Petter Jansson GHashNode *node = &hash_table->nodes [i]; 1208991b625aea5a8fbd7971b17154a0e01366027babHans Petter Jansson 1209991b625aea5a8fbd7971b17154a0e01366027babHans Petter Jansson if (node->key_hash > 1) 1210991b625aea5a8fbd7971b17154a0e01366027babHans Petter Jansson (* func) (node->key, node->value, user_data); 1211991b625aea5a8fbd7971b17154a0e01366027babHans Petter Jansson } 12122e0320d57e417f7d1c838d729a99545db2228e9Owen Taylor} 12132e0320d57e417f7d1c838d729a99545db2228e9Owen Taylor 1214a2b269bae3315a2ea772b741fb62f683c1db5770Sven Neumann/** 1215ee4e622d3724a6dfee8ce9463eccb31081cf852fTim Janik * g_hash_table_find: 1216ee4e622d3724a6dfee8ce9463eccb31081cf852fTim Janik * @hash_table: a #GHashTable. 1217ee4e622d3724a6dfee8ce9463eccb31081cf852fTim Janik * @predicate: function to test the key/value pairs for a certain property. 1218ee4e622d3724a6dfee8ce9463eccb31081cf852fTim Janik * @user_data: user data to pass to the function. 12198eed88b24e86f16021d94d9b16f7a2bc895d9239Ryan Lortie * 12208eed88b24e86f16021d94d9b16f7a2bc895d9239Ryan Lortie * Calls the given function for key/value pairs in the #GHashTable until 12218eed88b24e86f16021d94d9b16f7a2bc895d9239Ryan Lortie * @predicate returns %TRUE. The function is passed the key and value of 12223ce97fa284cbefdc2eb957f50a3a76d6ef923464Matthias Clasen * each pair, and the given @user_data parameter. The hash table may not 12232ef43de2af9dbb1b1ea583639c7339afe9c09af0Tim Janik * be modified while iterating over it (you can't add/remove items). 12242ef43de2af9dbb1b1ea583639c7339afe9c09af0Tim Janik * 12252ef43de2af9dbb1b1ea583639c7339afe9c09af0Tim Janik * Note, that hash tables are really only optimized for forward lookups, 12262ef43de2af9dbb1b1ea583639c7339afe9c09af0Tim Janik * i.e. g_hash_table_lookup(). 12272ef43de2af9dbb1b1ea583639c7339afe9c09af0Tim Janik * So code that frequently issues g_hash_table_find() or 12282ef43de2af9dbb1b1ea583639c7339afe9c09af0Tim Janik * g_hash_table_foreach() (e.g. in the order of once per every entry in a 12292ef43de2af9dbb1b1ea583639c7339afe9c09af0Tim Janik * hash table) should probably be reworked to use additional or different 12302ef43de2af9dbb1b1ea583639c7339afe9c09af0Tim Janik * data structures for reverse lookups (keep in mind that an O(n) find/foreach 12312ef43de2af9dbb1b1ea583639c7339afe9c09af0Tim Janik * operation issued for all n values in a hash table ends up needing O(n*n) 12322ef43de2af9dbb1b1ea583639c7339afe9c09af0Tim Janik * operations). 12333ce97fa284cbefdc2eb957f50a3a76d6ef923464Matthias Clasen * 12342ef43de2af9dbb1b1ea583639c7339afe9c09af0Tim Janik * Return value: The value of the first key/value pair is returned, for which 12352ef43de2af9dbb1b1ea583639c7339afe9c09af0Tim Janik * func evaluates to %TRUE. If no pair with the requested property is found, 12363ce97fa284cbefdc2eb957f50a3a76d6ef923464Matthias Clasen * %NULL is returned. 12373ce97fa284cbefdc2eb957f50a3a76d6ef923464Matthias Clasen * 12383ce97fa284cbefdc2eb957f50a3a76d6ef923464Matthias Clasen * Since: 2.4 1239ee4e622d3724a6dfee8ce9463eccb31081cf852fTim Janik **/ 1240ee4e622d3724a6dfee8ce9463eccb31081cf852fTim Janikgpointer 12418eed88b24e86f16021d94d9b16f7a2bc895d9239Ryan Lortieg_hash_table_find (GHashTable *hash_table, 12428eed88b24e86f16021d94d9b16f7a2bc895d9239Ryan Lortie GHRFunc predicate, 12438eed88b24e86f16021d94d9b16f7a2bc895d9239Ryan Lortie gpointer user_data) 1244ee4e622d3724a6dfee8ce9463eccb31081cf852fTim Janik{ 1245ee4e622d3724a6dfee8ce9463eccb31081cf852fTim Janik gint i; 12468eed88b24e86f16021d94d9b16f7a2bc895d9239Ryan Lortie 1247ee4e622d3724a6dfee8ce9463eccb31081cf852fTim Janik g_return_val_if_fail (hash_table != NULL, NULL); 1248ee4e622d3724a6dfee8ce9463eccb31081cf852fTim Janik g_return_val_if_fail (predicate != NULL, NULL); 12498eed88b24e86f16021d94d9b16f7a2bc895d9239Ryan Lortie 1250ee4e622d3724a6dfee8ce9463eccb31081cf852fTim Janik for (i = 0; i < hash_table->size; i++) 1251991b625aea5a8fbd7971b17154a0e01366027babHans Petter Jansson { 1252991b625aea5a8fbd7971b17154a0e01366027babHans Petter Jansson GHashNode *node = &hash_table->nodes [i]; 1253991b625aea5a8fbd7971b17154a0e01366027babHans Petter Jansson 1254991b625aea5a8fbd7971b17154a0e01366027babHans Petter Jansson if (node->key_hash > 1 && predicate (node->key, node->value, user_data)) 12558eed88b24e86f16021d94d9b16f7a2bc895d9239Ryan Lortie return node->value; 1256991b625aea5a8fbd7971b17154a0e01366027babHans Petter Jansson } 1257991b625aea5a8fbd7971b17154a0e01366027babHans Petter Jansson 1258ee4e622d3724a6dfee8ce9463eccb31081cf852fTim Janik return NULL; 1259ee4e622d3724a6dfee8ce9463eccb31081cf852fTim Janik} 1260ee4e622d3724a6dfee8ce9463eccb31081cf852fTim Janik 1261ee4e622d3724a6dfee8ce9463eccb31081cf852fTim Janik/** 1262a2b269bae3315a2ea772b741fb62f683c1db5770Sven Neumann * g_hash_table_size: 1263a2b269bae3315a2ea772b741fb62f683c1db5770Sven Neumann * @hash_table: a #GHashTable. 12648eed88b24e86f16021d94d9b16f7a2bc895d9239Ryan Lortie * 1265a2b269bae3315a2ea772b741fb62f683c1db5770Sven Neumann * Returns the number of elements contained in the #GHashTable. 12668eed88b24e86f16021d94d9b16f7a2bc895d9239Ryan Lortie * 1267a2b269bae3315a2ea772b741fb62f683c1db5770Sven Neumann * Return value: the number of key/value pairs in the #GHashTable. 1268a2b269bae3315a2ea772b741fb62f683c1db5770Sven Neumann **/ 1269d31ba84c8ea40b6f0199318e43cc2bb2e816c586Tim Janikguint 12702d68cbbb7d37d3f265bf1087e6ddedcc58bc62beTim Janikg_hash_table_size (GHashTable *hash_table) 12717519c2338ae484135b44bbb7eb49719aea8c4ca3Lauri Alanko{ 12722d68cbbb7d37d3f265bf1087e6ddedcc58bc62beTim Janik g_return_val_if_fail (hash_table != NULL, 0); 12738eed88b24e86f16021d94d9b16f7a2bc895d9239Ryan Lortie 12747519c2338ae484135b44bbb7eb49719aea8c4ca3Lauri Alanko return hash_table->nnodes; 12757519c2338ae484135b44bbb7eb49719aea8c4ca3Lauri Alanko} 12762e0320d57e417f7d1c838d729a99545db2228e9Owen Taylor 1277db8642a56c0436aeb730ead593140bc01b82d4acEmmanuele Bassi/** 1278db8642a56c0436aeb730ead593140bc01b82d4acEmmanuele Bassi * g_hash_table_get_keys: 1279db8642a56c0436aeb730ead593140bc01b82d4acEmmanuele Bassi * @hash_table: a #GHashTable 1280db8642a56c0436aeb730ead593140bc01b82d4acEmmanuele Bassi * 1281db8642a56c0436aeb730ead593140bc01b82d4acEmmanuele Bassi * Retrieves every key inside @hash_table. The returned data is valid 1282db8642a56c0436aeb730ead593140bc01b82d4acEmmanuele Bassi * until @hash_table is modified. 1283db8642a56c0436aeb730ead593140bc01b82d4acEmmanuele Bassi * 1284db8642a56c0436aeb730ead593140bc01b82d4acEmmanuele Bassi * Return value: a #GList containing all the keys inside the hash 1285db8642a56c0436aeb730ead593140bc01b82d4acEmmanuele Bassi * table. The content of the list is owned by the hash table and 1286db8642a56c0436aeb730ead593140bc01b82d4acEmmanuele Bassi * should not be modified or freed. Use g_list_free() when done 1287db8642a56c0436aeb730ead593140bc01b82d4acEmmanuele Bassi * using the list. 1288db8642a56c0436aeb730ead593140bc01b82d4acEmmanuele Bassi * 1289db8642a56c0436aeb730ead593140bc01b82d4acEmmanuele Bassi * Since: 2.14 1290db8642a56c0436aeb730ead593140bc01b82d4acEmmanuele Bassi */ 1291db8642a56c0436aeb730ead593140bc01b82d4acEmmanuele BassiGList * 1292db8642a56c0436aeb730ead593140bc01b82d4acEmmanuele Bassig_hash_table_get_keys (GHashTable *hash_table) 1293db8642a56c0436aeb730ead593140bc01b82d4acEmmanuele Bassi{ 1294db8642a56c0436aeb730ead593140bc01b82d4acEmmanuele Bassi gint i; 1295db8642a56c0436aeb730ead593140bc01b82d4acEmmanuele Bassi GList *retval; 12968eed88b24e86f16021d94d9b16f7a2bc895d9239Ryan Lortie 1297db8642a56c0436aeb730ead593140bc01b82d4acEmmanuele Bassi g_return_val_if_fail (hash_table != NULL, NULL); 12988eed88b24e86f16021d94d9b16f7a2bc895d9239Ryan Lortie 1299db8642a56c0436aeb730ead593140bc01b82d4acEmmanuele Bassi retval = NULL; 1300db8642a56c0436aeb730ead593140bc01b82d4acEmmanuele Bassi for (i = 0; i < hash_table->size; i++) 1301991b625aea5a8fbd7971b17154a0e01366027babHans Petter Jansson { 1302991b625aea5a8fbd7971b17154a0e01366027babHans Petter Jansson GHashNode *node = &hash_table->nodes [i]; 1303991b625aea5a8fbd7971b17154a0e01366027babHans Petter Jansson 1304991b625aea5a8fbd7971b17154a0e01366027babHans Petter Jansson if (node->key_hash > 1) 1305991b625aea5a8fbd7971b17154a0e01366027babHans Petter Jansson retval = g_list_prepend (retval, node->key); 1306991b625aea5a8fbd7971b17154a0e01366027babHans Petter Jansson } 13078eed88b24e86f16021d94d9b16f7a2bc895d9239Ryan Lortie 1308db8642a56c0436aeb730ead593140bc01b82d4acEmmanuele Bassi return retval; 1309db8642a56c0436aeb730ead593140bc01b82d4acEmmanuele Bassi} 1310db8642a56c0436aeb730ead593140bc01b82d4acEmmanuele Bassi 1311db8642a56c0436aeb730ead593140bc01b82d4acEmmanuele Bassi/** 1312db8642a56c0436aeb730ead593140bc01b82d4acEmmanuele Bassi * g_hash_table_get_values: 1313db8642a56c0436aeb730ead593140bc01b82d4acEmmanuele Bassi * @hash_table: a #GHashTable 1314db8642a56c0436aeb730ead593140bc01b82d4acEmmanuele Bassi * 1315db8642a56c0436aeb730ead593140bc01b82d4acEmmanuele Bassi * Retrieves every value inside @hash_table. The returned data is 1316db8642a56c0436aeb730ead593140bc01b82d4acEmmanuele Bassi * valid until @hash_table is modified. 1317db8642a56c0436aeb730ead593140bc01b82d4acEmmanuele Bassi * 1318db8642a56c0436aeb730ead593140bc01b82d4acEmmanuele Bassi * Return value: a #GList containing all the values inside the hash 1319db8642a56c0436aeb730ead593140bc01b82d4acEmmanuele Bassi * table. The content of the list is owned by the hash table and 1320db8642a56c0436aeb730ead593140bc01b82d4acEmmanuele Bassi * should not be modified or freed. Use g_list_free() when done 1321db8642a56c0436aeb730ead593140bc01b82d4acEmmanuele Bassi * using the list. 1322db8642a56c0436aeb730ead593140bc01b82d4acEmmanuele Bassi * 1323db8642a56c0436aeb730ead593140bc01b82d4acEmmanuele Bassi * Since: 2.14 1324db8642a56c0436aeb730ead593140bc01b82d4acEmmanuele Bassi */ 1325db8642a56c0436aeb730ead593140bc01b82d4acEmmanuele BassiGList * 1326db8642a56c0436aeb730ead593140bc01b82d4acEmmanuele Bassig_hash_table_get_values (GHashTable *hash_table) 1327db8642a56c0436aeb730ead593140bc01b82d4acEmmanuele Bassi{ 1328db8642a56c0436aeb730ead593140bc01b82d4acEmmanuele Bassi gint i; 1329db8642a56c0436aeb730ead593140bc01b82d4acEmmanuele Bassi GList *retval; 13308eed88b24e86f16021d94d9b16f7a2bc895d9239Ryan Lortie 1331db8642a56c0436aeb730ead593140bc01b82d4acEmmanuele Bassi g_return_val_if_fail (hash_table != NULL, NULL); 13328eed88b24e86f16021d94d9b16f7a2bc895d9239Ryan Lortie 1333db8642a56c0436aeb730ead593140bc01b82d4acEmmanuele Bassi retval = NULL; 1334db8642a56c0436aeb730ead593140bc01b82d4acEmmanuele Bassi for (i = 0; i < hash_table->size; i++) 1335991b625aea5a8fbd7971b17154a0e01366027babHans Petter Jansson { 1336991b625aea5a8fbd7971b17154a0e01366027babHans Petter Jansson GHashNode *node = &hash_table->nodes [i]; 1337991b625aea5a8fbd7971b17154a0e01366027babHans Petter Jansson 1338991b625aea5a8fbd7971b17154a0e01366027babHans Petter Jansson if (node->key_hash > 1) 1339991b625aea5a8fbd7971b17154a0e01366027babHans Petter Jansson retval = g_list_prepend (retval, node->value); 1340991b625aea5a8fbd7971b17154a0e01366027babHans Petter Jansson } 13418eed88b24e86f16021d94d9b16f7a2bc895d9239Ryan Lortie 1342db8642a56c0436aeb730ead593140bc01b82d4acEmmanuele Bassi return retval; 1343db8642a56c0436aeb730ead593140bc01b82d4acEmmanuele Bassi} 1344db8642a56c0436aeb730ead593140bc01b82d4acEmmanuele Bassi 1345608a31b98e1420f487190871ee7312db2643d93dMatthias Clasen#define __G_HASH_C__ 1346608a31b98e1420f487190871ee7312db2643d93dMatthias Clasen#include "galiasdef.c" 1347