1 /***********************************************************
2 * Copyright 1987, 1998 The Open Group
3 *
4 * Permission to use, copy, modify, distribute, and sell this software and its
5 * documentation for any purpose is hereby granted without fee, provided that
6 * the above copyright notice appear in all copies and that both that
7 * copyright notice and this permission notice appear in supporting
8 * documentation.
9 *
10 * The above copyright notice and this permission notice shall be included in
11 * all copies or substantial portions of the Software.
12 *
13 * THE SOFTWARE IS PROVIDED "AS IS", WITHOUT WARRANTY OF ANY KIND, EXPRESS OR
14 * IMPLIED, INCLUDING BUT NOT LIMITED TO THE WARRANTIES OF MERCHANTABILITY,
15 * FITNESS FOR A PARTICULAR PURPOSE AND NONINFRINGEMENT. IN NO EVENT SHALL THE
16 * OPEN GROUP BE LIABLE FOR ANY CLAIM, DAMAGES OR OTHER LIABILITY, WHETHER IN
17 * AN ACTION OF CONTRACT, TORT OR OTHERWISE, ARISING FROM, OUT OF OR IN
18 * CONNECTION WITH THE SOFTWARE OR THE USE OR OTHER DEALINGS IN THE SOFTWARE.
19 *
20 * Except as contained in this notice, the name of The Open Group shall not be
21 * used in advertising or otherwise to promote the sale, use or other dealings
22 * in this Software without prior written authorization from The Open Group.
23 *
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 /************************************************************
48 * Copyright 1994 by Silicon Graphics Computer Systems, Inc.
49 *
50 * Permission to use, copy, modify, and distribute this
51 * software and its documentation for any purpose and without
52 * fee is hereby granted, provided that the above copyright
53 * notice appear in all copies and that both that copyright
54 * notice and this permission notice appear in supporting
55 * documentation, and that the name of Silicon Graphics not be
56 * used in advertising or publicity pertaining to distribution
57 * of the software without specific prior written permission.
58 * Silicon Graphics makes no representation about the suitability
59 * of this software for any purpose. It is provided "as is"
60 * without any express or implied warranty.
61 *
62 * SILICON GRAPHICS DISCLAIMS ALL WARRANTIES WITH REGARD TO THIS
63 * SOFTWARE, INCLUDING ALL IMPLIED WARRANTIES OF MERCHANTABILITY
64 * AND FITNESS FOR A PARTICULAR PURPOSE. IN NO EVENT SHALL SILICON
65 * GRAPHICS BE LIABLE FOR ANY SPECIAL, INDIRECT OR CONSEQUENTIAL
66 * DAMAGES OR ANY DAMAGES WHATSOEVER RESULTING FROM LOSS OF USE,
67 * DATA OR PROFITS, WHETHER IN AN ACTION OF CONTRACT, NEGLIGENCE
68 * OR OTHER TORTIOUS ACTION, ARISING OUT OF OR IN CONNECTION WITH
69 * THE USE OR PERFORMANCE OF THIS SOFTWARE.
70 *
71 ********************************************************/
72
73 #include "utils.h"
74 #include "atom.h"
75
76 struct atom_node {
77 xkb_atom_t left, right;
78 xkb_atom_t atom;
79 unsigned int fingerprint;
80 char *string;
81 };
82
83 struct atom_table {
84 xkb_atom_t root;
85 darray(struct atom_node) table;
86 };
87
88 struct atom_table *
atom_table_new(void)89 atom_table_new(void)
90 {
91 struct atom_table *table;
92
93 table = calloc(1, sizeof(*table));
94 if (!table)
95 return NULL;
96
97 darray_init(table->table);
98 /* The original throw-away root is here, at the illegal atom 0. */
99 darray_resize0(table->table, 1);
100
101 return table;
102 }
103
104 void
atom_table_free(struct atom_table * table)105 atom_table_free(struct atom_table *table)
106 {
107 struct atom_node *node;
108
109 if (!table)
110 return;
111
112 darray_foreach(node, table->table)
113 free(node->string);
114 darray_free(table->table);
115 free(table);
116 }
117
118 const char *
atom_text(struct atom_table * table,xkb_atom_t atom)119 atom_text(struct atom_table *table, xkb_atom_t atom)
120 {
121 if (atom == XKB_ATOM_NONE || atom >= darray_size(table->table))
122 return NULL;
123
124 return darray_item(table->table, atom).string;
125 }
126
127 static bool
find_atom_pointer(struct atom_table * table,const char * string,size_t len,xkb_atom_t ** atomp_out,unsigned int * fingerprint_out)128 find_atom_pointer(struct atom_table *table, const char *string, size_t len,
129 xkb_atom_t **atomp_out, unsigned int *fingerprint_out)
130 {
131 xkb_atom_t *atomp = &table->root;
132 unsigned int fingerprint = 0;
133 bool found = false;
134
135 for (size_t i = 0; i < (len + 1) / 2; i++) {
136 fingerprint = fingerprint * 27 + string[i];
137 fingerprint = fingerprint * 27 + string[len - 1 - i];
138 }
139
140 while (*atomp != XKB_ATOM_NONE) {
141 struct atom_node *node = &darray_item(table->table, *atomp);
142
143 if (fingerprint < node->fingerprint) {
144 atomp = &node->left;
145 }
146 else if (fingerprint > node->fingerprint) {
147 atomp = &node->right;
148 }
149 else {
150 /* Now start testing the strings. */
151 const int cmp = strncmp(string, node->string, len);
152 if (cmp < 0 || (cmp == 0 && len < strlen(node->string))) {
153 atomp = &node->left;
154 }
155 else if (cmp > 0) {
156 atomp = &node->right;
157 }
158 else {
159 found = true;
160 break;
161 }
162 }
163 }
164
165 if (fingerprint_out)
166 *fingerprint_out = fingerprint;
167 if (atomp_out)
168 *atomp_out = atomp;
169 return found;
170 }
171
172 xkb_atom_t
atom_lookup(struct atom_table * table,const char * string,size_t len)173 atom_lookup(struct atom_table *table, const char *string, size_t len)
174 {
175 xkb_atom_t *atomp;
176
177 if (!string)
178 return XKB_ATOM_NONE;
179
180 if (!find_atom_pointer(table, string, len, &atomp, NULL))
181 return XKB_ATOM_NONE;
182
183 return *atomp;
184 }
185
186 /*
187 * If steal is true, we do not strdup @string; therefore it must be
188 * dynamically allocated, NUL-terminated, not be free'd by the caller
189 * and not be used afterwards. Use to avoid some redundant allocations.
190 */
191 xkb_atom_t
atom_intern(struct atom_table * table,const char * string,size_t len,bool steal)192 atom_intern(struct atom_table *table, const char *string, size_t len,
193 bool steal)
194 {
195 xkb_atom_t *atomp;
196 struct atom_node node;
197 unsigned int fingerprint;
198
199 if (!string)
200 return XKB_ATOM_NONE;
201
202 if (find_atom_pointer(table, string, len, &atomp, &fingerprint)) {
203 if (steal)
204 free(UNCONSTIFY(string));
205 return *atomp;
206 }
207
208 if (steal) {
209 node.string = UNCONSTIFY(string);
210 }
211 else {
212 node.string = strndup(string, len);
213 if (!node.string)
214 return XKB_ATOM_NONE;
215 }
216
217 node.left = node.right = XKB_ATOM_NONE;
218 node.fingerprint = fingerprint;
219 node.atom = darray_size(table->table);
220 /* Do this before the append, as it may realloc and change the offsets. */
221 *atomp = node.atom;
222 darray_append(table->table, node);
223
224 return node.atom;
225 }
226