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 53struct kxld_dict; 54typedef struct kxld_dict KXLDDict; 55typedef struct kxld_dict_iterator KXLDDictIterator; 56 57typedef u_int (*kxld_dict_hash)(const KXLDDict *dict, const void *key); 58typedef u_int (*kxld_dict_cmp)(const void *key1, const void *key2); 59 60struct 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 69struct 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 */ 81kern_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 */ 86void 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 */ 92void kxld_dict_clear(KXLDDict *dict) 93 __attribute__((nonnull, visibility("hidden"))); 94 95/* Destroys a dictionary and all of its entries */ 96void 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 */ 104u_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 */ 110void * 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 */ 120kern_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 */ 127void 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 */ 131void 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 */ 136void kxld_dict_iterator_reset(KXLDDictIterator *iter) 137 __attribute__((nonnull, visibility("hidden"))); 138 139/******************************************************************************* 140* Helpers 141*******************************************************************************/ 142 143u_int kxld_dict_string_hash(const KXLDDict *dict, const void *key) 144 __attribute__((pure, nonnull, visibility("hidden"))); 145u_int kxld_dict_uint32_hash(const KXLDDict *dict, const void *key) 146 __attribute__((pure, nonnull, visibility("hidden"))); 147u_int kxld_dict_kxldaddr_hash(const KXLDDict *dict, const void *key) 148 __attribute__((pure, nonnull, visibility("hidden"))); 149 150u_int kxld_dict_string_cmp(const void *key1, const void *key2) 151 __attribute__((pure, visibility("hidden"))); 152u_int kxld_dict_uint32_cmp(const void *key1, const void *key2) 153 __attribute__((pure, visibility("hidden"))); 154u_int kxld_dict_kxldaddr_cmp(const void *key1, const void *key2) 155 __attribute__((pure, visibility("hidden"))); 156 157#endif /* _KXLD_DICT_H_ */ 158