]> git.saurik.com Git - wxWidgets.git/blame - src/xpm/hashtab.c
fixed bug in determining the best listbox size
[wxWidgets.git] / src / xpm / hashtab.c
CommitLineData
cfbe03c9 1/*
e6ed776f 2 * Copyright (C) 1989-95 GROUPE BULL
cfbe03c9
JS
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/*****************************************************************************\
e6ed776f 27* hashtab.c: *
cfbe03c9
JS
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
e6ed776f 36#include "XpmI.h"
cfbe03c9
JS
37
38LFUNC(AtomMake, xpmHashAtom, (char *name, void *data));
39LFUNC(HashTableGrows, int, (xpmHashTable * table));
40
ea258ad3
DW
41#ifdef __OS2__
42/* Visual Age cannot deal with old, non-ansi, code */
43static xpmHashAtom
44AtomMake(char* name, void* data) /* makes an atom */
45#else
cfbe03c9 46static xpmHashAtom
e6ed776f
GRG
47AtomMake(name, data) /* makes an atom */
48 char *name; /* WARNING: is just pointed to */
49 void *data;
ea258ad3 50#endif
cfbe03c9
JS
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
ea258ad3
DW
112#ifdef __OS2__
113/* Visual Age cannot deal with old, non-ansi, code */
114xpmHashAtom* xpmHashSlot(xpmHashTable* table, char* s)
115#else
cfbe03c9 116xpmHashAtom *
e6ed776f
GRG
117xpmHashSlot(table, s)
118 xpmHashTable *table;
119 char *s;
ea258ad3 120#endif
cfbe03c9
JS
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
ea258ad3
DW
144#ifdef __OS2__
145/* Visual Age cannot deal with old, non-ansi, code */
146static int HashTableGrows(xpmHashTable* table)
147#else
cfbe03c9 148static int
e6ed776f
GRG
149HashTableGrows(table)
150 xpmHashTable *table;
ea258ad3 151#endif
cfbe03c9
JS
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
ea258ad3
DW
184#ifdef __OS2__
185/* Visual Age cannot deal with old, non-ansi, code */
186int xpmHashIntern(xpmHashTable* table, char* tag, void* data)
187#else
cfbe03c9 188int
e6ed776f
GRG
189xpmHashIntern(table, tag, data)
190 xpmHashTable *table;
191 char *tag;
192 void *data;
ea258ad3 193#endif
cfbe03c9
JS
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
ea258ad3
DW
218#ifdef __OS2__
219/* Visual Age cannot deal with old, non-ansi, code */
220int xpmHashTableInit(xpmHashTable* table)
221#else
cfbe03c9 222int
e6ed776f
GRG
223xpmHashTableInit(table)
224 xpmHashTable *table;
ea258ad3 225#endif
cfbe03c9
JS
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
ea258ad3
DW
246#ifdef __OS2__
247/* Visual Age cannot deal with old, non-ansi, code */
248void
249xpmHashTableFree(xpmHashTable* table)
250#else
cfbe03c9 251void
e6ed776f
GRG
252xpmHashTableFree(table)
253 xpmHashTable *table;
ea258ad3 254#endif
cfbe03c9
JS
255{
256 xpmHashAtom *p;
257 xpmHashAtom *atomTable = table->atomTable;
258
e6ed776f
GRG
259 if (!atomTable)
260 return;
cfbe03c9
JS
261 for (p = atomTable + table->size; p > atomTable;)
262 if (*--p)
263 XpmFree(*p);
264 XpmFree(atomTable);
265 table->atomTable = NULL;
266}