[virglrenderer-devel] [PATCH 1/5] utils: added intrusive linked-list implem

[Marc-André Lureau]

Hi

On Tue, Jul 24, 2018 at 3:32 PM, Nathan Gauer <nathan at gauer.org> wrote:
> Signed-off-by: Nathan Gauer <nathan at gauer.org>

Consider using src/util/list.h from mesa instead, as this will likely
help if we share more code with mesa.

> ---
>  src/util/list.c | 75 +++++++++++++++++++++++++++++++++++++++++++++++++
>  src/util/list.h | 31 ++++++++++++++++++++
>  2 files changed, 106 insertions(+)
>  create mode 100644 src/util/list.c
>  create mode 100644 src/util/list.h
>
> diff --git a/src/util/list.c b/src/util/list.c
> new file mode 100644
> index 0000000..d214aef
> --- /dev/null
> +++ b/src/util/list.c
> @@ -0,0 +1,75 @@
> +#include <assert.h>
> +#include <stdlib.h>
> +
> +#include "list.h"
> +
> +void list_init(struct list *head)
> +{
> +    head->next = head;
> +    head->prev = head;
> +}
> +
> +size_t list_length(struct list *head)
> +{
> +    size_t len = 0;
> +    struct list *n = head->next;
> +
> +    for (; n != head; n = n->next) {
> +        len += 1;
> +    }
> +
> +    return len;
> +}
> +
> +void list_append(struct list *head, struct list *n)
> +{
> +    assert(head && "invalid list pointer");
> +    assert(n && "invalid elt pointer");
> +
> +
> +    n->next = head;
> +    n->prev = head->prev;
> +    n->prev->next = n;
> +    head->prev = n;
> +}
> +
> +void list_insert(struct list *head, struct list *n, size_t pos)
> +{
> +    assert(head && "invalid list pointer");
> +    assert(n && "invalid elt pointer");
> +
> +    struct list *it = head->next;
> +    for (; pos > 0; pos--) {
> +        if (it == head)
> +            break;
> +
> +        it = it->next;
> +    }
> +
> +    n->prev = it->prev;
> +    n->next = it;
> +    n->prev->next = n;
> +    it->prev = n;
> +}
> +
> +int list_remove(struct list *head, size_t pos)
> +{
> +    assert(head && "invalid list pointer");
> +
> +    struct list *it = head->next;
> +
> +    for (; pos > 0; pos--) {
> +        it = it->next;
> +
> +        if (it == head)
> +            return 1;
> +    }
> +
> +    it->prev->next = it->next;
> +    it->next->prev = it->prev;
> +
> +    it->next = it;
> +    it->prev = it;
> +
> +    return 0;
> +}
> diff --git a/src/util/list.h b/src/util/list.h
> new file mode 100644
> index 0000000..c9269aa
> --- /dev/null
> +++ b/src/util/list.h
> @@ -0,0 +1,31 @@
> +#pragma once
> +
> +#include "stddef.h"
> +
> +struct list {
> +    struct list *next;
> +    struct list *prev;
> +};
> +
> +
> +#define LIST_FOR_EACH(Var, List, Field) \
> +    for (Var = CONTAINER_OF(List.next, typeof(*Var), Field) ; \
> +         &(Var->Field) != &List; \
> +         Var = CONTAINER_OF(Var->Field.next, typeof(*Var), Field))
> +
> +#define CONTAINER_OF(List, Type, Field) \
> +    (Type*)((char*)List - offsetof(Type, Field))
> +
> +
> +#define LIST_FRONT(Var, List, Field) \
> +    it = CONTAINER_OF(List.next, typeof(*Var), Field)
> +
> +#define LIST_BACK(Var, List, Field) \
> +    it = CONTAINER_OF(List.prev, typeof(*Var), Field)
> +
> +void list_init(struct list *head);
> +
> +size_t  list_length(struct list *head);
> +void    list_append(struct list *head, struct list *n);
> +void    list_insert(struct list *head, struct list *n, size_t pos);
> +int     list_remove(struct list *head, size_t pos);
> --
> 2.18.0
>
> _______________________________________________
> virglrenderer-devel mailing list
> virglrenderer-devel at lists.freedesktop.org
> https://lists.freedesktop.org/mailman/listinfo/virglrenderer-devel



-- 
Marc-André Lureau