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 struct atom_node {
  77     struct atom_node *left, *right;
  78     xkb_atom_t atom;
  79     unsigned int fingerprint;
  80     char *string;
  81 };
  82
  83 struct atom_table {
  84     struct atom_node *root;
  85     darray(struct atom_node *) table;
  86 };
  87
  88 struct atom_table *
  89 atom_table_new(void)
  90 {
  91     struct atom_table *table;
  92
  93     table = calloc(1, sizeof(*table));
  94     if (!table)
  95         return NULL;
  96
  97     darray_init(table->table);
  98     darray_growalloc(table->table, 100);
  99     darray_append(table->table, NULL);
 100
 101     return table;
 102 }
 103
 104 static void
 105 free_atom(struct atom_node *patom)
 106 {
 107     if (!patom)
 108         return;
 109
 110     free_atom(patom->left);
 111     free_atom(patom->right);
 112     free(patom->string);
 113     free(patom);
 114 }
 115
 116 void
 117 atom_table_free(struct atom_table *table)
 118 {
 119     if (!table)
 120         return;
 121
 122     free_atom(table->root);
 123     darray_free(table->table);
 124     free(table);
 125 }
 126
 127 const char *
 128 atom_text(struct atom_table *table, xkb_atom_t atom)
 129 {
 130     if (atom >= darray_size(table->table) ||
 131         darray_item(table->table, atom) == NULL)
 132         return NULL;
 133
 134     return darray_item(table->table, atom)->string;
 135 }
 136
 137 char *
 138 atom_strdup(struct atom_table *table, xkb_atom_t atom)
 139 {
 140     return strdup_safe(atom_text(table, atom));
 141 }
 142
 143 static bool
 144 find_node_pointer(struct atom_table *table, const char *string, size_t len,
 145                   struct atom_node ***nodep_out, unsigned int *fingerprint_out)
 146 {
 147     struct atom_node **nodep;
 148     unsigned int fingerprint = 0;
 149     bool found = false;
 150
 151     nodep = &table->root;
 152     for (size_t i = 0; i < (len + 1) / 2; i++) {
 153         fingerprint = fingerprint * 27 + string[i];
 154         fingerprint = fingerprint * 27 + string[len - 1 - i];
 155     }
 156
 157     while (*nodep) {
 158         if (fingerprint < (*nodep)->fingerprint) {
 159             nodep = &((*nodep)->left);
 160         }
 161         else if (fingerprint > (*nodep)->fingerprint) {
 162             nodep = &((*nodep)->right);
 163         }
 164         else {
 165             /* Now start testing the strings. */
 166             const int cmp = strncmp(string, (*nodep)->string, len);
 167             if (cmp < 0 || (cmp == 0 && len < strlen((*nodep)->string))) {
 168                 nodep = &((*nodep)->left);
 169             }
 170             else if (cmp > 0) {
 171                 nodep = &((*nodep)->right);
 172             }
 173             else {
 174                 found = true;
 175                 break;
 176             }
 177         }
 178     }
 179
 180     *fingerprint_out = fingerprint;
 181     *nodep_out = nodep;
 182     return found;
 183 }
 184
 185 xkb_atom_t
 186 atom_lookup(struct atom_table *table, const char *string, size_t len)
 187 {
 188     struct atom_node **nodep;
 189     unsigned int fingerprint;
 190
 191     if (!string)
 192         return XKB_ATOM_NONE;
 193
 194     if (!find_node_pointer(table, string, len, &nodep, &fingerprint))
 195         return XKB_ATOM_NONE;
 196
 197     return (*nodep)->atom;
 198 }
 199
 200 /*
 201  * If steal is true, we do not strdup @string; therefore it must be
 202  * dynamically allocated, NUL-terminated, not be free'd by the caller
 203  * and not be used afterwards. Use to avoid some redundant allocations.
 204  */
 205 xkb_atom_t
 206 atom_intern(struct atom_table *table, const char *string, size_t len,
 207             bool steal)
 208 {
 209     struct atom_node **nodep;
 210     struct atom_node *node;
 211     unsigned int fingerprint;
 212
 213     if (!string)
 214         return XKB_ATOM_NONE;
 215
 216     if (find_node_pointer(table, string, len, &nodep, &fingerprint)) {
 217         if (steal)
 218             free(UNCONSTIFY(string));
 219         return (*nodep)->atom;
 220     }
 221
 222     node = malloc(sizeof(*node));
 223     if (!node)
 224         return XKB_ATOM_NONE;
 225
 226     if (steal) {
 227         node->string = UNCONSTIFY(string);
 228     }
 229     else {
 230         node->string = strdup(string);
 231         if (!node->string) {
 232             free(node);
 233             return XKB_ATOM_NONE;
 234         }
 235     }
 236
 237     *nodep = node;
 238     node->left = node->right = NULL;
 239     node->fingerprint = fingerprint;
 240     node->atom = darray_size(table->table);
 241     darray_append(table->table, node);
 242
 243     return node->atom;
 244 }