From c1d5c163a89f53a3c6e4e67f5f4119af96f7a470 Mon Sep 17 00:00:00 2001
From: Justus Winter <4winter@informatik.uni-hamburg.de>
Date: Wed, 14 May 2014 16:24:21 +0200
Subject: libihash: optimize lookup-or-insert operations

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.h | 52 ++++++++++++++++++++++++++++++++++++++++++++++++++++
 1 file changed, 52 insertions(+)

(limited to 'libihash/ihash.h')

diff --git a/libihash/ihash.h b/libihash/ihash.h
index 128027a0..1dbc3483 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:
 
-- 
cgit v1.2.3