Messages in this thread Patch in this message | | | Date | Tue, 22 Feb 2000 09:03:55 +0100 | From | Andreas Gruenbacher <> | Subject | Improved <linux/lists.h> |
| |
I've had some trouble using the queues defined in <linux/lists.h>. The attached version fixes some problems, and generally simplifies using the macros. Please consider replacing the current lists.h with the improved version.
I did the following changes:
1. QUEUE_INIT(), QUEUE_ENTER() Removed the ptype parameter, which is redundant. Instead uses typeof() (GCC specific).
2. Queues are now offset adjusted: Fields don't have to be at the same offset in the head and in queue entries. [In some cases you simply can't
3. Added QUEUE_END() which gives the offset and type adjusted value to use in loops etc. No explicit typecasts are necessary anymore :-) (See example).
4. DLIST_DELETE() Added the missing parentheses around the node parameter.
Can anybody tell me why QUEUE_EMPTY() tests two obviously equivalent conditions?
Regards, Andreas
------------------------ <lists.h> ------------------------ --- lists.h Tue Feb 22 08:28:25 2000 +++ lists2.h Tue Feb 22 08:50:25 2000 @@ -1,62 +1,68 @@ /* * lists.h: Simple list macros for Linux */ #define DLNODE(ptype) \ struct { \ ptype * dl_prev; \ ptype * dl_next; \ } #define DNODE_SINGLE(node) {(node),(node)} #define DNODE_NULL {0,0} #define DLIST_INIT(listnam) \ (listnam).dl_prev = &(listnam); \ (listnam).dl_next = &(listnam); #define DLIST_NEXT(listnam) listnam.dl_next #define DLIST_PREV(listnam) listnam.dl_prev #define DLIST_INSERT_AFTER(node, new, listnam) do { \ (new)->listnam.dl_prev = (node); \ (new)->listnam.dl_next = (node)->listnam.dl_next; \ (node)->listnam.dl_next->listnam.dl_prev = (new); \ (node)->listnam.dl_next = (new); \ } while (0) #define DLIST_INSERT_BEFORE(node, new, listnam) do { \ (new)->listnam.dl_next = (node); \ (new)->listnam.dl_prev = (node)->listnam.dl_prev; \ (node)->listnam.dl_prev->listnam.dl_next = (new); \ (node)->listnam.dl_prev = (new); \ } while (0) -#define DLIST_DELETE(node, listnam) do { \ - node->listnam.dl_prev->listnam.dl_next = \ - node->listnam.dl_next; \ - node->listnam.dl_next->listnam.dl_prev = \ - node->listnam.dl_prev; \ +#define DLIST_DELETE(node, listnam) do { \ + (node)->listnam.dl_prev->listnam.dl_next = \ + (node)->listnam.dl_next; \ + (node)->listnam.dl_next->listnam.dl_prev = \ + (node)->listnam.dl_prev; \ } while (0) /* * queue-style operations, which have a head and tail */ -#define QUEUE_INIT(head, listnam, ptype) \ - (head)->listnam.dl_prev = (head)->listnam.dl_next = (ptype)(head); +#define QUEUE_END(head, listnam) \ + (typeof((head)->listnam.dl_prev))((char *)(head) + \ + ((int)&(((typeof(head))0)->listnam) - \ + (int)&(((typeof((head)->listnam.dl_prev))0)->listnam))) + +#define QUEUE_INIT(head, listnam) \ + (head)->listnam.dl_prev = (head)->listnam.dl_next = \ + QUEUE_END(head, listnam) #define QUEUE_FIRST(head, listnam) (head)->DLIST_NEXT(listnam) #define QUEUE_LAST(head, listnam) (head)->DLIST_PREV(listnam) -#define QUEUE_EMPTY(head, listnam) \ - ((QUEUE_FIRST(head, listnam) == QUEUE_LAST(head, listnam)) && \ - ((u_long)QUEUE_FIRST(head, listnam) == (u_long)head)) +#define QUEUE_EMPTY(head, listnam) \ + (QUEUE_FIRST(head, listnam) == QUEUE_LAST(head, listnam) && \ + QUEUE_FIRST(head, listnam) == QUEUE_END(head)) -#define QUEUE_ENTER(head, new, listnam, ptype) do { \ - (new)->listnam.dl_prev = (ptype)(head); \ +#define QUEUE_ENTER(head, new, listnam) do { \ + (new)->listnam.dl_prev = QUEUE_END(head, listnam); \ (new)->listnam.dl_next = (head)->listnam.dl_next; \ (head)->listnam.dl_next->listnam.dl_prev = (new); \ (head)->listnam.dl_next = (new); \ } while (0) #define QUEUE_REMOVE(head, node, listnam) DLIST_DELETE(node, listnam) ------------------------ </lists.h> -----------------------
------------------------ <lists.c> ------------------------ #include <stdio.h> #include "lists2.h" /* Note that the offsets of the list field differ in struct node and struct queue. The old lists.h header causes memory corruption in that case. QUEUE_END() returns an offset-adjusted value of the type of queue nodes. */
struct node { int data; DLNODE(struct node) list; }; struct queue { DLNODE(struct node) list; }; int main(void) { struct queue queue; struct node n1, n2, n3, *n; n1.data = 1; n2.data = 2; n3.data = 3; QUEUE_INIT(&queue, list); QUEUE_ENTER(&queue, &n1, list); QUEUE_ENTER(&queue, &n2, list); QUEUE_ENTER(&queue, &n3, list); n=QUEUE_LAST(&queue, list); while (n != QUEUE_END(&queue, list)) { printf("%d\n", n->data); n=n->DLIST_PREV(list); } QUEUE_REMOVE(&queue, &n2, list); QUEUE_REMOVE(&queue, &n1, list); QUEUE_REMOVE(&queue, &n3, list); } ------------------------ </lists.c> ----------------------- ------------------------------------------------------------------------ Andreas Gruenbacher, a.gruenbacher@computer.org Contact information: http://www.bestbits.at/~agruenba - To unsubscribe from this list: send the line "unsubscribe linux-kernel" in the body of a message to majordomo@vger.rutgers.edu Please read the FAQ at http://www.tux.org/lkml/
| |