[PATCH RFC 1/3] list: Introduce list entry pop/peek operations

[PATCH RFC 1/3] list: Introduce list entry pop/peek operations

[Konstantin Khlebnikov]

Introduce macroses:

list_pop_entry
list_pop_last_entry
list_pop_init_entry
list_pop_init_last_entry
list_peek_entry
list_peek_last_entry

as syntax sugar for widely used constructions like this:

while (!list_empty(&list_head)) {
	entry = list_first_entry(&list_head, struct entry, member);
	list_del(&entry->member);
	...
}

with this macro it become:

while (list_pop_entry(&entry, &list_head, member)) {
	...
}

All macros returns true if the list is not empty,
otherwise they not change the output variable.

list_pop_init_* call list_del_init instead list_del.
list_peek_* not remove entries from the list.

Signed-off-by: Konstantin Khlebnikov <khlebnikov@openvz.org>
---
 include/linux/list.h |   88 ++++++++++++++++++++++++++++++++++++++++++++++++++
 1 files changed, 88 insertions(+), 0 deletions(-)

diff --git a/include/linux/list.h b/include/linux/list.h
index 5d57a3a..6a6e9d3 100644
--- a/include/linux/list.h
+++ b/include/linux/list.h
@@ -360,6 +360,94 @@ static inline void list_splice_tail_init(struct list_head *list,
 	list_entry((ptr)->next, type, member)
 
 /**
+ * list_peek_entry - check is list non-empty and return list first entry
+ * @ptr:	the pointer to struct * to save first entry
+ * @head:	the struct list_head pointer.
+ * @member:	the name of the list_struct within the struct.
+ *
+ * Return true if list was not empty and @ptr is changed
+ */
+#define list_peek_entry(ptr, head, member) ({		\
+	bool __empty = list_empty(head);		\
+	if (!__empty)					\
+		*(ptr) = list_first_entry(head, typeof(**(ptr)), member); \
+	(!__empty); })
+
+/**
+ * list_peek_last_entry - check is list non-empty and return list last entry
+ * @ptr:	the pointer to struct * to save last entry
+ * @head:	the struct list_head pointer.
+ * @member:	the name of the list_struct within the struct.
+ *
+ * Return true if list was not empty and @ptr is changed
+ */
+#define list_peek_last_entry(ptr, head, member) ({	\
+	bool __empty = list_empty(head);		\
+	if (!__empty)					\
+		*(ptr) = list_entry((head)->prev, typeof(**(ptr)), member); \
+	(!__empty); })
+
+/**
+ * list_pop_entry - delete and return list first entry
+ * @ptr:	the pointer to struct * whereto save result
+ * @head:	the struct list_head pointer.
+ * @member:	the name of the list_struct within the struct.
+ *
+ * Return true if list was not empty and @ptr is changed
+ */
+#define list_pop_entry(ptr, head, member) ({		\
+	bool __empty = list_empty(head);		\
+	if (!__empty) {					\
+		*(ptr) = list_first_entry(head, typeof(**(ptr)), member); \
+		list_del(&(*(ptr))->member);		\
+	} (!__empty); })
+
+/**
+ * list_pop_init_entry - delete, reinitialise and return list first entry
+ * @ptr:	the pointer to struct * whereto save result
+ * @head:	the struct list_head pointer.
+ * @member:	the name of the list_struct within the struct.
+ *
+ * Return true if list was not empty and @ptr is changed
+ */
+#define list_pop_init_entry(ptr, head, member) ({	\
+	bool __empty = list_empty(head);		\
+	if (!__empty) {					\
+		*(ptr) = list_first_entry(head, typeof(**(ptr)), member); \
+		list_del_init(&(*(ptr))->member);	\
+	} (!__empty); })
+
+/**
+ * list_pop_last_entry - delete and return list last entry
+ * @ptr:	the pointer to struct * whereto save result
+ * @head:	the struct list_head pointer.
+ * @member:	the name of the list_struct within the struct.
+ *
+ * Return true if list was not empty and @ptr is changed
+ */
+#define list_pop_last_entry(ptr, head, member) ({	\
+	bool __empty = list_empty(head);		\
+	if (!__empty) {					\
+		*(ptr) = list_entry((head)->prev, typeof(**(ptr)), member); \
+		list_del(&(*(ptr))->member);		\
+	} (!__empty); })
+
+/**
+ * list_pop_init_last_entry - delete, reinitialise and return list last entry
+ * @ptr:	the pointer to struct * whereto save result
+ * @head:	the struct list_head pointer.
+ * @member:	the name of the list_struct within the struct.
+ *
+ * Return true if list was not empty and @ptr is changed
+ */
+#define list_pop_init_last_entry(ptr, head, member) ({	\
+	bool __empty = list_empty(head);		\
+	if (!__empty) {					\
+		*(ptr) = list_entry((head)->prev, typeof(**(ptr)), member); \
+		list_del_init(&(*(ptr))->member);	\
+	} (!__empty); })
+
+/**
  * list_for_each	-	iterate over a list
  * @pos:	the &struct list_head to use as a loop cursor.
  * @head:	the head for your list.

[PATCH RFC 2/3] slist: singly-linked stack implementation

[Konstantin Khlebnikov]

Intoduce slist -- singly-linked circular list.
Usable for implementing Stacks and Sets.

Struct slist_head uses twice less memory than nornal doubly-linked list_head.

slist able to freely add and delete entries only at head
or while safe-iterating: slist_for_each_entry_safe() provide pointer to
previous entry, it usable to remove current entry or add new entry before it.

Signed-off-by: Konstantin Khlebnikov <khlebnikov@openvz.org>
---
 include/linux/list.h |  194 ++++++++++++++++++++++++++++++++++++++++++++++++++
 1 files changed, 194 insertions(+), 0 deletions(-)

diff --git a/include/linux/list.h b/include/linux/list.h
index 6a6e9d3..691d37b 100644
--- a/include/linux/list.h
+++ b/include/linux/list.h
@@ -809,4 +809,198 @@ static inline void hlist_move_list(struct hlist_head *old,
 		({ tpos = hlist_entry(pos, typeof(*tpos), member); 1;}); \
 	     pos = n)
 
+/*
+ * Simple sindly-linked list implementation.
+ */
+
+struct slist_head {
+	struct slist_head *next;
+};
+
+#define SLIST_HEAD_INIT(name) { .next = &(name) }
+
+#define SLIST_HEAD(name) \
+	struct slist_head name = SLIST_HEAD_INIT(name)
+
+static inline void INIT_SLIST_HEAD(struct slist_head *list)
+{
+	list->next = list;
+}
+
+/**
+ * slist_empty - tests whether a list is empty
+ * @head: the list to test.
+ */
+static inline bool slist_empty(const struct slist_head *head)
+{
+	return head->next == head;
+}
+
+/**
+ * slist_add - add a new entry
+ * @entry: new entry to be added
+ * @prev: list head to add it after
+ *
+ * Insert a new entry after the specified head.
+ */
+static inline void slist_add(struct slist_head *entry, struct slist_head *prev)
+{
+	entry->next = prev->next;
+	prev->next = entry;
+}
+
+/**
+ * slist_del - deletes entry from list.
+ * @entry: the element to delete from the list.
+ * @prev: previous entry in the list, list head for first entry.
+ *
+ * Note: slist_empty() on entry does not return true after this, the entry is
+ * in an undefined state.
+ */
+static inline void slist_del(struct slist_head *entry,
+			     struct slist_head *prev)
+{
+	prev->next = entry->next;
+	entry->next = LIST_POISON1;
+}
+
+/**
+ * slist_del_init - deletes entry from list and reinitialize it.
+ * @entry: the element to delete from the list.
+ * @prev: previous entry in the list, list head for first entry.
+ */
+static inline void slist_del_init(struct slist_head *entry,
+				  struct slist_head *prev)
+{
+	slist_del(entry, prev);
+	INIT_SLIST_HEAD(entry);
+}
+
+/**
+ * __slist_splice - add entries chain into list
+ * @first:	chain first entry
+ * @last:	chain last entry
+ * @prev:	place to insert chain
+ */
+static inline void __slist_splice(struct slist_head *first,
+				  struct slist_head *last,
+				  struct slist_head *prev)
+{
+	last->next = prev->next;
+	prev->next = first;
+}
+
+/**
+ * slist_entry - get the struct for this entry
+ * @ptr:	the &struct slist_head pointer.
+ * @type:	the type of the struct this is embedded in.
+ * @member:	the name of the list_struct within the struct.
+ */
+#define slist_entry(ptr, type, member) \
+	container_of(ptr, type, member)
+
+/**
+ * slist_first_entry - get the first element from a list
+ * @head:	the list head to take the element from.
+ * @type:	the type of the struct this is embedded in.
+ * @member:	the name of the slist_struct within the struct.
+ *
+ * Note, that list is expected to be not empty.
+ */
+#define slist_first_entry(head, type, member) \
+	slist_entry((head)->next, type, member)
+
+/**
+ * slist_peek_entry - check is list non-empty and retrieve list first entry,
+ * @ptr		pointer to strict * there to save result
+ * @head:	the struct slist_head pointer.
+ * @member:	the name of the slist_struct within the struct.
+ *
+ * Return true if list was not empty and @ptr is changed
+ */
+#define slist_peek_entry(ptr, head, member) ({		\
+	bool __empty = slist_empty(head);		\
+	if (!__empty) {					\
+		*(ptr) = slist_first_entry(head, typeof(**(ptr)), member); \
+	} (!__empty); })
+
+/**
+ * slist_pop_entry - check is list non-empty, retrieve and delete first entry,
+ * @ptr		pointer to strict * there to save result
+ * @head:	the struct slist_head pointer.
+ * @member:	the name of the slist_struct within the struct.
+ *
+ * Return true if list was not empty and @ptr is changed
+ */
+#define slist_pop_entry(ptr, head, member) ({		\
+	bool __empty = slist_empty(head);		\
+	if (!__empty) {					\
+		*(ptr) = slist_first_entry(head, typeof(**(ptr)), member); \
+		slist_del(&(*(ptr))->member, head);	\
+	} (!__empty); })
+
+/**
+ * slist_pop_init_entry - delete, reinitialize and return list first entry,
+ * @ptr		pointer to strict * there to save result
+ * @head:	the struct slist_head pointer.
+ * @member:	the name of the slist_struct within the struct.
+ *
+ * Return true if list was not empty and @ptr is changed
+ */
+#define slist_pop_init_entry(ptr, head, member) ({	\
+	bool __empty = slist_empty(head);		\
+	if (!__empty) {					\
+		*(ptr) = slist_first_entry(head, typeof(**(ptr)), member); \
+		slist_del_init(&(*(ptr))->member, head); \
+	} (!__empty); })
+
+/**
+ * slist_for_each - iterate over a list
+ * @pos:	the &struct list_head to use as a loop cursor.
+ * @head:	the head for your list.
+ */
+#define slist_for_each(pos, head) \
+	for (pos = (head)->next; prefetch(pos->next), pos != (head); \
+	     pos = pos->next)
+
+/**
+ * slist_for_each_safe - iterate over a list safe against removal of list entry
+ * @pos:	the &struct slist_head to use as a loop cursor.
+ * @prev:	pointer to struct slist_head to store precursor.
+ * @n:		another &struct list_head to use as temporary storage
+ * @head:	the head for your list.
+ */
+#define slist_for_each_safe(pos, prev, n, head) \
+	for (prev = (head), pos = (head)->next, n = pos->next; \
+	     prefetch(pos->next), pos != (head); \
+	     prev = (prev->next == n) ? prev : pos, pos = n, n = pos->next)
+
+/**
+ * slist_for_each_entry	-	iterate over list of given type
+ * @pos:	the type * to use as a loop cursor.
+ * @head:	the head for your list.
+ * @member:	the name of the list_struct within the struct.
+ */
+#define slist_for_each_entry(pos, head, member)				\
+	for (pos = slist_entry((head)->next, typeof(*pos), member);	\
+	     prefetch(pos->member.next), &pos->member != (head);	\
+	     pos = slist_entry(pos->member.next, typeof(*pos), member))
+
+/**
+ * slist_for_each_entry_safe - iterate over list of given type
+ *			safe against removal of list entry
+ * @pos:	the type * to use as a loop cursor.
+ * @prev:	pointer to struct slist_head to store precursor.
+ * @n:		another type * to use as temporary storage
+ * @head:	the head for your list.
+ * @member:	the name of the list_struct within the struct.
+ */
+#define slist_for_each_entry_safe(pos, prev, n, head, member)		\
+	for (prev = &(head)->member,					\
+	     pos = slist_entry((head)->next, typeof(*pos), member),	\
+	     n = slist_entry(pos->member.next, typeof(*pos), member);	\
+	     prefetch(pos->member.next), &pos->member != (head);	\
+	     prev = (prev->next == &n->member) ? prev : &pos->member,	\
+	     pos = n, n = slist_entry(n->member.next, typeof(*n), member))
+
 #endif

