[ovs-dev] [RFC HSA 1/4] ovs_list: Extend list functions.

[Ben Pfaff]

On Mon, Mar 30, 2015 at 03:46:26PM -0700, Alex Wang 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 <alexw at nicira.com>

I always like new basic algorithms!

> +/* 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);
> +}

I think that list_join() can be simplified to just:
    list_splice(dst, src->next, src);
because if 'src' is empty then src->next == next and list_splice()
will become a no-op because of its test for first == last.

> +/* 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);
> +    }
> +}

I think that list_swap() can be simplified to the following, although I
have not tested it:

    /* Exchanges the positions of A and B, which may be in the same list
     * or different lists. */
    void
    ovs_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'.
> @@ -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;
> +        }
> +    }

I'd probably just write the following two statements as OVS_NOT_REACHED():
> +    ovs_assert(false);
> +
> +    return NULL;
> +}

Thanks,

Ben.