Home | History | Annotate | Download | only in src 
      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     xkb_atom_t left, right;
     78     xkb_atom_t atom;
     79     unsigned int fingerprint;
     80     char *string;
     81 };
     82 
     83 struct atom_table {
     84     xkb_atom_t 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     /* The original throw-away root is here, at the illegal atom 0. */
     99     darray_resize0(table->table, 1);
    100 
    101     return table;
    102 }
    103 
    104 void
    105 atom_table_free(struct atom_table *table)
    106 {
    107     struct atom_node *node;
    108 
    109     if (!table)
    110         return;
    111 
    112     darray_foreach(node, table->table)
    113         free(node->string);
    114     darray_free(table->table);
    115     free(table);
    116 }
    117 
    118 const char *
    119 atom_text(struct atom_table *table, xkb_atom_t atom)
    120 {
    121     if (atom == XKB_ATOM_NONE || atom >= darray_size(table->table))
    122         return NULL;
    123 
    124     return darray_item(table->table, atom).string;
    125 }
    126 
    127 static bool
    128 find_atom_pointer(struct atom_table *table, const char *string, size_t len,
    129                   xkb_atom_t **atomp_out, unsigned int *fingerprint_out)
    130 {
    131     xkb_atom_t *atomp = &table->root;
    132     unsigned int fingerprint = 0;
    133     bool found = false;
    134 
    135     for (size_t i = 0; i < (len + 1) / 2; i++) {
    136         fingerprint = fingerprint * 27 + string[i];
    137         fingerprint = fingerprint * 27 + string[len - 1 - i];
    138     }
    139 
    140     while (*atomp != XKB_ATOM_NONE) {
    141         struct atom_node *node = &darray_item(table->table, *atomp);
    142 
    143         if (fingerprint < node->fingerprint) {
    144             atomp = &node->left;
    145         }
    146         else if (fingerprint > node->fingerprint) {
    147             atomp = &node->right;
    148         }
    149         else {
    150             /* Now start testing the strings. */
    151             const int cmp = strncmp(string, node->string, len);
    152             if (cmp < 0 || (cmp == 0 && len < strlen(node->string))) {
    153                 atomp = &node->left;
    154             }
    155             else if (cmp > 0) {
    156                 atomp = &node->right;
    157             }
    158             else {
    159                 found = true;
    160                 break;
    161             }
    162         }
    163     }
    164 
    165     if (fingerprint_out)
    166         *fingerprint_out = fingerprint;
    167     if (atomp_out)
    168         *atomp_out = atomp;
    169     return found;
    170 }
    171 
    172 xkb_atom_t
    173 atom_lookup(struct atom_table *table, const char *string, size_t len)
    174 {
    175     xkb_atom_t *atomp;
    176 
    177     if (!string)
    178         return XKB_ATOM_NONE;
    179 
    180     if (!find_atom_pointer(table, string, len, &atomp, NULL))
    181         return XKB_ATOM_NONE;
    182 
    183     return *atomp;
    184 }
    185 
    186 /*
    187  * If steal is true, we do not strdup @string; therefore it must be
    188  * dynamically allocated, NUL-terminated, not be free'd by the caller
    189  * and not be used afterwards. Use to avoid some redundant allocations.
    190  */
    191 xkb_atom_t
    192 atom_intern(struct atom_table *table, const char *string, size_t len,
    193             bool steal)
    194 {
    195     xkb_atom_t *atomp;
    196     struct atom_node node;
    197     unsigned int fingerprint;
    198 
    199     if (!string)
    200         return XKB_ATOM_NONE;
    201 
    202     if (find_atom_pointer(table, string, len, &atomp, &fingerprint)) {
    203         if (steal)
    204             free(UNCONSTIFY(string));
    205         return *atomp;
    206     }
    207 
    208     if (steal) {
    209         node.string = UNCONSTIFY(string);
    210     }
    211     else {
    212         node.string = strndup(string, len);
    213         if (!node.string)
    214             return XKB_ATOM_NONE;
    215     }
    216 
    217     node.left = node.right = XKB_ATOM_NONE;
    218     node.fingerprint = fingerprint;
    219     node.atom = darray_size(table->table);
    220     /* Do this before the append, as it may realloc and change the offsets. */
    221     *atomp = node.atom;
    222     darray_append(table->table, node);
    223 
    224     return node.atom;
    225 }
    226