kern/src/hashtable.c

/* Copyright (C) 2002, 2004 Christopher Clark  <firstname.lastname@cl.cam.ac.uk>
 *
 * Modified 2009 by Barret Rhoden <brho@cs.berkeley.edu>
 * Changes include:
 *   - No longer frees keys or values.  It's up to the client to do that.
 *   - Uses the slab allocator for hash entry allocation.
 *   - Merges the iterator code with the main hash table code, mostly to avoid
 *   externing the hentry cache. */

#include <arch/types.h>
#include <assert.h>
#include <hash.h>
#include <hashtable.h>
#include <kmalloc.h>
#include <ros/common.h>
#include <slab.h>
#include <stdio.h>
#include <string.h>

/*
Credit for primes table: Aaron Krowne
 http://br.endernet.org/~akrowne/
 http://planetmath.org/encyclopedia/GoodHashTablePrimes.html
*/
static const unsigned int primes[] = {
    53,        97,        193,       389,       769,       1543,     3079,
    6151,      12289,     24593,     49157,     98317,     196613,   393241,
    786433,    1572869,   3145739,   6291469,   12582917,  25165843, 50331653,
    100663319, 201326611, 402653189, 805306457, 1610612741};
const unsigned int prime_table_length = sizeof(primes) / sizeof(primes[0]);
#define APPLY_MAX_LOAD_FACTOR(size) ((size * 13) / 20)
// const float max_load_factor = 0.65;

struct kmem_cache *hentry_cache;

/* Call this once on bootup, after initializing the slab allocator.  */
void hashtable_init(void)
{
	hentry_cache = kmem_cache_create("hash_entry",
					 sizeof(struct hash_entry),
					 __alignof__(struct hash_entry), 0,
					 NULL, 0, 0, NULL);
}

/* Common hash/equals functions.  Don't call these directly. */
size_t __generic_hash(void *k)
{
	return hash_long((unsigned long)k, BITS_PER_LONG);
}

ssize_t __generic_eq(void *k1, void *k2)
{
	return k1 == k2;
}

/*****************************************************************************/
hashtable_t *create_hashtable(size_t minsize, size_t (*hashf)(void *),
                              ssize_t (*eqf)(void *, void *))
{
	hashtable_t *h;
	size_t pindex, size = primes[0];

	/* Check requested hashtable isn't too large */
	if (minsize > (1u << 30))
		return NULL;
	/* Enforce size as prime */
	for (pindex = 0; pindex < prime_table_length; pindex++) {
		if (primes[pindex] > minsize) {
			size = primes[pindex];
			break;
		}
	}
	h = (hashtable_t *)kmalloc(sizeof(hashtable_t), 0);
	if (NULL == h)
		return NULL; /*oom*/
	h->table = (hash_entry_t **)kmalloc(sizeof(hash_entry_t *) * size, 0);
	if (NULL == h->table) {
		kfree(h);
		return NULL;
	} /*oom*/
	memset(h->table, 0, size * sizeof(hash_entry_t *));
	h->tablelength = size;
	h->primeindex = pindex;
	h->entrycount = 0;
	h->hashfn = hashf;
	h->eqfn = eqf;
	h->loadlimit = APPLY_MAX_LOAD_FACTOR(size);
	return h;
}

/*****************************************************************************/
static size_t hash(hashtable_t *h, void *k)
{
	/* Aim to protect against poor hash functions by adding logic here
	 * - logic taken from java 1.4 hashtable source */
	size_t i = h->hashfn(k);

	i += ~(i << 9);
	i ^= ((i >> 14) | (i << 18)); /* >>> */
	i += (i << 4);
	i ^= ((i >> 10) | (i << 22)); /* >>> */
	return i;
}

