contrib/ntp/lib/isc/include/isc/queue.h

   1 /*
   2  * Copyright (C) 2011, 2012  Internet Systems Consortium, Inc. ("ISC")
   3  *
   4  * Permission to use, copy, modify, and/or distribute this software for any
   5  * purpose with or without fee is hereby granted, provided that the above
   6  * copyright notice and this permission notice appear in all copies.
   7  *
   8  * THE SOFTWARE IS PROVIDED "AS IS" AND ISC DISCLAIMS ALL WARRANTIES WITH
   9  * REGARD TO THIS SOFTWARE INCLUDING ALL IMPLIED WARRANTIES OF MERCHANTABILITY
  10  * AND FITNESS.  IN NO EVENT SHALL ISC BE LIABLE FOR ANY SPECIAL, DIRECT,
  11  * INDIRECT, OR CONSEQUENTIAL DAMAGES OR ANY DAMAGES WHATSOEVER RESULTING FROM
  12  * LOSS OF USE, DATA OR PROFITS, WHETHER IN AN ACTION OF CONTRACT, NEGLIGENCE
  13  * OR OTHER TORTIOUS ACTION, ARISING OUT OF OR IN CONNECTION WITH THE USE OR
  14  * PERFORMANCE OF THIS SOFTWARE.
  15  */
  16
  17 /* $Id$ */
  18
  19 /*
  20  * This is a generic implementation of a two-lock concurrent queue.
  21  * There are built-in mutex locks for the head and tail of the queue,
  22  * allowing elements to be safely added and removed at the same time.
  23  */
  24
  25 #ifndef ISC_QUEUE_H
  26 #define ISC_QUEUE_H 1
  27 #include <isc/assertions.h>
  28 #include <isc/boolean.h>
  29 #include <isc/mutex.h>
  30
  31 #ifdef ISC_QUEUE_CHECKINIT
  32 #define ISC_QLINK_INSIST(x) ISC_INSIST(x)
  33 #else
  34 #define ISC_QLINK_INSIST(x) (void)0
  35 #endif
  36
  37 #define ISC_QLINK(type) struct { void *next; isc_boolean_t linked; }
  38 #define ISC_QLINK_INIT(elt, link) \
  39         do { \
  40                 (elt)->link.next = (void *)(-1); \
  41                 (elt)->link.linked = ISC_FALSE; \
  42         } while (0)
  43 #define ISC_QLINK_LINKED(elt, link) ((elt)->link.linked)
  44
  45 #define ISC_QUEUE(type) struct { \
  46         type headnode; \
  47         type *head, *tail; \
  48         isc_mutex_t headlock, taillock; \
  49 }
  50
  51 #define ISC_QUEUE_INIT(queue, link) \
  52         do { \
  53                 isc_mutex_init(&(queue).headlock); \
  54                 isc_mutex_init(&(queue).taillock); \
  55                 (queue).head = (void *) &((queue).headnode); \
  56                 (queue).tail = (void *) &((queue).headnode); \
  57                 ISC_QLINK_INIT((queue).head, link); \
  58         } while (0)
  59
  60 #define ISC_QUEUE_EMPTY(queue) ISC_TF((queue).head == (queue).tail)
  61
  62 #define ISC_QUEUE_DESTROY(queue) \
  63         do { \
  64                 ISC_QLINK_INSIST(ISC_QUEUE_EMPTY(queue)); \
  65                 isc_mutex_destroy(&(queue).headlock); \
  66                 isc_mutex_destroy(&(queue).taillock); \
  67         } while (0)
  68
  69 #define ISC_QUEUE_PUSH(queue, elt, link) \
  70         do { \
  71                 ISC_QLINK_INSIST(!ISC_QLINK_LINKED(elt, link)); \
  72                 (elt)->link.next = (void *)(-1); \
  73                 LOCK(&(queue).taillock); \
  74                 (queue).tail->link.next = elt; \
  75                 (queue).tail = elt; \
  76                 UNLOCK(&(queue).taillock); \
  77                 (elt)->link.linked = ISC_TRUE; \
  78         } while (0)
  79
  80 #define ISC_QUEUE_POP(queue, link, ret) \
  81         do { \
  82                 LOCK(&(queue).headlock); \
  83                 ret = (queue).head->link.next; \
  84                 if (ret == (void *)(-1)) { \
  85                         UNLOCK(&(queue).headlock); \
  86                         ret = NULL; \
  87                 } else { \
  88                         (queue).head->link.next = ret->link.next; \
  89                         if (ret->link.next == (void *)(-1)) { \
  90                                 LOCK(&(queue).taillock); \
  91                                 (queue).tail = (queue).head; \
  92                                 UNLOCK(&(queue).taillock); \
  93                         } \
  94                         UNLOCK(&(queue).headlock); \
  95                         ret->link.next = (void *)(-1); \
  96                         ret->link.linked = ISC_FALSE; \
  97                 } \
  98         } while (0)
  99
 100 #endif /* ISC_QUEUE_H */