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