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
38 struct idxset_entry
*hash_prev
, *hash_next
;
39 struct idxset_entry
* iterate_prev
, *iterate_next
;
43 unsigned (*hash_func
) (const void *p
);
44 int (*compare_func
)(const void *a
, const void *b
);
46 unsigned hash_table_size
, n_entries
;
47 struct idxset_entry
**hash_table
, **array
, *iterate_list_head
, *iterate_list_tail
;
48 uint32_t index
, start_index
, array_size
;
51 unsigned pa_idxset_string_hash_func(const void *p
) {
56 hash
= 31 * hash
+ *c
;
61 int pa_idxset_string_compare_func(const void *a
, const void *b
) {
65 unsigned pa_idxset_trivial_hash_func(const void *p
) {
69 int pa_idxset_trivial_compare_func(const void *a
, const void *b
) {
73 struct pa_idxset
* pa_idxset_new(unsigned (*hash_func
) (const void *p
), int (*compare_func
) (const void*a
, const void*b
)) {
76 s
= malloc(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
= malloc(sizeof(struct idxset_entry
*)*s
->hash_table_size
);
82 assert(s
->hash_table
);
83 memset(s
->hash_table
, 0, sizeof(struct idxset_entry
*)*s
->hash_table_size
);
90 s
->iterate_list_head
= s
->iterate_list_tail
= NULL
;
95 void pa_idxset_free(struct pa_idxset
*s
, void (*free_func
) (void *p
, void *userdata
), void *userdata
) {
99 while (s
->iterate_list_head
) {
100 struct idxset_entry
*e
= s
->iterate_list_head
;
101 s
->iterate_list_head
= s
->iterate_list_head
->iterate_next
;
104 free_func(e
->data
, userdata
);
114 static struct idxset_entry
* hash_scan(struct pa_idxset
*s
, struct idxset_entry
* e
, 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(struct pa_idxset
*s
, uint32_t index
) {
127 struct idxset_entry
** n
;
128 assert(index
>= s
->start_index
);
130 if (index
< s
->start_index
+ s
->array_size
)
133 for (i
= 0; i
< s
->array_size
; i
++)
137 l
= index
- s
->start_index
- i
+ 100;
138 n
= malloc(sizeof(struct hash_table_entry
*)*l
);
140 memset(n
, 0, sizeof(struct hash_table_entry
*)*l
);
142 for (j
= 0; j
< s
->array_size
-i
; j
++)
143 n
[j
] = s
->array
[i
+j
];
152 static struct idxset_entry
** array_index(struct pa_idxset
*s
, uint32_t index
) {
153 if (index
>= s
->start_index
+ s
->array_size
)
156 if (index
< s
->start_index
)
159 return s
->array
+ (index
- s
->start_index
);
162 int pa_idxset_put(struct pa_idxset
*s
, void *p
, uint32_t *index
) {
164 struct 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
= malloc(sizeof(struct idxset_entry
));
182 e
->index
= s
->index
++;
185 /* Insert into hash table */
186 e
->hash_next
= s
->hash_table
[h
];
188 if (s
->hash_table
[h
])
189 s
->hash_table
[h
]->hash_prev
= e
;
190 s
->hash_table
[h
] = e
;
192 /* Insert into array */
193 extend_array(s
, e
->index
);
194 a
= array_index(s
, e
->index
);
198 /* Insert into linked list */
199 e
->iterate_next
= NULL
;
200 e
->iterate_prev
= s
->iterate_list_tail
;
201 if (s
->iterate_list_tail
) {
202 assert(s
->iterate_list_head
);
203 s
->iterate_list_tail
->iterate_next
= e
;
205 assert(!s
->iterate_list_head
);
206 s
->iterate_list_head
= e
;
208 s
->iterate_list_tail
= e
;
211 assert(s
->n_entries
>= 1);
219 void* pa_idxset_get_by_index(struct pa_idxset
*s
, uint32_t index
) {
220 struct idxset_entry
**a
;
223 if (!(a
= array_index(s
, index
)))
232 void* pa_idxset_get_by_data(struct pa_idxset
*s
, void *p
, uint32_t *index
) {
234 struct idxset_entry
*e
;
237 assert(s
->hash_func
);
238 h
= s
->hash_func(p
) % s
->hash_table_size
;
240 assert(s
->hash_table
);
241 if (!(e
= hash_scan(s
, s
->hash_table
[h
], p
)))
250 static void remove_entry(struct pa_idxset
*s
, struct idxset_entry
*e
) {
251 struct idxset_entry
**a
;
254 /* Remove from array */
255 a
= array_index(s
, e
->index
);
256 assert(a
&& *a
&& *a
== e
);
259 /* Remove from linked list */
261 e
->iterate_next
->iterate_prev
= e
->iterate_prev
;
263 s
->iterate_list_tail
= e
->iterate_prev
;
266 e
->iterate_prev
->iterate_next
= e
->iterate_next
;
268 s
->iterate_list_head
= e
->iterate_next
;
270 /* Remove from hash table */
272 e
->hash_next
->hash_prev
= e
->hash_prev
;
275 e
->hash_prev
->hash_next
= e
->hash_next
;
277 s
->hash_table
[e
->hash_value
] = e
->hash_next
;
281 assert(s
->n_entries
>= 1);
285 void* pa_idxset_remove_by_index(struct pa_idxset
*s
, uint32_t index
) {
286 struct idxset_entry
**a
;
291 if (!(a
= array_index(s
, index
)))
300 void* pa_idxset_remove_by_data(struct pa_idxset
*s
, void *data
, uint32_t *index
) {
301 struct idxset_entry
*e
;
304 assert(s
->hash_func
);
305 h
= s
->hash_func(data
) % s
->hash_table_size
;
307 assert(s
->hash_table
);
308 if (!(e
= hash_scan(s
, s
->hash_table
[h
], data
)))
320 void* pa_idxset_rrobin(struct pa_idxset
*s
, uint32_t *index
) {
321 struct idxset_entry
**a
, *e
= NULL
;
324 if ((a
= array_index(s
, *index
)) && *a
)
325 e
= (*a
)->iterate_next
;
328 e
= s
->iterate_list_head
;
337 void* pa_idxset_first(struct pa_idxset
*s
, uint32_t *index
) {
340 if (!s
->iterate_list_head
)
344 *index
= s
->iterate_list_head
->index
;
345 return s
->iterate_list_head
->data
;
348 void *pa_idxset_next(struct pa_idxset
*s
, uint32_t *index
) {
349 struct idxset_entry
**a
, *e
= NULL
;
352 if ((a
= array_index(s
, *index
)) && *a
)
353 e
= (*a
)->iterate_next
;
359 *index
= PA_IDXSET_INVALID
;
365 int pa_idxset_foreach(struct pa_idxset
*s
, int (*func
)(void *p
, uint32_t index
, int *del
, void*userdata
), void *userdata
) {
366 struct idxset_entry
*e
;
369 e
= s
->iterate_list_head
;
372 struct idxset_entry
*n
= e
->iterate_next
;
374 r
= func(e
->data
, e
->index
, &del
, userdata
);
388 unsigned pa_idxset_ncontents(struct pa_idxset
*s
) {
393 int pa_idxset_isempty(struct pa_idxset
*s
) {
395 return s
->n_entries
== 0;