atom.c revision 41c30155 
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    int ret = TRUE;
122    if (reverseMapSize == 0)
123	reverseMapSize = 1000;
124    else
125	reverseMapSize *= 2;
126    reverseMap = realloc (reverseMap, reverseMapSize * sizeof (AtomListPtr));
127    if (!reverseMap) {
128	fprintf(stderr, "ResizeReverseMap(): Error: Couldn't reallocate"
129		" reverseMap (%ld)\n",
130		reverseMapSize * (unsigned long)sizeof(AtomListPtr));
131	ret = FALSE;
132    }
133    return ret;
134}
135
136static int
137NameEqual (const char *a, const char *b, int l)
138{
139    while (l--)
140	if (*a++ != *b++)
141	    return FALSE;
142    return TRUE;
143}
144
145#ifdef __SUNPRO_C
146#pragma weak MakeAtom
147#endif
148
149weak Atom
150MakeAtom(const char *string, unsigned len, int makeit)
151{
152    AtomListPtr	a;
153    int		hash;
154    int		h = 0;
155    int		r;
156
157    hash = Hash (string, len);
158    if (hashTable)
159    {
160    	h = hash & hashMask;
161	if (hashTable[h])
162	{
163	    if (hashTable[h]->hash == hash && hashTable[h]->len == len &&
164	    	NameEqual (hashTable[h]->name, string, len))
165	    {
166	    	return hashTable[h]->atom;
167	    }
168	    r = (hash % rehash) | 1;
169	    for (;;)
170	    {
171		h += r;
172		if (h >= hashSize)
173		    h -= hashSize;
174		if (!hashTable[h])
175		    break;
176		if (hashTable[h]->hash == hash && hashTable[h]->len == len &&
177		    NameEqual (hashTable[h]->name, string, len))
178		{
179		    return hashTable[h]->atom;
180		}
181	    }
182    	}
183    }
184    if (!makeit)
185	return None;
186    a = malloc (sizeof (AtomListRec) + len + 1);
187    if (a == NULL) {
188	fprintf(stderr, "MakeAtom(): Error: Couldn't allocate AtomListRec"
189		" (%ld)\n", (unsigned long)sizeof (AtomListRec) + len + 1);
190	return None;
191    }
192    a->name = (char *) (a + 1);
193    a->len = len;
194    strncpy (a->name, string, len);
195    a->name[len] = '\0';
196    a->atom = ++lastAtom;
197    a->hash = hash;
198    if (hashUsed >= hashSize / 2)
199    {
200	ResizeHashTable ();
201	h = hash & hashMask;
202	if (hashTable[h])
203	{
204	    r = (hash % rehash) | 1;
205	    do {
206		h += r;
207		if (h >= hashSize)
208		    h -= hashSize;
209	    } while (hashTable[h]);
210	}
211    }
212    hashTable[h] = a;
213    hashUsed++;
214    if (reverseMapSize <= a->atom) {
215	if (!ResizeReverseMap())
216	    return None;
217    }
218    reverseMap[a->atom] = a;
219    return a->atom;
220}
221
222#ifdef __SUNPRO_C
223#pragma weak ValidAtom
224#endif
225
226weak int
227ValidAtom(Atom atom)
228{
229    return (atom != None) && (atom <= lastAtom);
230}
231
232#ifdef __SUNPRO_C
233#pragma weak NameForAtom
234#endif
235
236weak char *
237NameForAtom(Atom atom)
238{
239    if (atom != None && atom <= lastAtom)
240	return reverseMap[atom]->name;
241    return NULL;
242}
243