libpool/common/dict.c

/*
 * CDDL HEADER START
 *
 * The contents of this file are subject to the terms of the
 * Common Development and Distribution License, Version 1.0 only
 * (the "License").  You may not use this file except in compliance
 * with the License.
 *
 * You can obtain a copy of the license at usr/src/OPENSOLARIS.LICENSE
 * or http://www.opensolaris.org/os/licensing.
 * See the License for the specific language governing permissions
 * and limitations under the License.
 *
 * When distributing Covered Code, include this CDDL HEADER in each
 * file and include the License file at usr/src/OPENSOLARIS.LICENSE.
 * If applicable, add the following below this CDDL HEADER, with the
 * fields enclosed by brackets "[]" replaced with your own identifying
 * information: Portions Copyright [yyyy] [name of copyright owner]
 *
 * CDDL HEADER END
 */
/*
 * Copyright 2003 Sun Microsystems, Inc.  All rights reserved.
 * Use is subject to license terms.
 */

#pragma ident	"%Z%%M%	%I%	%E% SMI"

/*
 * This file contains a basic dictionary implementation which stores
 * arbitrary key-value mappings. It is used by libpool to store
 * information about element pointers (pool_elem_t) in the kernel
 * provider implementation.
 */

#include <stdio.h>
#include <stdlib.h>
#include <sys/types.h>
#include <unistd.h>
#include <string.h>
#include <assert.h>

#include "dict.h"

/*
 * HASH_64_INIT is the same as the INIT value since it is the value
 * used by FNV (FNV1_64_INIT). More details on FNV are available at:
 *
 * http://www.isthe.com/chongo/tech/comp/fnv/index.html
 */
#define	HASH_64_INIT	(0xcbf29ce484222325ULL) /* Hash initializer */

/*
 * HASH_64_PRIME is a large prime number chosen to minimize hashing
 * collisions.
 */
#define	HASH_64_PRIME	(0x100000001b3ULL)	/* Large Prime */

/*
 * DICT_SIZE is chosen as it is the nearest prime to 2^9 (512). 512 is
 * chosen as it is unlikely that this dictionary will contain more
 * elements than this in normal operation. Of course overflow in each
 * bucket is acceptable, but if there is too much overflow, then
 * performance will degrade to that of a list.
 */
#define	DICT_SIZE	509			/* Reasonable prime */

/*
 * Data Types
 */

/*
 * A key bucket.
 */
typedef struct dict_bucket
{
	const void		*db_key;	/* key */
	void			*db_value;	/* value */
	struct dict_bucket	*db_next;	/* next bucket */
} dict_bucket_t;

/*
 * A dictionary which holds a mapping between a key and a value.
 *	dh_change	- detects changes to the dictionary.
 *	dh_cmp		- comparison function
 *	dh_hash		- hashing function
 *	dh_buckets	- key storage
 *	dh_size		- # of buckets
 */
struct dict_hdl {
	uint64_t		dh_change;
	int			(*dh_cmp)(const void *, const void *);
	uint64_t		(*dh_hash)(const void *);
	uint64_t		dh_length;
	dict_bucket_t		**dh_buckets;
	uint64_t		dh_size;
};

/*
 * Utility functions. Mainly used for debugging
 */

#if defined(DEBUG)

static void		bit_print_32(unsigned int);
static void		bit_print_64(unsigned long long);

#endif /* DEBUG */

/*
 * Default functions for hashing and comparing if the user does not specify
 * these values when creating the dictionary.
 */
static int		cmp_addr(const void *, const void *);
static uint64_t		hash_addr(const void *);

/*
 * static functions
 */

#if defined(DEBUG)

/*
 * Print to standard out the bit representation of the supplied value
 */
void
bit_print_32(unsigned int v)
{
#pragma	error_messages(off, E_INTEGER_OVERFLOW_DETECTED)
	int i, mask = 1 << 31;
#pragma	error_messages(on, E_INTEGER_OVERFLOW_DETECTED)

	for (i = 1; i <= 32; i++) {
		(void) putchar(((v & mask) == 0) ? '0' : '1');
		v <<= 1;
		if (i % 8 == 0 && i != 32)
			(void) putchar(' ');
	}
	(void) putchar('\n');
}

/*
 * Print to standard out the bit representation of the supplied value
 */
void
bit_print_64(unsigned long long v)
{
#pragma	error_messages(off, E_INTEGER_OVERFLOW_DETECTED)
	long long mask = 1ll << 63;
#pragma	error_messages(on, E_INTEGER_OVERFLOW_DETECTED)
	int i;

	for (i = 1; i <= 64; i++) {
		(void) putchar(((v & mask) == 0) ? '0' : '1');
		v <<= 1;
		if (i % 8 == 0 && i != 64)
			(void) putchar(' ');
	}
	(void) putchar('\n');
}


#endif /* DEBUG */

/*
 * Default comparison function which is used if no comparison function
 * is supplied when the dictionary is created. The default behaviour
 * is to compare memory address.
 */
int
cmp_addr(const void *x, const void *y)
{
	return (x != y);
}


/*
 * The default hashing function which is used if no hashing function
 * is provided when the dictionary is created. The default behaviour
 * is to use the hash_buf() function.
 */
uint64_t
hash_addr(const void *key)
{
	return (hash_buf(&key, sizeof (key)));
}


/*
 * public interface
 */

/*
 * Return a hash which is built by manipulating each byte in the
 * supplied data. The hash logic follows the approach suggested in the
 * FNV hash.
 */
