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