/* libnih | |

* | |

* hash.c - Fuller/Noll/Vo hash table implementation | |

* | |

* Copyright © 2006 Scott James Remnant <scott@netsplit.com>. | |

* | |

* This program is free software; you can redistribute it and/or modify | |

* it under the terms of the GNU General Public License as published by | |

* the Free Software Foundation; either version 2 of the License, or | |

* (at your option) any later version. | |

* | |

* This program is distributed in the hope that it will be useful, | |

* but WITHOUT ANY WARRANTY; without even the implied warranty of | |

* MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the | |

* GNU General Public License for more details. | |

* | |

* You should have received a copy of the GNU General Public License | |

* along with this program; if not, write to the Free Software | |

* Foundation, Inc., 51 Franklin St, Fifth Floor, Boston, MA 02110-1301 USA | |

*/ | |

#ifdef HAVE_CONFIG_H | |

# include <config.h> | |

#endif /* HAVE_CONFIG_H */ | |

#include <string.h> | |

#include <nih/macros.h> | |

#include <nih/logging.h> | |

#include <nih/alloc.h> | |

#include "hash.h" | |

/** | |

* FNV_PRIME: | |

* | |

* This constant is defined in the FNV description based on the size of | |

* the hash, in our case 32-bits. | |

**/ | |

#define FNV_PRIME 16777619UL | |

/** | |

* FNV_OFFSET_BASIS: | |

* | |

* This constant is also defined in the FNV description and is the result | |

* of hashing a known string wth the FNV-0 algorithm and the above prime. | |

**/ | |

#define FNV_OFFSET_BASIS 2166136261UL | |

/* Prototypes for static functions */ | |

static uint32_t fnv_hash (const char *key); | |

/** | |

* primes: | |

* | |

* Prime numbers always give the best hash table sizes, this is a selected | |

* list of primes giving a reasonable spread. We pick the largest one that | |

* is smaller than the estimated number of entries for the hash. | |

**/ | |

static const uint32_t primes[] = { | |

17, 37, 79, 163, 331, 673, 1259, 2521, 5051, 10103, 20219, 40459, | |

80929, 160231, 320449, 640973, 1281563, 2566637, 5136083, 10250323 | |

}; | |

/** | |

* num_primes: | |

* | |

* Number of prime numbers defined above. | |

**/ | |

static const size_t num_primes = sizeof (primes) / sizeof (uint32_t); | |

/** | |

* fnv_hash: | |

* @key: string key to hash. | |

* | |

* Generates and returns a 32-bit hash for the given string key using the | |

* FNV-1 algorithm as documented at http://www.isthe.com/chongo/tech/comp/fnv/ | |

* | |

* The returned key will need to be bounded within the number of bins | |

* used in the hash table. | |

* | |

* Returns: 32-bit hash. | |

**/ | |

static uint32_t | |

fnv_hash (const char *key) | |

{ | |

register uint32_t hash = FNV_OFFSET_BASIS; | |

nih_assert (key != NULL); | |

while (*key) { | |

hash *= FNV_PRIME; | |

hash ^= *(key++); | |

} | |

return hash; | |

} | |

/** | |

* nih_hash_new: | |

* @entries: rough number of entries expected, | |

* @key_function: function used to obtain keys for entries. | |

* | |

* Allocates a new hash table, the number of buckets selected is a prime | |

* number that is no larger than @entries; this should be set to a rough | |

* number of expected entries to ensure optimum distribution. | |

* | |

* Individual members of the hash table are #NihList members, so to | |

* associate them with a string key @key_function must be provided; this | |

* would ordinarily just return a static string within the entry itself. | |

* | |

* The structure is allocated using #nih_alloc so it can be used as a | |

* context to other allocations. | |

* | |

* Returns: the new hash table or %NULL if the allocation failed. | |

**/ | |

NihHash * | |

nih_hash_new (size_t entries, | |

NihKeyFunction key_function) | |

{ | |

NihHash *hash; | |

size_t i; | |

nih_assert (key_function != NULL); | |

hash = nih_new (NULL, NihHash); | |

if (! hash) | |

return NULL; | |

/* Pick a prime number larger than the number of entries */ | |

hash->size = primes[0]; | |

for (i = 0; (i < num_primes) && (primes[i] < entries); i++) | |

hash->size = primes[i]; | |

/* Allocate bins */ | |

hash->bins = nih_alloc (hash, sizeof (NihList) * hash->size); | |

if (! hash->bins) { | |

nih_free (hash); | |

return NULL; | |

} | |

/* Initialise bins */ | |

for (i = 0; i < hash->size; i++) | |

nih_list_init (&hash->bins[i]); | |

hash->key_function = key_function; | |

return hash; | |

} | |

/** | |

* nih_hash_add: | |

* @hash: destination hash table, | |

* @entry: entry to be added. | |

* | |

* Adds @entry to @hash using the value returned by the hash #NihKeyFunction | |

* to indicate which bin the entry should be placed into. | |

* | |

* For speed reasons, this function does not check whether an entry already | |

* exists with the key. If you need that constraint use either | |

* #nih_hash_add_unique or #nih_hash_replace. | |

* | |

* If @entry is already in another list it is removed so there is no need | |

* to call #nih_list_remove before this function. | |

* | |

* Returns: @entry which is now a member of one of @hash's bins. | |

**/ | |

