Goto sanos source index
//
// hash.c
//
// A hashed lookup mechanism
//
// Copyright (C) 2002 Michael Ringgaard. All rights reserved.
//
// Redistribution and use in source and binary forms, with or without
// modification, are permitted provided that the following conditions
// are met:
//
// 1. Redistributions of source code must retain the above copyright
// notice, this list of conditions and the following disclaimer.
// 2. Redistributions in binary form must reproduce the above copyright
// notice, this list of conditions and the following disclaimer in the
// documentation and/or other materials provided with the distribution.
// 3. Neither the name of the project nor the names of its contributors
// may be used to endorse or promote products derived from this software
// without specific prior written permission.
//
// THIS SOFTWARE IS PROVIDED BY THE COPYRIGHT HOLDERS AND CONTRIBUTORS "AS IS" AND
// ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE
// IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE
// ARE DISCLAIMED. IN NO EVENT SHALL THE COPYRIGHT OWNER OR CONTRIBUTORS BE LIABLE
// FOR ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL, EXEMPLARY, OR CONSEQUENTIAL
// DAMAGES (INCLUDING, BUT NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS
// OR SERVICES; LOSS OF USE, DATA, OR PROFITS; OR BUSINESS INTERRUPTION)
// HOWEVER CAUSED AND ON ANY THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT
// LIABILITY, OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY
// OUT OF THE USE OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF
// SUCH DAMAGE.
//
#include <stdlib.h>
#include <string.h>
#include <errno.h>
#include <hash.h>
//
// hashval
//
// Convert key into hash value
//
__inline unsigned int hashidx(unsigned long key, unsigned int mask) {
return (key ^ (key >> 2) ^ (key >> 6)) & mask;
}
//
// hash_alloc
//
// Allocate a hash data structure of the given hash size
//
// For speed we always round the hash table size to the nearest power
// of 2 above the requested size.
//
struct hash *hash_alloc(int hashsize) {
struct hash *h;
int i = 3, hashlim = 8;
// Adjust hash size to the next power of 2
while (hashsize > hashlim) {
i++;
hashlim <<= 1;
}
h = malloc(sizeof(struct hash) + hashlim * sizeof(struct hash_node *));
if (h) {
h->hashsize = hashlim;
h->hashmask = hashlim - 1;
memset(&h->buckets, 0, hashlim * sizeof(struct hash_node *));
}
return h;
}
//
// hash_insert
//
// Insert a new key/value pair into the hash
//
int hash_insert(struct hash *h, unsigned long key, void *val) {
struct hash_node *hn;
unsigned int idx;
if (!h) return -EINVAL;
idx = hashidx(key, h->hashmask);
hn = malloc(sizeof(struct hash_node));
if (!hn) return -ENOMEM;
hn->key = key;
hn->data = val;
hn->next = h->buckets[idx];
h->buckets[idx] = hn;
return 0;
}
//
// hash_delete
//
// Remove node from hash
//
int hash_delete(struct hash *h, unsigned long key) {
struct hash_node **hnp, *hn;
unsigned int idx;
if (!h) return -EINVAL;
// Walk hash chain list. Walk both the pointer, as
// well as a pointer to the previous pointer. When
// we find the node, patch out the current node and
// free it.
idx = hashidx(key, h->hashmask);
hnp = &h->buckets[idx];
hn = *hnp;
while (hn) {
if (hn->key == key) {
*hnp = hn->next;
free(hn);
return 0;
}
hnp = &hn->next;
hn = *hnp;
}
return -ESRCH;
}
//
// hash_dealloc
//
// Free up the entire hash structure
//
void hash_dealloc(struct hash *h) {
int x;
struct hash_node *hn, *hnn;
for (x = 0; x < h->hashsize; x++) {
for (hn = h->buckets[x]; hn; hn = hnn) {
hnn = hn->next;
free(hn);
}
}
free(h);
}
//
// hash_lookup
//
// Look up a node based on its key
//
void *hash_lookup(struct hash *h, unsigned long key) {
struct hash_node *hn;
unsigned int idx;
if (!h) return NULL;
idx = hashidx(key, h->hashmask);
for (hn = h->buckets[idx]; hn; hn = hn->next) {
if (hn->key == key) return hn->data;
}
return NULL;
}
//
// hash_size
//
// Tell how many elements are stored in the hash
//
int hash_size(struct hash *h) {
int x, cnt = 0;
struct hash_node *hn;
for (x = 0; x < h->hashsize; x++) {
for (hn = h->buckets[x]; hn; hn = hn->next) {
cnt += 1;
}
}
return cnt;
}
//
// hash_foreach
//
// Enumerate each entry in the hash, invoking a function
//
int hash_foreach(struct hash *h, enumfunc_t f, void *arg) {
int x;
int rc;
struct hash_node *hn;
for (x = 0; x < h->hashsize; x++) {
for (hn = h->buckets[x]; hn; hn = hn->next) {
rc = (*f)(hn->key, hn->data, arg);
if (rc) return rc;
}
}
return 0;
}