1 | /* GLIB - Library of useful routines for C programming |
2 | * Copyright (C) 1995-1997 Peter Mattis, Spencer Kimball and Josh MacDonald |
3 | * |
4 | * This library is free software; you can redistribute it and/or |
5 | * modify it under the terms of the GNU Lesser General Public |
6 | * License as published by the Free Software Foundation; either |
7 | * version 2.1 of the License, or (at your option) any later version. |
8 | * |
9 | * This library is distributed in the hope that it will be useful, |
10 | * but WITHOUT ANY WARRANTY; without even the implied warranty of |
11 | * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the GNU |
12 | * Lesser General Public License for more details. |
13 | * |
14 | * You should have received a copy of the GNU Lesser General Public |
15 | * License along with this library; if not, see <http://www.gnu.org/licenses/>. |
16 | */ |
17 | |
18 | /* |
19 | * Modified by the GLib Team and others 1997-2000. See the AUTHORS |
20 | * file for a list of people on the GLib Team. See the ChangeLog |
21 | * files for a list of changes. These files are distributed with |
22 | * GLib at ftp://ftp.gtk.org/pub/gtk/. |
23 | */ |
24 | |
25 | /* |
26 | * MT safe |
27 | */ |
28 | |
29 | #include "config.h" |
30 | |
31 | #include <string.h> /* memset */ |
32 | |
33 | #include "ghash.h" |
34 | #include "gmacros.h" |
35 | #include "glib-private.h" |
36 | #include "gstrfuncs.h" |
37 | #include "gatomic.h" |
38 | #include "gtestutils.h" |
39 | #include "gslice.h" |
40 | #include "grefcount.h" |
41 | #include "gvalgrind.h" |
42 | |
43 | /* The following #pragma is here so we can do this... |
44 | * |
45 | * #ifndef USE_SMALL_ARRAYS |
46 | * is_big = TRUE; |
47 | * #endif |
48 | * return is_big ? *(((gpointer *) a) + index) : GUINT_TO_POINTER (*(((guint *) a) + index)); |
49 | * |
50 | * ...instead of this... |
51 | * |
52 | * #ifndef USE_SMALL_ARRAYS |
53 | * return *(((gpointer *) a) + index); |
54 | * #else |
55 | * return is_big ? *(((gpointer *) a) + index) : GUINT_TO_POINTER (*(((guint *) a) + index)); |
56 | * #endif |
57 | * |
58 | * ...and still compile successfully when -Werror=duplicated-branches is passed. */ |
59 | |
60 | #if defined(__GNUC__) && __GNUC__ > 6 |
61 | #pragma GCC diagnostic ignored "-Wduplicated-branches" |
62 | #endif |
63 | |
64 | /** |
65 | * SECTION:hash_tables |
66 | * @title: Hash Tables |
67 | * @short_description: associations between keys and values so that |
68 | * given a key the value can be found quickly |
69 | * |
70 | * A #GHashTable provides associations between keys and values which is |
71 | * optimized so that given a key, the associated value can be found, |
72 | * inserted or removed in amortized O(1). All operations going through |
73 | * each element take O(n) time (list all keys/values, table resize, etc.). |
74 | * |
75 | * Note that neither keys nor values are copied when inserted into the |
76 | * #GHashTable, so they must exist for the lifetime of the #GHashTable. |
77 | * This means that the use of static strings is OK, but temporary |
78 | * strings (i.e. those created in buffers and those returned by GTK |
79 | * widgets) should be copied with g_strdup() before being inserted. |
80 | * |
81 | * If keys or values are dynamically allocated, you must be careful to |
82 | * ensure that they are freed when they are removed from the |
83 | * #GHashTable, and also when they are overwritten by new insertions |
84 | * into the #GHashTable. It is also not advisable to mix static strings |
85 | * and dynamically-allocated strings in a #GHashTable, because it then |
86 | * becomes difficult to determine whether the string should be freed. |
87 | * |
88 | * To create a #GHashTable, use g_hash_table_new(). |
89 | * |
90 | * To insert a key and value into a #GHashTable, use |
91 | * g_hash_table_insert(). |
92 | * |
93 | * To look up a value corresponding to a given key, use |
94 | * g_hash_table_lookup() and g_hash_table_lookup_extended(). |
95 | * |
96 | * g_hash_table_lookup_extended() can also be used to simply |
97 | * check if a key is present in the hash table. |
98 | * |
99 | * To remove a key and value, use g_hash_table_remove(). |
100 | * |
101 | * To call a function for each key and value pair use |
102 | * g_hash_table_foreach() or use an iterator to iterate over the |
103 | * key/value pairs in the hash table, see #GHashTableIter. The iteration order |
104 | * of a hash table is not defined, and you must not rely on iterating over |
105 | * keys/values in the same order as they were inserted. |
106 | * |
107 | * To destroy a #GHashTable use g_hash_table_destroy(). |
108 | * |
109 | * A common use-case for hash tables is to store information about a |
110 | * set of keys, without associating any particular value with each |
111 | * key. GHashTable optimizes one way of doing so: If you store only |
112 | * key-value pairs where key == value, then GHashTable does not |
113 | * allocate memory to store the values, which can be a considerable |
114 | * space saving, if your set is large. The functions |
115 | * g_hash_table_add() and g_hash_table_contains() are designed to be |
116 | * used when using #GHashTable this way. |
117 | * |
118 | * #GHashTable is not designed to be statically initialised with keys and |
119 | * values known at compile time. To build a static hash table, use a tool such |
120 | * as [gperf](https://www.gnu.org/software/gperf/). |
121 | */ |
122 | |
123 | /** |
124 | * GHashTable: |
125 | * |
126 | * The #GHashTable struct is an opaque data structure to represent a |
127 | * [Hash Table][glib-Hash-Tables]. It should only be accessed via the |
128 | * following functions. |
129 | */ |
130 | |
131 | /** |
132 | * GHashFunc: |
133 | * @key: a key |
134 | * |
135 | * Specifies the type of the hash function which is passed to |
136 | * g_hash_table_new() when a #GHashTable is created. |
137 | * |
138 | * The function is passed a key and should return a #guint hash value. |
139 | * The functions g_direct_hash(), g_int_hash() and g_str_hash() provide |
140 | * hash functions which can be used when the key is a #gpointer, #gint*, |
141 | * and #gchar* respectively. |
142 | * |
143 | * g_direct_hash() is also the appropriate hash function for keys |
144 | * of the form `GINT_TO_POINTER (n)` (or similar macros). |
145 | * |
146 | * A good hash functions should produce |
147 | * hash values that are evenly distributed over a fairly large range. |
148 | * The modulus is taken with the hash table size (a prime number) to |
149 | * find the 'bucket' to place each key into. The function should also |
150 | * be very fast, since it is called for each key lookup. |
151 | * |
152 | * Note that the hash functions provided by GLib have these qualities, |
153 | * but are not particularly robust against manufactured keys that |
154 | * cause hash collisions. Therefore, you should consider choosing |
155 | * a more secure hash function when using a GHashTable with keys |
156 | * that originate in untrusted data (such as HTTP requests). |
157 | * Using g_str_hash() in that situation might make your application |
158 | * vulnerable to |
159 | * [Algorithmic Complexity Attacks](https://lwn.net/Articles/474912/). |
160 | * |
161 | * The key to choosing a good hash is unpredictability. Even |
162 | * cryptographic hashes are very easy to find collisions for when the |
163 | * remainder is taken modulo a somewhat predictable prime number. There |
164 | * must be an element of randomness that an attacker is unable to guess. |
165 | * |
166 | * Returns: the hash value corresponding to the key |
167 | */ |
168 | |
169 | /** |
170 | * GHFunc: |
171 | * @key: a key |
172 | * @value: the value corresponding to the key |
173 | * @user_data: user data passed to g_hash_table_foreach() |
174 | * |
175 | * Specifies the type of the function passed to g_hash_table_foreach(). |
176 | * It is called with each key/value pair, together with the @user_data |
177 | * parameter which is passed to g_hash_table_foreach(). |
178 | */ |
179 | |
180 | /** |
181 | * GHRFunc: |
182 | * @key: a key |
183 | * @value: the value associated with the key |
184 | * @user_data: user data passed to g_hash_table_remove() |
185 | * |
186 | * Specifies the type of the function passed to |
187 | * g_hash_table_foreach_remove(). It is called with each key/value |
188 | * pair, together with the @user_data parameter passed to |
189 | * g_hash_table_foreach_remove(). It should return %TRUE if the |
190 | * key/value pair should be removed from the #GHashTable. |
191 | * |
192 | * Returns: %TRUE if the key/value pair should be removed from the |
193 | * #GHashTable |
194 | */ |
195 | |
196 | /** |
197 | * GEqualFunc: |
198 | * @a: a value |
199 | * @b: a value to compare with |
200 | * |
201 | * Specifies the type of a function used to test two values for |
202 | * equality. The function should return %TRUE if both values are equal |
203 | * and %FALSE otherwise. |
204 | * |
205 | * Returns: %TRUE if @a = @b; %FALSE otherwise |
206 | */ |
207 | |
208 | /** |
209 | * GHashTableIter: |
210 | * |
211 | * A GHashTableIter structure represents an iterator that can be used |
212 | * to iterate over the elements of a #GHashTable. GHashTableIter |
213 | * structures are typically allocated on the stack and then initialized |
214 | * with g_hash_table_iter_init(). |
215 | * |
216 | * The iteration order of a #GHashTableIter over the keys/values in a hash |
217 | * table is not defined. |
218 | */ |
219 | |
220 | /** |
221 | * g_hash_table_freeze: |
222 | * @hash_table: a #GHashTable |
223 | * |
224 | * This function is deprecated and will be removed in the next major |
225 | * release of GLib. It does nothing. |
226 | */ |
227 | |
228 | /** |
229 | * g_hash_table_thaw: |
230 | * @hash_table: a #GHashTable |
231 | * |
232 | * This function is deprecated and will be removed in the next major |
233 | * release of GLib. It does nothing. |
234 | */ |
235 | |
236 | #define HASH_TABLE_MIN_SHIFT 3 /* 1 << 3 == 8 buckets */ |
237 | |
238 | #define UNUSED_HASH_VALUE 0 |
239 | #define TOMBSTONE_HASH_VALUE 1 |
240 | #define HASH_IS_UNUSED(h_) ((h_) == UNUSED_HASH_VALUE) |
241 | #define HASH_IS_TOMBSTONE(h_) ((h_) == TOMBSTONE_HASH_VALUE) |
242 | #define HASH_IS_REAL(h_) ((h_) >= 2) |
243 | |
244 | /* If int is smaller than void * on our arch, we start out with |
245 | * int-sized keys and values and resize to pointer-sized entries as |
246 | * needed. This saves a good amount of memory when the HT is being |
247 | * used with e.g. GUINT_TO_POINTER(). */ |
248 | |
249 | #define BIG_ENTRY_SIZE (SIZEOF_VOID_P) |
250 | #define SMALL_ENTRY_SIZE (SIZEOF_INT) |
251 | |
252 | #if SMALL_ENTRY_SIZE < BIG_ENTRY_SIZE |
253 | # define USE_SMALL_ARRAYS |
254 | #endif |
255 | |
256 | struct _GHashTable |
257 | { |
258 | gsize size; |
259 | gint mod; |
260 | guint mask; |
261 | gint nnodes; |
262 | gint noccupied; /* nnodes + tombstones */ |
263 | |
264 | guint have_big_keys : 1; |
265 | guint have_big_values : 1; |
266 | |
267 | gpointer keys; |
268 | guint *hashes; |
269 | gpointer values; |
270 | |
271 | GHashFunc hash_func; |
272 | GEqualFunc key_equal_func; |
273 | gatomicrefcount ref_count; |
274 | #ifndef G_DISABLE_ASSERT |
275 | /* |
276 | * Tracks the structure of the hash table, not its contents: is only |
277 | * incremented when a node is added or removed (is not incremented |
278 | * when the key or data of a node is modified). |
279 | */ |
280 | int version; |
281 | #endif |
282 | GDestroyNotify key_destroy_func; |
283 | GDestroyNotify value_destroy_func; |
284 | }; |
285 | |
286 | typedef struct |
287 | { |
288 | GHashTable *hash_table; |
289 | gpointer dummy1; |
290 | gpointer dummy2; |
291 | gint position; |
292 | gboolean dummy3; |
293 | gint version; |
294 | } RealIter; |
295 | |
296 | G_STATIC_ASSERT (sizeof (GHashTableIter) == sizeof (RealIter)); |
297 | G_STATIC_ASSERT (G_ALIGNOF (GHashTableIter) >= G_ALIGNOF (RealIter)); |
298 | |
299 | /* Each table size has an associated prime modulo (the first prime |
300 | * lower than the table size) used to find the initial bucket. Probing |
301 | * then works modulo 2^n. The prime modulo is necessary to get a |
302 | * good distribution with poor hash functions. |
303 | */ |
304 | static const gint prime_mod [] = |
305 | { |
306 | 1, /* For 1 << 0 */ |
307 | 2, |
308 | 3, |
309 | 7, |
310 | 13, |
311 | 31, |
312 | 61, |
313 | 127, |
314 | 251, |
315 | 509, |
316 | 1021, |
317 | 2039, |
318 | 4093, |
319 | 8191, |
320 | 16381, |
321 | 32749, |
322 | 65521, /* For 1 << 16 */ |
323 | 131071, |
324 | 262139, |
325 | 524287, |
326 | 1048573, |
327 | 2097143, |
328 | 4194301, |
329 | 8388593, |
330 | 16777213, |
331 | 33554393, |
332 | 67108859, |
333 | 134217689, |
334 | 268435399, |
335 | 536870909, |
336 | 1073741789, |
337 | 2147483647 /* For 1 << 31 */ |
338 | }; |
339 | |
340 | static void |
341 | g_hash_table_set_shift (GHashTable *hash_table, gint shift) |
342 | { |
343 | hash_table->size = 1 << shift; |
344 | hash_table->mod = prime_mod [shift]; |
345 | |
346 | /* hash_table->size is always a power of two, so we can calculate the mask |
347 | * by simply subtracting 1 from it. The leading assertion ensures that |
348 | * we're really dealing with a power of two. */ |
349 | |
350 | g_assert ((hash_table->size & (hash_table->size - 1)) == 0); |
351 | hash_table->mask = hash_table->size - 1; |
352 | } |
353 | |
354 | static gint |
355 | g_hash_table_find_closest_shift (gint n) |
356 | { |
357 | gint i; |
358 | |
359 | for (i = 0; n; i++) |
360 | n >>= 1; |
361 | |
362 | return i; |
363 | } |
364 | |
365 | static void |
366 | g_hash_table_set_shift_from_size (GHashTable *hash_table, gint size) |
367 | { |
368 | gint shift; |
369 | |
370 | shift = g_hash_table_find_closest_shift (n: size); |
371 | shift = MAX (shift, HASH_TABLE_MIN_SHIFT); |
372 | |
373 | g_hash_table_set_shift (hash_table, shift); |
374 | } |
375 | |
376 | static inline gpointer |
377 | g_hash_table_realloc_key_or_value_array (gpointer a, guint size, G_GNUC_UNUSED gboolean is_big) |
378 | { |
379 | #ifdef USE_SMALL_ARRAYS |
380 | return g_realloc (mem: a, n_bytes: size * (is_big ? BIG_ENTRY_SIZE : SMALL_ENTRY_SIZE)); |
381 | #else |
382 | return g_renew (gpointer, a, size); |
383 | #endif |
384 | } |
385 | |
386 | static inline gpointer |
387 | g_hash_table_fetch_key_or_value (gpointer a, guint index, gboolean is_big) |
388 | { |
389 | #ifndef USE_SMALL_ARRAYS |
390 | is_big = TRUE; |
391 | #endif |
392 | return is_big ? *(((gpointer *) a) + index) : GUINT_TO_POINTER (*(((guint *) a) + index)); |
393 | } |
394 | |
395 | static inline void |
396 | g_hash_table_assign_key_or_value (gpointer a, guint index, gboolean is_big, gpointer v) |
397 | { |
398 | #ifndef USE_SMALL_ARRAYS |
399 | is_big = TRUE; |
400 | #endif |
401 | if (is_big) |
402 | *(((gpointer *) a) + index) = v; |
403 | else |
404 | *(((guint *) a) + index) = GPOINTER_TO_UINT (v); |
405 | } |
406 | |
407 | static inline gpointer |
408 | g_hash_table_evict_key_or_value (gpointer a, guint index, gboolean is_big, gpointer v) |
409 | { |
410 | #ifndef USE_SMALL_ARRAYS |
411 | is_big = TRUE; |
412 | #endif |
413 | if (is_big) |
414 | { |
415 | gpointer r = *(((gpointer *) a) + index); |
416 | *(((gpointer *) a) + index) = v; |
417 | return r; |
418 | } |
419 | else |
420 | { |
421 | gpointer r = GUINT_TO_POINTER (*(((guint *) a) + index)); |
422 | *(((guint *) a) + index) = GPOINTER_TO_UINT (v); |
423 | return r; |
424 | } |
425 | } |
426 | |
427 | static inline guint |
428 | g_hash_table_hash_to_index (GHashTable *hash_table, guint hash) |
429 | { |
430 | /* Multiply the hash by a small prime before applying the modulo. This |
431 | * prevents the table from becoming densely packed, even with a poor hash |
432 | * function. A densely packed table would have poor performance on |
433 | * workloads with many failed lookups or a high degree of churn. */ |
434 | return (hash * 11) % hash_table->mod; |
435 | } |
436 | |
437 | /* |
438 | * g_hash_table_lookup_node: |
439 | * @hash_table: our #GHashTable |
440 | * @key: the key to look up against |
441 | * @hash_return: key hash return location |
442 | * |
443 | * Performs a lookup in the hash table, preserving extra information |
444 | * usually needed for insertion. |
445 | * |
446 | * This function first computes the hash value of the key using the |
447 | * user's hash function. |
448 | * |
449 | * If an entry in the table matching @key is found then this function |
450 | * returns the index of that entry in the table, and if not, the |
451 | * index of an unused node (empty or tombstone) where the key can be |
452 | * inserted. |
453 | * |
454 | * The computed hash value is returned in the variable pointed to |
455 | * by @hash_return. This is to save insertions from having to compute |
456 | * the hash record again for the new record. |
457 | * |
458 | * Returns: index of the described node |
459 | */ |
460 | static inline guint |
461 | g_hash_table_lookup_node (GHashTable *hash_table, |
462 | gconstpointer key, |
463 | guint *hash_return) |
464 | { |
465 | guint node_index; |
466 | guint node_hash; |
467 | guint hash_value; |
468 | guint first_tombstone = 0; |
469 | gboolean have_tombstone = FALSE; |
470 | guint step = 0; |
471 | |
472 | hash_value = hash_table->hash_func (key); |
473 | if (G_UNLIKELY (!HASH_IS_REAL (hash_value))) |
474 | hash_value = 2; |
475 | |
476 | *hash_return = hash_value; |
477 | |
478 | node_index = g_hash_table_hash_to_index (hash_table, hash: hash_value); |
479 | node_hash = hash_table->hashes[node_index]; |
480 | |
481 | while (!HASH_IS_UNUSED (node_hash)) |
482 | { |
483 | /* We first check if our full hash values |
484 | * are equal so we can avoid calling the full-blown |
485 | * key equality function in most cases. |
486 | */ |
487 | if (node_hash == hash_value) |
488 | { |
489 | gpointer node_key = g_hash_table_fetch_key_or_value (a: hash_table->keys, index: node_index, is_big: hash_table->have_big_keys); |
490 | |
491 | if (hash_table->key_equal_func) |
492 | { |
493 | if (hash_table->key_equal_func (node_key, key)) |
494 | return node_index; |
495 | } |
496 | else if (node_key == key) |
497 | { |
498 | return node_index; |
499 | } |
500 | } |
501 | else if (HASH_IS_TOMBSTONE (node_hash) && !have_tombstone) |
502 | { |
503 | first_tombstone = node_index; |
504 | have_tombstone = TRUE; |
505 | } |
506 | |
507 | step++; |
508 | node_index += step; |
509 | node_index &= hash_table->mask; |
510 | node_hash = hash_table->hashes[node_index]; |
511 | } |
512 | |
513 | if (have_tombstone) |
514 | return first_tombstone; |
515 | |
516 | return node_index; |
517 | } |
518 | |
519 | /* |
520 | * g_hash_table_remove_node: |
521 | * @hash_table: our #GHashTable |
522 | * @node: pointer to node to remove |
523 | * @notify: %TRUE if the destroy notify handlers are to be called |
524 | * |
525 | * Removes a node from the hash table and updates the node count. |
526 | * The node is replaced by a tombstone. No table resize is performed. |
527 | * |
528 | * If @notify is %TRUE then the destroy notify functions are called |
529 | * for the key and value of the hash node. |
530 | */ |
531 | static void |
532 | g_hash_table_remove_node (GHashTable *hash_table, |
533 | gint i, |
534 | gboolean notify) |
535 | { |
536 | gpointer key; |
537 | gpointer value; |
538 | |
539 | key = g_hash_table_fetch_key_or_value (a: hash_table->keys, index: i, is_big: hash_table->have_big_keys); |
540 | value = g_hash_table_fetch_key_or_value (a: hash_table->values, index: i, is_big: hash_table->have_big_values); |
541 | |
542 | /* Erect tombstone */ |
543 | hash_table->hashes[i] = TOMBSTONE_HASH_VALUE; |
544 | |
545 | /* Be GC friendly */ |
546 | g_hash_table_assign_key_or_value (a: hash_table->keys, index: i, is_big: hash_table->have_big_keys, NULL); |
547 | g_hash_table_assign_key_or_value (a: hash_table->values, index: i, is_big: hash_table->have_big_values, NULL); |
548 | |
549 | hash_table->nnodes--; |
550 | |
551 | if (notify && hash_table->key_destroy_func) |
552 | hash_table->key_destroy_func (key); |
553 | |
554 | if (notify && hash_table->value_destroy_func) |
555 | hash_table->value_destroy_func (value); |
556 | |
557 | } |
558 | |
559 | /* |
560 | * g_hash_table_setup_storage: |
561 | * @hash_table: our #GHashTable |
562 | * |
563 | * Initialise the hash table size, mask, mod, and arrays. |
564 | */ |
565 | static void |
566 | g_hash_table_setup_storage (GHashTable *hash_table) |
567 | { |
568 | gboolean small = FALSE; |
569 | |
570 | /* We want to use small arrays only if: |
571 | * - we are running on a system where that makes sense (64 bit); and |
572 | * - we are not running under valgrind. |
573 | */ |
574 | |
575 | #ifdef USE_SMALL_ARRAYS |
576 | small = TRUE; |
577 | |
578 | # ifdef ENABLE_VALGRIND |
579 | if (RUNNING_ON_VALGRIND) |
580 | small = FALSE; |
581 | # endif |
582 | #endif |
583 | |
584 | g_hash_table_set_shift (hash_table, HASH_TABLE_MIN_SHIFT); |
585 | |
586 | hash_table->have_big_keys = !small; |
587 | hash_table->have_big_values = !small; |
588 | |
589 | hash_table->keys = g_hash_table_realloc_key_or_value_array (NULL, size: hash_table->size, is_big: hash_table->have_big_keys); |
590 | hash_table->values = hash_table->keys; |
591 | hash_table->hashes = g_new0 (guint, hash_table->size); |
592 | } |
593 | |
594 | /* |
595 | * g_hash_table_remove_all_nodes: |
596 | * @hash_table: our #GHashTable |
597 | * @notify: %TRUE if the destroy notify handlers are to be called |
598 | * |
599 | * Removes all nodes from the table. |
600 | * |
601 | * If @notify is %TRUE then the destroy notify functions are called |
602 | * for the key and value of the hash node. |
603 | * |
604 | * Since this may be a precursor to freeing the table entirely, we'd |
605 | * ideally perform no resize, and we can indeed avoid that in some |
606 | * cases. However: in the case that we'll be making callbacks to user |
607 | * code (via destroy notifies) we need to consider that the user code |
608 | * might call back into the table again. In this case, we setup a new |
609 | * set of arrays so that any callers will see an empty (but valid) |
610 | * table. |
611 | */ |
612 | static void |
613 | g_hash_table_remove_all_nodes (GHashTable *hash_table, |
614 | gboolean notify, |
615 | gboolean destruction) |
616 | { |
617 | int i; |
618 | gpointer key; |
619 | gpointer value; |
620 | gint old_size; |
621 | gpointer *old_keys; |
622 | gpointer *old_values; |
623 | guint *old_hashes; |
624 | gboolean old_have_big_keys; |
625 | gboolean old_have_big_values; |
626 | |
627 | /* If the hash table is already empty, there is nothing to be done. */ |
628 | if (hash_table->nnodes == 0) |
629 | return; |
630 | |
631 | hash_table->nnodes = 0; |
632 | hash_table->noccupied = 0; |
633 | |
634 | /* Easy case: no callbacks, so we just zero out the arrays */ |
635 | if (!notify || |
636 | (hash_table->key_destroy_func == NULL && |
637 | hash_table->value_destroy_func == NULL)) |
638 | { |
639 | if (!destruction) |
640 | { |
641 | memset (s: hash_table->hashes, c: 0, n: hash_table->size * sizeof (guint)); |
642 | |
643 | #ifdef USE_SMALL_ARRAYS |
644 | memset (s: hash_table->keys, c: 0, n: hash_table->size * (hash_table->have_big_keys ? BIG_ENTRY_SIZE : SMALL_ENTRY_SIZE)); |
645 | memset (s: hash_table->values, c: 0, n: hash_table->size * (hash_table->have_big_values ? BIG_ENTRY_SIZE : SMALL_ENTRY_SIZE)); |
646 | #else |
647 | memset (hash_table->keys, 0, hash_table->size * sizeof (gpointer)); |
648 | memset (hash_table->values, 0, hash_table->size * sizeof (gpointer)); |
649 | #endif |
650 | } |
651 | |
652 | return; |
653 | } |
654 | |
655 | /* Hard case: we need to do user callbacks. There are two |
656 | * possibilities here: |
657 | * |
658 | * 1) there are no outstanding references on the table and therefore |
659 | * nobody should be calling into it again (destroying == true) |
660 | * |
661 | * 2) there are outstanding references, and there may be future |
662 | * calls into the table, either after we return, or from the destroy |
663 | * notifies that we're about to do (destroying == false) |
664 | * |
665 | * We handle both cases by taking the current state of the table into |
666 | * local variables and replacing it with something else: in the "no |
667 | * outstanding references" cases we replace it with a bunch of |
668 | * null/zero values so that any access to the table will fail. In the |
669 | * "may receive future calls" case, we reinitialise the struct to |
670 | * appear like a newly-created empty table. |
671 | * |
672 | * In both cases, we take over the references for the current state, |
673 | * freeing them below. |
674 | */ |
675 | old_size = hash_table->size; |
676 | old_have_big_keys = hash_table->have_big_keys; |
677 | old_have_big_values = hash_table->have_big_values; |
678 | old_keys = g_steal_pointer (&hash_table->keys); |
679 | old_values = g_steal_pointer (&hash_table->values); |
680 | old_hashes = g_steal_pointer (&hash_table->hashes); |
681 | |
682 | if (!destruction) |
683 | /* Any accesses will see an empty table */ |
684 | g_hash_table_setup_storage (hash_table); |
685 | else |
686 | /* Will cause a quick crash on any attempted access */ |
687 | hash_table->size = hash_table->mod = hash_table->mask = 0; |
688 | |
689 | /* Now do the actual destroy notifies */ |
690 | for (i = 0; i < old_size; i++) |
691 | { |
692 | if (HASH_IS_REAL (old_hashes[i])) |
693 | { |
694 | key = g_hash_table_fetch_key_or_value (a: old_keys, index: i, is_big: old_have_big_keys); |
695 | value = g_hash_table_fetch_key_or_value (a: old_values, index: i, is_big: old_have_big_values); |
696 | |
697 | old_hashes[i] = UNUSED_HASH_VALUE; |
698 | |
699 | g_hash_table_assign_key_or_value (a: old_keys, index: i, is_big: old_have_big_keys, NULL); |
700 | g_hash_table_assign_key_or_value (a: old_values, index: i, is_big: old_have_big_values, NULL); |
701 | |
702 | if (hash_table->key_destroy_func != NULL) |
703 | hash_table->key_destroy_func (key); |
704 | |
705 | if (hash_table->value_destroy_func != NULL) |
706 | hash_table->value_destroy_func (value); |
707 | } |
708 | } |
709 | |
710 | /* Destroy old storage space. */ |
711 | if (old_keys != old_values) |
712 | g_free (mem: old_values); |
713 | |
714 | g_free (mem: old_keys); |
715 | g_free (mem: old_hashes); |
716 | } |
717 | |
718 | static void |
719 | realloc_arrays (GHashTable *hash_table, gboolean is_a_set) |
720 | { |
721 | hash_table->hashes = g_renew (guint, hash_table->hashes, hash_table->size); |
722 | hash_table->keys = g_hash_table_realloc_key_or_value_array (a: hash_table->keys, size: hash_table->size, is_big: hash_table->have_big_keys); |
723 | |
724 | if (is_a_set) |
725 | hash_table->values = hash_table->keys; |
726 | else |
727 | hash_table->values = g_hash_table_realloc_key_or_value_array (a: hash_table->values, size: hash_table->size, is_big: hash_table->have_big_values); |
728 | } |
729 | |
730 | /* When resizing the table in place, we use a temporary bit array to keep |
731 | * track of which entries have been assigned a proper location in the new |
732 | * table layout. |
733 | * |
734 | * Each bit corresponds to a bucket. A bit is set if an entry was assigned |
735 | * its corresponding location during the resize and thus should not be |
736 | * evicted. The array starts out cleared to zero. */ |
737 | |
738 | static inline gboolean |
739 | get_status_bit (const guint32 *bitmap, guint index) |
740 | { |
741 | return (bitmap[index / 32] >> (index % 32)) & 1; |
742 | } |
743 | |
744 | static inline void |
745 | set_status_bit (guint32 *bitmap, guint index) |
746 | { |
747 | bitmap[index / 32] |= 1U << (index % 32); |
748 | } |
749 | |
750 | /* By calling dedicated resize functions for sets and maps, we avoid 2x |
751 | * test-and-branch per key in the inner loop. This yields a small |
752 | * performance improvement at the cost of a bit of macro gunk. */ |
753 | |
754 | #define DEFINE_RESIZE_FUNC(fname) \ |
755 | static void fname (GHashTable *hash_table, guint old_size, guint32 *reallocated_buckets_bitmap) \ |
756 | { \ |
757 | guint i; \ |
758 | \ |
759 | for (i = 0; i < old_size; i++) \ |
760 | { \ |
761 | guint node_hash = hash_table->hashes[i]; \ |
762 | gpointer key, value G_GNUC_UNUSED; \ |
763 | \ |
764 | if (!HASH_IS_REAL (node_hash)) \ |
765 | { \ |
766 | /* Clear tombstones */ \ |
767 | hash_table->hashes[i] = UNUSED_HASH_VALUE; \ |
768 | continue; \ |
769 | } \ |
770 | \ |
771 | /* Skip entries relocated through eviction */ \ |
772 | if (get_status_bit (reallocated_buckets_bitmap, i)) \ |
773 | continue; \ |
774 | \ |
775 | hash_table->hashes[i] = UNUSED_HASH_VALUE; \ |
776 | EVICT_KEYVAL (hash_table, i, NULL, NULL, key, value); \ |
777 | \ |
778 | for (;;) \ |
779 | { \ |
780 | guint hash_val; \ |
781 | guint replaced_hash; \ |
782 | guint step = 0; \ |
783 | \ |
784 | hash_val = g_hash_table_hash_to_index (hash_table, node_hash); \ |
785 | \ |
786 | while (get_status_bit (reallocated_buckets_bitmap, hash_val)) \ |
787 | { \ |
788 | step++; \ |
789 | hash_val += step; \ |
790 | hash_val &= hash_table->mask; \ |
791 | } \ |
792 | \ |
793 | set_status_bit (reallocated_buckets_bitmap, hash_val); \ |
794 | \ |
795 | replaced_hash = hash_table->hashes[hash_val]; \ |
796 | hash_table->hashes[hash_val] = node_hash; \ |
797 | if (!HASH_IS_REAL (replaced_hash)) \ |
798 | { \ |
799 | ASSIGN_KEYVAL (hash_table, hash_val, key, value); \ |
800 | break; \ |
801 | } \ |
802 | \ |
803 | node_hash = replaced_hash; \ |
804 | EVICT_KEYVAL (hash_table, hash_val, key, value, key, value); \ |
805 | } \ |
806 | } \ |
807 | } |
808 | |
809 | #define ASSIGN_KEYVAL(ht, index, key, value) G_STMT_START{ \ |
810 | g_hash_table_assign_key_or_value ((ht)->keys, (index), (ht)->have_big_keys, (key)); \ |
811 | g_hash_table_assign_key_or_value ((ht)->values, (index), (ht)->have_big_values, (value)); \ |
812 | }G_STMT_END |
813 | |
814 | #define EVICT_KEYVAL(ht, index, key, value, outkey, outvalue) G_STMT_START{ \ |
815 | (outkey) = g_hash_table_evict_key_or_value ((ht)->keys, (index), (ht)->have_big_keys, (key)); \ |
816 | (outvalue) = g_hash_table_evict_key_or_value ((ht)->values, (index), (ht)->have_big_values, (value)); \ |
817 | }G_STMT_END |
818 | |
819 | DEFINE_RESIZE_FUNC (resize_map) |
820 | |
821 | #undef ASSIGN_KEYVAL |
822 | #undef EVICT_KEYVAL |
823 | |
824 | #define ASSIGN_KEYVAL(ht, index, key, value) G_STMT_START{ \ |
825 | g_hash_table_assign_key_or_value ((ht)->keys, (index), (ht)->have_big_keys, (key)); \ |
826 | }G_STMT_END |
827 | |
828 | #define EVICT_KEYVAL(ht, index, key, value, outkey, outvalue) G_STMT_START{ \ |
829 | (outkey) = g_hash_table_evict_key_or_value ((ht)->keys, (index), (ht)->have_big_keys, (key)); \ |
830 | }G_STMT_END |
831 | |
832 | DEFINE_RESIZE_FUNC (resize_set) |
833 | |
834 | #undef ASSIGN_KEYVAL |
835 | #undef EVICT_KEYVAL |
836 | |
837 | /* |
838 | * g_hash_table_resize: |
839 | * @hash_table: our #GHashTable |
840 | * |
841 | * Resizes the hash table to the optimal size based on the number of |
842 | * nodes currently held. If you call this function then a resize will |
843 | * occur, even if one does not need to occur. |
844 | * Use g_hash_table_maybe_resize() instead. |
845 | * |
846 | * This function may "resize" the hash table to its current size, with |
847 | * the side effect of cleaning up tombstones and otherwise optimizing |
848 | * the probe sequences. |
849 | */ |
850 | static void |
851 | g_hash_table_resize (GHashTable *hash_table) |
852 | { |
853 | guint32 *reallocated_buckets_bitmap; |
854 | gsize old_size; |
855 | gboolean is_a_set; |
856 | |
857 | old_size = hash_table->size; |
858 | is_a_set = hash_table->keys == hash_table->values; |
859 | |
860 | /* The outer checks in g_hash_table_maybe_resize() will only consider |
861 | * cleanup/resize when the load factor goes below .25 (1/4, ignoring |
862 | * tombstones) or above .9375 (15/16, including tombstones). |
863 | * |
864 | * Once this happens, tombstones will always be cleaned out. If our |
865 | * load sans tombstones is greater than .75 (1/1.333, see below), we'll |
866 | * take this opportunity to grow the table too. |
867 | * |
868 | * Immediately after growing, the load factor will be in the range |
869 | * .375 .. .469. After shrinking, it will be exactly .5. */ |
870 | |
871 | g_hash_table_set_shift_from_size (hash_table, size: hash_table->nnodes * 1.333); |
872 | |
873 | if (hash_table->size > old_size) |
874 | { |
875 | realloc_arrays (hash_table, is_a_set); |
876 | memset (s: &hash_table->hashes[old_size], c: 0, n: (hash_table->size - old_size) * sizeof (guint)); |
877 | |
878 | reallocated_buckets_bitmap = g_new0 (guint32, (hash_table->size + 31) / 32); |
879 | } |
880 | else |
881 | { |
882 | reallocated_buckets_bitmap = g_new0 (guint32, (old_size + 31) / 32); |
883 | } |
884 | |
885 | if (is_a_set) |
886 | resize_set (hash_table, old_size, reallocated_buckets_bitmap); |
887 | else |
888 | resize_map (hash_table, old_size, reallocated_buckets_bitmap); |
889 | |
890 | g_free (mem: reallocated_buckets_bitmap); |
891 | |
892 | if (hash_table->size < old_size) |
893 | realloc_arrays (hash_table, is_a_set); |
894 | |
895 | hash_table->noccupied = hash_table->nnodes; |
896 | } |
897 | |
898 | /* |
899 | * g_hash_table_maybe_resize: |
900 | * @hash_table: our #GHashTable |
901 | * |
902 | * Resizes the hash table, if needed. |
903 | * |
904 | * Essentially, calls g_hash_table_resize() if the table has strayed |
905 | * too far from its ideal size for its number of nodes. |
906 | */ |
907 | static inline void |
908 | g_hash_table_maybe_resize (GHashTable *hash_table) |
909 | { |
910 | gint noccupied = hash_table->noccupied; |
911 | gint size = hash_table->size; |
912 | |
913 | if ((size > hash_table->nnodes * 4 && size > 1 << HASH_TABLE_MIN_SHIFT) || |
914 | (size <= noccupied + (noccupied / 16))) |
915 | g_hash_table_resize (hash_table); |
916 | } |
917 | |
918 | #ifdef USE_SMALL_ARRAYS |
919 | |
920 | static inline gboolean |
921 | entry_is_big (gpointer v) |
922 | { |
923 | return (((guintptr) v) >> ((BIG_ENTRY_SIZE - SMALL_ENTRY_SIZE) * 8)) != 0; |
924 | } |
925 | |
926 | static inline gboolean |
927 | g_hash_table_maybe_make_big_keys_or_values (gpointer *a_p, gpointer v, gint ht_size) |
928 | { |
929 | if (entry_is_big (v)) |
930 | { |
931 | guint *a = (guint *) *a_p; |
932 | gpointer *a_new; |
933 | gint i; |
934 | |
935 | a_new = g_new (gpointer, ht_size); |
936 | |
937 | for (i = 0; i < ht_size; i++) |
938 | { |
939 | a_new[i] = GUINT_TO_POINTER (a[i]); |
940 | } |
941 | |
942 | g_free (mem: a); |
943 | *a_p = a_new; |
944 | return TRUE; |
945 | } |
946 | |
947 | return FALSE; |
948 | } |
949 | |
950 | #endif |
951 | |
952 | static inline void |
953 | g_hash_table_ensure_keyval_fits (GHashTable *hash_table, gpointer key, gpointer value) |
954 | { |
955 | gboolean is_a_set = (hash_table->keys == hash_table->values); |
956 | |
957 | #ifdef USE_SMALL_ARRAYS |
958 | |
959 | /* Convert from set to map? */ |
960 | if (is_a_set) |
961 | { |
962 | if (hash_table->have_big_keys) |
963 | { |
964 | if (key != value) |
965 | hash_table->values = g_memdup2 (mem: hash_table->keys, byte_size: sizeof (gpointer) * hash_table->size); |
966 | /* Keys and values are both big now, so no need for further checks */ |
967 | return; |
968 | } |
969 | else |
970 | { |
971 | if (key != value) |
972 | { |
973 | hash_table->values = g_memdup2 (mem: hash_table->keys, byte_size: sizeof (guint) * hash_table->size); |
974 | is_a_set = FALSE; |
975 | } |
976 | } |
977 | } |
978 | |
979 | /* Make keys big? */ |
980 | if (!hash_table->have_big_keys) |
981 | { |
982 | hash_table->have_big_keys = g_hash_table_maybe_make_big_keys_or_values (a_p: &hash_table->keys, v: key, ht_size: hash_table->size); |
983 | |
984 | if (is_a_set) |
985 | { |
986 | hash_table->values = hash_table->keys; |
987 | hash_table->have_big_values = hash_table->have_big_keys; |
988 | } |
989 | } |
990 | |
991 | /* Make values big? */ |
992 | if (!is_a_set && !hash_table->have_big_values) |
993 | { |
994 | hash_table->have_big_values = g_hash_table_maybe_make_big_keys_or_values (a_p: &hash_table->values, v: value, ht_size: hash_table->size); |
995 | } |
996 | |
997 | #else |
998 | |
999 | /* Just split if necessary */ |
1000 | if (is_a_set && key != value) |
1001 | hash_table->values = g_memdup2 (hash_table->keys, sizeof (gpointer) * hash_table->size); |
1002 | |
1003 | #endif |
1004 | } |
1005 | |
1006 | /** |
1007 | * g_hash_table_new: |
1008 | * @hash_func: a function to create a hash value from a key |
1009 | * @key_equal_func: a function to check two keys for equality |
1010 | * |
1011 | * Creates a new #GHashTable with a reference count of 1. |
1012 | * |
1013 | * Hash values returned by @hash_func are used to determine where keys |
1014 | * are stored within the #GHashTable data structure. The g_direct_hash(), |
1015 | * g_int_hash(), g_int64_hash(), g_double_hash() and g_str_hash() |
1016 | * functions are provided for some common types of keys. |
1017 | * If @hash_func is %NULL, g_direct_hash() is used. |
1018 | * |
1019 | * @key_equal_func is used when looking up keys in the #GHashTable. |
1020 | * The g_direct_equal(), g_int_equal(), g_int64_equal(), g_double_equal() |
1021 | * and g_str_equal() functions are provided for the most common types |
1022 | * of keys. If @key_equal_func is %NULL, keys are compared directly in |
1023 | * a similar fashion to g_direct_equal(), but without the overhead of |
1024 | * a function call. @key_equal_func is called with the key from the hash table |
1025 | * as its first parameter, and the user-provided key to check against as |
1026 | * its second. |
1027 | * |
1028 | * Returns: a new #GHashTable |
1029 | */ |
1030 | GHashTable * |
1031 | g_hash_table_new (GHashFunc hash_func, |
1032 | GEqualFunc key_equal_func) |
1033 | { |
1034 | return g_hash_table_new_full (hash_func, key_equal_func, NULL, NULL); |
1035 | } |
1036 | |
1037 | |
1038 | /** |
1039 | * g_hash_table_new_full: |
1040 | * @hash_func: a function to create a hash value from a key |
1041 | * @key_equal_func: a function to check two keys for equality |
1042 | * @key_destroy_func: (nullable): a function to free the memory allocated for the key |
1043 | * used when removing the entry from the #GHashTable, or %NULL |
1044 | * if you don't want to supply such a function. |
1045 | * @value_destroy_func: (nullable): a function to free the memory allocated for the |
1046 | * value used when removing the entry from the #GHashTable, or %NULL |
1047 | * if you don't want to supply such a function. |
1048 | * |
1049 | * Creates a new #GHashTable like g_hash_table_new() with a reference |
1050 | * count of 1 and allows to specify functions to free the memory |
1051 | * allocated for the key and value that get called when removing the |
1052 | * entry from the #GHashTable. |
1053 | * |
1054 | * Since version 2.42 it is permissible for destroy notify functions to |
1055 | * recursively remove further items from the hash table. This is only |
1056 | * permissible if the application still holds a reference to the hash table. |
1057 | * This means that you may need to ensure that the hash table is empty by |
1058 | * calling g_hash_table_remove_all() before releasing the last reference using |
1059 | * g_hash_table_unref(). |
1060 | * |
1061 | * Returns: a new #GHashTable |
1062 | */ |
1063 | GHashTable * |
1064 | g_hash_table_new_full (GHashFunc hash_func, |
1065 | GEqualFunc key_equal_func, |
1066 | GDestroyNotify key_destroy_func, |
1067 | GDestroyNotify value_destroy_func) |
1068 | { |
1069 | GHashTable *hash_table; |
1070 | |
1071 | hash_table = g_slice_new (GHashTable); |
1072 | g_atomic_ref_count_init (arc: &hash_table->ref_count); |
1073 | hash_table->nnodes = 0; |
1074 | hash_table->noccupied = 0; |
1075 | hash_table->hash_func = hash_func ? hash_func : g_direct_hash; |
1076 | hash_table->key_equal_func = key_equal_func; |
1077 | #ifndef G_DISABLE_ASSERT |
1078 | hash_table->version = 0; |
1079 | #endif |
1080 | hash_table->key_destroy_func = key_destroy_func; |
1081 | hash_table->value_destroy_func = value_destroy_func; |
1082 | |
1083 | g_hash_table_setup_storage (hash_table); |
1084 | |
1085 | return hash_table; |
1086 | } |
1087 | |
1088 | /** |
1089 | * g_hash_table_iter_init: |
1090 | * @iter: an uninitialized #GHashTableIter |
1091 | * @hash_table: a #GHashTable |
1092 | * |
1093 | * Initializes a key/value pair iterator and associates it with |
1094 | * @hash_table. Modifying the hash table after calling this function |
1095 | * invalidates the returned iterator. |
1096 | * |
1097 | * The iteration order of a #GHashTableIter over the keys/values in a hash |
1098 | * table is not defined. |
1099 | * |
1100 | * |[<!-- language="C" --> |
1101 | * GHashTableIter iter; |
1102 | * gpointer key, value; |
1103 | * |
1104 | * g_hash_table_iter_init (&iter, hash_table); |
1105 | * while (g_hash_table_iter_next (&iter, &key, &value)) |
1106 | * { |
1107 | * // do something with key and value |
1108 | * } |
1109 | * ]| |
1110 | * |
1111 | * Since: 2.16 |
1112 | */ |
1113 | void |
1114 | g_hash_table_iter_init (GHashTableIter *iter, |
1115 | GHashTable *hash_table) |
1116 | { |
1117 | RealIter *ri = (RealIter *) iter; |
1118 | |
1119 | g_return_if_fail (iter != NULL); |
1120 | g_return_if_fail (hash_table != NULL); |
1121 | |
1122 | ri->hash_table = hash_table; |
1123 | ri->position = -1; |
1124 | #ifndef G_DISABLE_ASSERT |
1125 | ri->version = hash_table->version; |
1126 | #endif |
1127 | } |
1128 | |
1129 | /** |
1130 | * g_hash_table_iter_next: |
1131 | * @iter: an initialized #GHashTableIter |
1132 | * @key: (out) (optional): a location to store the key |
1133 | * @value: (out) (optional) (nullable): a location to store the value |
1134 | * |
1135 | * Advances @iter and retrieves the key and/or value that are now |
1136 | * pointed to as a result of this advancement. If %FALSE is returned, |
1137 | * @key and @value are not set, and the iterator becomes invalid. |
1138 | * |
1139 | * Returns: %FALSE if the end of the #GHashTable has been reached. |
1140 | * |
1141 | * Since: 2.16 |
1142 | */ |
1143 | gboolean |
1144 | g_hash_table_iter_next (GHashTableIter *iter, |
1145 | gpointer *key, |
1146 | gpointer *value) |
1147 | { |
1148 | RealIter *ri = (RealIter *) iter; |
1149 | gint position; |
1150 | |
1151 | g_return_val_if_fail (iter != NULL, FALSE); |
1152 | #ifndef G_DISABLE_ASSERT |
1153 | g_return_val_if_fail (ri->version == ri->hash_table->version, FALSE); |
1154 | #endif |
1155 | g_return_val_if_fail (ri->position < (gssize) ri->hash_table->size, FALSE); |
1156 | |
1157 | position = ri->position; |
1158 | |
1159 | do |
1160 | { |
1161 | position++; |
1162 | if (position >= (gssize) ri->hash_table->size) |
1163 | { |
1164 | ri->position = position; |
1165 | return FALSE; |
1166 | } |
1167 | } |
1168 | while (!HASH_IS_REAL (ri->hash_table->hashes[position])); |
1169 | |
1170 | if (key != NULL) |
1171 | *key = g_hash_table_fetch_key_or_value (a: ri->hash_table->keys, index: position, is_big: ri->hash_table->have_big_keys); |
1172 | if (value != NULL) |
1173 | *value = g_hash_table_fetch_key_or_value (a: ri->hash_table->values, index: position, is_big: ri->hash_table->have_big_values); |
1174 | |
1175 | ri->position = position; |
1176 | return TRUE; |
1177 | } |
1178 | |
1179 | /** |
1180 | * g_hash_table_iter_get_hash_table: |
1181 | * @iter: an initialized #GHashTableIter |
1182 | * |
1183 | * Returns the #GHashTable associated with @iter. |
1184 | * |
1185 | * Returns: the #GHashTable associated with @iter. |
1186 | * |
1187 | * Since: 2.16 |
1188 | */ |
1189 | GHashTable * |
1190 | g_hash_table_iter_get_hash_table (GHashTableIter *iter) |
1191 | { |
1192 | g_return_val_if_fail (iter != NULL, NULL); |
1193 | |
1194 | return ((RealIter *) iter)->hash_table; |
1195 | } |
1196 | |
1197 | static void |
1198 | iter_remove_or_steal (RealIter *ri, gboolean notify) |
1199 | { |
1200 | g_return_if_fail (ri != NULL); |
1201 | #ifndef G_DISABLE_ASSERT |
1202 | g_return_if_fail (ri->version == ri->hash_table->version); |
1203 | #endif |
1204 | g_return_if_fail (ri->position >= 0); |
1205 | g_return_if_fail ((gsize) ri->position < ri->hash_table->size); |
1206 | |
1207 | g_hash_table_remove_node (hash_table: ri->hash_table, i: ri->position, notify); |
1208 | |
1209 | #ifndef G_DISABLE_ASSERT |
1210 | ri->version++; |
1211 | ri->hash_table->version++; |
1212 | #endif |
1213 | } |
1214 | |
1215 | /** |
1216 | * g_hash_table_iter_remove: |
1217 | * @iter: an initialized #GHashTableIter |
1218 | * |
1219 | * Removes the key/value pair currently pointed to by the iterator |
1220 | * from its associated #GHashTable. Can only be called after |
1221 | * g_hash_table_iter_next() returned %TRUE, and cannot be called |
1222 | * more than once for the same key/value pair. |
1223 | * |
1224 | * If the #GHashTable was created using g_hash_table_new_full(), |
1225 | * the key and value are freed using the supplied destroy functions, |
1226 | * otherwise you have to make sure that any dynamically allocated |
1227 | * values are freed yourself. |
1228 | * |
1229 | * It is safe to continue iterating the #GHashTable afterward: |
1230 | * |[<!-- language="C" --> |
1231 | * while (g_hash_table_iter_next (&iter, &key, &value)) |
1232 | * { |
1233 | * if (condition) |
1234 | * g_hash_table_iter_remove (&iter); |
1235 | * } |
1236 | * ]| |
1237 | * |
1238 | * Since: 2.16 |
1239 | */ |
1240 | void |
1241 | g_hash_table_iter_remove (GHashTableIter *iter) |
1242 | { |
1243 | iter_remove_or_steal (ri: (RealIter *) iter, TRUE); |
1244 | } |
1245 | |
1246 | /* |
1247 | * g_hash_table_insert_node: |
1248 | * @hash_table: our #GHashTable |
1249 | * @node_index: pointer to node to insert/replace |
1250 | * @key_hash: key hash |
1251 | * @key: (nullable): key to replace with, or %NULL |
1252 | * @value: value to replace with |
1253 | * @keep_new_key: whether to replace the key in the node with @key |
1254 | * @reusing_key: whether @key was taken out of the existing node |
1255 | * |
1256 | * Inserts a value at @node_index in the hash table and updates it. |
1257 | * |
1258 | * If @key has been taken out of the existing node (ie it is not |
1259 | * passed in via a g_hash_table_insert/replace) call, then @reusing_key |
1260 | * should be %TRUE. |
1261 | * |
1262 | * Returns: %TRUE if the key did not exist yet |
1263 | */ |
1264 | static gboolean |
1265 | g_hash_table_insert_node (GHashTable *hash_table, |
1266 | guint node_index, |
1267 | guint key_hash, |
1268 | gpointer new_key, |
1269 | gpointer new_value, |
1270 | gboolean keep_new_key, |
1271 | gboolean reusing_key) |
1272 | { |
1273 | gboolean already_exists; |
1274 | guint old_hash; |
1275 | gpointer key_to_free = NULL; |
1276 | gpointer key_to_keep = NULL; |
1277 | gpointer value_to_free = NULL; |
1278 | |
1279 | old_hash = hash_table->hashes[node_index]; |
1280 | already_exists = HASH_IS_REAL (old_hash); |
1281 | |
1282 | /* Proceed in three steps. First, deal with the key because it is the |
1283 | * most complicated. Then consider if we need to split the table in |
1284 | * two (because writing the value will result in the set invariant |
1285 | * becoming broken). Then deal with the value. |
1286 | * |
1287 | * There are three cases for the key: |
1288 | * |
1289 | * - entry already exists in table, reusing key: |
1290 | * free the just-passed-in new_key and use the existing value |
1291 | * |
1292 | * - entry already exists in table, not reusing key: |
1293 | * free the entry in the table, use the new key |
1294 | * |
1295 | * - entry not already in table: |
1296 | * use the new key, free nothing |
1297 | * |
1298 | * We update the hash at the same time... |
1299 | */ |
1300 | if (already_exists) |
1301 | { |
1302 | /* Note: we must record the old value before writing the new key |
1303 | * because we might change the value in the event that the two |
1304 | * arrays are shared. |
1305 | */ |
1306 | value_to_free = g_hash_table_fetch_key_or_value (a: hash_table->values, index: node_index, is_big: hash_table->have_big_values); |
1307 | |
1308 | if (keep_new_key) |
1309 | { |
1310 | key_to_free = g_hash_table_fetch_key_or_value (a: hash_table->keys, index: node_index, is_big: hash_table->have_big_keys); |
1311 | key_to_keep = new_key; |
1312 | } |
1313 | else |
1314 | { |
1315 | key_to_free = new_key; |
1316 | key_to_keep = g_hash_table_fetch_key_or_value (a: hash_table->keys, index: node_index, is_big: hash_table->have_big_keys); |
1317 | } |
1318 | } |
1319 | else |
1320 | { |
1321 | hash_table->hashes[node_index] = key_hash; |
1322 | key_to_keep = new_key; |
1323 | } |
1324 | |
1325 | /* Resize key/value arrays and split table as necessary */ |
1326 | g_hash_table_ensure_keyval_fits (hash_table, key: key_to_keep, value: new_value); |
1327 | g_hash_table_assign_key_or_value (a: hash_table->keys, index: node_index, is_big: hash_table->have_big_keys, v: key_to_keep); |
1328 | |
1329 | /* Step 3: Actually do the write */ |
1330 | g_hash_table_assign_key_or_value (a: hash_table->values, index: node_index, is_big: hash_table->have_big_values, v: new_value); |
1331 | |
1332 | /* Now, the bookkeeping... */ |
1333 | if (!already_exists) |
1334 | { |
1335 | hash_table->nnodes++; |
1336 | |
1337 | if (HASH_IS_UNUSED (old_hash)) |
1338 | { |
1339 | /* We replaced an empty node, and not a tombstone */ |
1340 | hash_table->noccupied++; |
1341 | g_hash_table_maybe_resize (hash_table); |
1342 | } |
1343 | |
1344 | #ifndef G_DISABLE_ASSERT |
1345 | hash_table->version++; |
1346 | #endif |
1347 | } |
1348 | |
1349 | if (already_exists) |
1350 | { |
1351 | if (hash_table->key_destroy_func && !reusing_key) |
1352 | (* hash_table->key_destroy_func) (key_to_free); |
1353 | if (hash_table->value_destroy_func) |
1354 | (* hash_table->value_destroy_func) (value_to_free); |
1355 | } |
1356 | |
1357 | return !already_exists; |
1358 | } |
1359 | |
1360 | /** |
1361 | * g_hash_table_iter_replace: |
1362 | * @iter: an initialized #GHashTableIter |
1363 | * @value: the value to replace with |
1364 | * |
1365 | * Replaces the value currently pointed to by the iterator |
1366 | * from its associated #GHashTable. Can only be called after |
1367 | * g_hash_table_iter_next() returned %TRUE. |
1368 | * |
1369 | * If you supplied a @value_destroy_func when creating the |
1370 | * #GHashTable, the old value is freed using that function. |
1371 | * |
1372 | * Since: 2.30 |
1373 | */ |
1374 | void |
1375 | g_hash_table_iter_replace (GHashTableIter *iter, |
1376 | gpointer value) |
1377 | { |
1378 | RealIter *ri; |
1379 | guint node_hash; |
1380 | gpointer key; |
1381 | |
1382 | ri = (RealIter *) iter; |
1383 | |
1384 | g_return_if_fail (ri != NULL); |
1385 | #ifndef G_DISABLE_ASSERT |
1386 | g_return_if_fail (ri->version == ri->hash_table->version); |
1387 | #endif |
1388 | g_return_if_fail (ri->position >= 0); |
1389 | g_return_if_fail ((gsize) ri->position < ri->hash_table->size); |
1390 | |
1391 | node_hash = ri->hash_table->hashes[ri->position]; |
1392 | |
1393 | key = g_hash_table_fetch_key_or_value (a: ri->hash_table->keys, index: ri->position, is_big: ri->hash_table->have_big_keys); |
1394 | |
1395 | g_hash_table_insert_node (hash_table: ri->hash_table, node_index: ri->position, key_hash: node_hash, new_key: key, new_value: value, TRUE, TRUE); |
1396 | |
1397 | #ifndef G_DISABLE_ASSERT |
1398 | ri->version++; |
1399 | ri->hash_table->version++; |
1400 | #endif |
1401 | } |
1402 | |
1403 | /** |
1404 | * g_hash_table_iter_steal: |
1405 | * @iter: an initialized #GHashTableIter |
1406 | * |
1407 | * Removes the key/value pair currently pointed to by the |
1408 | * iterator from its associated #GHashTable, without calling |
1409 | * the key and value destroy functions. Can only be called |
1410 | * after g_hash_table_iter_next() returned %TRUE, and cannot |
1411 | * be called more than once for the same key/value pair. |
1412 | * |
1413 | * Since: 2.16 |
1414 | */ |
1415 | void |
1416 | g_hash_table_iter_steal (GHashTableIter *iter) |
1417 | { |
1418 | iter_remove_or_steal (ri: (RealIter *) iter, FALSE); |
1419 | } |
1420 | |
1421 | |
1422 | /** |
1423 | * g_hash_table_ref: |
1424 | * @hash_table: a valid #GHashTable |
1425 | * |
1426 | * Atomically increments the reference count of @hash_table by one. |
1427 | * This function is MT-safe and may be called from any thread. |
1428 | * |
1429 | * Returns: the passed in #GHashTable |
1430 | * |
1431 | * Since: 2.10 |
1432 | */ |
1433 | GHashTable * |
1434 | g_hash_table_ref (GHashTable *hash_table) |
1435 | { |
1436 | g_return_val_if_fail (hash_table != NULL, NULL); |
1437 | |
1438 | g_atomic_ref_count_inc (arc: &hash_table->ref_count); |
1439 | |
1440 | return hash_table; |
1441 | } |
1442 | |
1443 | /** |
1444 | * g_hash_table_unref: |
1445 | * @hash_table: a valid #GHashTable |
1446 | * |
1447 | * Atomically decrements the reference count of @hash_table by one. |
1448 | * If the reference count drops to 0, all keys and values will be |
1449 | * destroyed, and all memory allocated by the hash table is released. |
1450 | * This function is MT-safe and may be called from any thread. |
1451 | * |
1452 | * Since: 2.10 |
1453 | */ |
1454 | void |
1455 | g_hash_table_unref (GHashTable *hash_table) |
1456 | { |
1457 | g_return_if_fail (hash_table != NULL); |
1458 | |
1459 | if (g_atomic_ref_count_dec (arc: &hash_table->ref_count)) |
1460 | { |
1461 | g_hash_table_remove_all_nodes (hash_table, TRUE, TRUE); |
1462 | if (hash_table->keys != hash_table->values) |
1463 | g_free (mem: hash_table->values); |
1464 | g_free (mem: hash_table->keys); |
1465 | g_free (mem: hash_table->hashes); |
1466 | g_slice_free (GHashTable, hash_table); |
1467 | } |
1468 | } |
1469 | |
1470 | /** |
1471 | * g_hash_table_destroy: |
1472 | * @hash_table: a #GHashTable |
1473 | * |
1474 | * Destroys all keys and values in the #GHashTable and decrements its |
1475 | * reference count by 1. If keys and/or values are dynamically allocated, |
1476 | * you should either free them first or create the #GHashTable with destroy |
1477 | * notifiers using g_hash_table_new_full(). In the latter case the destroy |
1478 | * functions you supplied will be called on all keys and values during the |
1479 | * destruction phase. |
1480 | */ |
1481 | void |
1482 | g_hash_table_destroy (GHashTable *hash_table) |
1483 | { |
1484 | g_return_if_fail (hash_table != NULL); |
1485 | |
1486 | g_hash_table_remove_all (hash_table); |
1487 | g_hash_table_unref (hash_table); |
1488 | } |
1489 | |
1490 | /** |
1491 | * g_hash_table_lookup: |
1492 | * @hash_table: a #GHashTable |
1493 | * @key: the key to look up |
1494 | * |
1495 | * Looks up a key in a #GHashTable. Note that this function cannot |
1496 | * distinguish between a key that is not present and one which is present |
1497 | * and has the value %NULL. If you need this distinction, use |
1498 | * g_hash_table_lookup_extended(). |
1499 | * |
1500 | * Returns: (nullable): the associated value, or %NULL if the key is not found |
1501 | */ |
1502 | gpointer |
1503 | g_hash_table_lookup (GHashTable *hash_table, |
1504 | gconstpointer key) |
1505 | { |
1506 | guint node_index; |
1507 | guint node_hash; |
1508 | |
1509 | g_return_val_if_fail (hash_table != NULL, NULL); |
1510 | |
1511 | node_index = g_hash_table_lookup_node (hash_table, key, hash_return: &node_hash); |
1512 | |
1513 | return HASH_IS_REAL (hash_table->hashes[node_index]) |
1514 | ? g_hash_table_fetch_key_or_value (a: hash_table->values, index: node_index, is_big: hash_table->have_big_values) |
1515 | : NULL; |
1516 | } |
1517 | |
1518 | /** |
1519 | * g_hash_table_lookup_extended: |
1520 | * @hash_table: a #GHashTable |
1521 | * @lookup_key: the key to look up |
1522 | * @orig_key: (out) (optional): return location for the original key |
1523 | * @value: (out) (optional) (nullable): return location for the value associated |
1524 | * with the key |
1525 | * |
1526 | * Looks up a key in the #GHashTable, returning the original key and the |
1527 | * associated value and a #gboolean which is %TRUE if the key was found. This |
1528 | * is useful if you need to free the memory allocated for the original key, |
1529 | * for example before calling g_hash_table_remove(). |
1530 | * |
1531 | * You can actually pass %NULL for @lookup_key to test |
1532 | * whether the %NULL key exists, provided the hash and equal functions |
1533 | * of @hash_table are %NULL-safe. |
1534 | * |
1535 | * Returns: %TRUE if the key was found in the #GHashTable |
1536 | */ |
1537 | gboolean |
1538 | g_hash_table_lookup_extended (GHashTable *hash_table, |
1539 | gconstpointer lookup_key, |
1540 | gpointer *orig_key, |
1541 | gpointer *value) |
1542 | { |
1543 | guint node_index; |
1544 | guint node_hash; |
1545 | |
1546 | g_return_val_if_fail (hash_table != NULL, FALSE); |
1547 | |
1548 | node_index = g_hash_table_lookup_node (hash_table, key: lookup_key, hash_return: &node_hash); |
1549 | |
1550 | if (!HASH_IS_REAL (hash_table->hashes[node_index])) |
1551 | { |
1552 | if (orig_key != NULL) |
1553 | *orig_key = NULL; |
1554 | if (value != NULL) |
1555 | *value = NULL; |
1556 | |
1557 | return FALSE; |
1558 | } |
1559 | |
1560 | if (orig_key) |
1561 | *orig_key = g_hash_table_fetch_key_or_value (a: hash_table->keys, index: node_index, is_big: hash_table->have_big_keys); |
1562 | |
1563 | if (value) |
1564 | *value = g_hash_table_fetch_key_or_value (a: hash_table->values, index: node_index, is_big: hash_table->have_big_values); |
1565 | |
1566 | return TRUE; |
1567 | } |
1568 | |
1569 | /* |
1570 | * g_hash_table_insert_internal: |
1571 | * @hash_table: our #GHashTable |
1572 | * @key: the key to insert |
1573 | * @value: the value to insert |
1574 | * @keep_new_key: if %TRUE and this key already exists in the table |
1575 | * then call the destroy notify function on the old key. If %FALSE |
1576 | * then call the destroy notify function on the new key. |
1577 | * |
1578 | * Implements the common logic for the g_hash_table_insert() and |
1579 | * g_hash_table_replace() functions. |
1580 | * |
1581 | * Do a lookup of @key. If it is found, replace it with the new |
1582 | * @value (and perhaps the new @key). If it is not found, create |
1583 | * a new node. |
1584 | * |
1585 | * Returns: %TRUE if the key did not exist yet |
1586 | */ |
1587 | static gboolean |
1588 | g_hash_table_insert_internal (GHashTable *hash_table, |
1589 | gpointer key, |
1590 | gpointer value, |
1591 | gboolean keep_new_key) |
1592 | { |
1593 | guint key_hash; |
1594 | guint node_index; |
1595 | |
1596 | g_return_val_if_fail (hash_table != NULL, FALSE); |
1597 | |
1598 | node_index = g_hash_table_lookup_node (hash_table, key, hash_return: &key_hash); |
1599 | |
1600 | return g_hash_table_insert_node (hash_table, node_index, key_hash, new_key: key, new_value: value, keep_new_key, FALSE); |
1601 | } |
1602 | |
1603 | /** |
1604 | * g_hash_table_insert: |
1605 | * @hash_table: a #GHashTable |
1606 | * @key: a key to insert |
1607 | * @value: the value to associate with the key |
1608 | * |
1609 | * Inserts a new key and value into a #GHashTable. |
1610 | * |
1611 | * If the key already exists in the #GHashTable its current |
1612 | * value is replaced with the new value. If you supplied a |
1613 | * @value_destroy_func when creating the #GHashTable, the old |
1614 | * value is freed using that function. If you supplied a |
1615 | * @key_destroy_func when creating the #GHashTable, the passed |
1616 | * key is freed using that function. |
1617 | * |
1618 | * Starting from GLib 2.40, this function returns a boolean value to |
1619 | * indicate whether the newly added value was already in the hash table |
1620 | * or not. |
1621 | * |
1622 | * Returns: %TRUE if the key did not exist yet |
1623 | */ |
1624 | gboolean |
1625 | g_hash_table_insert (GHashTable *hash_table, |
1626 | gpointer key, |
1627 | gpointer value) |
1628 | { |
1629 | return g_hash_table_insert_internal (hash_table, key, value, FALSE); |
1630 | } |
1631 | |
1632 | /** |
1633 | * g_hash_table_replace: |
1634 | * @hash_table: a #GHashTable |
1635 | * @key: a key to insert |
1636 | * @value: the value to associate with the key |
1637 | * |
1638 | * Inserts a new key and value into a #GHashTable similar to |
1639 | * g_hash_table_insert(). The difference is that if the key |
1640 | * already exists in the #GHashTable, it gets replaced by the |
1641 | * new key. If you supplied a @value_destroy_func when creating |
1642 | * the #GHashTable, the old value is freed using that function. |
1643 | * If you supplied a @key_destroy_func when creating the |
1644 | * #GHashTable, the old key is freed using that function. |
1645 | * |
1646 | * Starting from GLib 2.40, this function returns a boolean value to |
1647 | * indicate whether the newly added value was already in the hash table |
1648 | * or not. |
1649 | * |
1650 | * Returns: %TRUE if the key did not exist yet |
1651 | */ |
1652 | gboolean |
1653 | g_hash_table_replace (GHashTable *hash_table, |
1654 | gpointer key, |
1655 | gpointer value) |
1656 | { |
1657 | return g_hash_table_insert_internal (hash_table, key, value, TRUE); |
1658 | } |
1659 | |
1660 | /** |
1661 | * g_hash_table_add: |
1662 | * @hash_table: a #GHashTable |
1663 | * @key: (transfer full): a key to insert |
1664 | * |
1665 | * This is a convenience function for using a #GHashTable as a set. It |
1666 | * is equivalent to calling g_hash_table_replace() with @key as both the |
1667 | * key and the value. |
1668 | * |
1669 | * In particular, this means that if @key already exists in the hash table, then |
1670 | * the old copy of @key in the hash table is freed and @key replaces it in the |
1671 | * table. |
1672 | * |
1673 | * When a hash table only ever contains keys that have themselves as the |
1674 | * corresponding value it is able to be stored more efficiently. See |
1675 | * the discussion in the section description. |
1676 | * |
1677 | * Starting from GLib 2.40, this function returns a boolean value to |
1678 | * indicate whether the newly added value was already in the hash table |
1679 | * or not. |
1680 | * |
1681 | * Returns: %TRUE if the key did not exist yet |
1682 | * |
1683 | * Since: 2.32 |
1684 | */ |
1685 | gboolean |
1686 | g_hash_table_add (GHashTable *hash_table, |
1687 | gpointer key) |
1688 | { |
1689 | return g_hash_table_insert_internal (hash_table, key, value: key, TRUE); |
1690 | } |
1691 | |
1692 | /** |
1693 | * g_hash_table_contains: |
1694 | * @hash_table: a #GHashTable |
1695 | * @key: a key to check |
1696 | * |
1697 | * Checks if @key is in @hash_table. |
1698 | * |
1699 | * Returns: %TRUE if @key is in @hash_table, %FALSE otherwise. |
1700 | * |
1701 | * Since: 2.32 |
1702 | **/ |
1703 | gboolean |
1704 | g_hash_table_contains (GHashTable *hash_table, |
1705 | gconstpointer key) |
1706 | { |
1707 | guint node_index; |
1708 | guint node_hash; |
1709 | |
1710 | g_return_val_if_fail (hash_table != NULL, FALSE); |
1711 | |
1712 | node_index = g_hash_table_lookup_node (hash_table, key, hash_return: &node_hash); |
1713 | |
1714 | return HASH_IS_REAL (hash_table->hashes[node_index]); |
1715 | } |
1716 | |
1717 | /* |
1718 | * g_hash_table_remove_internal: |
1719 | * @hash_table: our #GHashTable |
1720 | * @key: the key to remove |
1721 | * @notify: %TRUE if the destroy notify handlers are to be called |
1722 | * Returns: %TRUE if a node was found and removed, else %FALSE |
1723 | * |
1724 | * Implements the common logic for the g_hash_table_remove() and |
1725 | * g_hash_table_steal() functions. |
1726 | * |
1727 | * Do a lookup of @key and remove it if it is found, calling the |
1728 | * destroy notify handlers only if @notify is %TRUE. |
1729 | */ |
1730 | static gboolean |
1731 | g_hash_table_remove_internal (GHashTable *hash_table, |
1732 | gconstpointer key, |
1733 | gboolean notify) |
1734 | { |
1735 | guint node_index; |
1736 | guint node_hash; |
1737 | |
1738 | g_return_val_if_fail (hash_table != NULL, FALSE); |
1739 | |
1740 | node_index = g_hash_table_lookup_node (hash_table, key, hash_return: &node_hash); |
1741 | |
1742 | if (!HASH_IS_REAL (hash_table->hashes[node_index])) |
1743 | return FALSE; |
1744 | |
1745 | g_hash_table_remove_node (hash_table, i: node_index, notify); |
1746 | g_hash_table_maybe_resize (hash_table); |
1747 | |
1748 | #ifndef G_DISABLE_ASSERT |
1749 | hash_table->version++; |
1750 | #endif |
1751 | |
1752 | return TRUE; |
1753 | } |
1754 | |
1755 | /** |
1756 | * g_hash_table_remove: |
1757 | * @hash_table: a #GHashTable |
1758 | * @key: the key to remove |
1759 | * |
1760 | * Removes a key and its associated value from a #GHashTable. |
1761 | * |
1762 | * If the #GHashTable was created using g_hash_table_new_full(), the |
1763 | * key and value are freed using the supplied destroy functions, otherwise |
1764 | * you have to make sure that any dynamically allocated values are freed |
1765 | * yourself. |
1766 | * |
1767 | * Returns: %TRUE if the key was found and removed from the #GHashTable |
1768 | */ |
1769 | gboolean |
1770 | g_hash_table_remove (GHashTable *hash_table, |
1771 | gconstpointer key) |
1772 | { |
1773 | return g_hash_table_remove_internal (hash_table, key, TRUE); |
1774 | } |
1775 | |
1776 | /** |
1777 | * g_hash_table_steal: |
1778 | * @hash_table: a #GHashTable |
1779 | * @key: the key to remove |
1780 | * |
1781 | * Removes a key and its associated value from a #GHashTable without |
1782 | * calling the key and value destroy functions. |
1783 | * |
1784 | * Returns: %TRUE if the key was found and removed from the #GHashTable |
1785 | */ |
1786 | gboolean |
1787 | g_hash_table_steal (GHashTable *hash_table, |
1788 | gconstpointer key) |
1789 | { |
1790 | return g_hash_table_remove_internal (hash_table, key, FALSE); |
1791 | } |
1792 | |
1793 | /** |
1794 | * g_hash_table_steal_extended: |
1795 | * @hash_table: a #GHashTable |
1796 | * @lookup_key: the key to look up |
1797 | * @stolen_key: (out) (optional) (transfer full): return location for the |
1798 | * original key |
1799 | * @stolen_value: (out) (optional) (nullable) (transfer full): return location |
1800 | * for the value associated with the key |
1801 | * |
1802 | * Looks up a key in the #GHashTable, stealing the original key and the |
1803 | * associated value and returning %TRUE if the key was found. If the key was |
1804 | * not found, %FALSE is returned. |
1805 | * |
1806 | * If found, the stolen key and value are removed from the hash table without |
1807 | * calling the key and value destroy functions, and ownership is transferred to |
1808 | * the caller of this method; as with g_hash_table_steal(). |
1809 | * |
1810 | * You can pass %NULL for @lookup_key, provided the hash and equal functions |
1811 | * of @hash_table are %NULL-safe. |
1812 | * |
1813 | * Returns: %TRUE if the key was found in the #GHashTable |
1814 | * Since: 2.58 |
1815 | */ |
1816 | gboolean |
1817 | g_hash_table_steal_extended (GHashTable *hash_table, |
1818 | gconstpointer lookup_key, |
1819 | gpointer *stolen_key, |
1820 | gpointer *stolen_value) |
1821 | { |
1822 | guint node_index; |
1823 | guint node_hash; |
1824 | |
1825 | g_return_val_if_fail (hash_table != NULL, FALSE); |
1826 | |
1827 | node_index = g_hash_table_lookup_node (hash_table, key: lookup_key, hash_return: &node_hash); |
1828 | |
1829 | if (!HASH_IS_REAL (hash_table->hashes[node_index])) |
1830 | { |
1831 | if (stolen_key != NULL) |
1832 | *stolen_key = NULL; |
1833 | if (stolen_value != NULL) |
1834 | *stolen_value = NULL; |
1835 | return FALSE; |
1836 | } |
1837 | |
1838 | if (stolen_key != NULL) |
1839 | { |
1840 | *stolen_key = g_hash_table_fetch_key_or_value (a: hash_table->keys, index: node_index, is_big: hash_table->have_big_keys); |
1841 | g_hash_table_assign_key_or_value (a: hash_table->keys, index: node_index, is_big: hash_table->have_big_keys, NULL); |
1842 | } |
1843 | |
1844 | if (stolen_value != NULL) |
1845 | { |
1846 | *stolen_value = g_hash_table_fetch_key_or_value (a: hash_table->values, index: node_index, is_big: hash_table->have_big_values); |
1847 | g_hash_table_assign_key_or_value (a: hash_table->values, index: node_index, is_big: hash_table->have_big_values, NULL); |
1848 | } |
1849 | |
1850 | g_hash_table_remove_node (hash_table, i: node_index, FALSE); |
1851 | g_hash_table_maybe_resize (hash_table); |
1852 | |
1853 | #ifndef G_DISABLE_ASSERT |
1854 | hash_table->version++; |
1855 | #endif |
1856 | |
1857 | return TRUE; |
1858 | } |
1859 | |
1860 | /** |
1861 | * g_hash_table_remove_all: |
1862 | * @hash_table: a #GHashTable |
1863 | * |
1864 | * Removes all keys and their associated values from a #GHashTable. |
1865 | * |
1866 | * If the #GHashTable was created using g_hash_table_new_full(), |
1867 | * the keys and values are freed using the supplied destroy functions, |
1868 | * otherwise you have to make sure that any dynamically allocated |
1869 | * values are freed yourself. |
1870 | * |
1871 | * Since: 2.12 |
1872 | */ |
1873 | void |
1874 | g_hash_table_remove_all (GHashTable *hash_table) |
1875 | { |
1876 | g_return_if_fail (hash_table != NULL); |
1877 | |
1878 | #ifndef G_DISABLE_ASSERT |
1879 | if (hash_table->nnodes != 0) |
1880 | hash_table->version++; |
1881 | #endif |
1882 | |
1883 | g_hash_table_remove_all_nodes (hash_table, TRUE, FALSE); |
1884 | g_hash_table_maybe_resize (hash_table); |
1885 | } |
1886 | |
1887 | /** |
1888 | * g_hash_table_steal_all: |
1889 | * @hash_table: a #GHashTable |
1890 | * |
1891 | * Removes all keys and their associated values from a #GHashTable |
1892 | * without calling the key and value destroy functions. |
1893 | * |
1894 | * Since: 2.12 |
1895 | */ |
1896 | void |
1897 | g_hash_table_steal_all (GHashTable *hash_table) |
1898 | { |
1899 | g_return_if_fail (hash_table != NULL); |
1900 | |
1901 | #ifndef G_DISABLE_ASSERT |
1902 | if (hash_table->nnodes != 0) |
1903 | hash_table->version++; |
1904 | #endif |
1905 | |
1906 | g_hash_table_remove_all_nodes (hash_table, FALSE, FALSE); |
1907 | g_hash_table_maybe_resize (hash_table); |
1908 | } |
1909 | |
1910 | /* |
1911 | * g_hash_table_foreach_remove_or_steal: |
1912 | * @hash_table: a #GHashTable |
1913 | * @func: the user's callback function |
1914 | * @user_data: data for @func |
1915 | * @notify: %TRUE if the destroy notify handlers are to be called |
1916 | * |
1917 | * Implements the common logic for g_hash_table_foreach_remove() |
1918 | * and g_hash_table_foreach_steal(). |
1919 | * |
1920 | * Iterates over every node in the table, calling @func with the key |
1921 | * and value of the node (and @user_data). If @func returns %TRUE the |
1922 | * node is removed from the table. |
1923 | * |
1924 | * If @notify is true then the destroy notify handlers will be called |
1925 | * for each removed node. |
1926 | */ |
1927 | static guint |
1928 | g_hash_table_foreach_remove_or_steal (GHashTable *hash_table, |
1929 | GHRFunc func, |
1930 | gpointer user_data, |
1931 | gboolean notify) |
1932 | { |
1933 | guint deleted = 0; |
1934 | gsize i; |
1935 | #ifndef G_DISABLE_ASSERT |
1936 | gint version = hash_table->version; |
1937 | #endif |
1938 | |
1939 | for (i = 0; i < hash_table->size; i++) |
1940 | { |
1941 | guint node_hash = hash_table->hashes[i]; |
1942 | gpointer node_key = g_hash_table_fetch_key_or_value (a: hash_table->keys, index: i, is_big: hash_table->have_big_keys); |
1943 | gpointer node_value = g_hash_table_fetch_key_or_value (a: hash_table->values, index: i, is_big: hash_table->have_big_values); |
1944 | |
1945 | if (HASH_IS_REAL (node_hash) && |
1946 | (* func) (node_key, node_value, user_data)) |
1947 | { |
1948 | g_hash_table_remove_node (hash_table, i, notify); |
1949 | deleted++; |
1950 | } |
1951 | |
1952 | #ifndef G_DISABLE_ASSERT |
1953 | g_return_val_if_fail (version == hash_table->version, 0); |
1954 | #endif |
1955 | } |
1956 | |
1957 | g_hash_table_maybe_resize (hash_table); |
1958 | |
1959 | #ifndef G_DISABLE_ASSERT |
1960 | if (deleted > 0) |
1961 | hash_table->version++; |
1962 | #endif |
1963 | |
1964 | return deleted; |
1965 | } |
1966 | |
1967 | /** |
1968 | * g_hash_table_foreach_remove: |
1969 | * @hash_table: a #GHashTable |
1970 | * @func: the function to call for each key/value pair |
1971 | * @user_data: user data to pass to the function |
1972 | * |
1973 | * Calls the given function for each key/value pair in the |
1974 | * #GHashTable. If the function returns %TRUE, then the key/value |
1975 | * pair is removed from the #GHashTable. If you supplied key or |
1976 | * value destroy functions when creating the #GHashTable, they are |
1977 | * used to free the memory allocated for the removed keys and values. |
1978 | * |
1979 | * See #GHashTableIter for an alternative way to loop over the |
1980 | * key/value pairs in the hash table. |
1981 | * |
1982 | * Returns: the number of key/value pairs removed |
1983 | */ |
1984 | guint |
1985 | g_hash_table_foreach_remove (GHashTable *hash_table, |
1986 | GHRFunc func, |
1987 | gpointer user_data) |
1988 | { |
1989 | g_return_val_if_fail (hash_table != NULL, 0); |
1990 | g_return_val_if_fail (func != NULL, 0); |
1991 | |
1992 | return g_hash_table_foreach_remove_or_steal (hash_table, func, user_data, TRUE); |
1993 | } |
1994 | |
1995 | /** |
1996 | * g_hash_table_foreach_steal: |
1997 | * @hash_table: a #GHashTable |
1998 | * @func: the function to call for each key/value pair |
1999 | * @user_data: user data to pass to the function |
2000 | * |
2001 | * Calls the given function for each key/value pair in the |
2002 | * #GHashTable. If the function returns %TRUE, then the key/value |
2003 | * pair is removed from the #GHashTable, but no key or value |
2004 | * destroy functions are called. |
2005 | * |
2006 | * See #GHashTableIter for an alternative way to loop over the |
2007 | * key/value pairs in the hash table. |
2008 | * |
2009 | * Returns: the number of key/value pairs removed. |
2010 | */ |
2011 | guint |
2012 | g_hash_table_foreach_steal (GHashTable *hash_table, |
2013 | GHRFunc func, |
2014 | gpointer user_data) |
2015 | { |
2016 | g_return_val_if_fail (hash_table != NULL, 0); |
2017 | g_return_val_if_fail (func != NULL, 0); |
2018 | |
2019 | return g_hash_table_foreach_remove_or_steal (hash_table, func, user_data, FALSE); |
2020 | } |
2021 | |
2022 | /** |
2023 | * g_hash_table_foreach: |
2024 | * @hash_table: a #GHashTable |
2025 | * @func: the function to call for each key/value pair |
2026 | * @user_data: user data to pass to the function |
2027 | * |
2028 | * Calls the given function for each of the key/value pairs in the |
2029 | * #GHashTable. The function is passed the key and value of each |
2030 | * pair, and the given @user_data parameter. The hash table may not |
2031 | * be modified while iterating over it (you can't add/remove |
2032 | * items). To remove all items matching a predicate, use |
2033 | * g_hash_table_foreach_remove(). |
2034 | * |
2035 | * The order in which g_hash_table_foreach() iterates over the keys/values in |
2036 | * the hash table is not defined. |
2037 | * |
2038 | * See g_hash_table_find() for performance caveats for linear |
2039 | * order searches in contrast to g_hash_table_lookup(). |
2040 | */ |
2041 | void |
2042 | g_hash_table_foreach (GHashTable *hash_table, |
2043 | GHFunc func, |
2044 | gpointer user_data) |
2045 | { |
2046 | gsize i; |
2047 | #ifndef G_DISABLE_ASSERT |
2048 | gint version; |
2049 | #endif |
2050 | |
2051 | g_return_if_fail (hash_table != NULL); |
2052 | g_return_if_fail (func != NULL); |
2053 | |
2054 | #ifndef G_DISABLE_ASSERT |
2055 | version = hash_table->version; |
2056 | #endif |
2057 | |
2058 | for (i = 0; i < hash_table->size; i++) |
2059 | { |
2060 | guint node_hash = hash_table->hashes[i]; |
2061 | gpointer node_key = g_hash_table_fetch_key_or_value (a: hash_table->keys, index: i, is_big: hash_table->have_big_keys); |
2062 | gpointer node_value = g_hash_table_fetch_key_or_value (a: hash_table->values, index: i, is_big: hash_table->have_big_values); |
2063 | |
2064 | if (HASH_IS_REAL (node_hash)) |
2065 | (* func) (node_key, node_value, user_data); |
2066 | |
2067 | #ifndef G_DISABLE_ASSERT |
2068 | g_return_if_fail (version == hash_table->version); |
2069 | #endif |
2070 | } |
2071 | } |
2072 | |
2073 | /** |
2074 | * g_hash_table_find: |
2075 | * @hash_table: a #GHashTable |
2076 | * @predicate: function to test the key/value pairs for a certain property |
2077 | * @user_data: user data to pass to the function |
2078 | * |
2079 | * Calls the given function for key/value pairs in the #GHashTable |
2080 | * until @predicate returns %TRUE. The function is passed the key |
2081 | * and value of each pair, and the given @user_data parameter. The |
2082 | * hash table may not be modified while iterating over it (you can't |
2083 | * add/remove items). |
2084 | * |
2085 | * Note, that hash tables are really only optimized for forward |
2086 | * lookups, i.e. g_hash_table_lookup(). So code that frequently issues |
2087 | * g_hash_table_find() or g_hash_table_foreach() (e.g. in the order of |
2088 | * once per every entry in a hash table) should probably be reworked |
2089 | * to use additional or different data structures for reverse lookups |
2090 | * (keep in mind that an O(n) find/foreach operation issued for all n |
2091 | * values in a hash table ends up needing O(n*n) operations). |
2092 | * |
2093 | * Returns: (nullable): The value of the first key/value pair is returned, |
2094 | * for which @predicate evaluates to %TRUE. If no pair with the |
2095 | * requested property is found, %NULL is returned. |
2096 | * |
2097 | * Since: 2.4 |
2098 | */ |
2099 | gpointer |
2100 | g_hash_table_find (GHashTable *hash_table, |
2101 | GHRFunc predicate, |
2102 | gpointer user_data) |
2103 | { |
2104 | gsize i; |
2105 | #ifndef G_DISABLE_ASSERT |
2106 | gint version; |
2107 | #endif |
2108 | gboolean match; |
2109 | |
2110 | g_return_val_if_fail (hash_table != NULL, NULL); |
2111 | g_return_val_if_fail (predicate != NULL, NULL); |
2112 | |
2113 | #ifndef G_DISABLE_ASSERT |
2114 | version = hash_table->version; |
2115 | #endif |
2116 | |
2117 | match = FALSE; |
2118 | |
2119 | for (i = 0; i < hash_table->size; i++) |
2120 | { |
2121 | guint node_hash = hash_table->hashes[i]; |
2122 | gpointer node_key = g_hash_table_fetch_key_or_value (a: hash_table->keys, index: i, is_big: hash_table->have_big_keys); |
2123 | gpointer node_value = g_hash_table_fetch_key_or_value (a: hash_table->values, index: i, is_big: hash_table->have_big_values); |
2124 | |
2125 | if (HASH_IS_REAL (node_hash)) |
2126 | match = predicate (node_key, node_value, user_data); |
2127 | |
2128 | #ifndef G_DISABLE_ASSERT |
2129 | g_return_val_if_fail (version == hash_table->version, NULL); |
2130 | #endif |
2131 | |
2132 | if (match) |
2133 | return node_value; |
2134 | } |
2135 | |
2136 | return NULL; |
2137 | } |
2138 | |
2139 | /** |
2140 | * g_hash_table_size: |
2141 | * @hash_table: a #GHashTable |
2142 | * |
2143 | * Returns the number of elements contained in the #GHashTable. |
2144 | * |
2145 | * Returns: the number of key/value pairs in the #GHashTable. |
2146 | */ |
2147 | guint |
2148 | g_hash_table_size (GHashTable *hash_table) |
2149 | { |
2150 | g_return_val_if_fail (hash_table != NULL, 0); |
2151 | |
2152 | return hash_table->nnodes; |
2153 | } |
2154 | |
2155 | /** |
2156 | * g_hash_table_get_keys: |
2157 | * @hash_table: a #GHashTable |
2158 | * |
2159 | * Retrieves every key inside @hash_table. The returned data is valid |
2160 | * until changes to the hash release those keys. |
2161 | * |
2162 | * This iterates over every entry in the hash table to build its return value. |
2163 | * To iterate over the entries in a #GHashTable more efficiently, use a |
2164 | * #GHashTableIter. |
2165 | * |
2166 | * Returns: (transfer container): a #GList containing all the keys |
2167 | * inside the hash table. The content of the list is owned by the |
2168 | * hash table and should not be modified or freed. Use g_list_free() |
2169 | * when done using the list. |
2170 | * |
2171 | * Since: 2.14 |
2172 | */ |
2173 | GList * |
2174 | g_hash_table_get_keys (GHashTable *hash_table) |
2175 | { |
2176 | gsize i; |
2177 | GList *retval; |
2178 | |
2179 | g_return_val_if_fail (hash_table != NULL, NULL); |
2180 | |
2181 | retval = NULL; |
2182 | for (i = 0; i < hash_table->size; i++) |
2183 | { |
2184 | if (HASH_IS_REAL (hash_table->hashes[i])) |
2185 | retval = g_list_prepend (list: retval, data: g_hash_table_fetch_key_or_value (a: hash_table->keys, index: i, is_big: hash_table->have_big_keys)); |
2186 | } |
2187 | |
2188 | return retval; |
2189 | } |
2190 | |
2191 | /** |
2192 | * g_hash_table_get_keys_as_array: |
2193 | * @hash_table: a #GHashTable |
2194 | * @length: (out): the length of the returned array |
2195 | * |
2196 | * Retrieves every key inside @hash_table, as an array. |
2197 | * |
2198 | * The returned array is %NULL-terminated but may contain %NULL as a |
2199 | * key. Use @length to determine the true length if it's possible that |
2200 | * %NULL was used as the value for a key. |
2201 | * |
2202 | * Note: in the common case of a string-keyed #GHashTable, the return |
2203 | * value of this function can be conveniently cast to (const gchar **). |
2204 | * |
2205 | * This iterates over every entry in the hash table to build its return value. |
2206 | * To iterate over the entries in a #GHashTable more efficiently, use a |
2207 | * #GHashTableIter. |
2208 | * |
2209 | * You should always free the return result with g_free(). In the |
2210 | * above-mentioned case of a string-keyed hash table, it may be |
2211 | * appropriate to use g_strfreev() if you call g_hash_table_steal_all() |
2212 | * first to transfer ownership of the keys. |
2213 | * |
2214 | * Returns: (array length=length) (transfer container): a |
2215 | * %NULL-terminated array containing each key from the table. |
2216 | * |
2217 | * Since: 2.40 |
2218 | **/ |
2219 | gpointer * |
2220 | g_hash_table_get_keys_as_array (GHashTable *hash_table, |
2221 | guint *length) |
2222 | { |
2223 | gpointer *result; |
2224 | gsize i, j = 0; |
2225 | |
2226 | result = g_new (gpointer, hash_table->nnodes + 1); |
2227 | for (i = 0; i < hash_table->size; i++) |
2228 | { |
2229 | if (HASH_IS_REAL (hash_table->hashes[i])) |
2230 | result[j++] = g_hash_table_fetch_key_or_value (a: hash_table->keys, index: i, is_big: hash_table->have_big_keys); |
2231 | } |
2232 | g_assert_cmpint (j, ==, hash_table->nnodes); |
2233 | result[j] = NULL; |
2234 | |
2235 | if (length) |
2236 | *length = j; |
2237 | |
2238 | return result; |
2239 | } |
2240 | |
2241 | /** |
2242 | * g_hash_table_get_values: |
2243 | * @hash_table: a #GHashTable |
2244 | * |
2245 | * Retrieves every value inside @hash_table. The returned data |
2246 | * is valid until @hash_table is modified. |
2247 | * |
2248 | * This iterates over every entry in the hash table to build its return value. |
2249 | * To iterate over the entries in a #GHashTable more efficiently, use a |
2250 | * #GHashTableIter. |
2251 | * |
2252 | * Returns: (transfer container): a #GList containing all the values |
2253 | * inside the hash table. The content of the list is owned by the |
2254 | * hash table and should not be modified or freed. Use g_list_free() |
2255 | * when done using the list. |
2256 | * |
2257 | * Since: 2.14 |
2258 | */ |
2259 | GList * |
2260 | g_hash_table_get_values (GHashTable *hash_table) |
2261 | { |
2262 | gsize i; |
2263 | GList *retval; |
2264 | |
2265 | g_return_val_if_fail (hash_table != NULL, NULL); |
2266 | |
2267 | retval = NULL; |
2268 | for (i = 0; i < hash_table->size; i++) |
2269 | { |
2270 | if (HASH_IS_REAL (hash_table->hashes[i])) |
2271 | retval = g_list_prepend (list: retval, data: g_hash_table_fetch_key_or_value (a: hash_table->values, index: i, is_big: hash_table->have_big_values)); |
2272 | } |
2273 | |
2274 | return retval; |
2275 | } |
2276 | |
2277 | /* Hash functions. |
2278 | */ |
2279 | |
2280 | /** |
2281 | * g_str_equal: |
2282 | * @v1: (not nullable): a key |
2283 | * @v2: (not nullable): a key to compare with @v1 |
2284 | * |
2285 | * Compares two strings for byte-by-byte equality and returns %TRUE |
2286 | * if they are equal. It can be passed to g_hash_table_new() as the |
2287 | * @key_equal_func parameter, when using non-%NULL strings as keys in a |
2288 | * #GHashTable. |
2289 | * |
2290 | * This function is typically used for hash table comparisons, but can be used |
2291 | * for general purpose comparisons of non-%NULL strings. For a %NULL-safe string |
2292 | * comparison function, see g_strcmp0(). |
2293 | * |
2294 | * Returns: %TRUE if the two keys match |
2295 | */ |
2296 | gboolean |
2297 | g_str_equal (gconstpointer v1, |
2298 | gconstpointer v2) |
2299 | { |
2300 | const gchar *string1 = v1; |
2301 | const gchar *string2 = v2; |
2302 | |
2303 | return strcmp (s1: string1, s2: string2) == 0; |
2304 | } |
2305 | |
2306 | /** |
2307 | * g_str_hash: |
2308 | * @v: (not nullable): a string key |
2309 | * |
2310 | * Converts a string to a hash value. |
2311 | * |
2312 | * This function implements the widely used "djb" hash apparently |
2313 | * posted by Daniel Bernstein to comp.lang.c some time ago. The 32 |
2314 | * bit unsigned hash value starts at 5381 and for each byte 'c' in |
2315 | * the string, is updated: `hash = hash * 33 + c`. This function |
2316 | * uses the signed value of each byte. |
2317 | * |
2318 | * It can be passed to g_hash_table_new() as the @hash_func parameter, |
2319 | * when using non-%NULL strings as keys in a #GHashTable. |
2320 | * |
2321 | * Note that this function may not be a perfect fit for all use cases. |
2322 | * For example, it produces some hash collisions with strings as short |
2323 | * as 2. |
2324 | * |
2325 | * Returns: a hash value corresponding to the key |
2326 | */ |
2327 | guint |
2328 | g_str_hash (gconstpointer v) |
2329 | { |
2330 | const signed char *p; |
2331 | guint32 h = 5381; |
2332 | |
2333 | for (p = v; *p != '\0'; p++) |
2334 | h = (h << 5) + h + *p; |
2335 | |
2336 | return h; |
2337 | } |
2338 | |
2339 | /** |
2340 | * g_direct_hash: |
2341 | * @v: (nullable): a #gpointer key |
2342 | * |
2343 | * Converts a gpointer to a hash value. |
2344 | * It can be passed to g_hash_table_new() as the @hash_func parameter, |
2345 | * when using opaque pointers compared by pointer value as keys in a |
2346 | * #GHashTable. |
2347 | * |
2348 | * This hash function is also appropriate for keys that are integers |
2349 | * stored in pointers, such as `GINT_TO_POINTER (n)`. |
2350 | * |
2351 | * Returns: a hash value corresponding to the key. |
2352 | */ |
2353 | guint |
2354 | g_direct_hash (gconstpointer v) |
2355 | { |
2356 | return GPOINTER_TO_UINT (v); |
2357 | } |
2358 | |
2359 | /** |
2360 | * g_direct_equal: |
2361 | * @v1: (nullable): a key |
2362 | * @v2: (nullable): a key to compare with @v1 |
2363 | * |
2364 | * Compares two #gpointer arguments and returns %TRUE if they are equal. |
2365 | * It can be passed to g_hash_table_new() as the @key_equal_func |
2366 | * parameter, when using opaque pointers compared by pointer value as |
2367 | * keys in a #GHashTable. |
2368 | * |
2369 | * This equality function is also appropriate for keys that are integers |
2370 | * stored in pointers, such as `GINT_TO_POINTER (n)`. |
2371 | * |
2372 | * Returns: %TRUE if the two keys match. |
2373 | */ |
2374 | gboolean |
2375 | g_direct_equal (gconstpointer v1, |
2376 | gconstpointer v2) |
2377 | { |
2378 | return v1 == v2; |
2379 | } |
2380 | |
2381 | /** |
2382 | * g_int_equal: |
2383 | * @v1: (not nullable): a pointer to a #gint key |
2384 | * @v2: (not nullable): a pointer to a #gint key to compare with @v1 |
2385 | * |
2386 | * Compares the two #gint values being pointed to and returns |
2387 | * %TRUE if they are equal. |
2388 | * It can be passed to g_hash_table_new() as the @key_equal_func |
2389 | * parameter, when using non-%NULL pointers to integers as keys in a |
2390 | * #GHashTable. |
2391 | * |
2392 | * Note that this function acts on pointers to #gint, not on #gint |
2393 | * directly: if your hash table's keys are of the form |
2394 | * `GINT_TO_POINTER (n)`, use g_direct_equal() instead. |
2395 | * |
2396 | * Returns: %TRUE if the two keys match. |
2397 | */ |
2398 | gboolean |
2399 | g_int_equal (gconstpointer v1, |
2400 | gconstpointer v2) |
2401 | { |
2402 | return *((const gint*) v1) == *((const gint*) v2); |
2403 | } |
2404 | |
2405 | /** |
2406 | * g_int_hash: |
2407 | * @v: (not nullable): a pointer to a #gint key |
2408 | * |
2409 | * Converts a pointer to a #gint to a hash value. |
2410 | * It can be passed to g_hash_table_new() as the @hash_func parameter, |
2411 | * when using non-%NULL pointers to integer values as keys in a #GHashTable. |
2412 | * |
2413 | * Note that this function acts on pointers to #gint, not on #gint |
2414 | * directly: if your hash table's keys are of the form |
2415 | * `GINT_TO_POINTER (n)`, use g_direct_hash() instead. |
2416 | * |
2417 | * Returns: a hash value corresponding to the key. |
2418 | */ |
2419 | guint |
2420 | g_int_hash (gconstpointer v) |
2421 | { |
2422 | return *(const gint*) v; |
2423 | } |
2424 | |
2425 | /** |
2426 | * g_int64_equal: |
2427 | * @v1: (not nullable): a pointer to a #gint64 key |
2428 | * @v2: (not nullable): a pointer to a #gint64 key to compare with @v1 |
2429 | * |
2430 | * Compares the two #gint64 values being pointed to and returns |
2431 | * %TRUE if they are equal. |
2432 | * It can be passed to g_hash_table_new() as the @key_equal_func |
2433 | * parameter, when using non-%NULL pointers to 64-bit integers as keys in a |
2434 | * #GHashTable. |
2435 | * |
2436 | * Returns: %TRUE if the two keys match. |
2437 | * |
2438 | * Since: 2.22 |
2439 | */ |
2440 | gboolean |
2441 | g_int64_equal (gconstpointer v1, |
2442 | gconstpointer v2) |
2443 | { |
2444 | return *((const gint64*) v1) == *((const gint64*) v2); |
2445 | } |
2446 | |
2447 | /** |
2448 | * g_int64_hash: |
2449 | * @v: (not nullable): a pointer to a #gint64 key |
2450 | * |
2451 | * Converts a pointer to a #gint64 to a hash value. |
2452 | * |
2453 | * It can be passed to g_hash_table_new() as the @hash_func parameter, |
2454 | * when using non-%NULL pointers to 64-bit integer values as keys in a |
2455 | * #GHashTable. |
2456 | * |
2457 | * Returns: a hash value corresponding to the key. |
2458 | * |
2459 | * Since: 2.22 |
2460 | */ |
2461 | guint |
2462 | g_int64_hash (gconstpointer v) |
2463 | { |
2464 | return (guint) *(const gint64*) v; |
2465 | } |
2466 | |
2467 | /** |
2468 | * g_double_equal: |
2469 | * @v1: (not nullable): a pointer to a #gdouble key |
2470 | * @v2: (not nullable): a pointer to a #gdouble key to compare with @v1 |
2471 | * |
2472 | * Compares the two #gdouble values being pointed to and returns |
2473 | * %TRUE if they are equal. |
2474 | * It can be passed to g_hash_table_new() as the @key_equal_func |
2475 | * parameter, when using non-%NULL pointers to doubles as keys in a |
2476 | * #GHashTable. |
2477 | * |
2478 | * Returns: %TRUE if the two keys match. |
2479 | * |
2480 | * Since: 2.22 |
2481 | */ |
2482 | gboolean |
2483 | g_double_equal (gconstpointer v1, |
2484 | gconstpointer v2) |
2485 | { |
2486 | return *((const gdouble*) v1) == *((const gdouble*) v2); |
2487 | } |
2488 | |
2489 | /** |
2490 | * g_double_hash: |
2491 | * @v: (not nullable): a pointer to a #gdouble key |
2492 | * |
2493 | * Converts a pointer to a #gdouble to a hash value. |
2494 | * It can be passed to g_hash_table_new() as the @hash_func parameter, |
2495 | * It can be passed to g_hash_table_new() as the @hash_func parameter, |
2496 | * when using non-%NULL pointers to doubles as keys in a #GHashTable. |
2497 | * |
2498 | * Returns: a hash value corresponding to the key. |
2499 | * |
2500 | * Since: 2.22 |
2501 | */ |
2502 | guint |
2503 | g_double_hash (gconstpointer v) |
2504 | { |
2505 | return (guint) *(const gdouble*) v; |
2506 | } |
2507 | |