← Back to branch summary

~ubuntu-branches/ubuntu/jaunty/pulseaudio/jaunty-updates

« back to all changes in this revision

Viewing changes to src/pulsecore/idxset.c

  • Committer: Bazaar Package Importer
  • Author(s): Oliver Grawert
  • Date: 2006-11-12 20:00:18 UTC
  • Revision ID: james.westby@ubuntu.com-20061112200018-oji9njq7rr3te53k
Tags: upstream-0.9.5
Import upstream version 0.9.5

Show diffs side-by-side

added added

removed removed

Lines of Context:
src/pulsecore/idxset.c
 
1
/* $Id: idxset.c 1262 2006-08-18 19:42:14Z lennart $ */
 
2
 
 
3
/***
 
4
  This file is part of PulseAudio.
 
5
 
 
6
  PulseAudio is free software; you can redistribute it and/or modify
 
7
  it under the terms of the GNU Lesser General Public License as
 
8
  published by the Free Software Foundation; either version 2.1 of the
 
9
  License, or (at your option) any later version.
 
10
 
 
11
  PulseAudio 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
  Lesser General Public License for more details.
 
15
 
 
16
  You should have received a copy of the GNU Lesser General Public
 
17
  License along with PulseAudio; 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 <pulse/xmalloc.h>
 
32
 
 
33
#include "idxset.h"
 
34
 
 
35
typedef struct idxset_entry {
 
36
    void *data;
 
37
    uint32_t index;
 
38
    unsigned hash_value;
 
39
 
 
40
    struct idxset_entry *hash_prev, *hash_next;
 
41
    struct idxset_entry* iterate_prev, *iterate_next;
 
42
} idxset_entry;
 
43
 
 
44
struct pa_idxset {
 
45
    pa_hash_func_t hash_func;
 
46
    pa_compare_func_t compare_func;
 
47
    
 
48
    unsigned hash_table_size, n_entries;
 
49
    idxset_entry **hash_table, **array, *iterate_list_head, *iterate_list_tail;
 
50
    uint32_t index, start_index, array_size;
 
51
};
 
52
 
 
53
unsigned pa_idxset_string_hash_func(const void *p) {
 
54
    unsigned hash = 0;
 
55
    const char *c;
 
56
    
 
57
    for (c = p; *c; c++)
 
58
        hash = 31 * hash + *c;
 
59
 
 
60
    return hash;
 
61
}
 
62
 
 
63
int pa_idxset_string_compare_func(const void *a, const void *b) {
 
64
    return strcmp(a, b);
 
65
}
 
66
 
 
67
unsigned pa_idxset_trivial_hash_func(const void *p) {
 
68
    return PA_PTR_TO_UINT(p);
 
69
}
 
70
 
 
71
int pa_idxset_trivial_compare_func(const void *a, const void *b) {
 
72
    return a != b;
 
73
}
 
74
 
 
75
pa_idxset* pa_idxset_new(pa_hash_func_t hash_func, pa_compare_func_t compare_func) {
 
76
    pa_idxset *s;
 
77
 
 
78
    s = pa_xnew(pa_idxset, 1);
 
79
    s->hash_func = hash_func ? hash_func : pa_idxset_trivial_hash_func;
 
80
    s->compare_func = compare_func ? compare_func : pa_idxset_trivial_compare_func;
 
81
    s->hash_table_size = 127;
 
82
    s->hash_table = pa_xnew0(idxset_entry*, s->hash_table_size);
 
83
    s->array = NULL;
 
84
    s->array_size = 0;
 
85
    s->index = 0;
 
86
    s->start_index = 0;
 
87
    s->n_entries = 0;
 
88
 
 
89
    s->iterate_list_head = s->iterate_list_tail = NULL;
 
90
 
 
91
    return s;
 
92
}
 
93
 
 
94
void pa_idxset_free(pa_idxset *s, void (*free_func) (void *p, void *userdata), void *userdata) {
 
95
    assert(s);
 
96
 
 
97
    while (s->iterate_list_head) {
 
98
        idxset_entry *e = s->iterate_list_head;
 
99
        s->iterate_list_head = s->iterate_list_head->iterate_next;
 
100
        
 
101
        if (free_func)
 
102
            free_func(e->data, userdata);
 
103
        pa_xfree(e);
 
104
    }
 
105
 
 
106
    pa_xfree(s->hash_table);
 
107
    pa_xfree(s->array);
 
108
    pa_xfree(s);
 
109
}
 
110
 
 
111
static idxset_entry* hash_scan(pa_idxset *s, idxset_entry* e, const void *p) {
 
112
    assert(p);
 
113
 
 
114
    assert(s->compare_func);
 
115
    for (; e; e = e->hash_next)
 
116
        if (s->compare_func(e->data, p) == 0)
 
117
            return e;
 
118
 
 
119
    return NULL;
 
120
}
 
121
 
 
122
static void extend_array(pa_idxset *s, uint32_t idx) {
 
123
    uint32_t i, j, l;
 
124
    idxset_entry** n;
 
125
    assert(idx >= s->start_index);
 
126
 
 
127
    if (idx < s->start_index + s->array_size)
 
128
        return;
 
129
 
 
130
    for (i = 0; i < s->array_size; i++)
 
131
        if (s->array[i])
 
132
            break;
 
133
 
 
134
    l = idx - s->start_index - i + 100;
 
135
    n = pa_xnew0(idxset_entry*, l);
 
136
    
 
137
    for (j = 0; j < s->array_size-i; j++)
 
138
        n[j] = s->array[i+j];
 
139
 
 
140
    pa_xfree(s->array);
 
141
    
 
142
    s->array = n;
 
143
    s->array_size = l;
 
144
    s->start_index += i;
 
145
}
 
146
 
 
147
static idxset_entry** array_index(pa_idxset*s, uint32_t idx) {
 
148
    if (idx >= s->start_index + s->array_size)
 
149
        return NULL;
 
150
    
 
151
    if (idx < s->start_index)
 
152
        return NULL;
 
153
    
 
154
    return s->array + idx - s->start_index;
 
155
}
 
156
 
 
157
int pa_idxset_put(pa_idxset*s, void *p, uint32_t *idx) {
 
158
    unsigned h;
 
159
    idxset_entry *e, **a;
 
160
    
 
161
    assert(s);
 
162
    assert(p);
 
163
 
 
164
    assert(s->hash_func);
 
165
    h = s->hash_func(p) % s->hash_table_size;
 
166
 
 
167
    assert(s->hash_table);
 
168
    if ((e = hash_scan(s, s->hash_table[h], p))) {
 
169
        if (idx)
 
170
            *idx = e->index;
 
171
        
 
172
        return -1;
 
173
    }
 
174
 
 
175
    e = pa_xmalloc(sizeof(idxset_entry));
 
176
    e->data = p;
 
177
    e->index = s->index++;
 
178
    e->hash_value = h;
 
179
 
 
180
    /* Insert into hash table */
 
