From mboxrd@z Thu Jan 1 00:00:00 1970 Received: from eggs.gnu.org ([140.186.70.92]:54307) by lists.gnu.org with esmtp (Exim 4.71) (envelope-from ) id 1RhmCA-00013O-K4 for qemu-devel@nongnu.org; Mon, 02 Jan 2012 13:01:15 -0500 Received: from Debian-exim by eggs.gnu.org with spam-scanned (Exim 4.71) (envelope-from ) id 1RhmC8-0001Aq-0h for qemu-devel@nongnu.org; Mon, 02 Jan 2012 13:01:14 -0500 Sender: Paolo Bonzini From: Paolo Bonzini Date: Mon, 2 Jan 2012 19:00:34 +0100 Message-Id: <1325527237-24146-6-git-send-email-pbonzini@redhat.com> In-Reply-To: <1325527237-24146-1-git-send-email-pbonzini@redhat.com> References: <1325527237-24146-1-git-send-email-pbonzini@redhat.com> Subject: [Qemu-devel] [PATCH 5/8] qemu-queue: really simplify QSIMPLEQ List-Id: List-Unsubscribe: , List-Archive: List-Post: List-Help: List-Subscribe: , To: qemu-devel@nongnu.org Cc: qemu-trivial@nongnu.org QSIMPLEQ is still relatively heavyweight when used as a free list, compared to a simple singly-linked list. One disadvantage is that it requires an initializer macro, unlike for example QLIST. The patch removes the double links so that there is a "really really simple" queue type. Signed-off-by: Paolo Bonzini --- qemu-queue.h | 57 +++++++++------------------------------------------------ 1 files changed, 9 insertions(+), 48 deletions(-) diff --git a/qemu-queue.h b/qemu-queue.h index 2214230..5f5b63a 100644 --- a/qemu-queue.h +++ b/qemu-queue.h @@ -51,12 +51,11 @@ * or after an existing element or at the head of the list. A list * may only be traversed in the forward direction. * - * A simple queue is headed by a pair of pointers, one the head of the - * list and the other to the tail of the list. The elements are singly - * linked to save space, so elements can only be removed from the - * head of the list. New elements can be added to the list after - * an existing element, at the head of the list, or at the end of the - * list. A simple queue may only be traversed in the forward direction. + * A simple queue is headed by a single forward pointer, and the elements + * are also singly linked to save space. Elements can only be removed + * from the head of the list. New elements can be added to the list after + * an existing element or at the head of the list. A simple queue may + * only be traversed in the forward direction. * * A tail queue is headed by a pair of pointers, one to the head of the * list and the other to the tail of the list. The elements are doubly @@ -166,11 +165,10 @@ struct { \ #define QSIMPLEQ_HEAD(name, type) \ struct name { \ struct type *sqh_first; /* first element */ \ - struct type **sqh_last; /* addr of last next element */ \ } #define QSIMPLEQ_HEAD_INITIALIZER(head) \ - { NULL, &(head).sqh_first } + { NULL } #define QSIMPLEQ_ENTRY(type) \ struct { \ @@ -182,43 +180,20 @@ struct { \ */ #define QSIMPLEQ_INIT(head) do { \ (head)->sqh_first = NULL; \ - (head)->sqh_last = &(head)->sqh_first; \ } while (/*CONSTCOND*/0) #define QSIMPLEQ_INSERT_HEAD(head, elm, field) do { \ - if (((elm)->field.sqe_next = (head)->sqh_first) == NULL) \ - (head)->sqh_last = &(elm)->field.sqe_next; \ + (elm)->field.sqe_next = (head)->sqh_first; \ (head)->sqh_first = (elm); \ } while (/*CONSTCOND*/0) -#define QSIMPLEQ_INSERT_TAIL(head, elm, field) do { \ - (elm)->field.sqe_next = NULL; \ - *(head)->sqh_last = (elm); \ - (head)->sqh_last = &(elm)->field.sqe_next; \ -} while (/*CONSTCOND*/0) - #define QSIMPLEQ_INSERT_AFTER(head, listelm, elm, field) do { \ - if (((elm)->field.sqe_next = (listelm)->field.sqe_next) == NULL) \ - (head)->sqh_last = &(elm)->field.sqe_next; \ + (elm)->field.sqe_next = (listelm)->field.sqe_next; \ (listelm)->field.sqe_next = (elm); \ } while (/*CONSTCOND*/0) #define QSIMPLEQ_REMOVE_HEAD(head, field) do { \ - if (((head)->sqh_first = (head)->sqh_first->field.sqe_next) == NULL)\ - (head)->sqh_last = &(head)->sqh_first; \ -} while (/*CONSTCOND*/0) - -#define QSIMPLEQ_REMOVE(head, elm, type, field) do { \ - if ((head)->sqh_first == (elm)) { \ - QSIMPLEQ_REMOVE_HEAD((head), field); \ - } else { \ - struct type *curelm = (head)->sqh_first; \ - while (curelm->field.sqe_next != (elm)) \ - curelm = curelm->field.sqe_next; \ - if ((curelm->field.sqe_next = \ - curelm->field.sqe_next->field.sqe_next) == NULL) \ - (head)->sqh_last = &(curelm)->field.sqe_next; \ - } \ + (head)->sqh_first = (head)->sqh_first->field.sqe_next; \ } while (/*CONSTCOND*/0) #define QSIMPLEQ_FOREACH(var, head, field) \ @@ -231,20 +206,6 @@ struct { \ (var) && ((next = ((var)->field.sqe_next)), 1); \ (var) = (next)) -#define QSIMPLEQ_CONCAT(head1, head2) do { \ - if (!QSIMPLEQ_EMPTY((head2))) { \ - *(head1)->sqh_last = (head2)->sqh_first; \ - (head1)->sqh_last = (head2)->sqh_last; \ - QSIMPLEQ_INIT((head2)); \ - } \ -} while (/*CONSTCOND*/0) - -#define QSIMPLEQ_LAST(head, type, field) \ - (QSIMPLEQ_EMPTY((head)) ? \ - NULL : \ - ((struct type *)(void *) \ - ((char *)((head)->sqh_last) - offsetof(struct type, field)))) - /* * Simple queue access methods. */ -- 1.7.7.1