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 "atom.h"
  74
  75 struct atom_node {
  76     struct atom_node *left, *right;
  77     uint32_t a;
  78     unsigned int fingerprint;
  79     char *string;
  80 };
  81
  82 struct atom_table {
  83     struct atom_node *root;
  84     darray(struct atom_node *) table;
  85 };
  86
  87 struct atom_table *
  88 atom_table_new(void)
  89 {
  90     struct atom_table *table;
  91
  92     table = calloc(1, sizeof(*table));
  93     if (!table)
  94         return NULL;
  95
  96     darray_init(table->table);
  97     darray_growalloc(table->table, 100);
  98     darray_append(table->table, NULL);
  99
 100     return table;
 101 }
 102
 103 static void
 104 free_atom(struct atom_node *patom)
 105 {
 106     if (!patom)
 107         return;
 108
 109     free_atom(patom->left);
 110     free_atom(patom->right);
 111     free(patom->string);
 112     free(patom);
 113 }
 114
 115 void
 116 atom_table_free(struct atom_table *table)
 117 {
 118     if (!table)
 119         return;
 120
 121     free_atom(table->root);
 122     darray_free(table->table);
 123     free(table);
 124 }
 125
 126 const char *
 127 atom_text(struct atom_table *table, xkb_atom_t atom)
 128 {
 129     if (atom >= darray_size(table->table) ||
 130         darray_item(table->table, atom) == NULL)
 131         return NULL;
 132
 133     return darray_item(table->table, atom)->string;
 134 }
 135
 136 char *
 137 atom_strdup(struct atom_table *table, xkb_atom_t atom)
 138 {
 139     const char *ret = atom_text(table, atom);
 140     return ret ? strdup(ret) : NULL;
 141 }
 142
 143 xkb_atom_t
 144 atom_intern(struct atom_table *table, const char *string)
 145 {
 146     struct atom_node **np;
 147     struct atom_node *nd;
 148     unsigned i;
 149     int comp;
 150     unsigned int fp = 0;
 151     size_t len;
 152
 153     if (!string)
 154         return XKB_ATOM_NONE;
 155
 156     len = strlen(string);
 157     np = &table->root;
 158     for (i = 0; i < (len + 1) / 2; i++) {
 159         fp = fp * 27 + string[i];
 160         fp = fp * 27 + string[len - 1 - i];
 161     }
 162
 163     while (*np) {
 164         if (fp < (*np)->fingerprint)
 165             np = &((*np)->left);
 166         else if (fp > (*np)->fingerprint)
 167             np = &((*np)->right);
 168         else {
 169             /* now start testing the strings */
 170             comp = strncmp(string, (*np)->string, len);
 171             if ((comp < 0) || ((comp == 0) && (len < strlen((*np)->string))))
 172                 np = &((*np)->left);
 173             else if (comp > 0)
 174                 np = &((*np)->right);
 175             else
 176                 return (*np)->a;
 177         }
 178     }
 179
 180     nd = malloc(sizeof(*nd));
 181     if (!nd)
 182         return XKB_ATOM_NONE;
 183
 184     nd->string = malloc(len + 1);
 185     if (!nd->string) {
 186         free(nd);
 187         return XKB_ATOM_NONE;
 188     }
 189     strncpy(nd->string, string, len);
 190     nd->string[len] = 0;
 191
 192     *np = nd;
 193     nd->left = nd->right = NULL;
 194     nd->fingerprint = fp;
 195     nd->a = darray_size(table->table);
 196     darray_append(table->table, nd);
 197
 198     return nd->a;
 199 }