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 #ifndef _KXLD_DICT_H_ 29 #define _KXLD_DICT_H_ 30 31 #include <sys/types.h> 32 #if KERNEL 33 #include <libkern/kxld_types.h> 34 #else 35 #include "kxld_types.h" 36 #endif 37 38 #include "kxld_array.h" 39 40 /******************************************************************************* 41 * This is a dictionary implementation for hash tables with c-string keys. It 42 * uses linear probing for collision resolution and supports hints for hash 43 * table size as well as automatic resizing. All possible sizes for it are 44 * prime or 'pseudoprime' - good choices for number of buckets. 45 * NOTE: NULL is NOT a valid key or value! 46 * 47 * The dictionary also provides a basic iterator interface. The iterator 48 * supports a basic walk through the dictionary in unsorted order. If the 49 * dictionary is changed in any way while an iterator is being used, the 50 * iterator's behavior is undefined. 51 *******************************************************************************/ 52 53 struct kxld_dict; 54 typedef struct kxld_dict KXLDDict; 55 typedef struct kxld_dict_iterator KXLDDictIterator; 56 57 typedef u_int (*kxld_dict_hash)(const KXLDDict *dict, const void *key); 58 typedef u_int (*kxld_dict_cmp)(const void *key1, const void *key2); 59 60 struct kxld_dict { 61 KXLDArray buckets; // The array of buckets 62 KXLDArray resize_buckets; // A helper array for resizing 63 kxld_dict_hash hash; // Hash function 64 kxld_dict_cmp cmp; // Comparison function 65 u_int num_entries; // Num entries in the dictionary 66 u_int resize_threshold; // Num entries we must reach to cause a resize 67 }; 68 69 struct kxld_dict_iterator { 70 u_int idx; 71 const KXLDDict *dict; 72 }; 73 74 /******************************************************************************* 75 * Constructors and Destructors 76 *******************************************************************************/ 77 78 /* Initializes a new dictionary object. 79 * num_entries is a hint to the maximum number of entries that will be inserted 80 */ 81 kern_return_t kxld_dict_init(KXLDDict *dict, kxld_dict_hash hash, 82 kxld_dict_cmp cmp, u_int num_entries) 83 __attribute__((nonnull, visibility("hidden"))); 84 85 /* Initializes a new dictionary iterator */ 86 void kxld_dict_iterator_init(KXLDDictIterator *iter, const KXLDDict *dict) 87 __attribute__((nonnull, visibility("hidden"))); 88 89 /* Removes all entries from the dictionary. The dictionary must be 90 * reinitialized before it can be used again. 91 */ 92 void kxld_dict_clear(KXLDDict *dict) 93 __attribute__((nonnull, visibility("hidden"))); 94 95 /* Destroys a dictionary and all of its entries */ 96 void kxld_dict_deinit(KXLDDict *dict) 97 __attribute__((nonnull, visibility("hidden"))); 98 99 /******************************************************************************* 100 * Accessors 101 *******************************************************************************/ 102 103 /* Returns the number of entries in the dictionary */ 104 u_int kxld_dict_get_num_entries(const KXLDDict *dict) 105 __attribute__((pure, nonnull, visibility("hidden"))); 106 107 /* Finds a key-value pair and assigns the value to the 'value' pointer, or NULL 108 * when not found. 109 */ 110 void * kxld_dict_find(const KXLDDict *dict, const void *key) 111 __attribute__((pure, nonnull, visibility("hidden"))); 112 113 /******************************************************************************* 114 * Modifiers 115 *******************************************************************************/ 116 117 /* Inserts a key-value pair, and will overwrite the value for a key if that key 118 * is already in the table. 119 */ 120 kern_return_t kxld_dict_insert(KXLDDict *dict, const void *key, void *value) 121 __attribute__((nonnull, visibility("hidden"))); 122 123 /* Removes a key-value pair and assigns the value to the 'value' pointer. 124 * 'value' pointer will be set to NULL if value to be removed is not found. 125 * 'value pointer may be NULL if removed value is not needed. 126 */ 127 void kxld_dict_remove(KXLDDict *dict, const void *key, void **value) 128 __attribute__((nonnull(1, 2), visibility("hidden"))); 129 130 /* Gets the next item in the dictionary */ 131 void kxld_dict_iterator_get_next(KXLDDictIterator *iter, const void **key, 132 void **value) 133 __attribute__((nonnull, visibility("hidden"))); 134 135 /* Resets the iterator to the first item in the dictionary */ 136 void kxld_dict_iterator_reset(KXLDDictIterator *iter) 137 __attribute__((nonnull, visibility("hidden"))); 138 139 /******************************************************************************* 140 * Helpers 141 *******************************************************************************/ 142 143 u_int kxld_dict_string_hash(const KXLDDict *dict, const void *key) 144 __attribute__((pure, nonnull, visibility("hidden"))); 145 u_int kxld_dict_uint32_hash(const KXLDDict *dict, const void *key) 146 __attribute__((pure, nonnull, visibility("hidden"))); 147 u_int kxld_dict_kxldaddr_hash(const KXLDDict *dict, const void *key) 148 __attribute__((pure, nonnull, visibility("hidden"))); 149 150 u_int kxld_dict_string_cmp(const void *key1, const void *key2) 151 __attribute__((pure, visibility("hidden"))); 152 u_int kxld_dict_uint32_cmp(const void *key1, const void *key2) 153 __attribute__((pure, visibility("hidden"))); 154 u_int kxld_dict_kxldaddr_cmp(const void *key1, const void *key2) 155 __attribute__((pure, visibility("hidden"))); 156 157 #endif /* _KXLD_DICT_H_ */ 158