181
    e->hash_next = s->hash_table[h];
 
182
    e->hash_prev = NULL;
 
183
    if (s->hash_table[h])
 
184
        s->hash_table[h]->hash_prev = e;
 
185
    s->hash_table[h] = e;
 
186
 
 
187
    /* Insert into array */
 
188
    extend_array(s, e->index);
 
189
    a = array_index(s, e->index);
 
190
    assert(a && !*a);
 
191
    *a = e;
 
192
 
 
193
    /* Insert into linked list */
 
194
    e->iterate_next = NULL;
 
195
    e->iterate_prev = s->iterate_list_tail;
 
196
    if (s->iterate_list_tail) {
 
197
        assert(s->iterate_list_head);
 
198
        s->iterate_list_tail->iterate_next = e;
 
199
    } else {
 
200
        assert(!s->iterate_list_head);
 
201
        s->iterate_list_head = e;
 
202
    }
 
203
    s->iterate_list_tail = e;
 
204
    
 
205
    s->n_entries++;
 
206
    assert(s->n_entries >= 1);
 
207
    
 
208
    if (idx)
 
209
        *idx = e->index;
 
210
 
 
211
    return 0;
 
212
}
 
213
 
 
214
void* pa_idxset_get_by_index(pa_idxset*s, uint32_t idx) {
 
215
    idxset_entry **a;
 
216
    assert(s);
 
217
    
 
218
    if (!(a = array_index(s, idx)))
 
219
        return NULL;
 
220
 
 
221
    if (!*a)
 
222
        return NULL;
 
223
 
 
224
    return (*a)->data;
 
225
}
 
226
 
 
227
void* pa_idxset_get_by_data(pa_idxset*s, const void *p, uint32_t *idx) {
 
228
    unsigned h;
 
229
    idxset_entry *e;
 
230
    assert(s && p);
 
231
    
 
232
    assert(s->hash_func);
 
233
    h = s->hash_func(p) % s->hash_table_size;
 
234
 
 
235
    assert(s->hash_table);
 
236
    if (!(e = hash_scan(s, s->hash_table[h], p)))
 
237
        return NULL;
 
238
 
 
239
    if (idx)
 
240
        *idx = e->index;
 
241
 
 
242
    return e->data;
 
243
}
 
