/*
* Copyright (c) 2020 Red Hat, Inc.
*
* This program is free software; you can redistribute it and/or
* modify it under the terms of the GNU General Public License
* as published by the Free Software Foundation; either version 2
* of the License, or (at your option) any later version.
*
* This program is distributed in the hope that it will be useful,
* but WITHOUT ANY WARRANTY; without even the implied warranty of
* MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the
* GNU General Public License for more details.
*
* You should have received a copy of the GNU General Public License
* along with this program; if not, write to the Free Software
* Foundation, Inc., 51 Franklin Street, Fifth Floor, Boston, MA
* 02110-1301, USA.
*
* $Id: //eng/vdo-releases/aluminum/src/c++/vdo/base/waitQueue.h#1 $
*/
#ifndef WAIT_QUEUE_H
#define WAIT_QUEUE_H
#include "common.h"
/**
* A wait queue is a circular list of entries waiting to be notified of a
* change in a condition. Keeping a circular list allows the queue structure
* to simply be a pointer to the tail (newest) entry in the queue, supporting
* constant-time enqueue and dequeue operations. A null pointer is an empty
* queue.
*
* An empty queue:
* queue0.lastWaiter -> NULL
*
* A singleton queue:
* queue1.lastWaiter -> entry1 -> entry1 -> [...]
*
* A three-element queue:
* queue2.lastWaiter -> entry3 -> entry1 -> entry2 -> entry3 -> [...]
**/
typedef struct waiter Waiter;
typedef struct {
/** The tail of the queue, the last (most recently added) entry */
Waiter *lastWaiter;
/** The number of waiters currently in the queue */
size_t queueLength;
} WaitQueue;
/**
* Callback type for functions which will be called to resume processing of a
* waiter after it has been removed from its wait queue.
**/
typedef void WaiterCallback(Waiter *waiter, void *context);
/**
* Method type for Waiter matching methods.
*
* A WaiterMatch method returns false if the waiter does not match.
**/
typedef bool WaiterMatch(Waiter *waiter, void *context);
/**
* The queue entry structure for entries in a WaitQueue.
**/
struct waiter {
/**
* The next waiter in the queue. If this entry is the last waiter, then this
* is actually a pointer back to the head of the queue.
**/
struct waiter *nextWaiter;
/** Optional waiter-specific callback to invoke when waking this waiter. */
WaiterCallback *callback;
};
/**
* Check whether a Waiter is waiting.
*
* @param waiter The waiter to check
*
* @return true
if the waiter is on some WaitQueue
**/
static inline bool isWaiting(Waiter *waiter)
{
return (waiter->nextWaiter != NULL);
}
/**
* Initialize a wait queue.
*
* @param queue The queue to initialize
**/
static inline void initializeWaitQueue(WaitQueue *queue)
{
*queue = (WaitQueue) {
.lastWaiter = NULL,
.queueLength = 0,
};
}
/**
* Check whether a wait queue has any entries waiting in it.
*
* @param queue The queue to query
*
* @return true
if there are any waiters in the queue
**/
__attribute__((warn_unused_result))
static inline bool hasWaiters(const WaitQueue *queue)
{
return (queue->lastWaiter != NULL);
}
/**
* Add a waiter to the tail end of a wait queue. The waiter must not already
* be waiting in a queue.
*
* @param queue The queue to which to add the waiter
* @param waiter The waiter to add to the queue
*
* @return VDO_SUCCESS or an error code
**/
int enqueueWaiter(WaitQueue *queue, Waiter *waiter)
__attribute__((warn_unused_result));
/**
* Notify all the entries waiting in a queue to continue execution by invoking
* a callback function on each of them in turn. The queue is copied and
* emptied before invoking any callbacks, and only the waiters that were in
* the queue at the start of the call will be notified.
*
* @param queue The wait queue containing the waiters to notify
* @param callback The function to call to notify each waiter, or NULL
* to invoke the callback field registered in each waiter
* @param context The context to pass to the callback function
**/
void notifyAllWaiters(WaitQueue *queue,
WaiterCallback *callback,
void *context);
/**
* Notify the next entry waiting in a queue to continue execution by invoking
* a callback function on it after removing it from the queue.
*
* @param queue The wait queue containing the waiter to notify
* @param callback The function to call to notify the waiter, or NULL
* to invoke the callback field registered in the waiter
* @param context The context to pass to the callback function
*
* @return true
if there was a waiter in the queue
**/
bool notifyNextWaiter(WaitQueue *queue,
WaiterCallback *callback,
void *context);
/**
* Transfer all waiters from one wait queue to a second queue, emptying the
* first queue.
*
* @param fromQueue The queue containing the waiters to move
* @param toQueue The queue that will receive the waiters from the
* the first queue
**/
void transferAllWaiters(WaitQueue *fromQueue, WaitQueue *toQueue);
/**
* Return the waiter that is at the head end of a wait queue.
*
* @param queue The queue from which to get the first waiter
*
* @return The first (oldest) waiter in the queue, or NULL
if
* the queue is empty
**/
Waiter *getFirstWaiter(const WaitQueue *queue);
/**
* Remove all waiters that match based on the specified matching method and
* append them to a WaitQueue.
*
* @param queue The wait queue to process
* @param matchMethod The method to determine matching
* @param matchContext Contextual info for the match method
* @param matchedQueue A WaitQueue to store matches
*
* @return VDO_SUCCESS or an error code
**/
int dequeueMatchingWaiters(WaitQueue *queue,
WaiterMatch *matchMethod,
void *matchContext,
WaitQueue *matchedQueue);
/**
* Remove the first waiter from the head end of a wait queue. The caller will
* be responsible for waking the waiter by invoking the correct callback
* function to resume its execution.
*
* @param queue The wait queue from which to remove the first entry
*
* @return The first (oldest) waiter in the queue, or NULL
if
* the queue is empty
**/
Waiter *dequeueNextWaiter(WaitQueue *queue);
/**
* Count the number of waiters in a wait queue.
*
* @param queue The wait queue to query
*
* @return the number of waiters in the queue
**/
__attribute__((warn_unused_result))
static inline size_t countWaiters(const WaitQueue *queue)
{
return queue->queueLength;
}
/**
* Get the waiter after this one, for debug iteration.
*
* @param queue The wait queue
* @param waiter A waiter
*
* @return the next waiter, or NULL
**/
const Waiter *getNextWaiter(const WaitQueue *queue, const Waiter *waiter)
__attribute__((warn_unused_result));
#endif // WAIT_QUEUE_H