2 * Copyright (C) 1989-95 GROUPE BULL
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:
11 * The above copyright notice and this permission notice shall be included in
12 * all copies or substantial portions of the Software.
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.
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.
26 /*****************************************************************************\
31 * Developed by Arnaud Le Hors *
32 * this originaly comes from Colas Nahaboo as a part of Wool *
34 \*****************************************************************************/
41 LFUNC(AtomMake, xpmHashAtom, (char *name, void *data));
42 LFUNC(HashTableGrows, int, (xpmHashTable * table));
45 AtomMake( /* makes an atom */
46 char *name, /* WARNING: is just pointed to */
49 xpmHashAtom object = (xpmHashAtom) XpmMalloc(sizeof(struct _xpmHashAtom));
58 /************************\
60 * hash table routines *
62 \************************/
65 * Hash function definition:
66 * HASH_FUNCTION: hash function, hash = hashcode, hp = pointer on char,
67 * hash2 = temporary for hashcode.
68 * INITIAL_TABLE_SIZE in slots
69 * HASH_TABLE_GROWS how hash table grows.
72 /* Mock lisp function */
73 #define HASH_FUNCTION hash = (hash << 5) - hash + *hp++;
74 /* #define INITIAL_HASH_SIZE 2017 */
75 #define INITIAL_HASH_SIZE 256 /* should be enough for colors */
76 #define HASH_TABLE_GROWS size = size * 2;
78 /* aho-sethi-ullman's HPJ (sizes should be primes)*/
80 #define HASH_FUNCTION hash <<= 4; hash += *hp++; \
81 if(hash2 = hash & 0xf0000000) hash ^= (hash2 >> 24) ^ hash2;
82 #define INITIAL_HASH_SIZE 4095 /* should be 2^n - 1 */
83 #define HASH_TABLE_GROWS size = size << 1 + 1;
86 /* GNU emacs function */
88 #define HASH_FUNCTION hash = (hash << 3) + (hash >> 28) + *hp++;
89 #define INITIAL_HASH_SIZE 2017
90 #define HASH_TABLE_GROWS size = size * 2;
93 /* end of hash functions */
96 * The hash table is used to store atoms via their NAME:
98 * NAME --hash--> ATOM |--name--> "foo"
99 * |--data--> any value which has to be stored
104 * xpmHashSlot gives the slot (pointer to xpmHashAtom) of a name
105 * (slot points to NULL if it is not defined)
114 xpmHashAtom *atomTable = table->atomTable;
121 while (*hp) { /* computes hash function */
124 p = atomTable + hash % table->size;
127 if (ns[0] == s[0] && strcmp(ns, s) == 0)
131 p = atomTable + table->size - 1;
137 HashTableGrows(xpmHashTable *table)
139 xpmHashAtom *atomTable = table->atomTable;
140 unsigned int size = table->size;
143 unsigned int oldSize = size;
148 table->limit = size / 3;
149 if (size >= UINT_MAX / sizeof(*atomTable))
150 return (XpmNoMemory);
151 atomTable = (xpmHashAtom *) XpmMalloc(size * sizeof(*atomTable));
153 return (XpmNoMemory);
154 table->atomTable = atomTable;
155 for (p = atomTable + size; p > atomTable;)
157 for (i = 0, p = t; i < oldSize; i++, p++)
159 xpmHashAtom *ps = xpmHashSlot(table, (*p)->name);
168 * xpmHashIntern(table, name, data)
169 * an xpmHashAtom is created if name doesn't exist, with the given data.
180 if (!*(slot = xpmHashSlot(table, tag))) {
181 /* undefined, make a new atom with the given data */
182 if (!(*slot = AtomMake(tag, data)))
183 return (XpmNoMemory);
184 if (table->used >= table->limit) {
187 if ((ErrorStatus = HashTableGrows(table)) != XpmSuccess)
188 return (ErrorStatus);
198 * must be called before allocating any atom
202 xpmHashTableInit(xpmHashTable *table)
205 xpmHashAtom *atomTable;
207 table->size = INITIAL_HASH_SIZE;
208 table->limit = table->size / 3;
210 table->atomTable = NULL;
211 if (table->size >= UINT_MAX / sizeof(*atomTable))
212 return (XpmNoMemory);
213 atomTable = (xpmHashAtom *) XpmMalloc(table->size * sizeof(*atomTable));
215 return (XpmNoMemory);
216 for (p = atomTable + table->size; p > atomTable;)
218 table->atomTable = atomTable;
223 * frees a hashtable and all the stored atoms
227 xpmHashTableFree(xpmHashTable *table)
230 xpmHashAtom *atomTable = table->atomTable;
234 for (p = atomTable + table->size; p > atomTable;)
238 table->atomTable = NULL;