source: trunk/sys/libphoenix/list.h @ 422

Last change on this file since 422 was 1, checked in by alain, 8 years ago

First import

File size: 4.9 KB
Line 
1/* Copyright (c) 2007-2009, Stanford University
2* All rights reserved.
3*
4* Redistribution and use in source and binary forms, with or without
5* modification, are permitted provided that the following conditions are met:
6*     * Redistributions of source code must retain the above copyright
7*       notice, this list of conditions and the following disclaimer.
8*     * Redistributions in binary form must reproduce the above copyright
9*       notice, this list of conditions and the following disclaimer in the
10*       documentation and/or other materials provided with the distribution.
11*     * Neither the name of Stanford University nor the names of its
12*       contributors may be used to endorse or promote products derived from
13*       this software without specific prior written permission.
14*
15* THIS SOFTWARE IS PROVIDED BY STANFORD UNIVERSITY ``AS IS'' AND ANY
16* EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE IMPLIED
17* WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE ARE
18* DISCLAIMED. IN NO EVENT SHALL STANFORD UNIVERSITY BE LIABLE FOR ANY
19* DIRECT, INDIRECT, INCIDENTAL, SPECIAL, EXEMPLARY, OR CONSEQUENTIAL DAMAGES
20* (INCLUDING, BUT NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES;
21* LOSS OF USE, DATA, OR PROFITS; OR BUSINESS INTERRUPTION) HOWEVER CAUSED AND
22* ON ANY THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY, OR TORT
23* (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT OF THE USE OF THIS
24* SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE.
25*/ 
26
27#ifndef LIST_H
28#define LIST_H
29
30/* doubly linked circular list with dummy node */
31typedef struct list_ent list_ent;
32typedef struct list list;
33
34struct list_ent{
35    list_ent    *li_next;
36    list_ent    *li_prev;
37};
38
39struct list {
40    list_ent    lst_list;
41};
42
43#ifndef offsetof
44#define offsetof(TYPE, MEMBER) ((size_t)&((TYPE *) 0)->MEMBER)
45#endif
46
47#define list_entry(LIST_ELEM, STRUCT, MEMBER)         \
48        ((STRUCT *) ((uint8_t *) &(LIST_ELEM)->li_next    \
49                        - offsetof (STRUCT, MEMBER.li_next)))
50
51static inline void list_init(list* l)
52{
53    l->lst_list.li_next = &l->lst_list;
54    l->lst_list.li_prev = &l->lst_list;
55}
56
57static inline void list_ent_init(list_ent* li)
58{
59    li->li_next = NULL;
60    li->li_prev = NULL;
61}
62
63static inline list_ent* list_peek_head(list* l)
64{
65    if(&l->lst_list != l->lst_list.li_next)
66        return l->lst_list.li_next;
67    else
68        return NULL;
69}
70
71static inline list_ent* list_peek_tail(list* l)
72{
73    if(&l->lst_list != l->lst_list.li_prev)
74        return l->lst_list.li_prev;
75    else
76        return NULL;
77}
78
79static inline int list_is_empty(list* l)
80{
81    return (&l->lst_list == l->lst_list.li_next);
82}
83
84static inline void list_add_head(list* l, list_ent* toadd)
85{
86    list_ent*    ltop = &l->lst_list;
87    toadd->li_prev = ltop;
88    toadd->li_next = ltop->li_next;
89    ltop->li_next->li_prev = toadd;
90    ltop->li_next = toadd;
91}
92
93static inline void list_add_tail(list* l, list_ent* toadd)
94{
95    list_ent*    ltop = &l->lst_list;
96    toadd->li_next = ltop;
97    toadd->li_prev = ltop->li_prev;
98    ltop->li_prev->li_next = toadd;
99    ltop->li_prev = toadd;
100}
101
102static inline void list_insert_after(list_ent* chain, list_ent* toadd)
103{
104    toadd->li_prev = chain;
105    toadd->li_next = chain->li_next;
106    chain->li_next->li_prev = toadd;
107    chain->li_next = toadd;
108}
109
110static inline void list_insert_before(list_ent* chain, list_ent* toadd)
111{
112    toadd->li_next = chain;
113    toadd->li_prev = chain->li_prev;
114    chain->li_prev->li_next = toadd;
115    chain->li_prev = toadd;
116}
117
118static inline void list_remove(list_ent* elem)
119{
120    elem->li_next->li_prev = elem->li_prev;
121    elem->li_prev->li_next = elem->li_next;
122    elem->li_prev = NULL;
123    elem->li_next = NULL;
124}
125
126static inline list_ent* list_remove_head(list* l)
127{
128    if(l->lst_list.li_next != &l->lst_list){
129        list_ent    *head;
130        head = l->lst_list.li_next;
131        list_remove(head);
132        return head;
133    }else
134        return NULL;
135}
136
137static inline list_ent* list_remove_tail(list* l)
138{
139    if(l->lst_list.li_prev != &l->lst_list){
140        list_ent    *tail;
141        tail = l->lst_list.li_prev;
142        list_remove(l->lst_list.li_prev);
143        return tail;
144    }else
145        return NULL;
146}
147
148static inline void list_clear(list* l)
149{
150    l->lst_list.li_next = &l->lst_list;
151    l->lst_list.li_prev = &l->lst_list;
152}
153
154#define list_from(x, y)        for(; y != &((x)->lst_list); y = y->li_next)
155#define list_for_all(x, y)    for(y = (x)->lst_list.li_next; y != &((x)->lst_list); y = y->li_next)
156#define list_for_all_safe(x,y,z)\
157    for(y = (x)->lst_list.li_next, z = y->li_next; y != &((x)->lst_list); y = z, z = y->li_next)
158#define list_for_all_backwards(x, y) for(y = (x)->lst_list.li_prev; y != &((x)->lst_list); y = y->li_prev)
159#define list_for_all_backwards_safe(x,y,z)\
160    for(y = (x)->lst_list.li_prev, z = y->li_prev; y != &((x)->lst_list); y = z, z = y->li_prev)
161
162#endif
Note: See TracBrowser for help on using the repository browser.