summaryrefslogtreecommitdiff
path: root/src/select/bloom.h
blob: 11628ab29d6e872e65810eb61ec0e798c6d8fef6 (plain)
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
180
181
182
183
184
185
186
187
188
189
190
191
192
193
194
195
196
/*
 * This file is part of LibCSS.
 * Licensed under the MIT License,
 *                http://www.opensource.org/licenses/mit-license.php
 * Copyright 2013 Michael Drake <tlsa@netsurf-browser.org>
 */

/** \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 hash value:
 *
 *     lwc_err = lwc_string_caseless_hash_value(str, &hash);
 */

#ifndef libcss_bloom_h_
#define libcss_bloom_h_

#include <stdint.h>

/* 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
}

#endif