4 This file is part of polypaudio.
6 polypaudio is free software; you can redistribute it and/or modify
7 it under the terms of the GNU Lesser General Public License as
8 published by the Free Software Foundation; either version 2.1 of the
9 License, or (at your option) any later version.
11 polypaudio is distributed in the hope that it will be useful, but
12 WITHOUT ANY WARRANTY; without even the implied warranty of
13 MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the GNU
14 Lesser General Public License for more details.
16 You should have received a copy of the GNU Lesser General Public
17 License along with polypaudio; if not, write to the Free Software
18 Foundation, Inc., 59 Temple Place, Suite 330, Boston, MA 02111-1307
31 #include <polyp/xmalloc.h>
35 typedef struct idxset_entry
{
40 struct idxset_entry
*hash_prev
, *hash_next
;
41 struct idxset_entry
* iterate_prev
, *iterate_next
;
45 unsigned (*hash_func
) (const void *p
);
46 int (*compare_func
)(const void *a
, const void *b
);
48 unsigned hash_table_size
, n_entries
;
49 idxset_entry
**hash_table
, **array
, *iterate_list_head
, *iterate_list_tail
;
50 uint32_t index
, start_index
, array_size
;
53 unsigned pa_idxset_string_hash_func(const void *p
) {
58 hash
= 31 * hash
+ *c
;
63 int pa_idxset_string_compare_func(const void *a
, const void *b
) {
67 unsigned pa_idxset_trivial_hash_func(const void *p
) {
68 return (unsigned) (long) p
;
71 int pa_idxset_trivial_compare_func(const void *a
, const void *b
) {
75 pa_idxset
* pa_idxset_new(unsigned (*hash_func
) (const void *p
), int (*compare_func
) (const void*a
, const void*b
)) {
78 s
= pa_xnew(pa_idxset
, 1);
79 s
->hash_func
= hash_func
? hash_func
: pa_idxset_trivial_hash_func
;
80 s
->compare_func
= compare_func
? compare_func
: pa_idxset_trivial_compare_func
;
81 s
->hash_table_size
= 1023;
82 s
->hash_table
= pa_xmalloc0(sizeof(idxset_entry
*)*s
->hash_table_size
);
89 s
->iterate_list_head
= s
->iterate_list_tail
= NULL
;
94 void pa_idxset_free(pa_idxset
*s
, void (*free_func
) (void *p
, void *userdata
), void *userdata
) {
97 while (s
->iterate_list_head
) {
98 idxset_entry
*e
= s
->iterate_list_head
;
99 s
->iterate_list_head
= s
->iterate_list_head
->iterate_next
;
102 free_func(e
->data
, userdata
);
106 pa_xfree(s
->hash_table
);
111 static idxset_entry
* hash_scan(pa_idxset
*s
, idxset_entry
* e
, const void *p
) {
114 assert(s
->compare_func
);
115 for (; e
; e
= e
->hash_next
)
116 if (s
->compare_func(e
->data
, p
) == 0)
122 static void extend_array(pa_idxset
*s
, uint32_t idx
) {
125 assert(idx
>= s
->start_index
);
127 if (idx
< s
->start_index
+ s
->array_size
)
130 for (i
= 0; i
< s
->array_size
; i
++)
134 l
= idx
- s
->start_index
- i
+ 100;
135 n
= pa_xnew0(idxset_entry
*, l
);
137 for (j
= 0; j
< s
->array_size
-i
; j
++)
138 n
[j
] = s
->array
[i
+j
];
147 static idxset_entry
** array_index(pa_idxset
*s
, uint32_t idx
) {
148 if (idx
>= s
->start_index
+ s
->array_size
)
151 if (idx
< s
->start_index
)
154 return s
->array
+ (idx
- s
->start_index
);
157 int pa_idxset_put(pa_idxset
*s
, void *p
, uint32_t *idx
) {
159 idxset_entry
*e
, **a
;
162 assert(s
->hash_func
);
163 h
= s
->hash_func(p
) % s
->hash_table_size
;
165 assert(s
->hash_table
);
166 if ((e
= hash_scan(s
, s
->hash_table
[h
], p
))) {
173 e
= pa_xmalloc(sizeof(idxset_entry
));
175 e
->index
= s
->index
++;
178 /* Insert into hash table */
179 e
->hash_next
= s
->hash_table
[h
];
181 if (s
->hash_table
[h
])
182 s
->hash_table
[h
]->hash_prev
= e
;
183 s
->hash_table
[h
] = e
;
185 /* Insert into array */
186 extend_array(s
, e
->index
);
187 a
= array_index(s
, e
->index
);
191 /* Insert into linked list */
192 e
->iterate_next
= NULL
;
193 e
->iterate_prev
= s
->iterate_list_tail
;
194 if (s
->iterate_list_tail
) {
195 assert(s
->iterate_list_head
);
196 s
->iterate_list_tail
->iterate_next
= e
;
198 assert(!s
->iterate_list_head
);
199 s
->iterate_list_head
= e
;
201 s
->iterate_list_tail
= e
;
204 assert(s
->n_entries
>= 1);
212 void* pa_idxset_get_by_index(pa_idxset
*s
, uint32_t idx
) {
216 if (!(a
= array_index(s
, idx
)))
225 void* pa_idxset_get_by_data(pa_idxset
*s
, const void *p
, uint32_t *idx
) {
230 assert(s
->hash_func
);
231 h
= s
->hash_func(p
) % s
->hash_table_size
;
233 assert(s
->hash_table
);
234 if (!(e
= hash_scan(s
, s
->hash_table
[h
], p
)))
243 static void remove_entry(pa_idxset
*s
, idxset_entry
*e
) {
247 /* Remove from array */
248 a
= array_index(s
, e
->index
);
249 assert(a
&& *a
&& *a
== e
);
252 /* Remove from linked list */
254 e
->iterate_next
->iterate_prev
= e
->iterate_prev
;
256 s
->iterate_list_tail
= e
->iterate_prev
;
259 e
->iterate_prev
->iterate_next
= e
->iterate_next
;
261 s
->iterate_list_head
= e
->iterate_next
;
263 /* Remove from hash table */
265 e
->hash_next
->hash_prev
= e
->hash_prev
;
268 e
->hash_prev
->hash_next
= e
->hash_next
;
270 s
->hash_table
[e
->hash_value
] = e
->hash_next
;
274 assert(s
->n_entries
>= 1);
278 void* pa_idxset_remove_by_index(pa_idxset
*s
, uint32_t idx
) {
284 if (!(a
= array_index(s
, idx
)))
293 void* pa_idxset_remove_by_data(pa_idxset
*s
, const void *data
, uint32_t *idx
) {
298 assert(s
->hash_func
);
299 h
= s
->hash_func(data
) % s
->hash_table_size
;
301 assert(s
->hash_table
);
302 if (!(e
= hash_scan(s
, s
->hash_table
[h
], data
)))
314 void* pa_idxset_rrobin(pa_idxset
*s
, uint32_t *idx
) {
315 idxset_entry
**a
, *e
= NULL
;
318 if ((a
= array_index(s
, *idx
)) && *a
)
319 e
= (*a
)->iterate_next
;
322 e
= s
->iterate_list_head
;
331 void* pa_idxset_first(pa_idxset
*s
, uint32_t *idx
) {
334 if (!s
->iterate_list_head
)
338 *idx
= s
->iterate_list_head
->index
;
339 return s
->iterate_list_head
->data
;
342 void *pa_idxset_next(pa_idxset
*s
, uint32_t *idx
) {
343 idxset_entry
**a
, *e
= NULL
;
346 if ((a
= array_index(s
, *idx
)) && *a
)
347 e
= (*a
)->iterate_next
;
353 *idx
= PA_IDXSET_INVALID
;
359 int pa_idxset_foreach(pa_idxset
*s
, int (*func
)(void *p
, uint32_t idx
, int *del
, void*userdata
), void *userdata
) {
363 e
= s
->iterate_list_head
;
366 idxset_entry
*n
= e
->iterate_next
;
368 r
= func(e
->data
, e
->index
, &del
, userdata
);
382 unsigned pa_idxset_size(pa_idxset
*s
) {
387 int pa_idxset_isempty(pa_idxset
*s
) {
389 return s
->n_entries
== 0;