Debian Codegraph @

gui/GraphLib/libsrc/uimxR5/src/hashtable.c

raw
1 /*---------------------------------------------------------------------
2 *---------------------------------------------------------------------
3 *
4 *
5 * Copyright (c) 1992, Visual Edge Software Ltd.
6 *
7 * ALL RIGHTS RESERVED. Permission to use, copy, modify, and
8 * distribute this software and its documentation for any purpose
9 * and without fee is hereby granted, provided that the above
10 * copyright notice appear in all copies and that both that
11 * copyright notice and this permission notice appear in supporting
12 * documentation, and that the name of Visual Edge Software not be
13 * used in advertising or publicity pertaining to distribution of
14 * the software without specific, written prior permission. The year
15 * included in the notice is the year of the creation of the work.
16 *-------------------------------------------------------------------*/
17 /*
18 * Copyright 1990, 1991 GROUPE BULL
19 *
20 * Permission to use, copy, modify, and distribute this software and its
21 * documentation for any purpose and without fee is hereby granted, provided
22 * that the above copyright notice appear in all copies and that both that
23 * copyright notice and this permission notice appear in supporting
24 * documentation, and that the name of GROUPE BULL not be used in advertising
25 * or publicity pertaining to distribution of the software without specific,
26 * written prior permission. GROUPE BULL makes no representations about the
27 * suitability of this software for any purpose. It is provided "as is"
28 * without express or implied warranty.
29 *
30 * GROUPE BULL disclaims all warranties with regard to this software,
31 * including all implied warranties of merchantability and fitness,
32 * in no event shall GROUPE BULL be liable for any special,
33 * indirect or consequential damages or any damages
34 * whatsoever resulting from loss of use, data or profits,
35 * whether in an action of contract, negligence or other tortious
36 * action, arising out of or in connection with the use
37 * or performance of this software.
38 *
39
40 .VERSION
41 090818 last modif
42
43 */
44
45 /*****************************************************************************\
46 * hashtable.c: *
47 * *
48 * XPM library *
49 * *
50 * Developed by Arnaud Le Hors *
51 * this originaly comes from Colas Nahaboo as a part of Wool *
52 * *
53 \*****************************************************************************/
54
55 #include <stdlib.h>
56
57 #include "xpmP.h"
58
59 LFUNC(AtomMake, xpmHashAtom, (char *name, void *data));
60 LFUNC(HashTableGrows, int, (xpmHashTable *table));
61
62 static xpmHashAtom
63 AtomMake(name, data) /* makes an atom */
64 char *name; /* WARNING: is just pointed to */
65 void *data;
66 {
67 xpmHashAtom object =
68 (xpmHashAtom) malloc((size_t)(sizeof(struct _xpmHashAtom)));
69 if (object) {
70 object->name = name;
71 object->data = data;
72 }
73 return object;
74 }
75
76 /************************\
77 * *
78 * hash table routines *
79 * *
80 \************************/
81
82 /*
83 * Hash function definition:
84 * HASH_FUNCTION: hash function, hash = hashcode, hp = pointer on char,
85 * hash2 = temporary for hashcode.
86 * INITIAL_TABLE_SIZE in slots
87 * HASH_TABLE_GROWS how hash table grows.
88 */
89
90 /* Mock lisp function */
91 /*
92 #define HASH_FUNCTION hash = (hash << 5) - hash + *hp++;
93 #define INITIAL_HASH_SIZE 2017
94 #define HASH_TABLE_GROWS size = size * 2;
95 */
96
97 /* aho-sethi-ullman's HPJ (sizes should be primes)*/
98
99 #define HASH_FUNCTION hash <<= 4; hash += *hp++; \
100 if((hash2 = hash & 0xf0000000)) hash ^= (hash2 >> 24) ^ hash2;
101 /* #define INITIAL_HASH_SIZE 4095 */ /* should be 2^n - 1 */
102 #define INITIAL_HASH_SIZE 288 /* should be enough for colors */
103 #define HASH_TABLE_GROWS size = (size << 1) + 1;
104
105 /* GNU emacs function */
106 /*
107 #define HASH_FUNCTION hash = (hash << 3) + (hash >> 28) + *hp++;
108 #define INITIAL_HASH_SIZE 2017
109 #define HASH_TABLE_GROWS size = size * 2;
110 */
111
112 /* end of hash functions */
113
114 /*
115 * The hash table is used to store atoms via their NAME:
116 *
117 * NAME --hash--> ATOM |--name--> "foo"
118 * |--data--> any value which has to be stored
119 *
120 */
121
122 /*
123 * xpmHashSlot gives the slot (pointer to xpmHashAtom) of a name
124 * (slot points to NULL if it is not defined)
125 *
126 */
127
128 xpmHashAtom *
129 xpmHashSlot(table, s)
130 xpmHashTable *table;
131 char *s;
132 {
133 xpmHashAtom *atomTable = table->atomTable;
134 unsigned int hash, hash2;
135 xpmHashAtom *p;
136 char *hp = s;
137 char *ns;
138
139 hash = 0;
140 while ((*hp)) { /* computes hash function */
141 HASH_FUNCTION
142 }
143 p = atomTable + hash % table->size;
144 while ((*p)) {
145 ns = (*p)->name;
146 if (ns[0] == s[0] && strcmp(ns, s) == 0)
147 break;
148 p--;
149 if (p < atomTable)
150 p = atomTable + table->size - 1;
151 }
152 return p;
153 }
154
155 static int
156 HashTableGrows(table)
157 xpmHashTable *table;
158 {
159 xpmHashAtom *atomTable = table->atomTable;
160 int size = table->size;
161 xpmHashAtom *t, *p;
162 int i;
163 int oldSize = size;
164
165 t = atomTable;
166 HASH_TABLE_GROWS
167 table->size = size;
168 table->limit = size / 3;
169 atomTable = (xpmHashAtom *) malloc((size_t)(size*sizeof(*atomTable)));
170 table->atomTable = atomTable;
171 for (p = atomTable + size; p > atomTable;)
172 *--p = NULL;
173 for (i = 0, p = t; i < oldSize; i++, p++)
174 if (*p) {
175 xpmHashAtom *ps = xpmHashSlot(table, (*p)->name);
176 *ps = *p;
177 }
178 free(t);
179 return 0;
180 }
181
182 /*
183 * xpmHashIntern(table, name, data)
184 * return an xpmHashAtom, which is the one at the slot, if present,
185 * or is created if name didn't exist, with the given data.
186 */
187
188 xpmHashAtom
189 xpmHashIntern(table, tag, data)
190 xpmHashTable *table;
191 char *tag;
192 void *data;
193 {
194 xpmHashAtom *slot;
195
196 if (!*(slot = xpmHashSlot(table, tag))) {
197 /* undefined, make a new atom with the given data */
198 *slot = AtomMake(tag, data);
199
200 if (table->used >= table->limit) {
201 xpmHashAtom new = *slot;
202
203 HashTableGrows(table);
204 table->used++;
205 return new;
206 }
207 table->used++;
208 }
209 return *slot;
210 }
211
212 /*
213 * must be called before allocating any atom
214 */
215
216 int xpmHashTableInit(table)
217 xpmHashTable *table;
218 {
219 xpmHashAtom *p;
220 xpmHashAtom *atomTable;
221
222 table->size = INITIAL_HASH_SIZE;
223 table->limit = table->size / 3;
224 table->used = 0;
225 atomTable = (xpmHashAtom *) malloc((size_t)(table->size*sizeof(*atomTable)));
226 if (atomTable)
227 for (p = atomTable + table->size; p > atomTable;)
228 *--p = NULL;
229 table->atomTable = atomTable;
230 return 0;
231 }
232
233 /*
234 * frees a hashtable and all the stored atoms
235 */
236
237 int xpmHashTableFree(table)
238 xpmHashTable *table;
239 {
240 xpmHashAtom *p;
241 xpmHashAtom *atomTable = table->atomTable;
242 for (p = atomTable + table->size; p > atomTable;)
243 if (*--p)
244 free(*p);
245 free(atomTable);
246 table->atomTable = NULL;
247 return 0;
248 }