/*****************************************************************************/
static ssize_t hashtable_expand(hashtable_t *h)
{
	/* Double the size of the table to accomodate more entries */
	hash_entry_t **newtable;
	hash_entry_t *e;
	hash_entry_t **pE;
	size_t newsize, i, index;

	/* Check we're not hitting max capacity */
	if (h->primeindex == (prime_table_length - 1))
		return 0;
	newsize = primes[++(h->primeindex)];

	newtable =
	    (hash_entry_t **)kmalloc(sizeof(hash_entry_t *) * newsize, 0);
	if (NULL != newtable) {
		memset(newtable, 0, newsize * sizeof(hash_entry_t *));
		/* This algorithm is not 'stable'. ie. it reverses the list
		 * when it transfers entries between the tables */
		for (i = 0; i < h->tablelength; i++) {
			while (NULL != (e = h->table[i])) {
				h->table[i] = e->next;
				index = indexFor(newsize, e->h);
				e->next = newtable[index];
				newtable[index] = e;
			}
		}
		kfree(h->table);
		h->table = newtable;
	}
	/* Plan B: realloc instead */
	else {
		newtable = (hash_entry_t **)krealloc(
		    h->table, newsize * sizeof(hash_entry_t *), 0);
		if (NULL == newtable) {
			(h->primeindex)--;
			return 0;
		}
		h->table = newtable;
		memset(newtable[h->tablelength], 0, newsize - h->tablelength);
		for (i = 0; i < h->tablelength; i++) {
			for (pE = &(newtable[i]), e = *pE; e != NULL; e = *pE) {
				index = indexFor(newsize, e->h);
				if (index == i) {
					pE = &(e->next);
				} else {
					*pE = e->next;
					e->next = newtable[index];
					newtable[index] = e;
				}
			}
		}
	}
	h->tablelength = newsize;
	h->loadlimit = APPLY_MAX_LOAD_FACTOR(newsize);
	return -1;
}

/*****************************************************************************/
size_t hashtable_count(hashtable_t *h)
{
	return h->entrycount;
}

/*****************************************************************************/
ssize_t hashtable_insert(hashtable_t *h, void *k, void *v)
{
	/* This method allows duplicate keys - but they shouldn't be used */
	size_t index;
	hash_entry_t *e;

	if (++(h->entrycount) > h->loadlimit) {
		/* Ignore the return value. If expand fails, we should
		 * still try cramming just this value into the existing table
		 * -- we may not have memory for a larger table, but one more
		 * element may be ok. Next time we insert, we'll try expanding
		 * again.*/
		hashtable_expand(h);
	}
	e = (hash_entry_t *)kmem_cache_alloc(hentry_cache, 0);
	if (NULL == e) {
		--(h->entrycount);
		return 0;
	} /*oom*/
	e->h = hash(h, k);
	index = indexFor(h->tablelength, e->h);
	e->k = k;
	e->v = v;
	e->next = h->table[index];
	h->table[index] = e;
	return -1;
}

/*****************************************************************************/
/* returns value associated with key */
void *hashtable_search(hashtable_t *h, void *k)
{
	hash_entry_t *e;
	size_t hashvalue, index;

	hashvalue = hash(h, k);
	index = indexFor(h->tablelength, hashvalue);
	e = h->table[index];
	while (NULL != e) {
		/* Check hash value to short circuit heavier comparison */
		if ((hashvalue == e->h) && (h->eqfn(k, e->k)))
			return e->v;
		e = e->next;
	}
	return NULL;
}

/*****************************************************************************/
/* returns value associated with key */
void *hashtable_remove(hashtable_t *h, void *k)
{
	/* TODO: consider compacting the table when the load factor drops
	 * enough, or provide a 'compact' method. */

	hash_entry_t *e;
	hash_entry_t **pE;
	void *v;
	size_t hashvalue, index;

	hashvalue = hash(h, k);
	index = indexFor(h->tablelength, hash(h, k));
	pE = &(h->table[index]);
	e = *pE;
	while (NULL != e) {
		/* Check hash value to short circuit heavier comparison */
		if ((hashvalue == e->h) && (h->eqfn(k, e->k))) {
			*pE = e->next;
			h->entrycount--;
			v = e->v;
			kmem_cache_free(hentry_cache, e);
			return v;
		}
		pE = &(e->next);
		e = e->next;
	}
	return NULL;
}

/*****************************************************************************/
/* destroy */
void hashtable_destroy(hashtable_t *h)
{
	if (hashtable_count(h))
		warn("Destroying a non-empty hashtable, clean up after "
		     "yourself!\n");

	size_t i;
	hash_entry_t *e, *f;
	hash_entry_t **table = h->table;

	for (i = 0; i < h->tablelength; i++) {
		e = table[i];
		while (NULL != e) {
			f = e;
			e = e->next;
			kmem_cache_free(hentry_cache, f);
		}
	}
	kfree(h->table);
	kfree(h);
}

/*****************************************************************************/
/* hashtable_iterator    - iterator constructor, be sure to kfree this when
 * you're done.
 *
 * If the htable isn't empty, e and index will refer to the first entry. */

hashtable_itr_t *hashtable_iterator(hashtable_t *h)
{
	size_t i, tablelength;
	hashtable_itr_t *itr =
	    (hashtable_itr_t *)kmalloc(sizeof(hashtable_itr_t), 0);

	if (NULL == itr)
		return NULL;
	itr->h = h;
	itr->e = NULL;
	itr->parent = NULL;
	tablelength = h->tablelength;
	itr->index = tablelength;
	if (0 == h->entrycount)
		return itr;

	for (i = 0; i < tablelength; i++) {
		if (NULL != h->table[i]) {
			itr->e = h->table[i];
			itr->index = i;
			break;
		}
	}
	return itr;
}

