Home | History | Annotate | Download | only in common
      1  0  stevel /*
      2  0  stevel  * CDDL HEADER START
      3  0  stevel  *
      4  0  stevel  * The contents of this file are subject to the terms of the
      5  0  stevel  * Common Development and Distribution License, Version 1.0 only
      6  0  stevel  * (the "License").  You may not use this file except in compliance
      7  0  stevel  * with the License.
      8  0  stevel  *
      9  0  stevel  * You can obtain a copy of the license at usr/src/OPENSOLARIS.LICENSE
     10  0  stevel  * or http://www.opensolaris.org/os/licensing.
     11  0  stevel  * See the License for the specific language governing permissions
     12  0  stevel  * and limitations under the License.
     13  0  stevel  *
     14  0  stevel  * When distributing Covered Code, include this CDDL HEADER in each
     15  0  stevel  * file and include the License file at usr/src/OPENSOLARIS.LICENSE.
     16  0  stevel  * If applicable, add the following below this CDDL HEADER, with the
     17  0  stevel  * fields enclosed by brackets "[]" replaced with your own identifying
     18  0  stevel  * information: Portions Copyright [yyyy] [name of copyright owner]
     19  0  stevel  *
     20  0  stevel  * CDDL HEADER END
     21  0  stevel  */
     22  0  stevel /*
     23  0  stevel  * Copyright 2003 Sun Microsystems, Inc.  All rights reserved.
     24  0  stevel  * Use is subject to license terms.
     25  0  stevel  */
     26  0  stevel 
     27  0  stevel #pragma ident	"%Z%%M%	%I%	%E% SMI"
     28  0  stevel 
     29  0  stevel /*
     30  0  stevel  * This file contains a basic dictionary implementation which stores
     31  0  stevel  * arbitrary key-value mappings. It is used by libpool to store
     32  0  stevel  * information about element pointers (pool_elem_t) in the kernel
     33  0  stevel  * provider implementation.
     34  0  stevel  */
     35  0  stevel 
     36  0  stevel #include <stdio.h>
     37  0  stevel #include <stdlib.h>
     38  0  stevel #include <sys/types.h>
     39  0  stevel #include <unistd.h>
     40  0  stevel #include <string.h>
     41  0  stevel #include <assert.h>
     42  0  stevel 
     43  0  stevel #include "dict.h"
     44  0  stevel 
     45  0  stevel /*
     46  0  stevel  * HASH_64_INIT is the same as the INIT value since it is the value
     47  0  stevel  * used by FNV (FNV1_64_INIT). More details on FNV are available at:
     48  0  stevel  *
     49  0  stevel  * http://www.isthe.com/chongo/tech/comp/fnv/index.html
     50  0  stevel  */
     51  0  stevel #define	HASH_64_INIT	(0xcbf29ce484222325ULL) /* Hash initializer */
     52  0  stevel 
     53  0  stevel /*
     54  0  stevel  * HASH_64_PRIME is a large prime number chosen to minimize hashing
     55  0  stevel  * collisions.
     56  0  stevel  */
     57  0  stevel #define	HASH_64_PRIME	(0x100000001b3ULL)	/* Large Prime */
     58  0  stevel 
     59  0  stevel /*
     60  0  stevel  * DICT_SIZE is chosen as it is the nearest prime to 2^9 (512). 512 is
     61  0  stevel  * chosen as it is unlikely that this dictionary will contain more
     62  0  stevel  * elements than this in normal operation. Of course overflow in each
     63  0  stevel  * bucket is acceptable, but if there is too much overflow, then
     64  0  stevel  * performance will degrade to that of a list.
     65  0  stevel  */
     66  0  stevel #define	DICT_SIZE	509			/* Reasonable prime */
     67  0  stevel 
     68  0  stevel /*
     69  0  stevel  * Data Types
     70  0  stevel  */
     71  0  stevel 
     72  0  stevel /*
     73  0  stevel  * A key bucket.
     74  0  stevel  */
     75  0  stevel typedef struct dict_bucket
     76  0  stevel {
     77  0  stevel 	const void		*db_key;	/* key */
     78  0  stevel 	void			*db_value;	/* value */
     79  0  stevel 	struct dict_bucket	*db_next;	/* next bucket */
     80  0  stevel } dict_bucket_t;
     81  0  stevel 
     82  0  stevel /*
     83  0  stevel  * A dictionary which holds a mapping between a key and a value.
     84  0  stevel  *	dh_change	- detects changes to the dictionary.
     85  0  stevel  *	dh_cmp		- comparison function
     86  0  stevel  *	dh_hash		- hashing function
     87  0  stevel  *	dh_buckets	- key storage
     88  0  stevel  *	dh_size		- # of buckets
     89  0  stevel  */
     90  0  stevel struct dict_hdl {
     91  0  stevel 	uint64_t		dh_change;
     92  0  stevel 	int			(*dh_cmp)(const void *, const void *);
     93  0  stevel 	uint64_t		(*dh_hash)(const void *);
     94  0  stevel 	uint64_t		dh_length;
     95  0  stevel 	dict_bucket_t		**dh_buckets;
     96  0  stevel 	uint64_t		dh_size;
     97  0  stevel };
     98  0  stevel 
     99  0  stevel /*
    100  0  stevel  * Utility functions. Mainly used for debugging
    101  0  stevel  */
    102  0  stevel 
    103  0  stevel #if defined(DEBUG)
    104  0  stevel 
    105  0  stevel static void		bit_print_32(unsigned int);
    106  0  stevel static void		bit_print_64(unsigned long long);
    107  0  stevel 
    108  0  stevel #endif /* DEBUG */
    109  0  stevel 
    110  0  stevel /*
    111  0  stevel  * Default functions for hashing and comparing if the user does not specify
    112  0  stevel  * these values when creating the dictionary.
    113  0  stevel  */
    114  0  stevel static int		cmp_addr(const void *, const void *);
    115  0  stevel static uint64_t		hash_addr(const void *);
    116  0  stevel 
    117  0  stevel /*
    118  0  stevel  * static functions
    119  0  stevel  */
    120  0  stevel 
    121  0  stevel #if defined(DEBUG)
    122  0  stevel 
    123  0  stevel /*
    124  0  stevel  * Print to standard out the bit representation of the supplied value
    125  0  stevel  */
    126  0  stevel void
    127  0  stevel bit_print_32(unsigned int v)
    128  0  stevel {
    129  0  stevel #pragma	error_messages(off, E_INTEGER_OVERFLOW_DETECTED)
    130  0  stevel 	int i, mask = 1 << 31;
    131  0  stevel #pragma	error_messages(on, E_INTEGER_OVERFLOW_DETECTED)
    132  0  stevel 
    133  0  stevel 	for (i = 1; i <= 32; i++) {
    134  0  stevel 		(void) putchar(((v & mask) == 0) ? '0' : '1');
    135  0  stevel 		v <<= 1;
    136  0  stevel 		if (i % 8 == 0 && i != 32)
    137  0  stevel 			(void) putchar(' ');
    138  0  stevel 	}
    139  0  stevel 	(void) putchar('\n');
    140  0  stevel }
    141  0  stevel 
    142  0  stevel /*
    143  0  stevel  * Print to standard out the bit representation of the supplied value
    144  0  stevel  */
    145  0  stevel void
    146  0  stevel bit_print_64(unsigned long long v)
    147  0  stevel {
    148  0  stevel #pragma	error_messages(off, E_INTEGER_OVERFLOW_DETECTED)
    149  0  stevel 	long long mask = 1ll << 63;
    150  0  stevel #pragma	error_messages(on, E_INTEGER_OVERFLOW_DETECTED)
    151  0  stevel 	int i;
    152  0  stevel 
    153  0  stevel 	for (i = 1; i <= 64; i++) {
    154  0  stevel 		(void) putchar(((v & mask) == 0) ? '0' : '1');
    155  0  stevel 		v <<= 1;
    156  0  stevel 		if (i % 8 == 0 && i != 64)
    157  0  stevel 			(void) putchar(' ');
    158  0  stevel 	}
    159  0  stevel 	(void) putchar('\n');
    160  0  stevel }
    161  0  stevel 
    162  0  stevel 
    163  0  stevel 
    164  0  stevel #endif /* DEBUG */
    165  0  stevel 
    166  0  stevel /*
    167  0  stevel  * Default comparison function which is used if no comparison function
    168  0  stevel  * is supplied when the dictionary is created. The default behaviour
    169  0  stevel  * is to compare memory address.
    170  0  stevel  */
    171  0  stevel int
    172  0  stevel cmp_addr(const void *x, const void *y)
    173  0  stevel {
    174  0  stevel 	return (x != y);
    175  0  stevel }
    176  0  stevel 
    177  0  stevel 
    178  0  stevel /*
    179  0  stevel  * The default hashing function which is used if no hashing function
    180  0  stevel  * is provided when the dictionary is created. The default behaviour
    181  0  stevel  * is to use the hash_buf() function.
    182  0  stevel  */
    183  0  stevel uint64_t
    184  0  stevel hash_addr(const void *key)
    185  0  stevel {
    186  0  stevel 	return (hash_buf(&key, sizeof (key)));
    187  0  stevel }
    188  0  stevel 
    189  0  stevel 
    190  0  stevel /*
    191  0  stevel  * public interface
    192  0  stevel  */
    193  0  stevel 
    194  0  stevel /*
    195  0  stevel  * Return a hash which is built by manipulating each byte in the
    196  0  stevel  * supplied data. The hash logic follows the approach suggested in the
    197  0  stevel  * FNV hash.
    198  0  stevel  */
    199  0  stevel uint64_t
    200  0  stevel hash_buf(const void *buf, size_t len)
    201  0  stevel {
    202  0  stevel 	uchar_t *start = (uchar_t *)buf;
    203  0  stevel 	uchar_t *end = start + len;
    204  0  stevel 	uint64_t hash = HASH_64_INIT;
    205  0  stevel 
    206  0  stevel 	while (start < end) {
    207  0  stevel 		hash *= HASH_64_PRIME;
    208  0  stevel 		hash ^= (uint64_t)*start++;
    209  0  stevel 	}
    210  0  stevel 
    211  0  stevel 	return (hash);
    212  0  stevel }
    213  0  stevel 
    214  0  stevel 
    215  0  stevel /*
    216  0  stevel  * Return a hash which is built by manipulating each byte in the
    217  0  stevel  * supplied string. The hash logic follows the approach suggested in
    218  0  stevel  * the FNV hash.
    219  0  stevel  */
    220  0  stevel uint64_t
    221  0  stevel hash_str(const char *str)
    222  0  stevel {
    223  0  stevel 	uchar_t *p = (uchar_t *)str;
    224  0  stevel 	uint64_t hash = HASH_64_INIT;
    225  0  stevel 
    226  0  stevel 	while (*p) {
    227  0  stevel 		hash *= HASH_64_PRIME;
    228  0  stevel 		hash ^= (uint64_t)*p++;
    229  0  stevel 	}
    230  0  stevel 
    231  0  stevel 	return (hash);
    232  0  stevel }
    233  0  stevel 
    234  0  stevel /*
    235  0  stevel  * Return the number of keys held in the supplied dictionary.
    236  0  stevel  */
    237  0  stevel uint64_t
    238  0  stevel dict_length(dict_hdl_t *hdl)
    239  0  stevel {
    240  0  stevel 	return (hdl->dh_length);
    241  0  stevel }
    242  0  stevel 
    243  0  stevel /*
    244  0  stevel  * Free the supplied dictionary and all it's associated resource.
    245  0  stevel  */
    246  0  stevel void
    247  0  stevel dict_free(dict_hdl_t **hdl)
    248  0  stevel {
    249  0  stevel 	if ((*hdl)->dh_length > 0) {
    250  0  stevel 		uint64_t i;
    251  0  stevel 		for (i = 0; i < (*hdl)->dh_size; i++) {
    252  0  stevel 			dict_bucket_t *this, *next;
    253  0  stevel 			for (this = (*hdl)->dh_buckets[i]; this != NULL;
    254  0  stevel 			    this = next) {
    255  0  stevel 				next = this->db_next;
    256  0  stevel 				free(this);
    257  0  stevel 			}
    258  0  stevel 		}
    259  0  stevel 	}
    260  0  stevel 	free((*hdl)->dh_buckets);
    261  0  stevel 	free((*hdl));
    262  0  stevel 	*hdl = NULL;
    263  0  stevel }
    264  0  stevel 
    265  0  stevel /*
    266  0  stevel  * Create a new dictionary using the supplied comparison and hashing
    267  0  stevel  * functions. If none are supplied then the defaults are used.
    268  0  stevel  */
    269  0  stevel dict_hdl_t *
    270  0  stevel dict_new(int (*cmp)(const void *, const void *),
    271  0  stevel     uint64_t (*hash)(const void *))
    272  0  stevel {
    273  0  stevel 	dict_hdl_t *hdl;
    274  0  stevel 
    275  0  stevel 	if ((hdl = calloc(1, sizeof (dict_hdl_t))) == NULL)
    276  0  stevel 		return (NULL);
    277  0  stevel 	hdl->dh_size = DICT_SIZE;
    278  0  stevel 	if ((hdl->dh_buckets = calloc(hdl->dh_size, sizeof (dict_bucket_t *)))
    279  0  stevel 	    == NULL) {
    280  0  stevel 		free(hdl);
    281  0  stevel 		return (NULL);
    282  0  stevel 	}
    283  0  stevel 	hdl->dh_cmp = cmp ? cmp : cmp_addr;
    284  0  stevel 	hdl->dh_hash = hash ? hash : hash_addr;
    285  0  stevel 	return (hdl);
    286  0  stevel }
    287  0  stevel 
    288  0  stevel /*
    289  0  stevel  * Get a value from the hash. Null is returned if the key cannot be
    290  0  stevel  * found.
    291  0  stevel  */
    292  0  stevel void *
    293  0  stevel dict_get(dict_hdl_t *hdl, const void *key)
    294  0  stevel {
    295  0  stevel 	uint64_t i;
    296  0  stevel 	dict_bucket_t *bucket;
    297  0  stevel 
    298  0  stevel 	i = (*hdl->dh_hash)(key)%hdl->dh_size;
    299  0  stevel 	for (bucket = hdl->dh_buckets[i]; bucket != NULL;
    300  0  stevel 	    bucket = bucket->db_next)
    301  0  stevel 		if ((*hdl->dh_cmp)(key, bucket->db_key) == 0)
    302  0  stevel 			break;
    303  0  stevel 	return (bucket ? bucket->db_value : NULL);
    304  0  stevel }
    305  0  stevel 
    306  0  stevel /*
    307  0  stevel  * Put an entry into the hash. Null is returned if this key was not
    308  0  stevel  * already present, otherwise the previous value is returned.
    309  0  stevel  */
    310  0  stevel void *
    311  0  stevel dict_put(dict_hdl_t *hdl, const void *key, void *value)
    312  0  stevel {
    313  0  stevel 	uint64_t i;
    314  0  stevel 	dict_bucket_t *bucket;
    315  0  stevel 	void *prev = NULL;
    316  0  stevel 
    317  0  stevel 	i = (*hdl->dh_hash)(key)%hdl->dh_size;
    318  0  stevel 	for (bucket = hdl->dh_buckets[i]; bucket != NULL;
    319  0  stevel 	    bucket = bucket->db_next)
    320  0  stevel 		if ((*hdl->dh_cmp)(key, bucket->db_key) == 0)
    321  0  stevel 			break;
    322  0  stevel 	if (bucket) {
    323  0  stevel 		prev = bucket->db_value;
    324  0  stevel 	} else {
    325  0  stevel 		bucket = malloc(sizeof (dict_bucket_t));
    326  0  stevel 		bucket->db_key = key;
    327  0  stevel 		bucket->db_next = hdl->dh_buckets[i];
    328  0  stevel 		hdl->dh_buckets[i] = bucket;
    329  0  stevel 		hdl->dh_length++;
    330  0  stevel 	}
    331  0  stevel 	hdl->dh_change++;
    332  0  stevel 	bucket->db_value = value;
    333  0  stevel 	return (prev);
    334  0  stevel }
    335  0  stevel 
    336  0  stevel /*
    337  0  stevel  * Remove the key/value from the dictionary. The value is returned if
    338  0  stevel  * the key is found. NULL is returned if the key cannot be located.
    339  0  stevel  */
    340  0  stevel void *
    341  0  stevel dict_remove(dict_hdl_t *hdl, const void *key)
    342  0  stevel {
    343  0  stevel 	uint64_t i;
    344  0  stevel 	dict_bucket_t	**pbucket;
    345  0  stevel 
    346  0  stevel 	hdl->dh_change++;
    347  0  stevel 	i = (*hdl->dh_hash)(key)%hdl->dh_size;
    348  0  stevel 
    349  0  stevel 	for (pbucket = &hdl->dh_buckets[i]; *pbucket != NULL;
    350  0  stevel 	    pbucket = &(*pbucket)->db_next) {
    351  0  stevel 		if ((*hdl->dh_cmp)(key, (*pbucket)->db_key) == 0) {
    352  0  stevel 			dict_bucket_t *bucket = *pbucket;
    353  0  stevel 			void *value = bucket->db_value;
    354  0  stevel 
    355  0  stevel 			*pbucket = bucket->db_next;
    356  0  stevel 			free(bucket);
    357  0  stevel 			hdl->dh_length--;
    358  0  stevel 			return (value);
    359  0  stevel 		}
    360  0  stevel 	}
    361  0  stevel 	return (NULL);
    362  0  stevel }
    363  0  stevel 
    364  0  stevel /*
    365  0  stevel  * For all entries in the dictionary call the user supplied function
    366  0  stevel  * (apply) with the key, value and user supplied data. If the
    367  0  stevel  * dictionary is modifed while this function is executing, then the
    368  0  stevel  * function will fail with an assertion about table modifcation.
    369  0  stevel  */
    370  0  stevel void
    371  0  stevel dict_map(dict_hdl_t *hdl, void (*apply)(const void *, void **, void *),
    372  0  stevel     void *cl)
    373  0  stevel {
    374  0  stevel 	uint64_t i;
    375  0  stevel 	dict_bucket_t *bucket = NULL;
    376  0  stevel 	uint64_t change_stamp = hdl->dh_change;
    377  0  stevel 
    378  0  stevel 	for (i = 0; i < hdl->dh_size; i++) {
    379  0  stevel 		for (bucket = hdl->dh_buckets[i]; bucket != NULL;
    380  0  stevel 		    bucket = bucket->db_next) {
    381  0  stevel 			apply(bucket->db_key, &bucket->db_value, cl);
    382  0  stevel 			if (hdl->dh_change != change_stamp)
    383  0  stevel 				assert(!"table modified illegally");
    384  0  stevel 		}
    385  0  stevel 	}
    386  0  stevel }
    387