On Mon, Jun 1, 2015 at 11:24 AM, Alex Wang <al...@nicira.com> wrote:
> 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>
> ---
> RFC->RFC V2:
> - Adopt Ben's suggestions.
>
> ---
> lib/list.h | 48 ++++++++++++++++++++++++
> tests/library.at | 2 +-
> tests/test-list.c | 106
> +++++++++++++++++++++++++++++++++++++++++++++++++++++
> 3 files changed, 155 insertions(+), 1 deletion(-)
>
> diff --git a/lib/list.h b/lib/list.h
> index 7ba1e35..229f1c3 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 *);
> @@ -104,6 +108,14 @@ 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)
> +{
> + list_splice(dst, src->next, src);
> +}
> +
> /* Removes elements 'first' though 'last' (exclusive) from their current
> list,
> then inserts them just before 'before'. */
> static inline void
> @@ -152,6 +164,25 @@ list_replace(struct ovs_list *element, const struct
> ovs_list *position)
> element->prev->next = element;
> }
>
> +/* Exchanges the positions of A and B, which may be in the same list
> + * or different lists. */
May need to check for list_empty() for a and b, or make it clear in
the comment that they
are not expected.
> +static inline void
> +list_swap(struct ovs_list *a, struct ovs_list *b)
> +{
> + if (a != b) {
> + if (a->next != b) {
> + struct ovs_list *a_next = list_remove(a);
> + struct ovs_list *b_next = list_remove(b);
> +
> + list_insert(b_next, a);
> + list_insert(a_next, b);
> + } else {
> + list_remove(b);
> + list_insert(a, b);
> + }
> + }
> +}
> +
> /* 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'.
> @@ -236,6 +267,23 @@ 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) {
How about change to if (!n--)? We don't need to maintain the 'cnt' variable.
> + return ret;
> + }
> + }
> + OVS_NOT_REACHED();
> +}
> +
> /* 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 9bd6d81..cb1f858 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 9b6b0bd..5c16990 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"
> @@ -185,6 +186,107 @@ test_list_for_each_pop(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();
> @@ -197,6 +299,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_for_each_pop);
> + 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
_______________________________________________
dev mailing list
dev@openvswitch.org
http://openvswitch.org/mailman/listinfo/dev
