]> git.saurik.com Git - wxWidgets.git/blob - src/mac/xpm/hashtab.c
set more event object fields for lbox dbl click events
[wxWidgets.git] / src / mac / 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 static xpmHashAtom
42 AtomMake(name, data) /* makes an atom */
43 char *name; /* WARNING: is just pointed to */
44 void *data;
45 {
46 xpmHashAtom object = (xpmHashAtom) XpmMalloc(sizeof(struct _xpmHashAtom));
47
48 if (object) {
49 object->name = name;
50 object->data = data;
51 }
52 return object;
53 }
54
55 /************************\
56 * *
57 * hash table routines *
58 * *
59 \************************/
60
61 /*
62 * Hash function definition:
63 * HASH_FUNCTION: hash function, hash = hashcode, hp = pointer on char,
64 * hash2 = temporary for hashcode.
65 * INITIAL_TABLE_SIZE in slots
66 * HASH_TABLE_GROWS how hash table grows.
67 */
68
69 /* Mock lisp function */
70 #define HASH_FUNCTION hash = (hash << 5) - hash + *hp++;
71 /* #define INITIAL_HASH_SIZE 2017 */
72 #define INITIAL_HASH_SIZE 256 /* should be enough for colors */
73 #define HASH_TABLE_GROWS size = size * 2;
74
75 /* aho-sethi-ullman's HPJ (sizes should be primes)*/
76 #ifdef notdef
77 #define HASH_FUNCTION hash <<= 4; hash += *hp++; \
78 if(hash2 = hash & 0xf0000000) hash ^= (hash2 >> 24) ^ hash2;
79 #define INITIAL_HASH_SIZE 4095 /* should be 2^n - 1 */
80 #define HASH_TABLE_GROWS size = size << 1 + 1;
81 #endif
82
83 /* GNU emacs function */
84 /*
85 #define HASH_FUNCTION hash = (hash << 3) + (hash >> 28) + *hp++;
86 #define INITIAL_HASH_SIZE 2017
87 #define HASH_TABLE_GROWS size = size * 2;
88 */
89
90 /* end of hash functions */
91
92 /*
93 * The hash table is used to store atoms via their NAME:
94 *
95 * NAME --hash--> ATOM |--name--> "foo"
96 * |--data--> any value which has to be stored
97 *
98 */
99
100 /*
101 * xpmHashSlot gives the slot (pointer to xpmHashAtom) of a name
102 * (slot points to NULL if it is not defined)
103 *
104 */
105
106 xpmHashAtom *
107 xpmHashSlot(table, s)
108 xpmHashTable *table;
109 char *s;
110 {
111 xpmHashAtom *atomTable = table->atomTable;
112 unsigned int hash;
113 xpmHashAtom *p;
114 char *hp = s;
115 char *ns;
116
117 hash = 0;
118 while (*hp) { /* computes hash function */
119 HASH_FUNCTION
120 }
121 p = atomTable + hash % table->size;
122 while (*p) {
123 ns = (*p)->name;
124 if (ns[0] == s[0] && strcmp(ns, s) == 0)
125 break;
126 p--;
127 if (p < atomTable)
128 p = atomTable + table->size - 1;
129 }
130 return p;
131 }
132
133 static int
134 HashTableGrows(table)
135 xpmHashTable *table;
136 {
137 xpmHashAtom *atomTable = table->atomTable;
138 int size = table->size;
139 xpmHashAtom *t, *p;
140 int i;
141 int oldSize = size;
142
143 t = atomTable;
144 HASH_TABLE_GROWS
145 table->size = size;
146 table->limit = size / 3;
147 atomTable = (xpmHashAtom *) XpmMalloc(size * sizeof(*atomTable));
148 if (!atomTable)
149 return (XpmNoMemory);
150 table->atomTable = atomTable;
151 for (p = atomTable + size; p > atomTable;)
152 *--p = NULL;
153 for (i = 0, p = t; i < oldSize; i++, p++)
154 if (*p) {
155 xpmHashAtom *ps = xpmHashSlot(table, (*p)->name);
156
157 *ps = *p;
158 }
159 XpmFree(t);
160 return (XpmSuccess);
161 }
162
163 /*
164 * xpmHashIntern(table, name, data)
165 * an xpmHashAtom is created if name doesn't exist, with the given data.
166 */
167
168 int
169 xpmHashIntern(table, tag, data)
170 xpmHashTable *table;
171 char *tag;
172 void *data;
173 {
174 xpmHashAtom *slot;
175
176 if (!*(slot = xpmHashSlot(table, tag))) {
177 /* undefined, make a new atom with the given data */
178 if (!(*slot = AtomMake(tag, data)))
179 return (XpmNoMemory);
180 if (table->used >= table->limit) {
181 int ErrorStatus;
182
183 if ((ErrorStatus = HashTableGrows(table)) != XpmSuccess)
184 return (ErrorStatus);
185 table->used++;
186 return (XpmSuccess);
187 }
188 table->used++;
189 }
190 return (XpmSuccess);
191 }
192
193 /*
194 * must be called before allocating any atom
195 */
196
197 int
198 xpmHashTableInit(table)
199 xpmHashTable *table;
200 {
201 xpmHashAtom *p;
202 xpmHashAtom *atomTable;
203
204 table->size = INITIAL_HASH_SIZE;
205 table->limit = table->size / 3;
206 table->used = 0;
207 atomTable = (xpmHashAtom *) XpmMalloc(table->size * sizeof(*atomTable));
208 if (!atomTable)
209 return (XpmNoMemory);
210 for (p = atomTable + table->size; p > atomTable;)
211 *--p = NULL;
212 table->atomTable = atomTable;
213 return (XpmSuccess);
214 }
215
216 /*
217 * frees a hashtable and all the stored atoms
218 */
219
220 void
221 xpmHashTableFree(table)
222 xpmHashTable *table;
223 {
224 xpmHashAtom *p;
225 xpmHashAtom *atomTable = table->atomTable;
226
227 if (!atomTable)
228 return;
229 for (p = atomTable + table->size; p > atomTable;)
230 if (*--p)
231 XpmFree(*p);
232 XpmFree(atomTable);
233 table->atomTable = NULL;
234 }