diff options
Diffstat (limited to 'src/third_party/wiredtiger/src/include/queue.h')
| -rw-r--r-- | src/third_party/wiredtiger/src/include/queue.h | 174 |
1 files changed, 114 insertions, 60 deletions
diff --git a/src/third_party/wiredtiger/src/include/queue.h b/src/third_party/wiredtiger/src/include/queue.h index 1d494875cf6..e3d4daf0f4c 100644 --- a/src/third_party/wiredtiger/src/include/queue.h +++ b/src/third_party/wiredtiger/src/include/queue.h @@ -1,4 +1,4 @@ -/* +/*- * Copyright (c) 1991, 1993 * The Regents of the University of California. All rights reserved. * @@ -27,28 +27,18 @@ * SUCH DAMAGE. * * @(#)queue.h 8.5 (Berkeley) 8/20/94 - * $FreeBSD: src/sys/sys/queue.h,v 1.54 2002/08/05 05:18:43 alfred Exp $ + * $FreeBSD$ */ -#ifndef _DB_QUEUE_H_ -#define _DB_QUEUE_H_ - -#if defined(__cplusplus) -extern "C" { -#endif - /* + * This is a stripped-down version of the FreeBSD sys/queue.h include file. + * * WiredTiger only uses the TAILQ macros (we've gotten into trouble in the past * by trying to use simpler queues and subsequently discovering a list we didn't * think would ever get to be large could, under some workloads, become large, * and the linear performance for removal of elements from simpler macros proved * to be more trouble than the memory savings were worth. * - * Additionally, we've altered the TAILQ_INSERT_XXX functions to include a write - * barrier, in order to ensure we never insert a partially built structure onto - * a list (this is required because the spinlocks we use don't necessarily imply - * a write barrier). - * * We #undef all of the macros because there are incompatible versions of this * file and these macros on various systems. What makes the problem worse is * they are included and/or defined by system include files which we may have @@ -57,13 +47,28 @@ extern "C" { * several of the LIST_XXX macros. Visual C.NET 7.0 also defines some of these * same macros in Vc7\PlatformSDK\Include\WinNT.h. Make sure we use ours. */ - +#undef QMD_SAVELINK +#undef QMD_TAILQ_CHECK_HEAD +#undef QMD_TAILQ_CHECK_NEXT +#undef QMD_TAILQ_CHECK_PREV +#undef QMD_TAILQ_CHECK_TAIL +#undef QMD_TRACE_ELEM +#undef QMD_TRACE_HEAD +#undef QUEUE_TYPEOF +#undef TAILQ_CLASS_ENTRY +#undef TAILQ_CLASS_HEAD #undef TAILQ_CONCAT #undef TAILQ_EMPTY #undef TAILQ_ENTRY #undef TAILQ_FIRST #undef TAILQ_FOREACH +#undef TAILQ_FOREACH_FROM +#undef TAILQ_FOREACH_FROM_SAFE #undef TAILQ_FOREACH_REVERSE +#undef TAILQ_FOREACH_REVERSE_FROM +#undef TAILQ_FOREACH_REVERSE_FROM_SAFE +#undef TAILQ_FOREACH_REVERSE_SAFE +#undef TAILQ_FOREACH_SAFE #undef TAILQ_HEAD #undef TAILQ_HEAD_INITIALIZER #undef TAILQ_INIT @@ -76,41 +81,25 @@ extern "C" { #undef TAILQ_PREV #undef TAILQ_REMOVE #undef TRACEBUF +#undef TRACEBUF_INITIALIZER #undef TRASHIT +#undef TAILQ_SWAP -#define QUEUE_MACRO_DEBUG 0 -#if QUEUE_MACRO_DEBUG -/* Store the last 2 places the queue element or head was altered */ -struct qm_trace { - char * lastfile; - int lastline; - char * prevfile; - int prevline; -}; - -#define TRACEBUF struct qm_trace trace; -#define TRASHIT(x) do {(x) = (void *)-1;} while (0) - -#define QMD_TRACE_HEAD(head) do { \ - (head)->trace.prevline = (head)->trace.lastline; \ - (head)->trace.prevfile = (head)->trace.lastfile; \ - (head)->trace.lastline = __LINE__; \ - (head)->trace.lastfile = __FILE__; \ -} while (0) - -#define QMD_TRACE_ELEM(elem) do { \ - (elem)->trace.prevline = (elem)->trace.lastline; \ - (elem)->trace.prevfile = (elem)->trace.lastfile; \ - (elem)->trace.lastline = __LINE__; \ - (elem)->trace.lastfile = __FILE__; \ -} while (0) - -#else #define QMD_TRACE_ELEM(elem) #define QMD_TRACE_HEAD(head) +#define QMD_SAVELINK(name, link) #define TRACEBUF +#define TRACEBUF_INITIALIZER #define TRASHIT(x) -#endif /* QUEUE_MACRO_DEBUG */ + +#ifdef __cplusplus +/* + * In C++ there can be structure lists and class lists: + */ +#define QUEUE_TYPEOF(type) type +#else +#define QUEUE_TYPEOF(type) struct type +#endif /* * Tail queue declarations. @@ -122,8 +111,15 @@ struct name { \ TRACEBUF \ } +#define TAILQ_CLASS_HEAD(name, type) \ +struct name { \ + class type *tqh_first; /* first element */ \ + class type **tqh_last; /* addr of last next element */ \ + TRACEBUF \ +} + #define TAILQ_HEAD_INITIALIZER(head) \ - { NULL, &(head).tqh_first } + { NULL, &(head).tqh_first, TRACEBUF_INITIALIZER } #define TAILQ_ENTRY(type) \ struct { \ @@ -132,16 +128,28 @@ struct { \ TRACEBUF \ } +#define TAILQ_CLASS_ENTRY(type) \ +struct { \ + class type *tqe_next; /* next element */ \ + class type **tqe_prev; /* address of previous next element */ \ + TRACEBUF \ +} + /* * Tail queue functions. */ +#define QMD_TAILQ_CHECK_HEAD(head, field) +#define QMD_TAILQ_CHECK_TAIL(head, headname) +#define QMD_TAILQ_CHECK_NEXT(elm, field) +#define QMD_TAILQ_CHECK_PREV(elm, field) + #define TAILQ_CONCAT(head1, head2, field) do { \ if (!TAILQ_EMPTY(head2)) { \ *(head1)->tqh_last = (head2)->tqh_first; \ (head2)->tqh_first->field.tqe_prev = (head1)->tqh_last; \ (head1)->tqh_last = (head2)->tqh_last; \ TAILQ_INIT((head2)); \ - QMD_TRACE_HEAD(head); \ + QMD_TRACE_HEAD(head1); \ QMD_TRACE_HEAD(head2); \ } \ } while (0) @@ -155,11 +163,41 @@ struct { \ (var); \ (var) = TAILQ_NEXT((var), field)) +#define TAILQ_FOREACH_FROM(var, head, field) \ + for ((var) = ((var) ? (var) : TAILQ_FIRST((head))); \ + (var); \ + (var) = TAILQ_NEXT((var), field)) + +#define TAILQ_FOREACH_SAFE(var, head, field, tvar) \ + for ((var) = TAILQ_FIRST((head)); \ + (var) && ((tvar) = TAILQ_NEXT((var), field), 1); \ + (var) = (tvar)) + +#define TAILQ_FOREACH_FROM_SAFE(var, head, field, tvar) \ + for ((var) = ((var) ? (var) : TAILQ_FIRST((head))); \ + (var) && ((tvar) = TAILQ_NEXT((var), field), 1); \ + (var) = (tvar)) + #define TAILQ_FOREACH_REVERSE(var, head, headname, field) \ for ((var) = TAILQ_LAST((head), headname); \ (var); \ (var) = TAILQ_PREV((var), headname, field)) +#define TAILQ_FOREACH_REVERSE_FROM(var, head, headname, field) \ + for ((var) = ((var) ? (var) : TAILQ_LAST((head), headname)); \ + (var); \ + (var) = TAILQ_PREV((var), headname, field)) + +#define TAILQ_FOREACH_REVERSE_SAFE(var, head, headname, field, tvar) \ + for ((var) = TAILQ_LAST((head), headname); \ + (var) && ((tvar) = TAILQ_PREV((var), headname, field), 1); \ + (var) = (tvar)) + +#define TAILQ_FOREACH_REVERSE_FROM_SAFE(var, head, headname, field, tvar) \ + for ((var) = ((var) ? (var) : TAILQ_LAST((head), headname)); \ + (var) && ((tvar) = TAILQ_PREV((var), headname, field), 1); \ + (var) = (tvar)) + #define TAILQ_INIT(head) do { \ TAILQ_FIRST((head)) = NULL; \ (head)->tqh_last = &TAILQ_FIRST((head)); \ @@ -167,9 +205,9 @@ struct { \ } while (0) #define TAILQ_INSERT_AFTER(head, listelm, elm, field) do { \ - WT_WRITE_BARRIER(); \ + QMD_TAILQ_CHECK_NEXT(listelm, field); \ if ((TAILQ_NEXT((elm), field) = TAILQ_NEXT((listelm), field)) != NULL)\ - TAILQ_NEXT((elm), field)->field.tqe_prev = \ + TAILQ_NEXT((elm), field)->field.tqe_prev = \ &TAILQ_NEXT((elm), field); \ else { \ (head)->tqh_last = &TAILQ_NEXT((elm), field); \ @@ -178,21 +216,21 @@ struct { \ TAILQ_NEXT((listelm), field) = (elm); \ (elm)->field.tqe_prev = &TAILQ_NEXT((listelm), field); \ QMD_TRACE_ELEM(&(elm)->field); \ - QMD_TRACE_ELEM(&listelm->field); \ + QMD_TRACE_ELEM(&(listelm)->field); \ } while (0) #define TAILQ_INSERT_BEFORE(listelm, elm, field) do { \ - WT_WRITE_BARRIER(); \ + QMD_TAILQ_CHECK_PREV(listelm, field); \ (elm)->field.tqe_prev = (listelm)->field.tqe_prev; \ TAILQ_NEXT((elm), field) = (listelm); \ *(listelm)->field.tqe_prev = (elm); \ (listelm)->field.tqe_prev = &TAILQ_NEXT((elm), field); \ QMD_TRACE_ELEM(&(elm)->field); \ - QMD_TRACE_ELEM(&listelm->field); \ + QMD_TRACE_ELEM(&(listelm)->field); \ } while (0) #define TAILQ_INSERT_HEAD(head, elm, field) do { \ - WT_WRITE_BARRIER(); \ + QMD_TAILQ_CHECK_HEAD(head, field); \ if ((TAILQ_NEXT((elm), field) = TAILQ_FIRST((head))) != NULL) \ TAILQ_FIRST((head))->field.tqe_prev = \ &TAILQ_NEXT((elm), field); \ @@ -205,7 +243,7 @@ struct { \ } while (0) #define TAILQ_INSERT_TAIL(head, elm, field) do { \ - WT_WRITE_BARRIER(); \ + QMD_TAILQ_CHECK_TAIL(head, field); \ TAILQ_NEXT((elm), field) = NULL; \ (elm)->field.tqe_prev = (head)->tqh_last; \ *(head)->tqh_last = (elm); \ @@ -223,20 +261,36 @@ struct { \ (*(((struct headname *)((elm)->field.tqe_prev))->tqh_last)) #define TAILQ_REMOVE(head, elm, field) do { \ + QMD_SAVELINK(oldnext, (elm)->field.tqe_next); \ + QMD_SAVELINK(oldprev, (elm)->field.tqe_prev); \ + QMD_TAILQ_CHECK_NEXT(elm, field); \ + QMD_TAILQ_CHECK_PREV(elm, field); \ if ((TAILQ_NEXT((elm), field)) != NULL) \ - TAILQ_NEXT((elm), field)->field.tqe_prev = \ + TAILQ_NEXT((elm), field)->field.tqe_prev = \ (elm)->field.tqe_prev; \ else { \ (head)->tqh_last = (elm)->field.tqe_prev; \ QMD_TRACE_HEAD(head); \ } \ *(elm)->field.tqe_prev = TAILQ_NEXT((elm), field); \ - TRASHIT((elm)->field.tqe_next); \ - TRASHIT((elm)->field.tqe_prev); \ + TRASHIT(*oldnext); \ + TRASHIT(*oldprev); \ QMD_TRACE_ELEM(&(elm)->field); \ } while (0) -#if defined(__cplusplus) -} -#endif -#endif /* !_DB_QUEUE_H_ */ +#define TAILQ_SWAP(head1, head2, type, field) do { \ + QUEUE_TYPEOF(type) *swap_first = (head1)->tqh_first; \ + QUEUE_TYPEOF(type) **swap_last = (head1)->tqh_last; \ + (head1)->tqh_first = (head2)->tqh_first; \ + (head1)->tqh_last = (head2)->tqh_last; \ + (head2)->tqh_first = swap_first; \ + (head2)->tqh_last = swap_last; \ + if ((swap_first = (head1)->tqh_first) != NULL) \ + swap_first->field.tqe_prev = &(head1)->tqh_first; \ + else \ + (head1)->tqh_last = &(head1)->tqh_first; \ + if ((swap_first = (head2)->tqh_first) != NULL) \ + swap_first->field.tqe_prev = &(head2)->tqh_first; \ + else \ + (head2)->tqh_last = &(head2)->tqh_first; \ +} while (0) |