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 General Public License as published
8 by the Free Software Foundation; either version 2 of the License,
9 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 General Public License for more details.
16 You should have received a copy of the GNU General Public License
17 along with polypaudio; if not, write to the Free Software
18 Foundation, Inc., 59 Temple Place, Suite 330, Boston, MA 02111-1307
39 struct idxset_entry
*hash_prev
, *hash_next
;
40 struct idxset_entry
* iterate_prev
, *iterate_next
;
44 unsigned (*hash_func
) (const void *p
);
45 int (*compare_func
)(const void *a
, const void *b
);
47 unsigned hash_table_size
, n_entries
;
48 struct idxset_entry
**hash_table
, **array
, *iterate_list_head
, *iterate_list_tail
;
49 uint32_t index
, start_index
, array_size
;
52 unsigned pa_idxset_string_hash_func(const void *p
) {
57 hash
= 31 * hash
+ *c
;
62 int pa_idxset_string_compare_func(const void *a
, const void *b
) {
66 unsigned pa_idxset_trivial_hash_func(const void *p
) {
70 int pa_idxset_trivial_compare_func(const void *a
, const void *b
) {
74 struct pa_idxset
* pa_idxset_new(unsigned (*hash_func
) (const void *p
), int (*compare_func
) (const void*a
, const void*b
)) {
77 s
= pa_xmalloc(sizeof(struct pa_idxset
));
78 s
->hash_func
= hash_func
? hash_func
: pa_idxset_trivial_hash_func
;
79 s
->compare_func
= compare_func
? compare_func
: pa_idxset_trivial_compare_func
;
80 s
->hash_table_size
= 1023;
81 s
->hash_table
= pa_xmalloc0(sizeof(struct idxset_entry
*)*s
->hash_table_size
);
88 s
->iterate_list_head
= s
->iterate_list_tail
= NULL
;
93 void pa_idxset_free(struct pa_idxset
*s
, void (*free_func
) (void *p
, void *userdata
), void *userdata
) {
96 while (s
->iterate_list_head
) {
97 struct idxset_entry
*e
= s
->iterate_list_head
;
98 s
->iterate_list_head
= s
->iterate_list_head
->iterate_next
;
101 free_func(e
->data
, userdata
);
105 pa_xfree(s
->hash_table
);
110 static struct idxset_entry
* hash_scan(struct pa_idxset
*s
, struct idxset_entry
* e
, const void *p
) {
113 assert(s
->compare_func
);
114 for (; e
; e
= e
->hash_next
)
115 if (s
->compare_func(e
->data
, p
) == 0)
121 static void extend_array(struct pa_idxset
*s
, uint32_t index
) {
123 struct idxset_entry
** n
;
124 assert(index
>= s
->start_index
);
126 if (index
< s
->start_index
+ s
->array_size
)
129 for (i
= 0; i
< s
->array_size
; i
++)
133 l
= index
- s
->start_index
- i
+ 100;
134 n
= pa_xmalloc0(sizeof(struct hash_table_entry
*)*l
);
136 for (j
= 0; j
< s
->array_size
-i
; j
++)
137 n
[j
] = s
->array
[i
+j
];
146 static struct idxset_entry
** array_index(struct pa_idxset
*s
, uint32_t index
) {
147 if (index
>= s
->start_index
+ s
->array_size
)
150 if (index
< s
->start_index
)
153 return s
->array
+ (index
- s
->start_index
);
156 int pa_idxset_put(struct pa_idxset
*s
, void *p
, uint32_t *index
) {
158 struct idxset_entry
*e
, **a
;
161 assert(s
->hash_func
);
162 h
= s
->hash_func(p
) % s
->hash_table_size
;
164 assert(s
->hash_table
);
165 if ((e
= hash_scan(s
, s
->hash_table
[h
], p
))) {
172 e
= pa_xmalloc(sizeof(struct idxset_entry
));
174 e
->index
= s
->index
++;
177 /* Insert into hash table */
178 e
->hash_next
= s
->hash_table
[h
];
180 if (s
->hash_table
[h
])
181 s
->hash_table
[h
]->hash_prev
= e
;
182 s
->hash_table
[h
] = e
;
184 /* Insert into array */
185 extend_array(s
, e
->index
);
186 a
= array_index(s
, e
->index
);
190 /* Insert into linked list */
191 e
->iterate_next
= NULL
;
192 e
->iterate_prev
= s
->iterate_list_tail
;
193 if (s
->iterate_list_tail
) {
194 assert(s
->iterate_list_head
);
195 s
->iterate_list_tail
->iterate_next
= e
;
197 assert(!s
->iterate_list_head
);
198 s
->iterate_list_head
= e
;
200 s
->iterate_list_tail
= e
;
203 assert(s
->n_entries
>= 1);
211 void* pa_idxset_get_by_index(struct pa_idxset
*s
, uint32_t index
) {
212 struct idxset_entry
**a
;
215 if (!(a
= array_index(s
, index
)))
224 void* pa_idxset_get_by_data(struct pa_idxset
*s
, const void *p
, uint32_t *index
) {
226 struct idxset_entry
*e
;
229 assert(s
->hash_func
);
230 h
= s
->hash_func(p
) % s
->hash_table_size
;
232 assert(s
->hash_table
);
233 if (!(e
= hash_scan(s
, s
->hash_table
[h
], p
)))
242 static void remove_entry(struct pa_idxset
*s
, struct idxset_entry
*e
) {
243 struct idxset_entry
**a
;
246 /* Remove from array */
247 a
= array_index(s
, e
->index
);
248 assert(a
&& *a
&& *a
== e
);
251 /* Remove from linked list */
253 e
->iterate_next
->iterate_prev
= e
->iterate_prev
;
255 s
->iterate_list_tail
= e
->iterate_prev
;
258 e
->iterate_prev
->iterate_next
= e
->iterate_next
;
260 s
->iterate_list_head
= e
->iterate_next
;
262 /* Remove from hash table */
264 e
->hash_next
->hash_prev
= e
->hash_prev
;
267 e
->hash_prev
->hash_next
= e
->hash_next
;
269 s
->hash_table
[e
->hash_value
] = e
->hash_next
;
273 assert(s
->n_entries
>= 1);
277 void* pa_idxset_remove_by_index(struct pa_idxset
*s
, uint32_t index
) {
278 struct idxset_entry
**a
;
283 if (!(a
= array_index(s
, index
)))
292 void* pa_idxset_remove_by_data(struct pa_idxset
*s
, const void *data
, uint32_t *index
) {
293 struct idxset_entry
*e
;
297 assert(s
->hash_func
);
298 h
= s
->hash_func(data
) % s
->hash_table_size
;
300 assert(s
->hash_table
);
301 if (!(e
= hash_scan(s
, s
->hash_table
[h
], data
)))
313 void* pa_idxset_rrobin(struct pa_idxset
*s
, uint32_t *index
) {
314 struct idxset_entry
**a
, *e
= NULL
;
317 if ((a
= array_index(s
, *index
)) && *a
)
318 e
= (*a
)->iterate_next
;
321 e
= s
->iterate_list_head
;
330 void* pa_idxset_first(struct pa_idxset
*s
, uint32_t *index
) {
333 if (!s
->iterate_list_head
)
337 *index
= s
->iterate_list_head
->index
;
338 return s
->iterate_list_head
->data
;
341 void *pa_idxset_next(struct pa_idxset
*s
, uint32_t *index
) {
342 struct idxset_entry
**a
, *e
= NULL
;
345 if ((a
= array_index(s
, *index
)) && *a
)
346 e
= (*a
)->iterate_next
;
352 *index
= PA_IDXSET_INVALID
;
358 int pa_idxset_foreach(struct pa_idxset
*s
, int (*func
)(void *p
, uint32_t index
, int *del
, void*userdata
), void *userdata
) {
359 struct idxset_entry
*e
;
362 e
= s
->iterate_list_head
;
365 struct idxset_entry
*n
= e
->iterate_next
;
367 r
= func(e
->data
, e
->index
, &del
, userdata
);
381 unsigned pa_idxset_ncontents(struct pa_idxset
*s
) {
386 int pa_idxset_isempty(struct pa_idxset
*s
) {
388 return s
->n_entries
== 0;