/*

 * 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