![[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 [GCC 2.x] / gcc / objc|
Return to hash.h CVS log | Up to [GCC 2.x] / gcc / objc |
1.1 root 1: /* Hash tables for Objective C method dispatch.
2: Copyright (C) 1992 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: #include "mutex.h"
31:
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 lexico-graphically 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 fullnes 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 pleaseure.
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 ((unsigned int)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: return !strcmp (k1, k2);
194: }
195:
196:
197: #endif /* not __hash_INCLUDE_GNU */
This archive runs on limited infrastructure. Preserving old code on modern bandwidth. Automated agents are requested to crawl responsibly.