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