atom.c revision 05b261ec 
1/***********************************************************
2
3Copyright 1987, 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
26Copyright 1987 by Digital Equipment Corporation, Maynard, Massachusetts.
27
28                        All Rights Reserved
29
30Permission to use, copy, modify, and distribute this software and its
31documentation for any purpose and without fee is hereby granted,
32provided that the above copyright notice appear in all copies and that
33both that copyright notice and this permission notice appear in
34supporting documentation, and that the name of Digital not be
35used in advertising or publicity pertaining to distribution of the
36software without specific, written prior permission.
37
38DIGITAL DISCLAIMS ALL WARRANTIES WITH REGARD TO THIS SOFTWARE, INCLUDING
39ALL IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS, IN NO EVENT SHALL
40DIGITAL BE LIABLE FOR ANY SPECIAL, INDIRECT OR CONSEQUENTIAL DAMAGES OR
41ANY DAMAGES WHATSOEVER RESULTING FROM LOSS OF USE, DATA OR PROFITS,
42WHETHER IN AN ACTION OF CONTRACT, NEGLIGENCE OR OTHER TORTIOUS ACTION,
43ARISING OUT OF OR IN CONNECTION WITH THE USE OR PERFORMANCE OF THIS
44SOFTWARE.
45
46******************************************************************/
47
48
49#ifdef HAVE_DIX_CONFIG_H
50#include <dix-config.h>
51#endif
52
53#include <X11/X.h>
54#include <X11/Xatom.h>
55#include <stdio.h>
56#include <string.h>
57#include "misc.h"
58#include "resource.h"
59#include "dix.h"
60
61#define InitialTableSize 100
62
63typedef struct _Node {
64    struct _Node   *left,   *right;
65    Atom a;
66    unsigned int fingerPrint;
67    char   *string;
68} NodeRec, *NodePtr;
69
70static Atom lastAtom = None;
71static NodePtr atomRoot = (NodePtr)NULL;
72static unsigned long tableLength;
73static NodePtr *nodeTable;
74
75void FreeAtom(NodePtr patom);
76
77_X_EXPORT Atom
78MakeAtom(char *string, unsigned len, Bool makeit)
79{
80    NodePtr * np;
81    unsigned i;
82    int comp;
83    unsigned int fp = 0;
84
85    np = &atomRoot;
86    for (i = 0; i < (len+1)/2; i++)
87    {
88	fp = fp * 27 + string[i];
89	fp = fp * 27 + string[len - 1 - i];
90    }
91    while (*np != (NodePtr) NULL)
92    {
93	if (fp < (*np)->fingerPrint)
94	    np = &((*np)->left);
95	else if (fp > (*np)->fingerPrint)
96	    np = &((*np)->right);
97	else
98	{			       /* now start testing the strings */
99	    comp = strncmp(string, (*np)->string, (int)len);
100	    if ((comp < 0) || ((comp == 0) && (len < strlen((*np)->string))))
101		np = &((*np)->left);
102	    else if (comp > 0)
103		np = &((*np)->right);
104	    else
105		return(*np)->a;
106	    }
107    }
108    if (makeit)
109    {
110	NodePtr nd;
111
112	nd = (NodePtr) xalloc(sizeof(NodeRec));
113	if (!nd)
114	    return BAD_RESOURCE;
115	if (lastAtom < XA_LAST_PREDEFINED)
116	{
117	    nd->string = string;
118	}
119	else
120	{
121	    nd->string = (char *) xalloc(len + 1);
122	    if (!nd->string) {
123		xfree(nd);
124		return BAD_RESOURCE;
125	    }
126	    strncpy(nd->string, string, (int)len);
127	    nd->string[len] = 0;
128	}
129	if ((lastAtom + 1) >= tableLength) {
130	    NodePtr *table;
131
132	    table = (NodePtr *) xrealloc(nodeTable,
133					 tableLength * (2 * sizeof(NodePtr)));
134	    if (!table) {
135		if (nd->string != string)
136		    xfree(nd->string);
137		xfree(nd);
138		return BAD_RESOURCE;
139	    }
140	    tableLength <<= 1;
141	    nodeTable = table;
142	}
143	*np = nd;
144	nd->left = nd->right = (NodePtr) NULL;
145	nd->fingerPrint = fp;
146	nd->a = (++lastAtom);
147	*(nodeTable+lastAtom) = nd;
148	return nd->a;
149    }
150    else
151	return None;
152}
153
154_X_EXPORT Bool
155ValidAtom(Atom atom)
156{
157    return (atom != None) && (atom <= lastAtom);
158}
159
160_X_EXPORT char *
161NameForAtom(Atom atom)
162{
163    NodePtr node;
164    if (atom > lastAtom) return 0;
165    if ((node = nodeTable[atom]) == (NodePtr)NULL) return 0;
166    return node->string;
167}
168
169void
170AtomError(void)
171{
172    FatalError("initializing atoms");
173}
174
175void
176FreeAtom(NodePtr patom)
177{
178    if(patom->left)
179	FreeAtom(patom->left);
180    if(patom->right)
181	FreeAtom(patom->right);
182    if (patom->a > XA_LAST_PREDEFINED)
183	xfree(patom->string);
184    xfree(patom);
185}
186
187void
188FreeAllAtoms(void)
189{
190    if(atomRoot == (NodePtr)NULL)
191	return;
192    FreeAtom(atomRoot);
193    atomRoot = (NodePtr)NULL;
194    xfree(nodeTable);
195    nodeTable = (NodePtr *)NULL;
196    lastAtom = None;
197}
198
199void
200InitAtoms(void)
201{
202    FreeAllAtoms();
203    tableLength = InitialTableSize;
204    nodeTable = (NodePtr *)xalloc(InitialTableSize*sizeof(NodePtr));
205    if (!nodeTable)
206	AtomError();
207    nodeTable[None] = (NodePtr)NULL;
208    MakePredeclaredAtoms();
209    if (lastAtom != XA_LAST_PREDEFINED)
210	AtomError ();
211}
212
213
214