X-Git-Url: http://review.tizen.org/git/?a=blobdiff_plain;f=glib%2Fghash.c;h=b42dd1423223e46ca51149995e19ed8a4f211d42;hb=0a4ee12c7a9dfc82443133dfb2b18fb411d79f48;hp=ac91d503436266a93439e1dc6c7b9b648c9e3e72;hpb=078dbda148a81af1b3a76fbda72f089b963087f1;p=platform%2Fupstream%2Fglib.git
diff --git a/glib/ghash.c b/glib/ghash.c
index ac91d50..b42dd14 100644
--- a/glib/ghash.c
+++ b/glib/ghash.c
@@ -95,8 +95,8 @@
* GHashTable:
*
* The #GHashTable struct is an opaque data structure to represent a
- * Hash Table. It should only be
- * accessed via the following functions.
+ * [Hash Table][glib-Hash-Tables]. It should only be accessed via the
+ * following functions.
*/
/**
@@ -112,7 +112,7 @@
* and #gchar* respectively.
*
* g_direct_hash() is also the appropriate hash function for keys
- * of the form GINT_TO_POINTER (n) (or similar macros).
+ * of the form `GINT_TO_POINTER (n)` (or similar macros).
*
* A good hash functions should produce
* hash values that are evenly distributed over a fairly large range.
@@ -126,7 +126,8 @@
* a more secure hash function when using a GHashTable with keys
* that originate in untrusted data (such as HTTP requests).
* Using g_str_hash() in that situation might make your application
- * vulerable to Algorithmic Complexity Attacks.
+ * vulerable to
+ * [Algorithmic Complexity Attacks](https://lwn.net/Articles/474912/).
*
* The key to choosing a good hash is unpredictability. Even
* cryptographic hashes are very easy to find collisions for when the
@@ -364,6 +365,13 @@ g_hash_table_lookup_node (GHashTable *hash_table,
gboolean have_tombstone = FALSE;
guint step = 0;
+ /* If this happens, then the application is probably doing too much work
+ * from a destroy notifier. The alternative would be to crash any second
+ * (as keys, etc. will be NULL).
+ * Applications need to either use g_hash_table_destroy, or ensure the hash
+ * table is empty prior to removing the last reference using g_hash_table_unref(). */
+ g_assert (hash_table->ref_count > 0);
+
hash_value = hash_table->hash_func (key);
if (G_UNLIKELY (!HASH_IS_REAL (hash_value)))
hash_value = 2;
@@ -464,11 +472,20 @@ g_hash_table_remove_node (GHashTable *hash_table,
*/
static void
g_hash_table_remove_all_nodes (GHashTable *hash_table,
- gboolean notify)
+ gboolean notify,
+ gboolean destruction)
{
int i;
gpointer key;
gpointer value;
+ gint old_size;
+ gpointer *old_keys;
+ gpointer *old_values;
+ guint *old_hashes;
+
+ /* If the hash table is already empty, there is nothing to be done. */
+ if (hash_table->nnodes == 0)
+ return;
hash_table->nnodes = 0;
hash_table->noccupied = 0;
@@ -477,23 +494,52 @@ g_hash_table_remove_all_nodes (GHashTable *hash_table,
(hash_table->key_destroy_func == NULL &&
hash_table->value_destroy_func == NULL))
{
- memset (hash_table->hashes, 0, hash_table->size * sizeof (guint));
- memset (hash_table->keys, 0, hash_table->size * sizeof (gpointer));
- memset (hash_table->values, 0, hash_table->size * sizeof (gpointer));
+ if (!destruction)
+ {
+ memset (hash_table->hashes, 0, hash_table->size * sizeof (guint));
+ memset (hash_table->keys, 0, hash_table->size * sizeof (gpointer));
+ memset (hash_table->values, 0, hash_table->size * sizeof (gpointer));
+ }
return;
}
- for (i = 0; i < hash_table->size; i++)
+ /* Keep the old storage space around to iterate over it. */
+ old_size = hash_table->size;
+ old_keys = hash_table->keys;
+ old_values = hash_table->values;
+ old_hashes = hash_table->hashes;
+
+ /* Now create a new storage space; If the table is destroyed we can use the
+ * shortcut of not creating a new storage. This saves the allocation at the
+ * cost of not allowing any recursive access.
+ * However, the application doesn't own any reference anymore, so access
+ * is not allowed. If accesses are done, then either an assert or crash
+ * *will* happen. */
+ g_hash_table_set_shift (hash_table, HASH_TABLE_MIN_SHIFT);
+ if (!destruction)
{
- if (HASH_IS_REAL (hash_table->hashes[i]))
+ hash_table->keys = g_new0 (gpointer, hash_table->size);
+ hash_table->values = hash_table->keys;
+ hash_table->hashes = g_new0 (guint, hash_table->size);
+ }
+ else
+ {
+ hash_table->keys = NULL;
+ hash_table->values = NULL;
+ hash_table->hashes = NULL;
+ }
+
+ for (i = 0; i < old_size; i++)
+ {
+ if (HASH_IS_REAL (old_hashes[i]))
{
- key = hash_table->keys[i];
- value = hash_table->values[i];
+ key = old_keys[i];
+ value = old_values[i];
- hash_table->hashes[i] = UNUSED_HASH_VALUE;
- hash_table->keys[i] = NULL;
- hash_table->values[i] = NULL;
+ old_hashes[i] = UNUSED_HASH_VALUE;
+ old_keys[i] = NULL;
+ old_values[i] = NULL;
if (hash_table->key_destroy_func != NULL)
hash_table->key_destroy_func (key);
@@ -501,11 +547,14 @@ g_hash_table_remove_all_nodes (GHashTable *hash_table,
if (hash_table->value_destroy_func != NULL)
hash_table->value_destroy_func (value);
}
- else if (HASH_IS_TOMBSTONE (hash_table->hashes[i]))
- {
- hash_table->hashes[i] = UNUSED_HASH_VALUE;
- }
}
+
+ /* Destroy old storage space. */
+ if (old_keys != old_values)
+ g_free (old_values);
+
+ g_free (old_keys);
+ g_free (old_hashes);
}
/*
@@ -616,7 +665,7 @@ g_hash_table_maybe_resize (GHashTable *hash_table)
* a similar fashion to g_direct_equal(), but without the overhead of
* a function call.
*
- * Return value: a new #GHashTable
+ * Returns: a new #GHashTable
*/
GHashTable *
g_hash_table_new (GHashFunc hash_func,
@@ -642,7 +691,14 @@ g_hash_table_new (GHashFunc hash_func,
* allocated for the key and value that get called when removing the
* entry from the #GHashTable.
*
- * Return value: a new #GHashTable
+ * Since version 2.42 it is permissible for destroy notify functions to
+ * recursively remove further items from the hash table. This is only
+ * permissible if the application still holds a reference to the hash table.
+ * This means that you may need to ensure that the hash table is empty by
+ * calling g_hash_table_remove_all before releasing the last reference using
+ * g_hash_table_unref().
+ *
+ * Returns: a new #GHashTable
*/
GHashTable *
g_hash_table_new_full (GHashFunc hash_func,
@@ -679,14 +735,14 @@ g_hash_table_new_full (GHashFunc hash_func,
* Initializes a key/value pair iterator and associates it with
* @hash_table. Modifying the hash table after calling this function
* invalidates the returned iterator.
- * |[
+ * |[
* GHashTableIter iter;
* gpointer key, value;
*
* g_hash_table_iter_init (&iter, hash_table);
* while (g_hash_table_iter_next (&iter, &key, &value))
* {
- * /* do something with key and value */
+ * // do something with key and value
* }
* ]|
*
@@ -718,7 +774,7 @@ g_hash_table_iter_init (GHashTableIter *iter,
* pointed to as a result of this advancement. If %FALSE is returned,
* @key and @value are not set, and the iterator becomes invalid.
*
- * Return value: %FALSE if the end of the #GHashTable has been reached.
+ * Returns: %FALSE if the end of the #GHashTable has been reached.
*
* Since: 2.16
*/
@@ -764,7 +820,7 @@ g_hash_table_iter_next (GHashTableIter *iter,
*
* Returns the #GHashTable associated with @iter.
*
- * Return value: the #GHashTable associated with @iter.
+ * Returns: the #GHashTable associated with @iter.
*
* Since: 2.16
*/
@@ -808,6 +864,15 @@ iter_remove_or_steal (RealIter *ri, gboolean notify)
* otherwise you have to make sure that any dynamically allocated
* values are freed yourself.
*
+ * It is safe to continue iterating the #GHashTable afterward:
+ * |[
+ * while (g_hash_table_iter_next (&iter, &key, &value))
+ * {
+ * if (condition)
+ * g_hash_table_iter_remove (&iter);
+ * }
+ * ]|
+ *
* Since: 2.16
*/
void
@@ -997,7 +1062,7 @@ g_hash_table_iter_steal (GHashTableIter *iter)
* Atomically increments the reference count of @hash_table by one.
* This function is MT-safe and may be called from any thread.
*
- * Return value: the passed in #GHashTable
+ * Returns: the passed in #GHashTable
*
* Since: 2.10
*/
@@ -1029,7 +1094,7 @@ g_hash_table_unref (GHashTable *hash_table)
if (g_atomic_int_dec_and_test (&hash_table->ref_count))
{
- g_hash_table_remove_all_nodes (hash_table, TRUE);
+ g_hash_table_remove_all_nodes (hash_table, TRUE, TRUE);
if (hash_table->keys != hash_table->values)
g_free (hash_table->values);
g_free (hash_table->keys);
@@ -1068,7 +1133,7 @@ g_hash_table_destroy (GHashTable *hash_table)
* and has the value %NULL. If you need this distinction, use
* g_hash_table_lookup_extended().
*
- * Return value: (allow-none): the associated value, or %NULL if the key is not found
+ * Returns: (allow-none): the associated value, or %NULL if the key is not found
*/
gpointer
g_hash_table_lookup (GHashTable *hash_table,
@@ -1102,7 +1167,7 @@ g_hash_table_lookup (GHashTable *hash_table,
* whether the %NULL key exists, provided the hash and equal functions
* of @hash_table are %NULL-safe.
*
- * Return value: %TRUE if the key was found in the #GHashTable
+ * Returns: %TRUE if the key was found in the #GHashTable
*/
gboolean
g_hash_table_lookup_extended (GHashTable *hash_table,
@@ -1264,7 +1329,7 @@ g_hash_table_contains (GHashTable *hash_table,
* @hash_table: our #GHashTable
* @key: the key to remove
* @notify: %TRUE if the destroy notify handlers are to be called
- * Return value: %TRUE if a node was found and removed, else %FALSE
+ * Returns: %TRUE if a node was found and removed, else %FALSE
*
* Implements the common logic for the g_hash_table_remove() and
* g_hash_table_steal() functions.
@@ -1358,7 +1423,7 @@ g_hash_table_remove_all (GHashTable *hash_table)
hash_table->version++;
#endif
- g_hash_table_remove_all_nodes (hash_table, TRUE);
+ g_hash_table_remove_all_nodes (hash_table, TRUE, FALSE);
g_hash_table_maybe_resize (hash_table);
}
@@ -1381,7 +1446,7 @@ g_hash_table_steal_all (GHashTable *hash_table)
hash_table->version++;
#endif
- g_hash_table_remove_all_nodes (hash_table, FALSE);
+ g_hash_table_remove_all_nodes (hash_table, FALSE, FALSE);
g_hash_table_maybe_resize (hash_table);
}
@@ -1457,7 +1522,7 @@ g_hash_table_foreach_remove_or_steal (GHashTable *hash_table,
* See #GHashTableIter for an alternative way to loop over the
* key/value pairs in the hash table.
*
- * Return value: the number of key/value pairs removed
+ * Returns: the number of key/value pairs removed
*/
guint
g_hash_table_foreach_remove (GHashTable *hash_table,
@@ -1484,7 +1549,7 @@ g_hash_table_foreach_remove (GHashTable *hash_table,
* See #GHashTableIter for an alternative way to loop over the
* key/value pairs in the hash table.
*
- * Return value: the number of key/value pairs removed.
+ * Returns: the number of key/value pairs removed.
*/
guint
g_hash_table_foreach_steal (GHashTable *hash_table,
@@ -1565,7 +1630,7 @@ g_hash_table_foreach (GHashTable *hash_table,
* (keep in mind that an O(n) find/foreach operation issued for all n
* values in a hash table ends up needing O(n*n) operations).
*
- * Return value: (allow-none): The value of the first key/value pair is returned,
+ * Returns: (allow-none): The value of the first key/value pair is returned,
* for which @predicate evaluates to %TRUE. If no pair with the
* requested property is found, %NULL is returned.
*
@@ -1617,7 +1682,7 @@ g_hash_table_find (GHashTable *hash_table,
*
* Returns the number of elements contained in the #GHashTable.
*
- * Return value: the number of key/value pairs in the #GHashTable.
+ * Returns: the number of key/value pairs in the #GHashTable.
*/
guint
g_hash_table_size (GHashTable *hash_table)
@@ -1634,7 +1699,7 @@ g_hash_table_size (GHashTable *hash_table)
* Retrieves every key inside @hash_table. The returned data is valid
* until changes to the hash release those keys.
*
- * Return value: a #GList containing all the keys inside the hash
+ * Returns: a #GList containing all the keys inside the hash
* table. The content of the list is owned by the hash table and
* should not be modified or freed. Use g_list_free() when done
* using the list.
@@ -1712,7 +1777,7 @@ g_hash_table_get_keys_as_array (GHashTable *hash_table,
* Retrieves every value inside @hash_table. The returned data
* is valid until @hash_table is modified.
*
- * Return value: a #GList containing all the values inside the hash
+ * Returns: a #GList containing all the values inside the hash
* table. The content of the list is owned by the hash table and
* should not be modified or freed. Use g_list_free() when done
* using the list.
@@ -1772,11 +1837,11 @@ g_str_equal (gconstpointer v1,
*
* Converts a string to a hash value.
*
- * This function implements the widely used "djb" hash apparently posted
- * by Daniel Bernstein to comp.lang.c some time ago. The 32 bit
- * unsigned hash value starts at 5381 and for each byte 'c' in the
- * string, is updated: hash = hash * 33 + c. This
- * function uses the signed value of each byte.
+ * This function implements the widely used "djb" hash apparently
+ * posted by Daniel Bernstein to comp.lang.c some time ago. The 32
+ * bit unsigned hash value starts at 5381 and for each byte 'c' in
+ * the string, is updated: `hash = hash * 33 + c`. This function
+ * uses the signed value of each byte.
*
* It can be passed to g_hash_table_new() as the @hash_func parameter,
* when using non-%NULL strings as keys in a #GHashTable.
@@ -1804,8 +1869,8 @@ g_str_hash (gconstpointer v)
* when using opaque pointers compared by pointer value as keys in a
* #GHashTable.
*
- * This hash function is also appropriate for keys that are integers stored
- * in pointers, such as GINT_TO_POINTER (n).
+ * This hash function is also appropriate for keys that are integers
+ * stored in pointers, such as `GINT_TO_POINTER (n)`.
*
* Returns: a hash value corresponding to the key.
*/
@@ -1822,11 +1887,11 @@ g_direct_hash (gconstpointer v)
*
* Compares two #gpointer arguments and returns %TRUE if they are equal.
* It can be passed to g_hash_table_new() as the @key_equal_func
- * parameter, when using opaque pointers compared by pointer value as keys
- * in a #GHashTable.
+ * parameter, when using opaque pointers compared by pointer value as
+ * keys in a #GHashTable.
*
- * This equality function is also appropriate for keys that are integers stored
- * in pointers, such as GINT_TO_POINTER (n).
+ * This equality function is also appropriate for keys that are integers
+ * stored in pointers, such as `GINT_TO_POINTER (n)`.
*
* Returns: %TRUE if the two keys match.
*/
@@ -1848,9 +1913,9 @@ g_direct_equal (gconstpointer v1,
* parameter, when using non-%NULL pointers to integers as keys in a
* #GHashTable.
*
- * Note that this function acts on pointers to #gint, not on #gint directly:
- * if your hash table's keys are of the form
- * GINT_TO_POINTER (n), use g_direct_equal() instead.
+ * Note that this function acts on pointers to #gint, not on #gint
+ * directly: if your hash table's keys are of the form
+ * `GINT_TO_POINTER (n)`, use g_direct_equal() instead.
*
* Returns: %TRUE if the two keys match.
*/
@@ -1869,9 +1934,9 @@ g_int_equal (gconstpointer v1,
* It can be passed to g_hash_table_new() as the @hash_func parameter,
* when using non-%NULL pointers to integer values as keys in a #GHashTable.
*
- * Note that this function acts on pointers to #gint, not on #gint directly:
- * if your hash table's keys are of the form
- * GINT_TO_POINTER (n), use g_direct_hash() instead.
+ * Note that this function acts on pointers to #gint, not on #gint
+ * directly: if your hash table's keys are of the form
+ * `GINT_TO_POINTER (n)`, use g_direct_hash() instead.
*
* Returns: a hash value corresponding to the key.
*/