]> git.saurik.com Git - wxWidgets.git/blob - src/xpm/hashtab.c
changed version number
[wxWidgets.git] / src / xpm / hashtab.c
1 /*
2 * Copyright (C) 1989-95 GROUPE BULL
3 *
4 * Permission is hereby granted, free of charge, to any person obtaining a copy
5 * of this software and associated documentation files (the "Software"), to
6 * deal in the Software without restriction, including without limitation the
7 * rights to use, copy, modify, merge, publish, distribute, sublicense, and/or
8 * sell copies of the Software, and to permit persons to whom the Software is
9 * furnished to do so, subject to the following conditions:
10 *
11 * The above copyright notice and this permission notice shall be included in
12 * all copies or substantial portions of the Software.
13 *
14 * THE SOFTWARE IS PROVIDED "AS IS", WITHOUT WARRANTY OF ANY KIND, EXPRESS OR
15 * IMPLIED, INCLUDING BUT NOT LIMITED TO THE WARRANTIES OF MERCHANTABILITY,
16 * FITNESS FOR A PARTICULAR PURPOSE AND NONINFRINGEMENT. IN NO EVENT SHALL
17 * GROUPE BULL BE LIABLE FOR ANY CLAIM, DAMAGES OR OTHER LIABILITY, WHETHER IN
18 * AN ACTION OF CONTRACT, TORT OR OTHERWISE, ARISING FROM, OUT OF OR IN
19 * CONNECTION WITH THE SOFTWARE OR THE USE OR OTHER DEALINGS IN THE SOFTWARE.
20 *
21 * Except as contained in this notice, the name of GROUPE BULL shall not be
22 * used in advertising or otherwise to promote the sale, use or other dealings
23 * in this Software without prior written authorization from GROUPE BULL.
24 */
25
26 /*****************************************************************************\
27 * hashtab.c: *
28 * *
29 * XPM library *
30 * *
31 * Developed by Arnaud Le Hors *
32 * this originaly comes from Colas Nahaboo as a part of Wool *
33 * *
34 \*****************************************************************************/
35
36 #include "XpmI.h"
37
38 LFUNC(AtomMake, xpmHashAtom, (char *name, void *data));
39 LFUNC(HashTableGrows, int, (xpmHashTable * table));
40
41 #ifdef __OS2__
42 /* Visual Age cannot deal with old, non-ansi, code */
43 static xpmHashAtom
44 AtomMake(char* name, void* data) /* makes an atom */
45 #else
46 static xpmHashAtom
47 AtomMake(name, data) /* makes an atom */
48 char *name; /* WARNING: is just pointed to */
49 void *data;
50 #endif
51 {
52 xpmHashAtom object = (xpmHashAtom) XpmMalloc(sizeof(struct _xpmHashAtom));
53
54 if (object) {
55 object->name = name;
56 object->data = data;
57 }
58 return object;
59 }
60
61 /************************\
62 * *
63 * hash table routines *
64 * *
65 \************************/
66
67 /*
68 * Hash function definition:
69 * HASH_FUNCTION: hash function, hash = hashcode, hp = pointer on char,
70 * hash2 = temporary for hashcode.
71 * INITIAL_TABLE_SIZE in slots
72 * HASH_TABLE_GROWS how hash table grows.
73 */
74
75 /* Mock lisp function */
76 #define HASH_FUNCTION hash = (hash << 5) - hash + *hp++;
77 /* #define INITIAL_HASH_SIZE 2017 */
78 #define INITIAL_HASH_SIZE 256 /* should be enough for colors */
79 #define HASH_TABLE_GROWS size = size * 2;
80
81 /* aho-sethi-ullman's HPJ (sizes should be primes)*/
82 #ifdef notdef
83 #define HASH_FUNCTION hash <<= 4; hash += *hp++; \
84 if(hash2 = hash & 0xf0000000) hash ^= (hash2 >> 24) ^ hash2;
85 #define INITIAL_HASH_SIZE 4095 /* should be 2^n - 1 */
86 #define HASH_TABLE_GROWS size = size << 1 + 1;
87 #endif
88
89 /* GNU emacs function */
90 /*
91 #define HASH_FUNCTION hash = (hash << 3) + (hash >> 28) + *hp++;
92 #define INITIAL_HASH_SIZE 2017
93 #define HASH_TABLE_GROWS size = size * 2;
94 */
95
96 /* end of hash functions */
97
98 /*
99 * The hash table is used to store atoms via their NAME:
100 *
101 * NAME --hash--> ATOM |--name--> "foo"
102 * |--data--> any value which has to be stored
103 *
104 */
105
106 /*
107 * xpmHashSlot gives the slot (pointer to xpmHashAtom) of a name
108 * (slot points to NULL if it is not defined)
109 *
110 */
111
112 #ifdef __OS2__
113 /* Visual Age cannot deal with old, non-ansi, code */
114 xpmHashAtom* xpmHashSlot(xpmHashTable* table, char* s)
115 #else
116 xpmHashAtom *
117 xpmHashSlot(table, s)
118 xpmHashTable *table;
119 char *s;
120 #endif
121 {
122 xpmHashAtom *atomTable = table->atomTable;
123 unsigned int hash;
124 xpmHashAtom *p;
125 char *hp = s;
126 char *ns;
127
128 hash = 0;
129 while (*hp) { /* computes hash function */
130 HASH_FUNCTION
131 }
132 p = atomTable + hash % table->size;
133 while (*p) {
134 ns = (*p)->name;
135 if (ns[0] == s[0] && strcmp(ns, s) == 0)
136 break;
137 p--;
138 if (p < atomTable)
139 p = atomTable + table->size - 1;
140 }
141 return p;
142 }
143
144 #ifdef __OS2__
145 /* Visual Age cannot deal with old, non-ansi, code */
146 static int HashTableGrows(xpmHashTable* table)
147 #else
148 static int
149 HashTableGrows(table)
150 xpmHashTable *table;
151 #endif
152 {
153 xpmHashAtom *atomTable = table->atomTable;
154 int size = table->size;
155 xpmHashAtom *t, *p;
156 int i;
157 int oldSize = size;
158
159 t = atomTable;
160 HASH_TABLE_GROWS
161 table->size = size;
162 table->limit = size / 3;
163 atomTable = (xpmHashAtom *) XpmMalloc(size * sizeof(*atomTable));
164 if (!atomTable)
165 return (XpmNoMemory);
166 table->atomTable = atomTable;
167 for (p = atomTable + size; p > atomTable;)
168 *--p = NULL;
169 for (i = 0, p = t; i < oldSize; i++, p++)
170 if (*p) {
171 xpmHashAtom *ps = xpmHashSlot(table, (*p)->name);
172
173 *ps = *p;
174 }
175 XpmFree(t);
176 return (XpmSuccess);
177 }
178
179 /*
180 * xpmHashIntern(table, name, data)
181 * an xpmHashAtom is created if name doesn't exist, with the given data.
182 */
183
184 #ifdef __OS2__
185 /* Visual Age cannot deal with old, non-ansi, code */
186 int xpmHashIntern(xpmHashTable* table, char* tag, void* data)
187 #else
188 int
189 xpmHashIntern(table, tag, data)
190 xpmHashTable *table;
191 char *tag;
192 void *data;
193 #endif
194 {
195 xpmHashAtom *slot;
196
197 if (!*(slot = xpmHashSlot(table, tag))) {
198 /* undefined, make a new atom with the given data */
199 if (!(*slot = AtomMake(tag, data)))
200 return (XpmNoMemory);
201 if (table->used >= table->limit) {
202 int ErrorStatus;
203
204 if ((ErrorStatus = HashTableGrows(table)) != XpmSuccess)
205 return (ErrorStatus);
206 table->used++;
207 return (XpmSuccess);
208 }
209 table->used++;
210 }
211 return (XpmSuccess);
212 }
213
214 /*
215 * must be called before allocating any atom
216 */
217
218 #ifdef __OS2__
219 /* Visual Age cannot deal with old, non-ansi, code */
220 int xpmHashTableInit(xpmHashTable* table)
221 #else
222 int
223 xpmHashTableInit(table)
224 xpmHashTable *table;
225 #endif
226 {
227 xpmHashAtom *p;
228 xpmHashAtom *atomTable;
229
230 table->size = INITIAL_HASH_SIZE;
231 table->limit = table->size / 3;
232 table->used = 0;
233 atomTable = (xpmHashAtom *) XpmMalloc(table->size * sizeof(*atomTable));
234 if (!atomTable)
235 return (XpmNoMemory);
236 for (p = atomTable + table->size; p > atomTable;)
237 *--p = NULL;
238 table->atomTable = atomTable;
239 return (XpmSuccess);
240 }
241
242 /*
243 * frees a hashtable and all the stored atoms
244 */
245
246 #ifdef __OS2__
247 /* Visual Age cannot deal with old, non-ansi, code */
248 void
249 xpmHashTableFree(xpmHashTable* table)
250 #else
251 void
252 xpmHashTableFree(table)
253 xpmHashTable *table;
254 #endif
255 {
256 xpmHashAtom *p;
257 xpmHashAtom *atomTable = table->atomTable;
258
259 if (!atomTable)
260 return;
261 for (p = atomTable + table->size; p > atomTable;)
262 if (*--p)
263 XpmFree(*p);
264 XpmFree(atomTable);
265 table->atomTable = NULL;
266 }