/usr/include/isc/queue.h is in libbind-dev 1:9.11.3+dfsg-1ubuntu1.
This file is owned by root:root, with mode 0o644.
The actual contents of the file can be viewed below.
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 81 82 83 84 85 86 87 88 89 90 91 92 93 94 95 96 97 98 99 100 101 102 103 104 105 106 107 108 109 110 111 112 113 114 115 116 117 118 119 120 121 122 123 124 125 126 127 128 129 130 131 132 133 134 135 136 137 138 139 140 141 142 143 144 145 146 147 148 149 150 151 152 153 154 155 156 157 | /*
* Copyright (C) 2011-2013, 2016 Internet Systems Consortium, Inc. ("ISC")
*
* This Source Code Form is subject to the terms of the Mozilla Public
* License, v. 2.0. If a copy of the MPL was not distributed with this
* file, You can obtain one at http://mozilla.org/MPL/2.0/.
*/
/* $Id$ */
/*
* This is a generic implementation of a two-lock concurrent queue.
* There are built-in mutex locks for the head and tail of the queue,
* allowing elements to be safely added and removed at the same time.
*
* NULL is "end of list"
* -1 is "not linked"
*/
#ifndef ISC_QUEUE_H
#define ISC_QUEUE_H 1
#include <isc/assertions.h>
#include <isc/boolean.h>
#include <isc/mutex.h>
#ifdef ISC_QUEUE_CHECKINIT
#define ISC_QLINK_INSIST(x) ISC_INSIST(x)
#else
#define ISC_QLINK_INSIST(x) (void)0
#endif
#define ISC_QLINK(type) struct { type *prev, *next; }
#define ISC_QLINK_INIT(elt, link) \
do { \
(elt)->link.next = (elt)->link.prev = (void *)(-1); \
} while(0)
#define ISC_QLINK_LINKED(elt, link) ((void*)(elt)->link.next != (void*)(-1))
#define ISC_QUEUE(type) struct { \
type *head, *tail; \
isc_mutex_t headlock, taillock; \
}
#define ISC_QUEUE_INIT(queue, link) \
do { \
(void) isc_mutex_init(&(queue).taillock); \
(void) isc_mutex_init(&(queue).headlock); \
(queue).tail = (queue).head = NULL; \
} while (0)
#define ISC_QUEUE_EMPTY(queue) ISC_TF((queue).head == NULL)
#define ISC_QUEUE_DESTROY(queue) \
do { \
ISC_QLINK_INSIST(ISC_QUEUE_EMPTY(queue)); \
(void) isc_mutex_destroy(&(queue).taillock); \
(void) isc_mutex_destroy(&(queue).headlock); \
} while (0)
/*
* queues are meant to separate the locks at either end. For best effect, that
* means keeping the ends separate - i.e. non-empty queues work best.
*
* a push to an empty queue has to take the pop lock to update
* the pop side of the queue.
* Popping the last entry has to take the push lock to update
* the push side of the queue.
*
* The order is (pop, push), because a pop is presumably in the
* latency path and a push is when we're done.
*
* We do an MT hot test in push to see if we need both locks, so we can
* acquire them in order. Hopefully that makes the case where we get
* the push lock and find we need the pop lock (and have to release it) rare.
*
* > 1 entry - no collision, push works on one end, pop on the other
* 0 entry - headlock race
* pop wins - return(NULL), push adds new as both head/tail
* push wins - updates head/tail, becomes 1 entry case.
* 1 entry - taillock race
* pop wins - return(pop) sets head/tail NULL, becomes 0 entry case
* push wins - updates {head,tail}->link.next, pop updates head
* with new ->link.next and doesn't update tail
*
*/
#define ISC_QUEUE_PUSH(queue, elt, link) \
do { \
isc_boolean_t headlocked = ISC_FALSE; \
ISC_QLINK_INSIST(!ISC_QLINK_LINKED(elt, link)); \
if ((queue).head == NULL) { \
LOCK(&(queue).headlock); \
headlocked = ISC_TRUE; \
} \
LOCK(&(queue).taillock); \
if ((queue).tail == NULL && !headlocked) { \
UNLOCK(&(queue).taillock); \
LOCK(&(queue).headlock); \
LOCK(&(queue).taillock); \
headlocked = ISC_TRUE; \
} \
(elt)->link.prev = (queue).tail; \
(elt)->link.next = NULL; \
if ((queue).tail != NULL) \
(queue).tail->link.next = (elt); \
(queue).tail = (elt); \
UNLOCK(&(queue).taillock); \
if (headlocked) { \
if ((queue).head == NULL) \
(queue).head = (elt); \
UNLOCK(&(queue).headlock); \
} \
} while (0)
#define ISC_QUEUE_POP(queue, link, ret) \
do { \
LOCK(&(queue).headlock); \
ret = (queue).head; \
while (ret != NULL) { \
if (ret->link.next == NULL) { \
LOCK(&(queue).taillock); \
if (ret->link.next == NULL) { \
(queue).head = (queue).tail = NULL; \
UNLOCK(&(queue).taillock); \
break; \
}\
UNLOCK(&(queue).taillock); \
} \
(queue).head = ret->link.next; \
(queue).head->link.prev = NULL; \
break; \
} \
UNLOCK(&(queue).headlock); \
if (ret != NULL) \
(ret)->link.next = (ret)->link.prev = (void *)(-1); \
} while(0)
#define ISC_QUEUE_UNLINK(queue, elt, link) \
do { \
ISC_QLINK_INSIST(ISC_QLINK_LINKED(elt, link)); \
LOCK(&(queue).headlock); \
LOCK(&(queue).taillock); \
if ((elt)->link.prev == NULL) \
(queue).head = (elt)->link.next; \
else \
(elt)->link.prev->link.next = (elt)->link.next; \
if ((elt)->link.next == NULL) \
(queue).tail = (elt)->link.prev; \
else \
(elt)->link.next->link.prev = (elt)->link.prev; \
UNLOCK(&(queue).taillock); \
UNLOCK(&(queue).headlock); \
(elt)->link.next = (elt)->link.prev = (void *)(-1); \
} while(0)
#endif /* ISC_QUEUE_H */
|