From 41f6aea8fdbc744c13bc461056a2d694a5c4d06f Mon Sep 17 00:00:00 2001 From: Lennart Poettering Date: Sat, 17 Jul 2004 14:12:30 +0000 Subject: rename src to polyp git-svn-id: file:///home/lennart/svn/public/pulseaudio/trunk@90 fefdeb5f-60dc-0310-8127-8f9354f1896f --- polyp/idxset.c | 397 +++++++++++++++++++++++++++++++++++++++++++++++++++++++++ 1 file changed, 397 insertions(+) create mode 100644 polyp/idxset.c (limited to 'polyp/idxset.c') diff --git a/polyp/idxset.c b/polyp/idxset.c new file mode 100644 index 00000000..cecda6b7 --- /dev/null +++ b/polyp/idxset.c @@ -0,0 +1,397 @@ +/* $Id$ */ + +/*** + This file is part of polypaudio. + + polypaudio is free software; you can redistribute it and/or modify + it under the terms of the GNU General Public License as published + by the Free Software Foundation; either version 2 of the License, + or (at your option) any later version. + + polypaudio is distributed in the hope that it will be useful, but + WITHOUT ANY WARRANTY; without even the implied warranty of + MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the GNU + General Public License for more details. + + You should have received a copy of the GNU General Public License + along with polypaudio; if not, write to the Free Software + Foundation, Inc., 59 Temple Place, Suite 330, Boston, MA 02111-1307 + USA. +***/ + +#ifdef HAVE_CONFIG_H +#include +#endif + +#include +#include +#include +#include + +#include "idxset.h" + +struct idxset_entry { + void *data; + uint32_t index; + unsigned hash_value; + + struct idxset_entry *hash_prev, *hash_next; + struct idxset_entry* iterate_prev, *iterate_next; +}; + +struct pa_idxset { + unsigned (*hash_func) (const void *p); + int (*compare_func)(const void *a, const void *b); + + unsigned hash_table_size, n_entries; + struct idxset_entry **hash_table, **array, *iterate_list_head, *iterate_list_tail; + uint32_t index, start_index, array_size; +}; + +unsigned pa_idxset_string_hash_func(const void *p) { + unsigned hash = 0; + const char *c; + + for (c = p; *c; c++) + hash = 31 * hash + *c; + + return hash; +} + +int pa_idxset_string_compare_func(const void *a, const void *b) { + return strcmp(a, b); +} + +unsigned pa_idxset_trivial_hash_func(const void *p) { + return (unsigned) p; +} + +int pa_idxset_trivial_compare_func(const void *a, const void *b) { + return a != b; +} + +struct pa_idxset* pa_idxset_new(unsigned (*hash_func) (const void *p), int (*compare_func) (const void*a, const void*b)) { + struct pa_idxset *s; + + s = malloc(sizeof(struct pa_idxset)); + assert(s); + s->hash_func = hash_func ? hash_func : pa_idxset_trivial_hash_func; + s->compare_func = compare_func ? compare_func : pa_idxset_trivial_compare_func; + s->hash_table_size = 1023; + s->hash_table = malloc(sizeof(struct idxset_entry*)*s->hash_table_size); + assert(s->hash_table); + memset(s->hash_table, 0, sizeof(struct idxset_entry*)*s->hash_table_size); + s->array = NULL; + s->array_size = 0; + s->index = 0; + s->start_index = 0; + s->n_entries = 0; + + s->iterate_list_head = s->iterate_list_tail = NULL; + + return s; +} + +void pa_idxset_free(struct pa_idxset *s, void (*free_func) (void *p, void *userdata), void *userdata) { + assert(s); + + if (free_func) { + while (s->iterate_list_head) { + struct idxset_entry *e = s->iterate_list_head; + s->iterate_list_head = s->iterate_list_head->iterate_next; + + if (free_func) + free_func(e->data, userdata); + free(e); + } + } + + free(s->hash_table); + free(s->array); + free(s); +} + +static struct idxset_entry* hash_scan(struct pa_idxset *s, struct idxset_entry* e, void *p) { + assert(p); + + assert(s->compare_func); + for (; e; e = e->hash_next) + if (s->compare_func(e->data, p) == 0) + return e; + + return NULL; +} + +static void extend_array(struct pa_idxset *s, uint32_t index) { + uint32_t i, j, l; + struct idxset_entry** n; + assert(index >= s->start_index); + + if (index < s->start_index + s->array_size) + return; + + for (i = 0; i < s->array_size; i++) + if (s->array[i]) + break; + + l = index - s->start_index - i + 100; + n = malloc(sizeof(struct hash_table_entry*)*l); + assert(n); + memset(n, 0, sizeof(struct hash_table_entry*)*l); + + for (j = 0; j < s->array_size-i; j++) + n[j] = s->array[i+j]; + + free(s->array); + + s->array = n; + s->array_size = l; + s->start_index += i; +} + +static struct idxset_entry** array_index(struct pa_idxset*s, uint32_t index) { + if (index >= s->start_index + s->array_size) + return NULL; + + if (index < s->start_index) + return NULL; + + return s->array + (index - s->start_index); +} + +int pa_idxset_put(struct pa_idxset*s, void *p, uint32_t *index) { + unsigned h; + struct idxset_entry *e, **a; + assert(s && p); + + assert(s->hash_func); + h = s->hash_func(p) % s->hash_table_size; + + assert(s->hash_table); + if ((e = hash_scan(s, s->hash_table[h], p))) { + if (index) + *index = e->index; + + return -1; + } + + e = malloc(sizeof(struct idxset_entry)); + assert(e); + + e->data = p; + e->index = s->index++; + e->hash_value = h; + + /* Insert into hash table */ + e->hash_next = s->hash_table[h]; + e->hash_prev = NULL; + if (s->hash_table[h]) + s->hash_table[h]->hash_prev = e; + s->hash_table[h] = e; + + /* Insert into array */ + extend_array(s, e->index); + a = array_index(s, e->index); + assert(a && !*a); + *a = e; + + /* Insert into linked list */ + e->iterate_next = NULL; + e->iterate_prev = s->iterate_list_tail; + if (s->iterate_list_tail) { + assert(s->iterate_list_head); + s->iterate_list_tail->iterate_next = e; + } else { + assert(!s->iterate_list_head); + s->iterate_list_head = e; + } + s->iterate_list_tail = e; + + s->n_entries++; + assert(s->n_entries >= 1); + + if (index) + *index = e->index; + + return 0; +} + +void* pa_idxset_get_by_index(struct pa_idxset*s, uint32_t index) { + struct idxset_entry **a; + assert(s); + + if (!(a = array_index(s, index))) + return NULL; + + if (!*a) + return NULL; + + return (*a)->data; +} + +void* pa_idxset_get_by_data(struct pa_idxset*s, void *p, uint32_t *index) { + unsigned h; + struct idxset_entry *e; + assert(s && p); + + assert(s->hash_func); + h = s->hash_func(p) % s->hash_table_size; + + assert(s->hash_table); + if (!(e = hash_scan(s, s->hash_table[h], p))) + return NULL; + + if (index) + *index = e->index; + + return e->data; +} + +static void remove_entry(struct pa_idxset *s, struct idxset_entry *e) { + struct idxset_entry **a; + assert(s && e); + + /* Remove from array */ + a = array_index(s, e->index); + assert(a && *a && *a == e); + *a = NULL; + + /* Remove from linked list */ + if (e->iterate_next) + e->iterate_next->iterate_prev = e->iterate_prev; + else + s->iterate_list_tail = e->iterate_prev; + + if (e->iterate_prev) + e->iterate_prev->iterate_next = e->iterate_next; + else + s->iterate_list_head = e->iterate_next; + + /* Remove from hash table */ + if (e->hash_next) + e->hash_next->hash_prev = e->hash_prev; + + if (e->hash_prev) + e->hash_prev->hash_next = e->hash_next; + else + s->hash_table[e->hash_value] = e->hash_next; + + free(e); + + assert(s->n_entries >= 1); + s->n_entries--; +} + +void* pa_idxset_remove_by_index(struct pa_idxset*s, uint32_t index) { + struct idxset_entry **a; + void *data; + + assert(s); + + if (!(a = array_index(s, index))) + return NULL; + + data = (*a)->data; + remove_entry(s, *a); + + return data; +} + +void* pa_idxset_remove_by_data(struct pa_idxset*s, void *data, uint32_t *index) { + struct idxset_entry *e; + unsigned h; + + assert(s->hash_func); + h = s->hash_func(data) % s->hash_table_size; + + assert(s->hash_table); + if (!(e = hash_scan(s, s->hash_table[h], data))) + return NULL; + + data = e->data; + if (index) + *index = e->index; + + remove_entry(s, e); + + return data; +} + +void* pa_idxset_rrobin(struct pa_idxset *s, uint32_t *index) { + struct idxset_entry **a, *e = NULL; + assert(s && index); + + if ((a = array_index(s, *index)) && *a) + e = (*a)->iterate_next; + + if (!e) + e = s->iterate_list_head; + + if (!e) + return NULL; + + *index = e->index; + return e->data; +} + +void* pa_idxset_first(struct pa_idxset *s, uint32_t *index) { + assert(s); + + if (!s->iterate_list_head) + return NULL; + + if (index) + *index = s->iterate_list_head->index; + return s->iterate_list_head->data; +} + +void *pa_idxset_next(struct pa_idxset *s, uint32_t *index) { + struct idxset_entry **a, *e = NULL; + assert(s && index); + + if ((a = array_index(s, *index)) && *a) + e = (*a)->iterate_next; + + if (e) { + *index = e->index; + return e->data; + } else { + *index = PA_IDXSET_INVALID; + return NULL; + } +} + + +int pa_idxset_foreach(struct pa_idxset*s, int (*func)(void *p, uint32_t index, int *del, void*userdata), void *userdata) { + struct idxset_entry *e; + assert(s && func); + + e = s->iterate_list_head; + while (e) { + int del = 0, r; + struct idxset_entry *n = e->iterate_next; + + r = func(e->data, e->index, &del, userdata); + + if (del) + remove_entry(s, e); + + if (r < 0) + return r; + + e = n; + } + + return 0; +} + +unsigned pa_idxset_ncontents(struct pa_idxset*s) { + assert(s); + return s->n_entries; +} + +int pa_idxset_isempty(struct pa_idxset *s) { + assert(s); + return s->n_entries == 0; +} + -- cgit