|
111
|
1 /* Hash tables for Objective C internal structures
|
|
145
|
2 Copyright (C) 1993-2020 Free Software Foundation, Inc.
|
|
111
|
3
|
|
|
4 This file is part of GCC.
|
|
|
5
|
|
|
6 GCC is free software; you can redistribute it and/or modify
|
|
|
7 it under the terms of the GNU General Public License as published by
|
|
|
8 the Free Software Foundation; either version 3, or (at your option)
|
|
|
9 any later version.
|
|
|
10
|
|
|
11 GCC is distributed in the hope that it will be useful,
|
|
|
12 but WITHOUT ANY WARRANTY; without even the implied warranty of
|
|
|
13 MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the
|
|
|
14 GNU General Public License for more details.
|
|
|
15
|
|
|
16 Under Section 7 of GPL version 3, you are granted additional
|
|
|
17 permissions described in the GCC Runtime Library Exception, version
|
|
|
18 3.1, as published by the Free Software Foundation.
|
|
|
19
|
|
|
20 You should have received a copy of the GNU General Public License and
|
|
|
21 a copy of the GCC Runtime Library Exception along with this program;
|
|
|
22 see the files COPYING3 and COPYING.RUNTIME respectively. If not, see
|
|
|
23 <http://www.gnu.org/licenses/>. */
|
|
|
24
|
|
|
25 #include "objc-private/common.h"
|
|
|
26 #include <assert.h> /* For assert. */
|
|
|
27
|
|
|
28 #include "objc/runtime.h" /* For objc_calloc. */
|
|
|
29 #include "objc-private/hash.h"
|
|
|
30
|
|
|
31 /* These two macros determine when a hash table is full and
|
|
|
32 by how much it should be expanded respectively.
|
|
|
33
|
|
|
34 These equations are percentages. */
|
|
|
35 #define FULLNESS(cache) \
|
|
|
36 ((((cache)->size * 75) / 100) <= (cache)->used)
|
|
|
37 #define EXPANSION(cache) \
|
|
|
38 ((cache)->size * 2)
|
|
|
39
|
|
|
40 cache_ptr
|
|
|
41 objc_hash_new (unsigned int size, hash_func_type hash_func,
|
|
|
42 compare_func_type compare_func)
|
|
|
43 {
|
|
|
44 cache_ptr cache;
|
|
|
45
|
|
|
46 /* Pass me a value greater than 0 and a power of 2. */
|
|
|
47 assert (size);
|
|
|
48 assert (! (size & (size - 1)));
|
|
|
49
|
|
|
50 /* Allocate the cache structure. calloc insures its initialization
|
|
|
51 for default values. */
|
|
|
52 cache = (cache_ptr) objc_calloc (1, sizeof (struct cache));
|
|
|
53 assert (cache);
|
|
|
54
|
|
|
55 /* Allocate the array of buckets for the cache. calloc initializes
|
|
|
56 all of the pointers to NULL. */
|
|
|
57 cache->node_table
|
|
|
58 = (node_ptr *) objc_calloc (size, sizeof (node_ptr));
|
|
|
59 assert (cache->node_table);
|
|
|
60
|
|
|
61 cache->size = size;
|
|
|
62
|
|
|
63 /* This should work for all processor architectures (?). */
|
|
|
64 cache->mask = (size - 1);
|
|
|
65
|
|
|
66 /* Store the hashing function so that codes can be computed. */
|
|
|
67 cache->hash_func = hash_func;
|
|
|
68
|
|
|
69 /* Store the function that compares hash keys to determine if they
|
|
|
70 are equal. */
|
|
|
71 cache->compare_func = compare_func;
|
|
|
72
|
|
|
73 return cache;
|
|
|
74 }
|
|
|
75
|
|
|
76
|
|
|
77 void
|
|
|
78 objc_hash_delete (cache_ptr cache)
|
|
|
79 {
|
|
|
80 node_ptr node;
|
|
|
81 node_ptr next_node;
|
|
|
82 unsigned int i;
|
|
|
83
|
|
|
84 /* Purge all key/value pairs from the table. */
|
|
|
85 /* Step through the nodes one by one and remove every node WITHOUT
|
|
|
86 using objc_hash_next. this makes objc_hash_delete much more
|
|
|
87 efficient. */
|
|
|
88 for (i = 0; i < cache->size; i++)
|
|
|
89 {
|
|
|
90 if ((node = cache->node_table[i]))
|
|
|
91 {
|
|
|
92 /* An entry in the hash table has been found. Now step
|
|
|
93 through the nodes next in the list and free them. */
|
|
|
94 while ((next_node = node->next))
|
|
|
95 {
|
|
|
96 objc_hash_remove (cache,node->key);
|
|
|
97 node = next_node;
|
|
|
98 }
|
|
|
99 objc_hash_remove (cache,node->key);
|
|
|
100 }
|
|
|
101 }
|
|
|
102
|
|
|
103 /* Release the array of nodes and the cache itself. */
|
|
|
104 objc_free(cache->node_table);
|
|
|
105 objc_free(cache);
|
|
|
106 }
|
|
|
107
|
|
|
108
|
|
|
109 void
|
|
|
110 objc_hash_add (cache_ptr *cachep, const void *key, void *value)
|
|
|
111 {
|
|
|
112 size_t indx = (*(*cachep)->hash_func) (*cachep, key);
|
|
|
113 node_ptr node = (node_ptr) objc_calloc (1, sizeof (struct cache_node));
|
|
|
114
|
|
|
115 assert (node);
|
|
|
116
|
|
|
117 /* Initialize the new node. */
|
|
|
118 node->key = key;
|
|
|
119 node->value = value;
|
|
|
120 node->next = (*cachep)->node_table[indx];
|
|
|
121
|
|
|
122 /* Debugging. Check the list for another key. */
|
|
|
123 #ifdef DEBUG
|
|
|
124 {
|
|
|
125 node_ptr node1 = (*cachep)->node_table[indx];
|
|
|
126 while (node1)
|
|
|
127 {
|
|
|
128 assert (node1->key != key);
|
|
|
129 node1 = node1->next;
|
|
|
130 }
|
|
|
131 }
|
|
|
132 #endif
|
|
|
133
|
|
|
134 /* Install the node as the first element on the list. */
|
|
|
135 (*cachep)->node_table[indx] = node;
|
|
|
136
|
|
|
137 /* Bump the number of entries in the cache. */
|
|
|
138 ++(*cachep)->used;
|
|
|
139
|
|
|
140 /* Check the hash table's fullness. We're going to expand if it is
|
|
|
141 above the fullness level. */
|
|
|
142 if (FULLNESS (*cachep))
|
|
|
143 {
|
|
|
144 /* The hash table has reached its fullness level. Time to
|
|
|
145 expand it.
|
|
|
146
|
|
|
147 I'm using a slow method here but is built on other primitive
|
|
|
148 functions thereby increasing its correctness. */
|
|
|
149 node_ptr node1 = NULL;
|
|
|
150 cache_ptr new = objc_hash_new (EXPANSION (*cachep),
|
|
|
151 (*cachep)->hash_func,
|
|
|
152 (*cachep)->compare_func);
|
|
|
153
|
|
|
154 DEBUG_PRINTF ("Expanding cache %#x from %d to %d\n",
|
|
|
155 (int) *cachep, (*cachep)->size, new->size);
|
|
|
156
|
|
|
157 /* Copy the nodes from the first hash table to the new one. */
|
|
|
158 while ((node1 = objc_hash_next (*cachep, node1)))
|
|
|
159 objc_hash_add (&new, node1->key, node1->value);
|
|
|
160
|
|
|
161 /* Trash the old cache. */
|
|
|
162 objc_hash_delete (*cachep);
|
|
|
163
|
|
|
164 /* Return a pointer to the new hash table. */
|
|
|
165 *cachep = new;
|
|
|
166 }
|
|
|
167 }
|
|
|
168
|
|
|
169 void
|
|
|
170 objc_hash_remove (cache_ptr cache, const void *key)
|
|
|
171 {
|
|
|
172 size_t indx = (*cache->hash_func) (cache, key);
|
|
|
173 node_ptr node = cache->node_table[indx];
|
|
|
174
|
|
|
175 /* We assume there is an entry in the table. Error if it is
|
|
|
176 not. */
|
|
|
177 assert (node);
|
|
|
178
|
|
|
179 /* Special case. First element is the key/value pair to be
|
|
|
180 removed. */
|
|
|
181 if ((*cache->compare_func) (node->key, key))
|
|
|
182 {
|
|
|
183 cache->node_table[indx] = node->next;
|
|
|
184 objc_free(node);
|
|
|
185 }
|
|
|
186 else
|
|
|
187 {
|
|
|
188 /* Otherwise, find the hash entry. */
|
|
|
189 node_ptr prev = node;
|
|
|
190 BOOL removed = NO;
|
|
|
191 do
|
|
|
192 {
|
|
|
193 if ((*cache->compare_func) (node->key, key))
|
|
|
194 {
|
|
|
195 prev->next = node->next, removed = YES;
|
|
|
196 objc_free(node);
|
|
|
197 }
|
|
|
198 else
|
|
|
199 prev = node, node = node->next;
|
|
|
200 }
|
|
|
201 while (!removed && node);
|
|
|
202 assert (removed);
|
|
|
203 }
|
|
|
204
|
|
|
205 /* Decrement the number of entries in the hash table. */
|
|
|
206 --cache->used;
|
|
|
207 }
|
|
|
208
|
|
|
209
|
|
|
210 node_ptr
|
|
|
211 objc_hash_next (cache_ptr cache, node_ptr node)
|
|
|
212 {
|
|
|
213 /* If the scan is being started then reset the last node visitied
|
|
|
214 pointer and bucket index. */
|
|
|
215 if (!node)
|
|
|
216 cache->last_bucket = 0;
|
|
|
217
|
|
|
218 /* If there is a node visited last then check for another entry in
|
|
|
219 the same bucket. Otherwise step to the next bucket. */
|
|
|
220 if (node)
|
|
|
221 {
|
|
|
222 if (node->next)
|
|
|
223 {
|
|
|
224 /* There is a node which follows the last node returned.
|
|
|
225 Step to that node and retun it. */
|
|
|
226 return node->next;
|
|
|
227 }
|
|
|
228 else
|
|
|
229 ++cache->last_bucket;
|
|
|
230 }
|
|
|
231
|
|
|
232 /* If the list isn't exhausted then search the buckets for other
|
|
|
233 nodes. */
|
|
|
234 if (cache->last_bucket < cache->size)
|
|
|
235 {
|
|
|
236 /* Scan the remainder of the buckets looking for an entry at
|
|
|
237 the head of the list. Return the first item found. */
|
|
|
238 while (cache->last_bucket < cache->size)
|
|
|
239 if (cache->node_table[cache->last_bucket])
|
|
|
240 return cache->node_table[cache->last_bucket];
|
|
|
241 else
|
|
|
242 ++cache->last_bucket;
|
|
|
243
|
|
|
244 /* No further nodes were found in the hash table. */
|
|
|
245 return NULL;
|
|
|
246 }
|
|
|
247 else
|
|
|
248 return NULL;
|
|
|
249 }
|
|
|
250
|
|
|
251
|
|
|
252 /* Given KEY, return corresponding value for it in CACHE. Return NULL
|
|
|
253 if the KEY is not recorded. */
|
|
|
254 void *
|
|
|
255 objc_hash_value_for_key (cache_ptr cache, const void *key)
|
|
|
256 {
|
|
|
257 node_ptr node = cache->node_table[(*cache->hash_func) (cache, key)];
|
|
|
258 void *retval = NULL;
|
|
|
259
|
|
|
260 if (node)
|
|
|
261 do
|
|
|
262 {
|
|
|
263 if ((*cache->compare_func) (node->key, key))
|
|
|
264 {
|
|
|
265 retval = node->value;
|
|
|
266 break;
|
|
|
267 }
|
|
|
268 else
|
|
|
269 node = node->next;
|
|
|
270 }
|
|
|
271 while (! retval && node);
|
|
|
272
|
|
|
273 return retval;
|
|
|
274 }
|
|
|
275
|
|
|
276 /* Given KEY, return YES if it exists in the CACHE. Return NO if it
|
|
|
277 does not */
|
|
|
278 BOOL
|
|
|
279 objc_hash_is_key_in_hash (cache_ptr cache, const void *key)
|
|
|
280 {
|
|
|
281 node_ptr node = cache->node_table[(*cache->hash_func) (cache, key)];
|
|
|
282
|
|
|
283 if (node)
|
|
|
284 do
|
|
|
285 {
|
|
|
286 if ((*cache->compare_func)(node->key, key))
|
|
|
287 return YES;
|
|
|
288 else
|
|
|
289 node = node->next;
|
|
|
290 }
|
|
|
291 while (node);
|
|
|
292
|
|
|
293 return NO;
|
|
|
294 }
|
