Keysyms: improve generator (#364)

[platform/upstream/libxkbcommon.git] / src / atom.c

diff --git a/src/atom.c b/src/atom.c
index 1d48d70..d43ac38 100644 (file)
--- a/src/atom.c
+++ b/src/atom.c
@@ -70,130 +70,124 @@
  *
  ********************************************************/
 
+#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;
-    uint32_t a;
-    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;
-}
-
-char *
-atom_strdup(struct atom_table *table, xkb_atom_t atom)
-{
-    const char *ret = atom_text(table, atom);
-    return ret ? strdup(ret) : NULL;
+    assert(atom < darray_size(table->strings));
+    return darray_item(table->strings, atom);
 }
 
 xkb_atom_t
-atom_intern(struct atom_table *table, const char *string)
+atom_intern(struct atom_table *table, const char *string, size_t len, bool add)
 {
-    struct atom_node **np;
-    struct atom_node *nd;
-    unsigned i;
-    int comp;
-    unsigned int fp = 0;
-    size_t len;
-
-    if (!string)
-        return XKB_ATOM_NONE;
-
-    len = strlen(string);
-    np = &table->root;
-    for (i = 0; i < (len + 1) / 2; i++) {
-        fp = fp * 27 + string[i];
-        fp = fp * 27 + string[len - 1 - i];
-    }
-
-    while (*np) {
-        if (fp < (*np)->fingerprint)
-            np = &((*np)->left);
-        else if (fp > (*np)->fingerprint)
-            np = &((*np)->right);
-        else {
-            /* now start testing the strings */
-            comp = strncmp(string, (*np)->string, len);
-            if ((comp < 0) || ((comp == 0) && (len < strlen((*np)->string))))
-                np = &((*np)->left);
-            else if (comp > 0)
-                np = &((*np)->right);
-            else
-                return (*np)->a;
+    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;
+                }
+            }
         }
     }
 
-    nd = malloc(sizeof(*nd));
-    if (!nd)
-        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;
+            }
+        }
 
-    nd->string = malloc(len + 1);
-    if (!nd->string) {
-        free(nd);
-        return XKB_ATOM_NONE;
+        const char *existing_value = darray_item(table->strings, existing_atom);
+        if (strncmp(existing_value, string, len) == 0 && existing_value[len] == '\0')
+            return existing_atom;
     }
-    strncpy(nd->string, string, len);
-    nd->string[len] = 0;
-
-    *np = nd;
-    nd->left = nd->right = NULL;
-    nd->fingerprint = fp;
-    nd->a = darray_size(table->table);
-    darray_append(table->table, nd);
 
-    return nd->a;
+    assert(!"couldn't find an empty slot during probing");
 }