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 ********************************************************/
76 /* FNV-1a (http://www.isthe.com/chongo/tech/comp/fnv/). */
77 static inline uint32_t
78 hash_buf(const char *string, size_t len)
80 uint32_t hash = 2166136261u;
81 for (size_t i = 0; i < (len + 1) / 2; i++) {
82 hash ^= (uint8_t) string[i];
84 hash ^= (uint8_t) string[len - 1 - i];
91 * The atom table is a insert-only unbalanced binary search tree
92 * mapping strings to atoms.
94 * The tree nodes are kept contiguously in the `table` array.
96 * The atom value is the index of the tree node in the array.
98 * As an optimization, strings are not compared by value directly,
100 * instead, they are compared by fingerprint (hash) and the value
101 * is only used to resolve collisions:
102 * (fingerprint(s1), s1) < (fingerprint(s2), s2)
103 * Fingerprint are pre-calculated and saved in the tree nodes.
105 * Why is this not just a hash table? Who knows!
108 xkb_atom_t left, right;
109 uint32_t fingerprint;
115 darray(struct atom_node) table;
121 struct atom_table *table = calloc(1, sizeof(*table));
125 darray_init(table->table);
126 /* The original throw-away root is here, at the illegal atom 0. */
127 darray_resize0(table->table, 1);
133 atom_table_free(struct atom_table *table)
138 struct atom_node *node;
139 darray_foreach(node, table->table)
141 darray_free(table->table);
146 atom_text(struct atom_table *table, xkb_atom_t atom)
148 assert(atom < darray_size(table->table));
149 return darray_item(table->table, atom).string;
153 atom_intern(struct atom_table *table, const char *string, size_t len, bool add)
155 uint32_t fingerprint = hash_buf(string, len);
157 xkb_atom_t *atomp = &table->root;
158 while (*atomp != XKB_ATOM_NONE) {
159 struct atom_node *node = &darray_item(table->table, *atomp);
161 if (fingerprint > node->fingerprint) {
162 atomp = &node->right;
164 else if (fingerprint < node->fingerprint) {
168 /* Now start testing the strings. */
169 const int cmp = strncmp(string, node->string, len);
170 if (likely(cmp == 0 && node->string[len] == '\0')) {
174 atomp = &node->right;
183 return XKB_ATOM_NONE;
185 struct atom_node node;
186 node.string = strndup(string, len);
187 assert(node.string != NULL);
188 node.left = node.right = XKB_ATOM_NONE;
189 node.fingerprint = fingerprint;
190 xkb_atom_t atom = darray_size(table->table);
191 /* Do this before the append, as it may realloc and change the offsets. */
193 darray_append(table->table, node);