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 "utils.h"
  74 #include "atom.h"
  75
  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)
  79 {
  80     uint32_t hash = 2166136261u;
  81     for (size_t i = 0; i < (len + 1) / 2; i++) {
  82         hash ^= (uint8_t) string[i];
  83         hash *= 0x01000193;
  84         hash ^= (uint8_t) string[len - 1 - i];
  85         hash *= 0x01000193;
  86     }
  87     return hash;
  88 }
  89
  90 /*
  91  * The atom table is a insert-only unbalanced binary search tree
  92  * mapping strings to atoms.
  93  *
  94  * The tree nodes are kept contiguously in the `table` array.
  95  *
  96  * The atom value is the index of the tree node in the array.
  97  *
  98  * As an optimization, strings are not compared by value directly,
  99  *      s1 < s2
 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.
 104  *
 105  * Why is this not just a hash table? Who knows!
 106  */
 107 struct atom_node {
 108     xkb_atom_t left, right;
 109     uint32_t fingerprint;
 110     char *string;
 111 };
 112
 113 struct atom_table {
 114     xkb_atom_t root;
 115     darray(struct atom_node) table;
 116 };
 117
 118 struct atom_table *
 119 atom_table_new(void)
 120 {
 121     struct atom_table *table = calloc(1, sizeof(*table));
 122     if (!table)
 123         return NULL;
 124
 125     darray_init(table->table);
 126     /* The original throw-away root is here, at the illegal atom 0. */
 127     darray_resize0(table->table, 1);
 128
 129     return table;
 130 }
 131
 132 void
 133 atom_table_free(struct atom_table *table)
 134 {
 135     if (!table)
 136         return;
 137
 138     struct atom_node *node;
 139     darray_foreach(node, table->table)
 140         free(node->string);
 141     darray_free(table->table);
 142     free(table);
 143 }
 144
 145 const char *
 146 atom_text(struct atom_table *table, xkb_atom_t atom)
 147 {
 148     assert(atom < darray_size(table->table));
 149     return darray_item(table->table, atom).string;
 150 }
 151
 152 static bool
 153 find_atom_pointer(struct atom_table *table, const char *string, size_t len,
 154                   xkb_atom_t **atomp_out, uint32_t *fingerprint_out)
 155 {
 156     uint32_t fingerprint = hash_buf(string, len);
 157
 158     xkb_atom_t *atomp = &table->root;
 159     while (*atomp != XKB_ATOM_NONE) {
 160         struct atom_node *node = &darray_item(table->table, *atomp);
 161
 162         if (fingerprint < node->fingerprint) {
 163             atomp = &node->left;
 164         }
 165         else if (fingerprint > node->fingerprint) {
 166             atomp = &node->right;
 167         }
 168         else {
 169             /* Now start testing the strings. */
 170             const int cmp = strncmp(string, node->string, len);
 171             if (cmp == 0 && node->string[len] == '\0') {
 172                 break;
 173             }
 174             else if (cmp < 0) {
 175                 atomp = &node->left;
 176             }
 177             else {
 178                 atomp = &node->right;
 179             }
 180         }
 181     }
 182
 183     if (fingerprint_out)
 184         *fingerprint_out = fingerprint;
 185     if (atomp_out)
 186         *atomp_out = atomp;
 187     return *atomp != XKB_ATOM_NONE;
 188 }
 189
 190 xkb_atom_t
 191 atom_lookup(struct atom_table *table, const char *string, size_t len)
 192 {
 193     xkb_atom_t *atomp;
 194     if (!find_atom_pointer(table, string, len, &atomp, NULL))
 195         return XKB_ATOM_NONE;
 196
 197     return *atomp;
 198 }
 199
 200 xkb_atom_t
 201 atom_intern(struct atom_table *table, const char *string, size_t len)
 202 {
 203     xkb_atom_t *atomp;
 204     uint32_t fingerprint;
 205     if (find_atom_pointer(table, string, len, &atomp, &fingerprint))
 206         return *atomp;
 207
 208     struct atom_node node;
 209     node.string = strndup(string, len);
 210     assert(node.string != NULL);
 211     node.left = node.right = XKB_ATOM_NONE;
 212     node.fingerprint = fingerprint;
 213     xkb_atom_t atom = darray_size(table->table);
 214     /* Do this before the append, as it may realloc and change the offsets. */
 215     *atomp = atom;
 216     darray_append(table->table, node);
 217
 218     return atom;
 219 }