From 1c23bae15b2bb019c39af68b1c0cfc5bb40ba2a7 Mon Sep 17 00:00:00 2001 From: John Mark Bell Date: Sun, 25 Jan 2009 14:02:45 +0000 Subject: Selector hash. svn path=/trunk/libcss/; revision=6263 --- src/select/Makefile | 49 +++++++++ src/select/hash.c | 288 ++++++++++++++++++++++++++++++++++++++++++++++++++++ src/select/hash.h | 36 +++++++ src/stylesheet.c | 15 ++- src/stylesheet.h | 4 +- 5 files changed, 388 insertions(+), 4 deletions(-) create mode 100644 src/select/Makefile create mode 100644 src/select/hash.c create mode 100644 src/select/hash.h 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 + */ + +#include +#include + +#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 + */ + +#ifndef css_select_hash_h_ +#define css_select_hash_h_ + +#include + +#include +#include + +/* 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 + diff --git a/src/stylesheet.c b/src/stylesheet.c index ca53170..80f2a1b 100644 --- a/src/stylesheet.c +++ b/src/stylesheet.c @@ -77,11 +77,19 @@ css_error css_stylesheet_create(css_language_level level, 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 @@ css_error css_stylesheet_create(css_language_level level, 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 @@ css_error css_stylesheet_destroy(css_stylesheet *sheet) 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); diff --git a/src/stylesheet.h b/src/stylesheet.h index 6439325..57bca56 100644 --- a/src/stylesheet.h +++ b/src/stylesheet.h @@ -19,6 +19,7 @@ #include #include "parse/parse.h" +#include "select/hash.h" typedef struct css_rule css_rule; typedef struct css_selector css_selector; @@ -137,8 +138,7 @@ typedef struct css_rule_charset { } 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 */ -- cgit v1.2.3