1/***
2  This file is part of PulseAudio.
3
4  Copyright 2004-2008 Lennart Poettering
5  Copyright 2006 Pierre Ossman <ossman@cendio.se> for Cendio AB
6
7  PulseAudio is free software; you can redistribute it and/or modify
8  it under the terms of the GNU Lesser General Public License as
9  published by the Free Software Foundation; either version 2.1 of the
10  License, or (at your option) any later version.
11
12  PulseAudio is distributed in the hope that it will be useful, but
13  WITHOUT ANY WARRANTY; without even the implied warranty of
14  MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the GNU
15  Lesser General Public License for more details.
16
17  You should have received a copy of the GNU Lesser General Public
18  License along with PulseAudio; if not, see <http://www.gnu.org/licenses/>.
19***/
20
21#ifdef HAVE_CONFIG_H
22#include <config.h>
23#endif
24
25#include <stdio.h>
26#include <stdlib.h>
27#include <string.h>
28
29#include <pulse/xmalloc.h>
30#include <pulsecore/flist.h>
31#include <pulsecore/macro.h>
32
33#include "idxset.h"
34
35#define NBUCKETS 127
36
37struct idxset_entry {
38    uint32_t idx;
39    void *data;
40
41    struct idxset_entry *data_next, *data_previous;
42    struct idxset_entry *index_next, *index_previous;
43    struct idxset_entry *iterate_next, *iterate_previous;
44};
45
46struct pa_idxset {
47    pa_hash_func_t hash_func;
48    pa_compare_func_t compare_func;
49
50    uint32_t current_index;
51
52    struct idxset_entry *iterate_list_head, *iterate_list_tail;
53    unsigned n_entries;
54};
55
56#define BY_DATA(i) ((struct idxset_entry**) ((uint8_t*) (i) + PA_ALIGN(sizeof(pa_idxset))))
57#define BY_INDEX(i) (BY_DATA(i) + NBUCKETS)
58
59PA_STATIC_FLIST_DECLARE(entries, 0, pa_xfree);
60
61unsigned pa_idxset_string_hash_func(const void *p) {
62    unsigned hash = 0;
63    const char *c;
64
65    for (c = p; *c; c++)
66        hash = 31 * hash + (unsigned) *c;
67
68    return hash;
69}
70
71int pa_idxset_string_compare_func(const void *a, const void *b) {
72    return strcmp(a, b);
73}
74
75unsigned pa_idxset_trivial_hash_func(const void *p) {
76    return PA_PTR_TO_UINT(p);
77}
78
79int pa_idxset_trivial_compare_func(const void *a, const void *b) {
80    return a < b ? -1 : (a > b ? 1 : 0);
81}
82
83pa_idxset* pa_idxset_new(pa_hash_func_t hash_func, pa_compare_func_t compare_func) {
84    pa_idxset *s;
85
86    s = pa_xmalloc0(PA_ALIGN(sizeof(pa_idxset)) + NBUCKETS*2*sizeof(struct idxset_entry*));
87
88    s->hash_func = hash_func ? hash_func : pa_idxset_trivial_hash_func;
89    s->compare_func = compare_func ? compare_func : pa_idxset_trivial_compare_func;
90
91    s->current_index = 0;
92    s->n_entries = 0;
93    s->iterate_list_head = s->iterate_list_tail = NULL;
94
95    return s;
96}
97
98static void remove_entry(pa_idxset *s, struct idxset_entry *e) {
99    pa_assert(s);
100    pa_assert(e);
101
102    /* Remove from iteration linked list */
103    if (e->iterate_next)
104        e->iterate_next->iterate_previous = e->iterate_previous;
105    else
106        s->iterate_list_tail = e->iterate_previous;
107
108    if (e->iterate_previous)
109        e->iterate_previous->iterate_next = e->iterate_next;
110    else
111        s->iterate_list_head = e->iterate_next;
112
113    /* Remove from data hash table */
114    if (e->data_next)
115        e->data_next->data_previous = e->data_previous;
116
117    if (e->data_previous)
118        e->data_previous->data_next = e->data_next;
119    else {
120        unsigned hash = s->hash_func(e->data) % NBUCKETS;
121        BY_DATA(s)[hash] = e->data_next;
122    }
123
124    /* Remove from index hash table */
125    if (e->index_next)
126        e->index_next->index_previous = e->index_previous;
127
128    if (e->index_previous)
129        e->index_previous->index_next = e->index_next;
130    else
131        BY_INDEX(s)[e->idx % NBUCKETS] = e->index_next;
132
133    if (pa_flist_push(PA_STATIC_FLIST_GET(entries), e) < 0)
134        pa_xfree(e);
135
136    pa_assert(s->n_entries >= 1);
137    s->n_entries--;
138}
139
140void pa_idxset_free(pa_idxset *s, pa_free_cb_t free_cb) {
141    pa_assert(s);
142
143    pa_idxset_remove_all(s, free_cb);
144    pa_xfree(s);
145}
146
147static struct idxset_entry* data_scan(pa_idxset *s, unsigned hash, const void *p) {
148    struct idxset_entry *e;
149    pa_assert(s);
150    pa_assert(hash < NBUCKETS);
151    pa_assert(p);
152
153    for (e = BY_DATA(s)[hash]; e; e = e->data_next)
154        if (s->compare_func(e->data, p) == 0)
155            return e;
156
157    return NULL;
158}
159
160static struct idxset_entry* index_scan(pa_idxset *s, unsigned hash, uint32_t idx) {
161    struct idxset_entry *e;
162    pa_assert(s);
163    pa_assert(hash < NBUCKETS);
164
165    for (e = BY_INDEX(s)[hash]; e; e = e->index_next)
166        if (e->idx == idx)
167            return e;
168
169    return NULL;
170}
171
172int pa_idxset_put(pa_idxset*s, void *p, uint32_t *idx) {
173    unsigned hash;
174    struct idxset_entry *e;
175
176    pa_assert(s);
177
178    hash = s->hash_func(p) % NBUCKETS;
179
180    if ((e = data_scan(s, hash, p))) {
181        if (idx)
182            *idx = e->idx;
183
184        return -1;
185    }
186
187    if (!(e = pa_flist_pop(PA_STATIC_FLIST_GET(entries))))
188        e = pa_xnew(struct idxset_entry, 1);
189
190    e->data = p;
191    e->idx = s->current_index++;
192
193    /* Insert into data hash table */
194    e->data_next = BY_DATA(s)[hash];
195    e->data_previous = NULL;
196    if (BY_DATA(s)[hash])
197        BY_DATA(s)[hash]->data_previous = e;
198    BY_DATA(s)[hash] = e;
199
200    hash = e->idx % NBUCKETS;
201
202    /* Insert into index hash table */
203    e->index_next = BY_INDEX(s)[hash];
204    e->index_previous = NULL;
205    if (BY_INDEX(s)[hash])
206        BY_INDEX(s)[hash]->index_previous = e;
207    BY_INDEX(s)[hash] = e;
208
209    /* Insert into iteration list */
210    e->iterate_previous = s->iterate_list_tail;
211    e->iterate_next = NULL;
212    if (s->iterate_list_tail) {
213        pa_assert(s->iterate_list_head);
214        s->iterate_list_tail->iterate_next = e;
215    } else {
216        pa_assert(!s->iterate_list_head);
217        s->iterate_list_head = e;
218    }
219    s->iterate_list_tail = e;
220
221    s->n_entries++;
222    pa_assert(s->n_entries >= 1);
223
224    if (idx)
225        *idx = e->idx;
226
227    return 0;
228}
229
230void* pa_idxset_get_by_index(pa_idxset*s, uint32_t idx) {
231    unsigned hash;
232    struct idxset_entry *e;
233
234    pa_assert(s);
235
236    hash = idx % NBUCKETS;
237
238    if (!(e = index_scan(s, hash, idx)))
239        return NULL;
240
241    return e->data;
242}
243
244void* pa_idxset_get_by_data(pa_idxset*s, const void *p, uint32_t *idx) {
245    unsigned hash;
246    struct idxset_entry *e;
247
248    pa_assert(s);
249
250    hash = s->hash_func(p) % NBUCKETS;
251
252    if (!(e = data_scan(s, hash, p)))
253        return NULL;
254
255    if (idx)
256        *idx = e->idx;
257
258    return e->data;
259}
260
261void* pa_idxset_remove_by_index(pa_idxset*s, uint32_t idx) {
262    struct idxset_entry *e;
263    unsigned hash;
264    void *data;
265
266    pa_assert(s);
267
268    hash = idx % NBUCKETS;
269
270    if (!(e = index_scan(s, hash, idx)))
271        return NULL;
272
273    data = e->data;
274    remove_entry(s, e);
275
276    return data;
277}
278
279void* pa_idxset_remove_by_data(pa_idxset*s, const void *data, uint32_t *idx) {
280    struct idxset_entry *e;
281    unsigned hash;
282    void *r;
283
284    pa_assert(s);
285
286    hash = s->hash_func(data) % NBUCKETS;
287
288    if (!(e = data_scan(s, hash, data)))
289        return NULL;
290
291    r = e->data;
292
293    if (idx)
294        *idx = e->idx;
295
296    remove_entry(s, e);
297
298    return r;
299}
300
301void pa_idxset_remove_all(pa_idxset *s, pa_free_cb_t free_cb) {
302    pa_assert(s);
303
304    while (s->iterate_list_head) {
305        void *data = s->iterate_list_head->data;
306
307        remove_entry(s, s->iterate_list_head);
308
309        if (free_cb)
310            free_cb(data);
311    }
312}
313
314void* pa_idxset_rrobin(pa_idxset *s, uint32_t *idx) {
315    unsigned hash;
316    struct idxset_entry *e;
317
318    pa_assert(s);
319    pa_assert(idx);
320
321    hash = *idx % NBUCKETS;
322
323    e = index_scan(s, hash, *idx);
324
325    if (e && e->iterate_next)
326        e = e->iterate_next;
327    else
328        e = s->iterate_list_head;
329
330    if (!e)
331        return NULL;
332
333    *idx = e->idx;
334    return e->data;
335}
336
337void *pa_idxset_iterate(pa_idxset *s, void **state, uint32_t *idx) {
338    struct idxset_entry *e;
339
340    pa_assert(s);
341    pa_assert(state);
342
343    if (*state == (void*) -1)
344        goto at_end;
345
346    if ((!*state && !s->iterate_list_head))
347        goto at_end;
348
349    e = *state ? *state : s->iterate_list_head;
350
351    if (e->iterate_next)
352        *state = e->iterate_next;
353    else
354        *state = (void*) -1;
355
356    if (idx)
357        *idx = e->idx;
358
359    return e->data;
360
361at_end:
362    *state = (void *) -1;
363
364    if (idx)
365        *idx = PA_IDXSET_INVALID;
366
367    return NULL;
368}
369
370void* pa_idxset_steal_first(pa_idxset *s, uint32_t *idx) {
371    void *data;
372
373    pa_assert(s);
374
375    if (!s->iterate_list_head)
376        return NULL;
377
378    data = s->iterate_list_head->data;
379
380    if (idx)
381        *idx = s->iterate_list_head->idx;
382
383    remove_entry(s, s->iterate_list_head);
384
385    return data;
386}
387
388void* pa_idxset_first(pa_idxset *s, uint32_t *idx) {
389    pa_assert(s);
390
391    if (!s->iterate_list_head) {
392        if (idx)
393            *idx = PA_IDXSET_INVALID;
394        return NULL;
395    }
396
397    if (idx)
398        *idx = s->iterate_list_head->idx;
399
400    return s->iterate_list_head->data;
401}
402
403void *pa_idxset_next(pa_idxset *s, uint32_t *idx) {
404    struct idxset_entry *e;
405    unsigned hash;
406
407    pa_assert(s);
408    pa_assert(idx);
409
410    if (*idx == PA_IDXSET_INVALID)
411        return NULL;
412
413    hash = *idx % NBUCKETS;
414
415    if ((e = index_scan(s, hash, *idx))) {
416
417        e = e->iterate_next;
418
419        if (e) {
420            *idx = e->idx;
421            return e->data;
422        } else {
423            *idx = PA_IDXSET_INVALID;
424            return NULL;
425        }
426
427    } else {
428
429        /* If the entry passed doesn't exist anymore we try to find
430         * the next following */
431
432        for ((*idx)++; *idx < s->current_index; (*idx)++) {
433
434            hash = *idx % NBUCKETS;
435
436            if ((e = index_scan(s, hash, *idx))) {
437                *idx = e->idx;
438                return e->data;
439            }
440        }
441
442        *idx = PA_IDXSET_INVALID;
443        return NULL;
444    }
445}
446
447unsigned pa_idxset_size(pa_idxset*s) {
448    pa_assert(s);
449
450    return s->n_entries;
451}
452
453bool pa_idxset_isempty(pa_idxset *s) {
454    pa_assert(s);
455
456    return s->n_entries == 0;
457}
458
459pa_idxset *pa_idxset_copy(pa_idxset *s, pa_copy_func_t copy_func) {
460    pa_idxset *copy;
461    struct idxset_entry *i;
462
463    pa_assert(s);
464
465    copy = pa_idxset_new(s->hash_func, s->compare_func);
466
467    for (i = s->iterate_list_head; i; i = i->iterate_next)
468        pa_idxset_put(copy, copy_func ? copy_func(i->data) : i->data, NULL);
469
470    return copy;
471}
472