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) {
98 while (s->iterate_list_head) {
99 struct idxset_entry *e = s->iterate_list_head;
100 s->iterate_list_head = s->iterate_list_head->iterate_next;
103 free_func(e->data, userdata);
112 static struct idxset_entry* hash_scan(struct pa_idxset *s, struct idxset_entry* e, void *p) {
115 assert(s->compare_func);
116 for (; e; e = e->hash_next)
117 if (s->compare_func(e->data, p) == 0)
123 static void extend_array(struct pa_idxset *s, uint32_t index) {
125 struct idxset_entry** n;
126 assert(index >= s->start_index);
128 if (index < s->start_index + s->array_size)
131 for (i = 0; i < s->array_size; i++)
135 l = index - s->start_index - i + 100;
136 n = malloc(sizeof(struct hash_table_entry*)*l);
138 memset(n, 0, sizeof(struct hash_table_entry*)*l);
140 for (j = 0; j < s->array_size-i; j++)
141 n[j] = s->array[i+j];
150 static struct idxset_entry** array_index(struct pa_idxset*s, uint32_t index) {
151 if (index >= s->start_index + s->array_size)
154 if (index < s->start_index)
157 return s->array + (index - s->start_index);
160 int pa_idxset_put(struct pa_idxset*s, void *p, uint32_t *index) {
162 struct idxset_entry *e, **a;
165 assert(s->hash_func);
166 h = s->hash_func(p) % s->hash_table_size;
168 assert(s->hash_table);
169 if ((e = hash_scan(s, s->hash_table[h], p))) {
176 e = malloc(sizeof(struct 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(struct pa_idxset*s, uint32_t index) {
218 struct idxset_entry **a;
221 if (!(a = array_index(s, index)))
230 void* pa_idxset_get_by_data(struct pa_idxset*s, void *p, uint32_t *index) {
232 struct idxset_entry *e;
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(struct pa_idxset *s, struct idxset_entry *e) {
249 struct idxset_entry **a;
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(struct pa_idxset*s, uint32_t index) {
284 struct idxset_entry **a;
289 if (!(a = array_index(s, index)))
298 void* pa_idxset_remove_by_data(struct pa_idxset*s, void *data, uint32_t *index) {
299 struct idxset_entry *e;
302 assert(s->hash_func);
303 h = s->hash_func(data) % s->hash_table_size;
305 assert(s->hash_table);
306 if (!(e = hash_scan(s, s->hash_table[h], data)))
318 void* pa_idxset_rrobin(struct pa_idxset *s, uint32_t *index) {
319 struct idxset_entry **a, *e = NULL;
322 if ((a = array_index(s, *index)) && *a)
323 e = (*a)->iterate_next;
326 e = s->iterate_list_head;
335 void* pa_idxset_first(struct pa_idxset *s, uint32_t *index) {
338 if (!s->iterate_list_head)
342 *index = s->iterate_list_head->index;
343 return s->iterate_list_head->data;
346 void *pa_idxset_next(struct pa_idxset *s, uint32_t *index) {
347 struct idxset_entry **a, *e = NULL;
350 if ((a = array_index(s, *index)) && *a)
351 e = (*a)->iterate_next;
357 *index = PA_IDXSET_INVALID;
363 int pa_idxset_foreach(struct pa_idxset*s, int (*func)(void *p, uint32_t index, int *del, void*userdata), void *userdata) {
364 struct idxset_entry *e;
367 e = s->iterate_list_head;
370 struct idxset_entry *n = e->iterate_next;
372 r = func(e->data, e->index, &del, userdata);
386 unsigned pa_idxset_ncontents(struct pa_idxset*s) {
391 int pa_idxset_isempty(struct pa_idxset *s) {
393 return s->n_entries == 0;