Ignore:
File:
1 edited

Legend:

Unmodified
Added
Removed

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

    r7a0359b r74464e8  
    11/*
    22 * Copyright (c) 2001-2004 Jakub Jermar
     3 * Copyright (c) 2011 Jiri Svoboda
    34 * All rights reserved.
    45 *
    … …  
    3940#include <trace.h>
    4041
    41 /** Doubly linked list head and link type. */
     42/** Doubly linked list link. */
    4243typedef struct link {
    43         struct link *prev;      /**< Pointer to the previous item in the list. */
    44         struct link *next;      /**< Pointer to the next item in the list. */
     44        struct link *prev;  /**< Pointer to the previous item in the list. */
     45        struct link *next;  /**< Pointer to the next item in the list. */
    4546} link_t;
    4647
     48/** Doubly linked list. */
     49typedef struct list {
     50        link_t head;  /**< List head. Does not have any data. */
     51} list_t;
     52
    4753/** Declare and initialize statically allocated list.
    4854 *
    4955 * @param name Name of the new statically allocated list.
     56 *
    5057 */
    5158#define LIST_INITIALIZE(name) \
    52         link_t name = { .prev = &name, .next = &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)
    5375
    5476/** Initialize doubly-linked circular list link
    … …  
    5779 *
    5880 * @param link Pointer to link_t structure to be initialized.
     81 *
    5982 */
    6083NO_TRACE static inline void link_initialize(link_t *link)
    … …  
    6891 * Initialize doubly-linked circular list.
    6992 *
    70  * @param head Pointer to link_t structure representing head of the list.
    71  */
    72 NO_TRACE static inline void list_initialize(link_t *head)
    73 {
    74         head->prev = head;
    75         head->next = head;
     93 * @param list Pointer to list_t structure.
     94 *
     95 */
     96NO_TRACE static inline void list_initialize(list_t *list)
     97{
     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 */
     105static 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 */
     116static 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;
    76122}
    77123
    … …  
    81127 *
    82128 * @param link Pointer to link_t structure to be added.
    83  * @param head Pointer to link_t structure representing head of the list.
    84  */
    85 NO_TRACE static inline void list_prepend(link_t *link, link_t *head)
    86 {
    87         link->next = head->next;
    88         link->prev = head;
    89         head->next->prev = link;
    90         head->next = link;
     129 * @param list Pointer to list_t structure.
     130 *
     131 */
     132NO_TRACE static inline void list_prepend(link_t *link, list_t *list)
     133{
     134        list_insert_after(link, &list->head);
    91135}
    92136
    … …  
    96140 *
    97141 * @param link Pointer to link_t structure to be added.
    98  * @param head Pointer to link_t structure representing head of the list.
    99  */
    100 NO_TRACE static inline void list_append(link_t *link, link_t *head)
    101 {
    102         link->prev = head->prev;
    103         link->next = head;
    104         head->prev->next = link;
    105         head->prev = link;
     142 * @param list Pointer to list_t structure.
     143 *
     144 */
     145NO_TRACE static inline void list_append(link_t *link, list_t *list)
     146{
     147        list_insert_before(link, &list->head);
    106148}
    107149
    … …  
    110152 * Remove item from doubly-linked circular list.
    111153 *
    112  * @param link  Pointer to link_t structure to be removed from the list it is
    113  *              contained in.
     154 * @param link Pointer to link_t structure to be removed from the list
     155 *             it is contained in.
     156 *
    114157 */
    115158NO_TRACE static inline void list_remove(link_t *link)
    … …  
    124167 * Query emptiness of doubly-linked circular list.
    125168 *
    126  * @param head Pointer to link_t structure representing head of the list.
    127  */
    128 NO_TRACE static inline bool list_empty(link_t *head)
    129 {
    130         return head->next == head ? true : false;
    131 }
    132 
     169 * @param list Pointer to lins_t structure.
     170 *
     171 */
     172NO_TRACE static inline int list_empty(list_t *list)
     173{
     174        return (list->head.next == &list->head);
     175}
     176
     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 */
     185static 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 */
     198static inline link_t *list_last(list_t *list)
     199{
     200        return ((list->head.prev == &list->head) ? NULL : list->head.prev);
     201}
    133202
    134203/** Split or concatenate headless doubly-linked circular list
    … …  
    139208 * concatenates splitted lists and splits concatenated lists.
    140209 *
    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.
     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 *
    145215 */
    146216NO_TRACE static inline void headless_list_split_or_concat(link_t *part1, link_t *part2)
    147217{
    148         link_t *hlp;
    149 
    150218        part1->prev->next = part2;
    151         part2->prev->next = part1;     
    152         hlp = part1->prev;
     219        part2->prev->next = part1;
     220       
     221        link_t *hlp = part1->prev;
     222       
    153223        part1->prev = part2->prev;
    154224        part2->prev = hlp;
    155225}
    156226
    157 
    158227/** Split headless doubly-linked circular list
    159228 *
    160229 * Split headless doubly-linked circular list.
    161230 *
    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.
     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 *
    166236 */
    167237NO_TRACE static inline void headless_list_split(link_t *part1, link_t *part2)
    … …  
    174244 * Concatenate two headless doubly-linked circular lists.
    175245 *
    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.
     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 *
    178251 */
    179252NO_TRACE static inline void headless_list_concat(link_t *part1, link_t *part2)
    … …  
    182255}
    183256
    184 #define list_get_instance(link, type, member) \
    185         ((type *)(((uint8_t *)(link)) - ((uint8_t *)&(((type *)NULL)->member))))
    186 
    187 extern bool list_member(const link_t *link, const link_t *head);
    188 extern void list_concat(link_t *head1, link_t *head2);
     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 */
     266static 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}
     279
     280extern int list_member(const link_t *, const list_t *);
     281extern void list_concat(list_t *, list_t *);
     282extern unsigned int list_count(const list_t *);
    189283
    190284#endif
Note: See TracChangeset for help on using the changeset viewer.