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 libraries 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/1 1996/04/21 19:23:21 drk $ */
25 * (c) Copyright 1993, 1994 Hewlett-Packard Company
26 * (c) Copyright 1993, 1994 International Business Machines Corp.
27 * (c) Copyright 1993, 1994 Novell, Inc.
28 * (c) Copyright 1993, 1994 Sun Microsystems, Inc.
37 void * _DtCmMakeHash(int size)
39 void * _DtCmMakeIHash(int size)
41 void ** _DtCmGetHash(void * tbl, unsigned char * key)
43 void ** _DtCmFindHash(void * tbl,unsigned char * key)
45 void ** _DtCmDelHash(void * tbl, unsigned char * key)
47 int _DtCmOperateHash(void * tbl, void (*op_func)(), void * usr_arg)
49 void _DtCmDestroyHash(void * tbl, int (*des_func)(), void * usr_arg)
54 These routines provide a general purpose hash table facility that
55 supports multiple open hash tables. Each entry in the table consists of a
56 key and a data ptr. The key is a null terminated character string, while
57 the data ptr is opaque. Since all the entries are maintained in a doubly
58 linked lists, deletions and operations on entire table execute very quickly.
59 This make these routines suitable for use when the tables may be very ephemeral.
61 _DtCmMakeHash returns a pointer to the created table. The size argument
62 indicate the number of buckets the routine is to allocate. This should be ~
63 the max number of items expected in the table for maximum performance....
64 but /2 or /3 should still be ok. Note that for maximum efficiency the hash
65 table size should be a prime number (a side effect of the hash alorithm).
67 _DtCmMakeIHash performs the same function as _DtCmMakeHash, except that the hash
68 routines will use the key arguments as arbitrary integers rather than strings.
70 _DtCmGetHash searches the specified hash table tbl for an entry with the
71 specified key. If the entry does not exist, it is created with a NULL data
72 ptr. The routine returns a ptr to the area where the data ptr is (can be)
75 _DtCmFindHash searchs the table for an entry with the specified key. If the
76 entry is found, the address of the data pointer associated with the key is
77 returned. If no such entry exists, the routine returns NULL.
79 _DtCmDelHash deletes the specified table entry and returns the associated data
80 ptr. If the entry did not exist ( or the data ptr was NULL), the routine
83 _DtCmOperateHash calls the routine pointed to by op_func once for each entry
84 in tbl, with three arguments: the data ptr, the usr_arg ptr and a ptr to the
85 key for that entry (which should NOT be altered). This is useful for
86 transversing a hash table quickly and operating on the entries. Note that
87 the order of the traversal of the hash table is the reverse order of
90 _DtCmDestroyHash destroys the specified hash table after operating on it
91 with the specified des_func function as described for _DtCmOperateHash. All storage
92 allocated by the hash routines is reclaimed.
94 Author: Bart Smaalders 1/89
98 #include <EUSCompat.h>
99 #include <stdio.h> /* grab NULL define */
104 static int hash_string();
106 typedef struct hash_entry {
115 typedef struct hash {
119 enum hash_type { String_Key = 0 , Integer_Key = 1} hash_type;
123 void * _DtCmMakeHash(int size)
127 ptr = (hash *) malloc(sizeof(*ptr));
129 ptr->table = (hash_entry **) malloc( (unsigned) (sizeof(hash_entry *) * size) );
130 (void)memset((char *) ptr->table, (char) 0, sizeof(hash_entry *)*size);
132 ptr->hash_type = String_Key;
136 void ** _DtCmGetHash(void * t, const unsigned char * key)
138 hash * tbl = (hash *) t;
143 if(tbl->hash_type == String_Key)
144 tmp = tbl->table[bucket = hash_string(key, tbl->size)];
146 tmp = tbl->table[bucket = abs((long)key) % tbl->size];
148 if(tbl->hash_type == String_Key)
151 if(strcmp((char *)tmp->key, (char *)key)==0)
153 tmp = tmp->next_entry;
160 tmp = tmp->next_entry;
165 insert new entry into bucket...
168 new = (hash_entry *) malloc(sizeof(*new));
169 new->key = (unsigned char *)((tbl->hash_type == String_Key)?(unsigned char *)strdup((char *)key):key);
171 hook into chain from tbl...
173 new->right_entry = NULL;
174 new->left_entry = tbl->start;
177 hook into bucket chain
179 new->next_entry = tbl->table[bucket];
180 tbl->table[bucket] = new;
181 new->data = NULL; /* so we know that it is new */
182 return((void*)& new->data);
185 void ** _DtCmFindHash(void * t, const unsigned char * key)
187 hash * tbl = (hash *) t;
190 if(tbl->hash_type == String_Key)
192 tmp = tbl->table[hash_string(key, tbl->size)];
193 for(;tmp!=NULL; tmp = tmp->next_entry)
194 if(!strcmp((char *)tmp->key, (char *)key))
195 return((void *)&tmp->data);
199 tmp = tbl->table[abs((long)key) % tbl->size];
200 for(;tmp!=NULL; tmp = tmp->next_entry)
202 return((void *)&tmp->data);
208 void _DtCmDestroyHash(void * t, int (*ptr)(), void * usr_arg)
210 hash * tbl = (hash *) t;
211 hash_entry * tmp = tbl->start, * prev;
216 (*ptr)(tmp->data,usr_arg, tmp->key);
218 if(tbl->hash_type == String_Key)
221 tmp = tmp->left_entry;
224 free((char *)tbl->table);
228 static int hash_string(char *s, int modulo)
234 result += (*s++ << i++);
236 return(result % modulo);