[PATCH 4/5] libihash: optimize lookup-or-insert operations

[Justus Winter]

If libihash is used to implement a cache, a insertion is always
preceeded by a lookup.  hurd_ihash_add has to do the lookup again.

Provide a new pair of functions, hurd_ihash_locp_add and
hurd_ihash_locp_find, that can be used in combination to avoid the
second lookup.

* libihash/ihash.c (hurd_ihash_locp_add): New function using a
location pointer...
(hurd_ihash_locp_find): ... that has been returned by this function.
* libihash/ihash.h (hurd_ihash_locp_add): New declaration.
(hurd_ihash_locp_find): Likewise.
(hurd_ihash_locp_value): New function.
---
 libihash/ihash.c | 78 +++++++++++++++++++++++++++++++++++++++++++++++++++++++-
 libihash/ihash.h | 52 +++++++++++++++++++++++++++++++++++++
 2 files changed, 129 insertions(+), 1 deletion(-)

diff --git a/libihash/ihash.c b/libihash/ihash.c
index 5b7b542..167c872 100644
--- a/libihash/ihash.c
+++ b/libihash/ihash.c
@@ -258,7 +258,54 @@ add_one (hurd_ihash_t ht, hurd_ihash_key_t key, 
hurd_ihash_value_t value)
   return 0;
 }
 
-  
+
+/* Add VALUE to the hash table HT under the key KEY at LOCP.  If there
+   already is an item under this key, call the cleanup function (if
+   any) for it before overriding the value.  This function is faster
+   than hurd_ihash_add.
+
+   If LOCP is NULL, fall back to hurd_ihash_add.  Otherwise, LOCP must
+   be valid and may either be obtained from hurd_ihash_locp_find, or
+   from an item that is currently in the hash table.  If an item is
+   replaced, KEY must match the key of the previous item.
+
+   If a memory allocation error occurs, ENOMEM is returned, otherwise
+   0.  */
+error_t
+hurd_ihash_locp_add (hurd_ihash_t ht, hurd_ihash_locp_t locp,
+                     hurd_ihash_key_t key, hurd_ihash_value_t value)
+{
+  struct _hurd_ihash_item *item = (struct _hurd_ihash_item *) locp;
+
+  /* In case of complications, fall back to hurd_ihash_add.  */
+  if (ht->size == 0
+      || item == NULL
+      || item->value == _HURD_IHASH_DELETED
+      || hurd_ihash_get_load (ht) > ht->max_load)
+    return hurd_ihash_add (ht, key, value);
+
+  if (item->value == _HURD_IHASH_EMPTY)
+    {
+      item->key = key;
+      ht->nr_items += 1;
+    }
+  else
+    {
+      assert (item->key == key);
+      if (ht->cleanup)
+        (*ht->cleanup) (locp, ht->cleanup_data);
+    }
+
+  item->value = value;
+
+  if (ht->locp_offset != HURD_IHASH_NO_LOCP)
+    *((hurd_ihash_locp_t *) (((char *) value) + ht->locp_offset))
+      = locp;
+
+  return 0;
+}
+
+
 /* Add ITEM to the hash table HT under the key KEY.  If there already
    is an item under this key, call the cleanup function (if any) for
    it before overriding the value.  If a memory allocation error
@@ -327,6 +374,35 @@ hurd_ihash_find (hurd_ihash_t ht, hurd_ihash_key_t key)
     }
 }
 
+/* Find the item in the hash table HT with key KEY.  If it is found,
+   return the location of its slot in the hash table.  If it is not
+   found, this function may still return a location.
+
+   This location pointer can always be safely accessed using
+   hurd_ihash_locp_value.  If the lookup is successful,
+   hurd_ihash_locp_value will return the value related to KEY.
+
+   If the lookup is successful, the returned location can be used with
+   hurd_ihash_locp_add to update the item, and with
+   hurd_ihash_locp_remove to remove it.
+
+   If the lookup is not successful, the returned location can be used
+   with hurd_ihash_locp_add to add the item.
+
+   Note that returned location is only valid until the next insertion
+   or deletion.  */
+hurd_ihash_locp_t
+hurd_ihash_locp_find (hurd_ihash_t ht, hurd_ihash_key_t key)
+{
+  int idx;
+
+  if (ht->size == 0)
+    return NULL;
+
+  idx = find_index (ht, key);
+  return &ht->items[idx].value;
+}
+
 
 /* Remove the entry with the key KEY from the hash table HT.  If such
    an entry was found and removed, 1 is returned, otherwise 0.  */
diff --git a/libihash/ihash.h b/libihash/ihash.h
index 394bcf9..f7ecf1b 100644
--- a/libihash/ihash.h
+++ b/libihash/ihash.h
@@ -26,6 +26,7 @@
 #include <sys/types.h>
 #include <limits.h>
 #include <stdint.h>
+#include <stddef.h>
 
 
 /* The type of the values corresponding to the keys.  Must be a
@@ -198,10 +199,61 @@ hurd_ihash_get_load (hurd_ihash_t ht)
 error_t hurd_ihash_add (hurd_ihash_t ht, hurd_ihash_key_t key,
                        hurd_ihash_value_t item);
 
+/* Add VALUE to the hash table HT under the key KEY at LOCP.  If there
+   already is an item under this key, call the cleanup function (if
+   any) for it before overriding the value.  This function is faster
+   than hurd_ihash_add.
+
+   If LOCP is NULL, fall back to hurd_ihash_add.  Otherwise, LOCP must
+   be valid and may either be obtained from hurd_ihash_locp_find, or
+   from an item that is currently in the hash table.  If an item is
+   replaced, KEY must match the key of the previous item.
+
+   If a memory allocation error occurs, ENOMEM is returned, otherwise
+   0.  */
+error_t hurd_ihash_locp_add (hurd_ihash_t ht, hurd_ihash_locp_t locp,
+                             hurd_ihash_key_t key, hurd_ihash_value_t value);
+
 /* Find and return the item in the hash table HT with key KEY, or NULL
    if it doesn't exist.  */
 hurd_ihash_value_t hurd_ihash_find (hurd_ihash_t ht, hurd_ihash_key_t key);
 
+/* Find the item in the hash table HT with key KEY.  If it is found,
+   return the location of its slot in the hash table.  If it is not
+   found, this function may still return a location.
+
+   This location pointer can always be safely accessed using
+   hurd_ihash_locp_value.  If the lookup is successful,
+   hurd_ihash_locp_value will return the value related to KEY.
+
+   If the lookup is successful, the returned location can be used with
+   hurd_ihash_locp_add to update the item, and with
+   hurd_ihash_locp_remove to remove it.
+
+   If the lookup is not successful, the returned location can be used
+   with hurd_ihash_locp_add to add the item.
+
+   Note that returned location is only valid until the next insertion
+   or deletion.  */
+hurd_ihash_locp_t hurd_ihash_locp_find (hurd_ihash_t ht,
+                                        hurd_ihash_key_t key);
+
+/* Given an hash table bucket location LOCP, return the value stored
+   there, or NULL if it is empty or LOCP is NULL.  */
+static inline void *
+hurd_ihash_locp_value (hurd_ihash_locp_t locp)
+{
+  struct _hurd_ihash_item *item = (struct _hurd_ihash_item *) locp;
+
+  if (item == NULL)
+    return NULL;
+
+  if (hurd_ihash_value_valid (item->value))
+    return item->value;
+
+  return NULL;
+}
+
 /* Iterate over all elements in the hash table.  You use this macro
    with a block, for example like this:
 
-- 
2.0.0.rc0