src/pulsecore/idxset.c

   1 /* $Id$ */
   2
   3 /***
   4   This file is part of PulseAudio.
   5
   6   Copyright 2004-2006 Lennart Poettering
   7   Copyright 2006 Pierre Ossman <ossman@cendio.se> for Cendio AB
   8
   9   PulseAudio is free software; you can redistribute it and/or modify
  10   it under the terms of the GNU Lesser General Public License as
  11   published by the Free Software Foundation; either version 2.1 of the
  12   License, or (at your option) any later version.
  13
  14   PulseAudio is distributed in the hope that it will be useful, but
  15   WITHOUT ANY WARRANTY; without even the implied warranty of
  16   MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the GNU
  17   Lesser General Public License for more details.
  18
  19   You should have received a copy of the GNU Lesser General Public
  20   License along with PulseAudio; if not, write to the Free Software
  21   Foundation, Inc., 59 Temple Place, Suite 330, Boston, MA 02111-1307
  22   USA.
  23 ***/
  24
  25 #ifdef HAVE_CONFIG_H
  26 #include <config.h>
  27 #endif
  28
  29 #include <stdio.h>
  30 #include <assert.h>
  31 #include <stdlib.h>
  32 #include <string.h>
  33
  34 #include <pulse/xmalloc.h>
  35 #include <pulsecore/macro.h>
  36
  37 #include "idxset.h"
  38
  39 typedef struct idxset_entry {
  40     void *data;
  41     uint32_t index;
  42     unsigned hash_value;
  43
  44     struct idxset_entry *hash_prev, *hash_next;
  45     struct idxset_entry* iterate_prev, *iterate_next;
  46 } idxset_entry;
  47
  48 struct pa_idxset {
  49     pa_hash_func_t hash_func;
  50     pa_compare_func_t compare_func;
  51
  52     unsigned hash_table_size, n_entries;
  53     idxset_entry **hash_table, **array, *iterate_list_head, *iterate_list_tail;
  54     uint32_t index, start_index, array_size;
  55 };
  56
  57 unsigned pa_idxset_string_hash_func(const void *p) {
  58     unsigned hash = 0;
  59     const char *c;
  60
  61     for (c = p; *c; c++)
  62         hash = 31 * hash + *c;
  63
  64     return hash;
  65 }
  66
  67 int pa_idxset_string_compare_func(const void *a, const void *b) {
  68     return strcmp(a, b);
  69 }
  70
  71 unsigned pa_idxset_trivial_hash_func(const void *p) {
  72     return PA_PTR_TO_UINT(p);
  73 }
  74
  75 int pa_idxset_trivial_compare_func(const void *a, const void *b) {
  76     return a != b;
  77 }
  78
  79 pa_idxset* pa_idxset_new(pa_hash_func_t hash_func, pa_compare_func_t compare_func) {
  80     pa_idxset *s;
  81
  82     s = pa_xnew(pa_idxset, 1);
  83     s->hash_func = hash_func ? hash_func : pa_idxset_trivial_hash_func;
  84     s->compare_func = compare_func ? compare_func : pa_idxset_trivial_compare_func;
  85     s->hash_table_size = 127;
  86     s->hash_table = pa_xnew0(idxset_entry*, s->hash_table_size);
  87     s->array = NULL;
  88     s->array_size = 0;
  89     s->index = 0;
  90     s->start_index = 0;
  91     s->n_entries = 0;
  92
  93     s->iterate_list_head = s->iterate_list_tail = NULL;
  94
  95     return s;
  96 }
  97
  98 void pa_idxset_free(pa_idxset *s, void (*free_func) (void *p, void *userdata), void *userdata) {
  99     assert(s);
 100
 101     while (s->iterate_list_head) {
 102         idxset_entry *e = s->iterate_list_head;
 103         s->iterate_list_head = s->iterate_list_head->iterate_next;
 104
 105         if (free_func)
 106             free_func(e->data, userdata);
 107         pa_xfree(e);
 108     }
 109
 110     pa_xfree(s->hash_table);
 111     pa_xfree(s->array);
 112     pa_xfree(s);
 113 }
 114
 115 static idxset_entry* hash_scan(pa_idxset *s, idxset_entry* e, const void *p) {
 116     assert(p);
 117
 118     assert(s->compare_func);
 119     for (; e; e = e->hash_next)
 120         if (s->compare_func(e->data, p) == 0)
 121             return e;
 122
 123     return NULL;
 124 }
 125
 126 static void extend_array(pa_idxset *s, uint32_t idx) {
 127     uint32_t i, j, l;
 128     idxset_entry** n;
 129     assert(idx >= s->start_index);
 130
 131     if (idx < s->start_index + s->array_size)
 132         return;
 133
 134     for (i = 0; i < s->array_size; i++)
 135         if (s->array[i])
 136             break;
 137
 138     l = idx - s->start_index - i + 100;
 139     n = pa_xnew0(idxset_entry*, l);
 140
 141     for (j = 0; j < s->array_size-i; j++)
 142         n[j] = s->array[i+j];
 143
 144     pa_xfree(s->array);
 145
 146     s->array = n;
 147     s->array_size = l;
 148     s->start_index += i;
 149 }
 150
 151 static idxset_entry** array_index(pa_idxset*s, uint32_t idx) {
 152     if (idx >= s->start_index + s->array_size)
 153         return NULL;
 154
 155     if (idx < s->start_index)
 156         return NULL;
 157
 158     return s->array + idx - s->start_index;
 159 }
 160
 161 int pa_idxset_put(pa_idxset*s, void *p, uint32_t *idx) {
 162     unsigned h;
 163     idxset_entry *e, **a;
 164
 165     assert(s);
 166     assert(p);
 167
 168     assert(s->hash_func);
 169     h = s->hash_func(p) % s->hash_table_size;
 170
 171     assert(s->hash_table);
 172     if ((e = hash_scan(s, s->hash_table[h], p))) {
 173         if (idx)
 174             *idx = e->index;
 175
 176         return -1;
 177     }
 178
 179     e = pa_xmalloc(sizeof(idxset_entry));
 180     e->data = p;
 181     e->index = s->index++;
 182     e->hash_value = h;
 183
 184     /* Insert into hash table */
 185     e->hash_next = s->hash_table[h];
 186     e->hash_prev = NULL;
 187     if (s->hash_table[h])
 188         s->hash_table[h]->hash_prev = e;
 189     s->hash_table[h] = e;
 190
 191     /* Insert into array */
 192     extend_array(s, e->index);
 193     a = array_index(s, e->index);
 194     assert(a && !*a);
 195     *a = e;
 196
 197     /* Insert into linked list */
 198     e->iterate_next = NULL;
 199     e->iterate_prev = s->iterate_list_tail;
 200     if (s->iterate_list_tail) {
 201         assert(s->iterate_list_head);
 202         s->iterate_list_tail->iterate_next = e;
 203     } else {
 204         assert(!s->iterate_list_head);
 205         s->iterate_list_head = e;
 206     }
 207     s->iterate_list_tail = e;
 208
 209     s->n_entries++;
 210     assert(s->n_entries >= 1);
 211
 212     if (idx)
 213         *idx = e->index;
 214
 215     return 0;
 216 }
 217
 218 void* pa_idxset_get_by_index(pa_idxset*s, uint32_t idx) {
 219     idxset_entry **a;
 220     assert(s);
 221
 222     if (!(a = array_index(s, idx)))
 223         return NULL;
 224
 225     if (!*a)
 226         return NULL;
 227
 228     return (*a)->data;
 229 }
 230
 231 void* pa_idxset_get_by_data(pa_idxset*s, const void *p, uint32_t *idx) {
 232     unsigned h;
 233     idxset_entry *e;
 234     assert(s && p);
 235
 236     assert(s->hash_func);
 237     h = s->hash_func(p) % s->hash_table_size;
 238
 239     assert(s->hash_table);
 240     if (!(e = hash_scan(s, s->hash_table[h], p)))
 241         return NULL;
 242
 243     if (idx)
 244         *idx = e->index;
 245
 246     return e->data;
 247 }
 248
 249 static void remove_entry(pa_idxset *s, idxset_entry *e) {
 250     idxset_entry **a;
 251     assert(s && e);
 252
 253     /* Remove from array */
 254     a = array_index(s, e->index);
 255     assert(a && *a && *a == e);
 256     *a = NULL;
 257
 258     /* Remove from linked list */
 259     if (e->iterate_next)
 260         e->iterate_next->iterate_prev = e->iterate_prev;
 261     else
 262         s->iterate_list_tail = e->iterate_prev;
 263
 264     if (e->iterate_prev)
 265         e->iterate_prev->iterate_next = e->iterate_next;
 266     else
 267         s->iterate_list_head = e->iterate_next;
 268
 269     /* Remove from hash table */
 270     if (e->hash_next)
 271         e->hash_next->hash_prev = e->hash_prev;
 272
 273     if (e->hash_prev)
 274         e->hash_prev->hash_next = e->hash_next;
 275     else
 276         s->hash_table[e->hash_value] = e->hash_next;
 277
 278     pa_xfree(e);
 279
 280     assert(s->n_entries >= 1);
 281     s->n_entries--;
 282 }
 283
 284 void* pa_idxset_remove_by_index(pa_idxset*s, uint32_t idx) {
 285     idxset_entry **a;
 286     void *data;
 287
 288     assert(s);
 289
 290     if (!(a = array_index(s, idx)))
 291         return NULL;
 292
 293     if (!*a)
 294         return NULL;
 295
 296     data = (*a)->data;
 297     remove_entry(s, *a);
 298
 299     return data;
 300 }
 301
 302 void* pa_idxset_remove_by_data(pa_idxset*s, const void *data, uint32_t *idx) {
 303     idxset_entry *e;
 304     unsigned h;
 305     void *r;
 306
 307     assert(s->hash_func);
 308     h = s->hash_func(data) % s->hash_table_size;
 309
 310     assert(s->hash_table);
 311     if (!(e = hash_scan(s, s->hash_table[h], data)))
 312         return NULL;
 313
 314     r = e->data;
 315     if (idx)
 316         *idx = e->index;
 317
 318     remove_entry(s, e);
 319
 320     return r;
 321 }
 322
 323 void* pa_idxset_rrobin(pa_idxset *s, uint32_t *idx) {
 324     idxset_entry **a, *e = NULL;
 325     assert(s && idx);
 326
 327     if ((a = array_index(s, *idx)) && *a)
 328         e = (*a)->iterate_next;
 329
 330     if (!e)
 331         e = s->iterate_list_head;
 332
 333     if (!e)
 334         return NULL;
 335
 336     *idx = e->index;
 337     return e->data;
 338 }
 339
 340 void* pa_idxset_first(pa_idxset *s, uint32_t *idx) {
 341     assert(s);
 342
 343     if (!s->iterate_list_head)
 344         return NULL;
 345
 346     if (idx)
 347         *idx = s->iterate_list_head->index;
 348     return s->iterate_list_head->data;
 349 }
 350
 351 void *pa_idxset_next(pa_idxset *s, uint32_t *idx) {
 352     idxset_entry **a, *e = NULL;
 353     assert(s);
 354     assert(idx);
 355
 356     if ((a = array_index(s, *idx)) && *a)
 357         e = (*a)->iterate_next;
 358
 359     if (e) {
 360         *idx = e->index;
 361         return e->data;
 362     } else {
 363         *idx = PA_IDXSET_INVALID;
 364         return NULL;
 365     }
 366 }
 367
 368 int pa_idxset_foreach(pa_idxset*s, int (*func)(void *p, uint32_t idx, int *del, void*userdata), void *userdata) {
 369     idxset_entry *e;
 370     assert(s && func);
 371
 372     e = s->iterate_list_head;
 373     while (e) {
 374         int del = 0, r;
 375         idxset_entry *n = e->iterate_next;
 376
 377         r = func(e->data, e->index, &del, userdata);
 378
 379         if (del)
 380             remove_entry(s, e);
 381
 382         if (r < 0)
 383             return r;
 384
 385         e = n;
 386     }
 387
 388     return 0;
 389 }
 390
 391 unsigned pa_idxset_size(pa_idxset*s) {
 392     assert(s);
 393     return s->n_entries;
 394 }
 395
 396 int pa_idxset_isempty(pa_idxset *s) {
 397     assert(s);
 398     return s->n_entries == 0;
 399 }
 400