idxset: Add reverse iteration functions

Add complementary functions to the existing idxset iterate(),
steal_first(), first(), next() functions that work in the reverse
direction: reverse_iterate(), steal_last(), last() and previous().

Signed-off-by: Alper Nebi Yasak <alpernebiyasak@gmail.com>
Part-of: <https://gitlab.freedesktop.org/pulseaudio/pulseaudio/-/merge_requests/596>

2 files changed, 123 insertions, 6 deletions

diff --git a/src/pulsecore/idxset.c b/src/pulsecore/idxset.c
index b5dd9b3e1..324894d01 100644
--- a/src/pulsecore/idxset.c
+++ b/src/pulsecore/idxset.c
@@ -381,6 +381,39 @@ at_end:
     return NULL;
 }
 
+void *pa_idxset_reverse_iterate(pa_idxset *s, void **state, uint32_t *idx) {
+    struct idxset_entry *e;
+
+    pa_assert(s);
+    pa_assert(state);
+
+    if (*state == (void*) -1)
+        goto at_end;
+
+    if ((!*state && !s->iterate_list_tail))
+        goto at_end;
+
+    e = *state ? *state : s->iterate_list_tail;
+
+    if (e->iterate_previous)
+        *state = e->iterate_previous;
+    else
+        *state = (void*) -1;
+
+    if (idx)
+        *idx = e->idx;
+
+    return e->data;
+
+at_end:
+    *state = (void *) -1;
+
+    if (idx)
+        *idx = PA_IDXSET_INVALID;
+
+    return NULL;
+}
+
 void* pa_idxset_steal_first(pa_idxset *s, uint32_t *idx) {
     void *data;
 
@@ -399,6 +432,24 @@ void* pa_idxset_steal_first(pa_idxset *s, uint32_t *idx) {
     return data;
 }
 
+void* pa_idxset_steal_last(pa_idxset *s, uint32_t *idx) {
+    void *data;
+
+    pa_assert(s);
+
+    if (!s->iterate_list_tail)
+        return NULL;
+
+    data = s->iterate_list_tail->data;
+
+    if (idx)
+        *idx = s->iterate_list_tail->idx;
+
+    remove_entry(s, s->iterate_list_tail);
+
+    return data;
+}
+
 void* pa_idxset_first(pa_idxset *s, uint32_t *idx) {
     pa_assert(s);
 
@@ -414,6 +465,21 @@ void* pa_idxset_first(pa_idxset *s, uint32_t *idx) {
     return s->iterate_list_head->data;
 }
 
+void* pa_idxset_last(pa_idxset *s, uint32_t *idx) {
+    pa_assert(s);
+
+    if (!s->iterate_list_tail) {
+        if (idx)
+            *idx = PA_IDXSET_INVALID;
+        return NULL;
+    }
+
+    if (idx)
+        *idx = s->iterate_list_tail->idx;
+
+    return s->iterate_list_tail->data;
+}
+
 void *pa_idxset_next(pa_idxset *s, uint32_t *idx) {
     struct idxset_entry *e;
     unsigned hash;
@@ -458,6 +524,50 @@ void *pa_idxset_next(pa_idxset *s, uint32_t *idx) {
     }
 }
 
+void *pa_idxset_previous(pa_idxset *s, uint32_t *idx) {
+    struct idxset_entry *e;
+    unsigned hash;
+
+    pa_assert(s);
+    pa_assert(idx);
+
+    if (*idx == PA_IDXSET_INVALID)
+        return NULL;
+
+    hash = *idx % NBUCKETS;
+
+    if ((e = index_scan(s, hash, *idx))) {
+
+        e = e->iterate_previous;
+
+        if (e) {
+            *idx = e->idx;
+            return e->data;
+        } else {
+            *idx = PA_IDXSET_INVALID;
+            return NULL;
+        }
+
+    } else {
+
+        /* If the entry passed doesn't exist anymore we try to find
+         * the preceding one. */
+
+        for ((*idx)--; *idx < s->current_index; (*idx)--) {
+
+            hash = *idx % NBUCKETS;
+
+            if ((e = index_scan(s, hash, *idx))) {
+                *idx = e->idx;
+                return e->data;
+            }
+        }
+
+        *idx = PA_IDXSET_INVALID;
+        return NULL;
+    }
+}
+
 unsigned pa_idxset_size(pa_idxset*s) {
     pa_assert(s);
 
diff --git a/src/pulsecore/idxset.h b/src/pulsecore/idxset.h
index ee530bf2b..dbc4187d9 100644
--- a/src/pulsecore/idxset.h
+++ b/src/pulsecore/idxset.h
@@ -88,18 +88,25 @@ void* pa_idxset_rrobin(pa_idxset *s, uint32_t *idx);
 
 /* Iterate through the idxset. At first iteration state should be NULL */
 void *pa_idxset_iterate(pa_idxset *s, void **state, uint32_t *idx);
+void *pa_idxset_reverse_iterate(pa_idxset *s, void **state, uint32_t *idx);
 
-/* Return the oldest entry in the idxset and remove it. If idx is not NULL fill in its index in *idx */
+/* Return the oldest or newest entry in the idxset and remove it.
+ * If idx is not NULL fill in its index in *idx */
 void* pa_idxset_steal_first(pa_idxset *s, uint32_t *idx);
+void* pa_idxset_steal_last(pa_idxset *s, uint32_t *idx);
 
-/* Return the oldest entry in the idxset. Fill in its index in *idx. */
+/* Return the oldest or newest entry in the idxset.
+ * Fill in its index in *idx. */
 void* pa_idxset_first(pa_idxset *s, uint32_t *idx);
+void* pa_idxset_last(pa_idxset *s, uint32_t *idx);
 
-/* Return the entry following the entry indexed by *idx.  After the
- * call *index contains the index of the returned
- * object. pa_idxset_first() and pa_idxset_next() may be used to
- * iterate through the set.*/
+/* Return the entry following or preceding the entry indexed by *idx.
+ * After the call *index contains the index of the returned object.
+ * pa_idxset_first() and pa_idxset_next() may be used to iterate through
+ * the set. pa_idxset_last() and pa_idxset_previous() may be used to
+ * iterate through the set in reverse. */
 void *pa_idxset_next(pa_idxset *s, uint32_t *idx);
+void *pa_idxset_previous(pa_idxset *s, uint32_t *idx);
 
 /* Return the current number of entries in the idxset */
 unsigned pa_idxset_size(pa_idxset*s);