/*****************************************************************************/
/* key      - return the key of the (key,value) pair at the current position */
/* value    - return the value of the (key,value) pair at the current position
 */

void *hashtable_iterator_key(hashtable_itr_t *i)
{
	return i->e->k;
}

void *hashtable_iterator_value(hashtable_itr_t *i)
{
	return i->e->v;
}

/*****************************************************************************/
/* advance - advance the iterator to the next element
 *           returns zero if advanced to end of table */

ssize_t hashtable_iterator_advance(hashtable_itr_t *itr)
{
	size_t j, tablelength;
	hash_entry_t **table;
	hash_entry_t *next;

	if (NULL == itr->e)
		return 0; /* stupidity check */

	next = itr->e->next;
	if (NULL != next) {
		itr->parent = itr->e;
		itr->e = next;
		return -1;
	}
	tablelength = itr->h->tablelength;
	itr->parent = NULL;
	if (tablelength <= (j = ++(itr->index))) {
		itr->e = NULL;
		return 0;
	}
	table = itr->h->table;
	while (NULL == (next = table[j])) {
		if (++j >= tablelength) {
			itr->index = tablelength;
			itr->e = NULL;
			return 0;
		}
	}
	itr->index = j;
	itr->e = next;
	return -1;
}

/*****************************************************************************/
/* remove - remove the entry at the current iterator position
 *          and advance the iterator, if there is a successive
 *          element.
 *          If you want the value, read it before you remove:
 *          beware memory leaks if you don't.
 *          Returns zero if end of iteration. */

ssize_t hashtable_iterator_remove(hashtable_itr_t *itr)
{
	hash_entry_t *remember_e, *remember_parent;
	ssize_t ret;

	/* Do the removal */
	if (NULL == (itr->parent)) {
		/* element is head of a chain */
		itr->h->table[itr->index] = itr->e->next;
	} else {
		/* element is mid-chain */
		itr->parent->next = itr->e->next;
	}
	/* itr->e is now outside the hashtable */
	remember_e = itr->e;
	itr->h->entrycount--;

	/* Advance the iterator, correcting the parent */
	remember_parent = itr->parent;
	ret = hashtable_iterator_advance(itr);
	if (itr->parent == remember_e) {
		itr->parent = remember_parent;
	}
	kmem_cache_free(hentry_cache, remember_e);
	return ret;
}

/*****************************************************************************/
/* returns zero if not found */
ssize_t hashtable_iterator_search(hashtable_itr_t *itr, hashtable_t *h, void *k)
{
	hash_entry_t *e, *parent;
	size_t hashvalue, index;

	hashvalue = hash(h, k);
	index = indexFor(h->tablelength, hashvalue);

	e = h->table[index];
	parent = NULL;
	while (NULL != e) {
		/* Check hash value to short circuit heavier comparison */
		if ((hashvalue == e->h) && (h->eqfn(k, e->k))) {
			itr->index = index;
			itr->e = e;
			itr->parent = parent;
			itr->h = h;
			return -1;
		}
		parent = e;
		e = e->next;
	}
	return 0;
}

/* Runs func on each member of the hash table */
void hash_for_each(struct hashtable *hash, void func(void *, void *),
                   void *opaque)
{
	if (hashtable_count(hash)) {
		struct hashtable_itr *iter = hashtable_iterator(hash);
		do {
			void *item = hashtable_iterator_value(iter);
			func(item, opaque);
		} while (hashtable_iterator_advance(iter));
		kfree(iter);
	}
}

/* Runs func on each member of the hash table, removing the item after
 * processing it.  Make sure func frees the item, o/w you'll leak. */
void hash_for_each_remove(struct hashtable *hash, void func(void *, void *),
                          void *opaque)
{
	if (hashtable_count(hash)) {
		struct hashtable_itr *iter = hashtable_iterator(hash);
		do {
			void *item = hashtable_iterator_value(iter);
			func(item, opaque);
		} while (hashtable_iterator_remove(iter));
		kfree(iter);
	}
}

/*
 * Copyright (c) 2002, 2004, Christopher Clark
 * All rights reserved.
 *
 * Redistribution and use in source and binary forms, with or without
 * modification, are permitted provided that the following conditions
 * are met:
 *
 * * Redistributions of source code must retain the above copyright
 * notice, this list of conditions and the following disclaimer.
 *
 * * 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.
 *
 * * Neither the name of the original author; nor the names of any 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.
 */