*
********************************************************/
-#include "utils.h"
+#include "config.h"
+
+#include <assert.h>
+#include <inttypes.h>
+#include <stdbool.h>
+#include <string.h>
+
#include "atom.h"
+#include "darray.h"
+#include "utils.h"
-struct atom_node {
- struct atom_node *left, *right;
- xkb_atom_t atom;
- unsigned int fingerprint;
- char *string;
-};
+/* FNV-1a (http://www.isthe.com/chongo/tech/comp/fnv/). */
+static inline uint32_t
+hash_buf(const char *string, size_t len)
+{
+ uint32_t hash = 2166136261u;
+ for (size_t i = 0; i < (len + 1) / 2; i++) {
+ hash ^= (uint8_t) string[i];
+ hash *= 0x01000193;
+ hash ^= (uint8_t) string[len - 1 - i];
+ hash *= 0x01000193;
+ }
+ return hash;
+}
+/*
+ * The atom table is an insert-only linear probing hash table
+ * mapping strings to atoms. Another array maps the atoms to
+ * strings. The atom value is the position in the strings array.
+ */
struct atom_table {
- struct atom_node *root;
- darray(struct atom_node *) table;
+ xkb_atom_t *index;
+ size_t index_size;
+ darray(char *) strings;
};
struct atom_table *
atom_table_new(void)
{
- struct atom_table *table;
-
- table = calloc(1, sizeof(*table));
+ struct atom_table *table = calloc(1, sizeof(*table));
if (!table)
return NULL;
- darray_init(table->table);
- darray_growalloc(table->table, 100);
- darray_append(table->table, NULL);
+ darray_init(table->strings);
+ darray_append(table->strings, NULL);
+ table->index_size = 4;
+ table->index = calloc(table->index_size, sizeof(*table->index));
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);
+ char **string;
+ darray_foreach(string, table->strings)
+ free(*string);
+ darray_free(table->strings);
+ free(table->index);
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;
+ assert(atom < darray_size(table->strings));
+ return darray_item(table->strings, atom);
}
-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)
+xkb_atom_t
+atom_intern(struct atom_table *table, const char *string, size_t len, bool add)
{
- 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;
+ if (darray_size(table->strings) > 0.80 * table->index_size) {
+ table->index_size *= 2;
+ table->index = realloc(table->index, table->index_size * sizeof(*table->index));
+ memset(table->index, 0, table->index_size * sizeof(*table->index));
+ for (size_t j = 1; j < darray_size(table->strings); j++) {
+ const char *s = darray_item(table->strings, j);
+ uint32_t hash = hash_buf(s, strlen(s));
+ for (size_t i = 0; i < table->index_size; i++) {
+ size_t index_pos = (hash + i) & (table->index_size - 1);
+ if (index_pos == 0)
+ continue;
+
+ xkb_atom_t atom = table->index[index_pos];
+ if (atom == XKB_ATOM_NONE) {
+ table->index[index_pos] = j;
+ 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)
- 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 = strdup(string);
- if (!node->string) {
- free(node);
- return XKB_ATOM_NONE;
+ uint32_t hash = hash_buf(string, len);
+ for (size_t i = 0; i < table->index_size; i++) {
+ size_t index_pos = (hash + i) & (table->index_size - 1);
+ if (index_pos == 0)
+ continue;
+
+ xkb_atom_t existing_atom = table->index[index_pos];
+ if (existing_atom == XKB_ATOM_NONE) {
+ if (add) {
+ xkb_atom_t new_atom = darray_size(table->strings);
+ darray_append(table->strings, strndup(string, len));
+ table->index[index_pos] = new_atom;
+ return new_atom;
+ } else {
+ 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);
+ const char *existing_value = darray_item(table->strings, existing_atom);
+ if (strncmp(existing_value, string, len) == 0 && existing_value[len] == '\0')
+ return existing_atom;
+ }
- return node->atom;
+ assert(!"couldn't find an empty slot during probing");
}
projects / platform / upstream / libxkbcommon.git / blobdiff