[PATCH RFC 3/3] qlist: singly-linked queue implementation

[Konstantin Khlebnikov]

Introduce qlist -- singly-linked queue implementation.

Based on slist, but additianally manage pointer to last entry.
So, qlist can add and splice elements to both ends.

Signed-off-by: Konstantin Khlebnikov <khlebnikov@openvz.org>
---
 include/linux/list.h |  338 ++++++++++++++++++++++++++++++++++++++++++++++++++
 1 files changed, 338 insertions(+), 0 deletions(-)

diff --git a/include/linux/list.h b/include/linux/list.h
index 691d37b..2c78bf2 100644
--- a/include/linux/list.h
+++ b/include/linux/list.h
@@ -1003,4 +1003,342 @@ static inline void __slist_splice(struct slist_head *first,
 	     prev = (prev->next == &n->member) ? prev : &pos->member,	\
 	     pos = n, n = slist_entry(n->member.next, typeof(*n), member))
 
+
+/*
+ * Singly-linked queue implementation
+ */
+
+struct qlist_head
+{
+	struct slist_head head;
+	struct slist_head *tail;
+};
+
+#define QLIST_HEAD_INIT(name) { .head = SLIST_HEAD_INIT(name.head),	\
+				.tail = &name.head }
+
+#define QLIST_HEAD(name) \
+	struct qlist_head name = QLIST_HEAD_INIT(name)
+
+static inline void INIT_QLIST_HEAD(struct qlist_head *list)
+{
+	INIT_SLIST_HEAD(&list->head);
+	list->tail = &list->head;
+}
+
+/**
+ * qlist_empty - tests whether a list is empty
+ * @head:	the list to test.
+ */
+static inline int qlist_empty(const struct qlist_head *list)
+{
+	return slist_empty(&list->head);
+}
+
+/**
+ * qlist_first - get list first entry
+ * @list:	list struct qlist_head
+ *
+ * Note, that list is expected to be not empty.
+ */
+#define qlist_first(list)	((list)->head.next)
+
+/**
+ * qlist_last - get list last entry
+ * @list:	list struct qlist_head
+ *
+ * Note, that list is expected to be not empty.
+ */
+#define qlist_last(list)	((list)->tail)
+
+/**
+ * qlist_add - add a new entry
+ * @entry:	new entry to be added
+ * @prev:	list position to add it after
+ * @list:	qlist head to add into it
+ *
+ * Insert a new entry after given position
+ */
+static inline void qlist_add(struct slist_head *entry,
+			     struct slist_head *prev,
+			     struct qlist_head *list)
+{
+	if (prev == list->tail)
+		list->tail = entry;
+	slist_add(entry, prev);
+}
+
+/**
+ * qlist_add_head - add a new entry
+ * @entry:	new entry to be added
+ * @list:	list head to add it after
+ *
+ * Insert a new entry into list head
+ */
+static inline void qlist_add_head(struct slist_head *entry,
+				  struct qlist_head *list)
+{
+	qlist_add(entry, &list->head, list);
+}
+
+/**
+ * qlist_add_tail - add a new entry
+ * @new:	new entry to be added
+ * @head:	list head to add it after
+ *
+ * Insert a new entry into list tail
+ */
+static inline void qlist_add_tail(struct slist_head *entry,
+				  struct qlist_head *list)
+{
+	slist_add(entry, list->tail);
+	list->tail = entry;
+}
+
+/**
+ * qlist_splice - insert list elements into given position
+ * @list:	source list
+ * @prev:	insert afther this position
+ * @head:	destination list
+ */
+static inline void qlist_splice(struct qlist_head *list,
+				struct slist_head *prev,
+				struct qlist_head *head)
+{
+	if (!qlist_empty(list)) {
+		if (prev == head->tail)
+			head->tail = list->tail;
+		__slist_splice(qlist_first(list), qlist_last(list), prev);
+	}
+}
+
+/**
+ * qlist_splice - insert list elements into given position and reinitialise src
+ * @list:	source list
+ * @prev:	insert afther this position
+ * @head:	destination list
+ */
+static inline void qlist_splice_init(struct qlist_head *list,
+				     struct slist_head *prev,
+				     struct qlist_head *head)
+{
+	if (!qlist_empty(list)) {
+		if (prev == head->tail)
+			head->tail = list->tail;
+		__slist_splice(qlist_first(list), qlist_last(list), prev);
+		INIT_QLIST_HEAD(list);
+	}
+}
+
+/**
+ * qlist_splice_head - insert elements into list head
+ * @list:	source
+ * @head:	destination
+ */
+static inline void qlist_splice_head(struct qlist_head *list,
+				     struct qlist_head *head)
+{
+	qlist_splice(list, &head->head, head);
+}
+
+/**
+ * qlist_splice_head_init - insert elements into list head and reinitialise src
+ * @list:	source
+ * @head:	destination
+ */
+static inline void qlist_splice_head_init(struct qlist_head *list,
+					  struct qlist_head *head)
+{
+	qlist_splice_init(list, &head->head, head);
+}
+
+/**
+ * qlist_splice_tail - insert elements into list tail
+ * @list:	source
+ * @head:	destination
+ */
+static inline void qlist_splice_tail(struct qlist_head *list,
+				     struct qlist_head *head)
+{
+	if (!qlist_empty(list)) {
+		__slist_splice(qlist_first(list), qlist_last(list), head->tail);
+		head->tail = list->tail;
+	}
+}
+
+/**
+ * qlist_splice_tail_init - insert elements into list tail and reinitialise src
+ * @list:	source
+ * @head:	destination
+ */
+static inline void qlist_splice_tail_init(struct qlist_head *list,
+					  struct qlist_head *head)
+{
+	if (!qlist_empty(list)) {
+		__slist_splice(qlist_first(list), qlist_last(list), head->tail);
+		head->tail = list->tail;
+		INIT_QLIST_HEAD(list);
+	}
+}
+
+/**
+ * qlist_del - deletes entry from list.
+ * @entry:	the element to delete.
+ * @prev:	previous entry in the list.
+ * @list:	list to delete from.
+ *
+ * Note: slist_empty() on entry does not return true after this, the entry is
+ * in an undefined state.
+ */
+static inline void qlist_del(struct slist_head *entry,
+			     struct slist_head *prev,
+			     struct qlist_head *list)
+{
+	if (entry == list->tail)
+		list->tail = prev;
+	slist_del(entry, prev);
+}
+
+/**
+ * qlist_del_init - deletes entry from list and reinitialize it.
+ * @entry:	the element to delete.
+ * @prev:	previous entry in the list.
+ * @list:	list to delete from.
+ */
+static inline void qlist_del_init(struct slist_head *entry,
+				  struct slist_head *prev,
+				  struct qlist_head *list)
+{
+	qlist_del(entry, prev, list);
+	INIT_SLIST_HEAD(entry);
+}
+
+/**
+ * qlist_entry - get the struct for this entry
+ * @ptr:	the &struct slist_head pointer.
+ * @type:	the type of the struct this is embedded in.
+ * @member:	the name of the slist_head within the struct.
+ */
+#define qlist_entry(ptr, type, member) \
+	slist_entry(ptr, type, member)
+
+/**
+ * qlist_first_entry - get the first element from a list
+ * @ptr:	the list head to take the element from.
+ * @type:	the type of the struct this is embedded in.
+ * @member:	the name of the slist_struct within the struct.
+ *
+ * Note, that list is expected to be not empty.
+ */
+#define qlist_first_entry(ptr, type, member) \
+	qlist_entry(qlist_first(ptr), type, member)
+
+/**
+ * qlist_last_entry - get the last element from a list
+ * @ptr:	the list head to take the element from.
+ * @type:	the type of the struct this is embedded in.
+ * @member:	the name of the slist_struct within the struct.
+ *
+ * Note, that list is expected to be not empty.
+ */
+#define qlist_last_entry(ptr, type, member) \
+	qlist_entry(qlist_last(ptr), type, member)
+
+/**
+ * qlist_peek_entry - check is list non-empty and retrieve list first entry
+ * @ptr:	pointer to struct * whereto save result
+ * @list:	the struct slist_head pointer.
+ * @member:	the name of the slist_struct within the struct.
+ *
+ * Return true if list was not empty and @ptr updated
+ */
+#define qlist_peek_entry(ptr, list, member) ({		\
+	bool __empty = qlist_empty(list);		\
+	if (!__empty) {					\
+		*(ptr) = qlist_first_entry(list, typeof(**(ptr)), member); \
+	} (!__empty); })
+
+/**
+ * qlist_peek_last_entry - check is list non-empty and retrieve list last entry
+ * @ptr:	pointer to struct * whereto save result
+ * @list:	the struct slist_head pointer.
+ * @member:	the name of the slist_struct within the struct.
+ *
+ * Return true if list was not empty and @ptr updated
+ */
+#define qlist_peek_last_entry(ptr, list, member) ({	\
+	bool __empty = qlist_empty(list);		\
+	if (!__empty) {					\
+		*(ptr) = qlist_last_entry(list, typeof(**(ptr)), member); \
+	} (!__empty); })
+
+/**
+ * qlist_pop_entry - delete and return list first entry
+ * @ptr:	pointer to struct * whereto save result
+ * @list:	the struct slist_head pointer.
+ * @member:	the name of the slist_struct within the struct.
+ *
+ * Return true if list was not empty and @ptr updated
+ */
+#define qlist_pop_entry(ptr, list, member) ({		\
+	bool __empty = qlist_empty(list);		\
+	if (!__empty) {					\
+		*(ptr) = qlist_first_entry(list, typeof(**(ptr)), member); \
+		qlist_del(&(*(ptr))->member, &(list)->head, list); \
+	} (!__empty); })
+
+/**
+ * qlist_pop_init_entry - delete, reinitialize and return list first entry
+ * @ptr:	pointer to struct * whereto save result
+ * @list:	the struct slist_head pointer.
+ * @member:	the name of the slist_struct within the struct.
+ *
+ * Return true if list was not empty and @ptr updated
+ */
+#define qlist_pop_init_entry(ptr, list, member) ({	\
+	bool __empty = qlist_empty(list);		\
+	if (!__empty) {					\
+		*(ptr) = qlist_first_entry(list, typeof(**(ptr)), member); \
+		qlist_del_init(&(*(ptr))->member, &(list)->head, list); \
+	} (!__empty); })
+
+/**
+ * qlist_for_each - iterate over a list
+ * @pos:	the &struct list_head to use as a loop cursor.
+ * @list:	the head for your list.
+ */
+#define qlist_for_each(pos, list) \
+	slist_for_each(pos, &(list)->head)
+
+/**
+ * qlist_for_each_safe - iterate over a list safe against removal of list entry
+ * @pos:	the &struct slist_head to use as a loop cursor.
+ * @prev:	pointer to struct slist_head to store precursor.
+ * @n:		another &struct list_head to use as temporary storage
+ * @list:	the head for your list.
+ */
+#define qlist_for_each_safe(pos, prev, n, list) \
+	slist_for_each_safe(pos, prev, n, &(list)->head)
+
+/**
+ * qlist_for_each_entry	-	iterate over list of given type
+ * @pos:	the type * to use as a loop cursor.
+ * @list:	the head for your list.
+ * @member:	the name of the list_struct within the struct.
+ */
+#define qlist_for_each_entry(pos, list, member) \
+	slist_for_each_entry(pos, &(list)->head, member)
+
+/**
+ * qlist_for_each_entry_safe - iterate over list of given type
+ *				safe against removal of list entry
+ * @pos:	the type * to use as a loop cursor.
+ * @prev:	pointer to struct slist_head to store precursor.
+ * @n:		another type * to use as temporary storage
+ * @list:	the head for your list.
+ * @member:	the name of the list_struct within the struct.
+ */
+#define qlist_for_each_entry_safe(pos, prev, n, list, member) \
+	slist_for_each_entry_safe(pos, prev, n, &(list)->head, member)
+
 #endif