244
 
 
245
static void remove_entry(pa_idxset *s, idxset_entry *e) {
 
246
    idxset_entry **a;
 
247
    assert(s && e);
 
248
 
 
249
    /* Remove from array */
 
250
    a = array_index(s, e->index);
 
251
    assert(a && *a && *a == e);
 
252
    *a = NULL;
 
253
    
 
254
    /* Remove from linked list */
 
255
    if (e->iterate_next)
 
256
        e->iterate_next->iterate_prev = e->iterate_prev;
 
257
    else
 
258
        s->iterate_list_tail = e->iterate_prev;
 
259
    
 
260
    if (e->iterate_prev)
 
261
        e->iterate_prev->iterate_next = e->iterate_next;
 
262
    else
 
263
        s->iterate_list_head = e->iterate_next;
 
264
 
 
265
    /* Remove from hash table */
 
266
    if (e->hash_next)
 
267
        e->hash_next->hash_prev = e->hash_prev;
 
268
 
 
269
    if (e->hash_prev)
 
270
        e->hash_prev->hash_next = e->hash_next;
 
271
    else
 
272
        s->hash_table[e->hash_value] = e->hash_next;
 
273
 
 
274
    pa_xfree(e);
 
275
 
 
276
    assert(s->n_entries >= 1);
 
277
    s->n_entries--;
 
278
}
 
279
 
 
280
void* pa_idxset_remove_by_index(pa_idxset*s, uint32_t idx) {
 
281
    idxset_entry **a;
 
282
    void *data;
 
283
    
 
284
    assert(s);
 
285
 
 
286
    if (!(a = array_index(s, idx)))
 
287
        return NULL;
 
288
 
 
289
    if (!*a)
 
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(pa_idxset*s, const void *data, uint32_t *idx) {
 
299
    idxset_entry *e;
 
300
    unsigned h;
 
301
    void *r;
 
302
    
 
303
    assert(s->hash_func);
 
304
    h = s->hash_func(data) % s->hash_table_size;
 
305
 
 
306
    assert(s->hash_table);
 
307
    if (!(e = hash_scan(s, s->hash_table[h], data)))
 
308
        return NULL;
 
309
 
 
310
    r = e->data;
 
311
    if (idx)
 
312
        *idx = e->index;
 
313
 
 
314
    remove_entry(s, e);
 
315
 
 
316
    return r;
 
317
}
 
318
 
 
319
void* pa_idxset_rrobin(pa_idxset *s, uint32_t *idx) {
 
320
    idxset_entry **a, *e = NULL;
 
321
    assert(s && idx);
 
322
 
 
323
    if ((a = array_index(s, *idx)) && *a)
 
324
        e = (*a)->iterate_next;
 
325
 
 
326
    if (!e)
 
327
        e = s->iterate_list_head;
 
328
 
 
329
    if (!e)
 
330
        return NULL;
 
331
    
 
332
    *idx = e->index;
 
333
    return e->data;
 
334
}
 
335
 
 
336
void* pa_idxset_first(pa_idxset *s, uint32_t *idx) {
 
337
    assert(s);
 
338
 
 
339
    if (!s->iterate_list_head)
 
340
        return NULL;
 
341
 
 
342
    if (idx)
 
343
        *idx = s->iterate_list_head->index;
 
344
    return s->iterate_list_head->data;
 
345
}
 
346
 
 
347
void *pa_idxset_next(pa_idxset *s, uint32_t *idx) {
 
348
    idxset_entry **a, *e = NULL;
 
349
    assert(s);
 
350
    assert(idx);
 
351
 
 
352
    if ((a = array_index(s, *idx)) && *a)
 
353
        e = (*a)->iterate_next;
 
354
    
 
355
    if (e) {
 
356
        *idx = e->index;
 
357
        return e->data;
 
358
    } else {
 
359
        *idx = PA_IDXSET_INVALID;
 
360
        return NULL;
 
361
    }
 
362
}
 
363
 
 
364
int pa_idxset_foreach(pa_idxset*s, int (*func)(void *p, uint32_t idx, int *del, void*userdata), void *userdata) {
 
365
    idxset_entry *e;
 
366
    assert(s && func);
 
367
 
 
368
    e = s->iterate_list_head;
 
369
    while (e) {
 
370
        int del = 0, r;
 
371
        idxset_entry *n = e->iterate_next;
 
372
 
 
373
        r = func(e->data, e->index, &del, userdata);
 
374
 
 
375
        if (del)
 
376
            remove_entry(s, e);
 
377
 
 
378
        if (r < 0)
 
379
            return r;
 
380
 
 
381
        e = n;
 
382
    }
 
383
    
 
384
    return 0;
 
385
}
 
386
 
 
387
unsigned pa_idxset_size(pa_idxset*s) {
 
388
    assert(s);
 
389
    return s->n_entries;
 
390
}
 
391
 
 
392
int pa_idxset_isempty(pa_idxset *s) {
 
393
    assert(s);
 
394
    return s->n_entries == 0;
 
395
}
 
396