/***********************************************************
|
* Copyright 1987, 1998 The Open Group
|
*
|
* Permission to use, copy, modify, distribute, and sell this software and its
|
* documentation for any purpose is hereby granted without fee, provided that
|
* the above copyright notice appear in all copies and that both that
|
* copyright notice and this permission notice appear in supporting
|
* documentation.
|
*
|
* The above copyright notice and this permission notice shall be included in
|
* all copies or substantial portions of the Software.
|
*
|
* THE SOFTWARE IS PROVIDED "AS IS", WITHOUT WARRANTY OF ANY KIND, EXPRESS OR
|
* IMPLIED, INCLUDING BUT NOT LIMITED TO THE WARRANTIES OF MERCHANTABILITY,
|
* FITNESS FOR A PARTICULAR PURPOSE AND NONINFRINGEMENT. IN NO EVENT SHALL THE
|
* OPEN GROUP BE LIABLE FOR ANY CLAIM, DAMAGES OR OTHER LIABILITY, WHETHER IN
|
* AN ACTION OF CONTRACT, TORT OR OTHERWISE, ARISING FROM, OUT OF OR IN
|
* CONNECTION WITH THE SOFTWARE OR THE USE OR OTHER DEALINGS IN THE SOFTWARE.
|
*
|
* Except as contained in this notice, the name of The Open Group shall not be
|
* used in advertising or otherwise to promote the sale, use or other dealings
|
* in this Software without prior written authorization from The Open Group.
|
*
|
*
|
* Copyright 1987 by Digital Equipment Corporation, Maynard, Massachusetts.
|
*
|
* All Rights Reserved
|
*
|
* Permission to use, copy, modify, and distribute this software and its
|
* documentation for any purpose and without fee is hereby granted,
|
* provided that the above copyright notice appear in all copies and that
|
* both that copyright notice and this permission notice appear in
|
* supporting documentation, and that the name of Digital not be
|
* used in advertising or publicity pertaining to distribution of the
|
* software without specific, written prior permission.
|
*
|
* DIGITAL DISCLAIMS ALL WARRANTIES WITH REGARD TO THIS SOFTWARE, INCLUDING
|
* ALL IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS, IN NO EVENT SHALL
|
* DIGITAL BE LIABLE FOR ANY SPECIAL, INDIRECT OR CONSEQUENTIAL DAMAGES OR
|
* ANY DAMAGES WHATSOEVER RESULTING FROM LOSS OF USE, DATA OR PROFITS,
|
* WHETHER IN AN ACTION OF CONTRACT, NEGLIGENCE OR OTHER TORTIOUS ACTION,
|
* ARISING OUT OF OR IN CONNECTION WITH THE USE OR PERFORMANCE OF THIS
|
* SOFTWARE.
|
*
|
******************************************************************/
|
|
/************************************************************
|
* Copyright 1994 by Silicon Graphics Computer Systems, Inc.
|
*
|
* Permission to use, copy, modify, and distribute this
|
* software and its documentation for any purpose and without
|
* fee is hereby granted, provided that the above copyright
|
* notice appear in all copies and that both that copyright
|
* notice and this permission notice appear in supporting
|
* documentation, and that the name of Silicon Graphics not be
|
* used in advertising or publicity pertaining to distribution
|
* of the software without specific prior written permission.
|
* Silicon Graphics makes no representation about the suitability
|
* of this software for any purpose. It is provided "as is"
|
* without any express or implied warranty.
|
*
|
* SILICON GRAPHICS DISCLAIMS ALL WARRANTIES WITH REGARD TO THIS
|
* SOFTWARE, INCLUDING ALL IMPLIED WARRANTIES OF MERCHANTABILITY
|
* AND FITNESS FOR A PARTICULAR PURPOSE. IN NO EVENT SHALL SILICON
|
* GRAPHICS BE LIABLE FOR ANY SPECIAL, INDIRECT OR CONSEQUENTIAL
|
* DAMAGES OR ANY DAMAGES WHATSOEVER RESULTING FROM LOSS OF USE,
|
* DATA OR PROFITS, WHETHER IN AN ACTION OF CONTRACT, NEGLIGENCE
|
* OR OTHER TORTIOUS ACTION, ARISING OUT OF OR IN CONNECTION WITH
|
* THE USE OR PERFORMANCE OF THIS SOFTWARE.
|
*
|
********************************************************/
|
|
#include "utils.h"
|
#include "atom.h"
|
|
struct atom_node {
|
xkb_atom_t left, right;
|
xkb_atom_t atom;
|
unsigned int fingerprint;
|
char *string;
|
};
|
|
struct atom_table {
|
xkb_atom_t root;
|
darray(struct atom_node) table;
|
};
|
|
struct atom_table *
|
atom_table_new(void)
|
{
|
struct atom_table *table;
|
|
table = calloc(1, sizeof(*table));
|
if (!table)
|
return NULL;
|
|
darray_init(table->table);
|
/* The original throw-away root is here, at the illegal atom 0. */
|
darray_resize0(table->table, 1);
|
|
return table;
|
}
|
|
void
|
atom_table_free(struct atom_table *table)
|
{
|
struct atom_node *node;
|
|
if (!table)
|
return;
|
|
darray_foreach(node, table->table)
|
free(node->string);
|
darray_free(table->table);
|
free(table);
|
}
|
|
const char *
|
atom_text(struct atom_table *table, xkb_atom_t atom)
|
{
|
if (atom == XKB_ATOM_NONE || atom >= darray_size(table->table))
|
return NULL;
|
|
return darray_item(table->table, atom).string;
|
}
|
|
static bool
|
find_atom_pointer(struct atom_table *table, const char *string, size_t len,
|
xkb_atom_t **atomp_out, unsigned int *fingerprint_out)
|
{
|
xkb_atom_t *atomp = &table->root;
|
unsigned int fingerprint = 0;
|
bool found = false;
|
|
for (size_t i = 0; i < (len + 1) / 2; i++) {
|
fingerprint = fingerprint * 27 + string[i];
|
fingerprint = fingerprint * 27 + string[len - 1 - i];
|
}
|
|
while (*atomp != XKB_ATOM_NONE) {
|
struct atom_node *node = &darray_item(table->table, *atomp);
|
|
if (fingerprint < node->fingerprint) {
|
atomp = &node->left;
|
}
|
else if (fingerprint > node->fingerprint) {
|
atomp = &node->right;
|
}
|
else {
|
/* Now start testing the strings. */
|
const int cmp = strncmp(string, node->string, len);
|
if (cmp < 0 || (cmp == 0 && len < strlen(node->string))) {
|
atomp = &node->left;
|
}
|
else if (cmp > 0) {
|
atomp = &node->right;
|
}
|
else {
|
found = true;
|
break;
|
}
|
}
|
}
|
|
if (fingerprint_out)
|
*fingerprint_out = fingerprint;
|
if (atomp_out)
|
*atomp_out = atomp;
|
return found;
|
}
|
|
xkb_atom_t
|
atom_lookup(struct atom_table *table, const char *string, size_t len)
|
{
|
xkb_atom_t *atomp;
|
|
if (!string)
|
return XKB_ATOM_NONE;
|
|
if (!find_atom_pointer(table, string, len, &atomp, NULL))
|
return XKB_ATOM_NONE;
|
|
return *atomp;
|
}
|
|
/*
|
* If steal is true, we do not strdup @string; therefore it must be
|
* dynamically allocated, NUL-terminated, not be free'd by the caller
|
* and not be used afterwards. Use to avoid some redundant allocations.
|
*/
|
xkb_atom_t
|
atom_intern(struct atom_table *table, const char *string, size_t len,
|
bool steal)
|
{
|
xkb_atom_t *atomp;
|
struct atom_node node;
|
unsigned int fingerprint;
|
|
if (!string)
|
return XKB_ATOM_NONE;
|
|
if (find_atom_pointer(table, string, len, &atomp, &fingerprint)) {
|
if (steal)
|
free(UNCONSTIFY(string));
|
return *atomp;
|
}
|
|
if (steal) {
|
node.string = UNCONSTIFY(string);
|
}
|
else {
|
node.string = strndup(string, len);
|
if (!node.string)
|
return XKB_ATOM_NONE;
|
}
|
|
node.left = node.right = XKB_ATOM_NONE;
|
node.fingerprint = fingerprint;
|
node.atom = darray_size(table->table);
|
/* Do this before the append, as it may realloc and change the offsets. */
|
*atomp = node.atom;
|
darray_append(table->table, node);
|
|
return node.atom;
|
}
|
