2 * CDE - Common Desktop Environment
4 * Copyright (c) 1993-2012, The Open Group. All rights reserved.
6 * These libraries and programs are free software; you can
7 * redistribute them and/or modify them under the terms of the GNU
8 * Lesser General Public License as published by the Free Software
9 * Foundation; either version 2 of the License, or (at your option)
12 * These libraries and programs are distributed in the hope that
13 * they will be useful, but WITHOUT ANY WARRANTY; without even the
14 * implied warranty of MERCHANTABILITY or FITNESS FOR A PARTICULAR
15 * PURPOSE. See the GNU Lesser General Public License for more
18 * You should have received a copy of the GNU Lesser General Public
19 * License along with these librararies and programs; if not, write
20 * to the Free Software Foundation, Inc., 51 Franklin Street, Fifth
21 * Floor, Boston, MA 02110-1301 USA
23 /* $XConsortium: Hash.c /main/4 1995/10/26 15:22:41 rswiston $ */
25 * (c) Copyright 1993, 1994 Hewlett-Packard Company *
26 * (c) Copyright 1993, 1994 International Business Machines Corp. *
27 * (c) Copyright 1993, 1994 Sun Microsystems, Inc. *
28 * (c) Copyright 1993, 1994 Novell, Inc. *
30 /***********************************************************
31 Copyright 1987, 1988, 1990 by Digital Equipment Corporation, Maynard,
32 Massachusetts, and the Massachusetts Institute of Technology, Cambridge,
37 Permission to use, copy, modify, and distribute this software and its
38 documentation for any purpose and without fee is hereby granted,
39 provided that the above copyright notice appear in all copies and that
40 both that copyright notice and this permission notice appear in
41 supporting documentation, and that the names of Digital or MIT not be
42 used in advertising or publicity pertaining to distribution of the
43 software without specific, written prior permission.
45 DIGITAL DISCLAIMS ALL WARRANTIES WITH REGARD TO THIS SOFTWARE, INCLUDING
46 ALL IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS, IN NO EVENT SHALL
47 DIGITAL BE LIABLE FOR ANY SPECIAL, INDIRECT OR CONSEQUENTIAL DAMAGES OR
48 ANY DAMAGES WHATSOEVER RESULTING FROM LOSS OF USE, DATA OR PROFITS,
49 WHETHER IN AN ACTION OF CONTRACT, NEGLIGENCE OR OTHER TORTIOUS ACTION,
50 ARISING OUT OF OR IN CONNECTION WITH THE USE OR PERFORMANCE OF THIS
53 ******************************************************************/
57 /******** Static Function Declarations ********/
59 static unsigned int GetTableIndex(
60 register DtHashTable tab,
61 register DtHashKey key,
62 #if NeedWidePrototypes
65 register Boolean new) ;
66 #endif /* NeedWidePrototypes */
67 static void ExpandHashTable(
68 register DtHashTable tab) ;
70 /******** End Static Function Declarations ********/
73 typedef unsigned long Signature;
75 typedef struct _DtHashTableRec {
76 unsigned int mask; /* size of hash table - 1 */
77 unsigned int rehash; /* mask - 2 */
78 unsigned int occupied; /* number of occupied entries */
79 unsigned int fakes; /* number occupied by DTHASHfake */
80 DtHashEntryType *types; /* lookup methods for key */
81 unsigned short numTypes; /* number of lookup methods */
82 Boolean keyIsString; /* whether the hash key is a string */
83 DtHashEntry *entries; /* the entries */
86 static DtHashEntryRec DtHashfake; /* placeholder for deletions */
88 #define HASH(tab,sig) ((sig) & tab->mask)
89 #define REHASHVAL(tab, idx) ((((idx) % tab->rehash) + 2) | 1)
90 #define REHASH(tab,idx,rehash) ((idx + rehash) & tab->mask)
91 #define KEY(tab, entry) \
92 ((* (tab->types[entry->hash.type]->hash.getKeyFunc) ) \
93 (entry, tab->types[entry->hash.type]->hash.getKeyClientData))
95 #define RELEASE_KEY(tab, entry, key) \
97 if (tab->types[entry->hash.type]->hash.releaseKeyProc) \
98 (* (tab->types[entry->hash.type]->hash.releaseKeyProc)) \
104 register DtHashTable tab,
105 register DtHashKey key,
106 #if NeedWidePrototypes
109 register Boolean new)
110 #endif /* NeedWidePrototypes */
112 register DtHashEntry *entries = tab->entries;
113 register int len, idx, i, rehash = 0;
115 register Signature sig = 0;
116 register DtHashEntry entry;
120 if (tab->keyIsString) {
122 for (s2 = (char *)s1; c = *s2++; )
123 sig = (sig << 1) + c;
127 sig = (Signature)key;
129 idx = HASH(tab, sig);
130 while (entry = entries[idx]) {
131 if (entries[idx] == &DtHashfake) {
137 if (tab->keyIsString) {
138 compKey = KEY(tab, entry);
139 for (i = len, s1 = (String)key, s2 = (String) compKey;
146 if ((compKey = KEY(tab, entry)) != key)
154 RELEASE_KEY(tab, entry, compKey);
156 rehash = REHASHVAL(tab, idx);
157 idx = REHASH(tab, idx, rehash);
161 RELEASE_KEY(tab, entry, compKey);
170 _DtRegisterHashEntry(
171 register DtHashTable tab,
172 register DtHashKey key,
173 register DtHashEntry entry )
177 if ((tab->occupied + (tab->occupied >> 2)) > tab->mask)
178 ExpandHashTable(tab);
180 idx = GetTableIndex(tab, key, True);
181 if (tab->entries[idx] == &DtHashfake)
184 tab->entries[idx] = entry;
188 _DtUnregisterHashEntry(
189 register DtHashTable tab,
190 register DtHashEntry entry )
192 register int idx, rehash;
193 register DtHashEntry *entries = tab->entries;
194 DtHashKey key = KEY(tab, entry);
196 idx = GetTableIndex(tab, key, False);
197 RELEASE_KEY(tab, entry, key);
198 entries[idx] = &DtHashfake;
206 register DtHashTable tab )
208 unsigned int oldmask;
209 register DtHashEntry *oldentries, *entries;
210 register int oldidx, newidx, rehash, len;
211 register DtHashEntry entry;
212 register DtHashKey key;
215 oldentries = tab->entries;
217 if ((tab->occupied + (tab->occupied >> 2)) > tab->mask) {
218 tab->mask = (tab->mask << 1) + 1;
219 tab->rehash = tab->mask - 2;
221 entries = tab->entries = (DtHashEntry *) XtCalloc(tab->mask+1, sizeof(DtHashEntry));
222 for (oldidx = 0; oldidx <= oldmask; oldidx++) {
223 if ((entry = oldentries[oldidx]) && entry != &DtHashfake) {
224 newidx = GetTableIndex(tab, key = KEY(tab, entry), True);
225 RELEASE_KEY(tab, entry, key);
226 entries[newidx] = entry;
229 XtFree((char *)oldentries);
234 _DtEnumerateHashTable(
235 register DtHashTable tab,
236 register DtHashEnumerateFunc enumFunc,
237 register XtPointer clientData )
239 register unsigned int i;
241 for (i = 0; i <= tab->mask; i++)
242 if (tab->entries[i] &&
243 tab->entries[i] != &DtHashfake &&
244 ((*enumFunc) (tab->entries[i], clientData)))
245 return tab->entries[i];
252 register DtHashTable tab,
253 register DtHashKey key )
255 register int idx, rehash, len;
256 register DtHashEntry entry, *entries = tab->entries;
258 if (!key) return NULL;
259 idx = GetTableIndex(tab, key, False);
264 _DtAllocHashTable(DtHashEntryType *hashEntryTypes,
265 Cardinal numHashEntryTypes,
266 #if NeedWidePrototypes
270 #endif /* NeedWidePrototypes */
272 register DtHashTable tab;
274 tab = (DtHashTable) XtMalloc(sizeof(struct _DtHashTableRec));
275 tab->types = hashEntryTypes;
276 tab->numTypes = numHashEntryTypes;
277 tab->keyIsString = keyIsString;
279 tab->rehash = tab->mask - 2;
280 tab->entries = (DtHashEntry *) XtCalloc(tab->mask+1, sizeof(DtHashEntry));
288 DtHashTable hashTable )
290 XtFree((char *)hashTable->entries);
291 XtFree((char *)hashTable);