Edit
kc3-lang/libxkbcommon/src/atom.c
Ran Benita
- src/atom.c
-
/*********************************************************** * 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 { struct atom_node *left, *right; xkb_atom_t atom; unsigned int fingerprint; char *string; }; struct atom_table { struct atom_node *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); darray_growalloc(table->table, 100); darray_append(table->table, NULL); return table; } static void free_atom(struct atom_node *patom) { if (!patom) return; free_atom(patom->left); free_atom(patom->right); free(patom->string); free(patom); } void atom_table_free(struct atom_table *table) { if (!table) return; free_atom(table->root); darray_free(table->table); free(table); } const char * atom_text(struct atom_table *table, xkb_atom_t atom) { if (atom >= darray_size(table->table) || darray_item(table->table, atom) == NULL) return NULL; return darray_item(table->table, atom)->string; } char * atom_strdup(struct atom_table *table, xkb_atom_t atom) { return strdup_safe(atom_text(table, atom)); } static bool find_node_pointer(struct atom_table *table, const char *string, size_t len, struct atom_node ***nodep_out, unsigned int *fingerprint_out) { struct atom_node **nodep; unsigned int fingerprint = 0; bool found = false; nodep = &table->root; for (size_t i = 0; i < (len + 1) / 2; i++) { fingerprint = fingerprint * 27 + string[i]; fingerprint = fingerprint * 27 + string[len - 1 - i]; } while (*nodep) { if (fingerprint < (*nodep)->fingerprint) { nodep = &((*nodep)->left); } else if (fingerprint > (*nodep)->fingerprint) { nodep = &((*nodep)->right); } else { /* Now start testing the strings. */ const int cmp = strncmp(string, (*nodep)->string, len); if (cmp < 0 || (cmp == 0 && len < strlen((*nodep)->string))) { nodep = &((*nodep)->left); } else if (cmp > 0) { nodep = &((*nodep)->right); } else { found = true; break; } } } *fingerprint_out = fingerprint; *nodep_out = nodep; return found; } xkb_atom_t atom_lookup(struct atom_table *table, const char *string, size_t len) { struct atom_node **nodep; unsigned int fingerprint; if (!string) return XKB_ATOM_NONE; if (!find_node_pointer(table, string, len, &nodep, &fingerprint)) return XKB_ATOM_NONE; return (*nodep)->atom; } /* * 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) { struct atom_node **nodep; struct atom_node *node; unsigned int fingerprint; if (!string || len == 0) return XKB_ATOM_NONE; if (find_node_pointer(table, string, len, &nodep, &fingerprint)) { if (steal) free(UNCONSTIFY(string)); return (*nodep)->atom; } node = malloc(sizeof(*node)); if (!node) return XKB_ATOM_NONE; if (steal) { node->string = UNCONSTIFY(string); } else { node->string = strndup(string, len); if (!node->string) { free(node); return XKB_ATOM_NONE; } } *nodep = node; node->left = node->right = NULL; node->fingerprint = fingerprint; node->atom = darray_size(table->table); darray_append(table->table, node); return node->atom; }