2 This file is part of PulseAudio.
4 Copyright 2004-2006 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/macro.h>
33 #include <pulsecore/flist.h>
42 struct idxset_entry
*hash_prev
, *hash_next
;
43 struct idxset_entry
* iterate_prev
, *iterate_next
;
47 pa_hash_func_t hash_func
;
48 pa_compare_func_t compare_func
;
50 unsigned hash_table_size
, n_entries
;
51 struct idxset_entry
**hash_table
, **array
, *iterate_list_head
, *iterate_list_tail
;
52 uint32_t index
, start_index
, array_size
;
55 PA_STATIC_FLIST_DECLARE(entries
, 0, pa_xfree
);
57 unsigned pa_idxset_string_hash_func(const void *p
) {
62 hash
= 31 * hash
+ *c
;
67 int pa_idxset_string_compare_func(const void *a
, const void *b
) {
71 unsigned pa_idxset_trivial_hash_func(const void *p
) {
72 return PA_PTR_TO_UINT(p
);
75 int pa_idxset_trivial_compare_func(const void *a
, const void *b
) {
79 pa_idxset
* pa_idxset_new(pa_hash_func_t hash_func
, pa_compare_func_t compare_func
) {
82 s
= pa_xnew(pa_idxset
, 1);
83 s
->hash_func
= hash_func
? hash_func
: pa_idxset_trivial_hash_func
;
84 s
->compare_func
= compare_func
? compare_func
: pa_idxset_trivial_compare_func
;
85 s
->hash_table_size
= 127;
86 s
->hash_table
= pa_xnew0(struct idxset_entry
*, s
->hash_table_size
);
93 s
->iterate_list_head
= s
->iterate_list_tail
= NULL
;
98 void pa_idxset_free(pa_idxset
*s
, void (*free_func
) (void *p
, void *userdata
), void *userdata
) {
101 while (s
->iterate_list_head
) {
102 struct idxset_entry
*e
= s
->iterate_list_head
;
103 s
->iterate_list_head
= s
->iterate_list_head
->iterate_next
;
106 free_func(e
->data
, userdata
);
108 if (pa_flist_push(PA_STATIC_FLIST_GET(entries
), e
) < 0)
112 pa_xfree(s
->hash_table
);
117 static struct idxset_entry
* hash_scan(pa_idxset
*s
, struct idxset_entry
* e
, const void *p
) {
120 pa_assert(s
->compare_func
);
121 for (; e
; e
= e
->hash_next
)
122 if (s
->compare_func(e
->data
, p
) == 0)
128 static void extend_array(pa_idxset
*s
, uint32_t idx
) {
130 struct idxset_entry
** n
;
133 pa_assert(idx
>= s
->start_index
);
135 if (idx
< s
->start_index
+ s
->array_size
)
138 for (i
= 0; i
< s
->array_size
; i
++)
142 l
= idx
- s
->start_index
- i
+ 100;
143 n
= pa_xnew0(struct idxset_entry
*, l
);
145 for (j
= 0; j
< s
->array_size
-i
; j
++)
146 n
[j
] = s
->array
[i
+j
];
155 static struct idxset_entry
** array_index(pa_idxset
*s
, uint32_t idx
) {
158 if (idx
>= s
->start_index
+ s
->array_size
)
161 if (idx
< s
->start_index
)
164 return s
->array
+ idx
- s
->start_index
;
167 int pa_idxset_put(pa_idxset
*s
, void *p
, uint32_t *idx
) {
169 struct idxset_entry
*e
, **a
;
174 pa_assert(s
->hash_func
);
175 h
= s
->hash_func(p
) % s
->hash_table_size
;
177 pa_assert(s
->hash_table
);
178 if ((e
= hash_scan(s
, s
->hash_table
[h
], p
))) {
185 if (!(e
= pa_flist_pop(PA_STATIC_FLIST_GET(entries
))))
186 e
= pa_xnew(struct idxset_entry
, 1);
188 e
->index
= s
->index
++;
191 /* Insert into hash table */
192 e
->hash_next
= s
->hash_table
[h
];
194 if (s
->hash_table
[h
])
195 s
->hash_table
[h
]->hash_prev
= e
;
196 s
->hash_table
[h
] = e
;
198 /* Insert into array */
199 extend_array(s
, e
->index
);
200 a
= array_index(s
, e
->index
);
204 /* Insert into linked list */
205 e
->iterate_next
= NULL
;
206 e
->iterate_prev
= s
->iterate_list_tail
;
207 if (s
->iterate_list_tail
) {
208 pa_assert(s
->iterate_list_head
);
209 s
->iterate_list_tail
->iterate_next
= e
;
211 pa_assert(!s
->iterate_list_head
);
212 s
->iterate_list_head
= e
;
214 s
->iterate_list_tail
= e
;
217 pa_assert(s
->n_entries
>= 1);
225 void* pa_idxset_get_by_index(pa_idxset
*s
, uint32_t idx
) {
226 struct idxset_entry
**a
;
229 if (!(a
= array_index(s
, idx
)))
238 void* pa_idxset_get_by_data(pa_idxset
*s
, const void *p
, uint32_t *idx
) {
240 struct idxset_entry
*e
;
245 pa_assert(s
->hash_func
);
246 h
= s
->hash_func(p
) % s
->hash_table_size
;
248 pa_assert(s
->hash_table
);
249 if (!(e
= hash_scan(s
, s
->hash_table
[h
], p
)))
258 static void remove_entry(pa_idxset
*s
, struct idxset_entry
*e
) {
259 struct idxset_entry
**a
;
264 /* Remove from array */
265 a
= array_index(s
, e
->index
);
266 pa_assert(a
&& *a
&& *a
== e
);
269 /* Remove from linked list */
271 e
->iterate_next
->iterate_prev
= e
->iterate_prev
;
273 s
->iterate_list_tail
= e
->iterate_prev
;
276 e
->iterate_prev
->iterate_next
= e
->iterate_next
;
278 s
->iterate_list_head
= e
->iterate_next
;
280 /* Remove from hash table */
282 e
->hash_next
->hash_prev
= e
->hash_prev
;
285 e
->hash_prev
->hash_next
= e
->hash_next
;
287 s
->hash_table
[e
->hash_value
] = e
->hash_next
;
289 if (pa_flist_push(PA_STATIC_FLIST_GET(entries
), e
) < 0)
292 pa_assert(s
->n_entries
>= 1);
296 void* pa_idxset_remove_by_index(pa_idxset
*s
, uint32_t idx
) {
297 struct idxset_entry
**a
;
302 if (!(a
= array_index(s
, idx
)))
314 void* pa_idxset_remove_by_data(pa_idxset
*s
, const void *data
, uint32_t *idx
) {
315 struct idxset_entry
*e
;
321 pa_assert(s
->hash_func
);
322 h
= s
->hash_func(data
) % s
->hash_table_size
;
324 pa_assert(s
->hash_table
);
325 if (!(e
= hash_scan(s
, s
->hash_table
[h
], data
)))
337 void* pa_idxset_rrobin(pa_idxset
*s
, uint32_t *idx
) {
338 struct idxset_entry
**a
, *e
= NULL
;
343 if ((a
= array_index(s
, *idx
)) && *a
)
344 e
= (*a
)->iterate_next
;
347 e
= s
->iterate_list_head
;
356 void* pa_idxset_first(pa_idxset
*s
, uint32_t *idx
) {
359 if (!s
->iterate_list_head
)
363 *idx
= s
->iterate_list_head
->index
;
364 return s
->iterate_list_head
->data
;
367 void *pa_idxset_next(pa_idxset
*s
, uint32_t *idx
) {
368 struct idxset_entry
**a
, *e
= NULL
;
373 if ((a
= array_index(s
, *idx
)) && *a
)
374 e
= (*a
)->iterate_next
;
380 *idx
= PA_IDXSET_INVALID
;
385 int pa_idxset_foreach(pa_idxset
*s
, int (*func
)(void *p
, uint32_t idx
, int *del
, void*userdata
), void *userdata
) {
386 struct idxset_entry
*e
;
391 e
= s
->iterate_list_head
;
394 struct idxset_entry
*n
= e
->iterate_next
;
396 r
= func(e
->data
, e
->index
, &del
, userdata
);
410 unsigned pa_idxset_size(pa_idxset
*s
) {
416 int pa_idxset_isempty(pa_idxset
*s
) {
419 return s
->n_entries
== 0;