[kdbus] KDBUS_ITEM_PAYLOAD_OFF items are (once again) relative to msg header
[platform/upstream/glib.git] / glib / ghash.c
index e204a40..b42dd14 100644 (file)
@@ -12,9 +12,7 @@
  * Lesser General Public License for more details.
  *
  * You should have received a copy of the GNU Lesser General Public
- * License along with this library; if not, write to the
- * Free Software Foundation, Inc., 59 Temple Place - Suite 330,
- * Boston, MA 02111-1307, USA.
+ * License along with this library; if not, see <http://www.gnu.org/licenses/>.
  */
 
 /*
@@ -34,6 +32,7 @@
 
 #include "ghash.h"
 
+#include "glib-private.h"
 #include "gstrfuncs.h"
 #include "gatomic.h"
 #include "gtestutils.h"
  *
  * To destroy a #GHashTable use g_hash_table_destroy().
  *
- * <example>
- * <title>Using a GHashTable as a set</title>
- * <para>
- * A common use-case for hash tables is to store information about
- * a set of keys, without associating any particular value with each
+ * A common use-case for hash tables is to store information about a
+ * set of keys, without associating any particular value with each
  * key. GHashTable optimizes one way of doing so: If you store only
  * key-value pairs where key == value, then GHashTable does not
  * allocate memory to store the values, which can be a considerable
- * space saving, if your set is large.
- * </para>
- * <programlisting>
- * GHashTable *
- * set_new (GHashFunc      hash_func,
- *          GEqualFunc     equal_func,
- *          GDestroyNotify destroy)
- * {
- *   return g_hash_table_new_full (hash_func, equal_func, destroy, NULL);
- * }
- *
- * void
- * set_add (GHashTable *set,
- *          gpointer    element)
- * {
- *   g_hash_table_replace (set, element, element);
- * }
- *
- * gboolean
- * set_contains (GHashTable *set,
- *               gpointer    element)
- * {
- *   return g_hash_table_lookup_extended (set, element, NULL, NULL);
- * }
- *
- * gboolean
- * set_remove (GHashTable *set,
- *             gpointer    element)
- * {
- *   return g_hash_table_remove (set, element);
- * }
- * </programlisting>
- * </example>
- *
- * As of version 2.32, there is also a g_hash_table_add() function to
- * add a key to a #GHashTable that is being used as a set.
+ * space saving, if your set is large. The functions
+ * g_hash_table_add() and g_hash_table_contains() are designed to be
+ * used when using #GHashTable this way.
  */
 
 /**
  * GHashTable:
  *
  * The #GHashTable struct is an opaque data structure to represent a
- * <link linkend="glib-Hash-Tables">Hash Table</link>. It should only be
- * accessed via the following functions.
+ * [Hash Table][glib-Hash-Tables]. It should only be accessed via the
+ * following functions.
  */
 
 /**
  * and #gchar* respectively.
  *
  * g_direct_hash() is also the appropriate hash function for keys
- * of the form <literal>GINT_TO_POINTER (n)</literal> (or similar macros).
+ * of the form `GINT_TO_POINTER (n)` (or similar macros).
  *
  * <!-- FIXME: Need more here. --> A good hash functions should produce
  * hash values that are evenly distributed over a fairly large range.
  * 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 <ulink url="https://lwn.net/Articles/474912/">Algorithmic Complexity Attacks</ulink>.
+ * 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
@@ -282,6 +246,9 @@ typedef struct
   int          version;
 } RealIter;
 
+G_STATIC_ASSERT (sizeof (GHashTableIter) == sizeof (RealIter));
+G_STATIC_ASSERT (_g_alignof (GHashTableIter) >= _g_alignof (RealIter));
+
 /* Each table size has an associated prime modulo (the first prime
  * lower than the table size) used to find the initial bucket. Probing
  * then works modulo 2^n. The prime modulo is necessary to get a
@@ -398,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;
@@ -498,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;
@@ -511,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);
@@ -535,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);
 }
 
 /*
@@ -650,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,
@@ -664,10 +679,10 @@ g_hash_table_new (GHashFunc  hash_func,
  * g_hash_table_new_full:
  * @hash_func: a function to create a hash value from a key
  * @key_equal_func: a function to check two keys for equality
- * @key_destroy_func: a function to free the memory allocated for the key
+ * @key_destroy_func: (allow-none): a function to free the memory allocated for the key
  *     used when removing the entry from the #GHashTable, or %NULL
  *     if you don't want to supply such a function.
- * @value_destroy_func: a function to free the memory allocated for the
+ * @value_destroy_func: (allow-none): a function to free the memory allocated for the
  *     value used when removing the entry from the #GHashTable, or %NULL
  *     if you don't want to supply such a function.
  *
@@ -676,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,
@@ -713,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.
- * |[
+ * |[<!-- language="C" -->
  * GHashTableIter iter;
  * gpointer key, value;
  *
  * g_hash_table_iter_init (&iter, hash_table);
  * while (g_hash_table_iter_next (&iter, &key, &value))
  *   {
- *     /&ast; do something with key and value &ast;/
+ *     // do something with key and value
  *   }
  * ]|
  *
@@ -745,14 +767,14 @@ g_hash_table_iter_init (GHashTableIter *iter,
 /**
  * g_hash_table_iter_next:
  * @iter: an initialized #GHashTableIter
- * @key: a location to store the key, or %NULL
- * @value: a location to store the value, or %NULL
+ * @key: (allow-none): a location to store the key, or %NULL
+ * @value: (allow-none): a location to store the value, or %NULL
  *
  * Advances @iter and retrieves the key and/or value that are now
  * 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
  */
