1 /***********************************************************
2 * Copyright 1987, 1998 The Open Group
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
10 * The above copyright notice and this permission notice shall be included in
11 * all copies or substantial portions of the Software.
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.
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.
25 * Copyright 1987 by Digital Equipment Corporation, Maynard, Massachusetts.
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.
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
45 ******************************************************************/
47 /************************************************************
48 * Copyright 1994 by Silicon Graphics Computer Systems, Inc.
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.
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.
71 ********************************************************/
77 struct atom_node *left, *right;
79 unsigned int fingerprint;
84 struct atom_node *root;
85 darray(struct atom_node *) table;
91 struct atom_table *table;
93 table = calloc(1, sizeof(*table));
97 darray_init(table->table);
98 darray_growalloc(table->table, 100);
99 darray_append(table->table, NULL);
105 free_atom(struct atom_node *patom)
110 free_atom(patom->left);
111 free_atom(patom->right);
117 atom_table_free(struct atom_table *table)
122 free_atom(table->root);
123 darray_free(table->table);
128 atom_text(struct atom_table *table, xkb_atom_t atom)
130 if (atom >= darray_size(table->table) ||
131 darray_item(table->table, atom) == NULL)
134 return darray_item(table->table, atom)->string;
138 atom_strdup(struct atom_table *table, xkb_atom_t atom)
140 return strdup_safe(atom_text(table, atom));
144 find_node_pointer(struct atom_table *table, const char *string,
145 struct atom_node ***np_out, unsigned int *fingerprint_out)
147 struct atom_node **np;
154 len = strlen(string);
156 for (i = 0; i < (len + 1) / 2; i++) {
157 fp = fp * 27 + string[i];
158 fp = fp * 27 + string[len - 1 - i];
162 if (fp < (*np)->fingerprint) {
165 else if (fp > (*np)->fingerprint) {
166 np = &((*np)->right);
169 /* now start testing the strings */
170 comp = strncmp(string, (*np)->string, len);
171 if (comp < 0 || (comp == 0 && len < strlen((*np)->string))) {
175 np = &((*np)->right);
184 *fingerprint_out = fp;
190 atom_lookup(struct atom_table *table, const char *string)
192 struct atom_node **np;
196 return XKB_ATOM_NONE;
198 if (!find_node_pointer(table, string, &np, &fp))
199 return XKB_ATOM_NONE;
205 * If steal is true, we do not strdup @string; therefore it must be
206 * dynamically allocated, not be free'd by the caller and not be used
207 * afterwards. Use to avoid some redundant allocations.
210 atom_intern(struct atom_table *table, const char *string,
213 struct atom_node **np;
214 struct atom_node *nd;
218 return XKB_ATOM_NONE;
220 if (find_node_pointer(table, string, &np, &fp)) {
222 free(UNCONSTIFY(string));
226 nd = malloc(sizeof(*nd));
228 return XKB_ATOM_NONE;
231 nd->string = UNCONSTIFY(string);
234 nd->string = strdup(string);
237 return XKB_ATOM_NONE;
242 nd->left = nd->right = NULL;
243 nd->fingerprint = fp;
244 nd->atom = darray_size(table->table);
245 darray_append(table->table, nd);