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_free2_cb_t free_cb, void *userdata) {
 143     pa_assert(s);
 144
 145     while (s->iterate_list_head) {
 146         void *data = s->iterate_list_head->data;
 147
 148         remove_entry(s, s->iterate_list_head);
 149
 150         if (free_cb)
 151             free_cb(data, userdata);
 152     }
 153
 154     pa_xfree(s);
 155 }
 156
 157 static struct idxset_entry* data_scan(pa_idxset *s, unsigned hash, const void *p) {
 158     struct idxset_entry *e;
 159     pa_assert(s);
 160     pa_assert(hash < NBUCKETS);
 161     pa_assert(p);
 162
 163     for (e = BY_DATA(s)[hash]; e; e = e->data_next)
 164         if (s->compare_func(e->data, p) == 0)
 165             return e;
 166
 167     return NULL;
 168 }
 169
 170 static struct idxset_entry* index_scan(pa_idxset *s, unsigned hash, uint32_t idx) {
 171     struct idxset_entry *e;
 172     pa_assert(s);
 173     pa_assert(hash < NBUCKETS);
 174
 175     for (e = BY_INDEX(s)[hash]; e; e = e->index_next)
 176         if (e->idx == idx)
 177             return e;
 178
 179     return NULL;
 180 }
 181
 182 int pa_idxset_put(pa_idxset*s, void *p, uint32_t *idx) {
 183     unsigned hash;
 184     struct idxset_entry *e;
 185
 186     pa_assert(s);
 187
 188     hash = s->hash_func(p) % NBUCKETS;
 189
 190     if ((e = data_scan(s, hash, p))) {
 191         if (idx)
 192             *idx = e->idx;
 193
 194         return -1;
 195     }
 196
 197     if (!(e = pa_flist_pop(PA_STATIC_FLIST_GET(entries))))
 198         e = pa_xnew(struct idxset_entry, 1);
 199
 200     e->data = p;
 201     e->idx = s->current_index++;
 202
 203     /* Insert into data hash table */
 204     e->data_next = BY_DATA(s)[hash];
 205     e->data_previous = NULL;
 206     if (BY_DATA(s)[hash])
 207         BY_DATA(s)[hash]->data_previous = e;
 208     BY_DATA(s)[hash] = e;
 209
 210     hash = e->idx % NBUCKETS;
 211
 212     /* Insert into index hash table */
 213     e->index_next = BY_INDEX(s)[hash];
 214     e->index_previous = NULL;
 215     if (BY_INDEX(s)[hash])
 216         BY_INDEX(s)[hash]->index_previous = e;
 217     BY_INDEX(s)[hash] = e;
 218
 219     /* Insert into iteration list */
 220     e->iterate_previous = s->iterate_list_tail;
 221     e->iterate_next = NULL;
 222     if (s->iterate_list_tail) {
 223         pa_assert(s->iterate_list_head);
 224         s->iterate_list_tail->iterate_next = e;
 225     } else {
 226         pa_assert(!s->iterate_list_head);
 227         s->iterate_list_head = e;
 228     }
 229     s->iterate_list_tail = e;
 230
 231     s->n_entries++;
 232     pa_assert(s->n_entries >= 1);
 233
 234     if (idx)
 235         *idx = e->idx;
 236
 237     return 0;
 238 }
 239
 240 void* pa_idxset_get_by_index(pa_idxset*s, uint32_t idx) {
 241     unsigned hash;
 242     struct idxset_entry *e;
 243
 244     pa_assert(s);
 245
 246     hash = idx % NBUCKETS;
 247
 248     if (!(e = index_scan(s, hash, idx)))
 249         return NULL;
 250
 251     return e->data;
 252 }
 253
 254 void* pa_idxset_get_by_data(pa_idxset*s, const void *p, uint32_t *idx) {
 255     unsigned hash;
 256     struct idxset_entry *e;
 257
 258     pa_assert(s);
 259
 260     hash = s->hash_func(p) % NBUCKETS;
 261
 262     if (!(e = data_scan(s, hash, p)))
 263         return NULL;
 264
 265     if (idx)
 266         *idx = e->idx;
 267
 268     return e->data;
 269 }
 270
 271 void* pa_idxset_remove_by_index(pa_idxset*s, uint32_t idx) {
 272     struct idxset_entry *e;
 273     unsigned hash;
 274     void *data;
 275
 276     pa_assert(s);
 277
 278     hash = idx % NBUCKETS;
 279
 280     if (!(e = index_scan(s, hash, idx)))
 281         return NULL;
 282
 283     data = e->data;
 284     remove_entry(s, e);
 285
 286     return data;
 287 }
 288
 289 void* pa_idxset_remove_by_data(pa_idxset*s, const void *data, uint32_t *idx) {
 290     struct idxset_entry *e;
 291     unsigned hash;
 292     void *r;
 293
 294     pa_assert(s);
 295
 296     hash = s->hash_func(data) % NBUCKETS;
 297
 298     if (!(e = data_scan(s, hash, data)))
 299         return NULL;
 300
 301     r = e->data;
 302
 303     if (idx)
 304         *idx = e->idx;
 305
 306     remove_entry(s, e);
 307
 308     return r;
 309 }
 310
 311 void* pa_idxset_rrobin(pa_idxset *s, uint32_t *idx) {
 312     unsigned hash;
 313     struct idxset_entry *e;
 314
 315     pa_assert(s);
 316     pa_assert(idx);
 317
 318     hash = *idx % NBUCKETS;
 319
 320     e = index_scan(s, hash, *idx);
 321
 322     if (e && e->iterate_next)
 323         e = e->iterate_next;
 324     else
 325         e = s->iterate_list_head;
 326
 327     if (!e)
 328         return NULL;
 329
 330     *idx = e->idx;
 331     return e->data;
 332 }
 333
 334 void *pa_idxset_iterate(pa_idxset *s, void **state, uint32_t *idx) {
 335     struct idxset_entry *e;
 336
 337     pa_assert(s);
 338     pa_assert(state);
 339
 340     if (*state == (void*) -1)
 341         goto at_end;
 342
 343     if ((!*state && !s->iterate_list_head))
 344         goto at_end;
 345
 346     e = *state ? *state : s->iterate_list_head;
 347
 348     if (e->iterate_next)
 349         *state = e->iterate_next;
 350     else
 351         *state = (void*) -1;
 352
 353     if (idx)
 354         *idx = e->idx;
 355
 356     return e->data;
 357
 358 at_end:
 359     *state = (void *) -1;
 360
 361     if (idx)
 362         *idx = PA_IDXSET_INVALID;
 363
 364     return NULL;
 365 }
 366
 367 void* pa_idxset_steal_first(pa_idxset *s, uint32_t *idx) {
 368     void *data;
 369
 370     pa_assert(s);
 371
 372     if (!s->iterate_list_head)
 373         return NULL;
 374
 375     data = s->iterate_list_head->data;
 376
 377     if (idx)
 378         *idx = s->iterate_list_head->idx;
 379
 380     remove_entry(s, s->iterate_list_head);
 381
 382     return data;
 383 }
 384
 385 void* pa_idxset_first(pa_idxset *s, uint32_t *idx) {
 386     pa_assert(s);
 387
 388     if (!s->iterate_list_head) {
 389         if (idx)
 390             *idx = PA_IDXSET_INVALID;
 391         return NULL;
 392     }
 393
 394     if (idx)
 395         *idx = s->iterate_list_head->idx;
 396
 397     return s->iterate_list_head->data;
 398 }
 399
 400 void *pa_idxset_next(pa_idxset *s, uint32_t *idx) {
 401     struct idxset_entry *e;
 402     unsigned hash;
 403
 404     pa_assert(s);
 405     pa_assert(idx);
 406
 407     if (*idx == PA_IDXSET_INVALID)
 408         return NULL;
 409
 410     hash = *idx % NBUCKETS;
 411
 412     if ((e = index_scan(s, hash, *idx))) {
 413
 414         e = e->iterate_next;
 415
 416         if (e) {
 417             *idx = e->idx;
 418             return e->data;
 419         } else {
 420             *idx = PA_IDXSET_INVALID;
 421             return NULL;
 422         }
 423
 424     } else {
 425
 426         /* If the entry passed doesn't exist anymore we try to find
 427          * the next following */
 428
 429         for ((*idx)++; *idx < s->current_index; (*idx)++) {
 430
 431             hash = *idx % NBUCKETS;
 432
 433             if ((e = index_scan(s, hash, *idx))) {
 434                 *idx = e->idx;
 435                 return e->data;
 436             }
 437         }
 438
 439         *idx = PA_IDXSET_INVALID;
 440         return NULL;
 441     }
 442 }
 443
 444 unsigned pa_idxset_size(pa_idxset*s) {
 445     pa_assert(s);
 446
 447     return s->n_entries;
 448 }
 449
 450 pa_bool_t pa_idxset_isempty(pa_idxset *s) {
 451     pa_assert(s);
 452
 453     return s->n_entries == 0;
 454 }
 455
 456 pa_idxset *pa_idxset_copy(pa_idxset *s) {
 457     pa_idxset *copy;
 458     struct idxset_entry *i;
 459
 460     pa_assert(s);
 461
 462     copy = pa_idxset_new(s->hash_func, s->compare_func);
 463
 464     for (i = s->iterate_list_head; i; i = i->iterate_next)
 465         pa_idxset_put(copy, i->data, NULL);
 466
 467     return copy;
 468 }