123456789101112131415161718192021222324252627282930313233343536373839404142434445464748495051525354555657585960616263646566676869707172737475767778798081828384858687888990919293949596979899100101102103104105106107108109110111112113114115116117118119120121122123124125126127128129130131132133134135136137138139140141142143144145146147148149150151152153154155156157158159160161162163164165166167168169170171172173174175176177178179180181182183184185186187188189190191192193194195196197198199200201202203204205206207208209210211212213214215216217218219220221222223224225226227228229230231232233234235236237238239240241242243244245246247248249250251252253254255256257258259260261262263264265266267268269270271272273274275276277278279280281282283284285286287288289290291292293294295296297298299300301302303304305306307308309310311312313314315316317318319320321322323324325326327328329330331332333334335336337338339340341342343344345346347348349350351352353354355356357358359360361 |
- /*
- * Copyright (c) 2009, 2010 Richard Braun.
- * All rights reserved.
- *
- * Redistribution and use in source and binary forms, with or without
- * modification, are permitted provided that the following conditions
- * are met:
- * 1. Redistributions of source code must retain the above copyright
- * notice, this rblist of conditions and the following disclaimer.
- * 2. Redistributions in binary form must reproduce the above copyright
- * notice, this rblist of conditions and the following disclaimer in the
- * documentation and/or other materials provided with the distribution.
- *
- * THIS SOFTWARE IS PROVIDED BY THE AUTHOR ``AS IS'' AND ANY EXPRESS OR
- * IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE IMPLIED WARRANTIES
- * OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE ARE DISCLAIMED.
- * IN NO EVENT SHALL THE AUTHOR BE LIABLE FOR ANY DIRECT, INDIRECT,
- * INCIDENTAL, SPECIAL, EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING, BUT
- * NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES; LOSS OF USE,
- * DATA, OR PROFITS; OR BUSINESS INTERRUPTION) HOWEVER CAUSED AND ON ANY
- * THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY, OR TORT
- * (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT OF THE USE OF
- * THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE.
- *
- *
- * Simple doubly-linked rblist.
- */
- #ifndef _KERN_rblist_H
- #define _KERN_rblist_H
- #include <stddef.h>
- #include <sys/types.h>
- #include <kern/macros.h>
- /*
- * Structure used as both head and node.
- *
- * This implementation relies on using the same type for both heads and nodes.
- *
- * It is recommended to encode the use of struct rblist variables in their names,
- * e.g. struct rblist free_rblist or struct rblist free_objects is a good hint for a
- * rblist of free objects. A declaration like struct rblist free_node clearly
- * indicates it is used as part of a node in the free rblist.
- */
- struct rblist {
- struct rblist *prev;
- struct rblist *next;
- };
- #define list rblist
- //undef if confliction
- /*
- * Static rblist initializer.
- */
- #define rblist_INITIALIZER(rblist) { &(rblist), &(rblist) }
- /*
- * Initialize a rblist.
- */
- static inline void rblist_init(struct rblist *rblist)
- {
- rblist->prev = rblist;
- rblist->next = rblist;
- }
- /*
- * Initialize a rblist node.
- *
- * An entry is in no rblist when its node members point to NULL.
- */
- static inline void rblist_node_init(struct rblist *node)
- {
- node->prev = NULL;
- node->next = NULL;
- }
- /*
- * Return true if node is in no rblist.
- */
- static inline int rblist_node_unlinked(const struct rblist *node)
- {
- return node->prev == NULL;
- }
- /*
- * Macro that evaluates to the address of the structure containing the
- * given node based on the given type and member.
- */
- #define rblist_entry(node, type, member) structof(node, type, member)
- /*
- * Return the first node of a rblist.
- */
- static inline struct rblist * rblist_first(const struct rblist *rblist)
- {
- return rblist->next;
- }
- /*
- * Return the last node of a rblist.
- */
- static inline struct rblist * rblist_last(const struct rblist *rblist)
- {
- return rblist->prev;
- }
- /*
- * Return the node next to the given node.
- */
- static inline struct rblist * rblist_next(const struct rblist *node)
- {
- return node->next;
- }
- /*
- * Return the node previous to the given node.
- */
- static inline struct rblist * rblist_prev(const struct rblist *node)
- {
- return node->prev;
- }
- /*
- * Get the first entry of a rblist.
- */
- #define rblist_first_entry(rblist, type, member) \
- rblist_entry(rblist_first(rblist), type, member)
- /*
- * Get the last entry of a rblist.
- */
- #define rblist_last_entry(rblist, type, member) \
- rblist_entry(rblist_last(rblist), type, member)
- /*
- * Return true if node is after the last or before the first node of the rblist.
- */
- static inline int rblist_end(const struct rblist *rblist, const struct rblist *node)
- {
- return rblist == node;
- }
- /*
- * Return true if rblist is empty.
- */
- static inline int rblist_empty(const struct rblist *rblist)
- {
- return rblist == rblist->next;
- }
- /*
- * Return true if rblist contains exactly one node.
- */
- static inline int rblist_singular(const struct rblist *rblist)
- {
- return (rblist != rblist->next) && (rblist->next == rblist->prev);
- }
- /*
- * Split rblist2 by moving its nodes up to (but not including) the given
- * node into rblist1 (which can be in a stale state).
- *
- * If rblist2 is empty, or node is rblist2 or rblist2->next, nothing is done.
- */
- static inline void rblist_split(struct rblist *rblist1, struct rblist *rblist2,
- struct rblist *node)
- {
- if (rblist_empty(rblist2) || (rblist2->next == node) || rblist_end(rblist2, node))
- return;
- rblist1->next = rblist2->next;
- rblist1->next->prev = rblist1;
- rblist1->prev = node->prev;
- node->prev->next = rblist1;
- rblist2->next = node;
- node->prev = rblist2;
- }
- /*
- * Append the nodes of rblist2 at the end of rblist1.
- *
- * After completion, rblist2 is stale.
- */
- static inline void rblist_concat(struct rblist *rblist1, const struct rblist *rblist2)
- {
- struct rblist *last1, *first2, *last2;
- if (rblist_empty(rblist2))
- return;
- last1 = rblist1->prev;
- first2 = rblist2->next;
- last2 = rblist2->prev;
- last1->next = first2;
- first2->prev = last1;
- last2->next = rblist1;
- rblist1->prev = last2;
- }
- /*
- * Set the new head of a rblist.
- *
- * This function is an optimized version of :
- * rblist_init(&new_rblist);
- * rblist_concat(&new_rblist, &old_rblist);
- *
- * After completion, old_head is stale.
- */
- static inline void rblist_set_head(struct rblist *new_head,
- const struct rblist *old_head)
- {
- if (rblist_empty(old_head)) {
- rblist_init(new_head);
- return;
- }
- *new_head = *old_head;
- new_head->next->prev = new_head;
- new_head->prev->next = new_head;
- }
- /*
- * Add a node between two nodes.
- */
- static inline void rblist_add(struct rblist *prev, struct rblist *next,
- struct rblist *node)
- {
- next->prev = node;
- node->next = next;
- prev->next = node;
- node->prev = prev;
- }
- /*
- * Insert a node at the head of a rblist.
- */
- static inline void rblist_insert_head(struct rblist *rblist, struct rblist *node)
- {
- rblist_add(rblist, rblist->next, node);
- }
- /*
- * Insert a node at the tail of a rblist.
- */
- static inline void rblist_insert_tail(struct rblist *rblist, struct rblist *node)
- {
- rblist_add(rblist->prev, rblist, node);
- }
- /*
- * Insert a node before another node.
- */
- static inline void rblist_insert_before(struct rblist *next, struct rblist *node)
- {
- rblist_add(next->prev, next, node);
- }
- /*
- * Insert a node after another node.
- */
- static inline void rblist_insert_after(struct rblist *prev, struct rblist *node)
- {
- rblist_add(prev, prev->next, node);
- }
- /*
- * Remove a node from a rblist.
- *
- * After completion, the node is stale.
- */
- static inline void rblist_remove(struct rblist *node)
- {
- node->prev->next = node->next;
- node->next->prev = node->prev;
- }
- /*
- * Forge a loop to process all nodes of a rblist.
- *
- * The node must not be altered during the loop.
- */
- #define rblist_for_each(rblist, node) \
- for (node = rblist_first(rblist); \
- !rblist_end(rblist, node); \
- node = rblist_next(node))
- /*
- * Forge a loop to process all nodes of a rblist.
- */
- #define rblist_for_each_safe(rblist, node, tmp) \
- for (node = rblist_first(rblist), tmp = rblist_next(node); \
- !rblist_end(rblist, node); \
- node = tmp, tmp = rblist_next(node))
- /*
- * Version of rblist_for_each() that processes nodes backward.
- */
- #define rblist_for_each_reverse(rblist, node) \
- for (node = rblist_last(rblist); \
- !rblist_end(rblist, node); \
- node = rblist_prev(node))
- /*
- * Version of rblist_for_each_safe() that processes nodes backward.
- */
- #define rblist_for_each_reverse_safe(rblist, node, tmp) \
- for (node = rblist_last(rblist), tmp = rblist_prev(node); \
- !rblist_end(rblist, node); \
- node = tmp, tmp = rblist_prev(node))
- /*
- * Forge a loop to process all entries of a rblist.
- *
- * The entry node must not be altered during the loop.
- */
- #define rblist_for_each_entry(rblist, entry, member) \
- for (entry = rblist_entry(rblist_first(rblist), typeof(*entry), member); \
- !rblist_end(rblist, &entry->member); \
- entry = rblist_entry(rblist_next(&entry->member), typeof(*entry), \
- member))
- /*
- * Forge a loop to process all entries of a rblist.
- */
- #define rblist_for_each_entry_safe(rblist, entry, tmp, member) \
- for (entry = rblist_entry(rblist_first(rblist), typeof(*entry), member), \
- tmp = rblist_entry(rblist_next(&entry->member), typeof(*entry), \
- member); \
- !rblist_end(rblist, &entry->member); \
- entry = tmp, tmp = rblist_entry(rblist_next(&entry->member), \
- typeof(*entry), member))
- /*
- * Version of rblist_for_each_entry() that processes entries backward.
- */
- #define rblist_for_each_entry_reverse(rblist, entry, member) \
- for (entry = rblist_entry(rblist_last(rblist), typeof(*entry), member); \
- !rblist_end(rblist, &entry->member); \
- entry = rblist_entry(rblist_prev(&entry->member), typeof(*entry), \
- member))
- /*
- * Version of rblist_for_each_entry_safe() that processes entries backward.
- */
- #define rblist_for_each_entry_reverse_safe(rblist, entry, tmp, member) \
- for (entry = rblist_entry(rblist_last(rblist), typeof(*entry), member), \
- tmp = rblist_entry(rblist_prev(&entry->member), typeof(*entry), \
- member); \
- !rblist_end(rblist, &entry->member); \
- entry = tmp, tmp = rblist_entry(rblist_prev(&entry->member), \
- typeof(*entry), member))
- #endif /* _KERN_rblist_H */
|