/* libnih | |

* | |

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

* | |

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

* Copyright © 2009 Canonical Ltd. | |

* | |

* Permission is hereby granted, free of charge, to any person obtaining | |

* a copy of this software and associated documentation files (the | |

* "Software"), to deal in the Software without restriction, including | |

* without limitation the rights to use, copy, modify, merge, publish, | |

* distribute, sublicense, and/or sell copies of the Software, and to | |

* permit persons to whom the Software is furnished to do so, subject to | |

* the following conditions: | |

* | |

* The above copyright notice and this permission notice shall be | |

* included in all copies or substantial portions of the Software. | |

* | |

* THE SOFTWARE IS PROVIDED "AS IS", WITHOUT WARRANTY OF ANY KIND, | |

* EXPRESS OR IMPLIED, INCLUDING BUT NOT LIMITED TO THE WARRANTIES OF | |

* MERCHANTABILITY, FITNESS FOR A PARTICULAR PURPOSE AND NONINFRINGEMENT. | |

* IN NO EVENT SHALL THE AUTHORS OR COPYRIGHT HOLDERS BE LIABLE FOR | |

* ANY CLAIM, DAMAGES OR OTHER LIABILITY, WHETHER IN AN ACTION OF | |

* CONTRACT, TORT OR OTHERWISE, ARISING FROM, OUT OF OR IN CONNECTION | |

* WITH THE SOFTWARE OR THE USE OR OTHER DEALINGS IN THE SOFTWARE. | |

*/ | |

#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 | |

/** | |

* 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); | |

/** | |

* nih_hash_new: | |

* @parent: parent of new hash, | |

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

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

* @hash_function: function used to obtain hash for keys, | |

* @cmp_function: function used to compare keys. | |

* | |

* 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 constant key @key_function must be provided, to | |

* convert that key into a hash @hash_function must be provided and to | |

* compare keys @cmp_function must be provided. The nih_hash_string_new() | |

* macro wraps this function for the most common case of a string key as | |

* the first structure member. | |

* | |

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

* context to other allocations; there is no non-allocated version of this | |

* function because the hash must be usable as a parent context to its bins. | |

* | |

* If @parent is not NULL, it should be a pointer to another object which | |

* will be used as a parent for the returned hash table. When all parents | |

* of the returned hash table are freed, the returned hash table will also be | |

* freed. | |

* | |

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

**/ | |

NihHash * | |

nih_hash_new (const void *parent, | |

size_t entries, | |

NihKeyFunction key_function, | |

NihHashFunction hash_function, | |

NihCmpFunction cmp_function) | |

{ | |

NihHash *hash; | |

size_t i; | |

nih_assert (key_function != NULL); | |

nih_assert (hash_function != NULL); | |

nih_assert (cmp_function != NULL); | |

hash = nih_new (parent, NihHash); | |

if (! hash) | |

return NULL; | |

/* Pick the largest prime number smaller 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; | |

hash->hash_function = hash_function; | |

hash->cmp_function = cmp_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 functions | |

* 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 void *key; | |

uint32_t hashval; | |

NihList *bin; | |

nih_assert (hash != NULL); | |

nih_assert (entry != NULL); | |

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

hashval = hash->hash_function (key) % hash->size; | |

bin = &hash->bins[hashval]; | |

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 functions | |

* 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 the key function 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 void *key; | |

uint32_t hashval; | |

NihList *bin; | |

nih_assert (hash != NULL); | |

nih_assert (entry != NULL); | |

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

hashval = hash->hash_function (key) % hash->size; | |

bin = &hash->bins[hashval]; | |

NIH_LIST_FOREACH (bin, iter) { | |

if (! hash->cmp_function (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 functions | |

* 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 the key function 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 void *key; | |

uint32_t hashval; | |

NihList *bin, *ret = NULL; | |

nih_assert (hash != NULL); | |

nih_assert (entry != NULL); | |

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

hashval = hash->hash_function (key) % hash->size; | |

bin = &hash->bins[hashval]; | |

NIH_LIST_FOREACH (bin, iter) { | |

if (! hash->cmp_function (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 | |

* key function 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 void *key, | |

NihList *entry) | |

{ | |

uint32_t hashval; | |

NihList *bin; | |

nih_assert (hash != NULL); | |

nih_assert (key != NULL); | |

hashval = hash->hash_function (key) % hash->size; | |

bin = &hash->bins[hashval]; | |

NIH_LIST_FOREACH (bin, iter) { | |

if (iter == entry) { | |

entry = NULL; | |

continue; | |

} else if (entry) { | |

continue; | |

} else if (! hash->cmp_function (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 void *key) | |

{ | |

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

} | |

/** | |

* nih_hash_string_key: | |

* @entry: entry to create key for. | |

* | |

* Key function that can be used for any list entry where the first member | |

* immediately after the list header is a pointer to the string containing | |

* the name. | |

* | |

* Returns: pointer to that string. | |

**/ | |

const char * | |

nih_hash_string_key (NihList *entry) | |

{ | |

nih_assert (entry != NULL); | |

return *((const char **)((char *)entry + sizeof (NihList))); | |

} | |

/** | |

* nih_hash_string_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. | |

**/ | |

uint32_t | |

nih_hash_string_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_string_cmp: | |

* @key1: key to compare, | |

* @key2: key to compare against. | |

* | |

* Compares @key1 to @key2 case-sensitively. | |

* | |

* Returns: integer less than, equal to or greater than zero if @key1 is | |

* respectively less then, equal to or greater than @key2. | |

**/ | |

int | |

nih_hash_string_cmp (const char *key1, | |

const char *key2) | |

{ | |

nih_assert (key1 != NULL); | |

nih_assert (key2 != NULL); | |

return strcmp (key1, key2); | |

} |