Commit | Line | Data |
---|---|---|
a09e091a JB |
1 | /*********************************************************** |
2 | ||
3 | Copyright 1987, 1998 The Open Group | |
4 | ||
5 | Permission to use, copy, modify, distribute, and sell this software and its | |
6 | documentation for any purpose is hereby granted without fee, provided that | |
7 | the above copyright notice appear in all copies and that both that | |
8 | copyright notice and this permission notice appear in supporting | |
9 | documentation. | |
10 | ||
11 | The above copyright notice and this permission notice shall be included in | |
12 | all copies or substantial portions of the Software. | |
13 | ||
14 | THE SOFTWARE IS PROVIDED "AS IS", WITHOUT WARRANTY OF ANY KIND, EXPRESS OR | |
15 | IMPLIED, INCLUDING BUT NOT LIMITED TO THE WARRANTIES OF MERCHANTABILITY, | |
16 | FITNESS FOR A PARTICULAR PURPOSE AND NONINFRINGEMENT. IN NO EVENT SHALL THE | |
17 | OPEN GROUP BE LIABLE FOR ANY CLAIM, DAMAGES OR OTHER LIABILITY, WHETHER IN | |
18 | AN ACTION OF CONTRACT, TORT OR OTHERWISE, ARISING FROM, OUT OF OR IN | |
19 | CONNECTION WITH THE SOFTWARE OR THE USE OR OTHER DEALINGS IN THE SOFTWARE. | |
20 | ||
21 | Except as contained in this notice, the name of The Open Group shall not be | |
22 | used in advertising or otherwise to promote the sale, use or other dealings | |
23 | in this Software without prior written authorization from The Open Group. | |
24 | ||
25 | Copyright 1987 by Digital Equipment Corporation, Maynard, Massachusetts. | |
26 | ||
27 | All Rights Reserved | |
28 | ||
29 | Permission to use, copy, modify, and distribute this software and its | |
30 | documentation for any purpose and without fee is hereby granted, | |
31 | provided that the above copyright notice appear in all copies and that | |
32 | both that copyright notice and this permission notice appear in | |
33 | supporting documentation, and that the name of Digital not be | |
34 | used in advertising or publicity pertaining to distribution of the | |
35 | software without specific, written prior permission. | |
36 | ||
37 | DIGITAL DISCLAIMS ALL WARRANTIES WITH REGARD TO THIS SOFTWARE, INCLUDING | |
38 | ALL IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS, IN NO EVENT SHALL | |
39 | DIGITAL BE LIABLE FOR ANY SPECIAL, INDIRECT OR CONSEQUENTIAL DAMAGES OR | |
40 | ANY DAMAGES WHATSOEVER RESULTING FROM LOSS OF USE, DATA OR PROFITS, | |
41 | WHETHER IN AN ACTION OF CONTRACT, NEGLIGENCE OR OTHER TORTIOUS ACTION, | |
42 | ARISING OUT OF OR IN CONNECTION WITH THE USE OR PERFORMANCE OF THIS | |
43 | SOFTWARE. | |
44 | ||
45 | ******************************************************************/ | |
46 | ||
47 | #ifdef HAVE_DIX_CONFIG_H | |
48 | #include <dix-config.h> | |
49 | #endif | |
50 | ||
51 | #include <X11/X.h> | |
52 | #include <X11/Xatom.h> | |
53 | #include <stdio.h> | |
54 | #include <string.h> | |
55 | #include "misc.h" | |
56 | #include "resource.h" | |
57 | #include "dix.h" | |
58 | ||
59 | #define InitialTableSize 100 | |
60 | ||
61 | typedef struct _Node { | |
62 | struct _Node *left, *right; | |
63 | Atom a; | |
64 | unsigned int fingerPrint; | |
65 | const char *string; | |
66 | } NodeRec, *NodePtr; | |
67 | ||
68 | static Atom lastAtom = None; | |
69 | static NodePtr atomRoot = NULL; | |
70 | static unsigned long tableLength; | |
71 | static NodePtr *nodeTable; | |
72 | ||
73 | void FreeAtom(NodePtr patom); | |
74 | ||
75 | Atom | |
76 | MakeAtom(const char *string, unsigned len, Bool makeit) | |
77 | { | |
78 | NodePtr *np; | |
79 | unsigned i; | |
80 | int comp; | |
81 | unsigned int fp = 0; | |
82 | ||
83 | np = &atomRoot; | |
84 | for (i = 0; i < (len + 1) / 2; i++) { | |
85 | fp = fp * 27 + string[i]; | |
86 | fp = fp * 27 + string[len - 1 - i]; | |
87 | } | |
88 | while (*np != NULL) { | |
89 | if (fp < (*np)->fingerPrint) | |
90 | np = &((*np)->left); | |
91 | else if (fp > (*np)->fingerPrint) | |
92 | np = &((*np)->right); | |
93 | else { /* now start testing the strings */ | |
94 | comp = strncmp(string, (*np)->string, (int) len); | |
95 | if ((comp < 0) || ((comp == 0) && (len < strlen((*np)->string)))) | |
96 | np = &((*np)->left); | |
97 | else if (comp > 0) | |
98 | np = &((*np)->right); | |
99 | else | |
100 | return (*np)->a; | |
101 | } | |
102 | } | |
103 | if (makeit) { | |
104 | NodePtr nd; | |
105 | ||
106 | nd = malloc(sizeof(NodeRec)); | |
107 | if (!nd) | |
108 | return BAD_RESOURCE; | |
109 | if (lastAtom < XA_LAST_PREDEFINED) { | |
110 | nd->string = string; | |
111 | } | |
112 | else { | |
113 | nd->string = strndup(string, len); | |
114 | if (!nd->string) { | |
115 | free(nd); | |
116 | return BAD_RESOURCE; | |
117 | } | |
118 | } | |
119 | if ((lastAtom + 1) >= tableLength) { | |
120 | NodePtr *table; | |
121 | ||
122 | table = realloc(nodeTable, tableLength * (2 * sizeof(NodePtr))); | |
123 | if (!table) { | |
124 | if (nd->string != string) { | |
125 | /* nd->string has been strdup'ed */ | |
126 | free((char *) nd->string); | |
127 | } | |
128 | free(nd); | |
129 | return BAD_RESOURCE; | |
130 | } | |
131 | tableLength <<= 1; | |
132 | nodeTable = table; | |
133 | } | |
134 | *np = nd; | |
135 | nd->left = nd->right = NULL; | |
136 | nd->fingerPrint = fp; | |
137 | nd->a = ++lastAtom; | |
138 | nodeTable[lastAtom] = nd; | |
139 | return nd->a; | |
140 | } | |
141 | else | |
142 | return None; | |
143 | } | |
144 | ||
145 | Bool | |
146 | ValidAtom(Atom atom) | |
147 | { | |
148 | return (atom != None) && (atom <= lastAtom); | |
149 | } | |
150 | ||
151 | const char * | |
152 | NameForAtom(Atom atom) | |
153 | { | |
154 | NodePtr node; | |
155 | ||
156 | if (atom > lastAtom) | |
157 | return 0; | |
158 | if ((node = nodeTable[atom]) == NULL) | |
159 | return 0; | |
160 | return node->string; | |
161 | } | |
162 | ||
163 | void | |
164 | AtomError(void) | |
165 | { | |
166 | FatalError("initializing atoms"); | |
167 | } | |
168 | ||
169 | void | |
170 | FreeAtom(NodePtr patom) | |
171 | { | |
172 | if (patom->left) | |
173 | FreeAtom(patom->left); | |
174 | if (patom->right) | |
175 | FreeAtom(patom->right); | |
176 | if (patom->a > XA_LAST_PREDEFINED) { | |
177 | /* | |
178 | * All strings above XA_LAST_PREDEFINED are strdup'ed, so it's safe to | |
179 | * cast here | |
180 | */ | |
181 | free((char *) patom->string); | |
182 | } | |
183 | free(patom); | |
184 | } | |
185 | ||
186 | void | |
187 | FreeAllAtoms(void) | |
188 | { | |
189 | if (atomRoot == NULL) | |
190 | return; | |
191 | FreeAtom(atomRoot); | |
192 | atomRoot = NULL; | |
193 | free(nodeTable); | |
194 | nodeTable = NULL; | |
195 | lastAtom = None; | |
196 | } | |
197 | ||
198 | void | |
199 | InitAtoms(void) | |
200 | { | |
201 | FreeAllAtoms(); | |
202 | tableLength = InitialTableSize; | |
203 | nodeTable = malloc(InitialTableSize * sizeof(NodePtr)); | |
204 | if (!nodeTable) | |
205 | AtomError(); | |
206 | nodeTable[None] = NULL; | |
207 | MakePredeclaredAtoms(); | |
208 | if (lastAtom != XA_LAST_PREDEFINED) | |
209 | AtomError(); | |
210 | } |