Repository : ssh://git@diktynna/alfred
On branches: main,main
>---------------------------------------------------------------
commit ba393626fa1a0140c02d9af5cb769b9543ecff92
Author: Sven Eckelmann <sven(a)narfation.org>
Date: Sat Jan 4 09:47:16 2025 +0100
alfred: Use same list implementation as batctl
Signed-off-by: Sven Eckelmann <sven(a)narfation.org>
>---------------------------------------------------------------
ba393626fa1a0140c02d9af5cb769b9543ecff92
list.h | 1159 ++++++++++++++++++++++++++++++++++------------------------------
1 file changed, 616 insertions(+), 543 deletions(-)
diff --git a/list.h b/list.h
index 0fa634f..a8bd44b 100644
--- a/list.h
+++ b/list.h
@@ -1,744 +1,817 @@
-/* SPDX-License-Identifier: GPL-2.0 */
-/* Copyright (C) 1991-2013 linux kernel contributors
+/* SPDX-License-Identifier: MIT */
+/* Minimal Linux-like double-linked list helper functions
*
- * Linus Torvalds, ...
- *
- * License-Filename: LICENSES/preferred/GPL-2.0
+ * SPDX-FileCopyrightText: Sven Eckelmann <sven(a)narfation.org>
*/
-#ifndef _LINUX_LIST_H
-#define _LINUX_LIST_H
-
-#include <stddef.h>
-
-/**
- * container_of - cast a member of a structure out to the containing structure
- * @ptr: the pointer to the member.
- * @type: the type of the container struct this is embedded in.
- * @member: the name of the member within the struct.
- *
- */
-#define container_of(ptr, type, member) __extension__ ({ \
- const typeof( ((type *)0)->member ) *__mptr = (ptr); \
- (type *)( (char *)__mptr - offsetof(type,member) );})
+#ifndef __LINUX_LIKE_LIST_H__
+#define __LINUX_LIKE_LIST_H__
-struct list_head {
- struct list_head *next, *prev;
-};
+#ifdef __cplusplus
+extern "C" {
+#endif
-struct hlist_head {
- struct hlist_node *first;
-};
+#include <stddef.h>
-struct hlist_node {
- struct hlist_node *next, **pprev;
-};
+#if defined(__GNUC__)
+#define LIST_TYPEOF_USE 1
+#endif
-/*
- * These are non-NULL pointers that will result in page faults
- * under normal circumstances, used to verify that nobody uses
- * non-initialized list entries.
- */
-#define LIST_POISON1 ((void *) 0x00100100)
-#define LIST_POISON2 ((void *) 0x00200200)
+#if defined(_MSC_VER)
+#define inline __inline
+#endif
-/*
- * Simple doubly linked list implementation.
+/**
+ * container_of() - Calculate address of object that contains address ptr
+ * @ptr: pointer to member variable
+ * @type: type of the structure containing ptr
+ * @member: name of the member variable in struct @type
*
- * Some of the internal functions ("__xxx") are useful when
- * manipulating whole lists rather than single entries, as
- * sometimes we already know the next/prev entries and we can
- * generate better code by using them directly rather than
- * using the generic single-entry routines.
- */
-
-#define LIST_HEAD_INIT(name) { &(name), &(name) }
-
-#define LIST_HEAD(name) \
- struct list_head name = LIST_HEAD_INIT(name)
-
-static inline void INIT_LIST_HEAD(struct list_head *list)
-{
- list->next = list;
- list->prev = list;
-}
+ * Return: @type pointer of object containing ptr
+ */
+#ifndef container_of
+#ifdef LIST_TYPEOF_USE
+#define container_of(ptr, type, member) __extension__ ({ \
+ const __typeof__(((type *)0)->member) *__pmember = (ptr); \
+ (type *)((char *)__pmember - offsetof(type, member)); })
+#else
+#define container_of(ptr, type, member) \
+ ((type *)((char *)(ptr) - offsetof(type, member)))
+#endif
+#endif
-/*
- * Insert a new entry between two known consecutive entries.
+/**
+ * struct list_head - Head and node of a double-linked list
+ * @prev: pointer to the previous node in the list
+ * @next: pointer to the next node in the list
+ *
+ * The simple double-linked list consists of a head and nodes attached to
+ * this head. Both node and head share the same struct type. The list_*
+ * functions and macros can be used to access and modify this data structure.
*
- * This is only for internal list manipulation where we know
- * the prev/next entries already!
+ * The @prev pointer of the list head points to the last list node of the
+ * list and @next points to the first list node of the list. For an empty list,
+ * both member variables point to the head.
+ *
+ * The list nodes are usually embedded in a container structure which holds the
+ * actual data. Such an container object is called entry. The helper list_entry
+ * can be used to calculate the object address from the address of the node.
*/
-static inline void __list_add(struct list_head *new,
- struct list_head *prev,
- struct list_head *next)
-{
- next->prev = new;
- new->next = next;
- new->prev = prev;
- prev->next = new;
-}
+struct list_head {
+ struct list_head *prev;
+ struct list_head *next;
+};
/**
- * list_add - add a new entry
- * @new: new entry to be added
- * @head: list head to add it after
- *
- * Insert a new entry after the specified head.
- * This is good for implementing stacks.
+ * LIST_HEAD - Declare list head and initialize it
+ * @head: name of the new object
*/
-static inline void list_add(struct list_head *new, struct list_head *head)
-{
- __list_add(new, head, head->next);
-}
-
+#define LIST_HEAD(head) \
+ struct list_head head = { &(head), &(head) }
/**
- * list_add_tail - add a new entry
- * @new: new entry to be added
- * @head: list head to add it before
+ * INIT_LIST_HEAD() - Initialize empty list head
+ * @head: pointer to list head
*
- * Insert a new entry before the specified head.
- * This is useful for implementing queues.
- */
-static inline void list_add_tail(struct list_head *new, struct list_head *head)
-{
- __list_add(new, head->prev, head);
-}
-
-/*
- * Delete a list entry by making the prev/next entries
- * point to each other.
+ * This can also be used to initialize a unlinked list node.
*
- * This is only for internal list manipulation where we know
- * the prev/next entries already!
+ * A node is usually linked inside a list, will be added to a list in
+ * the near future or the entry containing the node will be free'd soon.
+ *
+ * But an unlinked node may be given to a function which uses list_del(_init)
+ * before it ends up in a previously mentioned state. The list_del(_init) on an
+ * initialized node is well defined and safe. But the result of a
+ * list_del(_init) on an uninitialized node is undefined (unrelated memory is
+ * modified, crashes, ...).
*/
-static inline void __list_del(struct list_head * prev, struct list_head * next)
+static inline void INIT_LIST_HEAD(struct list_head *head)
{
- next->prev = prev;
- prev->next = next;
+ head->next = head;
+ head->prev = head;
}
/**
- * list_del - deletes entry from list.
- * @entry: the element to delete from the list.
- * Note: list_empty() on entry does not return true after this, the entry is
- * in an undefined state.
+ * list_add() - Add a list node to the beginning of the list
+ * @node: pointer to the new node
+ * @head: pointer to the head of the list
*/
-static inline void __list_del_entry(struct list_head *entry)
+static inline void list_add(struct list_head *node,
+ struct list_head *head)
{
- __list_del(entry->prev, entry->next);
-}
+ struct list_head *next = head->next;
-static inline void list_del(struct list_head *entry)
-{
- __list_del(entry->prev, entry->next);
- entry->next = LIST_POISON1;
- entry->prev = LIST_POISON2;
+ next->prev = node;
+ node->next = next;
+ node->prev = head;
+ head->next = node;
}
/**
- * list_replace - replace old entry by new one
- * @old : the element to be replaced
- * @new : the new element to insert
- *
- * If @old was empty, it will be overwritten.
+ * list_add_tail() - Add a list node to the end of the list
+ * @node: pointer to the new node
+ * @head: pointer to the head of the list
*/
-static inline void list_replace(struct list_head *old,
- struct list_head *new)
+static inline void list_add_tail(struct list_head *node,
+ struct list_head *head)
{
- new->next = old->next;
- new->next->prev = new;
- new->prev = old->prev;
- new->prev->next = new;
-}
+ struct list_head *prev = head->prev;
-static inline void list_replace_init(struct list_head *old,
- struct list_head *new)
-{
- list_replace(old, new);
- INIT_LIST_HEAD(old);
+ prev->next = node;
+ node->next = head;
+ node->prev = prev;
+ head->prev = node;
}
/**
- * list_del_init - deletes entry from list and reinitialize it.
- * @entry: the element to delete from the list.
+ * list_add_before() - Add a list node before another node to the list
+ * @new_node: pointer to the new node
+ * @node: pointer to the reference node in the list
+ *
+ * WARNING this functionality is not available in the Linux list implementation
*/
-static inline void list_del_init(struct list_head *entry)
-{
- __list_del_entry(entry);
- INIT_LIST_HEAD(entry);
-}
+#define list_add_before(new_node, node) \
+ list_add_tail(new_node, node)
/**
- * list_move - delete from one list and add as another's head
- * @list: the entry to move
- * @head: the head that will precede our entry
+ * list_add_behind() - Add a list node behind another node to the list
+ * @new_node: pointer to the new node
+ * @node: pointer to the reference node in the list
+ *
+ * WARNING this functionality is not available in the Linux list implementation
*/
-static inline void list_move(struct list_head *list, struct list_head *head)
-{
- __list_del_entry(list);
- list_add(list, head);
-}
+#define list_add_behind(new_node, node) \
+ list_add(new_node, node)
/**
- * list_move_tail - delete from one list and add as another's tail
- * @list: the entry to move
- * @head: the head that will follow our entry
+ * list_del() - Remove a list node from the list
+ * @node: pointer to the node
+ *
+ * The node is only removed from the list. Neither the memory of the removed
+ * node nor the memory of the entry containing the node is free'd. The node
+ * has to be handled like an uninitialized node. Accessing the next or prev
+ * pointer of the node is not safe.
+ *
+ * Unlinked, initialized nodes are also uninitialized after list_del.
+ *
+ * LIST_POISONING can be enabled during build-time to provoke an invalid memory
+ * access when the memory behind the next/prev pointer is used after a list_del.
+ * This only works on systems which prohibit access to the predefined memory
+ * addresses.
*/
-static inline void list_move_tail(struct list_head *list,
- struct list_head *head)
+static inline void list_del(struct list_head *node)
{
- __list_del_entry(list);
- list_add_tail(list, head);
+ struct list_head *next = node->next;
+ struct list_head *prev = node->prev;
+
+ next->prev = prev;
+ prev->next = next;
+
+#ifdef LIST_POISONING
+ node->prev = (struct list_head *)(0x00100100);
+ node->next = (struct list_head *)(0x00200200);
+#endif
}
/**
- * list_is_last - tests whether @list is the last entry in list @head
- * @list: the entry to test
- * @head: the head of the list
+ * list_del_init() - Remove a list node from the list and reinitialize it
+ * @node: pointer to the node
+ *
+ * The removed node will not end up in an uninitialized state like when using
+ * list_del. Instead the node is initialized again to the unlinked state.
*/
-static inline int list_is_last(const struct list_head *list,
- const struct list_head *head)
+static inline void list_del_init(struct list_head *node)
{
- return list->next == head;
+ list_del(node);
+ INIT_LIST_HEAD(node);
}
/**
- * list_empty - tests whether a list is empty
- * @head: the list to test.
+ * list_empty() - Check if list head has no nodes attached
+ * @head: pointer to the head of the list
+ *
+ * Return: 0 - list is not empty !0 - list is empty
*/
static inline int list_empty(const struct list_head *head)
{
- return head->next == head;
+ return (head->next == head);
}
/**
- * list_empty_careful - tests whether a list is empty and not being modified
- * @head: the list to test
+ * list_is_singular() - Check if list head has exactly one node attached
+ * @head: pointer to the head of the list
*
- * Description:
- * tests whether a list is empty _and_ checks that no other CPU might be
- * in the process of modifying either member (next or prev)
- *
- * NOTE: using list_empty_careful() without synchronization
- * can only be safe if the only activity that can happen
- * to the list entry is list_del_init(). Eg. it cannot be used
- * if another CPU could re-list_add() it.
+ * Return: 0 - list is not singular !0 -list has exactly one entry
*/
-static inline int list_empty_careful(const struct list_head *head)
+static inline int list_is_singular(const struct list_head *head)
{
- struct list_head *next = head->next;
- return (next == head) && (next == head->prev);
+ return (!list_empty(head) && head->prev == head->next);
}
/**
- * list_rotate_left - rotate the list to the left
- * @head: the head of the list
+ * list_splice() - Add list nodes from a list to beginning of another list
+ * @list: pointer to the head of the list with the node entries
+ * @head: pointer to the head of the list
+ *
+ * All nodes from @list are added to the beginning of the list of @head.
+ * It is similar to list_add but for multiple nodes. The @list head is not
+ * modified and has to be initialized to be used as a valid list head/node
+ * again.
*/
-static inline void list_rotate_left(struct list_head *head)
+static inline void list_splice(struct list_head *list,
+ struct list_head *head)
{
- struct list_head *first;
+ struct list_head *head_first = head->next;
+ struct list_head *list_first = list->next;
+ struct list_head *list_last = list->prev;
- if (!list_empty(head)) {
- first = head->next;
- list_move_tail(first, head);
- }
-}
+ if (list_empty(list))
+ return;
-/**
- * list_is_singular - tests whether a list has just one entry.
- * @head: the list to test.
- */
-static inline int list_is_singular(const struct list_head *head)
-{
- return !list_empty(head) && (head->next == head->prev);
-}
+ head->next = list_first;
+ list_first->prev = head;
-static inline void __list_cut_position(struct list_head *list,
- struct list_head *head, struct list_head *entry)
-{
- struct list_head *new_first = entry->next;
- list->next = head->next;
- list->next->prev = list;
- list->prev = entry;
- entry->next = list;
- head->next = new_first;
- new_first->prev = head;
+ list_last->next = head_first;
+ head_first->prev = list_last;
}
/**
- * list_cut_position - cut a list into two
- * @list: a new list to add all removed entries
- * @head: a list with entries
- * @entry: an entry within head, could be the head itself
- * and if so we won't cut the list
- *
- * This helper moves the initial part of @head, up to and
- * including @entry, from @head to @list. You should
- * pass on @entry an element you know is on @head. @list
- * should be an empty list or a list you do not care about
- * losing its data.
+ * list_splice_tail() - Add list nodes from a list to end of another list
+ * @list: pointer to the head of the list with the node entries
+ * @head: pointer to the head of the list
*
+ * All nodes from @list are added to the end of the list of @head.
+ * It is similar to list_add_tail but for multiple nodes. The @list head is not
+ * modified and has to be initialized to be used as a valid list head/node
+ * again.
*/
-static inline void list_cut_position(struct list_head *list,
- struct list_head *head, struct list_head *entry)
+static inline void list_splice_tail(struct list_head *list,
+ struct list_head *head)
{
- if (list_empty(head))
- return;
- if (list_is_singular(head) &&
- (head->next != entry && head != entry))
- return;
- if (entry == head)
- INIT_LIST_HEAD(list);
- else
- __list_cut_position(list, head, entry);
-}
+ struct list_head *head_last = head->prev;
+ struct list_head *list_first = list->next;
+ struct list_head *list_last = list->prev;
-static inline void __list_splice(const struct list_head *list,
- struct list_head *prev,
- struct list_head *next)
-{
- struct list_head *first = list->next;
- struct list_head *last = list->prev;
+ if (list_empty(list))
+ return;
- first->prev = prev;
- prev->next = first;
+ head->prev = list_last;
+ list_last->next = head;
- last->next = next;
- next->prev = last;
+ list_first->prev = head_last;
+ head_last->next = list_first;
}
/**
- * list_splice - join two lists, this is designed for stacks
- * @list: the new list to add.
- * @head: the place to add it in the first list.
+ * list_splice_init() - Move list nodes from a list to beginning of another list
+ * @list: pointer to the head of the list with the node entries
+ * @head: pointer to the head of the list
+ *
+ * All nodes from @list are added to the beginning of the list of @head.
+ * It is similar to list_add but for multiple nodes.
+ *
+ * The @list head will not end up in an uninitialized state like when using
+ * list_splice. Instead the @list is initialized again to the an empty
+ * list/unlinked state.
*/
-static inline void list_splice(const struct list_head *list,
- struct list_head *head)
+static inline void list_splice_init(struct list_head *list,
+ struct list_head *head)
{
- if (!list_empty(list))
- __list_splice(list, head, head->next);
+ list_splice(list, head);
+ INIT_LIST_HEAD(list);
}
/**
- * list_splice_tail - join two lists, each list being a queue
- * @list: the new list to add.
- * @head: the place to add it in the first list.
+ * list_splice_tail_init() - Move list nodes from a list to end of another list
+ * @list: pointer to the head of the list with the node entries
+ * @head: pointer to the head of the list
+ *
+ * All nodes from @list are added to the end of the list of @head.
+ * It is similar to list_add_tail but for multiple nodes.
+ *
+ * The @list head will not end up in an uninitialized state like when using
+ * list_splice. Instead the @list is initialized again to the an empty
+ * list/unlinked state.
*/
-static inline void list_splice_tail(struct list_head *list,
- struct list_head *head)
+static inline void list_splice_tail_init(struct list_head *list,
+ struct list_head *head)
{
- if (!list_empty(list))
- __list_splice(list, head->prev, head);
+ list_splice_tail(list, head);
+ INIT_LIST_HEAD(list);
}
/**
- * list_splice_init - join two lists and reinitialise the emptied list.
- * @list: the new list to add.
- * @head: the place to add it in the first list.
+ * list_cut_position() - Move beginning of a list to another list
+ * @head_to: pointer to the head of the list which receives nodes
+ * @head_from: pointer to the head of the list
+ * @node: pointer to the node in which defines the cutting point
+ *
+ * All entries from the beginning of the list @head_from to (including) the
+ * @node is moved to @head_to.
*
- * The list at @list is reinitialised
+ * @head_to is replaced when @head_from is not empty. @node must be a real
+ * list node from @head_from or the behavior is undefined.
*/
-static inline void list_splice_init(struct list_head *list,
- struct list_head *head)
+static inline void list_cut_position(struct list_head *head_to,
+ struct list_head *head_from,
+ struct list_head *node)
{
- if (!list_empty(list)) {
- __list_splice(list, head, head->next);
- INIT_LIST_HEAD(list);
+ struct list_head *head_from_first = head_from->next;
+
+ if (list_empty(head_from))
+ return;
+
+ if (head_from == node) {
+ INIT_LIST_HEAD(head_to);
+ return;
}
+
+ head_from->next = node->next;
+ head_from->next->prev = head_from;
+
+ head_to->prev = node;
+ node->next = head_to;
+ head_to->next = head_from_first;
+ head_to->next->prev = head_to;
}
/**
- * list_splice_tail_init - join two lists and reinitialise the emptied list
- * @list: the new list to add.
- * @head: the place to add it in the first list.
+ * list_move() - Move a list node to the beginning of the list
+ * @node: pointer to the node
+ * @head: pointer to the head of the list
*
- * Each of the lists is a queue.
- * The list at @list is reinitialised
+ * The @node is removed from its old position/node and add to the beginning of
+ * @head
*/
-static inline void list_splice_tail_init(struct list_head *list,
- struct list_head *head)
+static inline void list_move(struct list_head *node, struct list_head *head)
{
- if (!list_empty(list)) {
- __list_splice(list, head->prev, head);
- INIT_LIST_HEAD(list);
- }
+ list_del(node);
+ list_add(node, head);
}
/**
- * list_entry - get the struct for this entry
- * @ptr: the &struct list_head pointer.
- * @type: the type of the struct this is embedded in.
- * @member: the name of the list_struct within the struct.
- */
-#define list_entry(ptr, type, member) \
- container_of(ptr, type, member)
-
-/**
- * list_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 list_struct within the struct.
+ * list_move_tail() - Move a list node to the end of the list
+ * @node: pointer to the node
+ * @head: pointer to the head of the list
*
- * Note, that list is expected to be not empty.
+ * The @node is removed from its old position/node and add to the end of @head
*/
-#define list_first_entry(ptr, type, member) \
- list_entry((ptr)->next, type, member)
+static inline void list_move_tail(struct list_head *node,
+ struct list_head *head)
+{
+ list_del(node);
+ list_add_tail(node, head);
+}
/**
- * list_for_each - iterate over a list
- * @pos: the &struct list_head to use as a loop cursor.
- * @head: the head for your list.
+ * list_entry() - Calculate address of entry that contains list node
+ * @node: pointer to list node
+ * @type: type of the entry containing the list node
+ * @member: name of the list_head member variable in struct @type
+ *
+ * Return: @type pointer of entry containing node
*/
-#define list_for_each(pos, head) \
- for (pos = (head)->next; pos != (head); pos = pos->next)
+#define list_entry(node, type, member) container_of(node, type, member)
/**
- * __list_for_each - iterate over a list
- * @pos: the &struct list_head to use as a loop cursor.
- * @head: the head for your list.
+ * list_first_entry() - get first entry of the list
+ * @head: pointer to the head of the list
+ * @type: type of the entry containing the list node
+ * @member: name of the list_head member variable in struct @type
*
- * This variant doesn't differ from list_for_each() any more.
- * We don't do prefetching in either case.
+ * Return: @type pointer of first entry in list
*/
-#define __list_for_each(pos, head) \
- for (pos = (head)->next; pos != (head); pos = pos->next)
+#define list_first_entry(head, type, member) \
+ list_entry((head)->next, type, member)
/**
- * list_for_each_prev - iterate over a list backwards
- * @pos: the &struct list_head to use as a loop cursor.
- * @head: the head for your list.
+ * list_last_entry() - get last entry of the list
+ * @head: pointer to the head of the list
+ * @type: type of the entry containing the list node
+ * @member: name of the list_head member variable in struct @type
+ *
+ * Return: @type pointer of last entry in list
*/
-#define list_for_each_prev(pos, head) \
- for (pos = (head)->prev; pos != (head); pos = pos->prev)
+#define list_last_entry(head, type, member) \
+ list_entry((head)->prev, type, member)
/**
- * list_for_each_safe - iterate over a list safe against removal of list entry
- * @pos: the &struct list_head to use as a loop cursor.
- * @n: another &struct list_head to use as temporary storage
- * @head: the head for your list.
+ * list_for_each - iterate over list nodes
+ * @node: list_head pointer used as iterator
+ * @head: pointer to the head of the list
+ *
+ * The nodes and the head of the list must be kept unmodified while
+ * iterating through it. Any modifications to the list will cause undefined
+ * behavior.
*/
-#define list_for_each_safe(pos, n, head) \
- for (pos = (head)->next, n = pos->next; pos != (head); \
- pos = n, n = pos->next)
+#define list_for_each(node, head) \
+ for (node = (head)->next; \
+ node != (head); \
+ node = node->next)
/**
- * list_for_each_prev_safe - iterate over a list backwards safe against removal of list entry
- * @pos: the &struct list_head to use as a loop cursor.
- * @n: another &struct list_head to use as temporary storage
- * @head: the head for your list.
+ * list_for_each_entry_t - iterate over list entries
+ * @entry: @type pointer used as iterator
+ * @head: pointer to the head of the list
+ * @type: type of the entries containing the list nodes
+ * @member: name of the list_head member variable in struct @type
+ *
+ * The nodes and the head of the list must be kept unmodified while
+ * iterating through it. Any modifications to the list will cause undefined
+ * behavior.
+ *
+ * WARNING this functionality is not available in the Linux list implementation
*/
-#define list_for_each_prev_safe(pos, n, head) \
- for (pos = (head)->prev, n = pos->prev; \
- pos != (head); \
- pos = n, n = pos->prev)
+#define list_for_each_entry_t(entry, head, type, member) \
+ for (entry = list_entry((head)->next, type, member); \
+ &entry->member != (head); \
+ entry = list_entry(entry->member.next, type, member))
/**
- * list_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.
+ * list_for_each_entry - iterate over list entries
+ * @entry: pointer used as iterator
+ * @head: pointer to the head of the list
+ * @member: name of the list_head member variable in struct type of @entry
+ *
+ * The nodes and the head of the list must be kept unmodified while
+ * iterating through it. Any modifications to the list will cause undefined
+ * behavior.
*/
-#define list_for_each_entry(pos, head, member) \
- for (pos = list_entry((head)->next, typeof(*pos), member); \
- &pos->member != (head); \
- pos = list_entry(pos->member.next, typeof(*pos), member))
+#ifdef LIST_TYPEOF_USE
+#define list_for_each_entry(entry, head, member) \
+ list_for_each_entry_t(entry, head, __typeof__(*entry), member)
+#endif
/**
- * list_for_each_entry_reverse - iterate backwards 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.
+ * list_for_each_safe - iterate over list nodes and allow deletes
+ * @node: list_head pointer used as iterator
+ * @safe: list_head pointer used to store info for next entry in list
+ * @head: pointer to the head of the list
+ *
+ * The current node (iterator) is allowed to be removed from the list. Any
+ * other modifications to the list will cause undefined behavior.
*/
-#define list_for_each_entry_reverse(pos, head, member) \
- for (pos = list_entry((head)->prev, typeof(*pos), member); \
- &pos->member != (head); \
- pos = list_entry(pos->member.prev, typeof(*pos), member))
+#define list_for_each_safe(node, safe, head) \
+ for (node = (head)->next, safe = node->next; \
+ node != (head); \
+ node = safe, safe = node->next)
/**
- * list_prepare_entry - prepare a pos entry for use in list_for_each_entry_continue()
- * @pos: the type * to use as a start point
- * @head: the head of the list
- * @member: the name of the list_struct within the struct.
+ * list_for_each_entry_safe_t - iterate over list entries and allow deletes
+ * @entry: @type pointer used as iterator
+ * @safe: @type pointer used to store info for next entry in list
+ * @head: pointer to the head of the list
+ * @type: type of the entries containing the list nodes
+ * @member: name of the list_head member variable in struct @type
+ *
+ * The current node (iterator) is allowed to be removed from the list. Any
+ * other modifications to the list will cause undefined behavior.
*
- * Prepares a pos entry for use as a start point in list_for_each_entry_continue().
+ * WARNING this functionality is not available in the Linux list implementation
*/
-#define list_prepare_entry(pos, head, member) \
- ((pos) ? : list_entry(head, typeof(*pos), member))
+#define list_for_each_entry_safe_t(entry, safe, head, type, member) \
+ for (entry = list_entry((head)->next, type, member), \
+ safe = list_entry(entry->member.next, type, member); \
+ &entry->member != (head); \
+ entry = safe, \
+ safe = list_entry(safe->member.next, type, member))
/**
- * list_for_each_entry_continue - continue iteration 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.
+ * list_for_each_entry_safe - iterate over list entries and allow deletes
+ * @entry: pointer used as iterator
+ * @safe: @type pointer used to store info for next entry in list
+ * @head: pointer to the head of the list
+ * @member: name of the list_head member variable in struct type of @entry
*
- * Continue to iterate over list of given type, continuing after
- * the current position.
+ * The current node (iterator) is allowed to be removed from the list. Any
+ * other modifications to the list will cause undefined behavior.
*/
-#define list_for_each_entry_continue(pos, head, member) \
- for (pos = list_entry(pos->member.next, typeof(*pos), member); \
- &pos->member != (head); \
- pos = list_entry(pos->member.next, typeof(*pos), member))
+#ifdef LIST_TYPEOF_USE
+#define list_for_each_entry_safe(entry, safe, head, member) \
+ list_for_each_entry_safe_t(entry, safe, head, __typeof__(*entry), \
+ member)
+#endif
/**
- * list_for_each_entry_continue_reverse - iterate backwards from the given point
- * @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.
+ * struct hlist_node - Node of a double-linked list with single pointer head
+ * @next: pointer to the next node in the list
+ * @pprev: pointer to @next of the previous node in the hlist
+ *
+ * The double-linked list with single pointer head consists of a head and nodes
+ * attached to this head. The hlist_* functions and macros can be used to access
+ * and modify this data structure.
+ *
+ * The @pprev pointer is used to find the previous node (or head) in the list
+ * when doing hlist_del operations
*
- * Start to iterate over list of given type backwards, continuing after
- * the current position.
+ * The hlist nodes are usually embedded in a container structure which holds the
+ * actual data. Such an container object is called entry. The helper hlist_entry
+ * can be used to calculate the object address from the address of the node.
*/
-#define list_for_each_entry_continue_reverse(pos, head, member) \
- for (pos = list_entry(pos->member.prev, typeof(*pos), member); \
- &pos->member != (head); \
- pos = list_entry(pos->member.prev, typeof(*pos), member))
+struct hlist_node {
+ struct hlist_node *next;
+ struct hlist_node **pprev;
+};
/**
- * list_for_each_entry_from - iterate over list of given type from the current point
- * @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.
+ * struct hlist_head - Head of a double-linked list with single pointer head
+ * @first: pointer to the first node in the hlist
*
- * Iterate over list of given type, continuing from current position.
+ * The hlist doesn't have a pointer to the last node. This makes it harder to
+ * access or modify the tail of the list. But the single pointer to the first
+ * entry makes it well suited for implementation of hash tables because it
+ * cuts the size cost of the head pointers by half compared to the list_head.
*/
-#define list_for_each_entry_from(pos, head, member) \
- for (; &pos->member != (head); \
- pos = list_entry(pos->member.next, typeof(*pos), member))
+struct hlist_head {
+ struct hlist_node *first;
+};
/**
- * list_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.
- * @n: another type * to use as temporary storage
- * @head: the head for your list.
- * @member: the name of the list_struct within the struct.
+ * HLIST_HEAD - Declare hlist head and initialize it
+ * @head: name of the new object
*/
-#define list_for_each_entry_safe(pos, n, head, member) \
- for (pos = list_entry((head)->next, typeof(*pos), member), \
- n = list_entry(pos->member.next, typeof(*pos), member); \
- &pos->member != (head); \
- pos = n, n = list_entry(n->member.next, typeof(*n), member))
+#define HLIST_HEAD(head) \
+ struct hlist_head head = { NULL }
/**
- * list_for_each_entry_safe_continue - continue list iteration safe against removal
- * @pos: the type * to use as a loop cursor.
- * @n: another type * to use as temporary storage
- * @head: the head for your list.
- * @member: the name of the list_struct within the struct.
- *
- * Iterate over list of given type, continuing after current point,
- * safe against removal of list entry.
+ * INIT_HLIST_HEAD() - Initialize empty hlist head
+ * @head: pointer to hlist head
*/
-#define list_for_each_entry_safe_continue(pos, n, head, member) \
- for (pos = list_entry(pos->member.next, typeof(*pos), member), \
- n = list_entry(pos->member.next, typeof(*pos), member); \
- &pos->member != (head); \
- pos = n, n = list_entry(n->member.next, typeof(*n), member))
+static inline void INIT_HLIST_HEAD(struct hlist_head *head)
+{
+ head->first = NULL;
+}
/**
- * list_for_each_entry_safe_from - iterate over list from current point safe against removal
- * @pos: the type * to use as a loop cursor.
- * @n: another type * to use as temporary storage
- * @head: the head for your list.
- * @member: the name of the list_struct within the struct.
+ * INIT_HLIST_NODE() - Initialize unhashed hlist node
+ * @node: pointer to hlist node
*
- * Iterate over list of given type from current point, safe against
- * removal of list entry.
- */
-#define list_for_each_entry_safe_from(pos, n, head, member) \
- for (n = list_entry(pos->member.next, typeof(*pos), member); \
- &pos->member != (head); \
- pos = n, n = list_entry(n->member.next, typeof(*n), member))
-
-/**
- * list_for_each_entry_safe_reverse - iterate backwards over list safe against removal
- * @pos: the type * to use as a loop cursor.
- * @n: another type * to use as temporary storage
- * @head: the head for your list.
- * @member: the name of the list_struct within the struct.
+ * A hlist_node is usually linked inside a hlist, will be added to a hlist in
+ * the near future or the entry containing the node will be free'd soon.
*
- * Iterate backwards over list of given type, safe against removal
- * of list entry.
+ * But an unlinked node may be given to a function which uses hlist_del(_init)
+ * before it ends up in a previously mentioned state. The hlist_del(_init) on an
+ * initialized node is well defined and safe. But the result of a
+ * hlist_del(_init) on an uninitialized node is undefined (unrelated memory is
+ * modified, crashes, ...).
*/
-#define list_for_each_entry_safe_reverse(pos, n, head, member) \
- for (pos = list_entry((head)->prev, typeof(*pos), member), \
- n = list_entry(pos->member.prev, typeof(*pos), member); \
- &pos->member != (head); \
- pos = n, n = list_entry(n->member.prev, typeof(*n), member))
+static inline void INIT_HLIST_NODE(struct hlist_node *node)
+{
+ node->next = NULL;
+ node->pprev = NULL;
+}
/**
- * list_safe_reset_next - reset a stale list_for_each_entry_safe loop
- * @pos: the loop cursor used in the list_for_each_entry_safe loop
- * @n: temporary storage used in list_for_each_entry_safe
- * @member: the name of the list_struct within the struct.
- *
- * list_safe_reset_next is not safe to use in general if the list may be
- * modified concurrently (eg. the lock is dropped in the loop body). An
- * exception to this is if the cursor element (pos) is pinned in the list,
- * and list_safe_reset_next is called after re-taking the lock and before
- * completing the current iteration of the loop body.
- */
-#define list_safe_reset_next(pos, n, member) \
- n = list_entry(pos->member.next, typeof(*pos), member)
-
-/*
- * Double linked lists 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).
+ * hlist_add_head() - Add a hlist node to the beginning of the hlist
+ * @node: pointer to the new node
+ * @head: pointer to the head of the hlist
*/
-
-#define HLIST_HEAD_INIT { .first = NULL }
-#define HLIST_HEAD(name) struct hlist_head name = { .first = NULL }
-#define INIT_HLIST_HEAD(ptr) ((ptr)->first = NULL)
-static inline void INIT_HLIST_NODE(struct hlist_node *h)
+static inline void hlist_add_head(struct hlist_node *node,
+ struct hlist_head *head)
{
- h->next = NULL;
- h->pprev = NULL;
-}
+ struct hlist_node *first = head->first;
-static inline int hlist_unhashed(const struct hlist_node *h)
-{
- return !h->pprev;
+ head->first = node;
+ node->next = first;
+ node->pprev = &head->first;
+ if (first)
+ first->pprev = &node->next;
}
-static inline int hlist_empty(const struct hlist_head *h)
+/**
+ * hlist_add_before() - Add a hlist node before another node to the hlist
+ * @new_node: pointer to the new node
+ * @node: pointer to the reference node in the hlist
+ */
+static inline void hlist_add_before(struct hlist_node *new_node,
+ struct hlist_node *node)
{
- return !h->first;
+ struct hlist_node **pprev = node->pprev;
+
+ *pprev = new_node;
+ new_node->next = node;
+ new_node->pprev = pprev;
+ node->pprev = &new_node->next;
}
-static inline void __hlist_del(struct hlist_node *n)
+/**
+ * hlist_add_behind() - Add a hlist node behind another node to the hlist
+ * @new_node: pointer to the new node
+ * @node: pointer to the reference node in the hlist
+ */
+static inline void hlist_add_behind(struct hlist_node *new_node,
+ struct hlist_node *node)
{
- struct hlist_node *next = n->next;
- struct hlist_node **pprev = n->pprev;
- *pprev = next;
+ struct hlist_node *next = node->next;
+
+ node->next = new_node;
+ new_node->pprev = &node->next;
+ new_node->next = next;
if (next)
- next->pprev = pprev;
+ next->pprev = &new_node->next;
}
-static inline void hlist_del(struct hlist_node *n)
+/**
+ * hlist_del() - Remove a hlist node from the hlist
+ * @node: pointer to the node
+ *
+ * The node is only removed from the hlist. Neither the memory of the removed
+ * node nor the memory of the entry containing the node is free'd. The node
+ * has to be handled like an uninitialized node. Accessing the next or pprev
+ * pointer of the node is not safe.
+ *
+ * Unlinked, initialized nodes are also uninitialized after hlist_del.
+ *
+ * LIST_POISONING can be enabled during build-time to provoke an invalid memory
+ * access when the memory behind the next/prev pointer is used after an
+ * hlist_del. This only works on systems which prohibit access to the predefined
+ * memory addresses.
+ */
+static inline void hlist_del(struct hlist_node *node)
{
- __hlist_del(n);
- n->next = LIST_POISON1;
- n->pprev = LIST_POISON2;
-}
+ struct hlist_node *next = node->next;
+ struct hlist_node **pprev = node->pprev;
-static inline void hlist_del_init(struct hlist_node *n)
-{
- if (!hlist_unhashed(n)) {
- __hlist_del(n);
- INIT_HLIST_NODE(n);
- }
-}
+ if (pprev)
+ *pprev = next;
-static inline void hlist_add_head(struct hlist_node *n, struct hlist_head *h)
-{
- struct hlist_node *first = h->first;
- n->next = first;
- if (first)
- first->pprev = &n->next;
- h->first = n;
- n->pprev = &h->first;
-}
+ if (next)
+ next->pprev = pprev;
-/* next must be != NULL */
-static inline void hlist_add_before(struct hlist_node *n,
- struct hlist_node *next)
-{
- n->pprev = next->pprev;
- n->next = next;
- next->pprev = &n->next;
- *(n->pprev) = n;
+#ifdef LIST_POISONING
+ node->pprev = (struct hlist_node **)(0x00100100);
+ node->next = (struct hlist_node *)(0x00200200);
+#endif
}
-static inline void hlist_add_after(struct hlist_node *n,
- struct hlist_node *next)
+/**
+ * hlist_del_init() - Remove a hlist node from the hlist and reinitialize it
+ * @node: pointer to the node
+ *
+ * The removed node will not end up in an uninitialized state like when using
+ * hlist_del. Instead the node is initialized again to the unlinked state.
+ */
+static inline void hlist_del_init(struct hlist_node *node)
{
- next->next = n->next;
- n->next = next;
- next->pprev = &n->next;
-
- if(next->next)
- next->next->pprev = &next->next;
+ hlist_del(node);
+ INIT_HLIST_NODE(node);
}
-/* after that we'll appear to be on some hlist and hlist_del will work */
-static inline void hlist_add_fake(struct hlist_node *n)
+/**
+ * hlist_empty() - Check if hlist head has no nodes attached
+ * @head: pointer to the head of the hlist
+ *
+ * Return: 0 - hlist is not empty !0 - hlist is empty
+ */
+static inline int hlist_empty(const struct hlist_head *head)
{
- n->pprev = &n->next;
+ return !head->first;
}
-/*
- * Move a list from one list head to another. Fixup the pprev
- * reference of the first entry if it exists.
+/**
+ * hlist_move_list() - Move hlist nodes from a hlist head new hlist head
+ * @list: pointer to the head of the hlist with the node entries
+ * @head: pointer to the head of the hlist
+ *
+ * All nodes from @list are added to the beginning of the list of @head.
+ * @head can be uninitialized or an empty, initialized hlist. All entries of
+ * a non-empty hlist @head would be lost after this operation.
+ *
+ * The @list head will not end up in an uninitialized state. Instead the @list
+ * is initialized again to an empty hlist.
*/
-static inline void hlist_move_list(struct hlist_head *old,
- struct hlist_head *new)
+static inline void hlist_move_list(struct hlist_head *list,
+ struct hlist_head *head)
{
- new->first = old->first;
- if (new->first)
- new->first->pprev = &new->first;
- old->first = NULL;
+ head->first = list->first;
+ if (head->first)
+ head->first->pprev = &head->first;
+ INIT_HLIST_HEAD(list);
}
-#define hlist_entry(ptr, type, member) container_of(ptr,type,member)
+/**
+ * hlist_entry() - Calculate address of entry that contains hlist node
+ * @node: pointer to hlist node
+ * @type: type of the entry containing the hlist node
+ * @member: name of the hlist_node member variable in struct @type
+ *
+ * Return: @type pointer of entry containing node
+ */
+#define hlist_entry(node, type, member) container_of(node, type, member)
-#define hlist_for_each(pos, head) \
- for (pos = (head)->first; pos ; pos = pos->next)
+/**
+ * hlist_entry_safe() - Calculate address of entry that contains hlist node
+ * @node: pointer to hlist node or (struct hlist_node *)NULL
+ * @type: type of the entry containing the hlist node
+ * @member: name of the hlist_node member variable in struct @type
+ *
+ * Return: @type pointer of entry containing node or NULL
+ */
+#ifdef LIST_TYPEOF_USE
+#define hlist_entry_safe(node, type, member) __extension__ ({ \
+ __typeof__(node) __node = (node); \
+ !__node ? NULL : hlist_entry(__node, type, member); })
+#else
+#define hlist_entry_safe(node, type, member) \
+ (node) ? hlist_entry(node, type, member) : NULL
+#endif
-#define hlist_for_each_safe(pos, n, head) \
- for (pos = (head)->first; pos && ({ n = pos->next; 1; }); \
- pos = n)
+/**
+ * hlist_for_each - iterate over hlist nodes
+ * @node: hlist_node pointer used as iterator
+ * @head: pointer to the head of the hlist
+ *
+ * The nodes and the head of the hlist must be kept unmodified while
+ * iterating through it. Any modifications to the hlist will cause undefined
+ * behavior.
+ */
+#define hlist_for_each(node, head) \
+ for (node = (head)->first; \
+ node; \
+ node = node->next)
/**
- * hlist_for_each_entry - iterate over list of given type
- * @tpos: the type * to use as a loop cursor.
- * @pos: the &struct hlist_node to use as a loop cursor.
- * @head: the head for your list.
- * @member: the name of the hlist_node within the struct.
+ * hlist_for_each_entry_t - iterate over hlist entries
+ * @entry: @type pointer used as iterator
+ * @head: pointer to the head of the hlist
+ * @type: type of the entries containing the hlist nodes
+ * @member: name of the hlist_node member variable in struct @type
+ *
+ * The nodes and the head of the hlist must be kept unmodified while
+ * iterating through it. Any modifications to the hlist will cause undefined
+ * behavior.
+ *
+ * WARNING this functionality is not available in the Linux list implementation
*/
-#define hlist_for_each_entry(tpos, pos, head, member) \
- for (pos = (head)->first; \
- pos && \
- ({ tpos = hlist_entry(pos, typeof(*tpos), member); 1;}); \
- pos = pos->next)
+#define hlist_for_each_entry_t(entry, head, type, member) \
+ for (entry = hlist_entry_safe((head)->first, type, member); \
+ entry; \
+ entry = hlist_entry_safe(entry->member.next, type, member))
/**
- * hlist_for_each_entry_continue - iterate over a hlist continuing after current point
- * @tpos: the type * to use as a loop cursor.
- * @pos: the &struct hlist_node to use as a loop cursor.
- * @member: the name of the hlist_node within the struct.
+ * hlist_for_each_entry - iterate over hlist entries
+ * @entry: pointer used as iterator
+ * @head: pointer to the head of the hlist
+ * @member: name of the hlist_node member variable in struct type of @entry
+ *
+ * The nodes and the head of the hlist must be kept unmodified while
+ * iterating through it. Any modifications to the hlist will cause undefined
+ * behavior.
+ */
+#ifdef LIST_TYPEOF_USE
+#define hlist_for_each_entry(entry, head, member) \
+ hlist_for_each_entry_t(entry, head, __typeof__(*entry), member)
+#endif
+
+/**
+ * hlist_for_each_safe - iterate over hlist nodes and allow deletes
+ * @node: hlist_node pointer used as iterator
+ * @safe: hlist_node pointer used to store info for next entry in hlist
+ * @head: pointer to the head of the hlist
+ *
+ * The current node (iterator) is allowed to be removed from the hlist. Any
+ * other modifications to the hlist will cause undefined behavior.
*/
-#define hlist_for_each_entry_continue(tpos, pos, member) \
- for (pos = (pos)->next; \
- pos && \
- ({ tpos = hlist_entry(pos, typeof(*tpos), member); 1;}); \
- pos = pos->next)
+#define hlist_for_each_safe(node, safe, head) \
+ for (node = (head)->first; \
+ node && ((safe = node->next) || 1); \
+ node = safe)
/**
- * hlist_for_each_entry_from - iterate over a hlist continuing from current point
- * @tpos: the type * to use as a loop cursor.
- * @pos: the &struct hlist_node to use as a loop cursor.
- * @member: the name of the hlist_node within the struct.
+ * hlist_for_each_entry_safe_t - iterate over hlist entries and allow deletes
+ * @entry: @type pointer used as iterator
+ * @safe: hlist_node pointer used to store info for next entry in hlist
+ * @head: pointer to the head of the hlist
+ * @type: type of the entries containing the hlist nodes
+ * @member: name of the hlist_node member variable in struct @type
+ *
+ * The current node (iterator) is allowed to be removed from the hlist. Any
+ * other modifications to the hlist will cause undefined behavior.
+ *
+ * WARNING this functionality is not available in the Linux list implementation
*/
-#define hlist_for_each_entry_from(tpos, pos, member) \
- for (; pos && \
- ({ tpos = hlist_entry(pos, typeof(*tpos), member); 1;}); \
- pos = pos->next)
+#define hlist_for_each_entry_safe_t(entry, safe, head, type, member) \
+ for (entry = hlist_entry_safe((head)->first, type, member); \
+ entry && ((safe = entry->member.next) || 1); \
+ entry = hlist_entry_safe(safe, type, member))
/**
- * hlist_for_each_entry_safe - iterate over list of given type safe against removal of list entry
- * @tpos: the type * to use as a loop cursor.
- * @pos: the &struct hlist_node to use as a loop cursor.
- * @n: another &struct hlist_node to use as temporary storage
- * @head: the head for your list.
- * @member: the name of the hlist_node within the struct.
+ * hlist_for_each_entry_safe - iterate over hlist entries and allow deletes
+ * @entry: pointer used as iterator
+ * @safe: hlist_node pointer used to store info for next entry in hlist
+ * @head: pointer to the head of the hlist
+ * @member: name of the hlist_node member variable in struct type of @entry
+ *
+ * The current node (iterator) is allowed to be removed from the hlist. Any
+ * other modifications to the hlist will cause undefined behavior.
*/
-#define hlist_for_each_entry_safe(tpos, pos, n, head, member) \
- for (pos = (head)->first; \
- pos && ({ n = pos->next; 1; }) && \
- ({ tpos = hlist_entry(pos, typeof(*tpos), member); 1;}); \
- pos = n)
+#ifdef LIST_TYPEOF_USE
+#define hlist_for_each_entry_safe(entry, safe, head, member) \
+ hlist_for_each_entry_safe_t(entry, safe, head, __typeof__(*entry),\
+ member)
+#endif
+#ifdef __cplusplus
+}
#endif
+
+#endif /* __LINUX_LIKE_LIST_H__ */
