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