1275970Scy/* 2275970Scy * Copyright (C) 2011, 2012 Internet Systems Consortium, Inc. ("ISC") 3275970Scy * 4275970Scy * Permission to use, copy, modify, and/or distribute this software for any 5275970Scy * purpose with or without fee is hereby granted, provided that the above 6275970Scy * copyright notice and this permission notice appear in all copies. 7275970Scy * 8275970Scy * THE SOFTWARE IS PROVIDED "AS IS" AND ISC DISCLAIMS ALL WARRANTIES WITH 9275970Scy * REGARD TO THIS SOFTWARE INCLUDING ALL IMPLIED WARRANTIES OF MERCHANTABILITY 10275970Scy * AND FITNESS. IN NO EVENT SHALL ISC BE LIABLE FOR ANY SPECIAL, DIRECT, 11275970Scy * INDIRECT, OR CONSEQUENTIAL DAMAGES OR ANY DAMAGES WHATSOEVER RESULTING FROM 12275970Scy * LOSS OF USE, DATA OR PROFITS, WHETHER IN AN ACTION OF CONTRACT, NEGLIGENCE 13275970Scy * OR OTHER TORTIOUS ACTION, ARISING OUT OF OR IN CONNECTION WITH THE USE OR 14275970Scy * PERFORMANCE OF THIS SOFTWARE. 15275970Scy */ 16275970Scy 17275970Scy/* $Id$ */ 18275970Scy 19275970Scy/* 20275970Scy * This is a generic implementation of a two-lock concurrent queue. 21275970Scy * There are built-in mutex locks for the head and tail of the queue, 22275970Scy * allowing elements to be safely added and removed at the same time. 23275970Scy */ 24275970Scy 25275970Scy#ifndef ISC_QUEUE_H 26275970Scy#define ISC_QUEUE_H 1 27275970Scy#include <isc/assertions.h> 28275970Scy#include <isc/boolean.h> 29275970Scy#include <isc/mutex.h> 30275970Scy 31275970Scy#ifdef ISC_QUEUE_CHECKINIT 32275970Scy#define ISC_QLINK_INSIST(x) ISC_INSIST(x) 33275970Scy#else 34275970Scy#define ISC_QLINK_INSIST(x) (void)0 35275970Scy#endif 36275970Scy 37275970Scy#define ISC_QLINK(type) struct { void *next; isc_boolean_t linked; } 38275970Scy#define ISC_QLINK_INIT(elt, link) \ 39275970Scy do { \ 40275970Scy (elt)->link.next = (void *)(-1); \ 41275970Scy (elt)->link.linked = ISC_FALSE; \ 42275970Scy } while (0) 43275970Scy#define ISC_QLINK_LINKED(elt, link) ((elt)->link.linked) 44275970Scy 45275970Scy#define ISC_QUEUE(type) struct { \ 46275970Scy type headnode; \ 47275970Scy type *head, *tail; \ 48275970Scy isc_mutex_t headlock, taillock; \ 49275970Scy} 50275970Scy 51275970Scy#define ISC_QUEUE_INIT(queue, link) \ 52275970Scy do { \ 53275970Scy isc_mutex_init(&(queue).headlock); \ 54275970Scy isc_mutex_init(&(queue).taillock); \ 55275970Scy (queue).head = (void *) &((queue).headnode); \ 56275970Scy (queue).tail = (void *) &((queue).headnode); \ 57275970Scy ISC_QLINK_INIT((queue).head, link); \ 58275970Scy } while (0) 59275970Scy 60275970Scy#define ISC_QUEUE_EMPTY(queue) ISC_TF((queue).head == (queue).tail) 61275970Scy 62275970Scy#define ISC_QUEUE_DESTROY(queue) \ 63275970Scy do { \ 64275970Scy ISC_QLINK_INSIST(ISC_QUEUE_EMPTY(queue)); \ 65275970Scy isc_mutex_destroy(&(queue).headlock); \ 66275970Scy isc_mutex_destroy(&(queue).taillock); \ 67275970Scy } while (0) 68275970Scy 69275970Scy#define ISC_QUEUE_PUSH(queue, elt, link) \ 70275970Scy do { \ 71275970Scy ISC_QLINK_INSIST(!ISC_QLINK_LINKED(elt, link)); \ 72275970Scy (elt)->link.next = (void *)(-1); \ 73275970Scy LOCK(&(queue).taillock); \ 74275970Scy (queue).tail->link.next = elt; \ 75275970Scy (queue).tail = elt; \ 76275970Scy UNLOCK(&(queue).taillock); \ 77275970Scy (elt)->link.linked = ISC_TRUE; \ 78275970Scy } while (0) 79275970Scy 80275970Scy#define ISC_QUEUE_POP(queue, link, ret) \ 81275970Scy do { \ 82275970Scy LOCK(&(queue).headlock); \ 83275970Scy ret = (queue).head->link.next; \ 84275970Scy if (ret == (void *)(-1)) { \ 85275970Scy UNLOCK(&(queue).headlock); \ 86275970Scy ret = NULL; \ 87275970Scy } else { \ 88275970Scy (queue).head->link.next = ret->link.next; \ 89275970Scy if (ret->link.next == (void *)(-1)) { \ 90275970Scy LOCK(&(queue).taillock); \ 91275970Scy (queue).tail = (queue).head; \ 92275970Scy UNLOCK(&(queue).taillock); \ 93275970Scy } \ 94275970Scy UNLOCK(&(queue).headlock); \ 95275970Scy ret->link.next = (void *)(-1); \ 96275970Scy ret->link.linked = ISC_FALSE; \ 97275970Scy } \ 98275970Scy } while (0) 99275970Scy 100275970Scy#endif /* ISC_QUEUE_H */ 101