summaryrefslogtreecommitdiff
diff options
context:
space:
mode:
authorJohn Mark Bell <jmb@netsurf-browser.org>2009-07-29 09:57:04 +0000
committerJohn Mark Bell <jmb@netsurf-browser.org>2009-07-29 09:57:04 +0000
commit551c4e5bc7147f8eee1bb48cdd26bc83a66aa78a (patch)
treeaff3a1bb53332c80aa0b3e973c787baebaf3cc4a
parentfc6b96707730c54fb7ac4040680d79864169b5e0 (diff)
downloadlibcss-551c4e5bc7147f8eee1bb48cdd26bc83a66aa78a.tar.gz
libcss-551c4e5bc7147f8eee1bb48cdd26bc83a66aa78a.tar.bz2
Change selector hash to segregate:
1) element selectors 2) universal selectors with class names 3) universal selectors with ids 4) universal selectors Only bother looking for matching selectors in 2 & 3 if the node being selected for has class names or an id, respectively. In theory, this should speed up style selection somewhat. svn path=/trunk/libcss/; revision=8882
-rw-r--r--include/libcss/select.h5
-rw-r--r--src/select/hash.c738
-rw-r--r--src/select/hash.h19
-rw-r--r--src/select/select.c197
-rw-r--r--test/select-auto.c63
5 files changed, 851 insertions, 171 deletions
diff --git a/include/libcss/select.h b/include/libcss/select.h
index a3d18df..76bdcf5 100644
--- a/include/libcss/select.h
+++ b/include/libcss/select.h
@@ -26,6 +26,11 @@ enum css_pseudo_element {
typedef struct css_select_handler {
css_error (*node_name)(void *pw, void *node,
lwc_context *dict, lwc_string **name);
+ css_error (*node_classes)(void *pw, void *node,
+ lwc_context *dict, lwc_string ***classes,
+ uint32_t *n_classes);
+ css_error (*node_id)(void *pw, void *node,
+ lwc_context *dict, lwc_string **id);
css_error (*named_ancestor_node)(void *pw, void *node,
lwc_string *name, void **ancestor);
diff --git a/src/select/hash.c b/src/select/hash.c
index df6ce4e..de01ca3 100644
--- a/src/select/hash.c
+++ b/src/select/hash.c
@@ -17,11 +17,21 @@ typedef struct hash_entry {
struct hash_entry *next;
} hash_entry;
-struct css_selector_hash {
+typedef struct hash_t {
#define DEFAULT_SLOTS (1<<6)
size_t n_slots;
hash_entry *slots;
+} hash_t;
+
+struct css_selector_hash {
+ hash_t elements;
+
+ hash_t classes;
+
+ hash_t ids;
+
+ hash_entry universal;
lwc_context *ctx;
@@ -33,8 +43,26 @@ struct css_selector_hash {
static hash_entry empty_slot;
-static inline uint32_t _hash(const css_selector *sel);
static inline uint32_t _hash_name(lwc_string *name);
+static inline lwc_string *_class_name(const css_selector *selector);
+static inline lwc_string *_id_name(const css_selector *selector);
+static css_error _insert_into_chain(css_selector_hash *ctx, hash_entry *head,
+ const css_selector *selector);
+static css_error _remove_from_chain(css_selector_hash *ctx, hash_entry *head,
+ const css_selector *selector);
+
+static css_error _iterate_elements(css_selector_hash *hash,
+ const css_selector **current,
+ const css_selector ***next);
+static css_error _iterate_classes(css_selector_hash *hash,
+ const css_selector **current,
+ const css_selector ***next);
+static css_error _iterate_ids(css_selector_hash *hash,
+ const css_selector **current,
+ const css_selector ***next);
+static css_error _iterate_universal(css_selector_hash *hash,
+ const css_selector **current,
+ const css_selector ***next);
/**
* Create a hash
@@ -58,16 +86,42 @@ css_error css_selector_hash_create(lwc_context *dict,
if (h == NULL)
return CSS_NOMEM;
- h->slots = alloc(0, DEFAULT_SLOTS * sizeof(hash_entry), pw);
- if (h->slots == NULL) {
+ /* Element hash */
+ h->elements.slots = alloc(0, DEFAULT_SLOTS * sizeof(hash_entry), pw);
+ if (h->elements.slots == NULL) {
+ alloc(h, 0, pw);
+ return CSS_NOMEM;
+ }
+ memset(h->elements.slots, 0, DEFAULT_SLOTS * sizeof(hash_entry));
+ h->elements.n_slots = DEFAULT_SLOTS;
+
+ /* Class hash */
+ h->classes.slots = alloc(0, DEFAULT_SLOTS * sizeof(hash_entry), pw);
+ if (h->classes.slots == NULL) {
+ alloc(h->elements.slots, 0, pw);
+ alloc(h, 0, pw);
+ return CSS_NOMEM;
+ }
+ memset(h->classes.slots, 0, DEFAULT_SLOTS * sizeof(hash_entry));
+ h->classes.n_slots = DEFAULT_SLOTS;
+
+ /* ID hash */
+ h->ids.slots = alloc(0, DEFAULT_SLOTS * sizeof(hash_entry), pw);
+ if (h->ids.slots == NULL) {
+ alloc(h->classes.slots, 0, pw);
+ alloc(h->elements.slots, 0, pw);
alloc(h, 0, pw);
return CSS_NOMEM;
}
+ memset(h->ids.slots, 0, DEFAULT_SLOTS * sizeof(hash_entry));
+ h->ids.n_slots = DEFAULT_SLOTS;
- memset(h->slots, 0, DEFAULT_SLOTS * sizeof(hash_entry));
- h->n_slots = DEFAULT_SLOTS;
+ /* Universal chain */
+ memset(&h->universal, 0, sizeof(hash_entry));
h->hash_size = sizeof(css_selector_hash) +
+ DEFAULT_SLOTS * sizeof(hash_entry) +
+ DEFAULT_SLOTS * sizeof(hash_entry) +
DEFAULT_SLOTS * sizeof(hash_entry);
h->ctx = lwc_context_ref(dict);
@@ -87,24 +141,50 @@ css_error css_selector_hash_create(lwc_context *dict,
*/
css_error css_selector_hash_destroy(css_selector_hash *hash)
{
+ hash_entry *d, *e;
uint32_t i;
if (hash == NULL)
return CSS_BADPARM;
- for (i = 0; i < hash->n_slots; i++) {
- hash_entry *d, *e;
+ /* Element hash */
+ for (i = 0; i < hash->elements.n_slots; i++) {
+ for (d = hash->elements.slots[i].next; d != NULL; d = e) {
+ e = d->next;
+
+ hash->alloc(d, 0, hash->pw);
+ }
+ }
+ hash->alloc(hash->elements.slots, 0, hash->pw);
- for (d = hash->slots[i].next; d != NULL; d = e) {
+ /* Class hash */
+ for (i = 0; i < hash->classes.n_slots; i++) {
+ for (d = hash->classes.slots[i].next; d != NULL; d = e) {
e = d->next;
hash->alloc(d, 0, hash->pw);
}
}
+ hash->alloc(hash->classes.slots, 0, hash->pw);
- lwc_context_unref(hash->ctx);
+ /* ID hash */
+ for (i = 0; i < hash->ids.n_slots; i++) {
+ for (d = hash->ids.slots[i].next; d != NULL; d = e) {
+ e = d->next;
+
+ hash->alloc(d, 0, hash->pw);
+ }
+ }
+ hash->alloc(hash->ids.slots, 0, hash->pw);
- hash->alloc(hash->slots, 0, hash->pw);
+ /* Universal chain */
+ for (d = hash->universal.next; d != NULL; d = e) {
+ e = d->next;
+
+ hash->alloc(d, 0, hash->pw);
+ }
+
+ lwc_context_unref(hash->ctx);
hash->alloc(hash, 0, hash->pw);
@@ -122,57 +202,41 @@ css_error css_selector_hash_insert(css_selector_hash *hash,
const css_selector *selector)
{
uint32_t index, mask;
- hash_entry *head;
+ lwc_string *name;
+ css_error error;
if (hash == NULL || selector == NULL)
return CSS_BADPARM;
- /* Find index */
- mask = hash->n_slots - 1;
- index = _hash(selector) & mask;
-
- head = &hash->slots[index];
-
- if (head->sel == NULL) {
- head->sel = selector;
- head->next = NULL;
+ /* Work out which hash to insert into */
+ if (lwc_string_length(selector->data.name) != 1 ||
+ lwc_string_data(selector->data.name)[0] != '*') {
+ /* Named element */
+ mask = hash->elements.n_slots - 1;
+ index = _hash_name(selector->data.name) & mask;
+
+ error = _insert_into_chain(hash, &hash->elements.slots[index],
+ selector);
+ } else if ((name = _class_name(selector)) != NULL) {
+ /* Named class */
+ mask = hash->classes.n_slots - 1;
+ index = _hash_name(name) & mask;
+
+ error = _insert_into_chain(hash, &hash->classes.slots[index],
+ selector);
+ } else if ((name = _id_name(selector)) != NULL) {
+ /* Named ID */
+ mask = hash->ids.n_slots - 1;
+ index = _hash_name(name) & mask;
+
+ error = _insert_into_chain(hash, &hash->ids.slots[index],
+ selector);
} else {
- hash_entry *prev = NULL;
- hash_entry *entry =
- hash->alloc(NULL, sizeof(hash_entry), hash->pw);
- if (entry == NULL)
- return CSS_NOMEM;
-
- /* Find place to insert entry */
- do {
- /* Sort by ascending specificity */
- if (head->sel->specificity > selector->specificity)
- break;
-
- /* Sort by ascending rule index */
- if (head->sel->specificity == selector->specificity &&
- head->sel->rule->index > selector->rule->index)
- break;
-
- prev = head;
- head = head->next;
- } while (head != NULL);
-
- if (prev == NULL) {
- entry->sel = hash->slots[index].sel;
- entry->next = hash->slots[index].next;
- hash->slots[index].sel = selector;
- hash->slots[index].next = entry;
- } else {
- entry->sel = selector;
- entry->next = prev->next;
- prev->next = entry;
- }
-
- hash->hash_size += sizeof(hash_entry);
+ /* Universal chain */
+ error = _insert_into_chain(hash, &hash->universal, selector);
}
- return CSS_OK;
+ return error;
}
/**
@@ -186,76 +250,70 @@ css_error css_selector_hash_remove(css_selector_hash *hash,
const css_selector *selector)
{
uint32_t index, mask;
- hash_entry *head, *prev = NULL;
+ lwc_string *name;
+ css_error error;
if (hash == NULL || selector == NULL)
return CSS_BADPARM;
- /* Find index */
- mask = hash->n_slots - 1;
- index = _hash(selector) & mask;
-
- head = &hash->slots[index];
-
- if (head->sel == NULL)
- return CSS_INVALID;
-
- do {
- if (head->sel == selector)
- break;
-
- prev = head;
- head = head->next;
- } while (head != NULL);
-
- if (head == NULL)
- return CSS_INVALID;
-
- if (prev == NULL) {
- if (head->next != NULL) {
- hash->slots[index].sel = head->next->sel;
- hash->slots[index].next = head->next->next;
- } else {
- hash->slots[index].sel = NULL;
- hash->slots[index].next = NULL;
- }
+ /* Work out which hash to insert into */
+ if (lwc_string_length(selector->data.name) != 1 ||
+ lwc_string_data(selector->data.name)[0] != '*') {
+ /* Named element */
+ mask = hash->elements.n_slots - 1;
+ index = _hash_name(selector->data.name) & mask;
+
+ error = _remove_from_chain(hash, &hash->elements.slots[index],
+ selector);
+ } else if ((name = _class_name(selector)) != NULL) {
+ /* Named class */
+ mask = hash->classes.n_slots - 1;
+ index = _hash_name(name) & mask;
+
+ error = _remove_from_chain(hash, &hash->classes.slots[index],
+ selector);
+ } else if ((name = _id_name(selector)) != NULL) {
+ /* Named ID */
+ mask = hash->ids.n_slots - 1;
+ index = _hash_name(name) & mask;
+
+ error = _remove_from_chain(hash, &hash->ids.slots[index],
+ selector);
} else {
- prev->next = head->next;
-
- hash->alloc(head, 0, hash->pw);
-
- hash->hash_size -= sizeof(hash_entry);
+ /* Universal chain */
+ error = _remove_from_chain(hash, &hash->universal, selector);
}
- return CSS_OK;
+ return error;
}
-
/**
* 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
+ * \param hash Hash to search
+ * \param name Name to match
+ * \param iterator Pointer to location to receive iterator function
+ * \param matched Pointer to location to receive selector
* \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,
- lwc_string *name,
+ lwc_string *name,
+ css_selector_hash_iterator *iterator,
const css_selector ***matched)
{
uint32_t index, mask;
hash_entry *head;
- if (hash == NULL || name == NULL || matched == NULL)
+ if (hash == NULL || name == NULL || iterator == NULL || matched == NULL)
return CSS_BADPARM;
/* Find index */
- mask = hash->n_slots - 1;
+ mask = hash->elements.n_slots - 1;
index = _hash_name(name) & mask;
- head = &hash->slots[index];
+ head = &hash->elements.slots[index];
if (head->sel != NULL) {
/* Search through chain for first match */
@@ -268,7 +326,6 @@ css_error css_selector_hash_find(css_selector_hash *hash,
if (lerror != lwc_error_ok)
return css_error_from_lwc_error(lerror);
-
if (match)
break;
@@ -279,49 +336,149 @@ css_error css_selector_hash_find(css_selector_hash *hash,
head = &empty_slot;
}
+ (*iterator) = _iterate_elements;
(*matched) = (const css_selector **) head;
return CSS_OK;
}
/**
- * Find the next selector that matches the current search
+ * Find the first selector that has a class that matches name
*
- * \param hash Hash to search
- * \param current Current selector in search
- * \param next Location to receive pointer to pointer to next entry
+ * \param hash Hash to search
+ * \param name Name to match
+ * \param iterator Pointer to location to receive iterator function
+ * \param matched Pointer to location to receive selector
* \return CSS_OK on success, appropriate error otherwise
*
- * If nothing further matches, CSS_OK will be returned and **next == NULL
+ * If nothing matches, CSS_OK will be returned and **matched == NULL
*/
+css_error css_selector_hash_find_by_class(css_selector_hash *hash,
+ lwc_string *name,
+ css_selector_hash_iterator *iterator,
+ const css_selector ***matched)
+{
+ uint32_t index, mask;
+ hash_entry *head;
+
+ if (hash == NULL || name == NULL || iterator == NULL || matched == NULL)
+ return CSS_BADPARM;
+
+ /* Find index */
+ mask = hash->classes.n_slots - 1;
+ index = _hash_name(name) & mask;
+
+ head = &hash->classes.slots[index];
-css_error css_selector_hash_iterate(css_selector_hash *hash,
- const css_selector **current, const css_selector ***next)
+ if (head->sel != NULL) {
+ /* Search through chain for first match */
+ while (head != NULL) {
+ lwc_error lerror;
+ lwc_string *n;
+ bool match = false;
+
+ n = _class_name(head->sel);
+ if (n != NULL) {
+ lerror = lwc_context_string_caseless_isequal(
+ hash->ctx, name, n, &match);
+ if (lerror != lwc_error_ok)
+ return css_error_from_lwc_error(lerror);
+
+ if (match)
+ break;
+ }
+
+ head = head->next;
+ }
+
+ if (head == NULL)
+ head = &empty_slot;
+ }
+
+ (*iterator) = _iterate_classes;
+ (*matched) = (const css_selector **) head;
+
+ return CSS_OK;
+}
+
+/**
+ * Find the first selector that has an ID that matches name
+ *
+ * \param hash Hash to search
+ * \param name Name to match
+ * \param iterator Pointer to location to receive iterator function
+ * \param matched Pointer to location to receive selector
+ * \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_by_id(css_selector_hash *hash,
+ lwc_string *name,
+ css_selector_hash_iterator *iterator,
+ const css_selector ***matched)
{
- hash_entry *head = (hash_entry *) current;
+ uint32_t index, mask;
+ hash_entry *head;
- if (hash == NULL || current == NULL || next == NULL)
+ if (hash == NULL || name == NULL || iterator == NULL || matched == NULL)
return CSS_BADPARM;
- /* Look for the next selector with the same element name */
- for (head = head->next; head != NULL; head = head->next) {
- lwc_error lerror;
- bool match = false;
+ /* Find index */
+ mask = hash->ids.n_slots - 1;
+ index = _hash_name(name) & mask;
- lerror = lwc_context_string_caseless_isequal(hash->ctx,
- head->sel->data.name,
- (*current)->data.name, &match);
- if (lerror != lwc_error_ok)
- return css_error_from_lwc_error(lerror);
+ head = &hash->ids.slots[index];
- if (match)
- break;
+ if (head->sel != NULL) {
+ /* Search through chain for first match */
+ while (head != NULL) {
+ lwc_error lerror;
+ lwc_string *n;
+ bool match = false;
+
+ n = _id_name(head->sel);
+ if (n != NULL) {
+ lerror = lwc_context_string_caseless_isequal(
+ hash->ctx, name, n, &match);
+ if (lerror != lwc_error_ok)
+ return css_error_from_lwc_error(lerror);
+
+ if (match)
+ break;
+ }
+
+ head = head->next;
+ }
+
+ if (head == NULL)
+ head = &empty_slot;
}
- if (head == NULL)
- head = &empty_slot;
+ (*iterator) = _iterate_ids;
+ (*matched) = (const css_selector **) head;
- (*next) = (const css_selector **) head;
+ return CSS_OK;
+}
+
+/**
+ * Find the first universal selector
+ *
+ * \param hash Hash to search
+ * \param iterator Pointer to location to receive iterator function
+ * \param matched Pointer to location to receive selector
+ * \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_universal(css_selector_hash *hash,
+ css_selector_hash_iterator *iterator,
+ const css_selector ***matched)
+{
+ if (hash == NULL || iterator == NULL || matched == NULL)
+ return CSS_BADPARM;
+
+ (*iterator) = _iterate_universal;
+ (*matched) = (const css_selector **) &hash->universal;
return CSS_OK;
}
@@ -351,17 +508,6 @@ css_error css_selector_hash_size(css_selector_hash *hash, size_t *size)
******************************************************************************/
/**
- * Selector hash function
- *
- * \param sel Pointer to selector
- * \return hash value
- */
-uint32_t _hash(const css_selector *sel)
-{
- return _hash_name(sel->data.name);
-}
-
-/**
* Name hash function -- case-insensitive FNV.
*
* \param name Name to hash
@@ -385,3 +531,329 @@ uint32_t _hash_name(lwc_string *name)
return z;
}
+/**
+ * Retrieve the first class name in a selector, or NULL if none
+ *
+ * \param selector Selector to consider
+ * \return Pointer to class name, or NULL if none
+ */
+lwc_string *_class_name(const css_selector *selector)
+{
+ const css_selector_detail *detail = &selector->data;
+ lwc_string *name = NULL;
+
+ do {
+ if (detail->type == CSS_SELECTOR_CLASS) {
+ name = detail->name;
+ break;
+ }
+
+ if (detail->next)
+ detail++;
+ else
+ detail = NULL;
+ } while (detail != NULL);
+
+ return name;
+}
+
+/**
+ * Retrieve the first ID name in a selector, or NULL if none
+ *
+ * \param selector Selector to consider
+ * \return Pointer to ID name, or NULL if none
+ */
+lwc_string *_id_name(const css_selector *selector)
+{
+ const css_selector_detail *detail = &selector->data;
+ lwc_string *name = NULL;
+
+ do {
+ if (detail->type == CSS_SELECTOR_ID) {
+ name = detail->name;
+ break;
+ }
+
+ if (detail->next)
+ detail++;
+ else
+ detail = NULL;
+ } while (detail != NULL);
+
+ return name;
+}
+
+/**
+ * Insert a selector into a hash chain
+ *
+ * \param ctx Selector hash
+ * \param head Head of chain to insert into
+ * \param selector Selector to insert
+ * \return CSS_OK on success,
+ * CSS_NOMEM on memory exhaustion.
+ */
+css_error _insert_into_chain(css_selector_hash *ctx, hash_entry *head,
+ const css_selector *selector)
+{
+ if (head->sel == NULL) {
+ head->sel = selector;
+ head->next = NULL;
+ } else {
+ hash_entry *search = head;
+ hash_entry *prev = NULL;
+ hash_entry *entry =
+ ctx->alloc(NULL, sizeof(hash_entry), ctx->pw);
+ if (entry == NULL)
+ return CSS_NOMEM;
+
+ /* Find place to insert entry */
+ do {
+ /* Sort by ascending specificity */
+ if (search->sel->specificity > selector->specificity)
+ break;
+
+ /* Sort by ascending rule index */
+ if (search->sel->specificity == selector->specificity &&
+ search->sel->rule->index >
+ selector->rule->index)
+ break;
+
+ prev = search;
+ search = search->next;
+ } while (search != NULL);
+
+ if (prev == NULL) {
+ entry->sel = head->sel;
+ entry->next = head->next;
+ head->sel = selector;
+ head->next = entry;
+ } else {
+ entry->sel = selector;
+ entry->next = prev->next;
+ prev->next = entry;
+ }
+
+ ctx->hash_size += sizeof(hash_entry);
+ }
+
+ return CSS_OK;
+}
+
+/**
+ * Remove a selector from a hash chain
+ *
+ * \param ctx Selector hash
+ * \param head Head of chain to remove from
+ * \param selector Selector to remove
+ * \return CSS_OK on success,
+ * CSS_INVALID if selector not found in chain.
+ */
+css_error _remove_from_chain(css_selector_hash *ctx, hash_entry *head,
+ const css_selector *selector)
+{
+ hash_entry *search = head, *prev = NULL;
+
+ if (head->sel == NULL)
+ return CSS_INVALID;
+
+ do {
+ if (search->sel == selector)
+ break;
+
+ prev = search;
+ search = search->next;
+ } while (search != NULL);
+
+ if (search == NULL)
+ return CSS_INVALID;
+
+ if (prev == NULL) {
+ if (search->next != NULL) {
+ head->sel = search->next->sel;
+ head->next = search->next->next;
+ } else {
+ head->sel = NULL;
+ head->next = NULL;
+ }
+ } else {
+ prev->next = search->next;
+
+ ctx->alloc(search, 0, ctx->pw);
+
+ ctx->hash_size -= sizeof(hash_entry);
+ }
+
+ return CSS_OK;
+}
+
+/**
+ * Find the next selector that matches
+ *
+ * \param hash Hash to search
+ * \param current Current item
+ * \param next Pointer to location to receive next item
+ * \return CSS_OK on success, appropriate error otherwise
+ *
+ * If nothing further matches, CSS_OK will be returned and **next == NULL
+ */
+css_error _iterate_elements(css_selector_hash *hash,
+ const css_selector **current,
+ const css_selector ***next)
+{
+ const hash_entry *head = (const hash_entry *) current;
+ lwc_string *name;
+
+ if (hash == NULL || current == NULL || next == NULL)
+ return CSS_BADPARM;
+
+ name = head->sel->data.name;
+
+ /* Look for the next selector that matches the key */
+ for (head = head->next; head != NULL; head = head->next) {
+ lwc_error lerror = lwc_error_ok;
+ bool match = false;
+
+ lerror = lwc_context_string_caseless_isequal(hash->ctx,
+ name, head->sel->data.name, &match);
+ if (lerror != lwc_error_ok)
+ return css_error_from_lwc_error(lerror);
+
+ if (match)
+ break;
+ }
+
+ if (head == NULL)
+ head = &empty_slot;
+
+ (*next) = (const css_selector **) head;
+
+ return CSS_OK;
+}
+
+/**
+ * Find the next selector that matches
+ *
+ * \param hash Hash to search
+ * \param current Current item
+ * \param next Pointer to location to receive next item
+ * \return CSS_OK on success, appropriate error otherwise
+ *
+ * If nothing further matches, CSS_OK will be returned and **next == NULL
+ */
+css_error _iterate_classes(css_selector_hash *hash,
+ const css_selector **current,
+ const css_selector ***next)
+{
+ const hash_entry *head = (const hash_entry *) current;
+ lwc_string *ref;
+
+ if (hash == NULL || current == NULL || next == NULL)
+ return CSS_BADPARM;
+
+ ref = _class_name(head->sel);
+
+ /* Look for the next selector that matches the key */
+ for (head = head->next; head != NULL; head = head->next) {
+ lwc_error lerror = lwc_error_ok;
+ lwc_string *name;
+ bool match = false;
+
+ name = _class_name(head->sel);
+ if (name == NULL)
+ continue;
+
+ lerror = lwc_context_string_caseless_isequal(hash->ctx,
+ ref, name, &match);
+ if (lerror != lwc_error_ok)
+ return css_error_from_lwc_error(lerror);
+
+ if (match)
+ break;
+ }
+
+ if (head == NULL)
+ head = &empty_slot;
+
+ (*next) = (const css_selector **) head;
+
+ return CSS_OK;
+}
+
+/**
+ * Find the next selector that matches
+ *
+ * \param hash Hash to search
+ * \param current Current item
+ * \param next Pointer to location to receive next item
+ * \return CSS_OK on success, appropriate error otherwise
+ *
+ * If nothing further matches, CSS_OK will be returned and **next == NULL
+ */
+css_error _iterate_ids(css_selector_hash *hash,
+ const css_selector **current,
+ const css_selector ***next)
+{
+ const hash_entry *head = (const hash_entry *) current;
+ lwc_string *ref;
+
+ if (hash == NULL || current == NULL || next == NULL)
+ return CSS_BADPARM;
+
+ ref = _id_name(head->sel);
+
+ /* Look for the next selector that matches the key */
+ for (head = head->next; head != NULL; head = head->next) {
+ lwc_error lerror = lwc_error_ok;
+ lwc_string *name;
+ bool match = false;
+
+ name = _id_name(head->sel);
+ if (name == NULL)
+ continue;
+
+ lerror = lwc_context_string_caseless_isequal(hash->ctx,
+ ref, name, &match);
+ if (lerror != lwc_error_ok)
+ return css_error_from_lwc_error(lerror);
+
+ if (match)
+ break;
+ }
+
+ if (head == NULL)
+ head = &empty_slot;
+
+ (*next) = (const css_selector **) head;
+
+ return CSS_OK;
+}
+
+/**
+ * Find the next selector that matches
+ *
+ * \param hash Hash to search
+ * \param current Current item
+ * \param next Pointer to location to receive next item
+ * \return CSS_OK on success, appropriate error otherwise
+ *
+ * If nothing further matches, CSS_OK will be returned and **next == NULL
+ */
+css_error _iterate_universal(css_selector_hash *hash,
+ const css_selector **current,
+ const css_selector ***next)
+{
+ const hash_entry *head = (const hash_entry *) current;
+
+ if (hash == NULL || current == NULL || next == NULL)
+ return CSS_BADPARM;
+
+ if (head->next == NULL)
+ head = &empty_slot;
+ else
+ head = head->next;
+
+ (*next) = (const css_selector **) head;
+
+ return CSS_OK;
+}
+
diff --git a/src/select/hash.h b/src/select/hash.h
index 9beaa6b..e705554 100644
--- a/src/select/hash.h
+++ b/src/select/hash.h
@@ -18,6 +18,10 @@ struct css_selector;
typedef struct css_selector_hash css_selector_hash;
+typedef css_error (*css_selector_hash_iterator)(css_selector_hash *hash,
+ const struct css_selector **current,
+ const struct css_selector ***next);
+
css_error css_selector_hash_create(lwc_context *dict,
css_allocator_fn alloc, void *pw,
css_selector_hash **hash);
@@ -30,10 +34,19 @@ css_error css_selector_hash_remove(css_selector_hash *hash,
css_error css_selector_hash_find(css_selector_hash *hash,
lwc_string *name,
+ css_selector_hash_iterator *iterator,
+ const struct css_selector ***matched);
+css_error css_selector_hash_find_by_class(css_selector_hash *hash,
+ lwc_string *name,
+ css_selector_hash_iterator *iterator,
+ const struct css_selector ***matched);
+css_error css_selector_hash_find_by_id(css_selector_hash *hash,
+ lwc_string *name,
+ css_selector_hash_iterator *iterator,
+ const struct css_selector ***matched);
+css_error css_selector_hash_find_universal(css_selector_hash *hash,
+ css_selector_hash_iterator *iterator,
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);
css_error css_selector_hash_size(css_selector_hash *hash, size_t *size);
diff --git a/src/select/select.c b/src/select/select.c
index 1893f69..6261b62 100644
--- a/src/select/select.c
+++ b/src/select/select.c
@@ -622,12 +622,95 @@ css_error intern_strings_for_sheet(css_select_ctx *ctx,
return CSS_OK;
}
+static bool _selectors_pending(const css_selector **node,
+ const css_selector **id, const css_selector ***classes,
+ uint32_t n_classes, const css_selector **univ)
+{
+ bool pending = false;
+ uint32_t i;
+
+ pending |= *node != NULL;
+ pending |= *id != NULL;
+ pending |= *univ != NULL;
+
+ if (classes != NULL && n_classes > 0) {
+ for (i = 0; i < n_classes; i++)
+ pending |= *(classes[i]) != NULL;
+ }
+
+ return pending;
+}
+
+static inline bool _selector_less_specific(const css_selector *ref,
+ const css_selector *cand)
+{
+ bool result = true;
+
+ if (cand == NULL)
+ return false;
+
+ if (ref == NULL)
+ return true;
+
+ /* Sort by specificity */
+ if (cand->specificity < ref->specificity) {
+ result = true;
+ } else if (ref->specificity < cand->specificity) {
+ result = false;
+ } else {
+ /* Then by rule index -- earliest wins */
+ if (cand->rule->index < ref->rule->index)
+ result = true;
+ else
+ result = false;
+ }
+
+ return result;
+}
+
+static const css_selector *_selector_next(const css_selector **node,
+ const css_selector **id, const css_selector ***classes,
+ uint32_t n_classes, const css_selector **univ)
+{
+ const css_selector *ret = NULL;
+
+ if (_selector_less_specific(ret, *node))
+ ret = *node;
+
+ if (_selector_less_specific(ret, *id))
+ ret = *id;
+
+ if (_selector_less_specific(ret, *univ))
+ ret = *univ;
+
+ if (classes != NULL && n_classes > 0) {
+ uint32_t i;
+
+ for (i = 0; i < n_classes; i++) {
+ if (_selector_less_specific(ret, *(classes[i])))
+ ret = *(classes[i]);
+ }
+ }
+
+ return ret;
+}
+
css_error match_selectors_in_sheet(css_select_ctx *ctx,
const css_stylesheet *sheet, css_select_state *state)
{
- lwc_string *element;
- const css_selector **node_selectors;
- const css_selector **univ_selectors;
+ static const css_selector *empty_selector = NULL;
+ lwc_string *element = NULL;
+ lwc_string *id = NULL;
+ lwc_string **classes = NULL;
+ uint32_t n_classes = 0, i = 0;
+ const css_selector **node_selectors = &empty_selector;
+ css_selector_hash_iterator node_iterator;
+ const css_selector **id_selectors = &empty_selector;
+ css_selector_hash_iterator id_iterator;
+ const css_selector ***class_selectors = NULL;
+ css_selector_hash_iterator class_iterator;
+ const css_selector **univ_selectors = &empty_selector;
+ css_selector_hash_iterator univ_iterator;
css_error error;
/* Get node's name */
@@ -636,20 +719,62 @@ css_error match_selectors_in_sheet(css_select_ctx *ctx,
if (error != CSS_OK)
return error;
+ /* Get node's ID, if any */
+ error = state->handler->node_id(state->pw, state->node,
+ sheet->dictionary, &id);
+ if (error != CSS_OK)
+ goto cleanup;
+
+ /* Get node's classes, if any */
+ /** \todo Do we really want to force the client to allocate a new array
+ * every time we call this? It seems hugely inefficient, given they can
+ * cache the data. */
+ error = state->handler->node_classes(state->pw, state->node,
+ sheet->dictionary, &classes, &n_classes);
+ if (error != CSS_OK)
+ goto cleanup;
+
/* Find hash chain that applies to current node */
error = css_selector_hash_find(sheet->selectors, element,
- &node_selectors);
+ &node_iterator, &node_selectors);
if (error != CSS_OK)
goto cleanup;
+ if (classes != NULL && n_classes > 0) {
+ /* Find hash chains for node classes */
+ class_selectors = ctx->alloc(NULL,
+ n_classes * sizeof(css_selector **), ctx->pw);
+ if (class_selectors == NULL) {
+ error = CSS_NOMEM;
+ goto cleanup;
+ }
+
+ for (i = 0; i < n_classes; i++) {
+ error = css_selector_hash_find_by_class(
+ sheet->selectors, classes[i],
+ &class_iterator, &class_selectors[i]);
+ if (error != CSS_OK)
+ goto cleanup;
+ }
+ }
+
+ if (id != NULL) {
+ /* Find hash chain for node ID */
+ error = css_selector_hash_find_by_id(sheet->selectors, id,
+ &id_iterator, &id_selectors);
+ if (error != CSS_OK)
+ goto cleanup;
+ }
+
/* Find hash chain for universal selector */
- error = css_selector_hash_find(sheet->selectors, state->universal,
- &univ_selectors);
+ error = css_selector_hash_find_universal(sheet->selectors,
+ &univ_iterator, &univ_selectors);
if (error != CSS_OK)
goto cleanup;
/* Process matching selectors, if any */
- while (*node_selectors != NULL || *univ_selectors != NULL) {
+ while (_selectors_pending(node_selectors, id_selectors,
+ class_selectors, n_classes, univ_selectors)) {
const css_selector *selector;
css_rule *rule, *parent;
bool process = true;
@@ -659,31 +784,8 @@ css_error match_selectors_in_sheet(css_select_ctx *ctx,
*
* Pick the least specific/earliest occurring selector.
*/
- if (*node_selectors != NULL && *univ_selectors != NULL) {
- /* Both chains have entries, so choose least specific */
- const css_selector *node = *node_selectors;
- const css_selector *univ = *univ_selectors;
-
- /* Sort by specificity */
- if (node->specificity < univ->specificity) {
- selector = node;
- } else if (univ->specificity < node->specificity) {
- selector = univ;
- } else {
- /* Then by rule index -- earliest wins */
- if (node->rule->index < univ->rule->index)
- selector = node;
- else
- selector = univ;
- }
- } else if (*node_selectors != NULL) {
- /* Universal chain is empty, so exhaust node chain */
- selector = *node_selectors;
- } else {
- /* Node chain is empty, so exhaust universal chain */
- assert(*univ_selectors != NULL);
- selector = *univ_selectors;
- }
+ selector = _selector_next(node_selectors, id_selectors,
+ class_selectors, n_classes, univ_selectors);
/* Ignore any selectors contained in rules which are a child
* of an @media block that doesn't match the current media
@@ -711,11 +813,23 @@ css_error match_selectors_in_sheet(css_select_ctx *ctx,
/* Advance to next selector in whichever chain we extracted
* the processed selector from. */
if (selector == *node_selectors) {
- error = css_selector_hash_iterate(sheet->selectors,
+ error = node_iterator(sheet->selectors,
node_selectors, &node_selectors);
- } else {
- error = css_selector_hash_iterate(sheet->selectors,
+ } else if (selector == *id_selectors) {
+ error = id_iterator(sheet->selectors,
+ id_selectors, &id_selectors);
+ } else if (selector == *univ_selectors) {
+ error = univ_iterator(sheet->selectors,
univ_selectors, &univ_selectors);
+ } else {
+ for (i = 0; i < n_classes; i++) {
+ if (selector == *(class_selectors[i])) {
+ error = class_iterator(sheet->selectors,
+ class_selectors[i],
+ &class_selectors[i]);
+ break;
+ }
+ }
}
if (error != CSS_OK)
@@ -724,6 +838,19 @@ css_error match_selectors_in_sheet(css_select_ctx *ctx,
error = CSS_OK;
cleanup:
+ if (class_selectors != NULL)
+ ctx->alloc(class_selectors, 0, ctx->pw);
+
+ if (classes != NULL) {
+ for (i = 0; i < n_classes; i++)
+ lwc_context_string_unref(sheet->dictionary, classes[i]);
+
+ ctx->alloc(classes, 0, ctx->pw);
+ }
+
+ if (id != NULL)
+ lwc_context_string_unref(sheet->dictionary, id);
+
lwc_context_string_unref(sheet->dictionary, element);
return error;
}
diff --git a/test/select-auto.c b/test/select-auto.c
index 7e1ff35..2f3e028 100644
--- a/test/select-auto.c
+++ b/test/select-auto.c
@@ -72,6 +72,10 @@ static void destroy_tree(node *root);
static css_error node_name(void *pw, void *node, lwc_context *ctx,
lwc_string **name);
+static css_error node_classes(void *pw, void *node, lwc_context *ctx,
+ lwc_string ***classes, uint32_t *n_classes);
+static css_error node_id(void *pw, void *node, lwc_context *ctx,
+ lwc_string **id);
static css_error named_ancestor_node(void *pw, void *node,
lwc_string *name,
void **ancestor);
@@ -124,6 +128,8 @@ static css_error compute_font_size(void *pw, const css_hint *parent,
static css_select_handler select_handler = {
node_name,
+ node_classes,
+ node_id,
named_ancestor_node,
named_parent_node,
named_sibling_node,
@@ -721,6 +727,63 @@ css_error node_name(void *pw, void *n, lwc_context *ctx, lwc_string **name)
return CSS_OK;
}
+css_error node_classes(void *pw, void *n, lwc_context *ctx,
+ lwc_string ***classes, uint32_t *n_classes)
+{
+ node *node = n;
+ uint32_t i;
+ line_ctx *lc = pw;
+
+ for (i = 0; i < node->n_attrs; i++) {
+ bool amatch;
+ assert(lwc_context_string_caseless_isequal(ctx,
+ node->attrs[i].name, lc->attr_class, &amatch) ==
+ lwc_error_ok);
+ if (amatch == true)
+ break;
+ }
+
+ if (i != node->n_attrs) {
+ *classes = realloc(NULL, sizeof(lwc_string **));
+ if (*classes == NULL)
+ return CSS_NOMEM;
+
+ *(classes[0]) =
+ lwc_context_string_ref(ctx, node->attrs[i].value);
+ *n_classes = 1;
+ } else {
+ *classes = NULL;
+ *n_classes = 0;
+ }
+
+ return CSS_OK;
+
+}
+
+css_error node_id(void *pw, void *n, lwc_context *ctx,
+ lwc_string **id)
+{
+ node *node = n;
+ uint32_t i;
+ line_ctx *lc = pw;
+
+ for (i = 0; i < node->n_attrs; i++) {
+ bool amatch;
+ assert(lwc_context_string_caseless_isequal(ctx,
+ node->attrs[i].name, lc->attr_id, &amatch) ==
+ lwc_error_ok);
+ if (amatch == true)
+ break;
+ }
+
+ if (i != node->n_attrs)
+ *id = lwc_context_string_ref(ctx, node->attrs[i].value);
+ else
+ *id = NULL;
+
+ return CSS_OK;
+}
+
css_error named_ancestor_node(void *pw, void *n,
lwc_string *name,
void **ancestor)