lkml.org 
[lkml]   [2000]   [Feb]   [22]   [last100]   RSS Feed
Views: [wrap][no wrap]   [headers]  [forward] 
 
Messages in this thread
Patch in this message
/
Date
From
SubjectImproved <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/

\
 
 \ /
  Last update: 2005-03-22 13:56    [W:0.082 / U:0.708 seconds]
©2003-2020 Jasper Spaans|hosted at Digital Ocean and TransIP|Read the blog|Advertise on this site