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/hash.c | 288 ++++++++++++++++++++++++++++++++++++++++++++++++++++++ 1 file changed, 288 insertions(+) create mode 100644 src/select/hash.c (limited to 'src/select/hash.c') 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; +} + -- cgit v1.2.3