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