This commit adds function that allows the appending of one list
content to the other. Also, it adds functions which allows list
to be sorted.
Signed-off-by: Alex Wang <al...@nicira.com>
---
lib/list.h | 67 +++++++++++++++++++++++++++++++++
tests/library.at | 2 +-
tests/test-list.c | 106 +++++++++++++++++++++++++++++++++++++++++++++++++++++
3 files changed, 174 insertions(+), 1 deletion(-)
diff --git a/lib/list.h b/lib/list.h
index b40bbef..76f930c 100644
--- a/lib/list.h
+++ b/lib/list.h
@@ -30,10 +30,12 @@ static inline void list_poison(struct ovs_list *);
static inline void list_insert(struct ovs_list *, struct ovs_list *);
static inline void list_splice(struct ovs_list *before, struct ovs_list *first,
struct ovs_list *last);
+static inline void list_join(struct ovs_list *dst, struct ovs_list *src);
static inline void list_push_front(struct ovs_list *, struct ovs_list *);
static inline void list_push_back(struct ovs_list *, struct ovs_list *);
static inline void list_replace(struct ovs_list *, const struct ovs_list *);
static inline void list_moved(struct ovs_list *, const struct ovs_list *orig);
+static inline void list_swap(struct ovs_list *, struct ovs_list *);
static inline void list_move(struct ovs_list *dst, struct ovs_list *src);
/* List removal. */
@@ -44,6 +46,8 @@ static inline struct ovs_list *list_pop_back(struct ovs_list
*);
/* List elements. */
static inline struct ovs_list *list_front(const struct ovs_list *);
static inline struct ovs_list *list_back(const struct ovs_list *);
+static inline struct ovs_list *list_at_position(const struct ovs_list *,
+ size_t n);
/* List properties. */
static inline size_t list_size(const struct ovs_list *);
@@ -101,6 +105,18 @@ list_insert(struct ovs_list *before, struct ovs_list *elem)
before->prev = elem;
}
+/* Appends 'src''s content to the end of 'dst'. After 'list_join', 'src'
+ * becomes an empty list. */
+static inline void
+list_join(struct ovs_list *dst, struct ovs_list *src)
+{
+ if (list_is_empty(src)) {
+ return;
+ }
+
+ list_splice(dst, list_front(src), src);
+}
+
/* Removes elements 'first' though 'last' (exclusive) from their current list,
then inserts them just before 'before'. */
static inline void
@@ -149,6 +165,38 @@ list_replace(struct ovs_list *element, const struct
ovs_list *position)
element->prev->next = element;
}
+/* Swaps the two adjacent list elements. 'ahead' must be ahead of 'after'. */
+static inline void
+list_swap_adjacent(struct ovs_list *ahead, struct ovs_list *after)
+{
+ ahead->next = after->next;
+ ahead->next->prev = ahead;
+ after->prev = ahead->prev;
+ ahead->prev->next = after;
+ ahead->prev = after;
+ after->next = ahead;
+}
+
+/* Swaps the position of two list nodes, 'elem1' and 'elem2'. */
+static inline void
+list_swap(struct ovs_list *elem1, struct ovs_list *elem2)
+{
+ if (elem1 == elem2) {
+ return;
+ } else if (elem1->prev == elem2) {
+ /* element2 is ahead of element1. */
+ list_swap_adjacent(elem2, elem1);
+ } else if (elem2->prev == elem1) {
+ /* element1 is ahead of element2. */
+ list_swap_adjacent(elem1, elem2);
+ } else {
+ const struct ovs_list tmp = *elem1;
+
+ list_replace(elem1, elem2);
+ list_replace(elem2, &tmp);
+ }
+}
+
/* Adjusts pointers around 'list' to compensate for 'list' having been moved
* around in memory (e.g. as a consequence of realloc()), with original
* location 'orig'.
@@ -233,6 +281,25 @@ list_back(const struct ovs_list *list_)
return list->prev;
}
+/* Returns the element at position 'n', assumes the first element is
+ * at index 0. The 'list_' must contain at least 'n' elements. */
+static inline struct ovs_list *
+list_at_position(const struct ovs_list *list_, size_t n)
+{
+ struct ovs_list *list = CONST_CAST(struct ovs_list *, list_);
+ struct ovs_list *ret;
+ size_t cnt = 0;
+
+ for (ret = list->next; ret != list; ret = ret->next) {
+ if (cnt++ == n) {
+ return ret;
+ }
+ }
+ ovs_assert(false);
+
+ return NULL;
+}
+
/* Returns the number of elements in 'list'.
Runs in O(n) in the number of elements. */
static inline size_t
diff --git a/tests/library.at b/tests/library.at
index 2507688..fab7402 100644
--- a/tests/library.at
+++ b/tests/library.at
@@ -38,7 +38,7 @@ AT_CHECK([ovstest test-atomic])
AT_CLEANUP
AT_SETUP([test linked lists])
-AT_CHECK([ovstest test-list], [0], [..
+AT_CHECK([ovstest test-list], [0], [......
])
AT_CLEANUP
diff --git a/tests/test-list.c b/tests/test-list.c
index 5fd7149..3652064 100644
--- a/tests/test-list.c
+++ b/tests/test-list.c
@@ -20,6 +20,7 @@
#include <config.h>
#undef NDEBUG
#include "list.h"
+#include "sort.h"
#include <assert.h>
#include <string.h>
#include "ovstest.h"
@@ -160,6 +161,107 @@ test_list_for_each_safe(void)
}
static void
+test_list_swap_elem(void)
+{
+ enum { MAX_ELEMS = 100 };
+ struct element elements[MAX_ELEMS];
+ int values[MAX_ELEMS];
+ size_t n = MAX_ELEMS;
+ struct ovs_list list;
+
+ make_list(&list, elements, values, n);
+ elements[1].value = 50;
+ elements[50].value = 1;
+ list_swap(&elements[1].node, &elements[50].node);
+ elements[9].value = 10;
+ elements[10].value = 9;
+ list_swap(&elements[9].node, &elements[10].node);
+ elements[19].value = 20;
+ elements[20].value = 19;
+ list_swap(&elements[20].node, &elements[19].node);
+ list_swap(&elements[29].node, &elements[29].node);
+ check_list(&list, values, n);
+}
+
+static void
+test_list_at_position(void)
+{
+ enum { MAX_ELEMS = 10 };
+ struct element elements[MAX_ELEMS];
+ int values[MAX_ELEMS];
+ size_t n = MAX_ELEMS;
+ struct ovs_list list;
+
+ make_list(&list, elements, values, n);
+ for (n = 0; n < MAX_ELEMS; n++) {
+ struct ovs_list *node = list_at_position(&list, n);
+
+ ovs_assert(node == &elements[n].node);
+ }
+}
+
+static int
+test_list_compare(size_t a, size_t b, void *aux)
+{
+ struct ovs_list *list = aux;
+ struct element *elem1, *elem2;
+
+ elem1 = CONTAINER_OF(list_at_position(list, a), struct element, node);
+ elem2 = CONTAINER_OF(list_at_position(list, b), struct element, node);
+
+ return elem1->value - elem2->value;
+}
+
+static void
+test_list_swap(size_t a, size_t b, void *aux)
+{
+ struct ovs_list *list = aux;
+
+ list_swap(list_at_position(list, a), list_at_position(list, b));
+}
+
+static void
+test_list_sort(void)
+{
+ enum { MAX_ELEMS = 10 };
+ struct element elements[MAX_ELEMS];
+ int values[MAX_ELEMS];
+ size_t n = MAX_ELEMS;
+ struct ovs_list list;
+
+ make_list(&list, elements, values, n);
+ for (n = 0; n < MAX_ELEMS; n++) {
+ elements[n].value = MAX_ELEMS - 1 - n;
+ }
+ /* Sorts the list in ascending order of priority. */
+ sort(n, test_list_compare, test_list_swap, &list);
+ check_list(&list, values, n);
+}
+
+static void
+test_list_join(void)
+{
+ enum { MAX_ELEMS = 10 };
+ struct element elements_1[MAX_ELEMS];
+ struct element elements_2[MAX_ELEMS];
+ int values[2*MAX_ELEMS];
+ size_t n = MAX_ELEMS;
+ struct ovs_list list_dst, list_src;
+
+ make_list(&list_dst, elements_1, values, n);
+ make_list(&list_src, elements_2, values, n);
+ /* Makes 'elements_2' contains values {MAX_ELEMS..2*MAX_ELEMS-1}. */
+ for (n = MAX_ELEMS; n < 2*MAX_ELEMS; n++) {
+ elements_2[n-MAX_ELEMS].value += MAX_ELEMS;
+ values[n] = n;
+ }
+
+ list_join(&list_dst, &list_src);
+ assert(list_is_empty(&list_src));
+ check_list(&list_dst, values, 2*MAX_ELEMS);
+}
+
+static void
run_test(void (*function)(void))
{
function();
@@ -171,6 +273,10 @@ test_list_main(int argc OVS_UNUSED, char *argv[]
OVS_UNUSED)
{
run_test(test_list_construction);
run_test(test_list_for_each_safe);
+ run_test(test_list_swap_elem);
+ run_test(test_list_at_position);
+ run_test(test_list_sort);
+ run_test(test_list_join);
printf("\n");
}
--
1.7.9.5
_______________________________________________
dev mailing list
dev@openvswitch.org
http://openvswitch.org/mailman/listinfo/dev
