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 int i, mask = 1 << 31; 128 129 for (i = 1; i <= 32; i++) { 130 (void) putchar(((v & mask) == 0) ? '0' : '1'); 131 v <<= 1; 132 if (i % 8 == 0 && i != 32) 133 (void) putchar(' '); 134 } 135 (void) putchar('\n'); 136 } 137 138 /* 139 * Print to standard out the bit representation of the supplied value 140 */ 141 void 142 bit_print_64(unsigned long long v) 143 { 144 long long mask = 1ll << 63; 145 int i; 146 147 for (i = 1; i <= 64; i++) { 148 (void) putchar(((v & mask) == 0) ? '0' : '1'); 149 v <<= 1; 150 if (i % 8 == 0 && i != 64) 151 (void) putchar(' '); 152 } 153 (void) putchar('\n'); 154 } 155 156 157 158 #endif /* DEBUG */ 159 160 /* 161 * Default comparison function which is used if no comparison function 162 * is supplied when the dictionary is created. The default behaviour 163 * is to compare memory address. 164 */ 165 int 166 cmp_addr(const void *x, const void *y) 167 { 168 return (x != y); 169 } 170 171 172 /* 173 * The default hashing function which is used if no hashing function 174 * is provided when the dictionary is created. The default behaviour 175 * is to use the hash_buf() function. 176 */ 177 uint64_t 178 hash_addr(const void *key) 179 { 180 return (hash_buf(&key, sizeof (key))); 181 } 182 183 184 /* 185 * public interface 186 */ 187 188 /* 189 * Return a hash which is built by manipulating each byte in the 190 * supplied data. The hash logic follows the approach suggested in the 191 * FNV hash. 192 */ 193 uint64_t 194 hash_buf(const void *buf, size_t len) 195 { 196 uchar_t *start = (uchar_t *)buf; 197 uchar_t *end = start + len; 198 uint64_t hash = HASH_64_INIT; 199 200 while (start < end) { 201 hash *= HASH_64_PRIME; 202 hash ^= (uint64_t)*start++; 203 } 204 205 return (hash); 206 } 207 208 209 /* 210 * Return a hash which is built by manipulating each byte in the 211 * supplied string. The hash logic follows the approach suggested in 212 * the FNV hash. 213 */ 214 uint64_t 215 hash_str(const char *str) 216 { 217 uchar_t *p = (uchar_t *)str; 218 uint64_t hash = HASH_64_INIT; 219 220 while (*p) { 221 hash *= HASH_64_PRIME; 222 hash ^= (uint64_t)*p++; 223 } 224 225 return (hash); 226 } 227 228 /* 229 * Return the number of keys held in the supplied dictionary. 230 */ 231 uint64_t 232 dict_length(dict_hdl_t *hdl) 233 { 234 return (hdl->dh_length); 235 } 236 237 /* 238 * Free the supplied dictionary and all it's associated resource. 239 */ 240 void 241 dict_free(dict_hdl_t **hdl) 242 { 243 if ((*hdl)->dh_length > 0) { 244 uint64_t i; 245 for (i = 0; i < (*hdl)->dh_size; i++) { 246 dict_bucket_t *this, *next; 247 for (this = (*hdl)->dh_buckets[i]; this != NULL; 248 this = next) { 249 next = this->db_next; 250 free(this); 251 } 252 } 253 } 254 free((*hdl)->dh_buckets); 255 free((*hdl)); 256 *hdl = NULL; 257 } 258 259 /* 260 * Create a new dictionary using the supplied comparison and hashing 261 * functions. If none are supplied then the defaults are used. 262 */ 263 dict_hdl_t * 264 dict_new(int (*cmp)(const void *, const void *), 265 uint64_t (*hash)(const void *)) 266 { 267 dict_hdl_t *hdl; 268 269 if ((hdl = calloc(1, sizeof (dict_hdl_t))) == NULL) 270 return (NULL); 271 hdl->dh_size = DICT_SIZE; 272 if ((hdl->dh_buckets = calloc(hdl->dh_size, sizeof (dict_bucket_t *))) 273 == NULL) { 274 free(hdl); 275 return (NULL); 276 } 277 hdl->dh_cmp = cmp ? cmp : cmp_addr; 278 hdl->dh_hash = hash ? hash : hash_addr; 279 return (hdl); 280 } 281 282 /* 283 * Get a value from the hash. Null is returned if the key cannot be 284 * found. 285 */ 286 void * 287 dict_get(dict_hdl_t *hdl, const void *key) 288 { 289 uint64_t i; 290 dict_bucket_t *bucket; 291 292 i = (*hdl->dh_hash)(key)%hdl->dh_size; 293 for (bucket = hdl->dh_buckets[i]; bucket != NULL; 294 bucket = bucket->db_next) 295 if ((*hdl->dh_cmp)(key, bucket->db_key) == 0) 296 break; 297 return (bucket ? bucket->db_value : NULL); 298 } 299 300 /* 301 * Put an entry into the hash. Null is returned if this key was not 302 * already present, otherwise the previous value is returned. 303 */ 304 void * 305 dict_put(dict_hdl_t *hdl, const void *key, void *value) 306 { 307 uint64_t i; 308 dict_bucket_t *bucket; 309 void *prev = NULL; 310 311 i = (*hdl->dh_hash)(key)%hdl->dh_size; 312 for (bucket = hdl->dh_buckets[i]; bucket != NULL; 313 bucket = bucket->db_next) 314 if ((*hdl->dh_cmp)(key, bucket->db_key) == 0) 315 break; 316 if (bucket) { 317 prev = bucket->db_value; 318 } else { 319 bucket = malloc(sizeof (dict_bucket_t)); 320 bucket->db_key = key; 321 bucket->db_next = hdl->dh_buckets[i]; 322 hdl->dh_buckets[i] = bucket; 323 hdl->dh_length++; 324 } 325 hdl->dh_change++; 326 bucket->db_value = value; 327 return (prev); 328 } 329 330 /* 331 * Remove the key/value from the dictionary. The value is returned if 332 * the key is found. NULL is returned if the key cannot be located. 333 */ 334 void * 335 dict_remove(dict_hdl_t *hdl, const void *key) 336 { 337 uint64_t i; 338 dict_bucket_t **pbucket; 339 340 hdl->dh_change++; 341 i = (*hdl->dh_hash)(key)%hdl->dh_size; 342 343 for (pbucket = &hdl->dh_buckets[i]; *pbucket != NULL; 344 pbucket = &(*pbucket)->db_next) { 345 if ((*hdl->dh_cmp)(key, (*pbucket)->db_key) == 0) { 346 dict_bucket_t *bucket = *pbucket; 347 void *value = bucket->db_value; 348 349 *pbucket = bucket->db_next; 350 free(bucket); 351 hdl->dh_length--; 352 return (value); 353 } 354 } 355 return (NULL); 356 } 357 358 /* 359 * For all entries in the dictionary call the user supplied function 360 * (apply) with the key, value and user supplied data. If the 361 * dictionary is modifed while this function is executing, then the 362 * function will fail with an assertion about table modifcation. 363 */ 364 void 365 dict_map(dict_hdl_t *hdl, void (*apply)(const void *, void **, void *), 366 void *cl) 367 { 368 uint64_t i; 369 dict_bucket_t *bucket = NULL; 370 uint64_t change_stamp = hdl->dh_change; 371 372 for (i = 0; i < hdl->dh_size; i++) { 373 for (bucket = hdl->dh_buckets[i]; bucket != NULL; 374 bucket = bucket->db_next) { 375 apply(bucket->db_key, &bucket->db_value, cl); 376 if (hdl->dh_change != change_stamp) 377 assert(!"table modified illegally"); 378 } 379 } 380 } 381