Re: [igt-dev] [PATCH i-g-t v23 03/37] lib/igt_list: igt_hlist implementation.

[Daniel Vetter <daniel@ffwll.ch>]

On Mon, Mar 15, 2021 at 05:58:08PM +0100, Zbigniew Kempczyński wrote:
> From: Dominik Grzegorzek <dominik.grzegorzek@intel.com>
> 
> Double linked lists with a single pointer list head implementation,
> based on similar in the kernel.
> 
> Signed-off-by: Dominik Grzegorzek <dominik.grzegorzek@intel.com>
> Cc: Zbigniew Kempczyński <zbigniew.kempczynski@intel.com>
> Cc: Chris Wilson <chris@chris-wilson.co.uk>

igt doc for any new library should be here, but a) we've been
unfortunately very sloppy with that in a lot of areas and b) totally fine
to fix this in a follow up patch.

Acked-by: Daniel Vetter <daniel.vetter@ffwll.ch>
> ---
>  lib/igt_list.c | 72 ++++++++++++++++++++++++++++++++++++++++++++++++++
>  lib/igt_list.h | 50 +++++++++++++++++++++++++++++++++--
>  2 files changed, 120 insertions(+), 2 deletions(-)
> 
> diff --git a/lib/igt_list.c b/lib/igt_list.c
> index 37ae139c4..43200f9b3 100644
> --- a/lib/igt_list.c
> +++ b/lib/igt_list.c
> @@ -22,6 +22,7 @@
>   *
>   */
>  
> +#include "assert.h"
>  #include "igt_list.h"
>  
>  void IGT_INIT_LIST_HEAD(struct igt_list_head *list)
> @@ -81,3 +82,74 @@ bool igt_list_empty(const struct igt_list_head *head)
>  {
>  	return head->next == head;
>  }
> +
> +void igt_hlist_init(struct igt_hlist_node *h)
> +{
> +	h->next = NULL;
> +	h->pprev = NULL;
> +}
> +
> +int igt_hlist_unhashed(const struct igt_hlist_node *h)
> +{
> +	return !h->pprev;
> +}
> +
> +int igt_hlist_empty(const struct igt_hlist_head *h)
> +{
> +	return !h->first;
> +}
> +
> +static void __igt_hlist_del(struct igt_hlist_node *n)
> +{
> +	struct igt_hlist_node *next = n->next;
> +	struct igt_hlist_node **pprev = n->pprev;
> +
> +	*pprev = next;
> +	if (next)
> +		next->pprev = pprev;
> +}
> +
> +void igt_hlist_del(struct igt_hlist_node *n)
> +{
> +	__igt_hlist_del(n);
> +	n->next = NULL;
> +	n->pprev = NULL;
> +}
> +
> +void igt_hlist_del_init(struct igt_hlist_node *n)
> +{
> +	if (!igt_hlist_unhashed(n)) {
> +		__igt_hlist_del(n);
> +		igt_hlist_init(n);
> +	}
> +}
> +
> +void igt_hlist_add_head(struct igt_hlist_node *n, struct igt_hlist_head *h)
> +{
> +	struct igt_hlist_node *first = h->first;
> +
> +	n->next = first;
> +	if (first)
> +		first->pprev = &n->next;
> +	h->first = n;
> +	n->pprev = &h->first;
> +}
> +
> +void igt_hlist_add_before(struct igt_hlist_node *n, struct igt_hlist_node *next)
> +{
> +	assert(next);
> +	n->pprev = next->pprev;
> +	n->next = next;
> +	next->pprev = &n->next;
> +	*(n->pprev) = n;
> +}
> +
> +void igt_hlist_add_behind(struct igt_hlist_node *n, struct igt_hlist_node *prev)
> +{
> +	n->next = prev->next;
> +	prev->next = n;
> +	n->pprev = &prev->next;
> +
> +	if (n->next)
> +		n->next->pprev  = &n->next;
> +}
> diff --git a/lib/igt_list.h b/lib/igt_list.h
> index cc93d7a0d..78e761e05 100644
> --- a/lib/igt_list.h
> +++ b/lib/igt_list.h
> @@ -40,6 +40,10 @@
>   * igt_list is a doubly-linked list where an instance of igt_list_head is a
>   * head sentinel and has to be initialized.
>   *
> + * igt_hist is also an double linked lists, but with a single pointer list head.
> + * Mostly useful for hash tables where the two pointer list head is
> + * too wasteful. You lose the ability to access the tail in O(1).
> + *
>   * Example usage:
>   *
>   * |[<!-- language="C" -->
> @@ -71,6 +75,13 @@ struct igt_list_head {
>  	struct igt_list_head *next;
>  };
>  
> +struct igt_hlist_head {
> +	struct igt_hlist_node *first;
> +};
> +
> +struct igt_hlist_node {
> +	struct igt_hlist_node *next, **pprev;
> +};
>  
>  void IGT_INIT_LIST_HEAD(struct igt_list_head *head);
>  void igt_list_add(struct igt_list_head *elem, struct igt_list_head *head);
> @@ -81,6 +92,17 @@ void igt_list_move_tail(struct igt_list_head *elem, struct igt_list_head *list);
>  int igt_list_length(const struct igt_list_head *head);
>  bool igt_list_empty(const struct igt_list_head *head);
>  
> +void igt_hlist_init(struct igt_hlist_node *h);
> +int igt_hlist_unhashed(const struct igt_hlist_node *h);
> +int igt_hlist_empty(const struct igt_hlist_head *h);
> +void igt_hlist_del(struct igt_hlist_node *n);
> +void igt_hlist_del_init(struct igt_hlist_node *n);
> +void igt_hlist_add_head(struct igt_hlist_node *n, struct igt_hlist_head *h);
> +void igt_hlist_add_before(struct igt_hlist_node *n,
> +			  struct igt_hlist_node *next);
> +void igt_hlist_add_behind(struct igt_hlist_node *n,
> +			  struct igt_hlist_node *prev);
> +
>  #define igt_container_of(ptr, sample, member)				\
>  	(__typeof__(sample))((char *)(ptr) -				\
>  				offsetof(__typeof__(*sample), member))
> @@ -96,9 +118,10 @@ bool igt_list_empty(const struct igt_list_head *head);
>   * Safe against removel of the *current* list element. To achive this it
>   * requires an extra helper variable `tmp` with the same type as `pos`.
>   */
> -#define igt_list_for_each_entry_safe(pos, tmp, head, member)			\
> +
> +#define igt_list_for_each_entry_safe(pos, tmp, head, member)		\
>  	for (pos = igt_container_of((head)->next, pos, member),		\
> -	     tmp = igt_container_of((pos)->member.next, tmp, member); 	\
> +	     tmp = igt_container_of((pos)->member.next, tmp, member);	\
>  	     &pos->member != (head);					\
>  	     pos = tmp,							\
>  	     tmp = igt_container_of((pos)->member.next, tmp, member))
> @@ -108,6 +131,27 @@ bool igt_list_empty(const struct igt_list_head *head);
>  	     &pos->member != (head);					\
>  	     pos = igt_container_of((pos)->member.prev, pos, member))
>  
> +#define igt_list_for_each_entry_safe_reverse(pos, tmp, head, member)		\
> +	for (pos = igt_container_of((head)->prev, pos, member),		\
> +	     tmp = igt_container_of((pos)->member.prev, tmp, member);	\
> +	     &pos->member != (head);					\
> +	     pos = tmp,							\
> +	     tmp = igt_container_of((pos)->member.prev, tmp, member))
> +
> +#define igt_hlist_entry_safe(ptr, sample, member) \
> +	({ typeof(ptr) ____ptr = (ptr); \
> +	   ____ptr ? igt_container_of(____ptr, sample, member) : NULL; \
> +	})
> +
> +#define igt_hlist_for_each_entry(pos, head, member)			\
> +	for (pos = igt_hlist_entry_safe((head)->first, pos, member);	\
> +	     pos;							\
> +	     pos = igt_hlist_entry_safe((pos)->member.next, pos, member))
> +
> +#define igt_hlist_for_each_entry_safe(pos, n, head, member)		\
> +	for (pos = igt_hlist_entry_safe((head)->first, pos, member);	\
> +	     pos && ({ n = pos->member.next; 1; });			\
> +	     pos = igt_hlist_entry_safe(n, pos, member))
>  
>  /* IGT custom helpers */
>  
> @@ -127,4 +171,6 @@ bool igt_list_empty(const struct igt_list_head *head);
>  #define igt_list_last_entry(head, type, member) \
>  	igt_container_of((head)->prev, (type), member)
>  
> +#define IGT_INIT_HLIST_HEAD(ptr) ((ptr)->first = NULL)
> +
>  #endif /* IGT_LIST_H */
> -- 
> 2.26.0
> 
> _______________________________________________
> igt-dev mailing list
> igt-dev@lists.freedesktop.org
> https://lists.freedesktop.org/mailman/listinfo/igt-dev

-- 
Daniel Vetter
Software Engineer, Intel Corporation
http://blog.ffwll.ch
_______________________________________________
igt-dev mailing list
igt-dev@lists.freedesktop.org
https://lists.freedesktop.org/mailman/listinfo/igt-dev