X-Git-Url: http://review.tizen.org/git/?a=blobdiff_plain;f=src%2Fatom.c;h=d43ac381bbdc54fc7f859593ccd282a096978f72;hb=5b3774ace991a396752ff0a846fdfb5c38424551;hp=dc6e794b240947d71095a6520c5076039f34c94e;hpb=58345f4e9c7bf2a91f6614267bf86639bacbe66d;p=platform%2Fupstream%2Flibxkbcommon.git

diff --git a/src/atom.c b/src/atom.c
index dc6e794..d43ac38 100644
--- a/src/atom.c
+++ b/src/atom.c
@@ -70,169 +70,124 @@
  *
  ********************************************************/
 
-#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);
 }
 
-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 || 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;
+    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");
 }