uint64_t
hash_buf(const void *buf, size_t len)
{
	uchar_t *start = (uchar_t *)buf;
	uchar_t *end = start + len;
	uint64_t hash = HASH_64_INIT;

	while (start < end) {
		hash *= HASH_64_PRIME;
		hash ^= (uint64_t)*start++;
	}

	return (hash);
}


/*
 * Return a hash which is built by manipulating each byte in the
 * supplied string. The hash logic follows the approach suggested in
 * the FNV hash.
 */
uint64_t
hash_str(const char *str)
{
	uchar_t *p = (uchar_t *)str;
	uint64_t hash = HASH_64_INIT;

	while (*p) {
		hash *= HASH_64_PRIME;
		hash ^= (uint64_t)*p++;
	}

	return (hash);
}

/*
 * Return the number of keys held in the supplied dictionary.
 */
uint64_t
dict_length(dict_hdl_t *hdl)
{
	return (hdl->dh_length);
}

/*
 * Free the supplied dictionary and all it's associated resource.
 */
void
dict_free(dict_hdl_t **hdl)
{
	if ((*hdl)->dh_length > 0) {
		uint64_t i;
		for (i = 0; i < (*hdl)->dh_size; i++) {
			dict_bucket_t *this, *next;
			for (this = (*hdl)->dh_buckets[i]; this != NULL;
			    this = next) {
				next = this->db_next;
				free(this);
			}
		}
	}
	free((*hdl)->dh_buckets);
	free((*hdl));
	*hdl = NULL;
}

/*
 * Create a new dictionary using the supplied comparison and hashing
 * functions. If none are supplied then the defaults are used.
 */
dict_hdl_t *
dict_new(int (*cmp)(const void *, const void *),
    uint64_t (*hash)(const void *))
{
	dict_hdl_t *hdl;

	if ((hdl = calloc(1, sizeof (dict_hdl_t))) == NULL)
		return (NULL);
	hdl->dh_size = DICT_SIZE;
	if ((hdl->dh_buckets = calloc(hdl->dh_size, sizeof (dict_bucket_t *)))
	    == NULL) {
		free(hdl);
		return (NULL);
	}
	hdl->dh_cmp = cmp ? cmp : cmp_addr;
	hdl->dh_hash = hash ? hash : hash_addr;
	return (hdl);
}

/*
 * Get a value from the hash. Null is returned if the key cannot be
 * found.
 */
void *
dict_get(dict_hdl_t *hdl, const void *key)
{
	uint64_t i;
	dict_bucket_t *bucket;

	i = (*hdl->dh_hash)(key)%hdl->dh_size;
	for (bucket = hdl->dh_buckets[i]; bucket != NULL;
	    bucket = bucket->db_next)
		if ((*hdl->dh_cmp)(key, bucket->db_key) == 0)
			break;
	return (bucket ? bucket->db_value : NULL);
}

/*
 * Put an entry into the hash. Null is returned if this key was not
 * already present, otherwise the previous value is returned.
 */
void *
dict_put(dict_hdl_t *hdl, const void *key, void *value)
{
	uint64_t i;
	dict_bucket_t *bucket;
	void *prev = NULL;

	i = (*hdl->dh_hash)(key)%hdl->dh_size;
	for (bucket = hdl->dh_buckets[i]; bucket != NULL;
	    bucket = bucket->db_next)
		if ((*hdl->dh_cmp)(key, bucket->db_key) == 0)
			break;
	if (bucket) {
		prev = bucket->db_value;
	} else {
		bucket = malloc(sizeof (dict_bucket_t));
		bucket->db_key = key;
		bucket->db_next = hdl->dh_buckets[i];
		hdl->dh_buckets[i] = bucket;
		hdl->dh_length++;
	}
	hdl->dh_change++;
	bucket->db_value = value;
	return (prev);
}

/*
 * Remove the key/value from the dictionary. The value is returned if
 * the key is found. NULL is returned if the key cannot be located.
 */
void *
dict_remove(dict_hdl_t *hdl, const void *key)
{
	uint64_t i;
	dict_bucket_t	**pbucket;

	hdl->dh_change++;
	i = (*hdl->dh_hash)(key)%hdl->dh_size;

	for (pbucket = &hdl->dh_buckets[i]; *pbucket != NULL;
	    pbucket = &(*pbucket)->db_next) {
		if ((*hdl->dh_cmp)(key, (*pbucket)->db_key) == 0) {
			dict_bucket_t *bucket = *pbucket;
			void *value = bucket->db_value;

			*pbucket = bucket->db_next;
			free(bucket);
			hdl->dh_length--;
			return (value);
		}
	}
	return (NULL);
}

/*
 * For all entries in the dictionary call the user supplied function
 * (apply) with the key, value and user supplied data. If the
 * dictionary is modifed while this function is executing, then the
 * function will fail with an assertion about table modifcation.
 */
void
dict_map(dict_hdl_t *hdl, void (*apply)(const void *, void **, void *),
    void *cl)
{
	uint64_t i;
	dict_bucket_t *bucket = NULL;
	uint64_t change_stamp = hdl->dh_change;

	for (i = 0; i < hdl->dh_size; i++) {
		for (bucket = hdl->dh_buckets[i]; bucket != NULL;
		    bucket = bucket->db_next) {
			apply(bucket->db_key, &bucket->db_value, cl);
			if (hdl->dh_change != change_stamp)
				assert(!"table modified illegally");
		}
	}
}