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 ? -1 : (a > b ? 1 : 0);
  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     e = index_scan(s, hash, *idx);
 322
 323     if (e && e->iterate_next)
 324         e = e->iterate_next;
 325     else
 326         e = s->iterate_list_head;
 327
 328     if (!e)
 329         return NULL;
 330
 331     *idx = e->idx;
 332     return e->data;
 333 }
 334
 335 void *pa_idxset_iterate(pa_idxset *s, void **state, uint32_t *idx) {
 336     struct idxset_entry *e;
 337
 338     pa_assert(s);
 339     pa_assert(state);
 340
 341     if (*state == (void*) -1)
 342         goto at_end;
 343
 344     if ((!*state && !s->iterate_list_head))
 345         goto at_end;
 346
 347     e = *state ? *state : s->iterate_list_head;
 348
 349     if (e->iterate_next)
 350         *state = e->iterate_next;
 351     else
 352         *state = (void*) -1;
 353
 354     if (idx)
 355         *idx = e->idx;
 356
 357     return e->data;
 358
 359 at_end:
 360     *state = (void *) -1;
 361
 362     if (idx)
 363         *idx = PA_IDXSET_INVALID;
 364
 365     return NULL;
 366 }
 367
 368 void* pa_idxset_steal_first(pa_idxset *s, uint32_t *idx) {
 369     void *data;
 370
 371     pa_assert(s);
 372
 373     if (!s->iterate_list_head)
 374         return NULL;
 375
 376     data = s->iterate_list_head->data;
 377
 378     if (idx)
 379         *idx = s->iterate_list_head->idx;
 380
 381     remove_entry(s, s->iterate_list_head);
 382
 383     return data;
 384 }
 385
 386 void* pa_idxset_first(pa_idxset *s, uint32_t *idx) {
 387     pa_assert(s);
 388
 389     if (!s->iterate_list_head) {
 390         if (idx)
 391             *idx = PA_IDXSET_INVALID;
 392         return NULL;
 393     }
 394
 395     if (idx)
 396         *idx = s->iterate_list_head->idx;
 397
 398     return s->iterate_list_head->data;
 399 }
 400
 401 void *pa_idxset_next(pa_idxset *s, uint32_t *idx) {
 402     struct idxset_entry *e;
 403     unsigned hash;
 404
 405     pa_assert(s);
 406     pa_assert(idx);
 407
 408     if (*idx == PA_IDXSET_INVALID)
 409         return NULL;
 410
 411     hash = *idx % NBUCKETS;
 412
 413     if ((e = index_scan(s, hash, *idx))) {
 414
 415         e = e->iterate_next;
 416
 417         if (e) {
 418             *idx = e->idx;
 419             return e->data;
 420         } else {
 421             *idx = PA_IDXSET_INVALID;
 422             return NULL;
 423         }
 424
 425     } else {
 426
 427         /* If the entry passed doesn't exist anymore we try to find
 428          * the next following */
 429
 430         for ((*idx)++; *idx < s->current_index; (*idx)++) {
 431
 432             hash = *idx % NBUCKETS;
 433
 434             if ((e = index_scan(s, hash, *idx))) {
 435                 *idx = e->idx;
 436                 return e->data;
 437             }
 438         }
 439
 440         *idx = PA_IDXSET_INVALID;
 441         return NULL;
 442     }
 443 }
 444
 445 unsigned pa_idxset_size(pa_idxset*s) {
 446     pa_assert(s);
 447
 448     return s->n_entries;
 449 }
 450
 451 pa_bool_t pa_idxset_isempty(pa_idxset *s) {
 452     pa_assert(s);
 453
 454     return s->n_entries == 0;
 455 }
 456
 457 pa_idxset *pa_idxset_copy(pa_idxset *s) {
 458     pa_idxset *copy;
 459     struct idxset_entry *i;
 460
 461     pa_assert(s);
 462
 463     copy = pa_idxset_new(s->hash_func, s->compare_func);
 464
 465     for (i = s->iterate_list_head; i; i = i->iterate_next)
 466         pa_idxset_put(copy, i->data, NULL);
 467
 468     return copy;
 469 }