]>
Commit | Line | Data |
---|---|---|
437b9337 | 1 | /* Hash tables for Objective C method dispatch. |
cc06bcdb | 2 | Copyright (C) 1993, 1995, 1996 Free Software Foundation, Inc. |
2a425bd5 DG |
3 | |
4 | This file is part of GNU CC. | |
5 | ||
6 | GNU CC 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 2, or (at your option) | |
9 | any later version. | |
10 | ||
11 | GNU CC 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 | You should have received a copy of the GNU General Public License | |
17 | along with GNU CC; see the file COPYING. If not, write to | |
84c09f78 RK |
18 | the Free Software Foundation, 59 Temple Place - Suite 330, |
19 | Boston, MA 02111-1307, USA. */ | |
2a425bd5 DG |
20 | |
21 | /* As a special exception, if you link this library with files | |
22 | compiled with GCC to produce an executable, this does not cause | |
23 | the resulting executable to be covered by the GNU General Public License. | |
24 | This exception does not however invalidate any other reasons why | |
25 | the executable file might be covered by the GNU General Public License. */ | |
26 | ||
4217c456 | 27 | |
437b9337 RS |
28 | #ifndef __hash_INCLUDE_GNU |
29 | #define __hash_INCLUDE_GNU | |
4217c456 | 30 | |
d2a1b32f | 31 | #include <stddef.h> |
cc06bcdb | 32 | #include <objc/objc.h> |
4217c456 DG |
33 | |
34 | /* | |
35 | * This data structure is used to hold items | |
36 | * stored in a hash table. Each node holds | |
37 | * a key/value pair. | |
38 | * | |
437b9337 | 39 | * Items in the cache are really of type void *. |
4217c456 | 40 | */ |
437b9337 RS |
41 | typedef struct cache_node |
42 | { | |
d0bd180d RS |
43 | struct cache_node *next; /* Pointer to next entry on the list. |
44 | NULL indicates end of list. */ | |
437b9337 | 45 | const void *key; /* Key used to locate the value. Used |
d0bd180d | 46 | to locate value when more than one |
f847fb39 RS |
47 | key computes the same hash |
48 | value. */ | |
d0bd180d RS |
49 | void *value; /* Value stored for the key. */ |
50 | } *node_ptr; | |
4217c456 DG |
51 | |
52 | ||
2db2bea5 DG |
53 | /* |
54 | * This data type is the function that computes a hash code given a key. | |
55 | * Therefore, the key can be a pointer to anything and the function specific | |
56 | * to the key type. | |
57 | * | |
58 | * Unfortunately there is a mutual data structure reference problem with this | |
59 | * typedef. Therefore, to remove compiler warnings the functions passed to | |
f847fb39 | 60 | * hash_new will have to be casted to this type. |
2db2bea5 | 61 | */ |
437b9337 | 62 | typedef unsigned int (*hash_func_type)(void *, const void *); |
2db2bea5 DG |
63 | |
64 | /* | |
65 | * This data type is the function that compares two hash keys and returns an | |
66 | * integer greater than, equal to, or less than 0, according as the first | |
abc95ed3 | 67 | * parameter is lexicographically greater than, equal to, or less than the |
2db2bea5 DG |
68 | * second. |
69 | */ | |
70 | ||
437b9337 | 71 | typedef int (*compare_func_type)(const void *, const void *); |
2db2bea5 DG |
72 | |
73 | ||
4217c456 DG |
74 | /* |
75 | * This data structure is the cache. | |
76 | * | |
77 | * It must be passed to all of the hashing routines | |
cb21dc23 | 78 | * (except for new). |
4217c456 | 79 | */ |
437b9337 RS |
80 | typedef struct cache |
81 | { | |
d0bd180d | 82 | /* Variables used to implement the hash itself. */ |
437b9337 | 83 | node_ptr *node_table; /* Pointer to an array of hash nodes. */ |
d0bd180d RS |
84 | /* Variables used to track the size of the hash table so to determine |
85 | when to resize it. */ | |
86 | unsigned int size; /* Number of buckets allocated for the hash table | |
87 | (number of array entries allocated for | |
88 | "node_table"). Must be a power of two. */ | |
89 | unsigned int used; /* Current number of entries in the hash table. */ | |
90 | unsigned int mask; /* Precomputed mask. */ | |
91 | ||
92 | /* Variables used to implement indexing through the hash table. */ | |
93 | ||
94 | unsigned int last_bucket; /* Tracks which entry in the array where | |
95 | the last value was returned. */ | |
f847fb39 | 96 | /* Function used to compute a hash code given a key. |
d0bd180d RS |
97 | This function is specified when the hash table is created. */ |
98 | hash_func_type hash_func; | |
99 | /* Function used to compare two hash keys to see if they are equal. */ | |
100 | compare_func_type compare_func; | |
101 | } *cache_ptr; | |
102 | ||
103 | ||
437b9337 RS |
104 | /* Two important hash tables. */ |
105 | extern cache_ptr module_hash_table, class_hash_table; | |
106 | ||
d0bd180d RS |
107 | /* Allocate and initialize a hash table. */ |
108 | ||
109 | cache_ptr hash_new (unsigned int size, | |
437b9337 RS |
110 | hash_func_type hash_func, |
111 | compare_func_type compare_func); | |
f847fb39 | 112 | |
d0bd180d RS |
113 | /* Deallocate all of the hash nodes and the cache itself. */ |
114 | ||
115 | void hash_delete (cache_ptr cache); | |
f847fb39 RS |
116 | |
117 | /* Add the key/value pair to the hash table. If the | |
9faa82d8 | 118 | hash table reaches a level of fullness then it will be resized. |
eedb4710 | 119 | |
d0bd180d RS |
120 | assert if the key is already in the hash. */ |
121 | ||
437b9337 | 122 | void hash_add (cache_ptr *cachep, const void *key, void *value); |
f847fb39 RS |
123 | |
124 | /* Remove the key/value pair from the hash table. | |
d0bd180d RS |
125 | assert if the key isn't in the table. */ |
126 | ||
437b9337 | 127 | void hash_remove (cache_ptr cache, const void *key); |
f847fb39 RS |
128 | |
129 | /* Used to index through the hash table. Start with NULL | |
130 | to get the first entry. | |
4217c456 | 131 | |
f847fb39 RS |
132 | Successive calls pass the value returned previously. |
133 | ** Don't modify the hash during this operation *** | |
4217c456 | 134 | |
f847fb39 | 135 | Cache nodes are returned such that key or value can |
d0bd180d RS |
136 | be extracted. */ |
137 | ||
138 | node_ptr hash_next (cache_ptr cache, node_ptr node); | |
2db2bea5 | 139 | |
f847fb39 | 140 | /* Used to return a value from a hash table using a given key. */ |
d0bd180d | 141 | |
437b9337 | 142 | void *hash_value_for_key (cache_ptr cache, const void *key); |
2db2bea5 | 143 | |
cc06bcdb RK |
144 | /* Used to determine if the given key exists in the hash table */ |
145 | ||
146 | BOOL hash_is_key_in_hash (cache_ptr cache, const void *key); | |
2db2bea5 DG |
147 | |
148 | /************************************************ | |
149 | ||
2a425bd5 DG |
150 | Useful hashing functions. |
151 | ||
d09c6323 | 152 | Declared inline for your pleasure. |
2a425bd5 | 153 | |
2db2bea5 DG |
154 | ************************************************/ |
155 | ||
f847fb39 | 156 | /* Calculate a hash code by performing some |
437b9337 RS |
157 | manipulation of the key pointer. (Use the lowest bits |
158 | except for those likely to be 0 due to alignment.) */ | |
159 | ||
33d9bef5 | 160 | static inline unsigned int |
97d5530d | 161 | hash_ptr (cache_ptr cache, const void *key) |
f847fb39 | 162 | { |
33d9bef5 | 163 | return ((size_t)key / sizeof (void *)) & cache->mask; |
2db2bea5 DG |
164 | } |
165 | ||
2db2bea5 | 166 | |
f847fb39 | 167 | /* Calculate a hash code by iterating over a NULL |
d0bd180d | 168 | terminate string. */ |
f847fb39 | 169 | static inline unsigned int |
437b9337 | 170 | hash_string (cache_ptr cache, const void *key) |
f847fb39 RS |
171 | { |
172 | unsigned int ret = 0; | |
173 | unsigned int ctr = 0; | |
2a425bd5 DG |
174 | |
175 | ||
d0bd180d RS |
176 | while (*(char*)key) { |
177 | ret ^= *(char*)key++ << ctr; | |
178 | ctr = (ctr + 1) % sizeof (void *); | |
c7d30f66 | 179 | } |
2db2bea5 | 180 | |
d0bd180d | 181 | return ret & cache->mask; |
2db2bea5 DG |
182 | } |
183 | ||
184 | ||
97d5530d | 185 | /* Compare two pointers for equality. */ |
2db2bea5 | 186 | static inline int |
97d5530d | 187 | compare_ptrs (const void *k1, const void *k2) |
f847fb39 | 188 | { |
97d5530d | 189 | return !(k1 - k2); |
2db2bea5 DG |
190 | } |
191 | ||
192 | ||
d0bd180d | 193 | /* Compare two strings. */ |
2db2bea5 | 194 | static inline int |
437b9337 | 195 | compare_strings (const void *k1, const void *k2) |
f847fb39 | 196 | { |
6c8747b1 RS |
197 | if (k1 == k2) |
198 | return 1; | |
199 | else if (k1 == 0 || k2 == 0) | |
200 | return 0; | |
201 | else | |
202 | return !strcmp (k1, k2); | |
2db2bea5 | 203 | } |
4217c456 DG |
204 | |
205 | ||
437b9337 | 206 | #endif /* not __hash_INCLUDE_GNU */ |