From 551c4e5bc7147f8eee1bb48cdd26bc83a66aa78a Mon Sep 17 00:00:00 2001 From: John Mark Bell Date: Wed, 29 Jul 2009 09:57:04 +0000 Subject: 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 --- src/select/hash.c | 738 ++++++++++++++++++++++++++++++++++++++++++---------- src/select/hash.h | 19 +- src/select/select.c | 197 +++++++++++--- 3 files changed, 783 insertions(+), 171 deletions(-) (limited to 'src') 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; } @@ -350,17 +507,6 @@ css_error css_selector_hash_size(css_selector_hash *hash, size_t *size) * Private functions * ******************************************************************************/ -/** - * 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. * @@ -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; } -- cgit v1.2.3