code.delx.au - pulseaudio/blob - 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 <stdlib.h>
  31 #include <string.h>
  32
  33 #include <pulse/xmalloc.h>
  34 #include <pulsecore/macro.h>
  35 #include <pulsecore/flist.h>
  36
  37 #include "idxset.h"
  38
  39 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 };
  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     struct idxset_entry **hash_table, **array, *iterate_list_head, *iterate_list_tail;
  54     uint32_t index, start_index, array_size;
  55 };
  56
  57 PA_STATIC_FLIST_DECLARE(entries, 0, pa_xfree);
  58
  59 unsigned pa_idxset_string_hash_func(const void *p) {
  60     unsigned hash = 0;
  61     const char *c;
  62
  63     for (c = p; *c; c++)
  64         hash = 31 * hash + *c;
  65
  66     return hash;
  67 }
  68
  69 int pa_idxset_string_compare_func(const void *a, const void *b) {
  70     return strcmp(a, b);
  71 }
  72
  73 unsigned pa_idxset_trivial_hash_func(const void *p) {
  74     return PA_PTR_TO_UINT(p);
  75 }
  76
  77 int pa_idxset_trivial_compare_func(const void *a, const void *b) {
  78     return a != b;
  79 }
  80
  81 pa_idxset* pa_idxset_new(pa_hash_func_t hash_func, pa_compare_func_t compare_func) {
  82     pa_idxset *s;
  83
  84     s = pa_xnew(pa_idxset, 1);
  85     s->hash_func = hash_func ? hash_func : pa_idxset_trivial_hash_func;
  86     s->compare_func = compare_func ? compare_func : pa_idxset_trivial_compare_func;
  87     s->hash_table_size = 127;
  88     s->hash_table = pa_xnew0(struct idxset_entry*, s->hash_table_size);
  89     s->array = NULL;
  90     s->array_size = 0;
  91     s->index = 0;
  92     s->start_index = 0;
  93     s->n_entries = 0;
  94
  95     s->iterate_list_head = s->iterate_list_tail = NULL;
  96
  97     return s;
  98 }
  99
 100 void pa_idxset_free(pa_idxset *s, void (*free_func) (void *p, void *userdata), void *userdata) {
 101     pa_assert(s);
 102
 103     while (s->iterate_list_head) {
 104         struct idxset_entry *e = s->iterate_list_head;
 105         s->iterate_list_head = s->iterate_list_head->iterate_next;
 106
 107         if (free_func)
 108             free_func(e->data, userdata);
 109
 110         if (pa_flist_push(PA_STATIC_FLIST_GET(entries), e) < 0)
 111             pa_xfree(e);
 112     }
 113
 114     pa_xfree(s->hash_table);
 115     pa_xfree(s->array);
 116     pa_xfree(s);
 117 }
 118
 119 static struct idxset_entry* hash_scan(pa_idxset *s, struct idxset_entry* e, const void *p) {
 120     pa_assert(p);
 121
 122     pa_assert(s->compare_func);
 123     for (; e; e = e->hash_next)
 124         if (s->compare_func(e->data, p) == 0)
 125             return e;
 126
 127     return NULL;
 128 }
 129
 130 static void extend_array(pa_idxset *s, uint32_t idx) {
 131     uint32_t i, j, l;
 132     struct idxset_entry** n;
 133
 134     pa_assert(s);
 135     pa_assert(idx >= s->start_index);
 136
 137     if (idx < s->start_index + s->array_size)
 138         return;
 139
 140     for (i = 0; i < s->array_size; i++)
 141         if (s->array[i])
 142             break;
 143
 144     l = idx - s->start_index - i + 100;
 145     n = pa_xnew0(struct idxset_entry*, l);
 146
 147     for (j = 0; j < s->array_size-i; j++)
 148         n[j] = s->array[i+j];
 149
 150     pa_xfree(s->array);
 151
 152     s->array = n;
 153     s->array_size = l;
 154     s->start_index += i;
 155 }
 156
 157 static struct idxset_entry** array_index(pa_idxset*s, uint32_t idx) {
 158     pa_assert(s);
 159
 160     if (idx >= s->start_index + s->array_size)
 161         return NULL;
 162
 163     if (idx < s->start_index)
 164         return NULL;
 165
 166     return s->array + idx - s->start_index;
 167 }
 168
 169 int pa_idxset_put(pa_idxset*s, void *p, uint32_t *idx) {
 170     unsigned h;
 171     struct idxset_entry *e, **a;
 172
 173     pa_assert(s);
 174     pa_assert(p);
 175
 176     pa_assert(s->hash_func);
 177     h = s->hash_func(p) % s->hash_table_size;
 178
 179     pa_assert(s->hash_table);
 180     if ((e = hash_scan(s, s->hash_table[h], p))) {
 181         if (idx)
 182             *idx = e->index;
 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     e->data = p;
 190     e->index = s->index++;
 191     e->hash_value = h;
 192
 193     /* Insert into hash table */
 194     e->hash_next = s->hash_table[h];
 195     e->hash_prev = NULL;
 196     if (s->hash_table[h])
 197         s->hash_table[h]->hash_prev = e;
 198     s->hash_table[h] = e;
 199
 200     /* Insert into array */
 201     extend_array(s, e->index);
 202     a = array_index(s, e->index);
 203     pa_assert(a && !*a);
 204     *a = e;
 205
 206     /* Insert into linked list */
 207     e->iterate_next = NULL;
 208     e->iterate_prev = s->iterate_list_tail;
 209     if (s->iterate_list_tail) {
 210         pa_assert(s->iterate_list_head);
 211         s->iterate_list_tail->iterate_next = e;
 212     } else {
 213         pa_assert(!s->iterate_list_head);
 214         s->iterate_list_head = e;
 215     }
 216     s->iterate_list_tail = e;
 217
 218     s->n_entries++;
 219     pa_assert(s->n_entries >= 1);
 220
 221     if (idx)
 222         *idx = e->index;
 223
 224     return 0;
 225 }
 226
 227 void* pa_idxset_get_by_index(pa_idxset*s, uint32_t idx) {
 228     struct idxset_entry **a;
 229     pa_assert(s);
 230
 231     if (!(a = array_index(s, idx)))
 232         return NULL;
 233
 234     if (!*a)
 235         return NULL;
 236
 237     return (*a)->data;
 238 }
 239
 240 void* pa_idxset_get_by_data(pa_idxset*s, const void *p, uint32_t *idx) {
 241     unsigned h;
 242     struct idxset_entry *e;
 243
 244     pa_assert(s);
 245     pa_assert(p);
 246
 247     pa_assert(s->hash_func);
 248     h = s->hash_func(p) % s->hash_table_size;
 249
 250     pa_assert(s->hash_table);
 251     if (!(e = hash_scan(s, s->hash_table[h], p)))
 252         return NULL;
 253
 254     if (idx)
 255         *idx = e->index;
 256
 257     return e->data;
 258 }
 259
 260 static void remove_entry(pa_idxset *s, struct idxset_entry *e) {
 261     struct idxset_entry **a;
 262
 263     pa_assert(s);
 264     pa_assert(e);
 265
 266     /* Remove from array */
 267     a = array_index(s, e->index);
 268     pa_assert(a && *a && *a == e);
 269     *a = NULL;
 270
 271     /* Remove from linked list */
 272     if (e->iterate_next)
 273         e->iterate_next->iterate_prev = e->iterate_prev;
 274     else
 275         s->iterate_list_tail = e->iterate_prev;
 276
 277     if (e->iterate_prev)
 278         e->iterate_prev->iterate_next = e->iterate_next;
 279     else
 280         s->iterate_list_head = e->iterate_next;
 281
 282     /* Remove from hash table */
 283     if (e->hash_next)
 284         e->hash_next->hash_prev = e->hash_prev;
 285
 286     if (e->hash_prev)
 287         e->hash_prev->hash_next = e->hash_next;
 288     else
 289         s->hash_table[e->hash_value] = e->hash_next;
 290
 291     if (pa_flist_push(PA_STATIC_FLIST_GET(entries), e) < 0)
 292         pa_xfree(e);
 293
 294     pa_assert(s->n_entries >= 1);
 295     s->n_entries--;
 296 }
 297
 298 void* pa_idxset_remove_by_index(pa_idxset*s, uint32_t idx) {
 299     struct idxset_entry **a;
 300     void *data;
 301
 302     pa_assert(s);
 303
 304     if (!(a = array_index(s, idx)))
 305         return NULL;
 306
 307     if (!*a)
 308         return NULL;
 309
 310     data = (*a)->data;
 311     remove_entry(s, *a);
 312
 313     return data;
 314 }
 315
 316 void* pa_idxset_remove_by_data(pa_idxset*s, const void *data, uint32_t *idx) {
 317     struct idxset_entry *e;
 318     unsigned h;
 319     void *r;
 320
 321     pa_assert(s);
 322
 323     pa_assert(s->hash_func);
 324     h = s->hash_func(data) % s->hash_table_size;
 325
 326     pa_assert(s->hash_table);
 327     if (!(e = hash_scan(s, s->hash_table[h], data)))
 328         return NULL;
 329
 330     r = e->data;
 331     if (idx)
 332         *idx = e->index;
 333
 334     remove_entry(s, e);
 335
 336     return r;
 337 }
 338
 339 void* pa_idxset_rrobin(pa_idxset *s, uint32_t *idx) {
 340     struct idxset_entry **a, *e = NULL;
 341
 342     pa_assert(s);
 343     pa_assert(idx);
 344
 345     if ((a = array_index(s, *idx)) && *a)
 346         e = (*a)->iterate_next;
 347
 348     if (!e)
 349         e = s->iterate_list_head;
 350
 351     if (!e)
 352         return NULL;
 353
 354     *idx = e->index;
 355     return e->data;
 356 }
 357
 358 void* pa_idxset_first(pa_idxset *s, uint32_t *idx) {
 359     pa_assert(s);
 360
 361     if (!s->iterate_list_head)
 362         return NULL;
 363
 364     if (idx)
 365         *idx = s->iterate_list_head->index;
 366     return s->iterate_list_head->data;
 367 }
 368
 369 void *pa_idxset_next(pa_idxset *s, uint32_t *idx) {
 370     struct idxset_entry **a, *e = NULL;
 371
 372     pa_assert(s);
 373     pa_assert(idx);
 374
 375     if ((a = array_index(s, *idx)) && *a)
 376         e = (*a)->iterate_next;
 377
 378     if (e) {
 379         *idx = e->index;
 380         return e->data;
 381     } else {
 382         *idx = PA_IDXSET_INVALID;
 383         return NULL;
 384     }
 385 }
 386
 387 int pa_idxset_foreach(pa_idxset*s, int (*func)(void *p, uint32_t idx, int *del, void*userdata), void *userdata) {
 388     struct idxset_entry *e;
 389
 390     pa_assert(s);
 391     pa_assert(func);
 392
 393     e = s->iterate_list_head;
 394     while (e) {
 395         int del = 0, r;
 396         struct idxset_entry *n = e->iterate_next;
 397
 398         r = func(e->data, e->index, &del, userdata);
 399
 400         if (del)
 401             remove_entry(s, e);
 402
 403         if (r < 0)
 404             return r;
 405
 406         e = n;
 407     }
 408
 409     return 0;
 410 }
 411
 412 unsigned pa_idxset_size(pa_idxset*s) {
 413     pa_assert(s);
 414
 415     return s->n_entries;
 416 }
 417
 418 int pa_idxset_isempty(pa_idxset *s) {
 419     pa_assert(s);
 420
 421     return s->n_entries == 0;
 422 }
 423