BeRTOS
|
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 */