Author: jmb
Date: Sun Jan 25 08:02:45 2009
New Revision: 6263
URL: http://source.netsurf-browser.org?rev=6263&view=rev
Log:
Selector hash.
Added:
trunk/libcss/src/select/
trunk/libcss/src/select/Makefile
trunk/libcss/src/select/hash.c
trunk/libcss/src/select/hash.h
Modified:
trunk/libcss/src/stylesheet.c
trunk/libcss/src/stylesheet.h
Added: trunk/libcss/src/select/Makefile
URL:
http://source.netsurf-browser.org/trunk/libcss/src/select/Makefile?rev=6263&view=auto
==============================================================================
--- trunk/libcss/src/select/Makefile (added)
+++ trunk/libcss/src/select/Makefile Sun Jan 25 08:02:45 2009
@@ -1,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))
Added: trunk/libcss/src/select/hash.c
URL:
http://source.netsurf-browser.org/trunk/libcss/src/select/hash.c?rev=6263&view=auto
==============================================================================
--- trunk/libcss/src/select/hash.c (added)
+++ trunk/libcss/src/select/hash.c Sun Jan 25 08:02:45 2009
@@ -1,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 <[email protected]>
+ */
+
+#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;
+}
+
Added: trunk/libcss/src/select/hash.h
URL:
http://source.netsurf-browser.org/trunk/libcss/src/select/hash.h?rev=6263&view=auto
==============================================================================
--- trunk/libcss/src/select/hash.h (added)
+++ trunk/libcss/src/select/hash.h Sun Jan 25 08:02:45 2009
@@ -1,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 <[email protected]>
+ */
+
+#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
+
Modified: trunk/libcss/src/stylesheet.c
URL:
http://source.netsurf-browser.org/trunk/libcss/src/stylesheet.c?rev=6263&r1=6262&r2=6263&view=diff
==============================================================================
--- trunk/libcss/src/stylesheet.c (original)
+++ trunk/libcss/src/stylesheet.c Sun Jan 25 08:02:45 2009
@@ -77,11 +77,19 @@
return error;
}
- /** \todo create selector hash */
+ error = css_selector_hash_create(alloc, alloc_pw, &sheet->selectors);
+ if (error != CSS_OK) {
+ css_language_destroy(sheet->parser_frontend);
+ css_parser_destroy(sheet->parser);
+ parserutils_hash_destroy(sheet->dictionary);
+ alloc(sheet, 0, alloc_pw);
+ return error;
+ }
len = strlen(url) + 1;
sheet->url = alloc(NULL, len, alloc_pw);
if (sheet->url == NULL) {
+ css_selector_hash_destroy(sheet->selectors);
css_language_destroy(sheet->parser_frontend);
css_parser_destroy(sheet->parser);
parserutils_hash_destroy(sheet->dictionary);
@@ -95,6 +103,7 @@
sheet->title = alloc(NULL, len, alloc_pw);
if (sheet->title == NULL) {
alloc(sheet->url, 0, alloc_pw);
+ css_selector_hash_destroy(sheet->selectors);
css_language_destroy(sheet->parser_frontend);
css_parser_destroy(sheet->parser);
parserutils_hash_destroy(sheet->dictionary);
@@ -136,7 +145,9 @@
sheet->alloc(sheet->url, 0, sheet->pw);
- /** \todo destroy selector hash + other data */
+ /** \todo destroy other data */
+
+ css_selector_hash_destroy(sheet->selectors);
css_language_destroy(sheet->parser_frontend);
Modified: trunk/libcss/src/stylesheet.h
URL:
http://source.netsurf-browser.org/trunk/libcss/src/stylesheet.h?rev=6263&r1=6262&r2=6263&view=diff
==============================================================================
--- trunk/libcss/src/stylesheet.h (original)
+++ trunk/libcss/src/stylesheet.h Sun Jan 25 08:02:45 2009
@@ -19,6 +19,7 @@
#include <libcss/types.h>
#include "parse/parse.h"
+#include "select/hash.h"
typedef struct css_rule css_rule;
typedef struct css_selector css_selector;
@@ -137,8 +138,7 @@
} css_rule_charset;
struct css_stylesheet {
-#define HASH_SIZE (37)
- css_selector *selectors[HASH_SIZE]; /**< Hashtable of selectors */
+ css_selector_hash *selectors; /**< Hashtable of selectors */
uint32_t rule_count; /**< Number of rules in sheet */
css_rule *rule_list; /**< List of rules in sheet */
_______________________________________________
netsurf-commits mailing list
[email protected]
http://vlists.pepperfish.net/cgi-bin/mailman/listinfo/netsurf-commits-netsurf-browser.org
