2 This file is part of PulseAudio.
4 Copyright 2004-2008 Lennart Poettering
5 Copyright 2006 Pierre Ossman <ossman@cendio.se> for Cendio AB
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.
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.
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
31 #include <pulse/xmalloc.h>
32 #include <pulsecore/flist.h>
33 #include <pulsecore/macro.h>
43 struct idxset_entry
*data_next
, *data_previous
;
44 struct idxset_entry
*index_next
, *index_previous
;
45 struct idxset_entry
*iterate_next
, *iterate_previous
;
49 pa_hash_func_t hash_func
;
50 pa_compare_func_t compare_func
;
52 uint32_t current_index
;
54 struct idxset_entry
*iterate_list_head
, *iterate_list_tail
;
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)
61 PA_STATIC_FLIST_DECLARE(entries
, 0, pa_xfree
);
63 unsigned pa_idxset_string_hash_func(const void *p
) {
68 hash
= 31 * hash
+ (unsigned) *c
;
73 int pa_idxset_string_compare_func(const void *a
, const void *b
) {
77 unsigned pa_idxset_trivial_hash_func(const void *p
) {
78 return PA_PTR_TO_UINT(p
);
81 int pa_idxset_trivial_compare_func(const void *a
, const void *b
) {
82 return a
< b
? -1 : (a
> b
? 1 : 0);
85 pa_idxset
* pa_idxset_new(pa_hash_func_t hash_func
, pa_compare_func_t compare_func
) {
88 s
= pa_xmalloc0(PA_ALIGN(sizeof(pa_idxset
)) + NBUCKETS
*2*sizeof(struct idxset_entry
*));
90 s
->hash_func
= hash_func
? hash_func
: pa_idxset_trivial_hash_func
;
91 s
->compare_func
= compare_func
? compare_func
: pa_idxset_trivial_compare_func
;
95 s
->iterate_list_head
= s
->iterate_list_tail
= NULL
;
100 static void remove_entry(pa_idxset
*s
, struct idxset_entry
*e
) {
104 /* Remove from iteration linked list */
106 e
->iterate_next
->iterate_previous
= e
->iterate_previous
;
108 s
->iterate_list_tail
= e
->iterate_previous
;
110 if (e
->iterate_previous
)
111 e
->iterate_previous
->iterate_next
= e
->iterate_next
;
113 s
->iterate_list_head
= e
->iterate_next
;
115 /* Remove from data hash table */
117 e
->data_next
->data_previous
= e
->data_previous
;
119 if (e
->data_previous
)
120 e
->data_previous
->data_next
= e
->data_next
;
122 unsigned hash
= s
->hash_func(e
->data
) % NBUCKETS
;
123 BY_DATA(s
)[hash
] = e
->data_next
;
126 /* Remove from index hash table */
128 e
->index_next
->index_previous
= e
->index_previous
;
130 if (e
->index_previous
)
131 e
->index_previous
->index_next
= e
->index_next
;
133 BY_INDEX(s
)[e
->idx
% NBUCKETS
] = e
->index_next
;
135 if (pa_flist_push(PA_STATIC_FLIST_GET(entries
), e
) < 0)
138 pa_assert(s
->n_entries
>= 1);
142 void pa_idxset_free(pa_idxset
*s
, pa_free_cb_t free_cb
) {
145 pa_idxset_remove_all(s
, free_cb
);
149 static struct idxset_entry
* data_scan(pa_idxset
*s
, unsigned hash
, const void *p
) {
150 struct idxset_entry
*e
;
152 pa_assert(hash
< NBUCKETS
);
155 for (e
= BY_DATA(s
)[hash
]; e
; e
= e
->data_next
)
156 if (s
->compare_func(e
->data
, p
) == 0)
162 static struct idxset_entry
* index_scan(pa_idxset
*s
, unsigned hash
, uint32_t idx
) {
163 struct idxset_entry
*e
;
165 pa_assert(hash
< NBUCKETS
);
167 for (e
= BY_INDEX(s
)[hash
]; e
; e
= e
->index_next
)
174 int pa_idxset_put(pa_idxset
*s
, void *p
, uint32_t *idx
) {
176 struct idxset_entry
*e
;
180 hash
= s
->hash_func(p
) % NBUCKETS
;
182 if ((e
= data_scan(s
, hash
, p
))) {
189 if (!(e
= pa_flist_pop(PA_STATIC_FLIST_GET(entries
))))
190 e
= pa_xnew(struct idxset_entry
, 1);
193 e
->idx
= s
->current_index
++;
195 /* Insert into data hash table */
196 e
->data_next
= BY_DATA(s
)[hash
];
197 e
->data_previous
= NULL
;
198 if (BY_DATA(s
)[hash
])
199 BY_DATA(s
)[hash
]->data_previous
= e
;
200 BY_DATA(s
)[hash
] = e
;
202 hash
= e
->idx
% NBUCKETS
;
204 /* Insert into index hash table */
205 e
->index_next
= BY_INDEX(s
)[hash
];
206 e
->index_previous
= NULL
;
207 if (BY_INDEX(s
)[hash
])
208 BY_INDEX(s
)[hash
]->index_previous
= e
;
209 BY_INDEX(s
)[hash
] = e
;
211 /* Insert into iteration list */
212 e
->iterate_previous
= s
->iterate_list_tail
;
213 e
->iterate_next
= NULL
;
214 if (s
->iterate_list_tail
) {
215 pa_assert(s
->iterate_list_head
);
216 s
->iterate_list_tail
->iterate_next
= e
;
218 pa_assert(!s
->iterate_list_head
);
219 s
->iterate_list_head
= e
;
221 s
->iterate_list_tail
= e
;
224 pa_assert(s
->n_entries
>= 1);
232 void* pa_idxset_get_by_index(pa_idxset
*s
, uint32_t idx
) {
234 struct idxset_entry
*e
;
238 hash
= idx
% NBUCKETS
;
240 if (!(e
= index_scan(s
, hash
, idx
)))
246 void* pa_idxset_get_by_data(pa_idxset
*s
, const void *p
, uint32_t *idx
) {
248 struct idxset_entry
*e
;
252 hash
= s
->hash_func(p
) % NBUCKETS
;
254 if (!(e
= data_scan(s
, hash
, p
)))
263 void* pa_idxset_remove_by_index(pa_idxset
*s
, uint32_t idx
) {
264 struct idxset_entry
*e
;
270 hash
= idx
% NBUCKETS
;
272 if (!(e
= index_scan(s
, hash
, idx
)))
281 void* pa_idxset_remove_by_data(pa_idxset
*s
, const void *data
, uint32_t *idx
) {
282 struct idxset_entry
*e
;
288 hash
= s
->hash_func(data
) % NBUCKETS
;
290 if (!(e
= data_scan(s
, hash
, data
)))
303 void pa_idxset_remove_all(pa_idxset
*s
, pa_free_cb_t free_cb
) {
306 while (s
->iterate_list_head
) {
307 void *data
= s
->iterate_list_head
->data
;
309 remove_entry(s
, s
->iterate_list_head
);
316 void* pa_idxset_rrobin(pa_idxset
*s
, uint32_t *idx
) {
318 struct idxset_entry
*e
;
323 hash
= *idx
% NBUCKETS
;
325 e
= index_scan(s
, hash
, *idx
);
327 if (e
&& e
->iterate_next
)
330 e
= s
->iterate_list_head
;
339 void *pa_idxset_iterate(pa_idxset
*s
, void **state
, uint32_t *idx
) {
340 struct idxset_entry
*e
;
345 if (*state
== (void*) -1)
348 if ((!*state
&& !s
->iterate_list_head
))
351 e
= *state
? *state
: s
->iterate_list_head
;
354 *state
= e
->iterate_next
;
364 *state
= (void *) -1;
367 *idx
= PA_IDXSET_INVALID
;
372 void* pa_idxset_steal_first(pa_idxset
*s
, uint32_t *idx
) {
377 if (!s
->iterate_list_head
)
380 data
= s
->iterate_list_head
->data
;
383 *idx
= s
->iterate_list_head
->idx
;
385 remove_entry(s
, s
->iterate_list_head
);
390 void* pa_idxset_first(pa_idxset
*s
, uint32_t *idx
) {
393 if (!s
->iterate_list_head
) {
395 *idx
= PA_IDXSET_INVALID
;
400 *idx
= s
->iterate_list_head
->idx
;
402 return s
->iterate_list_head
->data
;
405 void *pa_idxset_next(pa_idxset
*s
, uint32_t *idx
) {
406 struct idxset_entry
*e
;
412 if (*idx
== PA_IDXSET_INVALID
)
415 hash
= *idx
% NBUCKETS
;
417 if ((e
= index_scan(s
, hash
, *idx
))) {
425 *idx
= PA_IDXSET_INVALID
;
431 /* If the entry passed doesn't exist anymore we try to find
432 * the next following */
434 for ((*idx
)++; *idx
< s
->current_index
; (*idx
)++) {
436 hash
= *idx
% NBUCKETS
;
438 if ((e
= index_scan(s
, hash
, *idx
))) {
444 *idx
= PA_IDXSET_INVALID
;
449 unsigned pa_idxset_size(pa_idxset
*s
) {
455 bool pa_idxset_isempty(pa_idxset
*s
) {
458 return s
->n_entries
== 0;
461 pa_idxset
*pa_idxset_copy(pa_idxset
*s
, pa_copy_func_t copy_func
) {
463 struct idxset_entry
*i
;
467 copy
= pa_idxset_new(s
->hash_func
, s
->compare_func
);
469 for (i
= s
->iterate_list_head
; i
; i
= i
->iterate_next
)
470 pa_idxset_put(copy
, copy_func
? copy_func(i
->data
) : i
->data
, NULL
);