1 files changed, 203 insertions, 86 deletions

diff --git a/src/pulsecore/hashmap.c b/src/pulsecore/hashmap.c
index 2cddba1d..e368512b 100644
--- a/src/pulsecore/hashmap.c
+++ b/src/pulsecore/hashmap.c
@@ -1,18 +1,18 @@
-/* $Id$ */
-
 /***
   This file is part of PulseAudio.
- 
+
+  Copyright 2004-2008 Lennart Poettering
+
   PulseAudio is free software; you can redistribute it and/or modify
   it under the terms of the GNU Lesser General Public License as published
-  by the Free Software Foundation; either version 2 of the License,
+  by the Free Software Foundation; either version 2.1 of the License,
   or (at your option) any later version.
- 
+
   PulseAudio 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 Lesser General Public License
   along with PulseAudio; if not, write to the Free Software
   Foundation, Inc., 59 Temple Place, Suite 330, Boston, MA 02111-1307
@@ -24,87 +24,104 @@
 #endif
 
 #include <stdlib.h>
-#include <assert.h>
-#include <string.h>
 
 #include <pulse/xmalloc.h>
-
 #include <pulsecore/idxset.h>
-#include <pulsecore/log.h>
+#include <pulsecore/flist.h>
+#include <pulsecore/macro.h>
 
 #include "hashmap.h"
 
-#define BUCKETS 1023
+#define NBUCKETS 127
 
 struct hashmap_entry {
-    struct hashmap_entry *next, *previous, *bucket_next, *bucket_previous;
-    unsigned hash;
     const void *key;
     void *value;
+
+    struct hashmap_entry *bucket_next, *bucket_previous;
+    struct hashmap_entry *iterate_next, *iterate_previous;
 };
 
 struct pa_hashmap {
-    unsigned size;
-    struct hashmap_entry **data;
-    struct hashmap_entry *first_entry;
-    
+    pa_hash_func_t hash_func;
+    pa_compare_func_t compare_func;
+
+    struct hashmap_entry *iterate_list_head, *iterate_list_tail;
     unsigned n_entries;
-    unsigned (*hash_func) (const void *p);
-    int (*compare_func) (const void*a, const void*b);
 };
 
-pa_hashmap *pa_hashmap_new(unsigned (*hash_func) (const void *p), int (*compare_func) (const void*a, const void*b)) {
+#define BY_HASH(h) ((struct hashmap_entry**) ((uint8_t*) (h) + PA_ALIGN(sizeof(pa_hashmap))))
+
+PA_STATIC_FLIST_DECLARE(entries, 0, pa_xfree);
+
+pa_hashmap *pa_hashmap_new(pa_hash_func_t hash_func, pa_compare_func_t compare_func) {
     pa_hashmap *h;
-    h = pa_xmalloc(sizeof(pa_hashmap));
-    h->data = pa_xmalloc0(sizeof(struct hashmap_entry*)*(h->size = BUCKETS));
-    h->first_entry = NULL;
-    h->n_entries = 0;
+
+    h = pa_xmalloc0(PA_ALIGN(sizeof(pa_hashmap)) + NBUCKETS*sizeof(struct hashmap_entry*));
+
     h->hash_func = hash_func ? hash_func : pa_idxset_trivial_hash_func;
     h->compare_func = compare_func ? compare_func : pa_idxset_trivial_compare_func;
+
+    h->n_entries = 0;
+    h->iterate_list_head = h->iterate_list_tail = NULL;
+
     return h;
 }
 
-static void remove(pa_hashmap *h, struct hashmap_entry *e) {
-    assert(e);
+static void remove_entry(pa_hashmap *h, struct hashmap_entry *e) {
+    pa_assert(h);
+    pa_assert(e);
+
+    /* Remove from iteration list */
+    if (e->iterate_next)
+        e->iterate_next->iterate_previous = e->iterate_previous;
+    else
+        h->iterate_list_tail = e->iterate_previous;
 
-    if (e->next)
-        e->next->previous = e->previous;
-    if (e->previous)
-        e->previous->next = e->next;
+    if (e->iterate_previous)
+        e->iterate_previous->iterate_next = e->iterate_next;
     else
