1/* 2 * Copyright (c) 2007-2008 Apple Inc. All rights reserved. 3 * 4 * @APPLE_OSREFERENCE_LICENSE_HEADER_START@ 5 * 6 * This file contains Original Code and/or Modifications of Original Code 7 * as defined in and that are subject to the Apple Public Source License 8 * Version 2.0 (the 'License'). You may not use this file except in 9 * compliance with the License. The rights granted to you under the License 10 * may not be used to create, or enable the creation or redistribution of, 11 * unlawful or unlicensed copies of an Apple operating system, or to 12 * circumvent, violate, or enable the circumvention or violation of, any 13 * terms of an Apple operating system software license agreement. 14 * 15 * Please obtain a copy of the License at 16 * http://www.opensource.apple.com/apsl/ and read it before using this file. 17 * 18 * The Original Code and all software distributed under the License are 19 * distributed on an 'AS IS' basis, WITHOUT WARRANTY OF ANY KIND, EITHER 20 * EXPRESS OR IMPLIED, AND APPLE HEREBY DISCLAIMS ALL SUCH WARRANTIES, 21 * INCLUDING WITHOUT LIMITATION, ANY WARRANTIES OF MERCHANTABILITY, 22 * FITNESS FOR A PARTICULAR PURPOSE, QUIET ENJOYMENT OR NON-INFRINGEMENT. 23 * Please see the License for the specific language governing rights and 24 * limitations under the License. 25 * 26 * @APPLE_OSREFERENCE_LICENSE_HEADER_END@ 27 */ 28#include <string.h> 29#include <sys/types.h> 30 31#define DEBUG_ASSERT_COMPONENT_NAME_STRING "kxld" 32#include <AssertMacros.h> 33 34#include "kxld_dict.h" 35#include "kxld_util.h" 36 37/******************************************************************************* 38* Types and macros 39*******************************************************************************/ 40 41/* Ratio of num_entries:num_buckets that will cause a resize */ 42#define RESIZE_NUMER 7 43#define RESIZE_DENOM 10 44#define RESIZE_THRESHOLD(x) (((x)*RESIZE_NUMER) / RESIZE_DENOM) 45#define MIN_BUCKETS(x) (((x)*RESIZE_DENOM) / RESIZE_NUMER) 46 47/* Selected for good scaling qualities when resizing dictionary 48 * ... see: http://www.concentric.net/~ttwang/tech/hashsize.htm 49 */ 50#define DEFAULT_DICT_SIZE 89 51 52typedef struct dict_entry DictEntry; 53 54typedef enum { 55 EMPTY = 0, 56 USED = 1, 57 DELETED = 2 58} DictEntryState; 59 60struct dict_entry { 61 const void *key; 62 void *value; 63 DictEntryState state; 64}; 65 66/******************************************************************************* 67* Function prototypes 68*******************************************************************************/ 69 70static kern_return_t get_locate_index(const KXLDDict *dict, const void *key, 71 u_int *idx); 72static kern_return_t get_insert_index(const KXLDDict *dict, const void *key, 73 u_int *idx); 74static kern_return_t resize_dict(KXLDDict *dict); 75 76/******************************************************************************* 77*******************************************************************************/ 78kern_return_t 79kxld_dict_init(KXLDDict * dict, kxld_dict_hash hash, kxld_dict_cmp cmp, 80 u_int num_entries) 81{ 82 kern_return_t rval = KERN_FAILURE; 83 u_int min_buckets = MIN_BUCKETS(num_entries); 84 u_int num_buckets = DEFAULT_DICT_SIZE; 85 86 check(dict); 87 check(hash); 88 check(cmp); 89 90 /* We want the number of allocated buckets to be at least twice that of the 91 * number to be inserted. 92 */ 93 while (min_buckets > num_buckets) { 94 num_buckets *= 2; 95 num_buckets++; 96 } 97 98 /* Allocate enough buckets for the anticipated number of entries */ 99 rval = kxld_array_init(&dict->buckets, sizeof(DictEntry), num_buckets); 100 require_noerr(rval, finish); 101 102 /* Initialize */ 103 dict->hash = hash; 104 dict->cmp = cmp; 105 dict->num_entries = 0; 106 dict->resize_threshold = RESIZE_THRESHOLD(num_buckets); 107 108 rval = KERN_SUCCESS; 109 110finish: 111 return rval; 112} 113 114/******************************************************************************* 115*******************************************************************************/ 116void 117kxld_dict_clear(KXLDDict *dict) 118{ 119 check(dict); 120 121 dict->hash = NULL; 122 dict->cmp = NULL; 123 dict->num_entries = 0; 124 dict->resize_threshold = 0; 125 kxld_array_clear(&dict->buckets); 126 kxld_array_clear(&dict->resize_buckets); 127} 128 129/******************************************************************************* 130*******************************************************************************/ 131void 132kxld_dict_iterator_init(KXLDDictIterator *iter, const KXLDDict *dict) 133{ 134 check(iter); 135 check(dict); 136 137 iter->idx = 0; 138 iter->dict = dict; 139} 140 141/******************************************************************************* 142*******************************************************************************/ 143void 144kxld_dict_deinit(KXLDDict *dict) 145{ 146 check(dict); 147 148 kxld_array_deinit(&dict->buckets); 149 kxld_array_deinit(&dict->resize_buckets); 150} 151 152/******************************************************************************* 153*******************************************************************************/ 154u_int 155kxld_dict_get_num_entries(const KXLDDict *dict) 156{ 157 check(dict); 158 159 return dict->num_entries; 160} 161 162/******************************************************************************* 163*******************************************************************************/ 164void * 165kxld_dict_find(const KXLDDict *dict, const void *key) 166{ 167 kern_return_t rval = KERN_FAILURE; 168 DictEntry *entry = NULL; 169 u_int idx = 0; 170 171 check(dict); 172 check(key); 173 174 rval = get_locate_index(dict, key, &idx); 175 if (rval) return NULL; 176 177 entry = kxld_array_get_item(&dict->buckets, idx); 178 179 return entry->value; 180} 181 182/******************************************************************************* 183* This dictionary uses linear probing, which means that when there is a 184* collision, we just walk along the buckets until a free bucket shows up. 185* A consequence of this is that when looking up an item, items that lie between 186* its hash value and its actual bucket may have been deleted since it was 187* inserted. Thus, we should only stop a lookup when we've wrapped around the 188* dictionary or encountered an EMPTY bucket. 189********************************************************************************/ 190static kern_return_t 191get_locate_index(const KXLDDict *dict, const void *key, u_int *_idx) 192{ 193 kern_return_t rval = KERN_FAILURE; 194 DictEntry *entry = NULL; 195 u_int base, idx; 196 197 base = idx = dict->hash(dict, key); 198 199 /* Iterate until we match the key, wrap, or hit an empty bucket */ 200 entry = kxld_array_get_item(&dict->buckets, idx); 201 while (!dict->cmp(entry->key, key)) { 202 if (entry->state == EMPTY) goto finish; 203 204 idx = (idx + 1) % dict->buckets.nitems; 205 if (idx == base) goto finish; 206 207 entry = kxld_array_get_item(&dict->buckets, idx); 208 } 209 210 check(idx < dict->buckets.nitems); 211 212 *_idx = idx; 213 rval = KERN_SUCCESS; 214 215finish: 216 return rval; 217} 218 219/******************************************************************************* 220*******************************************************************************/ 221kern_return_t 222kxld_dict_insert(KXLDDict *dict, const void *key, void *value) 223{ 224 kern_return_t rval = KERN_FAILURE; 225 DictEntry *entry = NULL; 226 u_int idx = 0; 227 228 check(dict); 229 check(key); 230 check(value); 231 232 /* Resize if we are greater than the capacity threshold. 233 * Note: this is expensive, but the dictionary can be sized correctly at 234 * construction to avoid ever having to do this. 235 */ 236 while (dict->num_entries > dict->resize_threshold) { 237 rval = resize_dict(dict); 238 require_noerr(rval, finish); 239 } 240 241 /* If this function returns FULL after we've already resized appropriately 242 * something is very wrong and we should return an error. 243 */ 244 rval = get_insert_index(dict, key, &idx); 245 require_noerr(rval, finish); 246 247 /* Insert the new key-value pair into the bucket, but only count it as a 248 * new entry if we are not overwriting an existing entry. 249 */ 250 entry = kxld_array_get_item(&dict->buckets, idx); 251 if (entry->state != USED) { 252 dict->num_entries++; 253 entry->key = key; 254 entry->state = USED; 255 } 256 entry->value = value; 257 258 rval = KERN_SUCCESS; 259 260finish: 261 return rval; 262} 263 264/******************************************************************************* 265* Increases the hash table's capacity by 2N+1. Uses dictionary API. Not 266* fast; just correct. 267*******************************************************************************/ 268static kern_return_t 269resize_dict(KXLDDict *dict) 270{ 271 kern_return_t rval = KERN_FAILURE; 272 KXLDArray tmparray; 273 DictEntry *entry = NULL; 274 u_int nbuckets = (dict->buckets.nitems * 2 + 1); 275 u_int i = 0; 276 277 check(dict); 278 279 /* Initialize a new set of buckets to hold more entries */ 280 rval = kxld_array_init(&dict->resize_buckets, sizeof(DictEntry), nbuckets); 281 require_noerr(rval, finish); 282 283 /* Swap the new buckets with the old buckets */ 284 tmparray = dict->buckets; 285 dict->buckets = dict->resize_buckets; 286 dict->resize_buckets = tmparray; 287 288 /* Reset dictionary parameters */ 289 dict->num_entries = 0; 290 dict->resize_threshold = RESIZE_THRESHOLD(dict->buckets.nitems); 291 292 /* Rehash all of the entries */ 293 for (i = 0; i < dict->resize_buckets.nitems; ++i) { 294 entry = kxld_array_get_item(&dict->resize_buckets, i); 295 if (entry->state == USED) { 296 rval = kxld_dict_insert(dict, entry->key, entry->value); 297 require_noerr(rval, finish); 298 } 299 } 300 301 /* Clear the old buckets */ 302 kxld_array_clear(&dict->resize_buckets); 303 304 rval = KERN_SUCCESS; 305 306finish: 307 return rval; 308} 309 310/******************************************************************************* 311* Simple function to find the first empty cell 312*******************************************************************************/ 313static kern_return_t 314get_insert_index(const KXLDDict *dict, const void *key, u_int *r_index) 315{ 316 kern_return_t rval = KERN_FAILURE; 317 DictEntry *entry = NULL; 318 u_int base, idx; 319 320 base = idx = dict->hash(dict, key); 321 322 /* Iterate through the buckets until we find an EMPTY bucket, a DELETED 323 * bucket, or a key match. 324 */ 325 entry = kxld_array_get_item(&dict->buckets, idx); 326 while (entry->state == USED && !dict->cmp(entry->key, key)) { 327 idx = (idx + 1) % dict->buckets.nitems; 328 require_action(base != idx, finish, rval=KERN_FAILURE); 329 entry = kxld_array_get_item(&dict->buckets, idx); 330 } 331 332 *r_index = idx; 333 rval = KERN_SUCCESS; 334 335finish: 336 return rval; 337} 338 339/******************************************************************************* 340*******************************************************************************/ 341void 342kxld_dict_remove(KXLDDict *dict, const void *key, void **value) 343{ 344 kern_return_t rval = KERN_FAILURE; 345 DictEntry *entry = NULL; 346 u_int idx = 0; 347 348 check(dict); 349 check(key); 350 351 /* Find the item */ 352 rval = get_locate_index(dict, key, &idx); 353 if (rval) { 354 if (value) *value = NULL; 355 return; 356 } 357 358 entry = kxld_array_get_item(&dict->buckets, idx); 359 360 /* Save the value if requested */ 361 if (value) *value = entry->value; 362 363 /* Delete the item from the dictionary */ 364 entry->key = NULL; 365 entry->value = NULL; 366 entry->state = DELETED; 367 dict->num_entries--; 368} 369 370/******************************************************************************* 371*******************************************************************************/ 372void 373kxld_dict_iterator_get_next(KXLDDictIterator *iter, const void **key, 374 void **value) 375{ 376 DictEntry *entry = NULL; 377 378 check(iter); 379 check(key); 380 check(value); 381 382 *key = NULL; 383 *value = NULL; 384 385 /* Walk over the dictionary looking for USED buckets */ 386 for (; iter->idx < iter->dict->buckets.nitems; ++(iter->idx)) { 387 entry = kxld_array_get_item(&iter->dict->buckets, iter->idx); 388 if (entry->state == USED) { 389 *key = entry->key; 390 *value = entry->value; 391 ++(iter->idx); 392 break; 393 } 394 } 395} 396 397/******************************************************************************* 398*******************************************************************************/ 399void 400kxld_dict_iterator_reset(KXLDDictIterator *iter) 401{ 402 iter->idx = 0; 403} 404 405/******************************************************************************* 406* This is Daniel Bernstein's hash algorithm from comp.lang.c 407* It's fast and distributes well. Returns an idx into the symbol hash table. 408* NOTE: Will not check for a valid pointer - performance 409*******************************************************************************/ 410u_int 411kxld_dict_string_hash(const KXLDDict *dict, const void *_key) 412{ 413 const char *key = _key; 414 u_int c = 0; 415 u_int hash_val = 5381; 416 417 check(dict); 418 check(_key); 419 420 while ((c = *key++)) { 421 /* hash(i) = hash(i-1) *33 ^ name[i] */ 422 hash_val = ((hash_val << 5) + hash_val) ^ c; 423 } 424 425 return (hash_val % dict->buckets.nitems); 426} 427 428u_int 429kxld_dict_uint32_hash(const KXLDDict *dict, const void *_key) 430{ 431 uint32_t key = *(const uint32_t *) _key; 432 433 check(_key); 434 435 return (u_int) (key % dict->buckets.nitems); 436} 437 438u_int 439kxld_dict_kxldaddr_hash(const KXLDDict *dict, const void *_key) 440{ 441 kxld_addr_t key = *(const kxld_addr_t *) _key; 442 443 check(_key); 444 445 return (u_int) (key % dict->buckets.nitems); 446} 447 448u_int 449kxld_dict_string_cmp(const void *key1, const void *key2) 450{ 451 return streq(key1, key2); 452} 453 454u_int 455kxld_dict_uint32_cmp(const void *key1, const void *key2) 456{ 457 const uint32_t *a = key1; 458 const uint32_t *b = key2; 459 460 return (a && b && (*a == *b)); 461} 462 463u_int 464kxld_dict_kxldaddr_cmp(const void *key1, const void *key2) 465{ 466 const kxld_addr_t *a = key1; 467 const kxld_addr_t *b = key2; 468 469 return (a && b && (*a == *b)); 470} 471 472