NihList * | |

nih_hash_add (NihHash *hash, | |

NihList *entry) | |

{ | |

const char *key; | |

NihList *bin; | |

nih_assert (hash != NULL); | |

nih_assert (entry != NULL); | |

key = hash->key_function (entry); | |

bin = &hash->bins[fnv_hash (key) % hash->size]; | |

return nih_list_add (bin, entry); | |

} | |

/** | |

* nih_hash_add_unique: | |

* @hash: destination hash table, | |

* @entry: entry to be added. | |

* | |

* Adds @entry to @hash using the value returned by the hash #NihKeyFunction | |

* to indicate which bin the entry should be placed into, provided the key | |

* is unique. | |

* | |

* Because the hash table does not store the key of each entry, this requires | |

* that #NihKeyFunction be called for each entry in the destination bin, so | |

* should only be used where the uniqueness constraint is required and not | |

* already enforced by other code. | |

* | |

* If @entry is already in another list it is removed so there is no need | |

* to call #nih_list_remove before this function. | |

* | |

* Returns: @entry which is now a member of one of @hash's bins or %NULL if | |

* an entry already existed with the same key. | |

**/ | |

NihList * | |

nih_hash_add_unique (NihHash *hash, | |

NihList *entry) | |

{ | |

const char *key; | |

NihList *bin; | |

nih_assert (hash != NULL); | |

nih_assert (entry != NULL); | |

key = hash->key_function (entry); | |

bin = &hash->bins[fnv_hash (key) % hash->size]; | |

NIH_LIST_FOREACH (bin, iter) { | |

if (! strcmp (key, hash->key_function (iter))) | |

return NULL; | |

} | |

return nih_list_add (bin, entry); | |

} | |

/** | |

* nih_hash_replace: | |

* @hash: destination hash table, | |

* @entry: entry to be added. | |

* | |

* Adds @entry to @hash using the value returned by the hash #NihKeyFunction | |

* to indicate which bin the entry should be placed into, replacing any | |

* existing entry with the same key. | |

* | |

* Because the hash table does not store the key of each entry, this requires | |

* that #NihKeyFunction be called for each entry in the destination bin, so | |

* should only be used where the uniqueness constraint is required and not | |

* already enforced by other code. | |

* | |

* The replaced entry is returned, it is up to the caller to free it and | |

* ensure this does not come as a surprise to other code. | |

* | |

* If @entry is already in another list it is removed so there is no need | |

* to call #nih_list_remove before this function. | |

* | |

* Returns: existing entry with the same key replaced in the table, or %NULL | |

* if no such entry existed. | |

**/ | |

NihList * | |

nih_hash_replace (NihHash *hash, | |

NihList *entry) | |

{ | |

const char *key; | |

NihList *bin, *ret = NULL; | |

nih_assert (hash != NULL); | |

nih_assert (entry != NULL); | |

key = hash->key_function (entry); | |

bin = &hash->bins[fnv_hash (key) % hash->size]; | |

NIH_LIST_FOREACH (bin, iter) { | |

if (! strcmp (key, hash->key_function (iter))) { | |

ret = nih_list_remove (iter); | |

break; | |

} | |

} | |

nih_list_add (bin, entry); | |

return ret; | |

} | |

/** | |

* nih_hash_search: | |

* @hash: hash table to search, | |

* @key: key to look for, | |

* @entry: previous entry found. | |

* | |

* Finds all entries in @hash with a key of @key by calling the hash's | |

* #NihKeyFunction on each entry in the appropriate bin, starting with @entry, | |

* until one is found. | |

* | |

* The initial @entry can be found by passing %NULL or using #nih_hash_lookup. | |

* | |

* Returns: next entry in the hash or %NULL if there are no more entries. | |

**/ | |

NihList * | |

nih_hash_search (NihHash *hash, | |

const char *key, | |

NihList *entry) | |

{ | |

NihList *bin; | |

nih_assert (hash != NULL); | |

nih_assert (key != NULL); | |

bin = &hash->bins[fnv_hash (key) % hash->size]; | |

NIH_LIST_FOREACH (bin, iter) { | |

if (iter == entry) { | |

entry = NULL; | |

continue; | |

} else if (entry) { | |

continue; | |

} else if (! strcmp (key, hash->key_function (iter))) { | |

return iter; | |

} | |

} | |

return NULL; | |

} | |

/** | |

* nih_hash_lookup: | |

* @hash: hash table to search. | |

* @key: key to look for. | |

* | |

* Finds the first entry in @hash with a key of @key by calling the hash's | |

* #NihKeyFunction on each entry in the appropriate bin until one is found. | |

* | |

* If multiple entries are expected, use #nih_hash_search instead. | |

* | |

* Returns: entry found or %NULL if no entry existed. | |

**/ | |

NihList * | |

nih_hash_lookup (NihHash *hash, | |

const char *key) | |

{ | |

return nih_hash_search (hash, key, NULL); | |

} |