Ignore:
File:
1 edited

Legend:

Unmodified
Added
Removed

  • kernel/generic/include/adt/list.h

    r74464e8 r7a0359b  
    11/*
    22 * Copyright (c) 2001-2004 Jakub Jermar
    3  * Copyright (c) 2011 Jiri Svoboda
    43 * All rights reserved.
    54 *
    … …  
    4039#include <trace.h>
    4140
    42 /** Doubly linked list link. */
     41/** Doubly linked list head and link type. */
    4342typedef 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. */
     43        struct link *prev;      /**< Pointer to the previous item in the list. */
     44        struct link *next;      /**< Pointer to the next item in the list. */
    4645} 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;
    5246
    5347/** Declare and initialize statically allocated list.
    5448 *
    5549 * @param name Name of the new statically allocated list.
    56  *
    5750 */
    5851#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)) - ((void *) &(((type *) NULL)->member))))
    68 
    69 #define list_foreach(list, iterator) \
    70         for (link_t *iterator = (list).head.next; \
    71             iterator != &(list).head; iterator = iterator->next)
    72 
    73 #define assert_link_not_used(link) \
    74         ASSERT((link)->prev == NULL && (link)->next == NULL)
     52        link_t name = { .prev = &name, .next = &name }
    7553
    7654/** Initialize doubly-linked circular list link
    … …  
    7957 *
    8058 * @param link Pointer to link_t structure to be initialized.
    81  *
    8259 */
    8360NO_TRACE static inline void link_initialize(link_t *link)
    … …  
    9168 * Initialize doubly-linked circular list.
    9269 *
    93  * @param list Pointer to list_t structure.
    94  *
     70 * @param head Pointer to link_t structure representing head of the list.
    9571 */
    96 NO_TRACE static inline void list_initialize(list_t *list)
     72NO_TRACE static inline void list_initialize(link_t *head)
    9773{
    98         list->head.prev = &list->head;
    99         list->head.next = &list->head;
    100 }
    101 
    102 /** Insert item before another item in doubly-linked circular list.
    103  *
    104  */
    105 static inline void list_insert_before(link_t *lnew, link_t *lold)
    106 {
    107         lnew->next = lold;
    108         lnew->prev = lold->prev;
    109         lold->prev->next = lnew;
    110         lold->prev = lnew;
    111 }
    112 
    113 /** Insert item after another item in doubly-linked circular list.
    114  *
    115  */
    116 static inline void list_insert_after(link_t *lnew, link_t *lold)
    117 {
    118         lnew->prev = lold;
    119         lnew->next = lold->next;
    120         lold->next->prev = lnew;
    121         lold->next = lnew;
     74        head->prev = head;
     75        head->next = head;
    12276}
    12377
    … …  
    12781 *
    12882 * @param link Pointer to link_t structure to be added.
    129  * @param list Pointer to list_t structure.
    130  *
     83 * @param head Pointer to link_t structure representing head of the list.
    13184 */
    132 NO_TRACE static inline void list_prepend(link_t *link, list_t *list)
     85NO_TRACE static inline void list_prepend(link_t *link, link_t *head)
    13386{
    134         list_insert_after(link, &list->head);
     87        link->next = head->next;
     88        link->prev = head;
     89        head->next->prev = link;
     90        head->next = link;
    13591}
    13692
    … …  
    14096 *
    14197 * @param link Pointer to link_t structure to be added.
    142  * @param list Pointer to list_t structure.
    143  *
     98 * @param head Pointer to link_t structure representing head of the list.
    14499 */
    145 NO_TRACE static inline void list_append(link_t *link, list_t *list)
     100NO_TRACE static inline void list_append(link_t *link, link_t *head)
    146101{
    147         list_insert_before(link, &list->head);
     102        link->prev = head->prev;
     103        link->next = head;
     104        head->prev->next = link;
     105        head->prev = link;
    148106}
    149107
    … …  
    152110 * Remove item from doubly-linked circular list.
    153111 *
    154  * @param link Pointer to link_t structure to be removed from the list
    155  *             it is contained in.
    156  *
     112 * @param link  Pointer to link_t structure to be removed from the list it is
     113 *              contained in.
    157114 */
    158115NO_TRACE static inline void list_remove(link_t *link)
    … …  
    167124 * Query emptiness of doubly-linked circular list.
    168125 *
    169  * @param list Pointer to lins_t structure.
    170  *
     126 * @param head Pointer to link_t structure representing head of the list.
    171127 */
    172 NO_TRACE static inline int list_empty(list_t *list)
     128NO_TRACE static inline bool list_empty(link_t *head)
    173129{
    174         return (list->head.next == &list->head);
     130        return head->next == head ? true : false;
    175131}
    176132
    177 /** Get first item in list.
    178  *
    179  * @param list Pointer to list_t structure.
    180  *
    181  * @return Head item of the list.
    182  * @return NULL if the list is empty.
    183  *
    184  */
    185 static inline link_t *list_first(list_t *list)
    186 {
    187         return ((list->head.next == &list->head) ? NULL : list->head.next);
    188 }
    189 
    190 /** Get last item in list.
    191  *
    192  * @param list Pointer to list_t structure.
    193  *
    194  * @return Head item of the list.
    195  * @return NULL if the list is empty.
    196  *
    197  */
    198 static inline link_t *list_last(list_t *list)
    199 {
    200         return ((list->head.prev == &list->head) ? NULL : list->head.prev);
    201 }
    202133
    203134/** Split or concatenate headless doubly-linked circular list
    … …  
    208139 * concatenates splitted lists and splits concatenated lists.
    209140 *
    210  * @param part1 Pointer to link_t structure leading the first
    211  *              (half of the headless) list.
    212  * @param part2 Pointer to link_t structure leading the second
    213  *              (half of the headless) list.
    214  *
     141 * @param part1 Pointer to link_t structure leading the first (half of the
     142 *              headless) list.
     143 * @param part2 Pointer to link_t structure leading the second (half of the
     144 *              headless) list.
    215145 */
    216146NO_TRACE static inline void headless_list_split_or_concat(link_t *part1, link_t *part2)
    217147{
     148        link_t *hlp;
     149
    218150        part1->prev->next = part2;
    219         part2->prev->next = part1;
    220        
    221         link_t *hlp = part1->prev;
    222        
     151        part2->prev->next = part1;     
     152        hlp = part1->prev;
    223153        part1->prev = part2->prev;
    224154        part2->prev = hlp;
    225155}
     156
    226157
    227158/** Split headless doubly-linked circular list
    … …  
    229160 * Split headless doubly-linked circular list.
    230161 *
    231  * @param part1 Pointer to link_t structure leading
    232  *              the first half of the headless list.
    233  * @param part2 Pointer to link_t structure leading
    234  *              the second half of the headless list.
    235  *
     162 * @param part1 Pointer to link_t structure leading the first half of the
     163 *              headless list.
     164 * @param part2 Pointer to link_t structure leading the second half of the
     165 *              headless list.
    236166 */
    237167NO_TRACE static inline void headless_list_split(link_t *part1, link_t *part2)
    … …  
    244174 * Concatenate two headless doubly-linked circular lists.
    245175 *
    246  * @param part1 Pointer to link_t structure leading
    247  *              the first headless list.
    248  * @param part2 Pointer to link_t structure leading
    249  *              the second headless list.
    250  *
     176 * @param part1 Pointer to link_t structure leading the first headless list.
     177 * @param part2 Pointer to link_t structure leading the second headless list.
    251178 */
    252179NO_TRACE static inline void headless_list_concat(link_t *part1, link_t *part2)
    … …  
    255182}
    256183
    257 /** Get n-th item in a list.
    258  *
    259  * @param list Pointer to link_t structure representing the list.
    260  * @param n    Item number (indexed from zero).
    261  *
    262  * @return n-th item of the list.
    263  * @return NULL if no n-th item found.
    264  *
    265  */
    266 static inline link_t *list_nth(list_t *list, unsigned int n)
    267 {
    268         unsigned int cnt = 0;
    269        
    270         list_foreach(*list, link) {
    271                 if (cnt == n)
    272                         return link;
    273                
    274                 cnt++;
    275         }
    276        
    277         return NULL;
    278 }
     184#define list_get_instance(link, type, member) \
     185        ((type *)(((uint8_t *)(link)) - ((uint8_t *)&(((type *)NULL)->member))))
    279186
    280 extern int list_member(const link_t *, const list_t *);
    281 extern void list_concat(list_t *, list_t *);
    282 extern unsigned int list_count(const list_t *);
     187extern bool list_member(const link_t *link, const link_t *head);
     188extern void list_concat(link_t *head1, link_t *head2);
    283189
    284190#endif
Note: See TracChangeset for help on using the changeset viewer.