* @(#)queue.h 8.5 (Berkeley) 8/20/94
*/
-#ifndef QEMU_SYS_QUEUE_H_
-#define QEMU_SYS_QUEUE_H_
+#ifndef QEMU_SYS_QUEUE_H
+#define QEMU_SYS_QUEUE_H
/*
* This file defines four types of data structures: singly-linked lists,
(head)->slh_first = (elm); \
} while (/*CONSTCOND*/0)
-#define QSLIST_INSERT_HEAD_ATOMIC(head, elm, field) do { \
- do { \
- (elm)->field.sle_next = (head)->slh_first; \
- } while (atomic_cmpxchg(&(head)->slh_first, (elm)->field.sle_next, \
- (elm)) != (elm)->field.sle_next); \
+#define QSLIST_INSERT_HEAD_ATOMIC(head, elm, field) do { \
+ typeof(elm) save_sle_next; \
+ do { \
+ save_sle_next = (elm)->field.sle_next = (head)->slh_first; \
+ } while (atomic_cmpxchg(&(head)->slh_first, save_sle_next, (elm)) != \
+ save_sle_next); \
} while (/*CONSTCOND*/0)
#define QSLIST_MOVE_ATOMIC(dest, src) do { \
} \
} while (/*CONSTCOND*/0)
+#define QSIMPLEQ_PREPEND(head1, head2) do { \
+ if (!QSIMPLEQ_EMPTY((head2))) { \
+ *(head2)->sqh_last = (head1)->sqh_first; \
+ (head1)->sqh_first = (head2)->sqh_first; \
+ QSIMPLEQ_INIT((head2)); \
+ } \
+} while (/*CONSTCOND*/0)
+
#define QSIMPLEQ_LAST(head, type, field) \
(QSIMPLEQ_EMPTY((head)) ? \
NULL : \
/*
* Simple queue access methods.
*/
+#define QSIMPLEQ_EMPTY_ATOMIC(head) (atomic_read(&((head)->sqh_first)) == NULL)
#define QSIMPLEQ_EMPTY(head) ((head)->sqh_first == NULL)
#define QSIMPLEQ_FIRST(head) ((head)->sqh_first)
#define QSIMPLEQ_NEXT(elm, field) ((elm)->field.sqe_next)
+typedef struct QTailQLink {
+ void *tql_next;
+ struct QTailQLink *tql_prev;
+} QTailQLink;
/*
- * Tail queue definitions.
+ * Tail queue definitions. The union acts as a poor man template, as if
+ * it were QTailQLink<type>.
*/
-#define Q_TAILQ_HEAD(name, type, qual) \
-struct name { \
- qual type *tqh_first; /* first element */ \
- qual type *qual *tqh_last; /* addr of last next element */ \
+#define QTAILQ_HEAD(name, type) \
+union name { \
+ struct type *tqh_first; /* first element */ \
+ QTailQLink tqh_circ; /* link for circular backwards list */ \
}
-#define QTAILQ_HEAD(name, type) Q_TAILQ_HEAD(name, struct type,)
#define QTAILQ_HEAD_INITIALIZER(head) \
- { NULL, &(head).tqh_first }
+ { .tqh_circ = { NULL, &(head).tqh_circ } }
-#define Q_TAILQ_ENTRY(type, qual) \
-struct { \
- qual type *tqe_next; /* next element */ \
- qual type *qual *tqe_prev; /* address of previous next element */\
+#define QTAILQ_ENTRY(type) \
+union { \
+ struct type *tqe_next; /* next element */ \
+ QTailQLink tqe_circ; /* link for circular backwards list */ \
}
-#define QTAILQ_ENTRY(type) Q_TAILQ_ENTRY(struct type,)
/*
* Tail queue functions.
*/
#define QTAILQ_INIT(head) do { \
(head)->tqh_first = NULL; \
- (head)->tqh_last = &(head)->tqh_first; \
+ (head)->tqh_circ.tql_prev = &(head)->tqh_circ; \
} while (/*CONSTCOND*/0)
#define QTAILQ_INSERT_HEAD(head, elm, field) do { \
if (((elm)->field.tqe_next = (head)->tqh_first) != NULL) \
- (head)->tqh_first->field.tqe_prev = \
- &(elm)->field.tqe_next; \
+ (head)->tqh_first->field.tqe_circ.tql_prev = \
+ &(elm)->field.tqe_circ; \
else \
- (head)->tqh_last = &(elm)->field.tqe_next; \
+ (head)->tqh_circ.tql_prev = &(elm)->field.tqe_circ; \
(head)->tqh_first = (elm); \
- (elm)->field.tqe_prev = &(head)->tqh_first; \
+ (elm)->field.tqe_circ.tql_prev = &(head)->tqh_circ; \
} while (/*CONSTCOND*/0)
#define QTAILQ_INSERT_TAIL(head, elm, field) do { \
(elm)->field.tqe_next = NULL; \
- (elm)->field.tqe_prev = (head)->tqh_last; \
- *(head)->tqh_last = (elm); \
- (head)->tqh_last = &(elm)->field.tqe_next; \
+ (elm)->field.tqe_circ.tql_prev = (head)->tqh_circ.tql_prev; \
+ (head)->tqh_circ.tql_prev->tql_next = (elm); \
+ (head)->tqh_circ.tql_prev = &(elm)->field.tqe_circ; \
} while (/*CONSTCOND*/0)
#define QTAILQ_INSERT_AFTER(head, listelm, elm, field) do { \
if (((elm)->field.tqe_next = (listelm)->field.tqe_next) != NULL)\
- (elm)->field.tqe_next->field.tqe_prev = \
- &(elm)->field.tqe_next; \
+ (elm)->field.tqe_next->field.tqe_circ.tql_prev = \
+ &(elm)->field.tqe_circ; \
else \
- (head)->tqh_last = &(elm)->field.tqe_next; \
+ (head)->tqh_circ.tql_prev = &(elm)->field.tqe_circ; \
(listelm)->field.tqe_next = (elm); \
- (elm)->field.tqe_prev = &(listelm)->field.tqe_next; \
+ (elm)->field.tqe_circ.tql_prev = &(listelm)->field.tqe_circ; \
} while (/*CONSTCOND*/0)
-#define QTAILQ_INSERT_BEFORE(listelm, elm, field) do { \
- (elm)->field.tqe_prev = (listelm)->field.tqe_prev; \
- (elm)->field.tqe_next = (listelm); \
- *(listelm)->field.tqe_prev = (elm); \
- (listelm)->field.tqe_prev = &(elm)->field.tqe_next; \
+#define QTAILQ_INSERT_BEFORE(listelm, elm, field) do { \
+ (elm)->field.tqe_circ.tql_prev = (listelm)->field.tqe_circ.tql_prev; \
+ (elm)->field.tqe_next = (listelm); \
+ (listelm)->field.tqe_circ.tql_prev->tql_next = (elm); \
+ (listelm)->field.tqe_circ.tql_prev = &(elm)->field.tqe_circ; \
} while (/*CONSTCOND*/0)
#define QTAILQ_REMOVE(head, elm, field) do { \
if (((elm)->field.tqe_next) != NULL) \
- (elm)->field.tqe_next->field.tqe_prev = \
- (elm)->field.tqe_prev; \
+ (elm)->field.tqe_next->field.tqe_circ.tql_prev = \
+ (elm)->field.tqe_circ.tql_prev; \
else \
- (head)->tqh_last = (elm)->field.tqe_prev; \
- *(elm)->field.tqe_prev = (elm)->field.tqe_next; \
+ (head)->tqh_circ.tql_prev = (elm)->field.tqe_circ.tql_prev; \
+ (elm)->field.tqe_circ.tql_prev->tql_next = (elm)->field.tqe_next; \
+ (elm)->field.tqe_circ.tql_prev = NULL; \
} while (/*CONSTCOND*/0)
#define QTAILQ_FOREACH(var, head, field) \
(var) && ((next_var) = ((var)->field.tqe_next), 1); \
(var) = (next_var))
-#define QTAILQ_FOREACH_REVERSE(var, head, headname, field) \
- for ((var) = (*(((struct headname *)((head)->tqh_last))->tqh_last)); \
+#define QTAILQ_FOREACH_REVERSE(var, head, field) \
+ for ((var) = QTAILQ_LAST(head); \
(var); \
- (var) = (*(((struct headname *)((var)->field.tqe_prev))->tqh_last)))
+ (var) = QTAILQ_PREV(var, field))
+
+#define QTAILQ_FOREACH_REVERSE_SAFE(var, head, field, prev_var) \
+ for ((var) = QTAILQ_LAST(head); \
+ (var) && ((prev_var) = QTAILQ_PREV(var, field), 1); \
+ (var) = (prev_var))
/*
* Tail queue access methods.
#define QTAILQ_EMPTY(head) ((head)->tqh_first == NULL)
#define QTAILQ_FIRST(head) ((head)->tqh_first)
#define QTAILQ_NEXT(elm, field) ((elm)->field.tqe_next)
+#define QTAILQ_IN_USE(elm, field) ((elm)->field.tqe_circ.tql_prev != NULL)
+
+#define QTAILQ_LINK_PREV(link) \
+ ((link).tql_prev->tql_prev->tql_next)
+#define QTAILQ_LAST(head) \
+ ((typeof((head)->tqh_first)) QTAILQ_LINK_PREV((head)->tqh_circ))
+#define QTAILQ_PREV(elm, field) \
+ ((typeof((elm)->field.tqe_next)) QTAILQ_LINK_PREV((elm)->field.tqe_circ))
+
+#define field_at_offset(base, offset, type) \
+ ((type *) (((char *) (base)) + (offset)))
-#define QTAILQ_LAST(head, headname) \
- (*(((struct headname *)((head)->tqh_last))->tqh_last))
-#define QTAILQ_PREV(elm, headname, field) \
- (*(((struct headname *)((elm)->field.tqe_prev))->tqh_last))
+/*
+ * Raw access of elements of a tail queue head. Offsets are all zero
+ * because it's a union.
+ */
+#define QTAILQ_RAW_FIRST(head) \
+ field_at_offset(head, 0, void *)
+#define QTAILQ_RAW_TQH_CIRC(head) \
+ field_at_offset(head, 0, QTailQLink)
+
+/*
+ * Raw access of elements of a tail entry
+ */
+#define QTAILQ_RAW_NEXT(elm, entry) \
+ field_at_offset(elm, entry, void *)
+#define QTAILQ_RAW_TQE_CIRC(elm, entry) \
+ field_at_offset(elm, entry, QTailQLink)
+/*
+ * Tail queue traversal using pointer arithmetic.
+ */
+#define QTAILQ_RAW_FOREACH(elm, head, entry) \
+ for ((elm) = *QTAILQ_RAW_FIRST(head); \
+ (elm); \
+ (elm) = *QTAILQ_RAW_NEXT(elm, entry))
+/*
+ * Tail queue insertion using pointer arithmetic.
+ */
+#define QTAILQ_RAW_INSERT_TAIL(head, elm, entry) do { \
+ *QTAILQ_RAW_NEXT(elm, entry) = NULL; \
+ QTAILQ_RAW_TQE_CIRC(elm, entry)->tql_prev = QTAILQ_RAW_TQH_CIRC(head)->tql_prev; \
+ QTAILQ_RAW_TQH_CIRC(head)->tql_prev->tql_next = (elm); \
+ QTAILQ_RAW_TQH_CIRC(head)->tql_prev = QTAILQ_RAW_TQE_CIRC(elm, entry); \
+} while (/*CONSTCOND*/0)
-#endif /* !QEMU_SYS_QUEUE_H_ */
+#endif /* QEMU_SYS_QUEUE_H */
projects / qemu.git / blobdiff