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