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, 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
  37 struct 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
  46 struct 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
  59 PA_STATIC_FLIST_DECLARE(entries, 0, pa_xfree);
  60
  61 unsigned 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
  71 int pa_idxset_string_compare_func(const void *a, const void *b) {
  72     return strcmp(a, b);
  73 }
  74
  75 unsigned pa_idxset_trivial_hash_func(const void *p) {
  76     return PA_PTR_TO_UINT(p);
  77 }
  78
  79 int pa_idxset_trivial_compare_func(const void *a, const void *b) {
  80     return a < b ? -1 : (a > b ? 1 : 0);
  81 }
  82
  83 pa_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
  98 static 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
 140 void 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
 147 static 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
 160 static 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
 172 int 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
 230 void* 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
 244 void* 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
 261 void* 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
 279 void* 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
 301 void 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
 314 void* 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
 337 void *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
 361 at_end:
 362     *state = (void *) -1;
 363
 364     if (idx)
 365         *idx = PA_IDXSET_INVALID;
 366
 367     return NULL;
 368 }
 369
 370 void* 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
 388 void* 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
 403 void *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
 447 unsigned pa_idxset_size(pa_idxset*s) {
 448     pa_assert(s);
 449
 450     return s->n_entries;
 451 }
 452
 453 bool pa_idxset_isempty(pa_idxset *s) {
 454     pa_assert(s);
 455
 456     return s->n_entries == 0;
 457 }
 458
 459 pa_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
 473 #ifdef __TIZEN__
 474 pa_idxset *pa_idxset_filtered_copy(pa_idxset *s, pa_copy_func_t copy_func, pa_compare_func_t filter_func, const void *filter) {
 475     pa_idxset *copy;
 476     struct idxset_entry *i;
 477
 478     pa_assert(s);
 479
 480     copy = pa_idxset_new(s->hash_func, s->compare_func);
 481
 482     for (i = s->iterate_list_head; i; i = i->iterate_next) {
 483         if (filter_func) {
 484             if (filter_func(i->data, filter))
 485                 pa_idxset_put(copy, copy_func ? copy_func(i->data) : i->data, NULL);
 486         } else
 487             pa_idxset_put(copy, copy_func ? copy_func(i->data) : i->data, NULL);
 488     }
 489
 490     return copy;
 491 }
 492 #endif