src/atom.c

   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
  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 *
 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
 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 *
 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
 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         if (!table->index)
 152             return XKB_ATOM_NONE;
 153
 154         memset(table->index, 0, table->index_size * sizeof(*table->index));
 155         for (size_t j = 1; j < darray_size(table->strings); j++) {
 156             const char *s = darray_item(table->strings, j);
 157             uint32_t hash = hash_buf(s, strlen(s));
 158             for (size_t i = 0; i < table->index_size; i++) {
 159                 size_t index_pos = (hash + i) & (table->index_size - 1);
 160                 if (index_pos == 0)
 161                     continue;
 162
 163                 xkb_atom_t atom = table->index[index_pos];
 164                 if (atom == XKB_ATOM_NONE) {
 165                     table->index[index_pos] = j;
 166                     break;
 167                 }
 168             }
 169         }
 170     }
 171
 172     uint32_t hash = hash_buf(string, len);
 173     for (size_t i = 0; i < table->index_size; i++) {
 174         size_t index_pos = (hash + i) & (table->index_size - 1);
 175         if (index_pos == 0)
 176             continue;
 177
 178         xkb_atom_t existing_atom = table->index[index_pos];
 179         if (existing_atom == XKB_ATOM_NONE) {
 180             if (add) {
 181                 xkb_atom_t new_atom = darray_size(table->strings);
 182                 darray_append(table->strings, strndup(string, len));
 183                 table->index[index_pos] = new_atom;
 184                 return new_atom;
 185             } else {
 186                 return XKB_ATOM_NONE;
 187             }
 188         }
 189
 190         const char *existing_value = darray_item(table->strings, existing_atom);
 191         if (strncmp(existing_value, string, len) == 0 && existing_value[len] == '\0')
 192             return existing_atom;
 193     }
 194
 195     assert(!"couldn't find an empty slot during probing");
 196 }