atom.c revision 23a0898a 
1/* $Xorg: atom.c,v 1.5 2001/02/09 02:04:04 xorgcvs Exp $ */
2
3/*
4
5Copyright 1990, 1994, 1998  The Open Group
6
7Permission to use, copy, modify, distribute, and sell this software and its
8documentation for any purpose is hereby granted without fee, provided that
9the above copyright notice appear in all copies and that both that
10copyright notice and this permission notice appear in supporting
11documentation.
12
13The above copyright notice and this permission notice shall be included in
14all copies or substantial portions of the Software.
15
16THE SOFTWARE IS PROVIDED "AS IS", WITHOUT WARRANTY OF ANY KIND, EXPRESS OR
17IMPLIED, INCLUDING BUT NOT LIMITED TO THE WARRANTIES OF MERCHANTABILITY,
18FITNESS FOR A PARTICULAR PURPOSE AND NONINFRINGEMENT.  IN NO EVENT SHALL THE
19OPEN GROUP BE LIABLE FOR ANY CLAIM, DAMAGES OR OTHER LIABILITY, WHETHER IN
20AN ACTION OF CONTRACT, TORT OR OTHERWISE, ARISING FROM, OUT OF OR IN
21CONNECTION WITH THE SOFTWARE OR THE USE OR OTHER DEALINGS IN THE SOFTWARE.
22
23Except as contained in this notice, the name of The Open Group shall not be
24used in advertising or otherwise to promote the sale, use or other dealings
25in this Software without prior written authorization from The Open Group.
26
27*/
28/* $XFree86: xc/lib/font/util/atom.c,v 1.9 2002/09/19 13:22:00 tsi Exp $ */
29
30/*
31 * Author:  Keith Packard, MIT X Consortium
32 */
33
34/* lame atom replacement routines for font applications */
35
36#ifdef HAVE_CONFIG_H
37#include <config.h>
38#endif
39#include <X11/fonts/fontmisc.h>
40#include "stubs.h"
41
42typedef struct _AtomList {
43    char		*name;
44    int			len;
45    int			hash;
46    Atom		atom;
47} AtomListRec, *AtomListPtr;
48
49static AtomListPtr  *hashTable;
50
51static int	    hashSize, hashUsed;
52static int	    hashMask;
53static int	    rehash;
54
55static AtomListPtr  *reverseMap;
56static int	    reverseMapSize;
57static Atom	    lastAtom;
58
59static int
60Hash(char *string, int len)
61{
62    int	h;
63
64    h = 0;
65    while (len--)
66	h = (h << 3) ^ *string++;
67    if (h < 0)
68	return -h;
69    return h;
70}
71
72static int
73ResizeHashTable (void)
74{
75    int		newHashSize;
76    int		newHashMask;
77    AtomListPtr	*newHashTable;
78    int		i;
79    int		h;
80    int		newRehash;
81    int		r;
82
83    if (hashSize == 0)
84	newHashSize = 1024;
85    else
86	newHashSize = hashSize * 2;
87    newHashTable = (AtomListPtr *) xalloc (newHashSize * sizeof (AtomListPtr));
88    if (!newHashTable) {
89	fprintf(stderr, "ResizeHashTable(): Error: Couldn't allocate"
90		" newHashTable (%ld)\n",
91		newHashSize * (unsigned long)sizeof (AtomListPtr));
92	return FALSE;
93    }
94    bzero ((char *) newHashTable, newHashSize * sizeof (AtomListPtr));
95    newHashMask = newHashSize - 1;
96    newRehash = (newHashMask - 2);
97    for (i = 0; i < hashSize; i++)
98    {
99	if (hashTable[i])
100	{
101	    h = (hashTable[i]->hash) & newHashMask;
102	    if (newHashTable[h])
103	    {
104		r = hashTable[i]->hash % newRehash | 1;
105		do {
106		    h += r;
107		    if (h >= newHashSize)
108			h -= newHashSize;
109		} while (newHashTable[h]);
110	    }
111	    newHashTable[h] = hashTable[i];
112	}
113    }
114    xfree (hashTable);
115    hashTable = newHashTable;
116    hashSize = newHashSize;
117    hashMask = newHashMask;
118    rehash = newRehash;
119    return TRUE;
120}
121
122static int
123ResizeReverseMap (void)
124{
125    int ret = TRUE;
126    if (reverseMapSize == 0)
127	reverseMapSize = 1000;
128    else
129	reverseMapSize *= 2;
130    reverseMap = (AtomListPtr *) xrealloc (reverseMap, reverseMapSize * sizeof (AtomListPtr));
131    if (!reverseMap) {
132	fprintf(stderr, "ResizeReverseMap(): Error: Couldn't reallocate"
133		" reverseMap (%ld)\n",
134		reverseMapSize * (unsigned long)sizeof(AtomListPtr));
135	ret = FALSE;
136    }
137    return ret;
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(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 = (AtomListPtr) xalloc (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