BeRTOS
list.h
Go to the documentation of this file.
00001 
00079 #ifndef STRUCT_LIST_H
00080 #define STRUCT_LIST_H
00081 
00082 #include <cfg/compiler.h> /* INLINE */
00083 #include <cfg/debug.h> /* ASSERT_VALID_PTR() */
00084 
00091 typedef struct _Node
00092 {
00093     struct _Node *succ;
00094     struct _Node *pred;
00095 } Node;
00096 
00106 typedef struct _List
00107 {
00108     Node head;
00109     Node tail;
00110 } List;
00111 
00115 typedef struct _PriNode
00116 {
00117     Node link;
00118     int  pri;
00119 } PriNode;
00120 
00121 
00152 #define DECLARE_NODE_ANON(T) \
00153     T *succ; T *pred;
00154 
00156 #define DECLARE_NODE_TYPE(T) \
00157     typedef struct T##Node { T *succ; T *pred; } T##Node
00158 
00160 #define DECLARE_LIST_TYPE(T) \
00161     DECLARE_NODE_TYPE(T); \
00162     typedef struct T##List { \
00163          T##Node head; \
00164          T##Node tail; \
00165     } T##List
00166 
00167 #define NODE_TYPE(T) T##Node
00168 #define LIST_TYPE(T) T##List
00169 
00175 #define LIST_HEAD(l) ((l)->head.succ)
00176 
00182 #define LIST_TAIL(l) ((l)->tail.pred)
00183 
00184 // TODO: move in compiler.h
00185 #if COMPILER_TYPEOF
00186     #define TYPEOF_OR_VOIDPTR(type) typeof(type)
00187 #else
00188     #define TYPEOF_OR_VOIDPTR(type) void *
00189 #endif
00190 
00198 #define FOREACH_NODE(n, l) \
00199     for( \
00200         (n) = (TYPEOF_OR_VOIDPTR(n))LIST_HEAD(l); \
00201         ((Node *)(n))->succ; \
00202         (n) = (TYPEOF_OR_VOIDPTR(n))(((Node *)(n))->succ) \
00203     )
00204 
00212 #define REVERSE_FOREACH_NODE(n, l) \
00213     for( \
00214         (n) = (TYPEOF_OR_VOIDPTR(n))LIST_TAIL(l); \
00215         ((Node *)(n))->pred; \
00216         (n) = (TYPEOF_OR_VOIDPTR(n))(((Node *)(n))->pred) \
00217     )
00218 
00220 #define LIST_INIT(l) \
00221     do { \
00222         (l)->head.succ = (TYPEOF_OR_VOIDPTR((l)->head.succ)) &(l)->tail; \
00223         (l)->head.pred = NULL; \
00224         (l)->tail.succ = NULL; \
00225         (l)->tail.pred = (TYPEOF_OR_VOIDPTR((l)->tail.pred)) &(l)->head; \
00226     } while (0)
00227 
00228 #ifdef _DEBUG
00229 
00230     #define LIST_ASSERT_VALID(l) \
00231         do { \
00232             Node *n, *pred; \
00233             ASSERT((l)->head.succ != NULL); \
00234             ASSERT((l)->head.pred == NULL); \
00235             ASSERT((l)->tail.succ == NULL); \
00236             ASSERT((l)->tail.pred != NULL); \
00237             pred = &(l)->head; \
00238             FOREACH_NODE(n, l) \
00239             { \
00240                 ASSERT(n->pred == pred); \
00241                 pred = n; \
00242             } \
00243             ASSERT(n == &(l)->tail); \
00244         } while (0)
00245 
00247     #define LIST_ASSERT_NOT_CONTAINS(list,node) \
00248         do { \
00249             Node *ln; \
00250             ASSERT_VALID_PTR(list); \
00251             ASSERT_VALID_PTR(node); \
00252             FOREACH_NODE(ln, list) \
00253                 ASSERT(ln != (Node *)(node)); \
00254         } while (0)
00255 
00256     #define INVALIDATE_NODE(n) ((n)->succ = (n)->pred = NULL)
00257 #else
00258     #define LIST_ASSERT_VALID(l) do {} while (0)
00259     #define LIST_ASSERT_NOT_CONTAINS(list,node) do {} while (0)
00260     #define INVALIDATE_NODE(n) do {} while (0)
00261 #endif
00262 
00264 #define LIST_EMPTY(l)  ( (void *)((l)->head.succ) == (void *)(&(l)->tail) )
00265 
00267 #define ADDHEAD(l,n) \
00268     do { \
00269         LIST_ASSERT_NOT_CONTAINS((l),(n)); \
00270         (n)->succ = (l)->head.succ; \
00271         (n)->pred = (l)->head.succ->pred; \
00272         (n)->succ->pred = (n); \
00273         (n)->pred->succ = (n); \
00274     } while (0)
00275 
00277 #define ADDTAIL(l,n) \
00278     do { \
00279         LIST_ASSERT_NOT_CONTAINS((l),(n)); \
00280         (n)->succ = &(l)->tail; \
00281         (n)->pred = (l)->tail.pred; \
00282         (n)->pred->succ = (n); \
00283         (l)->tail.pred = (n); \
00284     } while (0)
00285 
00292 #define INSERT_BEFORE(n,ln) \
00293     do { \
00294         ASSERT_VALID_PTR(n); \
00295         ASSERT_VALID_PTR(ln); \
00296         (n)->succ = (ln); \
00297         (n)->pred = (ln)->pred; \
00298         (ln)->pred->succ = (n); \
00299         (ln)->pred = (n); \
00300     } while (0)
00301 
00308 #define REMOVE(n) \
00309     do { \
00310         ASSERT_VALID_PTR(n); \
00311         (n)->pred->succ = (n)->succ; \
00312         (n)->succ->pred = (n)->pred; \
00313         INVALIDATE_NODE(n); \
00314     } while (0)
00315 
00322 #define LIST_ENQUEUE_HEAD(list, node) \
00323     do { \
00324         PriNode *ln; \
00325         LIST_ASSERT_NOT_CONTAINS((list),(node)); \
00326         FOREACH_NODE(ln, (list)) \
00327             if (ln->pri <= (node)->pri) \
00328                 break; \
00329         INSERT_BEFORE(&(node)->link, &ln->link); \
00330     } while (0)
00331 
00338 #define LIST_ENQUEUE(list, node) \
00339     do { \
00340         PriNode *ln; \
00341         LIST_ASSERT_NOT_CONTAINS((list),(node)); \
00342         FOREACH_NODE(ln, (list)) \
00343             if (ln->pri < (node)->pri) \
00344                 break; \
00345         INSERT_BEFORE(&(node)->link, &ln->link); \
00346     } while (0)
00347 
00348 
00354 INLINE Node *list_remHead(List *l)
00355 {
00356     Node *n;
00357 
00358     ASSERT_VALID_PTR(l);
00359 
00360     if (LIST_EMPTY(l))
00361         return (Node *)0;
00362 
00363     n = l->head.succ; /* Get first node. */
00364     l->head.succ = n->succ; /* Link list head to second node. */
00365     n->succ->pred = &l->head; /* Link second node to list head. */
00366 
00367     INVALIDATE_NODE(n);
00368     return n;
00369 }
00370 
00376 INLINE Node *list_remTail(List *l)
00377 {
00378     Node *n;
00379 
00380     ASSERT_VALID_PTR(l);
00381 
00382     if (LIST_EMPTY(l))
00383         return NULL;
00384 
00385     n = l->tail.pred; /* Get last node. */
00386     l->tail.pred = n->pred; /* Link list tail to second last node. */
00387     n->pred->succ = &l->tail; /* Link second last node to list tail. */
00388 
00389     INVALIDATE_NODE(n);
00390     return n;
00391 }
00392  //defgroup list
00394 
00395 #endif /* STRUCT_LIST_H */