summaryrefslogtreecommitdiff
path: root/src/select/hash.c
blob: 2a30a5f35be6da630f47d03d1487d4cb24a4eff7 (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
197
198
199
200
201
202
203
204
205
206
207
208
209
210
211
212
213
214
215
216
217
218
219
220
221
222
223
224
225
226
227
228
229
230
231
232
233
234
235
236
237
238
239
240
241
242
243
244
245
246
247
248
249
250
251
252
253
254
255
256
257
258
259
260
261
262
263
264
265
266
267
268
269
270
271
272
273
274
275
276
277
278
279
280
281
282
283
284
285
286
287
288
289
290
291
292
293
294
295
296
297
298
299
300
301
302
303
304
305
306
307
308
309
310
311
312
313
314
315
316
317
/*
 * This file is part of LibCSS
 * Licensed under the MIT License,
 *                http://www.opensource.org/licenses/mit-license.php
 * Copyright 2009 John-Mark Bell <jmb@netsurf-browser.org>
 */

#include <stdio.h>
#include <string.h>

#include "stylesheet.h"
#include "select/hash.h"

typedef struct hash_entry {
	const css_selector *sel;
	struct hash_entry *next;
} hash_entry;

struct css_selector_hash {
#define DEFAULT_SLOTS (1<<6)
	size_t n_slots;

	hash_entry *slots;

	css_allocator_fn alloc;
	void *pw;
};

static hash_entry empty_slot;

static inline uint32_t _hash(const css_selector *sel);
static inline uint32_t _hash_name(const parserutils_hash_entry *name);

/**
 * 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_allocator_fn 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(hash_entry), pw);
	if (h->slots == NULL) {
		alloc(h, 0, pw);
		return CSS_NOMEM;
	}

	memset(h->slots, 0, DEFAULT_SLOTS * sizeof(hash_entry));
	h->n_slots = DEFAULT_SLOTS;

	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)
{
	uint32_t i;

	if (hash == NULL)
		return CSS_BADPARM;

	for (i = 0; i < hash->n_slots; i++) {
		hash_entry *d, *e;

		for (d = hash->slots[i].next; d != NULL; d = e) {
			e = d->next;

			hash->alloc(d, 0, hash->pw);
		}
	}

	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;
	hash_entry *head;

	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;
	} 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;
		}
	}

	return CSS_OK;
}

/**
 * Remove an item from a hash
 *
 * \param hash      The hash to remove from
 * \param selector  Pointer to selector
 * \return CSS_OK on success, appropriate error otherwise
 */
css_error css_selector_hash_remove(css_selector_hash *hash,
		const css_selector *selector)
{
	uint32_t index, mask;
	hash_entry *head, *prev = NULL;

	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;
		}
	} else {
		prev->next = head->next;

		hash->alloc(head, 0, hash->pw);
	}

	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;
	hash_entry *head;

	if (hash == NULL || name == NULL || matched == NULL)
		return CSS_BADPARM;

	/* Find index */
	mask = hash->n_slots - 1;
	index = _hash_name(name) & mask;

	head = &hash->slots[index];

	if (head->sel != NULL) {
		do {
			if (head->sel->data.name == name)
				break;

			head = head->next;
		} while (head != NULL);

		if (head == NULL)
			head = &empty_slot;
	}

	(*matched) = (const css_selector **) head;

	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)
{
	hash_entry *head = (hash_entry *) current;

	if (hash == NULL || current == NULL || next == NULL)
		return CSS_BADPARM;

	for (head = head->next; head != NULL; head = head->next) {
		if (head->sel->data.name == (*current)->data.name)
			break;
	}

	if (head == NULL)
		head = &empty_slot;

	(*next) = (const css_selector **) head;

	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);
}