|
Packit Service |
75d76b |
/*
|
|
Packit Service |
75d76b |
* Copyright (c) 2020 Red Hat, Inc.
|
|
Packit Service |
75d76b |
*
|
|
Packit Service |
75d76b |
* This program is free software; you can redistribute it and/or
|
|
Packit Service |
75d76b |
* modify it under the terms of the GNU General Public License
|
|
Packit Service |
75d76b |
* as published by the Free Software Foundation; either version 2
|
|
Packit Service |
75d76b |
* of the License, or (at your option) any later version.
|
|
Packit Service |
75d76b |
*
|
|
Packit Service |
75d76b |
* This program is distributed in the hope that it will be useful,
|
|
Packit Service |
75d76b |
* but WITHOUT ANY WARRANTY; without even the implied warranty of
|
|
Packit Service |
75d76b |
* MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the
|
|
Packit Service |
75d76b |
* GNU General Public License for more details.
|
|
Packit Service |
75d76b |
*
|
|
Packit Service |
75d76b |
* You should have received a copy of the GNU General Public License
|
|
Packit Service |
75d76b |
* along with this program; if not, write to the Free Software
|
|
Packit Service |
75d76b |
* Foundation, Inc., 51 Franklin Street, Fifth Floor, Boston, MA
|
|
Packit Service |
75d76b |
* 02110-1301, USA.
|
|
Packit Service |
75d76b |
*
|
|
Packit Service |
75d76b |
* $Id: //eng/vdo-releases/aluminum/src/c++/vdo/base/waitQueue.c#1 $
|
|
Packit Service |
75d76b |
*/
|
|
Packit Service |
75d76b |
|
|
Packit Service |
75d76b |
#include "waitQueue.h"
|
|
Packit Service |
75d76b |
|
|
Packit Service |
75d76b |
#include "permassert.h"
|
|
Packit Service |
75d76b |
|
|
Packit Service |
75d76b |
#include "statusCodes.h"
|
|
Packit Service |
75d76b |
|
|
Packit Service |
75d76b |
/**********************************************************************/
|
|
Packit Service |
75d76b |
int enqueueWaiter(WaitQueue *queue, Waiter *waiter)
|
|
Packit Service |
75d76b |
{
|
|
Packit Service |
75d76b |
int result = ASSERT((waiter->nextWaiter == NULL),
|
|
Packit Service |
75d76b |
"new waiter must not already be in a waiter queue");
|
|
Packit Service |
75d76b |
if (result != VDO_SUCCESS) {
|
|
Packit Service |
75d76b |
return result;
|
|
Packit Service |
75d76b |
}
|
|
Packit Service |
75d76b |
|
|
Packit Service |
75d76b |
if (queue->lastWaiter == NULL) {
|
|
Packit Service |
75d76b |
// The queue is empty, so form the initial circular list by self-linking
|
|
Packit Service |
75d76b |
// the initial waiter.
|
|
Packit Service |
75d76b |
waiter->nextWaiter = waiter;
|
|
Packit Service |
75d76b |
} else {
|
|
Packit Service |
75d76b |
// Splice the new waiter in at the end of the queue.
|
|
Packit Service |
75d76b |
waiter->nextWaiter = queue->lastWaiter->nextWaiter;
|
|
Packit Service |
75d76b |
queue->lastWaiter->nextWaiter = waiter;
|
|
Packit Service |
75d76b |
}
|
|
Packit Service |
75d76b |
// In both cases, the waiter we added to the ring becomes the last waiter.
|
|
Packit Service |
75d76b |
queue->lastWaiter = waiter;
|
|
Packit Service |
75d76b |
queue->queueLength += 1;
|
|
Packit Service |
75d76b |
return VDO_SUCCESS;
|
|
Packit Service |
75d76b |
}
|
|
Packit Service |
75d76b |
|
|
Packit Service |
75d76b |
/**********************************************************************/
|
|
Packit Service |
75d76b |
void transferAllWaiters(WaitQueue *fromQueue, WaitQueue *toQueue)
|
|
Packit Service |
75d76b |
{
|
|
Packit Service |
75d76b |
// If the source queue is empty, there's nothing to do.
|
|
Packit Service |
75d76b |
if (!hasWaiters(fromQueue)) {
|
|
Packit Service |
75d76b |
return;
|
|
Packit Service |
75d76b |
}
|
|
Packit Service |
75d76b |
|
|
Packit Service |
75d76b |
if (hasWaiters(toQueue)) {
|
|
Packit Service |
75d76b |
// Both queues are non-empty. Splice the two circular lists together by
|
|
Packit Service |
75d76b |
// swapping the next (head) pointers in the list tails.
|
|
Packit Service |
75d76b |
Waiter *fromHead = fromQueue->lastWaiter->nextWaiter;
|
|
Packit Service |
75d76b |
Waiter *toHead = toQueue->lastWaiter->nextWaiter;
|
|
Packit Service |
75d76b |
toQueue->lastWaiter->nextWaiter = fromHead;
|
|
Packit Service |
75d76b |
fromQueue->lastWaiter->nextWaiter = toHead;
|
|
Packit Service |
75d76b |
}
|
|
Packit Service |
75d76b |
|
|
Packit Service |
75d76b |
toQueue->lastWaiter = fromQueue->lastWaiter;
|
|
Packit Service |
75d76b |
toQueue->queueLength += fromQueue->queueLength;
|
|
Packit Service |
75d76b |
initializeWaitQueue(fromQueue);
|
|
Packit Service |
75d76b |
}
|
|
Packit Service |
75d76b |
|
|
Packit Service |
75d76b |
/**********************************************************************/
|
|
Packit Service |
75d76b |
void notifyAllWaiters(WaitQueue *queue,
|
|
Packit Service |
75d76b |
WaiterCallback *callback,
|
|
Packit Service |
75d76b |
void *context)
|
|
Packit Service |
75d76b |
{
|
|
Packit Service |
75d76b |
// Copy and empty the queue first, avoiding the possibility of an infinite
|
|
Packit Service |
75d76b |
// loop if entries are returned to the queue by the callback function.
|
|
Packit Service |
75d76b |
WaitQueue waiters;
|
|
Packit Service |
75d76b |
initializeWaitQueue(&waiters);
|
|
Packit Service |
75d76b |
transferAllWaiters(queue, &waiters);
|
|
Packit Service |
75d76b |
|
|
Packit Service |
75d76b |
// Drain the copied queue, invoking the callback on every entry.
|
|
Packit Service |
75d76b |
while (notifyNextWaiter(&waiters, callback, context)) {
|
|
Packit Service |
75d76b |
// All the work is done by the loop condition.
|
|
Packit Service |
75d76b |
}
|
|
Packit Service |
75d76b |
}
|
|
Packit Service |
75d76b |
|
|
Packit Service |
75d76b |
/**********************************************************************/
|
|
Packit Service |
75d76b |
Waiter *getFirstWaiter(const WaitQueue *queue)
|
|
Packit Service |
75d76b |
{
|
|
Packit Service |
75d76b |
Waiter *lastWaiter = queue->lastWaiter;
|
|
Packit Service |
75d76b |
if (lastWaiter == NULL) {
|
|
Packit Service |
75d76b |
// There are no waiters, so we're done.
|
|
Packit Service |
75d76b |
return NULL;
|
|
Packit Service |
75d76b |
}
|
|
Packit Service |
75d76b |
|
|
Packit Service |
75d76b |
// The queue is circular, so the last entry links to the head of the queue.
|
|
Packit Service |
75d76b |
return lastWaiter->nextWaiter;
|
|
Packit Service |
75d76b |
}
|
|
Packit Service |
75d76b |
|
|
Packit Service |
75d76b |
/**********************************************************************/
|
|
Packit Service |
75d76b |
int dequeueMatchingWaiters(WaitQueue *queue,
|
|
Packit Service |
75d76b |
WaiterMatch *matchMethod,
|
|
Packit Service |
75d76b |
void *matchContext,
|
|
Packit Service |
75d76b |
WaitQueue *matchedQueue)
|
|
Packit Service |
75d76b |
{
|
|
Packit Service |
75d76b |
WaitQueue matchedWaiters;
|
|
Packit Service |
75d76b |
initializeWaitQueue(&matchedWaiters);
|
|
Packit Service |
75d76b |
|
|
Packit Service |
75d76b |
WaitQueue iterationQueue;
|
|
Packit Service |
75d76b |
initializeWaitQueue(&iterationQueue);
|
|
Packit Service |
75d76b |
transferAllWaiters(queue, &iterationQueue);
|
|
Packit Service |
75d76b |
while (hasWaiters(&iterationQueue)) {
|
|
Packit Service |
75d76b |
Waiter *waiter = dequeueNextWaiter(&iterationQueue);
|
|
Packit Service |
75d76b |
int result = VDO_SUCCESS;
|
|
Packit Service |
75d76b |
if (!matchMethod(waiter, matchContext)) {
|
|
Packit Service |
75d76b |
result = enqueueWaiter(queue, waiter);
|
|
Packit Service |
75d76b |
} else {
|
|
Packit Service |
75d76b |
result = enqueueWaiter(&matchedWaiters, waiter);
|
|
Packit Service |
75d76b |
}
|
|
Packit Service |
75d76b |
if (result != VDO_SUCCESS) {
|
|
Packit Service |
75d76b |
transferAllWaiters(&matchedWaiters, queue);
|
|
Packit Service |
75d76b |
transferAllWaiters(&iterationQueue, queue);
|
|
Packit Service |
75d76b |
return result;
|
|
Packit Service |
75d76b |
}
|
|
Packit Service |
75d76b |
}
|
|
Packit Service |
75d76b |
|
|
Packit Service |
75d76b |
transferAllWaiters(&matchedWaiters, matchedQueue);
|
|
Packit Service |
75d76b |
return VDO_SUCCESS;
|
|
Packit Service |
75d76b |
}
|
|
Packit Service |
75d76b |
|
|
Packit Service |
75d76b |
/**********************************************************************/
|
|
Packit Service |
75d76b |
Waiter *dequeueNextWaiter(WaitQueue *queue)
|
|
Packit Service |
75d76b |
{
|
|
Packit Service |
75d76b |
Waiter *firstWaiter = getFirstWaiter(queue);
|
|
Packit Service |
75d76b |
if (firstWaiter == NULL) {
|
|
Packit Service |
75d76b |
return NULL;
|
|
Packit Service |
75d76b |
}
|
|
Packit Service |
75d76b |
|
|
Packit Service |
75d76b |
Waiter *lastWaiter = queue->lastWaiter;
|
|
Packit Service |
75d76b |
if (firstWaiter == lastWaiter) {
|
|
Packit Service |
75d76b |
// The queue has a single entry, so just empty it out by nulling the tail.
|
|
Packit Service |
75d76b |
queue->lastWaiter = NULL;
|
|
Packit Service |
75d76b |
} else {
|
|
Packit Service |
75d76b |
// The queue has more than one entry, so splice the first waiter out of
|
|
Packit Service |
75d76b |
// the circular queue.
|
|
Packit Service |
75d76b |
lastWaiter->nextWaiter = firstWaiter->nextWaiter;
|
|
Packit Service |
75d76b |
}
|
|
Packit Service |
75d76b |
|
|
Packit Service |
75d76b |
// The waiter is no longer in a wait queue.
|
|
Packit Service |
75d76b |
firstWaiter->nextWaiter = NULL;
|
|
Packit Service |
75d76b |
queue->queueLength -= 1;
|
|
Packit Service |
75d76b |
return firstWaiter;
|
|
Packit Service |
75d76b |
}
|
|
Packit Service |
75d76b |
|
|
Packit Service |
75d76b |
/**********************************************************************/
|
|
Packit Service |
75d76b |
bool notifyNextWaiter(WaitQueue *queue,
|
|
Packit Service |
75d76b |
WaiterCallback *callback,
|
|
Packit Service |
75d76b |
void *context)
|
|
Packit Service |
75d76b |
{
|
|
Packit Service |
75d76b |
Waiter *waiter = dequeueNextWaiter(queue);
|
|
Packit Service |
75d76b |
if (waiter == NULL) {
|
|
Packit Service |
75d76b |
return false;
|
|
Packit Service |
75d76b |
}
|
|
Packit Service |
75d76b |
|
|
Packit Service |
75d76b |
if (callback == NULL) {
|
|
Packit Service |
75d76b |
callback = waiter->callback;
|
|
Packit Service |
75d76b |
}
|
|
Packit Service |
75d76b |
(*callback)(waiter, context);
|
|
Packit Service |
75d76b |
return true;
|
|
Packit Service |
75d76b |
}
|
|
Packit Service |
75d76b |
|
|
Packit Service |
75d76b |
/**********************************************************************/
|
|
Packit Service |
75d76b |
const Waiter *getNextWaiter(const WaitQueue *queue, const Waiter *waiter)
|
|
Packit Service |
75d76b |
{
|
|
Packit Service |
75d76b |
Waiter *firstWaiter = getFirstWaiter(queue);
|
|
Packit Service |
75d76b |
if (waiter == NULL) {
|
|
Packit Service |
75d76b |
return firstWaiter;
|
|
Packit Service |
75d76b |
}
|
|
Packit Service |
75d76b |
return ((waiter->nextWaiter != firstWaiter) ? waiter->nextWaiter : NULL);
|
|
Packit Service |
75d76b |
}
|