From 36021b117b10530bc94e960a3d3d319ff03fe27a Mon Sep 17 00:00:00 2001
From: Lennart Poettering <lennart@poettering.net>
Date: Fri, 27 Jun 2008 20:34:14 +0200
Subject: modernize idxset a bit, reduce memory consumption, get rid of
 pa_idxset_foreach()

---
 src/pulsecore/idxset.c | 387 +++++++++++++++++++++++++------------------------
 1 file changed, 199 insertions(+), 188 deletions(-)

(limited to 'src/pulsecore/idxset.c')

diff --git a/src/pulsecore/idxset.c b/src/pulsecore/idxset.c
index 7c9520a4..fb4497b8 100644
--- a/src/pulsecore/idxset.c
+++ b/src/pulsecore/idxset.c
@@ -1,7 +1,7 @@
 /***
   This file is part of PulseAudio.
 
-  Copyright 2004-2006 Lennart Poettering
+  Copyright 2004-2008 Lennart Poettering
   Copyright 2006 Pierre Ossman <ossman@cendio.se> for Cendio AB
 
   PulseAudio is free software; you can redistribute it and/or modify
@@ -29,29 +29,36 @@
 #include <string.h>
 
 #include <pulse/xmalloc.h>
-#include <pulsecore/macro.h>
+#include <pulsecore/log.h>
 #include <pulsecore/flist.h>
+#include <pulsecore/macro.h>
 
 #include "idxset.h"
 
+#define NBUCKETS 127
+
 struct idxset_entry {
+    uint32_t idx;
     void *data;
-    uint32_t index;
-    unsigned hash_value;
 
-    struct idxset_entry *hash_prev, *hash_next;
-    struct idxset_entry* iterate_prev, *iterate_next;
+    struct idxset_entry *data_next, *data_previous;
+    struct idxset_entry *index_next, *index_previous;
+    struct idxset_entry *iterate_next, *iterate_previous;
 };
 
 struct pa_idxset {
     pa_hash_func_t hash_func;
     pa_compare_func_t compare_func;
 
-    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;
+    uint32_t current_index;
+
+    struct idxset_entry *iterate_list_head, *iterate_list_tail;
+    unsigned n_entries;
 };
 
+#define BY_DATA(i) ((struct idxset_entry**) ((uint8_t*) (i) + PA_ALIGN(sizeof(pa_idxset))))
+#define BY_INDEX(i) (BY_DATA(i) + NBUCKETS)
+
 PA_STATIC_FLIST_DECLARE(entries, 0, pa_xfree);
 
 unsigned pa_idxset_string_hash_func(const void *p) {
@@ -79,131 +86,140 @@ int pa_idxset_trivial_compare_func(const void *a, const void *b) {
 pa_idxset* pa_idxset_new(pa_hash_func_t hash_func, pa_compare_func_t compare_func) {
     pa_idxset *s;
 
-    s = pa_xnew(pa_idxset, 1);
+    s = pa_xmalloc0(PA_ALIGN(sizeof(pa_idxset)) + NBUCKETS*2*sizeof(struct idxset_entry*));
+
     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 = 127;
-    s->hash_table = pa_xnew0(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->current_index = 0;
+    s->n_entries = 0;
     s->iterate_list_head = s->iterate_list_tail = NULL;
 
     return s;
 }
 
-void pa_idxset_free(pa_idxset *s, void (*free_func) (void *p, void *userdata), void *userdata) {
+static void remove_entry(pa_idxset *s, struct idxset_entry *e) {
     pa_assert(s);
+    pa_assert(e);
 
-    while (s->iterate_list_head) {
-        struct idxset_entry *e = s->iterate_list_head;
-        s->iterate_list_head = s->iterate_list_head->iterate_next;
+    /* Remove from iteration linked list */
+    if (e->iterate_next)
+        e->iterate_next->iterate_previous = e->iterate_previous;
+    else
+        s->iterate_list_tail = e->iterate_previous;
 
-        if (free_func)
-            free_func(e->data, userdata);
+    if (e->iterate_previous)
+        e->iterate_previous->iterate_next = e->iterate_next;
+    else
+        s->iterate_list_head = e->iterate_next;
+
+    /* Remove from data hash table */
+    if (e->data_next)
+        e->data_next->data_previous = e->data_previous;
 
