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