htable: add a htable_prev method to oppose _next

Useful for unwinding actions taken while iterating over a htable.

Signed-off-by: Cody P Schafer <dev@codyps.com>

diff --git a/ccan/htable/htable.c b/ccan/htable/htable.c
index 59048dc0ada0df95b23583e0dfbba65d3c96768c..5a773cd8876d2f36b53733c659757213811651ff 100644 (file)
--- a/ccan/htable/htable.c
+++ b/ccan/htable/htable.c
@@ -135,6 +135,17 @@ void *htable_next(const struct htable *ht, struct htable_iter *i)
        return NULL;
 }
 
        return NULL;
 }
 

+void *htable_prev(const struct htable *ht, struct htable_iter *i)
+{
+       for (;;) {
+               if (!i->off)
+                       return NULL;
+               i->off --;
+               if (entry_is_valid(ht->table[i->off]))
+                       return get_raw_ptr(ht, ht->table[i->off]);
+       }
+}
+

 /* This does not expand the hash table, that's up to caller. */
 static void ht_add(struct htable *ht, const void *new, size_t h)
 {
 /* This does not expand the hash table, that's up to caller. */
 static void ht_add(struct htable *ht, const void *new, size_t h)
 {

diff --git a/ccan/htable/htable.h b/ccan/htable/htable.h
index 03193567d847a5512b31d173bcb8a21a6d54d09e..e150c2ef0958065d3e289482d78dfe8267017a9b 100644 (file)
--- a/ccan/htable/htable.h
+++ b/ccan/htable/htable.h
@@ -178,6 +178,21 @@ void *htable_first(const struct htable *htable, struct htable_iter *i);
  */
 void *htable_next(const struct htable *htable, struct htable_iter *i);
 
  */
 void *htable_next(const struct htable *htable, struct htable_iter *i);
 

+/**
+ * htable_prev - find the previous entry in the hash table
+ * @ht: the hashtable
+ * @i: the struct htable_iter to use
+ *
+ * Get previous entry in the hashtable; NULL if all done.
+ *
+ * "previous" here only means the item that would have been returned by
+ * htable_next() before the item it returned most recently.
+ *
+ * This is usually used in the middle of (or after) a htable_next iteration and
+ * to "unwind" actions taken.
+ */
+void *htable_prev(const struct htable *htable, struct htable_iter *i);
+

 /**
  * htable_delval - remove an iterated pointer from a hash table
  * @ht: the htable
 /**
  * htable_delval - remove an iterated pointer from a hash table
  * @ht: the htable

diff --git a/ccan/htable/htable_type.h b/ccan/htable/htable_type.h
index 15a70fc28d039e31f9285f83a496e14faa09c71f..ba33f139d72a89387c73847b80bab73f47e1ce15 100644 (file)
--- a/ccan/htable/htable_type.h
+++ b/ccan/htable/htable_type.h
@@ -43,6 +43,7 @@
  * Iteration over hashtable is also supported:
  *     type *<name>_first(const struct <name> *ht, struct <name>_iter *i);
  *     type *<name>_next(const struct <name> *ht, struct <name>_iter *i);
  * Iteration over hashtable is also supported:
  *     type *<name>_first(const struct <name> *ht, struct <name>_iter *i);
  *     type *<name>_next(const struct <name> *ht, struct <name>_iter *i);

+ *     type *<name>_prev(const struct <name> *ht, struct <name>_iter *i);

  *
  * It's currently safe to iterate over a changing hashtable, but you might
  * miss an element.  Iteration isn't very efficient, either.
  *
  * It's currently safe to iterate over a changing hashtable, but you might
  * miss an element.  Iteration isn't very efficient, either.


@@ -137,6 +138,11 @@
                                        struct name##_iter *iter)       \
        {                                                               \
                return htable_next(&ht->raw, &iter->i);                 \
                                        struct name##_iter *iter)       \
        {                                                               \
                return htable_next(&ht->raw, &iter->i);                 \

+       }                                                               \
+       static inline UNNEEDED type *name##_prev(const struct name *ht, \
+                                       struct name##_iter *iter)       \
+       {                                                               \
+               return htable_prev(&ht->raw, &iter->i);                 \

        }
 
 #if HAVE_TYPEOF
        }
 
 #if HAVE_TYPEOF

diff --git a/ccan/htable/test/run-type.c b/ccan/htable/test/run-type.c
index 11ce54bac7fd889338893264822ac6be022159ca..51a85ff2a6f455e530e2e2245a273bc841d966d2 100644 (file)
--- a/ccan/htable/test/run-type.c
+++ b/ccan/htable/test/run-type.c
@@ -116,7 +116,7 @@ int main(int argc, char *argv[])
        void *p;
        struct htable_obj_iter iter;
 
        void *p;
        struct htable_obj_iter iter;
 

-       plan_tests(26);
+       plan_tests(27);

        for (i = 0; i < NUM_VALS; i++)
                val[i].key = i;
        dne = i;
        for (i = 0; i < NUM_VALS; i++)
                val[i].key = i;
        dne = i;


@@ -147,6 +147,10 @@ int main(int argc, char *argv[])
        for (p = htable_obj_first(&ht,&iter); p; p = htable_obj_next(&ht, &iter))
                i++;
        ok1(i == NUM_VALS);
        for (p = htable_obj_first(&ht,&iter); p; p = htable_obj_next(&ht, &iter))
                i++;
        ok1(i == NUM_VALS);

+       i = 0;
+       for (p = htable_obj_prev(&ht,&iter); p; p = htable_obj_prev(&ht, &iter))
+               i++;
+       ok1(i == NUM_VALS);

 
        /* Delete all. */
        del_vals(&ht, val, NUM_VALS);
 
        /* Delete all. */
        del_vals(&ht, val, NUM_VALS);

diff --git a/ccan/htable/test/run.c b/ccan/htable/test/run.c
index c5272c151df43686fbae208004d2a51ed951875c..09cde890f7ea34af2e8be9c080ebd472c2b8f21c 100644 (file)
--- a/ccan/htable/test/run.c
+++ b/ccan/htable/test/run.c
@@ -105,7 +105,7 @@ int main(int argc, char *argv[])
        void *p;
        struct htable_iter iter;
 
        void *p;
        struct htable_iter iter;
 

-       plan_tests(35);
+       plan_tests(36);

        for (i = 0; i < NUM_VALS; i++)
                val[i] = i;
        dne = i;
        for (i = 0; i < NUM_VALS; i++)
                val[i] = i;
        dne = i;


@@ -156,6 +156,11 @@ int main(int argc, char *argv[])
                i++;
        ok1(i == NUM_VALS);
 
                i++;
        ok1(i == NUM_VALS);
 

+       i = 0;
+       for (p = htable_prev(&ht, &iter); p; p = htable_prev(&ht, &iter))
+               i++;
+       ok1(i == NUM_VALS);
+

        /* Delete all. */
        del_vals(&ht, val, NUM_VALS);
        ok1(!htable_get(&ht, hash(&val[0], NULL), objcmp, &val[0]));
        /* Delete all. */
        del_vals(&ht, val, NUM_VALS);
        ok1(!htable_get(&ht, hash(&val[0], NULL), objcmp, &val[0]));