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