Ignore:
File:
1 edited

Legend:

Unmodified
Added
Removed

  • uspace/lib/c/include/adt/list.h

    rb72efe8 r63f8966  
    11/*
    22 * Copyright (c) 2001-2004 Jakub Jermar
    3  * Copyright (c) 2011 Jiri Svoboda
    43 * All rights reserved.
    54 *
    … …  
    3736#define LIBC_LIST_H_
    3837
    39 #include <assert.h>
    4038#include <unistd.h>
    4139
    42 /** Doubly linked list link. */
     40/** Doubly linked list head and link type. */
    4341typedef struct link {
    4442        struct link *prev;  /**< Pointer to the previous item in the list. */
    … …  
    4644} link_t;
    4745
    48 /** Doubly linked list. */
    49 typedef struct list {
    50         link_t head;  /**< List head. Does not have any data. */
    51 } list_t;
    52 
    5346/** Declare and initialize statically allocated list.
    5447 *
    5548 * @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)) - ((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)
     49 */
     50#define LIST_INITIALIZE(name)  link_t name = { \
     51        .prev = &name, \
     52        .next = &name \
     53}
    7554
    7655/** Initialize doubly-linked circular list link
    … …  
    7958 *
    8059 * @param link Pointer to link_t structure to be initialized.
    81  *
    8260 */
    8361static inline void link_initialize(link_t *link)
    … …  
    9169 * Initialize doubly-linked circular list.
    9270 *
    93  * @param list Pointer to list_t structure.
    94  *
    95  */
    96 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  */
    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;
     71 * @param head Pointer to link_t structure representing head of the list.
     72 */
     73static inline void list_initialize(link_t *head)
     74{
     75        head->prev = head;
     76        head->next = head;
    12277}
    12378
    … …  
    12782 *
    12883 * @param link Pointer to link_t structure to be added.
    129  * @param list Pointer to list_t structure.
    130  *
    131  */
    132 static inline void list_prepend(link_t *link, list_t *list)
    133 {
    134         list_insert_after(link, &list->head);
     84 * @param head Pointer to link_t structure representing head of the list.
     85 */
     86static inline void list_prepend(link_t *link, link_t *head)
     87{
     88        link->next = head->next;
     89        link->prev = head;
     90        head->next->prev = link;
     91        head->next = link;
    13592}
    13693
    … …  
    14097 *
    14198 * @param link Pointer to link_t structure to be added.
    142  * @param list Pointer to list_t structure.
    143  *
    144  */
    145 static inline void list_append(link_t *link, list_t *list)
    146 {
    147         list_insert_before(link, &list->head);
     99 * @param head Pointer to link_t structure representing head of the list.
     100 */
     101static inline void list_append(link_t *link, link_t *head)
     102{
     103        link->prev = head->prev;
     104        link->next = head;
     105        head->prev->next = link;
     106        head->prev = link;
     107}
     108
     109/** Insert item before another item in doubly-linked circular list. */
     110static inline void list_insert_before(link_t *l, link_t *r)
     111{
     112        list_append(l, r);
     113}
     114
     115/** Insert item after another item in doubly-linked circular list. */
     116static inline void list_insert_after(link_t *r, link_t *l)
     117{
     118        list_prepend(l, r);
    148119}
    149120
    … …  
    152123 * Remove item from doubly-linked circular list.
    153124 *
    154  * @param link Pointer to link_t structure to be removed from the list
    155  *             it is contained in.
    156  *
     125 * @param link Pointer to link_t structure to be removed from the list it is contained in.
    157126 */
    158127static inline void list_remove(link_t *link)
    … …  
    167136 * Query emptiness of doubly-linked circular list.
    168137 *
    169  * @param list Pointer to lins_t structure.
    170  *
    171  */
    172 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  */
    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 }
     138 * @param head Pointer to link_t structure representing head of the list.
     139 */
     140static inline int list_empty(link_t *head)
     141{
     142        return ((head->next == head) ? 1 : 0);
     143}
     144
    202145
    203146/** Split or concatenate headless doubly-linked circular list
    … …  
    208151 * concatenates splitted lists and splits concatenated lists.
    209152 *
    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  *
     153 * @param part1 Pointer to link_t structure leading the first (half of the headless) list.
     154 * @param part2 Pointer to link_t structure leading the second (half of the headless) list.
    215155 */
    216156static inline void headless_list_split_or_concat(link_t *part1, link_t *part2)
    … …  
    225165}
    226166
     167
    227168/** Split headless doubly-linked circular list
    228169 *
    229170 * Split headless doubly-linked circular list.
    230171 *
    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  *
     172 * @param part1 Pointer to link_t structure leading the first half of the headless list.
     173 * @param part2 Pointer to link_t structure leading the second half of the headless list.
    236174 */
    237175static inline void headless_list_split(link_t *part1, link_t *part2)
    … …  
    244182 * Concatenate two headless doubly-linked circular lists.
    245183 *
    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  *
     184 * @param part1 Pointer to link_t structure leading the first headless list.
     185 * @param part2 Pointer to link_t structure leading the second headless list.
    251186 */
    252187static inline void headless_list_concat(link_t *part1, link_t *part2)
    … …  
    255190}
    256191
    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 }
    279 
    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 *);
     192#define list_get_instance(link, type, member)  ((type *) (((void *)(link)) - ((void *) &(((type *) NULL)->member))))
     193
     194extern int list_member(const link_t *link, const link_t *head);
     195extern void list_concat(link_t *head1, link_t *head2);
     196extern unsigned int list_count(const link_t *link);
    283197
    284198#endif
Note: See TracChangeset for help on using the changeset viewer.