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