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