@@ -798,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
  */
@@ -842,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:
+ * |[<!-- language="C" -->
+ * while (g_hash_table_iter_next (&iter, &key, &value))
+ *   {
+ *     if (condition)
+ *       g_hash_table_iter_remove (&iter);
+ *   }
+ * ]|
+ *
  * Since: 2.16
  */
 void
@@ -855,7 +886,7 @@ g_hash_table_iter_remove (GHashTableIter *iter)
  * @hash_table: our #GHashTable
  * @node_index: pointer to node to insert/replace
  * @key_hash: key hash
- * @key: key to replace with, or %NULL
+ * @key: (allow-none): key to replace with, or %NULL
  * @value: value to replace with
  * @keep_new_key: whether to replace the key in the node with @key
  * @reusing_key: whether @key was taken out of the existing node
@@ -865,39 +896,79 @@ g_hash_table_iter_remove (GHashTableIter *iter)
  * If @key has been taken out of the existing node (ie it is not
  * passed in via a g_hash_table_insert/replace) call, then @reusing_key
  * should be %TRUE.
+ *
+ * Returns: %TRUE if the key did not exist yet
  */
-static void
+static gboolean
 g_hash_table_insert_node (GHashTable *hash_table,
                           guint       node_index,
                           guint       key_hash,
-                          gpointer    key,
-                          gpointer    value,
+                          gpointer    new_key,
+                          gpointer    new_value,
                           gboolean    keep_new_key,
                           gboolean    reusing_key)
 {
+  gboolean already_exists;
   guint old_hash;
-  gpointer old_key;
-  gpointer old_value;
-
-  if (G_UNLIKELY (hash_table->keys == hash_table->values && key != value))
-    hash_table->values = g_memdup (hash_table->keys, sizeof (gpointer) * hash_table->size);
+  gpointer key_to_free = NULL;
+  gpointer value_to_free = NULL;
 
   old_hash = hash_table->hashes[node_index];
-  old_key = hash_table->keys[node_index];
-  old_value = hash_table->values[node_index];
-
-  if (HASH_IS_REAL (old_hash))
+  already_exists = HASH_IS_REAL (old_hash);
+
+  /* Proceed in three steps.  First, deal with the key because it is the
+   * most complicated.  Then consider if we need to split the table in
+   * two (because writing the value will result in the set invariant
+   * becoming broken).  Then deal with the value.
+   *
+   * There are three cases for the key:
+   *
+   *  - entry already exists in table, reusing key:
+   *    free the just-passed-in new_key and use the existing value
+   *
+   *  - entry already exists in table, not reusing key:
+   *    free the entry in the table, use the new key
+   *
+   *  - entry not already in table:
+   *    use the new key, free nothing
+   *
+   * We update the hash at the same time...
+   */
+  if (already_exists)
     {
+      /* Note: we must record the old value before writing the new key
+       * because we might change the value in the event that the two
+       * arrays are shared.
+       */
+      value_to_free = hash_table->values[node_index];
+
       if (keep_new_key)
-        hash_table->keys[node_index] = key;
-      hash_table->values[node_index] = value;
+        {
+          key_to_free = hash_table->keys[node_index];
+          hash_table->keys[node_index] = new_key;
+        }
+      else
+        key_to_free = new_key;
     }
   else
     {
-      hash_table->keys[node_index] = key;
-      hash_table->values[node_index] = value;
       hash_table->hashes[node_index] = key_hash;
+      hash_table->keys[node_index] = new_key;
+    }
 
+  /* Step two: check if the value that we are about to write to the
+   * table is the same as the key in the same position.  If it's not,
+   * split the table.
+   */
+  if (G_UNLIKELY (hash_table->keys == hash_table->values && hash_table->keys[node_index] != new_value))
+    hash_table->values = g_memdup (hash_table->keys, sizeof (gpointer) * hash_table->size);
+
+  /* Step 3: Actually do the write */
+  hash_table->values[node_index] = new_value;
+
+  /* Now, the bookkeeping... */
+  if (!already_exists)
+    {
       hash_table->nnodes++;
 
       if (HASH_IS_UNUSED (old_hash))
@@ -912,13 +983,15 @@ g_hash_table_insert_node (GHashTable *hash_table,
 #endif
     }
 
-  if (HASH_IS_REAL (old_hash))
+  if (already_exists)
     {
       if (hash_table->key_destroy_func && !reusing_key)
-        hash_table->key_destroy_func (keep_new_key ? old_key : key);
+        (* hash_table->key_destroy_func) (key_to_free);
       if (hash_table->value_destroy_func)
-        hash_table->value_destroy_func (old_value);
+        (* hash_table->value_destroy_func) (value_to_free);
     }
+
+  return !already_exists;
 }
 
 /**
@@ -989,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
  */
@@ -1021,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);
@@ -1060,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,
@@ -1094,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,
@@ -1136,8 +1209,10 @@ g_hash_table_lookup_extended (GHashTable    *hash_table,
  * Do a lookup of @key. If it is found, replace it with the new
  * @value (and perhaps the new @key). If it is not found, create
  * a new node.
+ *
+ * Returns: %TRUE if the key did not exist yet
  */
-static void
+static gboolean
 g_hash_table_insert_internal (GHashTable *hash_table,
                               gpointer    key,
                               gpointer    value,
@@ -1146,11 +1221,11 @@ g_hash_table_insert_internal (GHashTable *hash_table,
   guint key_hash;
   guint node_index;
 
-  g_return_if_fail (hash_table != NULL);
+  g_return_val_if_fail (hash_table != NULL, FALSE);
 
   node_index = g_hash_table_lookup_node (hash_table, key, &key_hash);
 
-  g_hash_table_insert_node (hash_table, node_index, key_hash, key, value, keep_new_key, FALSE);
+  return g_hash_table_insert_node (hash_table, node_index, key_hash, key, value, keep_new_key, FALSE);
 }
 
 /**
@@ -1167,13 +1242,15 @@ g_hash_table_insert_internal (GHashTable *hash_table,
  * value is freed using that function. If you supplied a
  * @key_destroy_func when creating the #GHashTable, the passed
  * key is freed using that function.
+ *
+ * Returns: %TRUE if the key did not exist yet
  */
-void
+gboolean
 g_hash_table_insert (GHashTable *hash_table,
                      gpointer    key,
                      gpointer    value)
 {
-  g_hash_table_insert_internal (hash_table, key, value, FALSE);
+  return g_hash_table_insert_internal (hash_table, key, value, FALSE);
 }
 
 /**
@@ -1189,13 +1266,15 @@ g_hash_table_insert (GHashTable *hash_table,
  * the #GHashTable, the old value is freed using that function.
  * If you supplied a @key_destroy_func when creating the
  * #GHashTable, the old key is freed using that function.
+ *
+ * Returns: %TRUE of the key did not exist yet
  */
-void
+gboolean
 g_hash_table_replace (GHashTable *hash_table,
                       gpointer    key,
                       gpointer    value)
 {
-  g_hash_table_insert_internal (hash_table, key, value, TRUE);
+  return g_hash_table_insert_internal (hash_table, key, value, TRUE);
 }
 
 /**
@@ -1211,13 +1290,15 @@ g_hash_table_replace (GHashTable *hash_table,
  * corresponding value it is able to be stored more efficiently.  See
  * the discussion in the section description.
  *
+ * Returns: %TRUE if the key did not exist yet
+ *
  * Since: 2.32
- **/
-void
+ */
+gboolean
 g_hash_table_add (GHashTable *hash_table,
                   gpointer    key)
 {
-  g_hash_table_insert_internal (hash_table, key, key, TRUE);
+  return g_hash_table_insert_internal (hash_table, key, key, TRUE);
 }
 
 /**
@@ -1248,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.
@@ -1342,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);
 }
 
@@ -1365,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);
 }
 
@@ -1441,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,
@@ -1468,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,
@@ -1549,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.
  *
@@ -1601,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)
@@ -1615,10 +1696,10 @@ g_hash_table_size (GHashTable *hash_table)
  * g_hash_table_get_keys:
  * @hash_table: a #GHashTable
  *
- * Retrieves every key inside @hash_table. The returned data
- * is valid until @hash_table is modified.
+ * 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.
@@ -1644,13 +1725,59 @@ g_hash_table_get_keys (GHashTable *hash_table)
 }
 
 /**
+ * g_hash_table_get_keys_as_array:
+ * @hash_table: a #GHashTable
+ * @length: (out): the length of the returned array
+ *
+ * Retrieves every key inside @hash_table, as an array.
+ *
+ * The returned array is %NULL-terminated but may contain %NULL as a
+ * key.  Use @length to determine the true length if it's possible that
+ * %NULL was used as the value for a key.
+ *
+ * Note: in the common case of a string-keyed #GHashTable, the return
+ * value of this function can be conveniently cast to (gchar **).
+ *
+ * You should always free the return result with g_free().  In the
+ * above-mentioned case of a string-keyed hash table, it may be
+ * appropriate to use g_strfreev() if you call g_hash_table_steal_all()
+ * first to transfer ownership of the keys.
+ *
+ * Returns: (array length=length) (transfer container): a
+ *   %NULL-terminated array containing each key from the table.
+ *
+ * Since: 2.40
+ **/
+gpointer *
+g_hash_table_get_keys_as_array (GHashTable *hash_table,
+                                guint      *length)
+{
+  gpointer *result;
+  guint i, j = 0;
+
+  result = g_new (gpointer, hash_table->nnodes + 1);
+  for (i = 0; i < hash_table->size; i++)
+    {
+      if (HASH_IS_REAL (hash_table->hashes[i]))
+        result[j++] = hash_table->keys[i];
+    }
+  g_assert_cmpint (j, ==, hash_table->nnodes);
+  result[j] = NULL;
+
+  if (length)
+    *length = j;
+
+  return result;
+}
+
+/**
  * g_hash_table_get_values:
  * @hash_table: a #GHashTable
  *
  * 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.
@@ -1710,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: <literal>hash = hash * 33 + c</literal>.  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.
@@ -1742,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 <literal>GINT_TO_POINTER (n)</literal>.
+ * 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.
  */
@@ -1760,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 <literal>GINT_TO_POINTER (n)</literal>.
+ * 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.
  */
@@ -1786,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
- * <literal>GINT_TO_POINTER (n)</literal>, 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.
  */
@@ -1807,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
- * <literal>GINT_TO_POINTER (n)</literal>, 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.
  */