[hurd] 27/75: libihash: generalize the interface to support non-integer keys

[Samuel Thibault]

This is an automated email from the git hooks/post-receive script.

sthibault pushed a commit to branch dde
in repository hurd.

commit 2c4b1db9c9760205979d22b721c324cf215987da
Author: Justus Winter <address@hidden>
Date:   Sat Nov 21 16:27:40 2015 +0100

    libihash: generalize the interface to support non-integer keys
    
    * libihash/ihash.c (hash, compare): New functions that are used
    throughout libihash to hash and compare keys.
    (hurd_ihash_set_gki): New function.
    * libihash/ihash.h (hurd_ihash_fct_hash_t): New type for hash functions.
    (hurd_ihash_fct_cmp_t): New type for comparison functions.
    (struct hurd_ihash): New fields for hash and comparison functions.
    (HURD_IHASH_INITIALIZER_GKI): New static initializer.
    (hurd_ihash_set_gki): New prototype.
---
 libihash/ihash.c | 60 +++++++++++++++++++++++++++++++++++++++++++++-----------
 libihash/ihash.h | 36 +++++++++++++++++++++++++++++++++-
 2 files changed, 84 insertions(+), 12 deletions(-)

diff --git a/libihash/ihash.c b/libihash/ihash.c
index 598d341..451f8db 100644
--- a/libihash/ihash.c
+++ b/libihash/ihash.c
@@ -1,5 +1,5 @@
 /* ihash.c - Integer-keyed hash table functions.
-   Copyright (C) 1993-1997, 2001, 2003, 2004, 2006
+   Copyright (C) 1993-1997, 2001, 2003, 2004, 2006, 2014, 2015
      Free Software Foundation, Inc.
    Written by Michael I. Bushnell.
    Revised by Miles Bader <address@hidden>.
@@ -32,6 +32,23 @@
 
 #include "ihash.h"
 
+/* This function is used to hash the key.  */
+static inline hurd_ihash_key_t
+hash (hurd_ihash_t ht, hurd_ihash_key_t k)
+{
+  return ht->fct_hash ? ht->fct_hash ((const void *) k) : k;
+}
+
+/* This function is used to compare the key.  Returns true if A is
+   equal to B.  */
+static inline int
+compare (hurd_ihash_t ht, hurd_ihash_key_t a, hurd_ihash_key_t b)
+{
+  return
+    ht->fct_cmp ? (a && ht->fct_cmp ((const void *) a, (const void *) b))
+               : a == b;
+}
+
 /* Return 1 if the slot with the index IDX in the hash table HT is
    empty, and 0 otherwise.  */
 static inline int
@@ -46,7 +63,7 @@ index_empty (hurd_ihash_t ht, unsigned int idx)
 static inline int
 index_valid (hurd_ihash_t ht, unsigned int idx, hurd_ihash_key_t key)
 {
-  return !index_empty (ht, idx) && ht->items[idx].key == key;
+  return !index_empty (ht, idx) && compare (ht, ht->items[idx].key, key);
 }
 
 
@@ -60,9 +77,10 @@ find_index (hurd_ihash_t ht, hurd_ihash_key_t key)
   unsigned int up_idx;
   unsigned int mask = ht->size - 1;
 
-  idx = key & mask;
+  idx = hash (ht, key) & mask;
 
-  if (ht->items[idx].value == _HURD_IHASH_EMPTY || ht->items[idx].key == key)
+  if (ht->items[idx].value == _HURD_IHASH_EMPTY
+      || compare (ht, ht->items[idx].key, key))
     return idx;
 
   up_idx = idx;
@@ -71,7 +89,7 @@ find_index (hurd_ihash_t ht, hurd_ihash_key_t key)
     {
       up_idx = (up_idx + 1) & mask;
       if (ht->items[up_idx].value == _HURD_IHASH_EMPTY
-         || ht->items[up_idx].key == key)
+         || compare (ht, ht->items[up_idx].key, key))
        return up_idx;
     }
   while (up_idx != idx);
@@ -88,9 +106,11 @@ find_index (hurd_ihash_t ht, hurd_ihash_key_t key)
 static inline void
 locp_remove (hurd_ihash_t ht, hurd_ihash_locp_t locp)
 {
+  struct _hurd_ihash_item *item = locp;
   if (ht->cleanup)
-    (*ht->cleanup) (*locp, ht->cleanup_data);
-  *locp = _HURD_IHASH_DELETED;
+    (*ht->cleanup) (item->value, ht->cleanup_data);
+  item->value = _HURD_IHASH_DELETED;
+  item->key = 0;
   ht->nr_items--;
 }
 
@@ -106,6 +126,8 @@ hurd_ihash_init (hurd_ihash_t ht, intptr_t locp_offs)
   ht->locp_offset = locp_offs;
   ht->max_load = HURD_IHASH_MAX_LOAD_DEFAULT;
   ht->cleanup = 0;
+  ht->fct_hash = NULL;
+  ht->fct_cmp = NULL;
 }
 
 
@@ -166,6 +188,21 @@ hurd_ihash_set_cleanup (hurd_ihash_t ht, 
hurd_ihash_cleanup_t cleanup,
 }
 
 
