Ignore:
File:
1 edited

Legend:

Unmodified
Added
Removed

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

    r0a02653 r14a60e3  
    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 {
    4344        struct link *prev;  /**< Pointer to the previous 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 *
    … …  
    5157 */
    5258#define LIST_INITIALIZE(name) \
    53         link_t name = { \
    54                 .prev = &name, \
    55                 .next = &name \
     59        list_t name = { \
     60                .head = { \
     61                        .prev = &(name).head, \
     62                        .next = &(name).head \
     63                } \
    5664        }
    5765
    … …  
    6068
    6169#define list_foreach(list, iterator) \
    62         for (link_t *iterator = (list).next; \
    63             iterator != &(list); iterator = iterator->next)
     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))
    6475
    6576/** Initialize doubly-linked circular list link
    … …  
    8091 * Initialize doubly-linked circular list.
    8192 *
    82  * @param list Pointer to link_t structure representing the list.
    83  *
    84  */
    85 NO_TRACE static inline void list_initialize(link_t *list)
    86 {
    87         list->prev = list;
    88         list->next = list;
     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;
    89122}
    90123
    … …  
    94127 *
    95128 * @param link Pointer to link_t structure to be added.
    96  * @param list Pointer to link_t structure representing the list.
    97  *
    98  */
    99 NO_TRACE static inline void list_prepend(link_t *link, link_t *list)
    100 {
    101         link->next = list->next;
    102         link->prev = list;
    103         list->next->prev = link;
    104         list->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);
    105135}
    106136
    … …  
    110140 *
    111141 * @param link Pointer to link_t structure to be added.
    112  * @param list Pointer to link_t structure representing the list.
    113  *
    114  */
    115 NO_TRACE static inline void list_append(link_t *link, link_t *list)
    116 {
    117         link->prev = list->prev;
    118         link->next = list;
    119         list->prev->next = link;
    120         list->prev = link;
    121 }
    122 
    123 /** Insert item before another item in doubly-linked circular list.
    124  *
    125  */
    126 static inline void list_insert_before(link_t *link, link_t *list)
    127 {
    128         list_append(link, list);
    129 }
    130 
    131 /** Insert item after another item in doubly-linked circular list.
    132  *
    133  */
    134 static inline void list_insert_after(link_t *link, link_t *list)
    135 {
    136         list_prepend(list, 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);
    137148}
    138149
    … …  
    147158NO_TRACE static inline void list_remove(link_t *link)
    148159{
    149         link->next->prev = link->prev;
    150         link->prev->next = link->next;
     160        if ((link->prev != NULL) && (link->next != NULL)) {
     161                link->next->prev = link->prev;
     162                link->prev->next = link->next;
     163        }
     164       
    151165        link_initialize(link);
    152166}
    … …  
    156170 * Query emptiness of doubly-linked circular list.
    157171 *
    158  * @param list Pointer to link_t structure representing the list.
    159  *
    160  */
    161 NO_TRACE static inline int list_empty(link_t *list)
    162 {
    163         return (list->next == list);
    164 }
    165 
    166 /** Get head item of a list.
    167  *
    168  * @param list Pointer to link_t structure representing the list.
     172 * @param list Pointer to lins_t structure.
     173 *
     174 */
     175NO_TRACE static inline int list_empty(list_t *list)
     176{
     177        return (list->head.next == &list->head);
     178}
     179
     180/** Get first item in list.
     181 *
     182 * @param list Pointer to list_t structure.
    169183 *
    170184 * @return Head item of the list.
    … …  
    172186 *
    173187 */
    174 static inline link_t *list_head(link_t *list)
    175 {
    176         return ((list->next == list) ? NULL : list->next);
     188static inline link_t *list_first(list_t *list)
     189{
     190        return ((list->head.next == &list->head) ? NULL : list->head.next);
     191}
     192
     193/** Get last item in list.
     194 *
     195 * @param list Pointer to list_t structure.
     196 *
     197 * @return Head item of the list.
     198 * @return NULL if the list is empty.
     199 *
     200 */
     201static inline link_t *list_last(list_t *list)
     202{
     203        return ((list->head.prev == &list->head) ? NULL : list->head.prev);
    177204}
    178205
    … …  
    231258}
    232259
    233 /** Get n-th item of a list.
     260/** Get n-th item in a list.
    234261 *
    235262 * @param list Pointer to link_t structure representing the list.
    … …  
    240267 *
    241268 */
    242 static inline link_t *list_nth(link_t *list, unsigned int n)
     269static inline link_t *list_nth(list_t *list, unsigned int n)
    243270{
    244271        unsigned int cnt = 0;
    … …  
    254281}
    255282
    256 extern int list_member(const link_t *, const link_t *);
    257 extern void list_concat(link_t *, link_t *);
    258 extern unsigned int list_count(const link_t *);
     283extern int list_member(const link_t *, const list_t *);
     284extern void list_concat(list_t *, list_t *);
     285extern unsigned int list_count(const list_t *);
    259286
    260287#endif
Note: See TracChangeset for help on using the changeset viewer.