Return to list.h CVS log

Up to [GnuMach] / Gnu-Mach / kern

Annotation of Gnu-Mach/kern/list.h, revision 1.1

1.1     ! root        1: /*
        !             2:  * Copyright (c) 2009, 2010 Richard Braun.
        !             3:  * All rights reserved.
        !             4:  *
        !             5:  * Redistribution and use in source and binary forms, with or without
        !             6:  * modification, are permitted provided that the following conditions
        !             7:  * are met:
        !             8:  * 1. Redistributions of source code must retain the above copyright
        !             9:  *    notice, this list of conditions and the following disclaimer.
        !            10:  * 2. Redistributions in binary form must reproduce the above copyright
        !            11:  *    notice, this list of conditions and the following disclaimer in the
        !            12:  *    documentation and/or other materials provided with the distribution.
        !            13:  *
        !            14:  * THIS SOFTWARE IS PROVIDED BY THE AUTHOR ``AS IS'' AND ANY EXPRESS OR
        !            15:  * IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE IMPLIED WARRANTIES
        !            16:  * OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE ARE DISCLAIMED.
        !            17:  * IN NO EVENT SHALL THE AUTHOR BE LIABLE FOR ANY DIRECT, INDIRECT,
        !            18:  * INCIDENTAL, SPECIAL, EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING, BUT
        !            19:  * NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES; LOSS OF USE,
        !            20:  * DATA, OR PROFITS; OR BUSINESS INTERRUPTION) HOWEVER CAUSED AND ON ANY
        !            21:  * THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY, OR TORT
        !            22:  * (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT OF THE USE OF
        !            23:  * THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE.
        !            24:  *
        !            25:  *
        !            26:  * Simple doubly-linked list.
        !            27:  */
        !            28: 
        !            29: #ifndef _KERN_LIST_H
        !            30: #define _KERN_LIST_H
        !            31: 
        !            32: #include <stddef.h>
        !            33: #include <sys/types.h>
        !            34: 
        !            35: #define structof(ptr, type, member) \
        !            36:     ((type *)((char *)ptr - offsetof(type, member)))
        !            37: 
        !            38: /*
        !            39:  * Structure used as both head and node.
        !            40:  *
        !            41:  * This implementation relies on using the same type for both heads and nodes.
        !            42:  *
        !            43:  * It is recommended to encode the use of struct list variables in their names,
        !            44:  * e.g. struct list free_list or struct list free_objects is a good hint for a
        !            45:  * list of free objects. A declaration like struct list free_node clearly
        !            46:  * indicates it is used as part of a node in the free list.
        !            47:  */
        !            48: struct list {
        !            49:     struct list *prev;
        !            50:     struct list *next;
        !            51: };
        !            52: 
        !            53: /*
        !            54:  * Static list initializer.
        !            55:  */
        !            56: #define LIST_INITIALIZER(list) { &(list), &(list) }
        !            57: 
        !            58: /*
        !            59:  * Initialize a list.
        !            60:  */
        !            61: static inline void list_init(struct list *list)
        !            62: {
        !            63:     list->prev = list;
        !            64:     list->next = list;
        !            65: }
        !            66: 
        !            67: /*
        !            68:  * Initialize a list node.
        !            69:  *
        !            70:  * An entry is in no list when its node members point to NULL.
        !            71:  */
        !            72: static inline void list_node_init(struct list *node)
        !            73: {
        !            74:     node->prev = NULL;
        !            75:     node->next = NULL;
        !            76: }
        !            77: 
        !            78: /*
        !            79:  * Return true if node is in no list.
        !            80:  */
        !            81: static inline int list_node_unlinked(const struct list *node)
        !            82: {
        !            83:     return node->prev == NULL;
        !            84: }
        !            85: 
        !            86: /*
        !            87:  * Macro that evaluates to the address of the structure containing the
        !            88:  * given node based on the given type and member.
        !            89:  */
        !            90: #define list_entry(node, type, member) structof(node, type, member)
        !            91: 
        !            92: /*
        !            93:  * Return the first node of a list.
        !            94:  */
        !            95: static inline struct list * list_first(const struct list *list)
        !            96: {
        !            97:     return list->next;
        !            98: }
        !            99: 
        !           100: /*
        !           101:  * Return the last node of a list.
        !           102:  */
        !           103: static inline struct list * list_last(const struct list *list)
        !           104: {
        !           105:     return list->prev;
        !           106: }
        !           107: 
        !           108: /*
        !           109:  * Return the node next to the given node.
        !           110:  */
        !           111: static inline struct list * list_next(const struct list *node)
        !           112: {
        !           113:     return node->next;
        !           114: }
        !           115: 
        !           116: /*
        !           117:  * Return the node previous to the given node.
        !           118:  */
        !           119: static inline struct list * list_prev(const struct list *node)
        !           120: {
        !           121:     return node->prev;
        !           122: }
        !           123: 
        !           124: /*
        !           125:  * Get the first entry of a list.
        !           126:  */
        !           127: #define list_first_entry(list, type, member) \
        !           128:     list_entry(list_first(list), type, member)
        !           129: 
        !           130: /*
        !           131:  * Get the last entry of a list.
        !           132:  */
        !           133: #define list_last_entry(list, type, member) \
        !           134:     list_entry(list_last(list), type, member)
        !           135: 
        !           136: /*
        !           137:  * Return true if node is after the last or before the first node of the list.
        !           138:  */
        !           139: static inline int list_end(const struct list *list, const struct list *node)
        !           140: {
        !           141:     return list == node;
        !           142: }
        !           143: 
        !           144: /*
        !           145:  * Return true if list is empty.
        !           146:  */
        !           147: static inline int list_empty(const struct list *list)
        !           148: {
        !           149:     return list == list->next;
        !           150: }
        !           151: 
        !           152: /*
        !           153:  * Return true if list contains exactly one node.
        !           154:  */
        !           155: static inline int list_singular(const struct list *list)
        !           156: {
        !           157:     return (list != list->next) && (list->next == list->prev);
        !           158: }
        !           159: 
        !           160: /*
        !           161:  * Split list2 by moving its nodes up to (but not including) the given
        !           162:  * node into list1 (which can be in a stale state).
        !           163:  *
        !           164:  * If list2 is empty, or node is list2 or list2->next, nothing is done.
        !           165:  */
        !           166: static inline void list_split(struct list *list1, struct list *list2,
        !           167:                               struct list *node)
        !           168: {
        !           169:     if (list_empty(list2) || (list2->next == node) || list_end(list2, node))
        !           170:         return;
        !           171: 
        !           172:     list1->next = list2->next;
        !           173:     list1->next->prev = list1;
        !           174: 
        !           175:     list1->prev = node->prev;
        !           176:     node->prev->next = list1;
        !           177: 
        !           178:     list2->next = node;
        !           179:     node->prev = list2;
        !           180: }
        !           181: 
        !           182: /*
        !           183:  * Append the nodes of list2 at the end of list1.
        !           184:  *
        !           185:  * After completion, list2 is stale.
        !           186:  */
        !           187: static inline void list_concat(struct list *list1, const struct list *list2)
        !           188: {
        !           189:     struct list *last1, *first2, *last2;
        !           190: 
        !           191:     if (list_empty(list2))
        !           192:         return;
        !           193: 
        !           194:     last1 = list1->prev;
        !           195:     first2 = list2->next;
        !           196:     last2 = list2->prev;
        !           197: 
        !           198:     last1->next = first2;
        !           199:     first2->prev = last1;
        !           200: 
        !           201:     last2->next = list1;
        !           202:     list1->prev = last2;
        !           203: }
        !           204: 
        !           205: /*
        !           206:  * Set the new head of a list.
        !           207:  *
        !           208:  * This function is an optimized version of :
        !           209:  * list_init(&new_list);
        !           210:  * list_concat(&new_list, &old_list);
        !           211:  *
        !           212:  * After completion, old_head is stale.
        !           213:  */
        !           214: static inline void list_set_head(struct list *new_head,
        !           215:                                  const struct list *old_head)
        !           216: {
        !           217:     if (list_empty(old_head)) {
        !           218:         list_init(new_head);
        !           219:         return;
        !           220:     }
        !           221: 
        !           222:     *new_head = *old_head;
        !           223:     new_head->next->prev = new_head;
        !           224:     new_head->prev->next = new_head;
        !           225: }
        !           226: 
        !           227: /*
        !           228:  * Add a node between two nodes.
        !           229:  */
        !           230: static inline void list_add(struct list *prev, struct list *next,
        !           231:                             struct list *node)
        !           232: {
        !           233:     next->prev = node;
        !           234:     node->next = next;
        !           235: 
        !           236:     prev->next = node;
        !           237:     node->prev = prev;
        !           238: }
        !           239: 
        !           240: /*
        !           241:  * Insert a node at the head of a list.
        !           242:  */
        !           243: static inline void list_insert_head(struct list *list, struct list *node)
        !           244: {
        !           245:     list_add(list, list->next, node);
        !           246: }
        !           247: 
        !           248: /*
        !           249:  * Insert a node at the tail of a list.
        !           250:  */
        !           251: static inline void list_insert_tail(struct list *list, struct list *node)
        !           252: {
        !           253:     list_add(list->prev, list, node);
        !           254: }
        !           255: 
        !           256: /*
        !           257:  * Insert a node before another node.
        !           258:  */
        !           259: static inline void list_insert_before(struct list *next, struct list *node)
        !           260: {
        !           261:     list_add(next->prev, next, node);
        !           262: }
        !           263: 
        !           264: /*
        !           265:  * Insert a node after another node.
        !           266:  */
        !           267: static inline void list_insert_after(struct list *prev, struct list *node)
        !           268: {
        !           269:     list_add(prev, prev->next, node);
        !           270: }
        !           271: 
        !           272: /*
        !           273:  * Remove a node from a list.
        !           274:  *
        !           275:  * After completion, the node is stale.
        !           276:  */
        !           277: static inline void list_remove(struct list *node)
        !           278: {
        !           279:     node->prev->next = node->next;
        !           280:     node->next->prev = node->prev;
        !           281: }
        !           282: 
        !           283: /*
        !           284:  * Forge a loop to process all nodes of a list.
        !           285:  *
        !           286:  * The node must not be altered during the loop.
        !           287:  */
        !           288: #define list_for_each(list, node)   \
        !           289: for (node = list_first(list);       \
        !           290:      !list_end(list, node);         \
        !           291:      node = list_next(node))
        !           292: 
        !           293: /*
        !           294:  * Forge a loop to process all nodes of a list.
        !           295:  */
        !           296: #define list_for_each_safe(list, node, tmp)             \
        !           297: for (node = list_first(list), tmp = list_next(node);    \
        !           298:      !list_end(list, node);                             \
        !           299:      node = tmp, tmp = list_next(node))
        !           300: 
        !           301: /*
        !           302:  * Version of list_for_each() that processes nodes backward.
        !           303:  */
        !           304: #define list_for_each_reverse(list, node)   \
        !           305: for (node = list_last(list);                \
        !           306:      !list_end(list, node);                 \
        !           307:      node = list_prev(node))
        !           308: 
        !           309: /*
        !           310:  * Version of list_for_each_safe() that processes nodes backward.
        !           311:  */
        !           312: #define list_for_each_reverse_safe(list, node, tmp) \
        !           313: for (node = list_last(list), tmp = list_prev(node); \
        !           314:      !list_end(list, node);                         \
        !           315:      node = tmp, tmp = list_prev(node))
        !           316: 
        !           317: /*
        !           318:  * Forge a loop to process all entries of a list.
        !           319:  *
        !           320:  * The entry node must not be altered during the loop.
        !           321:  */
        !           322: #define list_for_each_entry(list, entry, member)                    \
        !           323: for (entry = list_entry(list_first(list), typeof(*entry), member);  \
        !           324:      !list_end(list, &entry->member);                               \
        !           325:      entry = list_entry(list_next(&entry->member), typeof(*entry),  \
        !           326:                         member))
        !           327: 
        !           328: /*
        !           329:  * Forge a loop to process all entries of a list.
        !           330:  */
        !           331: #define list_for_each_entry_safe(list, entry, tmp, member)          \
        !           332: for (entry = list_entry(list_first(list), typeof(*entry), member),  \
        !           333:        tmp = list_entry(list_next(&entry->member), typeof(*entry),  \
        !           334:                         member);                                    \
        !           335:      !list_end(list, &entry->member);                               \
        !           336:      entry = tmp, tmp = list_entry(list_next(&entry->member),       \
        !           337:                                    typeof(*entry), member))
        !           338: 
        !           339: /*
        !           340:  * Version of list_for_each_entry() that processes entries backward.
        !           341:  */
        !           342: #define list_for_each_entry_reverse(list, entry, member)            \
        !           343: for (entry = list_entry(list_last(list), typeof(*entry), member);   \
        !           344:      !list_end(list, &entry->member);                               \
        !           345:      entry = list_entry(list_prev(&entry->member), typeof(*entry),  \
        !           346:                         member))
        !           347: 
        !           348: /*
        !           349:  * Version of list_for_each_entry_safe() that processes entries backward.
        !           350:  */
        !           351: #define list_for_each_entry_reverse_safe(list, entry, tmp, member)  \
        !           352: for (entry = list_entry(list_last(list), typeof(*entry), member),   \
        !           353:        tmp = list_entry(list_prev(&entry->member), typeof(*entry),  \
        !           354:                         member);                                    \
        !           355:      !list_end(list, &entry->member);                               \
        !           356:      entry = tmp, tmp = list_entry(list_prev(&entry->member),       \
        !           357:                                    typeof(*entry), member))
        !           358: 
        !           359: #endif /* _KERN_LIST_H */

This archive runs on limited infrastructure. Preserving old code on modern bandwidth. Automated agents are requested to crawl responsibly.