+/* Use the generalized key interface.  Must be called before any item
+   is inserted into the table.  */
+void
+hurd_ihash_set_gki (hurd_ihash_t ht,
+                   hurd_ihash_fct_hash_t fct_hash,
+                   hurd_ihash_fct_cmp_t fct_cmp)
+{
+  assert (ht->size == 0 || !"called after insertion");
+  assert (fct_hash);
+  assert (fct_cmp);
+  ht->fct_hash = fct_hash;
+  ht->fct_cmp = fct_cmp;
+}
+
+
 /* Set the maximum load factor in binary percent to MAX_LOAD, which
    should be between 64 and 128.  The default is
    HURD_IHASH_MAX_LOAD_DEFAULT.  New elements are only added to the
@@ -199,10 +236,11 @@ add_one (hurd_ihash_t ht, hurd_ihash_key_t key, 
hurd_ihash_value_t value)
   unsigned int first_free;
   unsigned int mask = ht->size - 1;
 
-  idx = key & mask;
+  idx = hash (ht, key) & mask;
   first_free = idx;
 
-  if (ht->items[idx].value != _HURD_IHASH_EMPTY && ht->items[idx].key != key)
+  if (ht->items[idx].value != _HURD_IHASH_EMPTY
+      && ! compare (ht, ht->items[idx].key, key))
     {
       unsigned int up_idx = idx;
 
@@ -210,7 +248,7 @@ add_one (hurd_ihash_t ht, hurd_ihash_key_t key, 
hurd_ihash_value_t value)
        {
         up_idx = (up_idx + 1) & mask;
          if (ht->items[up_idx].value == _HURD_IHASH_EMPTY
-             || ht->items[up_idx].key == key)
+             || compare (ht, ht->items[up_idx].key, key))
            {
              idx = up_idx;
              break;
@@ -278,7 +316,7 @@ hurd_ihash_locp_add (hurd_ihash_t ht, hurd_ihash_locp_t 
locp,
     }
   else
     {
-      assert (item->key == key);
+      assert (compare (ht, item->key, key));
       if (ht->cleanup)
         (*ht->cleanup) (locp, ht->cleanup_data);
     }
diff --git a/libihash/ihash.h b/libihash/ihash.h
index fdfc367..28fefe8 100644
--- a/libihash/ihash.h
+++ b/libihash/ihash.h
@@ -1,5 +1,5 @@
 /* ihash.h - Integer keyed hash table interface.
-   Copyright (C) 1995, 2003, 2004 Free Software Foundation, Inc.
+   Copyright (C) 1995, 2003, 2004, 2014, 2015 Free Software Foundation, Inc.
    Written by Miles Bader <address@hidden>.
    Revised by Marcus Brinkmann <address@hidden>.
 
@@ -57,6 +57,20 @@ typedef uintptr_t hurd_ihash_key_t;
 typedef hurd_ihash_value_t *hurd_ihash_locp_t;
 
 
+/* We support non-integer keys using the generalized key interface.
+
+   To use it, supply a pair of functions matching the following
+   specification, and use pointers to the key instead of the key
+   itself in all calls to libihash.  */
+
+/* The type of a function computing a hash for the given key.  */
+typedef hurd_ihash_key_t (*hurd_ihash_fct_hash_t) (const void *);
+
+/* The type of a function comparing two given keys.  Return true if
+   both keys are equal.  */
+typedef int (*hurd_ihash_fct_cmp_t) (const void *, const void *);
+
+
 /* The type of the cleanup function, which is called for every value
    removed from the hash table.  */
 typedef void (*hurd_ihash_cleanup_t) (hurd_ihash_value_t value, void *arg);
@@ -95,6 +109,10 @@ struct hurd_ihash
      second argument.  This does not happen if CLEANUP is NULL.  */
   hurd_ihash_cleanup_t cleanup;
   void *cleanup_data;
+
+  /* User-supplied functions for the generalized key interface.  */
+  hurd_ihash_fct_hash_t fct_hash;
+  hurd_ihash_fct_cmp_t fct_cmp;
 };
 typedef struct hurd_ihash *hurd_ihash_t;
 
@@ -118,6 +136,16 @@ typedef struct hurd_ihash *hurd_ihash_t;
     .max_load = HURD_IHASH_MAX_LOAD_DEFAULT,                           \
     .locp_offset = (locp_offs)}
 
+#define HURD_IHASH_INITIALIZER_GKI(locp_offs, f_clean, f_clean_data,   \
+                                  f_hash, f_compare)                   \
+  { .nr_items = 0, .size = 0,                                          \
+    .cleanup = (f_clean),                                              \
+    .cleanup_data = (f_clean_data),                                    \
+    .max_load = HURD_IHASH_MAX_LOAD_DEFAULT,                           \
+    .locp_offset = (locp_offs),                                                
\
+    .fct_hash = (f_hash),                                              \
+    .fct_cmp = (f_compare)}                                            \
+
 /* Initialize the hash table at address HT.  If LOCP_OFFSET is not
    HURD_IHASH_NO_LOCP, then this is an offset (in bytes) from the
    address of a hash value where a location pointer can be found.  The
@@ -152,6 +180,12 @@ void hurd_ihash_free (hurd_ihash_t ht);
 void hurd_ihash_set_cleanup (hurd_ihash_t ht, hurd_ihash_cleanup_t cleanup,
                             void *cleanup_data);
 
+/* Use the generalized key interface.  Must be called before any item
+   is inserted into the table. */
+void hurd_ihash_set_gki (hurd_ihash_t ht,
+                        hurd_ihash_fct_hash_t fct_hash,
+                        hurd_ihash_fct_cmp_t fct_cmp);
+
 /* Set the maximum load factor in binary percent to MAX_LOAD, which
    should be between 64 and 128.  The default is
    HURD_IHASH_MAX_LOAD_DEFAULT.  New elements are only added to the

-- 
Alioth's /usr/local/bin/git-commit-notice on 
/srv/git.debian.org/git/pkg-hurd/hurd.git