libkern/kxld/kxld_dict.h

   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_ */