1/*
2
3Copyright 1990, 1994, 1998  The Open Group
4
5Permission to use, copy, modify, distribute, and sell this software and its
6documentation for any purpose is hereby granted without fee, provided that
7the above copyright notice appear in all copies and that both that
8copyright notice and this permission notice appear in supporting
9documentation.
10
11The above copyright notice and this permission notice shall be included in
12all copies or substantial portions of the Software.
13
14THE SOFTWARE IS PROVIDED "AS IS", WITHOUT WARRANTY OF ANY KIND, EXPRESS OR
15IMPLIED, INCLUDING BUT NOT LIMITED TO THE WARRANTIES OF MERCHANTABILITY,
16FITNESS FOR A PARTICULAR PURPOSE AND NONINFRINGEMENT.  IN NO EVENT SHALL THE
17OPEN GROUP BE LIABLE FOR ANY CLAIM, DAMAGES OR OTHER LIABILITY, WHETHER IN
18AN ACTION OF CONTRACT, TORT OR OTHERWISE, ARISING FROM, OUT OF OR IN
19CONNECTION WITH THE SOFTWARE OR THE USE OR OTHER DEALINGS IN THE SOFTWARE.
20
21Except as contained in this notice, the name of The Open Group shall not be
22used in advertising or otherwise to promote the sale, use or other dealings
23in this Software without prior written authorization from The Open Group.
24
25*/
26
27/*
28 * Author:  Keith Packard, MIT X Consortium
29 */
30
31/* lame atom replacement routines for font applications */
32
33#ifdef HAVE_CONFIG_H
34#include <config.h>
35#endif
36#include <X11/fonts/fontmisc.h>
37#include "stubs.h"
38
39typedef struct _AtomList {
40    char		*name;
41    int			len;
42    int			hash;
43    Atom		atom;
44} AtomListRec, *AtomListPtr;
45
46static AtomListPtr  *hashTable;
47
48static int	    hashSize, hashUsed;
49static int	    hashMask;
50static int	    rehash;
51
52static AtomListPtr  *reverseMap;
53static int	    reverseMapSize;
54static Atom	    lastAtom;
55
56static int
57Hash(const char *string, int len)
58{
59    int	h;
60
61    h = 0;
62    while (len--)
63	h = (h << 3) ^ *string++;
64    if (h < 0)
65	return -h;
66    return h;
67}
68
69static int
70ResizeHashTable (void)
71{
72    int		newHashSize;
73    int		newHashMask;
74    AtomListPtr	*newHashTable;
75    int		i;
76    int		h;
77    int		newRehash;
78    int		r;
79
80    if (hashSize == 0)
81	newHashSize = 1024;
82    else
83	newHashSize = hashSize * 2;
84    newHashTable = calloc (newHashSize, sizeof (AtomListPtr));
85    if (!newHashTable) {
86	fprintf(stderr, "ResizeHashTable(): Error: Couldn't allocate"
87		" newHashTable (%ld)\n",
88		newHashSize * (unsigned long)sizeof (AtomListPtr));
89	return FALSE;
90    }
91    newHashMask = newHashSize - 1;
92    newRehash = (newHashMask - 2);
93    for (i = 0; i < hashSize; i++)
94    {
95	if (hashTable[i])
96	{
97	    h = (hashTable[i]->hash) & newHashMask;
98	    if (newHashTable[h])
99	    {
100		r = hashTable[i]->hash % newRehash | 1;
101		do {
102		    h += r;
103		    if (h >= newHashSize)
104			h -= newHashSize;
105		} while (newHashTable[h]);
106	    }
107	    newHashTable[h] = hashTable[i];
108	}
109    }
110    free (hashTable);
111    hashTable = newHashTable;
112    hashSize = newHashSize;
113    hashMask = newHashMask;
114    rehash = newRehash;
115    return TRUE;
116}
117
118static int
119ResizeReverseMap (void)
120{
121    AtomListPtr *newMap;
122    int newMapSize;
123
124    if (reverseMapSize == 0)
125	newMapSize = 1000;
126    else
127	newMapSize = reverseMapSize * 2;
128    newMap = realloc (reverseMap, newMapSize * sizeof (AtomListPtr));
129    if (newMap == NULL) {
130	fprintf(stderr, "ResizeReverseMap(): Error: Couldn't reallocate"
131		" reverseMap (%ld)\n",
132		newMapSize * (unsigned long)sizeof(AtomListPtr));
133	return FALSE;
134    }
135    reverseMap = newMap;
136    reverseMapSize = newMapSize;
137    return TRUE;
138}
139
140static int
141NameEqual (const char *a, const char *b, int l)
142{
143    while (l--)
144	if (*a++ != *b++)
145	    return FALSE;
146    return TRUE;
147}
148
149#ifdef __SUNPRO_C
150#pragma weak MakeAtom
151#endif
152
153weak Atom
154MakeAtom(const char *string, unsigned len, int makeit)
155{
156    AtomListPtr	a;
157    int		hash;
158    int		h = 0;
159    int		r;
160
161    OVERRIDE_SYMBOL(MakeAtom, string, len, makeit);
162
163    hash = Hash (string, len);
164    if (hashTable)
165    {
166    	h = hash & hashMask;
167	if (hashTable[h])
168	{
169	    if (hashTable[h]->hash == hash && hashTable[h]->len == len &&
170	    	NameEqual (hashTable[h]->name, string, len))
171	    {
172	    	return hashTable[h]->atom;
173	    }
174	    r = (hash % rehash) | 1;
175	    for (;;)
176	    {
177		h += r;
178		if (h >= hashSize)
179		    h -= hashSize;
180		if (!hashTable[h])
181		    break;
182		if (hashTable[h]->hash == hash && hashTable[h]->len == len &&
183		    NameEqual (hashTable[h]->name, string, len))
184		{
185		    return hashTable[h]->atom;
186		}
187	    }
188    	}
189    }
190    if (!makeit)
191	return None;
192    a = malloc (sizeof (AtomListRec) + len + 1);
193    if (a == NULL) {
194	fprintf(stderr, "MakeAtom(): Error: Couldn't allocate AtomListRec"
195		" (%ld)\n", (unsigned long)sizeof (AtomListRec) + len + 1);
196	return None;
197    }
198    a->name = (char *) (a + 1);
199    a->len = len;
200    strncpy (a->name, string, len);
201    a->name[len] = '\0';
202    a->atom = ++lastAtom;
203    a->hash = hash;
204    if (hashUsed >= hashSize / 2)
205    {
206	ResizeHashTable ();
207	h = hash & hashMask;
208	if (hashTable[h])
209	{
210	    r = (hash % rehash) | 1;
211	    do {
212		h += r;
213		if (h >= hashSize)
214		    h -= hashSize;
215	    } while (hashTable[h]);
216	}
217    }
218    hashTable[h] = a;
219    hashUsed++;
220    if (reverseMapSize <= a->atom) {
221	if (!ResizeReverseMap())
222	    return None;
223    }
224    reverseMap[a->atom] = a;
225    return a->atom;
226}
227
228#ifdef __SUNPRO_C
229#pragma weak ValidAtom
230#endif
231
232weak int
233ValidAtom(Atom atom)
234{
235    OVERRIDE_SYMBOL(ValidAtom, atom);
236    return (atom != None) && (atom <= lastAtom);
237}
238
239#ifdef __SUNPRO_C
240#pragma weak NameForAtom
241#endif
242
243weak char *
244NameForAtom(Atom atom)
245{
246    OVERRIDE_SYMBOL(NameForAtom, atom);
247    if (atom != None && atom <= lastAtom)
248	return reverseMap[atom]->name;
249    return NULL;
250}
251