summaryrefslogtreecommitdiff
path: root/src/select
diff options
context:
space:
mode:
authorJohn Mark Bell <jmb@netsurf-browser.org>2009-01-25 14:02:45 +0000
committerJohn Mark Bell <jmb@netsurf-browser.org>2009-01-25 14:02:45 +0000
commit1c23bae15b2bb019c39af68b1c0cfc5bb40ba2a7 (patch)
tree0d5426e92b6ea7dbadd2f3558be67ef4595e106d /src/select
parentd0bb179f15f58958bc7d52bb36c1148b2ea79880 (diff)
downloadlibcss-1c23bae15b2bb019c39af68b1c0cfc5bb40ba2a7.tar.gz
libcss-1c23bae15b2bb019c39af68b1c0cfc5bb40ba2a7.tar.bz2
Selector hash.
svn path=/trunk/libcss/; revision=6263
Diffstat (limited to 'src/select')
-rw-r--r--src/select/Makefile49
-rw-r--r--src/select/hash.c288
-rw-r--r--src/select/hash.h36
3 files changed, 373 insertions, 0 deletions
diff --git a/src/select/Makefile b/src/select/Makefile
new file mode 100644
index 0000000..645c97e
--- /dev/null
+++ b/src/select/Makefile
@@ -0,0 +1,49 @@
+# Child makefile fragment
+#
+# Toolchain is provided by top-level makefile
+#
+# Variables provided by top-level makefile
+#
+# COMPONENT The name of the component
+# EXPORT The location of the export directory
+# TOP The location of the source tree root
+# RELEASEDIR The place to put release objects
+# DEBUGDIR The place to put debug objects
+#
+# do_include Canned command sequence to include a child makefile
+#
+# Variables provided by parent makefile:
+#
+# DIR The name of the directory we're in, relative to $(TOP)
+#
+# Variables we can manipulate:
+#
+# ITEMS_CLEAN The list of items to remove for "make clean"
+# ITEMS_DISTCLEAN The list of items to remove for "make distclean"
+# TARGET_TESTS The list of target names to run for "make test"
+#
+# SOURCES The list of sources to build for $(COMPONENT)
+#
+# Plus anything from the toolchain
+
+# Push parent directory onto the directory stack
+sp := $(sp).x
+dirstack_$(sp) := $(d)
+d := $(DIR)
+
+# Manipulate include paths
+CFLAGS := $(CFLAGS) -I$(d)
+
+# Sources
+SRCS_$(d) := hash.c
+
+# Append to sources for component
+SOURCES += $(addprefix $(d), $(SRCS_$(d)))
+
+# Now include any children we may have
+MAKE_INCLUDES := $(wildcard $(d)*/Makefile)
+$(eval $(foreach INC, $(MAKE_INCLUDES), $(call do_include,$(INC))))
+
+# Finally, pop off the directory stack
+d := $(dirstack_$(sp))
+sp := $(basename $(sp))
diff --git a/src/select/hash.c b/src/select/hash.c
new file mode 100644
index 0000000..d37f89e
--- /dev/null
+++ b/src/select/hash.c
@@ -0,0 +1,288 @@
+/*
+ * This file is part of LibCSS
+ * Licensed under the MIT License,
+ * http://www.opensource.org/licenses/mit-license.php
+ * Copyright 2009 John-Mark Bell <jmb@netsurf-browser.org>
+ */
+
+#include <stdio.h>
+#include <string.h>
+
+#include "stylesheet.h"
+#include "select/hash.h"
+
+struct css_selector_hash {
+#define DEFAULT_SLOTS (1<<6)
+ size_t n_slots;
+ size_t n_used;
+
+ const css_selector **slots;
+
+ css_alloc alloc;
+ void *pw;
+};
+
+static inline uint32_t _hash(const css_selector *sel);
+static inline uint32_t _hash_name(const parserutils_hash_entry *name);
+static inline void grow_slots(css_selector_hash *hash);
+
+/**
+ * Create a hash
+ *
+ * \param alloc Memory (de)allocation function
+ * \param pw Pointer to client-specific private data
+ * \param hash Pointer to location to receive result
+ * \return CSS_OK on success, appropriate error otherwise
+ */
+css_error css_selector_hash_create(css_alloc alloc, void *pw,
+ css_selector_hash **hash)
+{
+ css_selector_hash *h;
+
+ if (alloc == NULL || hash == NULL)
+ return CSS_BADPARM;
+
+ h = alloc(0, sizeof(css_selector_hash), pw);
+ if (h == NULL)
+ return CSS_NOMEM;
+
+ h->slots = alloc(0, DEFAULT_SLOTS * sizeof(css_selector *), pw);
+ if (h->slots == NULL) {
+ alloc(h, 0, pw);
+ return CSS_NOMEM;
+ }
+
+ memset(h->slots, 0, DEFAULT_SLOTS * sizeof(css_selector *));
+ h->n_slots = DEFAULT_SLOTS;
+ h->n_used = 0;
+
+ h->alloc = alloc;
+ h->pw = pw;
+
+ *hash = h;
+
+ return CSS_OK;
+}
+
+/**
+ * Destroy a hash
+ *
+ * \param hash The hash to destroy
+ * \return CSS_OK on success, appropriate error otherwise
+ */
+css_error css_selector_hash_destroy(css_selector_hash *hash)
+{
+ if (hash == NULL)
+ return CSS_BADPARM;
+
+ hash->alloc(hash->slots, 0, hash->pw);
+
+ hash->alloc(hash, 0, hash->pw);
+
+ return CSS_OK;
+}
+
+/**
+ * Insert an item into a hash
+ *
+ * \param hash The hash to insert into
+ * \param selector Pointer to selector
+ * \return CSS_OK on success, appropriate error otherwise
+ */
+css_error css_selector_hash_insert(css_selector_hash *hash,
+ const css_selector *selector)
+{
+ uint32_t index, mask;
+ const css_selector **entries;
+ const css_selector *entry;
+
+ if (hash == NULL || selector == NULL)
+ return CSS_BADPARM;
+
+ entries = hash->slots;
+
+ /* Find index */
+ mask = hash->n_slots - 1;
+ index = _hash(selector) & mask;
+
+ /* Use linear probing to resolve collisions */
+ while ((entry = entries[index]) != NULL) {
+ /* If this data is already in the hash, return it */
+ if (selector == entry) {
+ return CSS_OK;
+ }
+
+ index = (index + 1) & mask;
+ }
+
+ /* The data isn't in the hash. Index identifies the slot to use */
+ entries[index] = selector;
+
+ /* If the table is 75% full, then increase its size */
+ if (++hash->n_used >= (hash->n_slots >> 1) + (hash->n_slots >> 2))
+ grow_slots(hash);
+
+ return CSS_OK;
+}
+
+/**
+ * Find the first selector that matches name
+ *
+ * \param hash Hash to search
+ * \param name Name to match
+ * \param matched Location to receive pointer to pointer to matched entry
+ * \return CSS_OK on success, appropriate error otherwise
+ *
+ * If nothing matches, CSS_OK will be returned and **matched == NULL
+ */
+css_error css_selector_hash_find(css_selector_hash *hash,
+ const parserutils_hash_entry *name,
+ const css_selector ***matched)
+{
+ uint32_t index, mask;
+ const css_selector **entries;
+ const css_selector *entry;
+
+ if (hash == NULL || name == NULL || matched == NULL)
+ return CSS_BADPARM;
+
+ entries = hash->slots;
+
+ /* Find index */
+ mask = hash->n_slots - 1;
+ index = _hash_name(name) & mask;
+
+ /* Use linear probing to resolve collisions */
+ while ((entry = entries[index]) != NULL) {
+ /* Names match, so we're done here */
+ if (entry->data.name == name) {
+ break;
+ }
+
+ index = (index + 1) & mask;
+ }
+
+ (*matched) = &entries[index];
+
+ return CSS_OK;
+}
+
+/**
+ * Find the next selector that matches the current search
+ *
+ * \param hash Hash to search
+ * \param current Current selector in search
+ * \param next Location to receive pointer to pointer to next entry
+ * \return CSS_OK on success, appropriate error otherwise
+ *
+ * If nothing further matches, CSS_OK will be returned and **next == NULL
+ */
+
+css_error css_selector_hash_iterate(css_selector_hash *hash,
+ const css_selector **current, const css_selector ***next)
+{
+ uint32_t index, mask;
+ const css_selector **entries;
+ const css_selector *entry;
+
+ if (hash == NULL || current == NULL || next == NULL)
+ return CSS_BADPARM;
+
+ entries = hash->slots;
+
+ /* Find index */
+ mask = hash->n_slots - 1;
+ index = (current - entries + 1) & mask;
+
+ /* Use linear probing to resolve collisions */
+ while ((entry = entries[index]) != NULL) {
+ if (entry->data.name == (*current)->data.name) {
+ break;
+ }
+
+ index = (index + 1) & mask;
+ }
+
+ *next = &entries[index];
+
+ return CSS_OK;
+}
+
+/******************************************************************************
+ * Private functions *
+ ******************************************************************************/
+
+/**
+ * Selector hash function
+ *
+ * \param sel Pointer to selector
+ * \return hash value
+ */
+uint32_t _hash(const css_selector *sel)
+{
+ return (uint32_t) (((uintptr_t) sel->data.name) & 0xffffffff);
+}
+
+/**
+ * Name hash function
+ *
+ * \param name Name to hash
+ * \return hash value
+ */
+uint32_t _hash_name(const parserutils_hash_entry *name)
+{
+ return (uint32_t) (((uintptr_t) name) & 0xffffffff);
+}
+
+/**
+ * Increase the size of the slot table
+ *
+ * \param hash The hash to process
+ */
+void grow_slots(css_selector_hash *hash)
+{
+ const css_selector **s;
+ size_t new_size;
+ size_t n_used = 0;
+
+ if (hash == NULL)
+ return;
+
+ new_size = hash->n_slots << 1;
+
+ /* Create new slot table */
+ s = hash->alloc(0, new_size * sizeof(css_selector *), hash->pw);
+ if (s == NULL)
+ return;
+
+ memset(s, 0, new_size * sizeof(css_selector *));
+
+ /* Now, populate it with the contents of the current one */
+ for (uint32_t i = 0; i < hash->n_slots; i++) {
+ const css_selector *e = hash->slots[i];
+
+ if (e == NULL)
+ continue;
+
+ /* Find new index */
+ uint32_t mask = new_size - 1;
+ uint32_t index = _hash(e) & mask;
+
+ /* Use linear probing to resolve collisions */
+ while (s[index] != NULL)
+ index = (index + 1) & mask;
+
+ /* Insert into new slot table */
+ s[index] = e;
+ n_used++;
+ }
+
+ /* Destroy current table, and replace it with the new one */
+ hash->alloc(hash->slots, 0, hash->pw);
+ hash->slots = s;
+ hash->n_slots = new_size;
+ hash->n_used = n_used;
+
+ return;
+}
+
diff --git a/src/select/hash.h b/src/select/hash.h
new file mode 100644
index 0000000..155ed69
--- /dev/null
+++ b/src/select/hash.h
@@ -0,0 +1,36 @@
+/*
+ * This file is part of LibCSS
+ * Licensed under the MIT License,
+ * http://www.opensource.org/licenses/mit-license.php
+ * Copyright 2009 John-Mark Bell <jmb@netsurf-browser.org>
+ */
+
+#ifndef css_select_hash_h_
+#define css_select_hash_h_
+
+#include <parserutils/utils/hash.h>
+
+#include <libcss/errors.h>
+#include <libcss/functypes.h>
+
+/* Ugh. We need this to avoid circular includes. Happy! */
+struct css_selector;
+
+typedef struct css_selector_hash css_selector_hash;
+
+css_error css_selector_hash_create(css_alloc alloc, void *pw,
+ css_selector_hash **hash);
+css_error css_selector_hash_destroy(css_selector_hash *hash);
+
+css_error css_selector_hash_insert(css_selector_hash *hash,
+ const struct css_selector *selector);
+
+css_error css_selector_hash_find(css_selector_hash *hash,
+ const parserutils_hash_entry *name,
+ const struct css_selector ***matched);
+css_error css_selector_hash_iterate(css_selector_hash *hash,
+ const struct css_selector **current,
+ const struct css_selector ***next);
+
+#endif
+