Repository : ssh://git@diktynna/alfred On branches: main,main
commit ba393626fa1a0140c02d9af5cb769b9543ecff92 Author: Sven Eckelmann sven@narfation.org Date: Sat Jan 4 09:47:16 2025 +0100
alfred: Use same list implementation as batctl
Signed-off-by: Sven Eckelmann sven@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@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__ */