kernel/generic/include/adt/list.h

   1 /*
   2  * Copyright (c) 2001-2004 Jakub Jermar
   3  * Copyright (c) 2013 Jiri Svoboda
   4  * All rights reserved.
   5  *
   6  * Redistribution and use in source and binary forms, with or without
   7  * modification, are permitted provided that the following conditions
   8  * are met:
   9  *
  10  * - Redistributions of source code must retain the above copyright
  11  *   notice, this list of conditions and the following disclaimer.
  12  * - Redistributions in binary form must reproduce the above copyright
  13  *   notice, this list of conditions and the following disclaimer in the
  14  *   documentation and/or other materials provided with the distribution.
  15  * - The name of the author may not be used to endorse or promote products
  16  *   derived from this software without specific prior written permission.
  17  *
  18  * THIS SOFTWARE IS PROVIDED BY THE AUTHOR ``AS IS'' AND ANY EXPRESS OR
  19  * IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE IMPLIED WARRANTIES
  20  * OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE ARE DISCLAIMED.
  21  * IN NO EVENT SHALL THE AUTHOR BE LIABLE FOR ANY DIRECT, INDIRECT,
  22  * INCIDENTAL, SPECIAL, EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING, BUT
  23  * NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES; LOSS OF USE,
  24  * DATA, OR PROFITS; OR BUSINESS INTERRUPTION) HOWEVER CAUSED AND ON ANY
  25  * THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY, OR TORT
  26  * (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT OF THE USE OF
  27  * THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE.
  28  */
  29
  30 /** @addtogroup genericadt
  31  * @{
  32  */
  33 /** @file
  34  */
  35
  36 #ifndef KERN_LIST_H_
  37 #define KERN_LIST_H_
  38
  39 #include <typedefs.h>
  40 #include <trace.h>
  41
  42 /** Doubly linked list link. */
  43 typedef struct link {
  44         struct link *prev;  /**< Pointer to the previous item in the list. */
  45         struct link *next;  /**< Pointer to the next item in the list. */
  46 } link_t;
  47
  48 /** Doubly linked list. */
  49 typedef struct list {
  50         link_t head;  /**< List head. Does not have any data. */
  51 } list_t;
  52
  53 /** Declare and initialize statically allocated list.
  54  *
  55  * @param name Name of the new statically allocated list.
  56  *
  57  */
  58 #define LIST_INITIALIZE(name) \
  59         list_t name = { \
  60                 .head = { \
  61                         .prev = &(name).head, \
  62                         .next = &(name).head \
  63                 } \
  64         }
  65
  66 #define list_get_instance(link, type, member) \
  67         ((type *) (((void *)(link)) - list_link_to_void(&(((type *) NULL)->member))))
  68
  69 #define list_foreach(list, member, itype, iterator) \
  70         for (itype *iterator = NULL; iterator == NULL; iterator =(itype *)1) \
  71             for (link_t *_link = (list).head.next; \
  72             iterator = list_get_instance(_link, itype, member), \
  73             _link != &(list).head; _link = _link->next)
  74
  75 #define assert_link_not_used(link) \
  76         ASSERT(((link)->prev == NULL) && ((link)->next == NULL))
  77
  78 /** Initialize doubly-linked circular list link
  79  *
  80  * Initialize doubly-linked list link.
  81  *
  82  * @param link Pointer to link_t structure to be initialized.
  83  *
  84  */
  85 NO_TRACE static inline void link_initialize(link_t *link)
  86 {
  87         link->prev = NULL;
  88         link->next = NULL;
  89 }
  90
  91 /** Initialize doubly-linked circular list
  92  *
  93  * Initialize doubly-linked circular list.
  94  *
  95  * @param list Pointer to list_t structure.
  96  *
  97  */
  98 NO_TRACE static inline void list_initialize(list_t *list)
  99 {
 100         list->head.prev = &list->head;
 101         list->head.next = &list->head;
 102 }
 103
 104 /** Insert item before another item in doubly-linked circular list.
 105  *
 106  */
 107 static inline void list_insert_before(link_t *lnew, link_t *lold)
 108 {
 109         lnew->next = lold;
 110         lnew->prev = lold->prev;
 111         lold->prev->next = lnew;
 112         lold->prev = lnew;
 113 }
 114
 115 /** Insert item after another item in doubly-linked circular list.
 116  *
 117  */
 118 static inline void list_insert_after(link_t *lnew, link_t *lold)
 119 {
 120         lnew->prev = lold;
 121         lnew->next = lold->next;
 122         lold->next->prev = lnew;
 123         lold->next = lnew;
 124 }
 125
 126 /** Add item to the beginning of doubly-linked circular list
 127  *
 128  * Add item to the beginning of doubly-linked circular list.
 129  *
 130  * @param link Pointer to link_t structure to be added.
 131  * @param list Pointer to list_t structure.
 132  *
 133  */
 134 NO_TRACE static inline void list_prepend(link_t *link, list_t *list)
 135 {
 136         list_insert_after(link, &list->head);
 137 }
 138
 139 /** Add item to the end of doubly-linked circular list
 140  *
 141  * Add item to the end of doubly-linked circular list.
 142  *
 143  * @param link Pointer to link_t structure to be added.
 144  * @param list Pointer to list_t structure.
 145  *
 146  */
 147 NO_TRACE static inline void list_append(link_t *link, list_t *list)
 148 {
 149         list_insert_before(link, &list->head);
 150 }
 151
 152 /** Remove item from doubly-linked circular list
 153  *
 154  * Remove item from doubly-linked circular list.
 155  *
 156  * @param link Pointer to link_t structure to be removed from the list
 157  *             it is contained in.
 158  *
 159  */
 160 NO_TRACE static inline void list_remove(link_t *link)
 161 {
 162         if ((link->prev != NULL) && (link->next != NULL)) {
 163                 link->next->prev = link->prev;
 164                 link->prev->next = link->next;
 165         }
 166
 167         link_initialize(link);
 168 }
 169
 170 /** Query emptiness of doubly-linked circular list
 171  *
 172  * Query emptiness of doubly-linked circular list.
 173  *
 174  * @param list Pointer to lins_t structure.
 175  *
 176  */
 177 NO_TRACE static inline int list_empty(const list_t *list)
 178 {
 179         return (list->head.next == &list->head);
 180 }
 181
 182 /** Get first item in list.
 183  *
 184  * @param list Pointer to list_t structure.
 185  *
 186  * @return Head item of the list.
 187  * @return NULL if the list is empty.
 188  *
 189  */
 190 static inline link_t *list_first(const list_t *list)
 191 {
 192         return ((list->head.next == &list->head) ? NULL : list->head.next);
 193 }
 194
 195 /** Get last item in list.
 196  *
 197  * @param list Pointer to list_t structure.
 198  *
 199  * @return Head item of the list.
 200  * @return NULL if the list is empty.
 201  *
 202  */
 203 static inline link_t *list_last(list_t *list)
 204 {
 205         return ((list->head.prev == &list->head) ? NULL : list->head.prev);
 206 }
 207
 208 /** Get next item in list.
 209  *
 210  * @param link Current item link
 211  * @param list List containing @a link
 212  *
 213  * @return Next item or NULL if @a link is the last item.
 214  */
 215 static inline link_t *list_next(link_t *link, const list_t *list)
 216 {
 217         return (link->next == &list->head) ? NULL : link->next;
 218 }
 219
 220 /** Get previous item in list.
 221  *
 222  * @param link Current item link
 223  * @param list List containing @a link
 224  *
 225  * @return Previous item or NULL if @a link is the first item.
 226  */
 227 static inline link_t *list_prev(link_t *link, const list_t *list)
 228 {
 229         return (link->prev == &list->head) ? NULL : link->prev;
 230 }
 231
 232 /** Split or concatenate headless doubly-linked circular list
 233  *
 234  * Split or concatenate headless doubly-linked circular list.
 235  *
 236  * Note that the algorithm works both directions:
 237  * concatenates splitted lists and splits concatenated lists.
 238  *
 239  * @param part1 Pointer to link_t structure leading the first
 240  *              (half of the headless) list.
 241  * @param part2 Pointer to link_t structure leading the second
 242  *              (half of the headless) list.
 243  *
 244  */
 245 NO_TRACE static inline void headless_list_split_or_concat(link_t *part1, link_t *part2)
 246 {
 247         part1->prev->next = part2;
 248         part2->prev->next = part1;
 249
 250         link_t *hlp = part1->prev;
 251
 252         part1->prev = part2->prev;
 253         part2->prev = hlp;
 254 }
 255
 256 /** Split headless doubly-linked circular list
 257  *
 258  * Split headless doubly-linked circular list.
 259  *
 260  * @param part1 Pointer to link_t structure leading
 261  *              the first half of the headless list.
 262  * @param part2 Pointer to link_t structure leading
 263  *              the second half of the headless list.
 264  *
 265  */
 266 NO_TRACE static inline void headless_list_split(link_t *part1, link_t *part2)
 267 {
 268         headless_list_split_or_concat(part1, part2);
 269 }
 270
 271 /** Concatenate two headless doubly-linked circular lists
 272  *
 273  * Concatenate two headless doubly-linked circular lists.
 274  *
 275  * @param part1 Pointer to link_t structure leading
 276  *              the first headless list.
 277  * @param part2 Pointer to link_t structure leading
 278  *              the second headless list.
 279  *
 280  */
 281 NO_TRACE static inline void headless_list_concat(link_t *part1, link_t *part2)
 282 {
 283         headless_list_split_or_concat(part1, part2);
 284 }
 285
 286 /** Get n-th item in a list.
 287  *
 288  * @param list Pointer to link_t structure representing the list.
 289  * @param n    Item number (indexed from zero).
 290  *
 291  * @return n-th item of the list.
 292  * @return NULL if no n-th item found.
 293  *
 294  */
 295 static inline link_t *list_nth(list_t *list, unsigned int n)
 296 {
 297         unsigned int cnt = 0;
 298         link_t *link;
 299
 300         link = list_first(list);
 301         while (link != NULL) {
 302                 if (cnt == n)
 303                         return link;
 304
 305                 cnt++;
 306                 link = list_next(link, list);
 307         }
 308
 309         return NULL;
 310 }
 311
 312 /** Verify that argument type is a pointer to link_t (at compile time).
 313  *
 314  * This can be used to check argument type in a macro.
 315  */
 316 static inline const void *list_link_to_void(const link_t *link)
 317 {
 318         return link;
 319 }
 320
 321 extern int list_member(const link_t *, const list_t *);
 322 extern void list_concat(list_t *, list_t *);
 323 extern unsigned int list_count(const list_t *);
 324
 325 #endif
 326
 327 /** @}
 328  */