kernel/generic/include/adt/list.h

   1 /*
   2  * Copyright (c) 2001-2004 Jakub Jermar
   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  *
   9  * - Redistributions of source code must retain the above copyright
  10  *   notice, this list of conditions and the following disclaimer.
  11  * - Redistributions in binary form must reproduce the above copyright
  12  *   notice, this list of conditions and the following disclaimer in the
  13  *   documentation and/or other materials provided with the distribution.
  14  * - The name of the author may not be used to endorse or promote products
  15  *   derived from this software without specific prior written permission.
  16  *
  17  * THIS SOFTWARE IS PROVIDED BY THE AUTHOR ``AS IS'' AND ANY EXPRESS OR
  18  * IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE IMPLIED WARRANTIES
  19  * OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE ARE DISCLAIMED.
  20  * IN NO EVENT SHALL THE AUTHOR BE LIABLE FOR ANY DIRECT, INDIRECT,
  21  * INCIDENTAL, SPECIAL, EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING, BUT
  22  * NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES; LOSS OF USE,
  23  * DATA, OR PROFITS; OR BUSINESS INTERRUPTION) HOWEVER CAUSED AND ON ANY
  24  * THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY, OR TORT
  25  * (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT OF THE USE OF
  26  * THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE.
  27  */
  28
  29 /** @addtogroup genericadt
  30  * @{
  31  */
  32 /** @file
  33  */
  34
  35 #ifndef KERN_LIST_H_
  36 #define KERN_LIST_H_
  37
  38 #include <arch/types.h>
  39 #include <typedefs.h>
  40
  41 /** Doubly linked list head and link type. */
  42 struct link {
  43         link_t *prev;   /**< Pointer to the previous item in the list. */
  44         link_t *next;   /**< Pointer to the next item in the list. */
  45 };
  46
  47 /** Declare and initialize statically allocated list.
  48  *
  49  * @param name Name of the new statically allocated list.
  50  */
  51 #define LIST_INITIALIZE(name)           link_t name = { .prev = &name, .next = &name }
  52
  53 /** Initialize doubly-linked circular list link
  54  *
  55  * Initialize doubly-linked list link.
  56  *
  57  * @param link Pointer to link_t structure to be initialized.
  58  */
  59 static inline void link_initialize(link_t *link)
  60 {
  61         link->prev = NULL;
  62         link->next = NULL;
  63 }
  64
  65 /** Initialize doubly-linked circular list
  66  *
  67  * Initialize doubly-linked circular list.
  68  *
  69  * @param head Pointer to link_t structure representing head of the list.
  70  */
  71 static inline void list_initialize(link_t *head)
  72 {
  73         head->prev = head;
  74         head->next = head;
  75 }
  76
  77 /** Add item to the beginning of doubly-linked circular list
  78  *
  79  * Add item to the beginning of doubly-linked circular list.
  80  *
  81  * @param link Pointer to link_t structure to be added.
  82  * @param head Pointer to link_t structure representing head of the list.
  83  */
  84 static inline void list_prepend(link_t *link, link_t *head)
  85 {
  86         link->next = head->next;
  87         link->prev = head;
  88         head->next->prev = link;
  89         head->next = link;
  90 }
  91
  92 /** Add item to the end of doubly-linked circular list
  93  *
  94  * Add item to the end of doubly-linked circular list.
  95  *
  96  * @param link Pointer to link_t structure to be added.
  97  * @param head Pointer to link_t structure representing head of the list.
  98  */
  99 static inline void list_append(link_t *link, link_t *head)
 100 {
 101         link->prev = head->prev;
 102         link->next = head;
 103         head->prev->next = link;
 104         head->prev = link;
 105 }
 106
 107 /** Remove item from doubly-linked circular list
 108  *
 109  * Remove item from doubly-linked circular list.
 110  *
 111  * @param link Pointer to link_t structure to be removed from the list it is contained in.
 112  */
 113 static inline void list_remove(link_t *link)
 114 {
 115         link->next->prev = link->prev;
 116         link->prev->next = link->next;
 117         link_initialize(link);
 118 }
 119
 120 /** Query emptiness of doubly-linked circular list
 121  *
 122  * Query emptiness of doubly-linked circular list.
 123  *
 124  * @param head Pointer to link_t structure representing head of the list.
 125  */
 126 static inline bool list_empty(link_t *head)
 127 {
 128         return head->next == head ? true : false;
 129 }
 130
 131
 132 /** Split or concatenate headless doubly-linked circular list
 133  *
 134  * Split or concatenate headless doubly-linked circular list.
 135  *
 136  * Note that the algorithm works both directions:
 137  * concatenates splitted lists and splits concatenated lists.
 138  *
 139  * @param part1 Pointer to link_t structure leading the first (half of the headless) list.
 140  * @param part2 Pointer to link_t structure leading the second (half of the headless) list.
 141  */
 142 static inline void headless_list_split_or_concat(link_t *part1, link_t *part2)
 143 {
 144         link_t *hlp;
 145
 146         part1->prev->next = part2;
 147         part2->prev->next = part1;
 148         hlp = part1->prev;
 149         part1->prev = part2->prev;
 150         part2->prev = hlp;
 151 }
 152
 153
 154 /** Split headless doubly-linked circular list
 155  *
 156  * Split headless doubly-linked circular list.
 157  *
 158  * @param part1 Pointer to link_t structure leading the first half of the headless list.
 159  * @param part2 Pointer to link_t structure leading the second half of the headless list.
 160  */
 161 static inline void headless_list_split(link_t *part1, link_t *part2)
 162 {
 163         headless_list_split_or_concat(part1, part2);
 164 }
 165
 166 /** Concatenate two headless doubly-linked circular lists
 167  *
 168  * Concatenate two headless doubly-linked circular lists.
 169  *
 170  * @param part1 Pointer to link_t structure leading the first headless list.
 171  * @param part2 Pointer to link_t structure leading the second headless list.
 172  */
 173 static inline void headless_list_concat(link_t *part1, link_t *part2)
 174 {
 175         headless_list_split_or_concat(part1, part2);
 176 }
 177
 178 #define list_get_instance(link,type,member) (type *)(((uint8_t*)(link))-((uint8_t*)&(((type *)NULL)->member)))
 179
 180 extern bool list_member(const link_t *link, const link_t *head);
 181 extern void list_concat(link_t *head1, link_t *head2);
 182
 183 #endif
 184
 185 /** @}
 186  */