Branch data Line data Source code
1 : : /***
2 : : This file is part of PulseAudio.
3 : :
4 : : Copyright 2004-2008 Lennart Poettering
5 : : Copyright 2006 Pierre Ossman <ossman@cendio.se> for Cendio AB
6 : :
7 : : PulseAudio is free software; you can redistribute it and/or modify
8 : : it under the terms of the GNU Lesser General Public License as
9 : : published by the Free Software Foundation; either version 2.1 of the
10 : : License, or (at your option) any later version.
11 : :
12 : : PulseAudio is distributed in the hope that it will be useful, but
13 : : WITHOUT ANY WARRANTY; without even the implied warranty of
14 : : MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the GNU
15 : : Lesser General Public License for more details.
16 : :
17 : : You should have received a copy of the GNU Lesser General Public
18 : : License along with PulseAudio; if not, write to the Free Software
19 : : Foundation, Inc., 59 Temple Place, Suite 330, Boston, MA 02111-1307
20 : : USA.
21 : : ***/
22 : :
23 : : #ifdef HAVE_CONFIG_H
24 : : #include <config.h>
25 : : #endif
26 : :
27 : : #include <stdio.h>
28 : : #include <stdlib.h>
29 : : #include <string.h>
30 : :
31 : : #include <pulse/xmalloc.h>
32 : : #include <pulsecore/flist.h>
33 : : #include <pulsecore/macro.h>
34 : :
35 : : #include "idxset.h"
36 : :
37 : : #define NBUCKETS 127
38 : :
39 : : struct idxset_entry {
40 : : uint32_t idx;
41 : : void *data;
42 : :
43 : : struct idxset_entry *data_next, *data_previous;
44 : : struct idxset_entry *index_next, *index_previous;
45 : : struct idxset_entry *iterate_next, *iterate_previous;
46 : : };
47 : :
48 : : struct pa_idxset {
49 : : pa_hash_func_t hash_func;
50 : : pa_compare_func_t compare_func;
51 : :
52 : : uint32_t current_index;
53 : :
54 : : struct idxset_entry *iterate_list_head, *iterate_list_tail;
55 : : unsigned n_entries;
56 : : };
57 : :
58 : : #define BY_DATA(i) ((struct idxset_entry**) ((uint8_t*) (i) + PA_ALIGN(sizeof(pa_idxset))))
59 : : #define BY_INDEX(i) (BY_DATA(i) + NBUCKETS)
60 : :
61 [ - + ][ # # ]: 27 : PA_STATIC_FLIST_DECLARE(entries, 0, pa_xfree);
62 : :
63 : 200 : unsigned pa_idxset_string_hash_func(const void *p) {
64 : 200 : unsigned hash = 0;
65 : : const char *c;
66 : :
67 [ + + ]: 2290 : for (c = p; *c; c++)
68 : 2090 : hash = 31 * hash + (unsigned) *c;
69 : :
70 : 200 : return hash;
71 : : }
72 : :
73 : 68 : int pa_idxset_string_compare_func(const void *a, const void *b) {
74 : 68 : return strcmp(a, b);
75 : : }
76 : :
77 : 64 : unsigned pa_idxset_trivial_hash_func(const void *p) {
78 : 64 : return PA_PTR_TO_UINT(p);
79 : : }
80 : :
81 : 16 : int pa_idxset_trivial_compare_func(const void *a, const void *b) {
82 [ + - ]: 16 : return a < b ? -1 : (a > b ? 1 : 0);
83 : : }
84 : :
85 : 0 : pa_idxset* pa_idxset_new(pa_hash_func_t hash_func, pa_compare_func_t compare_func) {
86 : : pa_idxset *s;
87 : :
88 : 0 : s = pa_xmalloc0(PA_ALIGN(sizeof(pa_idxset)) + NBUCKETS*2*sizeof(struct idxset_entry*));
89 : :
90 [ # # ]: 0 : s->hash_func = hash_func ? hash_func : pa_idxset_trivial_hash_func;
91 [ # # ]: 0 : s->compare_func = compare_func ? compare_func : pa_idxset_trivial_compare_func;
92 : :
93 : 0 : s->current_index = 0;
94 : 0 : s->n_entries = 0;
95 : 0 : s->iterate_list_head = s->iterate_list_tail = NULL;
96 : :
97 : 0 : return s;
98 : : }
99 : :
100 : 0 : static void remove_entry(pa_idxset *s, struct idxset_entry *e) {
101 [ # # ]: 0 : pa_assert(s);
102 [ # # ]: 0 : pa_assert(e);
103 : :
104 : : /* Remove from iteration linked list */
105 [ # # ]: 0 : if (e->iterate_next)
106 : 0 : e->iterate_next->iterate_previous = e->iterate_previous;
107 : : else
108 : 0 : s->iterate_list_tail = e->iterate_previous;
109 : :
110 [ # # ]: 0 : if (e->iterate_previous)
111 : 0 : e->iterate_previous->iterate_next = e->iterate_next;
112 : : else
113 : 0 : s->iterate_list_head = e->iterate_next;
114 : :
115 : : /* Remove from data hash table */
116 [ # # ]: 0 : if (e->data_next)
117 : 0 : e->data_next->data_previous = e->data_previous;
118 : :
119 [ # # ]: 0 : if (e->data_previous)
120 : 0 : e->data_previous->data_next = e->data_next;
121 : : else {
122 : 0 : unsigned hash = s->hash_func(e->data) % NBUCKETS;
123 : 0 : BY_DATA(s)[hash] = e->data_next;
124 : : }
125 : :
126 : : /* Remove from index hash table */
127 [ # # ]: 0 : if (e->index_next)
128 : 0 : e->index_next->index_previous = e->index_previous;
129 : :
130 [ # # ]: 0 : if (e->index_previous)
131 : 0 : e->index_previous->index_next = e->index_next;
132 : : else
133 : 0 : BY_INDEX(s)[e->idx % NBUCKETS] = e->index_next;
134 : :
135 [ # # ]: 0 : if (pa_flist_push(PA_STATIC_FLIST_GET(entries), e) < 0)
136 : 0 : pa_xfree(e);
137 : :
138 [ # # ]: 0 : pa_assert(s->n_entries >= 1);
139 : 0 : s->n_entries--;
140 : 0 : }
141 : :
142 : 0 : void pa_idxset_free(pa_idxset *s, pa_free2_cb_t free_cb, void *userdata) {
143 [ # # ]: 0 : pa_assert(s);
144 : :
145 [ # # ]: 0 : while (s->iterate_list_head) {
146 : 0 : void *data = s->iterate_list_head->data;
147 : :
148 : 0 : remove_entry(s, s->iterate_list_head);
149 : :
150 [ # # ]: 0 : if (free_cb)
151 : 0 : free_cb(data, userdata);
152 : : }
153 : :
154 : 0 : pa_xfree(s);
155 : 0 : }
156 : :
157 : 0 : static struct idxset_entry* data_scan(pa_idxset *s, unsigned hash, const void *p) {
158 : : struct idxset_entry *e;
159 [ # # ]: 0 : pa_assert(s);
160 [ # # ]: 0 : pa_assert(hash < NBUCKETS);
161 [ # # ]: 0 : pa_assert(p);
162 : :
163 [ # # ]: 0 : for (e = BY_DATA(s)[hash]; e; e = e->data_next)
164 [ # # ]: 0 : if (s->compare_func(e->data, p) == 0)
165 : : return e;
166 : :
167 : : return NULL;
168 : : }
169 : :
170 : 0 : static struct idxset_entry* index_scan(pa_idxset *s, unsigned hash, uint32_t idx) {
171 : : struct idxset_entry *e;
172 [ # # ]: 0 : pa_assert(s);
173 [ # # ]: 0 : pa_assert(hash < NBUCKETS);
174 : :
175 [ # # ]: 0 : for (e = BY_INDEX(s)[hash]; e; e = e->index_next)
176 [ # # ]: 0 : if (e->idx == idx)
177 : : return e;
178 : :
179 : : return NULL;
180 : : }
181 : :
182 : 0 : int pa_idxset_put(pa_idxset*s, void *p, uint32_t *idx) {
183 : : unsigned hash;
184 : : struct idxset_entry *e;
185 : :
186 [ # # ]: 0 : pa_assert(s);
187 : :
188 : 0 : hash = s->hash_func(p) % NBUCKETS;
189 : :
190 [ # # ]: 0 : if ((e = data_scan(s, hash, p))) {
191 [ # # ]: 0 : if (idx)
192 : 0 : *idx = e->idx;
193 : :
194 : : return -1;
195 : : }
196 : :
197 [ # # ]: 0 : if (!(e = pa_flist_pop(PA_STATIC_FLIST_GET(entries))))
198 : 0 : e = pa_xnew(struct idxset_entry, 1);
199 : :
200 : 0 : e->data = p;
201 : 0 : e->idx = s->current_index++;
202 : :
203 : : /* Insert into data hash table */
204 : 0 : e->data_next = BY_DATA(s)[hash];
205 : 0 : e->data_previous = NULL;
206 [ # # ]: 0 : if (BY_DATA(s)[hash])
207 : 0 : BY_DATA(s)[hash]->data_previous = e;
208 : 0 : BY_DATA(s)[hash] = e;
209 : :
210 : 0 : hash = e->idx % NBUCKETS;
211 : :
212 : : /* Insert into index hash table */
213 : 0 : e->index_next = BY_INDEX(s)[hash];
214 : 0 : e->index_previous = NULL;
215 [ # # ]: 0 : if (BY_INDEX(s)[hash])
216 : 0 : BY_INDEX(s)[hash]->index_previous = e;
217 : 0 : BY_INDEX(s)[hash] = e;
218 : :
219 : : /* Insert into iteration list */
220 : 0 : e->iterate_previous = s->iterate_list_tail;
221 : 0 : e->iterate_next = NULL;
222 [ # # ]: 0 : if (s->iterate_list_tail) {
223 [ # # ]: 0 : pa_assert(s->iterate_list_head);
224 : 0 : s->iterate_list_tail->iterate_next = e;
225 : : } else {
226 [ # # ]: 0 : pa_assert(!s->iterate_list_head);
227 : 0 : s->iterate_list_head = e;
228 : : }
229 : 0 : s->iterate_list_tail = e;
230 : :
231 : 0 : s->n_entries++;
232 [ # # ]: 0 : pa_assert(s->n_entries >= 1);
233 : :
234 [ # # ]: 0 : if (idx)
235 : 0 : *idx = e->idx;
236 : :
237 : : return 0;
238 : : }
239 : :
240 : 0 : void* pa_idxset_get_by_index(pa_idxset*s, uint32_t idx) {
241 : : unsigned hash;
242 : : struct idxset_entry *e;
243 : :
244 [ # # ]: 0 : pa_assert(s);
245 : :
246 : 0 : hash = idx % NBUCKETS;
247 : :
248 [ # # ]: 0 : if (!(e = index_scan(s, hash, idx)))
249 : : return NULL;
250 : :
251 : 0 : return e->data;
252 : : }
253 : :
254 : 0 : void* pa_idxset_get_by_data(pa_idxset*s, const void *p, uint32_t *idx) {
255 : : unsigned hash;
256 : : struct idxset_entry *e;
257 : :
258 [ # # ]: 0 : pa_assert(s);
259 : :
260 : 0 : hash = s->hash_func(p) % NBUCKETS;
261 : :
262 [ # # ]: 0 : if (!(e = data_scan(s, hash, p)))
263 : : return NULL;
264 : :
265 [ # # ]: 0 : if (idx)
266 : 0 : *idx = e->idx;
267 : :
268 : 0 : return e->data;
269 : : }
270 : :
271 : 0 : void* pa_idxset_remove_by_index(pa_idxset*s, uint32_t idx) {
272 : : struct idxset_entry *e;
273 : : unsigned hash;
274 : : void *data;
275 : :
276 [ # # ]: 0 : pa_assert(s);
277 : :
278 : 0 : hash = idx % NBUCKETS;
279 : :
280 [ # # ]: 0 : if (!(e = index_scan(s, hash, idx)))
281 : : return NULL;
282 : :
283 : 0 : data = e->data;
284 : 0 : remove_entry(s, e);
285 : :
286 : 0 : return data;
287 : : }
288 : :
289 : 0 : void* pa_idxset_remove_by_data(pa_idxset*s, const void *data, uint32_t *idx) {
290 : : struct idxset_entry *e;
291 : : unsigned hash;
292 : : void *r;
293 : :
294 [ # # ]: 0 : pa_assert(s);
295 : :
296 : 0 : hash = s->hash_func(data) % NBUCKETS;
297 : :
298 [ # # ]: 0 : if (!(e = data_scan(s, hash, data)))
299 : : return NULL;
300 : :
301 : 0 : r = e->data;
302 : :
303 [ # # ]: 0 : if (idx)
304 : 0 : *idx = e->idx;
305 : :
306 : 0 : remove_entry(s, e);
307 : :
308 : 0 : return r;
309 : : }
310 : :
311 : 0 : void* pa_idxset_rrobin(pa_idxset *s, uint32_t *idx) {
312 : : unsigned hash;
313 : : struct idxset_entry *e;
314 : :
315 [ # # ]: 0 : pa_assert(s);
316 [ # # ]: 0 : pa_assert(idx);
317 : :
318 : 0 : hash = *idx % NBUCKETS;
319 : :
320 : 0 : e = index_scan(s, hash, *idx);
321 : :
322 [ # # ][ # # ]: 0 : if (e && e->iterate_next)
323 : 0 : e = e->iterate_next;
324 : : else
325 : 0 : e = s->iterate_list_head;
326 : :
327 [ # # ]: 0 : if (!e)
328 : : return NULL;
329 : :
330 : 0 : *idx = e->idx;
331 : 0 : return e->data;
332 : : }
333 : :
334 : 0 : void *pa_idxset_iterate(pa_idxset *s, void **state, uint32_t *idx) {
335 : : struct idxset_entry *e;
336 : :
337 [ # # ]: 0 : pa_assert(s);
338 [ # # ]: 0 : pa_assert(state);
339 : :
340 [ # # ]: 0 : if (*state == (void*) -1)
341 : : goto at_end;
342 : :
343 [ # # ][ # # ]: 0 : if ((!*state && !s->iterate_list_head))
344 : : goto at_end;
345 : :
346 [ # # ]: 0 : e = *state ? *state : s->iterate_list_head;
347 : :
348 [ # # ]: 0 : if (e->iterate_next)
349 : 0 : *state = e->iterate_next;
350 : : else
351 : 0 : *state = (void*) -1;
352 : :
353 [ # # ]: 0 : if (idx)
354 : 0 : *idx = e->idx;
355 : :
356 : 0 : return e->data;
357 : :
358 : : at_end:
359 : 0 : *state = (void *) -1;
360 : :
361 [ # # ]: 0 : if (idx)
362 : 0 : *idx = PA_IDXSET_INVALID;
363 : :
364 : : return NULL;
365 : : }
366 : :
367 : 0 : void* pa_idxset_steal_first(pa_idxset *s, uint32_t *idx) {
368 : : void *data;
369 : :
370 [ # # ]: 0 : pa_assert(s);
371 : :
372 [ # # ]: 0 : if (!s->iterate_list_head)
373 : : return NULL;
374 : :
375 : 0 : data = s->iterate_list_head->data;
376 : :
377 [ # # ]: 0 : if (idx)
378 : 0 : *idx = s->iterate_list_head->idx;
379 : :
380 : 0 : remove_entry(s, s->iterate_list_head);
381 : :
382 : 0 : return data;
383 : : }
384 : :
385 : 0 : void* pa_idxset_first(pa_idxset *s, uint32_t *idx) {
386 [ # # ]: 0 : pa_assert(s);
387 : :
388 [ # # ]: 0 : if (!s->iterate_list_head) {
389 [ # # ]: 0 : if (idx)
390 : 0 : *idx = PA_IDXSET_INVALID;
391 : : return NULL;
392 : : }
393 : :
394 [ # # ]: 0 : if (idx)
395 : 0 : *idx = s->iterate_list_head->idx;
396 : :
397 : 0 : return s->iterate_list_head->data;
398 : : }
399 : :
400 : 0 : void *pa_idxset_next(pa_idxset *s, uint32_t *idx) {
401 : : struct idxset_entry *e;
402 : : unsigned hash;
403 : :
404 [ # # ]: 0 : pa_assert(s);
405 [ # # ]: 0 : pa_assert(idx);
406 : :
407 [ # # ]: 0 : if (*idx == PA_IDXSET_INVALID)
408 : : return NULL;
409 : :
410 : 0 : hash = *idx % NBUCKETS;
411 : :
412 [ # # ]: 0 : if ((e = index_scan(s, hash, *idx))) {
413 : :
414 : 0 : e = e->iterate_next;
415 : :
416 [ # # ]: 0 : if (e) {
417 : 0 : *idx = e->idx;
418 : 0 : return e->data;
419 : : } else {
420 : 0 : *idx = PA_IDXSET_INVALID;
421 : 0 : return NULL;
422 : : }
423 : :
424 : : } else {
425 : :
426 : : /* If the entry passed doesn't exist anymore we try to find
427 : : * the next following */
428 : :
429 [ # # ]: 0 : for ((*idx)++; *idx < s->current_index; (*idx)++) {
430 : :
431 : 0 : hash = *idx % NBUCKETS;
432 : :
433 [ # # ]: 0 : if ((e = index_scan(s, hash, *idx))) {
434 : 0 : *idx = e->idx;
435 : 0 : return e->data;
436 : : }
437 : : }
438 : :
439 : 0 : *idx = PA_IDXSET_INVALID;
440 : 0 : return NULL;
441 : : }
442 : : }
443 : :
444 : 0 : unsigned pa_idxset_size(pa_idxset*s) {
445 [ # # ]: 0 : pa_assert(s);
446 : :
447 : 0 : return s->n_entries;
448 : : }
449 : :
450 : 0 : pa_bool_t pa_idxset_isempty(pa_idxset *s) {
451 [ # # ]: 0 : pa_assert(s);
452 : :
453 : 0 : return s->n_entries == 0;
454 : : }
455 : :
456 : 0 : pa_idxset *pa_idxset_copy(pa_idxset *s) {
457 : : pa_idxset *copy;
458 : : struct idxset_entry *i;
459 : :
460 [ # # ]: 0 : pa_assert(s);
461 : :
462 : 0 : copy = pa_idxset_new(s->hash_func, s->compare_func);
463 : :
464 [ # # ]: 0 : for (i = s->iterate_list_head; i; i = i->iterate_next)
465 : 0 : pa_idxset_put(copy, i->data, NULL);
466 : :
467 : 0 : return copy;
468 : : }
|
