From b03224b9a82a4d46fd1e469821975f9a5295ed40 Mon Sep 17 00:00:00 2001 From: Richard Braun Date: Thu, 4 Jan 2018 21:50:05 +0100 Subject: Move sources to new src/ directory --- src/hlist.h | 418 ++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++ 1 file changed, 418 insertions(+) create mode 100644 src/hlist.h (limited to 'src/hlist.h') diff --git a/src/hlist.h b/src/hlist.h new file mode 100644 index 0000000..dd32112 --- /dev/null +++ b/src/hlist.h @@ -0,0 +1,418 @@ +/* + * Copyright (c) 2017 Richard Braun. + * + * Permission is hereby granted, free of charge, to any person obtaining a + * copy of this software and associated documentation files (the "Software"), + * to deal in the Software without restriction, including without limitation + * the rights to use, copy, modify, merge, publish, distribute, sublicense, + * and/or sell copies of the Software, and to permit persons to whom the + * Software is furnished to do so, subject to the following conditions: + * + * The above copyright notice and this permission notice shall be included in + * all copies or substantial portions of the Software. + * + * THE SOFTWARE IS PROVIDED "AS IS", WITHOUT WARRANTY OF ANY KIND, EXPRESS OR + * IMPLIED, INCLUDING BUT NOT LIMITED TO THE WARRANTIES OF MERCHANTABILITY, + * FITNESS FOR A PARTICULAR PURPOSE AND NONINFRINGEMENT. IN NO EVENT SHALL THE + * AUTHORS OR COPYRIGHT HOLDERS BE LIABLE FOR ANY CLAIM, DAMAGES OR OTHER + * LIABILITY, WHETHER IN AN ACTION OF CONTRACT, TORT OR OTHERWISE, ARISING + * FROM, OUT OF OR IN CONNECTION WITH THE SOFTWARE OR THE USE OR OTHER + * DEALINGS IN THE SOFTWARE. + * + * Upstream site with license notes : + * http://git.sceen.net/rbraun/librbraun.git/ + * + * + * Doubly-linked list specialized for forward traversals and O(1) removals. + */ + +#ifndef _HLIST_H +#define _HLIST_H + +#include +#include + +#include "macros.h" + +/* + * List node. + * + * The pprev member points to another node member instead of another node, + * so that it may safely refer to the first member of the list head. Its + * main purpose is to allow O(1) removal. + */ +struct hlist_node { + struct hlist_node *next; + struct hlist_node **pprev; +}; + +/* + * List head. + */ +struct hlist { + struct hlist_node *first; +}; + +/* + * Static list initializer. + */ +#define HLIST_INITIALIZER(list) { NULL } + +/* + * Initialize a list. + */ +static inline void +hlist_init(struct hlist *list) +{ + list->first = NULL; +} + +/* + * Initialize a list node. + * + * A node is in no list when its pprev member points to NULL. + */ +static inline void +hlist_node_init(struct hlist_node *node) +{ + node->pprev = NULL; +} + +/* + * Return true if node is in no list. + */ +static inline bool +hlist_node_unlinked(const struct hlist_node *node) +{ + return node->pprev == NULL; +} + +/* + * Return the first node of a list. + */ +static inline struct hlist_node * +hlist_first(const struct hlist *list) +{ + return list->first; +} + +/* + * Return the node next to the given node. + */ +static inline struct hlist_node * +hlist_next(const struct hlist_node *node) +{ + return node->next; +} + +/* + * Return true if node is invalid and denotes the end of the list. + */ +static inline bool +hlist_end(const struct hlist_node *node) +{ + return node == NULL; +} + +/* + * Return true if list is empty. + */ +static inline bool +hlist_empty(const struct hlist *list) +{ + return list->first == NULL; +} + +/* + * Return true if list contains exactly one node. + */ +static inline bool +hlist_singular(const struct hlist *list) +{ + return !hlist_empty(list) && hlist_end(list->first->next); +} + +/* + * Set the new head of a list. + * + * After completion, old_head is stale. + */ +static inline void +hlist_set_head(struct hlist *new_head, const struct hlist *old_head) +{ + *new_head = *old_head; + + if (!hlist_empty(new_head)) { + new_head->first->pprev = &new_head->first; + } +} + +/* + * Insert a node at the head of a list. + */ +static inline void +hlist_insert_head(struct hlist *list, struct hlist_node *node) +{ + struct hlist_node *first; + + first = list->first; + node->next = first; + node->pprev = &list->first; + + if (first != NULL) { + first->pprev = &node->next; + } + + list->first = node; +} + +/* + * Insert a node before another node. + */ +static inline void +hlist_insert_before(struct hlist_node *next, struct hlist_node *node) +{ + node->next = next; + node->pprev = next->pprev; + next->pprev = &node->next; + *node->pprev = node; +} + +/* + * Insert a node after another node. + */ +static inline void +hlist_insert_after(struct hlist_node *prev, struct hlist_node *node) +{ + node->next = prev->next; + node->pprev = &prev->next; + + if (node->next != NULL) { + node->next->pprev = &node->next; + } + + prev->next = node; +} + +/* + * Remove a node from a list. + */ +static inline void +hlist_remove(struct hlist_node *node) +{ + if (node->next != NULL) { + node->next->pprev = node->pprev; + } + + *node->pprev = node->next; +} + +/* + * Macro that evaluates to the address of the structure containing the + * given node based on the given type and member. + */ +#define hlist_entry(node, type, member) structof(node, type, member) + +/* + * Get the first entry of a list. + */ +#define hlist_first_entry(list, type, member) \ +MACRO_BEGIN \ + struct hlist_node *___first; \ + \ + ___first = (list)->first; \ + hlist_end(___first) ? NULL : hlist_entry(___first, type, member); \ +MACRO_END + +/* + * Get the entry next to the given entry. + */ +#define hlist_next_entry(entry, member) \ +MACRO_BEGIN \ + struct hlist_node *___next; \ + \ + ___next = (entry)->member.next; \ + hlist_end(___next) \ + ? NULL \ + : hlist_entry(___next, typeof(*entry), member); \ +MACRO_END + +/* + * Forge a loop to process all nodes of a list. + * + * The node must not be altered during the loop. + */ +#define hlist_for_each(list, node) \ +for (node = hlist_first(list); \ + !hlist_end(node); \ + node = hlist_next(node)) + +/* + * Forge a loop to process all nodes of a list. + */ +#define hlist_for_each_safe(list, node, tmp) \ +for (node = hlist_first(list), \ + tmp = hlist_end(node) ? NULL : hlist_next(node); \ + !hlist_end(node); \ + node = tmp, \ + tmp = hlist_end(node) ? NULL : hlist_next(node)) + +/* + * Forge a loop to process all entries of a list. + * + * The entry node must not be altered during the loop. + */ +#define hlist_for_each_entry(list, entry, member) \ +for (entry = hlist_first_entry(list, typeof(*entry), member); \ + entry != NULL; \ + entry = hlist_next_entry(entry, member)) + +/* + * Forge a loop to process all entries of a list. + */ +#define hlist_for_each_entry_safe(list, entry, tmp, member) \ +for (entry = hlist_first_entry(list, typeof(*entry), member), \ + tmp = (entry == NULL) ? NULL : hlist_next_entry(entry, member); \ + entry != NULL; \ + entry = tmp, \ + tmp = (entry == NULL) ? NULL : hlist_next_entry(entry, member)) \ + +/* + * Lockless variants + * + * The hlist_end() function may be used from read-side critical sections. + */ + +/* + * These macros can be replaced by actual functions in an environment + * that provides lockless synchronization such as RCU. + */ +#define llsync_store_ptr(ptr, value) ((ptr) = (value)) +#define llsync_load_ptr(ptr) (ptr) + +/* + * Return the first node of a list. + */ +static inline struct hlist_node * +hlist_llsync_first(const struct hlist *list) +{ + return llsync_load_ptr(list->first); +} + +/* + * Return the node next to the given node. + */ +static inline struct hlist_node * +hlist_llsync_next(const struct hlist_node *node) +{ + return llsync_load_ptr(node->next); +} + +/* + * Insert a node at the head of a list. + */ +static inline void +hlist_llsync_insert_head(struct hlist *list, struct hlist_node *node) +{ + struct hlist_node *first; + + first = list->first; + node->next = first; + node->pprev = &list->first; + + if (first != NULL) { + first->pprev = &node->next; + } + + llsync_store_ptr(list->first, node); +} + +/* + * Insert a node before another node. + */ +static inline void +hlist_llsync_insert_before(struct hlist_node *next, struct hlist_node *node) +{ + node->next = next; + node->pprev = next->pprev; + next->pprev = &node->next; + llsync_store_ptr(*node->pprev, node); +} + +/* + * Insert a node after another node. + */ +static inline void +hlist_llsync_insert_after(struct hlist_node *prev, struct hlist_node *node) +{ + node->next = prev->next; + node->pprev = &prev->next; + + if (node->next != NULL) { + node->next->pprev = &node->next; + } + + llsync_store_ptr(prev->next, node); +} + +/* + * Remove a node from a list. + */ +static inline void +hlist_llsync_remove(struct hlist_node *node) +{ + if (node->next != NULL) { + node->next->pprev = node->pprev; + } + + llsync_store_ptr(*node->pprev, node->next); +} + +/* + * Macro that evaluates to the address of the structure containing the + * given node based on the given type and member. + */ +#define hlist_llsync_entry(node, type, member) \ + structof(llsync_load_ptr(node), type, member) + +/* + * Get the first entry of a list. + */ +#define hlist_llsync_first_entry(list, type, member) \ +MACRO_BEGIN \ + struct hlist_node *___first; \ + \ + ___first = hlist_llsync_first(list); \ + hlist_end(___first) ? NULL : hlist_entry(___first, type, member); \ +MACRO_END + +/* + * Get the entry next to the given entry. + */ +#define hlist_llsync_next_entry(entry, member) \ +MACRO_BEGIN \ + struct hlist_node *___next; \ + \ + ___next = hlist_llsync_next(&entry->member); \ + hlist_end(___next) \ + ? NULL \ + : hlist_entry(___next, typeof(*entry), member); \ +MACRO_END + +/* + * Forge a loop to process all nodes of a list. + */ +#define hlist_llsync_for_each(list, node) \ +for (node = hlist_llsync_first(list); \ + !hlist_end(node); \ + node = hlist_llsync_next(node)) + +/* + * Forge a loop to process all entries of a list. + */ +#define hlist_llsync_for_each_entry(list, entry, member) \ +for (entry = hlist_llsync_first_entry(list, typeof(*entry), member); \ + entry != NULL; \ + entry = hlist_llsync_next_entry(entry, member)) + +#endif /* _HLIST_H */ -- cgit v1.2.3