-        if (pa_flist_push(PA_STATIC_FLIST_GET(entries), e) < 0)
-            pa_xfree(e);
+    if (e->data_previous)
+        e->data_previous->data_next = e->data_next;
+    else {
+        unsigned hash = s->hash_func(e->data) % NBUCKETS;
+        BY_DATA(s)[hash] = e->data_next;
     }
 
-    pa_xfree(s->hash_table);
-    pa_xfree(s->array);
-    pa_xfree(s);
-}
+    /* Remove from index hash table */
+    if (e->index_next)
+        e->index_next->index_previous = e->index_previous;
 
-static struct idxset_entry* hash_scan(pa_idxset *s, struct idxset_entry* e, const void *p) {
-    pa_assert(p);
+    if (e->index_previous)
+        e->index_previous->index_next = e->index_next;
+    else
+        BY_INDEX(s)[e->idx % NBUCKETS] = e->index_next;
 
-    pa_assert(s->compare_func);
-    for (; e; e = e->hash_next)
-        if (s->compare_func(e->data, p) == 0)
-            return e;
+    if (pa_flist_push(PA_STATIC_FLIST_GET(entries), e) < 0)
+        pa_xfree(e);
 
-    return NULL;
+    pa_assert(s->n_entries >= 1);
+    s->n_entries--;
 }
 
