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    const char   *string;
68} NodeRec, *NodePtr;
69
70static Atom lastAtom = None;
71static NodePtr atomRoot = NULL;
72static unsigned long tableLength;
73static NodePtr *nodeTable;
74
75void FreeAtom(NodePtr patom);
76
77Atom
78MakeAtom(const 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 != 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 = malloc(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	    char *newstring = malloc(len + 1);
122	    if (!newstring) {
123		free(nd);
124		return BAD_RESOURCE;
125	    }
126	    strncpy(newstring, string, (int)len);
127	    newstring[len] = 0;
128	    nd->string = newstring;
129	}
130	if ((lastAtom + 1) >= tableLength) {
131	    NodePtr *table;
132
133	    table = realloc(nodeTable, tableLength * (2 * sizeof(NodePtr)));
134	    if (!table) {
135		if (nd->string != string) {
136                    /* nd->string has been strdup'ed */
137		    free((char *)nd->string);
138                }
139		free(nd);
140		return BAD_RESOURCE;
141	    }
142	    tableLength <<= 1;
143	    nodeTable = table;
144	}
145	*np = nd;
146	nd->left = nd->right = NULL;
147	nd->fingerPrint = fp;
148	nd->a = ++lastAtom;
149	nodeTable[lastAtom] = nd;
150	return nd->a;
151    }
152    else
153	return None;
154}
155
156Bool
157ValidAtom(Atom atom)
158{
159    return (atom != None) && (atom <= lastAtom);
160}
161
162const char *
163NameForAtom(Atom atom)
164{
165    NodePtr node;
166    if (atom > lastAtom) return 0;
167    if ((node = nodeTable[atom]) == NULL) return 0;
168    return node->string;
169}
170
171void
172AtomError(void)
173{
174    FatalError("initializing atoms");
175}
176
177void
178FreeAtom(NodePtr patom)
179{
180    if(patom->left)
181	FreeAtom(patom->left);
182    if(patom->right)
183	FreeAtom(patom->right);
184    if (patom->a > XA_LAST_PREDEFINED) {
185        /*
186         * All strings above XA_LAST_PREDEFINED are strdup'ed, so it's safe to
187         * cast here
188         */
189	free((char *)patom->string);
190    }
191    free(patom);
192}
193
194void
195FreeAllAtoms(void)
196{
197    if (atomRoot == NULL)
198	return;
199    FreeAtom(atomRoot);
200    atomRoot = NULL;
201    free(nodeTable);
202    nodeTable = NULL;
203    lastAtom = None;
204}
205
206void
207InitAtoms(void)
208{
209    FreeAllAtoms();
210    tableLength = InitialTableSize;
211    nodeTable = malloc(InitialTableSize * sizeof(NodePtr));
212    if (!nodeTable)
213	AtomError();
214    nodeTable[None] = NULL;
215    MakePredeclaredAtoms();
216    if (lastAtom != XA_LAST_PREDEFINED)
217	AtomError();
218}
219