From 2c4b1db9c9760205979d22b721c324cf215987da Mon Sep 17 00:00:00 2001 From: Justus Winter <4winter@informatik.uni-hamburg.de> Date: Sat, 21 Nov 2015 16:27:40 +0100 Subject: 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(-) (limited to 'libihash') diff --git a/libihash/ihash.c b/libihash/ihash.c index 598d3412..451f8db6 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 . @@ -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 fdfc3673..28fefe80 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 . Revised by Marcus Brinkmann . @@ -56,6 +56,20 @@ typedef uintptr_t hurd_ihash_key_t; value stored in the hash table. */ 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. */ @@ -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 -- cgit v1.2.3