-static void extend_array(pa_idxset *s, uint32_t idx) {
-    uint32_t i, j, l;
-    struct idxset_entry** n;
-
+void pa_idxset_free(pa_idxset *s, pa_free2_cb_t free_cb, void *userdata) {
     pa_assert(s);
-    pa_assert(idx >= s->start_index);
 
-    if (idx < s->start_index + s->array_size)
-        return;
+    while (s->iterate_list_head) {
+        void *data = s->iterate_list_head->data;
 
-    for (i = 0; i < s->array_size; i++)
-        if (s->array[i])
-            break;
+        remove_entry(s, s->iterate_list_head);
 
-    l = idx - s->start_index - i + 100;
-    n = pa_xnew0(struct idxset_entry*, l);
+        if (free_cb)
+            free_cb(data, userdata);
+    }
 
-    for (j = 0; j < s->array_size-i; j++)
-        n[j] = s->array[i+j];
+    pa_xfree(s);
+}
 
-    pa_xfree(s->array);
+static struct idxset_entry* data_scan(pa_idxset *s, unsigned hash, const void *p) {
+    struct idxset_entry *e;
+    pa_assert(s);
+    pa_assert(hash < NBUCKETS);
+    pa_assert(p);
 
-    s->array = n;
-    s->array_size = l;
-    s->start_index += i;
+    for (e = BY_DATA(s)[hash]; e; e = e->data_next)
+        if (s->compare_func(e->data, p) == 0)
+            return e;
+
+    return NULL;
 }
 
-static struct idxset_entry** array_index(pa_idxset*s, uint32_t idx) {
+static struct idxset_entry* index_scan(pa_idxset *s, unsigned hash, uint32_t idx) {
+    struct idxset_entry *e;
     pa_assert(s);
+    pa_assert(hash < NBUCKETS);
 
-    if (idx >= s->start_index + s->array_size)
-        return NULL;
-
-    if (idx < s->start_index)
-        return NULL;
+    for (e = BY_INDEX(s)[hash]; e; e = e->index_next)
+        if (e->idx == idx)
+            return e;
 
-    return s->array + idx - s->start_index;
+    return NULL;
 }
 
 int pa_idxset_put(pa_idxset*s, void *p, uint32_t *idx) {
-    unsigned h;
-    struct idxset_entry *e, **a;
+    unsigned hash;
+    struct idxset_entry *e;
 
     pa_assert(s);
-    pa_assert(p);
 
-    pa_assert(s->hash_func);
-    h = s->hash_func(p) % s->hash_table_size;
+    hash = s->hash_func(p) % NBUCKETS;
 
-    pa_assert(s->hash_table);
-    if ((e = hash_scan(s, s->hash_table[h], p))) {
+    if ((e = data_scan(s, hash, p))) {
         if (idx)
-            *idx = e->index;
+            *idx = e->idx;
 
         return -1;
     }
 
     if (!(e = pa_flist_pop(PA_STATIC_FLIST_GET(entries))))
         e = pa_xnew(struct idxset_entry, 1);
+
     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);
-    pa_assert(a && !*a);
-    *a = e;
-
-    /* Insert into linked list */
+    e->idx = s->current_index++;
+
+    /* Insert into data hash table */
+    e->data_next = BY_DATA(s)[hash];
+    e->data_previous = NULL;
+    if (BY_DATA(s)[hash])
+        BY_DATA(s)[hash]->data_previous = e;
+    BY_DATA(s)[hash] = e;
+
+    hash = e->idx % NBUCKETS;
+
+    /* Insert into index hash table */
+    e->index_next = BY_INDEX(s)[hash];
+    e->index_previous = NULL;
+    if (BY_INDEX(s)[hash])
+        BY_INDEX(s)[hash]->index_previous = e;
+    BY_INDEX(s)[hash] = e;
+
+    /* Insert into iteration list */
+    e->iterate_previous = s->iterate_list_tail;
     e->iterate_next = NULL;
-    e->iterate_prev = s->iterate_list_tail;
     if (s->iterate_list_tail) {
         pa_assert(s->iterate_list_head);
         s->iterate_list_tail->iterate_next = e;
@@ -217,117 +233,76 @@ int pa_idxset_put(pa_idxset*s, void *p, uint32_t *idx) {
     pa_assert(s->n_entries >= 1);
 
     if (idx)
-        *idx = e->index;
+        *idx = e->idx;
 
     return 0;
 }
 
 void* pa_idxset_get_by_index(pa_idxset*s, uint32_t idx) {
-    struct idxset_entry **a;
+    unsigned hash;
+    struct idxset_entry *e;
+
     pa_assert(s);
 
-    if (!(a = array_index(s, idx)))
-        return NULL;
+    hash = idx % NBUCKETS;
 
-    if (!*a)
+    if (!(e = index_scan(s, hash, idx)))
         return NULL;
 
-    return (*a)->data;
+    return e->data;
 }
 
 void* pa_idxset_get_by_data(pa_idxset*s, const void *p, uint32_t *idx) {
-    unsigned h;
+    unsigned hash;
     struct idxset_entry *e;
 
     pa_assert(s);
-    pa_assert(p);
 
-    pa_assert(s->hash_func);
-    h = s->hash_func(p) % s->hash_table_size;
+    hash = s->hash_func(p) % NBUCKETS;
 
-    pa_assert(s->hash_table);
-    if (!(e = hash_scan(s, s->hash_table[h], p)))
+    if (!(e = data_scan(s, hash, p)))
         return NULL;
 
     if (idx)
-        *idx = e->index;
+        *idx = e->idx;
 
     return e->data;
 }
 
-static void remove_entry(pa_idxset *s, struct idxset_entry *e) {
-    struct idxset_entry **a;
-
-    pa_assert(s);
-    pa_assert(e);
-
-    /* Remove from array */
-    a = array_index(s, e->index);
-    pa_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;
-
-    if (pa_flist_push(PA_STATIC_FLIST_GET(entries), e) < 0)
-        pa_xfree(e);
-
-    pa_assert(s->n_entries >= 1);
-    s->n_entries--;
-}
-
 void* pa_idxset_remove_by_index(pa_idxset*s, uint32_t idx) {
-    struct idxset_entry **a;
+    struct idxset_entry *e;
+    unsigned hash;
     void *data;
 
     pa_assert(s);
 
-    if (!(a = array_index(s, idx)))
-        return NULL;
+    hash = idx % NBUCKETS;
 
-    if (!*a)
+    if (!(e = index_scan(s, hash, idx)))
         return NULL;
 
-    data = (*a)->data;
-    remove_entry(s, *a);
+    data = e->data;
+    remove_entry(s, e);
 
     return data;
 }
 
 void* pa_idxset_remove_by_data(pa_idxset*s, const void *data, uint32_t *idx) {
     struct idxset_entry *e;
-    unsigned h;
+    unsigned hash;
     void *r;
 
     pa_assert(s);
 
-    pa_assert(s->hash_func);
-    h = s->hash_func(data) % s->hash_table_size;
+    hash = s->hash_func(data) % NBUCKETS;
 
-    pa_assert(s->hash_table);
-    if (!(e = hash_scan(s, s->hash_table[h], data)))
+    if (!(e = data_scan(s, hash, data)))
         return NULL;
 
     r = e->data;
+
     if (idx)
-        *idx = e->index;
+        *idx = e->idx;
 
     remove_entry(s, e);
 
@@ -335,76 +310,113 @@ void* pa_idxset_remove_by_data(pa_idxset*s, const void *data, uint32_t *idx) {
 }
 
 void* pa_idxset_rrobin(pa_idxset *s, uint32_t *idx) {
-    struct idxset_entry **a, *e = NULL;
+    unsigned hash;
+    struct idxset_entry *e;
 
     pa_assert(s);
     pa_assert(idx);
 
-    if ((a = array_index(s, *idx)) && *a)
-        e = (*a)->iterate_next;
+    hash = *idx % NBUCKETS;
 
-    if (!e)
+    if (!(e = index_scan(s, hash, *idx)))
+        return NULL;
+
+    if (e && e->iterate_next)
+        e = e->iterate_next;
+    else
         e = s->iterate_list_head;
 
     if (!e)
         return NULL;
 
-    *idx = e->index;
+    *idx = e->idx;
     return e->data;
 }
 
-void* pa_idxset_first(pa_idxset *s, uint32_t *idx) {
+void *pa_idxset_iterate(pa_idxset *s, void **state, uint32_t *idx) {
+    struct idxset_entry *e;
+
     pa_assert(s);
+    pa_assert(state);
 
-    if (!s->iterate_list_head)
-        return NULL;
+    if (*state == (void*) -1)
+        goto at_end;
+
+    if ((!*state && !s->iterate_list_head))
+        goto at_end;
+
+    e = *state ? *state : s->iterate_list_head;
+
+    if (e->iterate_next)
+        *state = e->iterate_next;
+    else
+        *state = (void*) -1;
 
     if (idx)
-        *idx = s->iterate_list_head->index;
-    return s->iterate_list_head->data;
+        *idx = e->idx;
+
+    return e->data;
+
+at_end:
+    *state = (void *) -1;
+
+    if (idx)
+        *idx = PA_IDXSET_INVALID;
+
+    return NULL;
 }
 
-void *pa_idxset_next(pa_idxset *s, uint32_t *idx) {
-    struct idxset_entry **a, *e = NULL;
+void* pa_idxset_steal_first(pa_idxset *s, uint32_t *idx) {
+    void *data;
 
     pa_assert(s);
-    pa_assert(idx);
 
-    if ((a = array_index(s, *idx)) && *a)
-        e = (*a)->iterate_next;
+    if (!s->iterate_list_head)
+        return NULL;
 
-    if (e) {
-        *idx = e->index;
-        return e->data;
-    } else {
-        *idx = PA_IDXSET_INVALID;
+    data = s->iterate_list_head->data;
+
+    if (idx)
+        *idx = s->iterate_list_head->idx;
+
+    remove_entry(s, s->iterate_list_head);
+
+    return data;
+}
+
+void* pa_idxset_first(pa_idxset *s, uint32_t *idx) {
+    pa_assert(s);
+
+    if (!s->iterate_list_head)
         return NULL;
-    }
+
+    if (idx)
+        *idx = s->iterate_list_head->idx;
+
+    return s->iterate_list_head->data;
 }
 
-int pa_idxset_foreach(pa_idxset*s, int (*func)(void *p, uint32_t idx, int *del, void*userdata), void *userdata) {
+void *pa_idxset_next(pa_idxset *s, uint32_t *idx) {
     struct idxset_entry *e;
+    unsigned hash;
 
     pa_assert(s);
-    pa_assert(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);
+    pa_assert(idx);
 
-        if (del)
-            remove_entry(s, e);
+    hash = *idx % NBUCKETS;
 
-        if (r < 0)
-            return r;
+    if (!(e = index_scan(s, hash, *idx)))
+        return NULL;
 
-        e = n;
+    if (!e->iterate_next) {
+        *idx = PA_IDXSET_INVALID;
+        return NULL;
     }
 
-    return 0;
+    e = e->iterate_next;
+
+    *idx = e->idx;
+    return e->data;
 }
 
 unsigned pa_idxset_size(pa_idxset*s) {
@@ -413,9 +425,8 @@ unsigned pa_idxset_size(pa_idxset*s) {
     return s->n_entries;
 }
 
-int pa_idxset_isempty(pa_idxset *s) {
+pa_bool_t pa_idxset_isempty(pa_idxset *s) {
     pa_assert(s);
 
     return s->n_entries == 0;
 }
-
-- 
cgit