/*
 * 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.c#1 $
 */

#include "waitQueue.h"

#include "permassert.h"

#include "statusCodes.h"

/**********************************************************************/
int enqueueWaiter(WaitQueue *queue, Waiter *waiter)
{
  int result = ASSERT((waiter->nextWaiter == NULL),
                      "new waiter must not already be in a waiter queue");
  if (result != VDO_SUCCESS) {
    return result;
  }

  if (queue->lastWaiter == NULL) {
    // The queue is empty, so form the initial circular list by self-linking
    // the initial waiter.
    waiter->nextWaiter = waiter;
  } else {
    // Splice the new waiter in at the end of the queue.
    waiter->nextWaiter = queue->lastWaiter->nextWaiter;
    queue->lastWaiter->nextWaiter = waiter;
  }
  // In both cases, the waiter we added to the ring becomes the last waiter.
  queue->lastWaiter   = waiter;
  queue->queueLength += 1;
  return VDO_SUCCESS;
}

/**********************************************************************/
void transferAllWaiters(WaitQueue *fromQueue, WaitQueue *toQueue)
{
  // If the source queue is empty, there's nothing to do.
  if (!hasWaiters(fromQueue)) {
    return;
  }

  if (hasWaiters(toQueue)) {
    // Both queues are non-empty. Splice the two circular lists together by
    // swapping the next (head) pointers in the list tails.
    Waiter *fromHead = fromQueue->lastWaiter->nextWaiter;
    Waiter *toHead   = toQueue->lastWaiter->nextWaiter;
    toQueue->lastWaiter->nextWaiter   = fromHead;
    fromQueue->lastWaiter->nextWaiter = toHead;
  }

  toQueue->lastWaiter   = fromQueue->lastWaiter;
  toQueue->queueLength += fromQueue->queueLength;
  initializeWaitQueue(fromQueue);
}

/**********************************************************************/
void notifyAllWaiters(WaitQueue      *queue,
                      WaiterCallback *callback,
                      void           *context)
{
  // Copy and empty the queue first, avoiding the possibility of an infinite
  // loop if entries are returned to the queue by the callback function.
  WaitQueue waiters;
  initializeWaitQueue(&waiters);
  transferAllWaiters(queue, &waiters);

  // Drain the copied queue, invoking the callback on every entry.
  while (notifyNextWaiter(&waiters, callback, context)) {
    // All the work is done by the loop condition.
  }
}

/**********************************************************************/
Waiter *getFirstWaiter(const WaitQueue *queue)
{
  Waiter *lastWaiter = queue->lastWaiter;
  if (lastWaiter == NULL) {
    // There are no waiters, so we're done.
    return NULL;
  }

  // The queue is circular, so the last entry links to the head of the queue.
  return lastWaiter->nextWaiter;
}

/**********************************************************************/
int dequeueMatchingWaiters(WaitQueue   *queue,
                           WaiterMatch *matchMethod,
                           void        *matchContext,
                           WaitQueue   *matchedQueue)
{
  WaitQueue matchedWaiters;
  initializeWaitQueue(&matchedWaiters);

  WaitQueue iterationQueue;
  initializeWaitQueue(&iterationQueue);
  transferAllWaiters(queue, &iterationQueue);
  while (hasWaiters(&iterationQueue)) {
    Waiter *waiter = dequeueNextWaiter(&iterationQueue);
    int     result = VDO_SUCCESS;
    if (!matchMethod(waiter, matchContext)) {
      result = enqueueWaiter(queue, waiter);
    } else {
      result = enqueueWaiter(&matchedWaiters, waiter);
    }
    if (result != VDO_SUCCESS) {
      transferAllWaiters(&matchedWaiters, queue);
      transferAllWaiters(&iterationQueue, queue);
      return result;
    }
  }

  transferAllWaiters(&matchedWaiters, matchedQueue);
  return VDO_SUCCESS;
}

/**********************************************************************/
Waiter *dequeueNextWaiter(WaitQueue *queue)
{
  Waiter *firstWaiter = getFirstWaiter(queue);
  if (firstWaiter == NULL) {
    return NULL;
  }

  Waiter *lastWaiter = queue->lastWaiter;
  if (firstWaiter == lastWaiter) {
    // The queue has a single entry, so just empty it out by nulling the tail.
    queue->lastWaiter = NULL;
  } else {
    // The queue has more than one entry, so splice the first waiter out of
    // the circular queue.
    lastWaiter->nextWaiter = firstWaiter->nextWaiter;
  }

  // The waiter is no longer in a wait queue.
  firstWaiter->nextWaiter  = NULL;
  queue->queueLength      -= 1;
  return firstWaiter;
}

/**********************************************************************/
bool notifyNextWaiter(WaitQueue      *queue,
                      WaiterCallback *callback,
                      void           *context)
{
  Waiter *waiter = dequeueNextWaiter(queue);
  if (waiter == NULL) {
    return false;
  }

  if (callback == NULL) {
    callback = waiter->callback;
  }
  (*callback)(waiter, context);
  return true;
}

/**********************************************************************/
const Waiter *getNextWaiter(const WaitQueue *queue, const Waiter *waiter)
{
  Waiter *firstWaiter = getFirstWaiter(queue);
  if (waiter == NULL) {
    return firstWaiter;
  }
  return ((waiter->nextWaiter != firstWaiter) ? waiter->nextWaiter : NULL);
}