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 "config.h"
74
75 #include <assert.h>
76 #include <inttypes.h>
77 #include <stdbool.h>
78 #include <string.h>
79
80 #include "atom.h"
81 #include "darray.h"
82 #include "utils.h"
83
84 /* FNV-1a (http://www.isthe.com/chongo/tech/comp/fnv/). */
85 static inline uint32_t
hash_buf(const char * string,size_t len)86 hash_buf(const char *string, size_t len)
87 {
88 uint32_t hash = 2166136261u;
89 for (size_t i = 0; i < (len + 1) / 2; i++) {
90 hash ^= (uint8_t) string[i];
91 hash *= 0x01000193;
92 hash ^= (uint8_t) string[len - 1 - i];
93 hash *= 0x01000193;
94 }
95 return hash;
96 }
97
98 /*
99 * The atom table is an insert-only linear probing hash table
100 * mapping strings to atoms. Another array maps the atoms to
101 * strings. The atom value is the position in the strings array.
102 */
103 struct atom_table {
104 xkb_atom_t *index;
105 size_t index_size;
106 darray(char *) strings;
107 };
108
109 struct atom_table *
atom_table_new(void)110 atom_table_new(void)
111 {
112 struct atom_table *table = calloc(1, sizeof(*table));
113 if (!table)
114 return NULL;
115
116 darray_init(table->strings);
117 darray_append(table->strings, NULL);
118 table->index_size = 4;
119 table->index = calloc(table->index_size, sizeof(*table->index));
120
121 return table;
122 }
123
124 void
atom_table_free(struct atom_table * table)125 atom_table_free(struct atom_table *table)
126 {
127 if (!table)
128 return;
129
130 char **string;
131 darray_foreach(string, table->strings)
132 free(*string);
133 darray_free(table->strings);
134 free(table->index);
135 free(table);
136 }
137
138 const char *
atom_text(struct atom_table * table,xkb_atom_t atom)139 atom_text(struct atom_table *table, xkb_atom_t atom)
140 {
141 assert(atom < darray_size(table->strings));
142 return darray_item(table->strings, atom);
143 }
144
145 xkb_atom_t
atom_intern(struct atom_table * table,const char * string,size_t len,bool add)146 atom_intern(struct atom_table *table, const char *string, size_t len, bool add)
147 {
148 if (darray_size(table->strings) > 0.80 * table->index_size) {
149 table->index_size *= 2;
150 table->index = realloc(table->index, table->index_size * sizeof(*table->index));
151 memset(table->index, 0, table->index_size * sizeof(*table->index));
152 for (size_t j = 1; j < darray_size(table->strings); j++) {
153 const char *s = darray_item(table->strings, j);
154 uint32_t hash = hash_buf(s, strlen(s));
155 for (size_t i = 0; i < table->index_size; i++) {
156 size_t index_pos = (hash + i) & (table->index_size - 1);
157 if (index_pos == 0)
158 continue;
159
160 xkb_atom_t atom = table->index[index_pos];
161 if (atom == XKB_ATOM_NONE) {
162 table->index[index_pos] = j;
163 break;
164 }
165 }
166 }
167 }
168
169 uint32_t hash = hash_buf(string, len);
170 for (size_t i = 0; i < table->index_size; i++) {
171 size_t index_pos = (hash + i) & (table->index_size - 1);
172 if (index_pos == 0)
173 continue;
174
175 xkb_atom_t existing_atom = table->index[index_pos];
176 if (existing_atom == XKB_ATOM_NONE) {
177 if (add) {
178 xkb_atom_t new_atom = darray_size(table->strings);
179 darray_append(table->strings, strndup(string, len));
180 table->index[index_pos] = new_atom;
181 return new_atom;
182 } else {
183 return XKB_ATOM_NONE;
184 }
185 }
186
187 const char *existing_value = darray_item(table->strings, existing_atom);
188 if (strncmp(existing_value, string, len) == 0 && existing_value[len] == '\0')
189 return existing_atom;
190 }
191
192 assert(!"couldn't find an empty slot during probing");
193 }
194