]>
Commit | Line | Data |
---|---|---|
88e17b57 | 1 | /* Hash tables for Objective C method dispatch. |
748086b7 | 2 | Copyright (C) 1993, 1995, 1996, 2004, 2009 Free Software Foundation, Inc. |
88e17b57 | 3 | |
6c82ad25 | 4 | This file is part of GCC. |
88e17b57 | 5 | |
6c82ad25 | 6 | GCC is free software; you can redistribute it and/or modify |
88e17b57 | 7 | it under the terms of the GNU General Public License as published by |
748086b7 | 8 | the Free Software Foundation; either version 3, or (at your option) |
88e17b57 BE |
9 | any later version. |
10 | ||
6c82ad25 | 11 | GCC is distributed in the hope that it will be useful, |
88e17b57 BE |
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 | ||
748086b7 JJ |
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/>. */ | |
88e17b57 | 24 | |
88e17b57 BE |
25 | |
26 | ||
27 | #ifndef __hash_INCLUDE_GNU | |
28 | #define __hash_INCLUDE_GNU | |
29 | ||
9567d415 AP |
30 | #include <stddef.h> |
31 | #include <string.h> | |
88e17b57 | 32 | |
6f0aa5e1 AP |
33 | #ifdef __cplusplus |
34 | extern "C" { | |
35 | #endif /* __cplusplus */ | |
36 | ||
88e17b57 BE |
37 | /* |
38 | * This data structure is used to hold items | |
39 | * stored in a hash table. Each node holds | |
40 | * a key/value pair. | |
41 | * | |
42 | * Items in the cache are really of type void *. | |
43 | */ | |
44 | typedef struct cache_node | |
45 | { | |
46 | struct cache_node *next; /* Pointer to next entry on the list. | |
47 | NULL indicates end of list. */ | |
48 | const void *key; /* Key used to locate the value. Used | |
49 | to locate value when more than one | |
50 | key computes the same hash | |
51 | value. */ | |
52 | void *value; /* Value stored for the key. */ | |
53 | } *node_ptr; | |
54 | ||
55 | ||
56 | /* | |
57 | * This data type is the function that computes a hash code given a key. | |
58 | * Therefore, the key can be a pointer to anything and the function specific | |
59 | * to the key type. | |
60 | * | |
61 | * Unfortunately there is a mutual data structure reference problem with this | |
62 | * typedef. Therefore, to remove compiler warnings the functions passed to | |
270a1283 | 63 | * objc_hash_new will have to be casted to this type. |
88e17b57 | 64 | */ |
40165636 | 65 | typedef unsigned int (*hash_func_type) (void *, const void *); |
88e17b57 BE |
66 | |
67 | /* | |
68 | * This data type is the function that compares two hash keys and returns an | |
69 | * integer greater than, equal to, or less than 0, according as the first | |
70 | * parameter is lexicographically greater than, equal to, or less than the | |
71 | * second. | |
72 | */ | |
73 | ||
40165636 | 74 | typedef int (*compare_func_type) (const void *, const void *); |
88e17b57 BE |
75 | |
76 | ||
77 | /* | |
78 | * This data structure is the cache. | |
79 | * | |
80 | * It must be passed to all of the hashing routines | |
81 | * (except for new). | |
82 | */ | |
83 | typedef struct cache | |
84 | { | |
85 | /* Variables used to implement the hash itself. */ | |
86 | node_ptr *node_table; /* Pointer to an array of hash nodes. */ | |
87 | /* Variables used to track the size of the hash table so to determine | |
88 | when to resize it. */ | |
89 | unsigned int size; /* Number of buckets allocated for the hash table | |
90 | (number of array entries allocated for | |
91 | "node_table"). Must be a power of two. */ | |
92 | unsigned int used; /* Current number of entries in the hash table. */ | |
93 | unsigned int mask; /* Precomputed mask. */ | |
94 | ||
95 | /* Variables used to implement indexing through the hash table. */ | |
96 | ||
97 | unsigned int last_bucket; /* Tracks which entry in the array where | |
98 | the last value was returned. */ | |
99 | /* Function used to compute a hash code given a key. | |
100 | This function is specified when the hash table is created. */ | |
101 | hash_func_type hash_func; | |
102 | /* Function used to compare two hash keys to see if they are equal. */ | |
103 | compare_func_type compare_func; | |
104 | } *cache_ptr; | |
105 | ||
106 | ||
88e17b57 BE |
107 | /* Allocate and initialize a hash table. */ |
108 | ||
270a1283 DA |
109 | cache_ptr objc_hash_new (unsigned int size, |
110 | hash_func_type hash_func, | |
111 | compare_func_type compare_func); | |
88e17b57 BE |
112 | |
113 | /* Deallocate all of the hash nodes and the cache itself. */ | |
114 | ||
270a1283 | 115 | void objc_hash_delete (cache_ptr cache); |
88e17b57 BE |
116 | |
117 | /* Add the key/value pair to the hash table. If the | |
118 | hash table reaches a level of fullness then it will be resized. | |
119 | ||
120 | assert if the key is already in the hash. */ | |
121 | ||
270a1283 | 122 | void objc_hash_add (cache_ptr *cachep, const void *key, void *value); |
88e17b57 BE |
123 | |
124 | /* Remove the key/value pair from the hash table. | |
125 | assert if the key isn't in the table. */ | |
126 | ||
270a1283 | 127 | void objc_hash_remove (cache_ptr cache, const void *key); |
88e17b57 BE |
128 | |
129 | /* Used to index through the hash table. Start with NULL | |
130 | to get the first entry. | |
131 | ||
132 | Successive calls pass the value returned previously. | |
133 | ** Don't modify the hash during this operation *** | |
134 | ||
135 | Cache nodes are returned such that key or value can | |
136 | be extracted. */ | |
137 | ||
270a1283 | 138 | node_ptr objc_hash_next (cache_ptr cache, node_ptr node); |
88e17b57 BE |
139 | |
140 | /* Used to return a value from a hash table using a given key. */ | |
141 | ||
270a1283 | 142 | void *objc_hash_value_for_key (cache_ptr cache, const void *key); |
88e17b57 BE |
143 | |
144 | /* Used to determine if the given key exists in the hash table */ | |
145 | ||
270a1283 | 146 | BOOL objc_hash_is_key_in_hash (cache_ptr cache, const void *key); |
88e17b57 BE |
147 | |
148 | /************************************************ | |
149 | ||
150 | Useful hashing functions. | |
151 | ||
152 | Declared inline for your pleasure. | |
153 | ||
154 | ************************************************/ | |
155 | ||
156 | /* Calculate a hash code by performing some | |
157 | manipulation of the key pointer. (Use the lowest bits | |
158 | except for those likely to be 0 due to alignment.) */ | |
159 | ||
160 | static inline unsigned int | |
270a1283 | 161 | objc_hash_ptr (cache_ptr cache, const void *key) |
88e17b57 BE |
162 | { |
163 | return ((size_t)key / sizeof (void *)) & cache->mask; | |
164 | } | |
165 | ||
166 | ||
167 | /* Calculate a hash code by iterating over a NULL | |
168 | terminate string. */ | |
169 | static inline unsigned int | |
270a1283 | 170 | objc_hash_string (cache_ptr cache, const void *key) |
88e17b57 BE |
171 | { |
172 | unsigned int ret = 0; | |
173 | unsigned int ctr = 0; | |
d5e63fce | 174 | const char *ckey = (const char *) key; |
88e17b57 | 175 | |
beca20d2 JM |
176 | while (*ckey) { |
177 | ret ^= *ckey++ << ctr; | |
88e17b57 BE |
178 | ctr = (ctr + 1) % sizeof (void *); |
179 | } | |
180 | ||
181 | return ret & cache->mask; | |
182 | } | |
183 | ||
184 | ||
185 | /* Compare two pointers for equality. */ | |
186 | static inline int | |
270a1283 | 187 | objc_compare_ptrs (const void *k1, const void *k2) |
88e17b57 | 188 | { |
0b87e18e | 189 | return (k1 == k2); |
88e17b57 BE |
190 | } |
191 | ||
192 | ||
193 | /* Compare two strings. */ | |
194 | static inline int | |
270a1283 | 195 | objc_compare_strings (const void *k1, const void *k2) |
88e17b57 BE |
196 | { |
197 | if (k1 == k2) | |
198 | return 1; | |
199 | else if (k1 == 0 || k2 == 0) | |
200 | return 0; | |
201 | else | |
d5e63fce | 202 | return ! strcmp ((const char *) k1, (const char *) k2); |
88e17b57 BE |
203 | } |
204 | ||
270a1283 | 205 | |
6f0aa5e1 AP |
206 | #ifdef __cplusplus |
207 | } | |
208 | #endif /* __cplusplus */ | |
209 | ||
88e17b57 BE |
210 | |
211 | #endif /* not __hash_INCLUDE_GNU */ |