4 This file is part of PulseAudio.
6 Copyright 2004-2006 Lennart Poettering
7 Copyright 2006 Pierre Ossman <ossman@cendio.se> for Cendio AB
9 PulseAudio is free software; you can redistribute it and/or modify
10 it under the terms of the GNU Lesser General Public License as
11 published by the Free Software Foundation; either version 2.1 of the
12 License, or (at your option) any later version.
14 PulseAudio is distributed in the hope that it will be useful, but
15 WITHOUT ANY WARRANTY; without even the implied warranty of
16 MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the GNU
17 Lesser General Public License for more details.
19 You should have received a copy of the GNU Lesser General Public
20 License along with PulseAudio; if not, write to the Free Software
21 Foundation, Inc., 59 Temple Place, Suite 330, Boston, MA 02111-1307
34 #include <pulse/xmalloc.h>
38 typedef struct idxset_entry
{
43 struct idxset_entry
*hash_prev
, *hash_next
;
44 struct idxset_entry
* iterate_prev
, *iterate_next
;
48 pa_hash_func_t hash_func
;
49 pa_compare_func_t compare_func
;
51 unsigned hash_table_size
, n_entries
;
52 idxset_entry
**hash_table
, **array
, *iterate_list_head
, *iterate_list_tail
;
53 uint32_t index
, start_index
, array_size
;
56 unsigned pa_idxset_string_hash_func(const void *p
) {
61 hash
= 31 * hash
+ *c
;
66 int pa_idxset_string_compare_func(const void *a
, const void *b
) {
70 unsigned pa_idxset_trivial_hash_func(const void *p
) {
71 return PA_PTR_TO_UINT(p
);
74 int pa_idxset_trivial_compare_func(const void *a
, const void *b
) {
78 pa_idxset
* pa_idxset_new(pa_hash_func_t hash_func
, pa_compare_func_t compare_func
) {
81 s
= pa_xnew(pa_idxset
, 1);
82 s
->hash_func
= hash_func
? hash_func
: pa_idxset_trivial_hash_func
;
83 s
->compare_func
= compare_func
? compare_func
: pa_idxset_trivial_compare_func
;
84 s
->hash_table_size
= 127;
85 s
->hash_table
= pa_xnew0(idxset_entry
*, s
->hash_table_size
);
92 s
->iterate_list_head
= s
->iterate_list_tail
= NULL
;
97 void pa_idxset_free(pa_idxset
*s
, void (*free_func
) (void *p
, void *userdata
), void *userdata
) {
100 while (s
->iterate_list_head
) {
101 idxset_entry
*e
= s
->iterate_list_head
;
102 s
->iterate_list_head
= s
->iterate_list_head
->iterate_next
;
105 free_func(e
->data
, userdata
);
109 pa_xfree(s
->hash_table
);
114 static idxset_entry
* hash_scan(pa_idxset
*s
, idxset_entry
* e
, const void *p
) {
117 assert(s
->compare_func
);
118 for (; e
; e
= e
->hash_next
)
119 if (s
->compare_func(e
->data
, p
) == 0)
125 static void extend_array(pa_idxset
*s
, uint32_t idx
) {
128 assert(idx
>= s
->start_index
);
130 if (idx
< s
->start_index
+ s
->array_size
)
133 for (i
= 0; i
< s
->array_size
; i
++)
137 l
= idx
- s
->start_index
- i
+ 100;
138 n
= pa_xnew0(idxset_entry
*, l
);
140 for (j
= 0; j
< s
->array_size
-i
; j
++)
141 n
[j
] = s
->array
[i
+j
];
150 static idxset_entry
** array_index(pa_idxset
*s
, uint32_t idx
) {
151 if (idx
>= s
->start_index
+ s
->array_size
)
154 if (idx
< s
->start_index
)
157 return s
->array
+ idx
- s
->start_index
;
160 int pa_idxset_put(pa_idxset
*s
, void *p
, uint32_t *idx
) {
162 idxset_entry
*e
, **a
;
167 assert(s
->hash_func
);
168 h
= s
->hash_func(p
) % s
->hash_table_size
;
170 assert(s
->hash_table
);
171 if ((e
= hash_scan(s
, s
->hash_table
[h
], p
))) {
178 e
= pa_xmalloc(sizeof(idxset_entry
));
180 e
->index
= s
->index
++;
183 /* Insert into hash table */
184 e
->hash_next
= s
->hash_table
[h
];
186 if (s
->hash_table
[h
])
187 s
->hash_table
[h
]->hash_prev
= e
;
188 s
->hash_table
[h
] = e
;
190 /* Insert into array */
191 extend_array(s
, e
->index
);
192 a
= array_index(s
, e
->index
);
196 /* Insert into linked list */
197 e
->iterate_next
= NULL
;
198 e
->iterate_prev
= s
->iterate_list_tail
;
199 if (s
->iterate_list_tail
) {
200 assert(s
->iterate_list_head
);
201 s
->iterate_list_tail
->iterate_next
= e
;
203 assert(!s
->iterate_list_head
);
204 s
->iterate_list_head
= e
;
206 s
->iterate_list_tail
= e
;
209 assert(s
->n_entries
>= 1);
217 void* pa_idxset_get_by_index(pa_idxset
*s
, uint32_t idx
) {
221 if (!(a
= array_index(s
, idx
)))
230 void* pa_idxset_get_by_data(pa_idxset
*s
, const void *p
, uint32_t *idx
) {
235 assert(s
->hash_func
);
236 h
= s
->hash_func(p
) % s
->hash_table_size
;
238 assert(s
->hash_table
);
239 if (!(e
= hash_scan(s
, s
->hash_table
[h
], p
)))
248 static void remove_entry(pa_idxset
*s
, idxset_entry
*e
) {
252 /* Remove from array */
253 a
= array_index(s
, e
->index
);
254 assert(a
&& *a
&& *a
== e
);
257 /* Remove from linked list */
259 e
->iterate_next
->iterate_prev
= e
->iterate_prev
;
261 s
->iterate_list_tail
= e
->iterate_prev
;
264 e
->iterate_prev
->iterate_next
= e
->iterate_next
;
266 s
->iterate_list_head
= e
->iterate_next
;
268 /* Remove from hash table */
270 e
->hash_next
->hash_prev
= e
->hash_prev
;
273 e
->hash_prev
->hash_next
= e
->hash_next
;
275 s
->hash_table
[e
->hash_value
] = e
->hash_next
;
279 assert(s
->n_entries
>= 1);
283 void* pa_idxset_remove_by_index(pa_idxset
*s
, uint32_t idx
) {
289 if (!(a
= array_index(s
, idx
)))
301 void* pa_idxset_remove_by_data(pa_idxset
*s
, const void *data
, uint32_t *idx
) {
306 assert(s
->hash_func
);
307 h
= s
->hash_func(data
) % s
->hash_table_size
;
309 assert(s
->hash_table
);
310 if (!(e
= hash_scan(s
, s
->hash_table
[h
], data
)))
322 void* pa_idxset_rrobin(pa_idxset
*s
, uint32_t *idx
) {
323 idxset_entry
**a
, *e
= NULL
;
326 if ((a
= array_index(s
, *idx
)) && *a
)
327 e
= (*a
)->iterate_next
;
330 e
= s
->iterate_list_head
;
339 void* pa_idxset_first(pa_idxset
*s
, uint32_t *idx
) {
342 if (!s
->iterate_list_head
)
346 *idx
= s
->iterate_list_head
->index
;
347 return s
->iterate_list_head
->data
;
350 void *pa_idxset_next(pa_idxset
*s
, uint32_t *idx
) {
351 idxset_entry
**a
, *e
= NULL
;
355 if ((a
= array_index(s
, *idx
)) && *a
)
356 e
= (*a
)->iterate_next
;
362 *idx
= PA_IDXSET_INVALID
;
367 int pa_idxset_foreach(pa_idxset
*s
, int (*func
)(void *p
, uint32_t idx
, int *del
, void*userdata
), void *userdata
) {
371 e
= s
->iterate_list_head
;
374 idxset_entry
*n
= e
->iterate_next
;
376 r
= func(e
->data
, e
->index
, &del
, userdata
);
390 unsigned pa_idxset_size(pa_idxset
*s
) {
395 int pa_idxset_isempty(pa_idxset
*s
) {
397 return s
->n_entries
== 0;