Thanks for the review, really good points, adopt both,
On Tue, Jun 2, 2015 at 12:57 PM, Andy Zhou <az...@nicira.com> wrote:
> 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
