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 *
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
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 *
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
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
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
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