0072e3cd365a21e901ea6b473130bee58a617272
[profile/ivi/pulseaudio-panda.git] / polyp / idxset.c
1 /* $Id$ */
2
3 /***
4   This file is part of polypaudio.
5  
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.
10  
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.
15  
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
19   USA.
20 ***/
21
22 #ifdef HAVE_CONFIG_H
23 #include <config.h>
24 #endif
25
26 #include <stdio.h>
27 #include <assert.h>
28 #include <stdlib.h>
29 #include <string.h>
30
31 #include "idxset.h"
32
33 struct idxset_entry {
34     void *data;
35     uint32_t index;
36     unsigned hash_value;
37
38     struct idxset_entry *hash_prev, *hash_next;
39     struct idxset_entry* iterate_prev, *iterate_next;
40 };
41
42 struct pa_idxset {
43     unsigned (*hash_func) (const void *p);
44     int (*compare_func)(const void *a, const void *b);
45     
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;
49 };
50
51 unsigned pa_idxset_string_hash_func(const void *p) {
52     unsigned hash = 0;
53     const char *c;
54     
55     for (c = p; *c; c++)
56         hash = 31 * hash + *c;
57
58     return hash;
59 }
60
61 int pa_idxset_string_compare_func(const void *a, const void *b) {
62     return strcmp(a, b);
63 }
64
65 unsigned pa_idxset_trivial_hash_func(const void *p) {
66     return (unsigned) p;
67 }
68
69 int pa_idxset_trivial_compare_func(const void *a, const void *b) {
70     return a != b;
71 }
72
73 struct pa_idxset* pa_idxset_new(unsigned (*hash_func) (const void *p), int (*compare_func) (const void*a, const void*b)) {
74     struct pa_idxset *s;
75
76     s = malloc(sizeof(struct pa_idxset));
77     assert(s);
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);
84     s->array = NULL;
85     s->array_size = 0;
86     s->index = 0;
87     s->start_index = 0;
88     s->n_entries = 0;
89
90     s->iterate_list_head = s->iterate_list_tail = NULL;
91
92     return s;
93 }
94
95 void pa_idxset_free(struct pa_idxset *s, void (*free_func) (void *p, void *userdata), void *userdata) {
96     assert(s);
97
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;
101         
102         if (free_func)
103             free_func(e->data, userdata);
104         free(e);
105     }
106
107     free(s->hash_table);
108     free(s->array);
109     free(s);
110 }
111
112 static struct idxset_entry* hash_scan(struct pa_idxset *s, struct idxset_entry* e, void *p) {
113     assert(p);
114
115     assert(s->compare_func);
116     for (; e; e = e->hash_next)
117         if (s->compare_func(e->data, p) == 0)
118             return e;
119
120     return NULL;
121 }
122
123 static void extend_array(struct pa_idxset *s, uint32_t index) {
124     uint32_t i, j, l;
125     struct idxset_entry** n;
126     assert(index >= s->start_index);
127
128     if (index < s->start_index + s->array_size)
129         return;
130
131     for (i = 0; i < s->array_size; i++)
132         if (s->array[i])
133             break;
134
135     l = index - s->start_index - i + 100;
136     n = malloc(sizeof(struct hash_table_entry*)*l);
137     assert(n);
138     memset(n, 0, sizeof(struct hash_table_entry*)*l);
139     
140     for (j = 0; j < s->array_size-i; j++)
141         n[j] = s->array[i+j];
142
143     free(s->array);
144     
145     s->array = n;
146     s->array_size = l;
147     s->start_index += i;
148 }
149
150 static struct idxset_entry** array_index(struct pa_idxset*s, uint32_t index) {
151     if (index >= s->start_index + s->array_size)
152         return NULL;
153     
154     if (index < s->start_index)
155         return NULL;
156     
157     return s->array + (index - s->start_index);
158 }
159
160 int pa_idxset_put(struct pa_idxset*s, void *p, uint32_t *index) {
161     unsigned h;
162     struct idxset_entry *e, **a;
163     assert(s && p);
164
165     assert(s->hash_func);
166     h = s->hash_func(p) % s->hash_table_size;
167
168     assert(s->hash_table);
169     if ((e = hash_scan(s, s->hash_table[h], p))) {
170         if (index)
171             *index = e->index;
172         
173         return -1;
174     }
175
176     e = malloc(sizeof(struct idxset_entry));
177     assert(e);
178
179     e->data = p;
180     e->index = s->index++;
181     e->hash_value = h;
182
183     /* Insert into hash table */
184     e->hash_next = s->hash_table[h];
185     e->hash_prev = NULL;
186     if (s->hash_table[h])
187         s->hash_table[h]->hash_prev = e;
188     s->hash_table[h] = e;
189
190     /* Insert into array */
191     extend_array(s, e->index);
192     a = array_index(s, e->index);
193     assert(a && !*a);
194     *a = e;
195
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;
202     } else {
203         assert(!s->iterate_list_head);
204         s->iterate_list_head = e;
205     }
206     s->iterate_list_tail = e;
207     
208     s->n_entries++;
209     assert(s->n_entries >= 1);
210     
211     if (index)
212         *index = e->index;
213
214     return 0;
215 }
216
217 void* pa_idxset_get_by_index(struct pa_idxset*s, uint32_t index) {
218     struct idxset_entry **a;
219     assert(s);
220     
221     if (!(a = array_index(s, index)))
222         return NULL;
223
224     if (!*a)
225         return NULL;
226
227     return (*a)->data;
228 }
229
230 void* pa_idxset_get_by_data(struct pa_idxset*s, void *p, uint32_t *index) {
231     unsigned h;
232     struct idxset_entry *e;
233     assert(s && p);
234     
235     assert(s->hash_func);
236     h = s->hash_func(p) % s->hash_table_size;
237
238     assert(s->hash_table);
239     if (!(e = hash_scan(s, s->hash_table[h], p)))
240         return NULL;
241
242     if (index)
243         *index = e->index;
244
245     return e->data;
246 }
247
248 static void remove_entry(struct pa_idxset *s, struct idxset_entry *e) {
249     struct idxset_entry **a;
250     assert(s && e);
251
252     /* Remove from array */
253     a = array_index(s, e->index);
254     assert(a && *a && *a == e);
255     *a = NULL;
256     
257     /* Remove from linked list */
258     if (e->iterate_next)
259         e->iterate_next->iterate_prev = e->iterate_prev;
260     else
261         s->iterate_list_tail = e->iterate_prev;
262     
263     if (e->iterate_prev)
264         e->iterate_prev->iterate_next = e->iterate_next;
265     else
266         s->iterate_list_head = e->iterate_next;
267
268     /* Remove from hash table */
269     if (e->hash_next)
270         e->hash_next->hash_prev = e->hash_prev;
271
272     if (e->hash_prev)
273         e->hash_prev->hash_next = e->hash_next;
274     else
275         s->hash_table[e->hash_value] = e->hash_next;
276
277     free(e);
278
279     assert(s->n_entries >= 1);
280     s->n_entries--;
281 }
282
283 void* pa_idxset_remove_by_index(struct pa_idxset*s, uint32_t index) {
284     struct idxset_entry **a;
285     void *data;
286     
287     assert(s);
288
289     if (!(a = array_index(s, index)))
290         return NULL;
291
292     data = (*a)->data;
293     remove_entry(s, *a);
294     
295     return data; 
296 }
297
298 void* pa_idxset_remove_by_data(struct pa_idxset*s, void *data, uint32_t *index) {
299     struct idxset_entry *e;
300     unsigned h;
301     
302     assert(s->hash_func);
303     h = s->hash_func(data) % s->hash_table_size;
304
305     assert(s->hash_table);
306     if (!(e = hash_scan(s, s->hash_table[h], data)))
307         return NULL;
308
309     data = e->data;
310     if (index)
311         *index = e->index;
312
313     remove_entry(s, e);
314
315     return data;
316 }
317
318 void* pa_idxset_rrobin(struct pa_idxset *s, uint32_t *index) {
319     struct idxset_entry **a, *e = NULL;
320     assert(s && index);
321
322     if ((a = array_index(s, *index)) && *a)
323         e = (*a)->iterate_next;
324
325     if (!e)
326         e = s->iterate_list_head;
327
328     if (!e)
329         return NULL;
330     
331     *index = e->index;
332     return e->data;
333 }
334
335 void* pa_idxset_first(struct pa_idxset *s, uint32_t *index) {
336     assert(s);
337
338     if (!s->iterate_list_head)
339         return NULL;
340
341     if (index)
342         *index = s->iterate_list_head->index;
343     return s->iterate_list_head->data;
344 }
345
346 void *pa_idxset_next(struct pa_idxset *s, uint32_t *index) {
347     struct idxset_entry **a, *e = NULL;
348     assert(s && index);
349
350     if ((a = array_index(s, *index)) && *a)
351         e = (*a)->iterate_next;
352     
353     if (e) {
354         *index = e->index;
355         return e->data;
356     } else {
357         *index = PA_IDXSET_INVALID;
358         return NULL;
359     }
360 }
361
362
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;
365     assert(s && func);
366
367     e = s->iterate_list_head;
368     while (e) {
369         int del = 0, r;
370         struct idxset_entry *n = e->iterate_next;
371
372         r = func(e->data, e->index, &del, userdata);
373
374         if (del)
375             remove_entry(s, e);
376
377         if (r < 0)
378             return r;
379
380         e = n;
381     }
382     
383     return 0;
384 }
385
386 unsigned pa_idxset_ncontents(struct pa_idxset*s) {
387     assert(s);
388     return s->n_entries;
389 }
390
391 int pa_idxset_isempty(struct pa_idxset *s) {
392     assert(s);
393     return s->n_entries == 0;
394 }
395