-        h->first_entry = e->next;
+        h->iterate_list_head = e->iterate_next;
 
+    /* Remove from hash table bucket list */
     if (e->bucket_next)
         e->bucket_next->bucket_previous = e->bucket_previous;
+
     if (e->bucket_previous)
         e->bucket_previous->bucket_next = e->bucket_next;
     else {
-        assert(e->hash < h->size);
-        h->data[e->hash] = e->bucket_next;
+        unsigned hash = h->hash_func(e->key) % NBUCKETS;
+        BY_HASH(h)[hash] = e->bucket_next;
     }
 
-    pa_xfree(e);
+    if (pa_flist_push(PA_STATIC_FLIST_GET(entries), e) < 0)
+        pa_xfree(e);
+
+    pa_assert(h->n_entries >= 1);
     h->n_entries--;
 }
 
-void pa_hashmap_free(pa_hashmap*h, void (*free_func)(void *p, void *userdata), void *userdata) {
-    assert(h);
+void pa_hashmap_free(pa_hashmap*h, pa_free2_cb_t free_cb, void *userdata) {
+    pa_assert(h);
 
-    while (h->first_entry) {
-        if (free_func)
-            free_func(h->first_entry->value, userdata);
-        remove(h, h->first_entry);
+    while (h->iterate_list_head) {
+        void *data;
+        data = h->iterate_list_head->value;
+        remove_entry(h, h->iterate_list_head);
+
+        if (free_cb)
+            free_cb(data, userdata);
     }
-    
-    pa_xfree(h->data);
+
     pa_xfree(h);
 }
 
-static struct hashmap_entry *get(pa_hashmap *h, unsigned hash, const void *key) {
+static struct hashmap_entry *hash_scan(pa_hashmap *h, unsigned hash, const void *key) {
     struct hashmap_entry *e;
-    assert(h && hash < h->size);
+    pa_assert(h);
+    pa_assert(hash < NBUCKETS);
 
-    for (e = h->data[hash]; e; e = e->bucket_next)
+    for (e = BY_HASH(h)[hash]; e; e = e->bucket_next)
         if (h->compare_func(e->key, key) == 0)
             return e;
 
@@ -114,42 +131,54 @@ static struct hashmap_entry *get(pa_hashmap *h, unsigned hash, const void *key)
 int pa_hashmap_put(pa_hashmap *h, const void *key, void *value) {
     struct hashmap_entry *e;
     unsigned hash;
-    assert(h);
 
-    hash = h->hash_func(key) % h->size;
+    pa_assert(h);
+
+    hash = h->hash_func(key) % NBUCKETS;
 
-    if ((e = get(h, hash, key)))
+    if (hash_scan(h, hash, key))
         return -1;
-    
-    e = pa_xmalloc(sizeof(struct hashmap_entry));
-    e->hash = hash;
+
+    if (!(e = pa_flist_pop(PA_STATIC_FLIST_GET(entries))))
+        e = pa_xnew(struct hashmap_entry, 1);
+
     e->key = key;
     e->value = value;
-    
-    e->previous = NULL;
-    e->next = h->first_entry;
-    if (h->first_entry)
-        h->first_entry->previous = e;
-    h->first_entry = e;
-    
+
+    /* Insert into hash table */
+    e->bucket_next = BY_HASH(h)[hash];
     e->bucket_previous = NULL;
-    e->bucket_next = h->data[hash];
-    if (h->data[hash])
-        h->data[hash]->bucket_previous = e;
-    h->data[hash] = e;
-    
-    h->n_entries ++;
+    if (BY_HASH(h)[hash])
+        BY_HASH(h)[hash]->bucket_previous = e;
+    BY_HASH(h)[hash] = e;
+
+    /* Insert into iteration list */
+    e->iterate_previous = h->iterate_list_tail;
+    e->iterate_next = NULL;
+    if (h->iterate_list_tail) {
+        pa_assert(h->iterate_list_head);
+        h->iterate_list_tail->iterate_next = e;
+    } else {
+        pa_assert(!h->iterate_list_head);
+        h->iterate_list_head = e;
+    }
+    h->iterate_list_tail = e;
+
+    h->n_entries++;
+    pa_assert(h->n_entries >= 1);
+
     return 0;
 }
 
 void* pa_hashmap_get(pa_hashmap *h, const void *key) {
     unsigned hash;
     struct hashmap_entry *e;
-    assert(h && key);
 
-    hash = h->hash_func(key) % h->size;
+    pa_assert(h);
 
-    if (!(e = get(h, hash, key)))
+    hash = h->hash_func(key) % NBUCKETS;
+
+    if (!(e = hash_scan(h, hash, key)))
         return NULL;
 
     return e->value;
@@ -159,38 +188,126 @@ void* pa_hashmap_remove(pa_hashmap *h, const void *key) {
     struct hashmap_entry *e;
     unsigned hash;
     void *data;
-    assert(h && key);
 
-    hash = h->hash_func(key) % h->size;
+    pa_assert(h);
+
+    hash = h->hash_func(key) % NBUCKETS;
 
-    if (!(e = get(h, hash, key)))
+    if (!(e = hash_scan(h, hash, key)))
         return NULL;
 
     data = e->value;
-    remove(h, e);
+    remove_entry(h, e);
+
     return data;
 }
 
-unsigned pa_hashmap_size(pa_hashmap *h) {
-    return h->n_entries;
+void *pa_hashmap_iterate(pa_hashmap *h, void **state, const void **key) {
+    struct hashmap_entry *e;
+
+    pa_assert(h);
+    pa_assert(state);
+
+    if (*state == (void*) -1)
+        goto at_end;
+
+    if (!*state && !h->iterate_list_head)
+        goto at_end;
+
+    e = *state ? *state : h->iterate_list_head;
+
+    if (e->iterate_next)
+        *state = e->iterate_next;
+    else
+        *state = (void*) -1;
+
+    if (key)
+        *key = e->key;
+
+    return e->value;
+
+at_end:
+    *state = (void *) -1;
+
+    if (key)
+        *key = NULL;
+
+    return NULL;
 }
 
-void *pa_hashmap_iterate(pa_hashmap *h, void **state, const void **key) {
-    assert(h && state);
+void *pa_hashmap_iterate_backwards(pa_hashmap *h, void **state, const void **key) {
+    struct hashmap_entry *e;
+
+    pa_assert(h);
+    pa_assert(state);
+
+    if (*state == (void*) -1)
+        goto at_beginning;
 
-    if (!*state) 
-        *state = h->first_entry;
+    if (!*state && !h->iterate_list_tail)
+        goto at_beginning;
+
+    e = *state ? *state : h->iterate_list_tail;
+
+    if (e->iterate_previous)
+        *state = e->iterate_previous;
     else
-        *state = ((struct hashmap_entry*) *state)->next;
+        *state = (void*) -1;
 
-    if (!*state) {
-        if (key)
-            *key = NULL;
-        return NULL;
-    }
+    if (key)
+        *key = e->key;
+
+    return e->value;
+
+at_beginning:
+    *state = (void *) -1;
 
     if (key)
-        *key = ((struct hashmap_entry*) *state)->key;
-    
-    return ((struct hashmap_entry*) *state)->value;
+        *key = NULL;
+
+    return NULL;
+}
+
+void* pa_hashmap_first(pa_hashmap *h) {
+    pa_assert(h);
+
+    if (!h->iterate_list_head)
+        return NULL;
+
+    return h->iterate_list_head->value;
+}
+
+void* pa_hashmap_last(pa_hashmap *h) {
+    pa_assert(h);
+
+    if (!h->iterate_list_tail)
+        return NULL;
+
+    return h->iterate_list_tail->value;
+}
+
+void* pa_hashmap_steal_first(pa_hashmap *h) {
+    void *data;
+
+    pa_assert(h);
+
+    if (!h->iterate_list_head)
+        return NULL;
+
+    data = h->iterate_list_head->value;
+    remove_entry(h, h->iterate_list_head);
+
+    return data;
+}
+
+unsigned pa_hashmap_size(pa_hashmap *h) {
+    pa_assert(h);
+
+    return h->n_entries;
+}
+
+pa_bool_t pa_hashmap_isempty(pa_hashmap *h) {
+    pa_assert(h);
+
+    return h->n_entries == 0;
 }