X-Git-Url: http://review.tizen.org/git/?a=blobdiff_plain;f=src%2Fatom.c;h=925ca13514a3195100a37def5e8797f1a6d3c898;hb=b5c5c305e3c123948fd43c8b348c08e6aac9055e;hp=2b5b3ed60f3bac4ed9552288b56558d060895724;hpb=8ea4a001d1979c99db28a280489a95906fe43048;p=platform%2Fupstream%2Flibxkbcommon.git diff --git a/src/atom.c b/src/atom.c index 2b5b3ed..925ca13 100644 --- a/src/atom.c +++ b/src/atom.c @@ -70,32 +70,53 @@ * ********************************************************/ -#include "utils.h" +#include "config.h" + +#include +#include +#include +#include + #include "atom.h" +#include "darray.h" +#include "utils.h" -struct atom_node { - xkb_atom_t left, right; - 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 { - xkb_atom_t 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); - /* The original throw-away root is here, at the illegal atom 0. */ - darray_resize0(table->table, 1); + darray_init(table->strings); + darray_append(table->strings, NULL); + table->index_size = 4; + table->index = calloc(table->index_size, sizeof(*table->index)); return table; } @@ -103,109 +124,73 @@ atom_table_new(void) 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); + 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 == XKB_ATOM_NONE || atom >= darray_size(table->table)) - return NULL; - - return darray_item(table->table, atom).string; + assert(atom < darray_size(table->strings)); + return darray_item(table->strings, atom); } -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 +atom_intern(struct atom_table *table, const char *string, size_t len, bool add) { - 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 && node->string[len] != '\0')) { - atomp = &node->left; - } - else if (cmp > 0) { - atomp = &node->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)); + if (!table->index) + return XKB_ATOM_NONE; + + 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; + } } } } - 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; -} - -xkb_atom_t -atom_intern(struct atom_table *table, const char *string, size_t len) -{ - xkb_atom_t *atomp; - struct atom_node node; - unsigned int fingerprint; - - if (!string) - 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; + } + } - if (find_atom_pointer(table, string, len, &atomp, &fingerprint)) { - return *atomp; + const char *existing_value = darray_item(table->strings, existing_atom); + if (strncmp(existing_value, string, len) == 0 && existing_value[len] == '\0') + return existing_atom; } - node.string = strndup(string, len); - if (!node.string) - return XKB_ATOM_NONE; - - node.left = node.right = XKB_ATOM_NONE; - node.fingerprint = fingerprint; - xkb_atom_t atom = darray_size(table->table); - /* Do this before the append, as it may realloc and change the offsets. */ - *atomp = atom; - darray_append(table->table, node); - - return atom; + assert(!"couldn't find an empty slot during probing"); }