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 Copyright 1994 by Silicon Graphics Computer Systems, Inc.
50
51 Permission to use, copy, modify, and distribute this
52 software and its documentation for any purpose and without
53 fee is hereby granted, provided that the above copyright
54 notice appear in all copies and that both that copyright
55 notice and this permission notice appear in supporting
56 documentation, and that the name of Silicon Graphics not be
57 used in advertising or publicity pertaining to distribution
58 of the software without specific prior written permission.
59 Silicon Graphics makes no representation about the suitability
60 of this software for any purpose. It is provided "as is"
61 without any express or implied warranty.
62
63 SILICON GRAPHICS DISCLAIMS ALL WARRANTIES WITH REGARD TO THIS
64 SOFTWARE, INCLUDING ALL IMPLIED WARRANTIES OF MERCHANTABILITY
65 AND FITNESS FOR A PARTICULAR PURPOSE. IN NO EVENT SHALL SILICON
66 GRAPHICS BE LIABLE FOR ANY SPECIAL, INDIRECT OR CONSEQUENTIAL
67 DAMAGES OR ANY DAMAGES WHATSOEVER RESULTING FROM LOSS OF USE,
68 DATA OR PROFITS, WHETHER IN AN ACTION OF CONTRACT, NEGLIGENCE
69 OR OTHER TORTIOUS ACTION, ARISING OUT OF OR IN CONNECTION  WITH
70 THE USE OR PERFORMANCE OF THIS SOFTWARE.
71
72 ********************************************************/
73
74#ifdef HAVE_CONFIG_H
75#include <config.h>
76#endif
77#include <stdio.h>
78#include <ctype.h>
79#include <stdlib.h>
80#include <X11/Xos.h>
81#include <X11/Xlib.h>
82#include <X11/XKBlib.h>
83
84#include "XKMformat.h"
85#include "XKBfileInt.h"
86
87/***====================================================================***/
88
89#define InitialTableSize 100
90
91typedef struct _Node {
92    struct _Node *left, *right;
93    Atom a;
94    unsigned int fingerPrint;
95    char *string;
96} NodeRec, *NodePtr;
97
98#define BAD_RESOURCE 0xe0000000
99
100static Atom lastAtom = None;
101static NodePtr atomRoot = (NodePtr) NULL;
102static unsigned long tableLength;
103static NodePtr *nodeTable;
104
105static Atom
106_XkbMakeAtom(const char *string, size_t len, Bool makeit)
107{
108    register NodePtr *np;
109    unsigned i;
110    int comp;
111    register unsigned int fp = 0;
112
113    np = &atomRoot;
114    for (i = 0; i < (len + 1) / 2; i++) {
115        fp = fp * 27 + string[i];
116        fp = fp * 27 + string[len - 1 - i];
117    }
118    while (*np != (NodePtr) NULL) {
119        if (fp < (*np)->fingerPrint)
120            np = &((*np)->left);
121        else if (fp > (*np)->fingerPrint)
122            np = &((*np)->right);
123        else {                  /* now start testing the strings */
124            comp = strncmp(string, (*np)->string, len);
125            if ((comp < 0) || ((comp == 0) && (len < strlen((*np)->string))))
126                np = &((*np)->left);
127            else if (comp > 0)
128                np = &((*np)->right);
129            else
130                return (*np)->a;
131        }
132    }
133    if (makeit) {
134        register NodePtr nd;
135
136        nd = (NodePtr) _XkbAlloc(sizeof(NodeRec));
137        if (!nd)
138            return BAD_RESOURCE;
139#ifdef HAVE_STRNDUP
140        nd->string = strndup(string, len);
141#else
142        nd->string = (char *) _XkbAlloc(len + 1);
143#endif
144        if (!nd->string) {
145            _XkbFree(nd);
146            return BAD_RESOURCE;
147        }
148#ifndef HAVE_STRNDUP
149        strncpy(nd->string, string, len);
150        nd->string[len] = 0;
151#endif
152        if ((lastAtom + 1) >= tableLength) {
153            NodePtr *table;
154
155            table = (NodePtr *) _XkbRealloc(nodeTable,
156                                            tableLength * (2 *
157                                                           sizeof(NodePtr)));
158            if (!table) {
159                if (nd->string != string)
160                    _XkbFree(nd->string);
161                _XkbFree(nd);
162                return BAD_RESOURCE;
163            }
164            tableLength <<= 1;
165            nodeTable = table;
166        }
167        *np = nd;
168        nd->left = nd->right = (NodePtr) NULL;
169        nd->fingerPrint = fp;
170        nd->a = (++lastAtom);
171        *(nodeTable + lastAtom) = nd;
172        return nd->a;
173    }
174    else
175        return None;
176}
177
178static char *
179_XkbNameForAtom(Atom atom)
180{
181    NodePtr node;
182
183    if (atom > lastAtom)
184        return NULL;
185    if ((node = nodeTable[atom]) == (NodePtr) NULL)
186        return NULL;
187    return strdup(node->string);
188}
189
190static void
191_XkbInitAtoms(void)
192{
193    tableLength = InitialTableSize;
194    nodeTable = (NodePtr *) _XkbAlloc(InitialTableSize * sizeof(NodePtr));
195    nodeTable[None] = (NodePtr) NULL;
196}
197
198/***====================================================================***/
199
200char *
201XkbAtomGetString(Display *dpy, Atom atm)
202{
203    if (atm == None)
204        return NULL;
205    if (dpy == NULL)
206        return _XkbNameForAtom(atm);
207    return XGetAtomName(dpy, atm);
208}
209
210/***====================================================================***/
211
212Atom
213XkbInternAtom(Display *dpy, const char *name, Bool onlyIfExists)
214{
215    if (name == NULL)
216        return None;
217    if (dpy == NULL) {
218        return _XkbMakeAtom(name, strlen(name), (!onlyIfExists));
219    }
220    return XInternAtom(dpy, name, onlyIfExists);
221}
222
223/***====================================================================***/
224
225Atom
226XkbChangeAtomDisplay(Display *oldDpy, Display *newDpy, Atom atm)
227{
228    char *tmp;
229
230    if (atm != None) {
231        tmp = XkbAtomGetString(oldDpy, atm);
232        if (tmp != NULL)
233            return XkbInternAtom(newDpy, tmp, False);
234    }
235    return None;
236}
237
238/***====================================================================***/
239
240void
241XkbInitAtoms(Display *dpy)
242{
243    static int been_here = 0;
244
245    if ((dpy == NULL) && (!been_here)) {
246        _XkbInitAtoms();
247        been_here = 1;
248    }
249    return;
250}
251