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

[Zbigniew Kempczyński]

From: Dominik Grzegorzek <dominik.grzegorzek at 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 at intel.com>
Cc: Zbigniew Kempczyński <zbigniew.kempczynski at intel.com>
Cc: Chris Wilson <chris at chris-wilson.co.uk>
---
 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