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 
00227 #define FOREACH_NODE_SAFE(n, p, l) \
00228     for( \
00229         (n) = (TYPEOF_OR_VOIDPTR(n))LIST_HEAD(l), (p) = ((Node *)(n))->succ; \
00230         ((Node *)(n))->succ; \
00231         (n) = (p), (p) = (TYPEOF_OR_VOIDPTR(n))(((Node *)(n))->succ) \
00232     )
00233 
00235 #define LIST_INIT(l) \
00236     do { \
00237         (l)->head.succ = (TYPEOF_OR_VOIDPTR((l)->head.succ)) &(l)->tail; \
00238         (l)->head.pred = NULL; \
00239         (l)->tail.succ = NULL; \
00240         (l)->tail.pred = (TYPEOF_OR_VOIDPTR((l)->tail.pred)) &(l)->head; \
00241     } while (0)
00242 
00243 #ifdef _DEBUG
00244 
00245     #define LIST_ASSERT_VALID(l) \
00246         do { \
00247             Node *n, *pred; \
00248             ASSERT((l)->head.succ != NULL); \
00249             ASSERT((l)->head.pred == NULL); \
00250             ASSERT((l)->tail.succ == NULL); \
00251             ASSERT((l)->tail.pred != NULL); \
00252             pred = &(l)->head; \
00253             FOREACH_NODE(n, l) \
00254             { \
00255                 ASSERT(n->pred == pred); \
00256                 pred = n; \
00257             } \
00258             ASSERT(n == &(l)->tail); \
00259         } while (0)
00260 
00262     #define LIST_ASSERT_NOT_CONTAINS(list,node) \
00263         do { \
00264             Node *ln; \
00265             ASSERT_VALID_PTR(list); \
00266             ASSERT_VALID_PTR(node); \
00267             FOREACH_NODE(ln, list) \
00268                 ASSERT(ln != (Node *)(node)); \
00269         } while (0)
00270 
00271     #define INVALIDATE_NODE(n) ((n)->succ = (n)->pred = NULL)
00272 #else
00273     #define LIST_ASSERT_VALID(l) do {} while (0)
00274     #define LIST_ASSERT_NOT_CONTAINS(list,node) do {} while (0)
00275     #define INVALIDATE_NODE(n) do {} while (0)
00276 #endif
00277 
00279 #define LIST_EMPTY(l)  ( (void *)((l)->head.succ) == (void *)(&(l)->tail) )
00280 
00282 #define ADDHEAD(l,n) \
00283     do { \
00284         LIST_ASSERT_NOT_CONTAINS((l),(n)); \
00285         (n)->succ = (l)->head.succ; \
00286         (n)->pred = (l)->head.succ->pred; \
00287         (n)->succ->pred = (n); \
00288         (n)->pred->succ = (n); \
00289     } while (0)
00290 
00292 #define ADDTAIL(l,n) \
00293     do { \
00294         LIST_ASSERT_NOT_CONTAINS((l),(n)); \
00295         (n)->succ = &(l)->tail; \
00296         (n)->pred = (l)->tail.pred; \
00297         (n)->pred->succ = (n); \
00298         (l)->tail.pred = (n); \
00299     } while (0)
00300 
00307 #define INSERT_BEFORE(n,ln) \
00308     do { \
00309         ASSERT_VALID_PTR(n); \
00310         ASSERT_VALID_PTR(ln); \
00311         (n)->succ = (ln); \
00312         (n)->pred = (ln)->pred; \
00313         (ln)->pred->succ = (n); \
00314         (ln)->pred = (n); \
00315     } while (0)
00316 
00323 #define REMOVE(n) \
00324     do { \
00325         ASSERT_VALID_PTR(n); \
00326         (n)->pred->succ = (n)->succ; \
00327         (n)->succ->pred = (n)->pred; \
00328         INVALIDATE_NODE(n); \
00329     } while (0)
00330 
00337 #define LIST_ENQUEUE_HEAD(list, node) \
00338     do { \
00339         PriNode *ln; \
00340         LIST_ASSERT_NOT_CONTAINS((list),(node)); \
00341         FOREACH_NODE(ln, (list)) \
00342             if (ln->pri <= (node)->pri) \
00343                 break; \
00344         INSERT_BEFORE(&(node)->link, &ln->link); \
00345     } while (0)
00346 
00353 #define LIST_ENQUEUE(list, node) \
00354     do { \
00355         PriNode *ln; \
00356         LIST_ASSERT_NOT_CONTAINS((list),(node)); \
00357         FOREACH_NODE(ln, (list)) \
00358             if (ln->pri < (node)->pri) \
00359                 break; \
00360         INSERT_BEFORE(&(node)->link, &ln->link); \
00361     } while (0)
00362 
00363
00369 INLINE Node *list_remHead(List *l)
00370 {
00371     Node *n;
00372
00373     ASSERT_VALID_PTR(l);
00374
00375     if (LIST_EMPTY(l))
00376         return (Node *)0;
00377
00378     n = l->head.succ; /* Get first node. */
00379     l->head.succ = n->succ; /* Link list head to second node. */
00380     n->succ->pred = &l->head; /* Link second node to list head. */
00381
00382     INVALIDATE_NODE(n);
00383     return n;
00384 }
00385
00391 INLINE Node *list_remTail(List *l)
00392 {
00393     Node *n;
00394
00395     ASSERT_VALID_PTR(l);
00396
00397     if (LIST_EMPTY(l))
00398         return NULL;
00399
00400     n = l->tail.pred; /* Get last node. */
00401     l->tail.pred = n->pred; /* Link list tail to second last node. */
00402     n->pred->succ = &l->tail; /* Link second last node to list tail. */
00403
00404     INVALIDATE_NODE(n);
00405     return n;
00406 }
00407  //defgroup list
00409
00410 #endif /* STRUCT_LIST_H */