From d2460b3a2f2690813abdf3b350be9dc5ebf2fe18 Mon Sep 17 00:00:00 2001 From: Michael Drake Date: Sun, 1 Dec 2013 19:00:25 +0000 Subject: Bloom filter implementation for selection optimisation. --- include/libcss/bloom.h | 205 +++++++++++++++++++++++++++++++++++++++++++++++++ 1 file changed, 205 insertions(+) create mode 100644 include/libcss/bloom.h (limited to 'include/libcss') diff --git a/include/libcss/bloom.h b/include/libcss/bloom.h new file mode 100644 index 0000000..8c1da3f --- /dev/null +++ b/include/libcss/bloom.h @@ -0,0 +1,205 @@ +/* + * This file is part of LibCSS. + * Licensed under the MIT License, + * http://www.opensource.org/licenses/mit-license.php + * Copyright 2013 Michael Drake + */ + +/** \file + * Bloom filter for CSS style selection optimisation. + * + * Attempting to match CSS rules by querying the client about DOM nodes via + * the selection callbacks is slow. To avoid this, clients may pass a node + * bloom filter to css_get_style. This bloom filter has bits set according + * to the node's ancestor element names, class names and id names. + * + * Generate the bloom filter by adding calling css_bloom_add_hash() on each + * ancestor element name, class name and id name for the node. + * + * Use the insesnsitive lwc_string: + * + * lwc_string_hash_value(str->insensitive) + */ + +#ifndef libcss_bloom_h_ +#define libcss_bloom_h_ + +#ifdef __cplusplus +extern "C" +{ +#endif + +#include + +/* Size of bloom filter as multiple of 32 bits. + * Has to be 4, 8, or 16. + * Larger increases optimisation of style selection engine but uses more memory. + */ +#define CSS_BLOOM_SIZE 4 + + + +/* Check valid bloom filter size */ +#if !(CSS_BLOOM_SIZE == 4 || CSS_BLOOM_SIZE == 8 || CSS_BLOOM_SIZE == 16) +# error Unsupported bloom filter size. Size must be {4|8|16}. +#endif + +/* Setup index bit mask */ +#define INDEX_BITS_N (CSS_BLOOM_SIZE - 1) + + + +/* type for bloom */ +typedef uint32_t css_bloom; + + +/** + * Add a hash value to the bloom filter. + * + * \param bloom bloom filter to insert into + * \param hash libwapcaplet hash value to insert + */ +static inline void css_bloom_add_hash(css_bloom bloom[CSS_BLOOM_SIZE], + lwc_hash hash) +{ + unsigned int bit = hash & 0x1f; /* Top 5 bits */ + unsigned int index = (hash >> 5) & INDEX_BITS_N; /* Next N bits */ + + bloom[index] |= (1 << bit); +} + + +/** + * Test whether bloom filter contains given hash value. + * + * \param bloom bloom filter to check inside + * \param hash libwapcaplet hash value to look for + * \return true hash value is already set in bloom + */ +static inline bool css_bloom_has_hash(const css_bloom bloom[CSS_BLOOM_SIZE], + lwc_hash hash) +{ + unsigned int bit = hash & 0x1f; /* Top 5 bits */ + unsigned int index = (hash >> 5) & INDEX_BITS_N; /* Next N bits */ + + return (bloom[index] & (1 << bit)); +} + + +/** + * Test whether bloom 'a' is a subset of bloom 'b'. + * + * \param a potential subset bloom to test + * \param b superset bloom + * \return true iff 'a' is subset of 'b' + */ +static inline bool css_bloom_in_bloom(const css_bloom a[CSS_BLOOM_SIZE], + const css_bloom b[CSS_BLOOM_SIZE]) +{ + if ((a[0] & b[0]) != a[0]) + return false; + if ((a[1] & b[1]) != a[1]) + return false; + if ((a[2] & b[2]) != a[2]) + return false; + if ((a[3] & b[3]) != a[3]) + return false; +#if (CSS_BLOOM_SIZE > 4) + if ((a[4] & b[4]) != a[4]) + return false; + if ((a[5] & b[5]) != a[5]) + return false; + if ((a[6] & b[6]) != a[6]) + return false; + if ((a[7] & b[7]) != a[7]) + return false; +#endif +#if (CSS_BLOOM_SIZE > 8) + if ((a[8] & b[8]) != a[8]) + return false; + if ((a[9] & b[9]) != a[9]) + return false; + if ((a[10] & b[10]) != a[10]) + return false; + if ((a[11] & b[11]) != a[11]) + return false; + if ((a[12] & b[12]) != a[12]) + return false; + if ((a[13] & b[13]) != a[13]) + return false; + if ((a[14] & b[14]) != a[14]) + return false; + if ((a[15] & b[15]) != a[15]) + return false; +#endif + return true; +} + + +/** + * Merge bloom 'a' into bloom 'b'. + * + * \param a bloom to insert + * \param b target bloom + */ +static inline void css_bloom_merge(const css_bloom a[CSS_BLOOM_SIZE], + css_bloom b[CSS_BLOOM_SIZE]) +{ + b[0] |= a[0]; + b[1] |= a[1]; + b[2] |= a[2]; + b[3] |= a[3]; +#if (CSS_BLOOM_SIZE > 4) + b[4] |= a[4]; + b[5] |= a[5]; + b[6] |= a[6]; + b[7] |= a[7]; +#endif +#if (CSS_BLOOM_SIZE > 8) + b[8] |= a[8]; + b[9] |= a[9]; + b[10] |= a[10]; + b[11] |= a[11]; + b[12] |= a[12]; + b[13] |= a[13]; + b[14] |= a[14]; + b[15] |= a[15]; +#endif +} + + +/** + * Initialise a bloom filter to 0 + * + * \param bloom bloom filter to initialise + */ +static inline void css_bloom_init(css_bloom bloom[CSS_BLOOM_SIZE]) +{ + bloom[0] = 0; + bloom[1] = 0; + bloom[2] = 0; + bloom[3] = 0; +#if (CSS_BLOOM_SIZE > 4) + bloom[4] = 0; + bloom[5] = 0; + bloom[6] = 0; + bloom[7] = 0; +#endif +#if (CSS_BLOOM_SIZE > 8) + bloom[8] = 0; + bloom[9] = 0; + bloom[10] = 0; + bloom[11] = 0; + bloom[12] = 0; + bloom[13] = 0; + bloom[14] = 0; + bloom[15] = 0; +#endif +} + +#ifdef __cplusplus +} +#endif + +#endif + -- cgit v1.2.3