code.delx.au - pulseaudio/blob - src/pulsecore/idxset.c

   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, write to the Free Software
  19   Foundation, Inc., 59 Temple Place, Suite 330, Boston, MA 02111-1307
  20   USA.
  21 ***/
  22
  23 #ifdef HAVE_CONFIG_H
  24 #include <config.h>
  25 #endif
  26
  27 #include <stdio.h>
  28 #include <stdlib.h>
  29 #include <string.h>
  30
  31 #include <pulse/xmalloc.h>
  32 #include <pulsecore/log.h>
  33 #include <pulsecore/flist.h>
  34 #include <pulsecore/macro.h>
  35
  36 #include "idxset.h"
  37
  38 #define NBUCKETS 127
  39
  40 struct idxset_entry {
  41     uint32_t idx;
  42     void *data;
  43
  44     struct idxset_entry *data_next, *data_previous;
  45     struct idxset_entry *index_next, *index_previous;
  46     struct idxset_entry *iterate_next, *iterate_previous;
  47 };
  48
  49 struct pa_idxset {
  50     pa_hash_func_t hash_func;
  51     pa_compare_func_t compare_func;
  52
  53     uint32_t current_index;
  54
  55     struct idxset_entry *iterate_list_head, *iterate_list_tail;
  56     unsigned n_entries;
  57 };
  58
  59 #define BY_DATA(i) ((struct idxset_entry**) ((uint8_t*) (i) + PA_ALIGN(sizeof(pa_idxset))))
  60 #define BY_INDEX(i) (BY_DATA(i) + NBUCKETS)
  61
  62 PA_STATIC_FLIST_DECLARE(entries, 0, pa_xfree);
  63
  64 unsigned pa_idxset_string_hash_func(const void *p) {
  65     unsigned hash = 0;
  66     const char *c;
  67
  68     for (c = p; *c; c++)
  69         hash = 31 * hash + (unsigned) *c;
  70
  71     return hash;
  72 }
  73
  74 int pa_idxset_string_compare_func(const void *a, const void *b) {
  75     return strcmp(a, b);
  76 }
  77
  78 unsigned pa_idxset_trivial_hash_func(const void *p) {
  79     return PA_PTR_TO_UINT(p);
  80 }
  81
  82 int pa_idxset_trivial_compare_func(const void *a, const void *b) {
  83     return a != b;
  84 }
  85
  86 pa_idxset* pa_idxset_new(pa_hash_func_t hash_func, pa_compare_func_t compare_func) {
  87     pa_idxset *s;
  88
  89     s = pa_xmalloc0(PA_ALIGN(sizeof(pa_idxset)) + NBUCKETS*2*sizeof(struct idxset_entry*));
  90
  91     s->hash_func = hash_func ? hash_func : pa_idxset_trivial_hash_func;
  92     s->compare_func = compare_func ? compare_func : pa_idxset_trivial_compare_func;
  93
  94     s->current_index = 0;
  95     s->n_entries = 0;
  96     s->iterate_list_head = s->iterate_list_tail = NULL;
  97
  98     return s;
  99 }
 100
 101 static void remove_entry(pa_idxset *s, struct idxset_entry *e) {
 102     pa_assert(s);
 103     pa_assert(e);
 104
 105     /* Remove from iteration linked list */
 106     if (e->iterate_next)
 107         e->iterate_next->iterate_previous = e->iterate_previous;
 108     else
 109         s->iterate_list_tail = e->iterate_previous;
 110
 111     if (e->iterate_previous)
 112         e->iterate_previous->iterate_next = e->iterate_next;
 113     else
 114         s->iterate_list_head = e->iterate_next;
 115
 116     /* Remove from data hash table */
 117     if (e->data_next)
 118         e->data_next->data_previous = e->data_previous;
 119
 120     if (e->data_previous)
 121         e->data_previous->data_next = e->data_next;
 122     else {
 123         unsigned hash = s->hash_func(e->data) % NBUCKETS;
 124         BY_DATA(s)[hash] = e->data_next;
 125     }
 126
 127     /* Remove from index hash table */
 128     if (e->index_next)
 129         e->index_next->index_previous = e->index_previous;
 130
 131     if (e->index_previous)
 132         e->index_previous->index_next = e->index_next;
 133     else
 134         BY_INDEX(s)[e->idx % NBUCKETS] = e->index_next;
 135
 136     if (pa_flist_push(PA_STATIC_FLIST_GET(entries), e) < 0)
 137         pa_xfree(e);
 138
 139     pa_assert(s->n_entries >= 1);
 140     s->n_entries--;
 141 }
 142
 143 void pa_idxset_free(pa_idxset *s, pa_free2_cb_t free_cb, void *userdata) {
 144     pa_assert(s);
 145
 146     while (s->iterate_list_head) {
 147         void *data = s->iterate_list_head->data;
 148
 149         remove_entry(s, s->iterate_list_head);
 150
 151         if (free_cb)
 152             free_cb(data, userdata);
 153     }
 154
 155     pa_xfree(s);
 156 }
 157
 158 static struct idxset_entry* data_scan(pa_idxset *s, unsigned hash, const void *p) {
 159     struct idxset_entry *e;
 160     pa_assert(s);
 161     pa_assert(hash < NBUCKETS);
 162     pa_assert(p);
 163
 164     for (e = BY_DATA(s)[hash]; e; e = e->data_next)
 165         if (s->compare_func(e->data, p) == 0)
 166             return e;
 167
 168     return NULL;
 169 }
 170
 171 static struct idxset_entry* index_scan(pa_idxset *s, unsigned hash, uint32_t idx) {
 172     struct idxset_entry *e;
 173     pa_assert(s);
 174     pa_assert(hash < NBUCKETS);
 175
 176     for (e = BY_INDEX(s)[hash]; e; e = e->index_next)
 177         if (e->idx == idx)
 178             return e;
 179
 180     return NULL;
 181 }
 182
 183 int pa_idxset_put(pa_idxset*s, void *p, uint32_t *idx) {
 184     unsigned hash;
 185     struct idxset_entry *e;
 186
 187     pa_assert(s);
 188
 189     hash = s->hash_func(p) % NBUCKETS;
 190
 191     if ((e = data_scan(s, hash, p))) {
 192         if (idx)
 193             *idx = e->idx;
 194
 195         return -1;
 196     }
 197
 198     if (!(e = pa_flist_pop(PA_STATIC_FLIST_GET(entries))))
 199         e = pa_xnew(struct idxset_entry, 1);
 200
 201     e->data = p;
 202     e->idx = s->current_index++;
 203
 204     /* Insert into data hash table */
 205     e->data_next = BY_DATA(s)[hash];
 206     e->data_previous = NULL;
 207     if (BY_DATA(s)[hash])
 208         BY_DATA(s)[hash]->data_previous = e;
 209     BY_DATA(s)[hash] = e;
 210
 211     hash = e->idx % NBUCKETS;
 212
 213     /* Insert into index hash table */
 214     e->index_next = BY_INDEX(s)[hash];
 215     e->index_previous = NULL;
 216     if (BY_INDEX(s)[hash])
 217         BY_INDEX(s)[hash]->index_previous = e;
 218     BY_INDEX(s)[hash] = e;
 219
 220     /* Insert into iteration list */
 221     e->iterate_previous = s->iterate_list_tail;
 222     e->iterate_next = NULL;
 223     if (s->iterate_list_tail) {
 224         pa_assert(s->iterate_list_head);
 225         s->iterate_list_tail->iterate_next = e;
 226     } else {
 227         pa_assert(!s->iterate_list_head);
 228         s->iterate_list_head = e;
 229     }
 230     s->iterate_list_tail = e;
 231
 232     s->n_entries++;
 233     pa_assert(s->n_entries >= 1);
 234
 235     if (idx)
 236         *idx = e->idx;
 237
 238     return 0;
 239 }
 240
 241 void* pa_idxset_get_by_index(pa_idxset*s, uint32_t idx) {
 242     unsigned hash;
 243     struct idxset_entry *e;
 244
 245     pa_assert(s);
 246
 247     hash = idx % NBUCKETS;
 248
 249     if (!(e = index_scan(s, hash, idx)))
 250         return NULL;
 251
 252     return e->data;
 253 }
 254
 255 void* pa_idxset_get_by_data(pa_idxset*s, const void *p, uint32_t *idx) {
 256     unsigned hash;
 257     struct idxset_entry *e;
 258
 259     pa_assert(s);
 260
 261     hash = s->hash_func(p) % NBUCKETS;
 262
 263     if (!(e = data_scan(s, hash, p)))
 264         return NULL;
 265
 266     if (idx)
 267         *idx = e->idx;
 268
 269     return e->data;
 270 }
 271
 272 void* pa_idxset_remove_by_index(pa_idxset*s, uint32_t idx) {
 273     struct idxset_entry *e;
 274     unsigned hash;
 275     void *data;
 276
 277     pa_assert(s);
 278
 279     hash = idx % NBUCKETS;
 280
 281     if (!(e = index_scan(s, hash, idx)))
 282         return NULL;
 283
 284     data = e->data;
 285     remove_entry(s, e);
 286
 287     return data;
 288 }
 289
 290 void* pa_idxset_remove_by_data(pa_idxset*s, const void *data, uint32_t *idx) {
 291     struct idxset_entry *e;
 292     unsigned hash;
 293     void *r;
 294
 295     pa_assert(s);
 296
 297     hash = s->hash_func(data) % NBUCKETS;
 298
 299     if (!(e = data_scan(s, hash, data)))
 300         return NULL;
 301
 302     r = e->data;
 303
 304     if (idx)
 305         *idx = e->idx;
 306
 307     remove_entry(s, e);
 308
 309     return r;
 310 }
 311
 312 void* pa_idxset_rrobin(pa_idxset *s, uint32_t *idx) {
 313     unsigned hash;
 314     struct idxset_entry *e;
 315
 316     pa_assert(s);
 317     pa_assert(idx);
 318
 319     hash = *idx % NBUCKETS;
 320
 321     if (!(e = index_scan(s, hash, *idx)))
 322         return NULL;
 323
 324     if (e && e->iterate_next)
 325         e = e->iterate_next;
 326     else
 327         e = s->iterate_list_head;
 328
 329     if (!e)
 330         return NULL;
 331
 332     *idx = e->idx;
 333     return e->data;
 334 }
 335
 336 void *pa_idxset_iterate(pa_idxset *s, void **state, uint32_t *idx) {
 337     struct idxset_entry *e;
 338
 339     pa_assert(s);
 340     pa_assert(state);
 341
 342     if (*state == (void*) -1)
 343         goto at_end;
 344
 345     if ((!*state && !s->iterate_list_head))
 346         goto at_end;
 347
 348     e = *state ? *state : s->iterate_list_head;
 349
 350     if (e->iterate_next)
 351         *state = e->iterate_next;
 352     else
 353         *state = (void*) -1;
 354
 355     if (idx)
 356         *idx = e->idx;
 357
 358     return e->data;
 359
 360 at_end:
 361     *state = (void *) -1;
 362
 363     if (idx)
 364         *idx = PA_IDXSET_INVALID;
 365
 366     return NULL;
 367 }
 368
 369 void* pa_idxset_steal_first(pa_idxset *s, uint32_t *idx) {
 370     void *data;
 371
 372     pa_assert(s);
 373
 374     if (!s->iterate_list_head)
 375         return NULL;
 376
 377     data = s->iterate_list_head->data;
 378
 379     if (idx)
 380         *idx = s->iterate_list_head->idx;
 381
 382     remove_entry(s, s->iterate_list_head);
 383
 384     return data;
 385 }
 386
 387 void* pa_idxset_first(pa_idxset *s, uint32_t *idx) {
 388     pa_assert(s);
 389
 390     if (!s->iterate_list_head)
 391         return NULL;
 392
 393     if (idx)
 394         *idx = s->iterate_list_head->idx;
 395
 396     return s->iterate_list_head->data;
 397 }
 398
 399 void *pa_idxset_next(pa_idxset *s, uint32_t *idx) {
 400     struct idxset_entry *e;
 401     unsigned hash;
 402
 403     pa_assert(s);
 404     pa_assert(idx);
 405
 406     hash = *idx % NBUCKETS;
 407
 408     if (!(e = index_scan(s, hash, *idx)))
 409         return NULL;
 410
 411     if (!e->iterate_next) {
 412         *idx = PA_IDXSET_INVALID;
 413         return NULL;
 414     }
 415
 416     e = e->iterate_next;
 417
 418     *idx = e->idx;
 419     return e->data;
 420 }
 421
 422 unsigned pa_idxset_size(pa_idxset*s) {
 423     pa_assert(s);
 424
 425     return s->n_entries;
 426 }
 427
 428 pa_bool_t pa_idxset_isempty(pa_idxset *s) {
 429     pa_assert(s);
 430
 431     return s->n_entries == 0;
 432 }