atom.c revision b020570b 
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    hash = Hash (string, len);
162    if (hashTable)
163    {
164    	h = hash & hashMask;
165	if (hashTable[h])
166	{
167	    if (hashTable[h]->hash == hash && hashTable[h]->len == len &&
168	    	NameEqual (hashTable[h]->name, string, len))
169	    {
170	    	return hashTable[h]->atom;
171	    }
172	    r = (hash % rehash) | 1;
173	    for (;;)
174	    {
175		h += r;
176		if (h >= hashSize)
177		    h -= hashSize;
178		if (!hashTable[h])
179		    break;
180		if (hashTable[h]->hash == hash && hashTable[h]->len == len &&
181		    NameEqual (hashTable[h]->name, string, len))
182		{
183		    return hashTable[h]->atom;
184		}
185	    }
186    	}
187    }
188    if (!makeit)
189	return None;
190    a = malloc (sizeof (AtomListRec) + len + 1);
191    if (a == NULL) {
192	fprintf(stderr, "MakeAtom(): Error: Couldn't allocate AtomListRec"
193		" (%ld)\n", (unsigned long)sizeof (AtomListRec) + len + 1);
194	return None;
195    }
196    a->name = (char *) (a + 1);
197    a->len = len;
198    strncpy (a->name, string, len);
199    a->name[len] = '\0';
200    a->atom = ++lastAtom;
201    a->hash = hash;
202    if (hashUsed >= hashSize / 2)
203    {
204	ResizeHashTable ();
205	h = hash & hashMask;
206	if (hashTable[h])
207	{
208	    r = (hash % rehash) | 1;
209	    do {
210		h += r;
211		if (h >= hashSize)
212		    h -= hashSize;
213	    } while (hashTable[h]);
214	}
215    }
216    hashTable[h] = a;
217    hashUsed++;
218    if (reverseMapSize <= a->atom) {
219	if (!ResizeReverseMap())
220	    return None;
221    }
222    reverseMap[a->atom] = a;
223    return a->atom;
224}
225
226#ifdef __SUNPRO_C
227#pragma weak ValidAtom
228#endif
229
230weak int
231ValidAtom(Atom atom)
232{
233    return (atom != None) && (atom <= lastAtom);
234}
235
236#ifdef __SUNPRO_C
237#pragma weak NameForAtom
238#endif
239
240weak char *
241NameForAtom(Atom atom)
242{
243    if (atom != None && atom <= lastAtom)
244	return reverseMap[atom]->name;
245    return NULL;
246}
247