/* GLIB - Library of useful routines for C programming
 * Copyright (C) 1995-1997  Peter Mattis, Spencer Kimball and Josh MacDonald
 *
 * GAsyncQueue: asynchronous queue implementation, based on GQueue.
 * Copyright (C) 2000 Sebastian Wilhelmi; University of Karlsruhe
 *
 * SPDX-License-Identifier: LGPL-2.1-or-later
 *
 * This library is free software; you can redistribute it and/or
 * modify it under the terms of the GNU Lesser General Public
 * License as published by the Free Software Foundation; either
 * version 2.1 of the License, or (at your option) any later version.
 *
 * This library 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
 * Lesser General Public License for more details.
 *
 * You should have received a copy of the GNU Lesser General Public
 * License along with this library; if not, see <http://www.gnu.org/licenses/>.
 */

/*
 * MT safe
 */

#include "config.h"

#include "gasyncqueue.h"
#include "gasyncqueueprivate.h"

#include "gmain.h"
#include "gmem.h"
#include "gqueue.h"
#include "gtestutils.h"
#include "gtimer.h"
#include "gthread.h"
#include "deprecated/gthread.h"

/**
 * GAsyncQueue:
 *
 * An opaque data structure which represents an asynchronous queue.
 *
 * It should only be accessed through the `g_async_queue_*` functions.
 */
struct _GAsyncQueue
{
  GMutex mutex;
  GCond cond;
  GQueue queue;
  GDestroyNotify item_free_func;
  guint waiting_threads;
  gint ref_count;
};

typedef struct
{
  GCompareDataFunc func;
  gpointer         user_data;
} SortData;

/**
 * g_async_queue_new: (constructor)
 *
 * Creates a new asynchronous queue.
 *
 * Returns: (transfer full): a new #GAsyncQueue. Free with g_async_queue_unref()
 */
GAsyncQueue *
g_async_queue_new (void)
{
  return g_async_queue_new_full (NULL);
}

/**
 * g_async_queue_new_full: (constructor)
 * @item_free_func: (nullable): function to free queue elements
 *
 * Creates a new asynchronous queue and sets up a destroy notify
 * function that is used to free any remaining queue items when
 * the queue is destroyed after the final unref.
 *
 * Returns: (transfer full): a new #GAsyncQueue. Free with g_async_queue_unref()
 *
 * Since: 2.16
 */
GAsyncQueue *
g_async_queue_new_full (GDestroyNotify item_free_func)
{
  GAsyncQueue *queue;

  queue = g_new (GAsyncQueue, 1);
  g_mutex_init (&queue->mutex);
  g_cond_init (&queue->cond);
  g_queue_init (&queue->queue);
  queue->waiting_threads = 0;
  queue->ref_count = 1;
  queue->item_free_func = item_free_func;

  return queue;
}

/**
 * g_async_queue_ref:
 * @queue: a #GAsyncQueue
 *
 * Increases the reference count of the asynchronous @queue by 1.
 * You do not need to hold the lock to call this function.
 *
 * Returns: (transfer full): the @queue that was passed in (since 2.6)
 */
GAsyncQueue *
g_async_queue_ref (GAsyncQueue *queue)
{
  g_return_val_if_fail (queue, NULL);

  g_atomic_int_inc (&queue->ref_count);

  return queue;
}

/**
 * g_async_queue_ref_unlocked:
 * @queue: a #GAsyncQueue
 *
 * Increases the reference count of the asynchronous @queue by 1.
 *
 * Deprecated: 2.8: Reference counting is done atomically.
 * so g_async_queue_ref() can be used regardless of the @queue's
 * lock.
 */
void
g_async_queue_ref_unlocked (GAsyncQueue *queue)
{
  g_return_if_fail (queue);

  g_atomic_int_inc (&queue->ref_count);
}

/**
 * g_async_queue_unref_and_unlock:
 * @queue: a #GAsyncQueue
 *
 * Decreases the reference count of the asynchronous @queue by 1
 * and releases the lock. This function must be called while holding
 * the @queue's lock. If the reference count went to 0, the @queue
 * will be destroyed and the memory allocated will be freed.
 *
 * Deprecated: 2.8: Reference counting is done atomically.
 * so g_async_queue_unref() can be used regardless of the @queue's
 * lock.
 */
void
g_async_queue_unref_and_unlock (GAsyncQueue *queue)
{
  g_return_if_fail (queue);

  g_mutex_unlock (&queue->mutex);
  g_async_queue_unref (queue);
}

/**
 * g_async_queue_unref:
 * @queue: (transfer full): a #GAsyncQueue.
 *
 * Decreases the reference count of the asynchronous @queue by 1.
 *
 * If the reference count went to 0, the @queue will be destroyed
 * and the memory allocated will be freed. So you are not allowed
 * to use the @queue afterwards, as it might have disappeared.
 * You do not need to hold the lock to call this function.
 */
void
g_async_queue_unref (GAsyncQueue *queue)
{
  g_return_if_fail (queue);

  if (g_atomic_int_dec_and_test (&queue->ref_count))
    {
      g_return_if_fail (queue->waiting_threads == 0);
      g_mutex_clear (&queue->mutex);
      g_cond_clear (&queue->cond);
      if (queue->item_free_func)
        g_queue_foreach (&queue->queue, (GFunc) queue->item_free_func, NULL);
      g_queue_clear (&queue->queue);
      g_free (queue);
    }
}

/**
 * g_async_queue_lock:
 * @queue: a #GAsyncQueue
 *
 * Acquires the @queue's lock. If another thread is already
 * holding the lock, this call will block until the lock
 * becomes available.
 *
 * Call g_async_queue_unlock() to drop the lock again.
 *
 * While holding the lock, you can only call the
 * g_async_queue_*_unlocked() functions on @queue. Otherwise,
 * deadlock may occur.
 */
void
g_async_queue_lock (GAsyncQueue *queue)
{
  g_return_if_fail (queue);

  g_mutex_lock (&queue->mutex);
}

/**
 * g_async_queue_unlock:
 * @queue: a #GAsyncQueue
 *
 * Releases the queue's lock.
 *
 * Calling this function when you have not acquired
 * the with g_async_queue_lock() leads to undefined
 * behaviour.
 */
void
g_async_queue_unlock (GAsyncQueue *queue)
{
  g_return_if_fail (queue);

  g_mutex_unlock (&queue->mutex);
}

/**
 * g_async_queue_push:
 * @queue: a #GAsyncQueue
 * @data: (not nullable): data to push onto the @queue
 *
 * Pushes the @data into the @queue.
 *
 * The @data parameter must not be %NULL.
 */
void
g_async_queue_push (GAsyncQueue *queue,
                    gpointer     data)
{
  g_return_if_fail (queue);
  g_return_if_fail (data);

  g_mutex_lock (&queue->mutex);
  g_async_queue_push_unlocked (queue, data);
  g_mutex_unlock (&queue->mutex);
}

/**
 * g_async_queue_push_unlocked:
 * @queue: a #GAsyncQueue
 * @data: (not nullable): data to push onto the @queue
 *
 * Pushes the @data into the @queue.
 *
 * The @data parameter must not be %NULL.
 *
 * This function must be called while holding the @queue's lock.
 */
void
g_async_queue_push_unlocked (GAsyncQueue *queue,
                             gpointer     data)
{
  g_return_if_fail (queue);
  g_return_if_fail (data);

  g_queue_push_head (&queue->queue, data);
  if (queue->waiting_threads > 0)
    g_cond_signal (&queue->cond);
}

/**
 * g_async_queue_push_sorted:
 * @queue: a #GAsyncQueue
 * @data: (not nullable): the @data to push into the @queue
 * @func: (scope call): the #GCompareDataFunc is used to sort @queue
 * @user_data: user data passed to @func.
 *
 * Inserts @data into @queue using @func to determine the new
 * position.
 *
 * This function requires that the @queue is sorted before pushing on
 * new elements, see g_async_queue_sort().
 *
 * This function will lock @queue before it sorts the queue and unlock
 * it when it is finished.
 *
 * For an example of @func see g_async_queue_sort().
 *
 * Since: 2.10
 */
void
g_async_queue_push_sorted (GAsyncQueue      *queue,
                           gpointer          data,
                           GCompareDataFunc  func,
                           gpointer          user_data)
{
  g_return_if_fail (queue != NULL);

  g_mutex_lock (&queue->mutex);
  g_async_queue_push_sorted_unlocked (queue, data, func, user_data);
  g_mutex_unlock (&queue->mutex);
}

static gint
g_async_queue_invert_compare (gpointer  v1,
                              gpointer  v2,
                              SortData *sd)
{
  return -sd->func (v1, v2, sd->user_data);
}

/**
 * g_async_queue_push_sorted_unlocked:
 * @queue: a #GAsyncQueue
 * @data: the data to push into the @queue
 * @func: (scope call): the #GCompareDataFunc is used to sort @queue
 * @user_data: user data passed to @func.
 *
 * Inserts @data into @queue using @func to determine the new
 * position.
 *
 * The sort function @func is passed two elements of the @queue.
 * It should return 0 if they are equal, a negative value if the
 * first element should be higher in the @queue or a positive value
 * if the first element should be lower in the @queue than the second
 * element.
 *
 * This function requires that the @queue is sorted before pushing on
 * new elements, see g_async_queue_sort().
 *
 * This function must be called while holding the @queue's lock.
 *
 * For an example of @func see g_async_queue_sort().
 *
 * Since: 2.10
 */
void
g_async_queue_push_sorted_unlocked (GAsyncQueue      *queue,
                                    gpointer          data,
                                    GCompareDataFunc  func,
                                    gpointer          user_data)
{
  SortData sd;

  g_return_if_fail (queue != NULL);

  sd.func = func;
  sd.user_data = user_data;

  g_queue_insert_sorted (&queue->queue,
                         data,
                         (GCompareDataFunc)g_async_queue_invert_compare,
                         &sd);
  if (queue->waiting_threads > 0)
    g_cond_signal (&queue->cond);
}

static gpointer
g_async_queue_pop_intern_unlocked (GAsyncQueue *queue,
                                   gboolean     wait,
                                   gint64       end_time)
{
  gpointer retval;

  if (!g_queue_peek_tail_link (&queue->queue) && wait)
    {
      queue->waiting_threads++;
      while (!g_queue_peek_tail_link (&queue->queue))
        {
	  if (end_time == -1)
	    g_cond_wait (&queue->cond, &queue->mutex);
	  else
	    {
	      if (!g_cond_wait_until (&queue->cond, &queue->mutex, end_time))
		break;
	    }
        }
      queue->waiting_threads--;
    }

  retval = g_queue_pop_tail (&queue->queue);

  g_assert (retval || !wait || end_time > 0);

  return retval;
}

/**
 * g_async_queue_pop:
 * @queue: a #GAsyncQueue
 *
 * Pops data from the @queue. If @queue is empty, this function
 * blocks until data becomes available.
 *
 * Returns: data from the queue
 */
gpointer
g_async_queue_pop (GAsyncQueue *queue)
{
  gpointer retval;

  g_return_val_if_fail (queue, NULL);

  g_mutex_lock (&queue->mutex);
  retval = g_async_queue_pop_intern_unlocked (queue, TRUE, -1);
  g_mutex_unlock (&queue->mutex);

  return retval;
}

/**
 * g_async_queue_pop_unlocked:
 * @queue: a #GAsyncQueue
 *
 * Pops data from the @queue. If @queue is empty, this function
 * blocks until data becomes available.
 *
 * This function must be called while holding the @queue's lock.
 *
 * Returns: data from the queue.
 */
gpointer
g_async_queue_pop_unlocked (GAsyncQueue *queue)
{
  g_return_val_if_fail (queue, NULL);

  return g_async_queue_pop_intern_unlocked (queue, TRUE, -1);
}

/**
 * g_async_queue_try_pop:
 * @queue: a #GAsyncQueue
 *
 * Tries to pop data from the @queue. If no data is available,
 * %NULL is returned.
 *
 * Returns: (nullable): data from the queue or %NULL, when no data is
 *   available immediately.
 */
gpointer
g_async_queue_try_pop (GAsyncQueue *queue)
{
  gpointer retval;

  g_return_val_if_fail (queue, NULL);

  g_mutex_lock (&queue->mutex);
  retval = g_async_queue_pop_intern_unlocked (queue, FALSE, -1);
  g_mutex_unlock (&queue->mutex);

  return retval;
}

/**
 * g_async_queue_try_pop_unlocked:
 * @queue: a #GAsyncQueue
 *
 * Tries to pop data from the @queue. If no data is available,
 * %NULL is returned.
 *
 * This function must be called while holding the @queue's lock.
 *
 * Returns: (nullable): data from the queue or %NULL, when no data is
 *   available immediately.
 */
gpointer
g_async_queue_try_pop_unlocked (GAsyncQueue *queue)
{
  g_return_val_if_fail (queue, NULL);

  return g_async_queue_pop_intern_unlocked (queue, FALSE, -1);
}

/**
 * g_async_queue_timeout_pop:
 * @queue: a #GAsyncQueue
 * @timeout: the number of microseconds to wait
 *
 * Pops data from the @queue. If the queue is empty, blocks for
 * @timeout microseconds, or until data becomes available.
 *
 * If no data is received before the timeout, %NULL is returned.
 *
 * Returns: (nullable): data from the queue or %NULL, when no data is
 *   received before the timeout.
 */
gpointer
g_async_queue_timeout_pop (GAsyncQueue *queue,
			   guint64      timeout)
{
  gint64 end_time = g_get_monotonic_time () + timeout;
  gpointer retval;

  g_return_val_if_fail (queue != NULL, NULL);

  g_mutex_lock (&queue->mutex);
  retval = g_async_queue_pop_intern_unlocked (queue, TRUE, end_time);
  g_mutex_unlock (&queue->mutex);

  return retval;
}

/**
 * g_async_queue_timeout_pop_unlocked:
 * @queue: a #GAsyncQueue
 * @timeout: the number of microseconds to wait
 *
 * Pops data from the @queue. If the queue is empty, blocks for
 * @timeout microseconds, or until data becomes available.
 *
 * If no data is received before the timeout, %NULL is returned.
 *
 * This function must be called while holding the @queue's lock.
 *
 * Returns: (nullable): data from the queue or %NULL, when no data is
 *   received before the timeout.
 */
gpointer
g_async_queue_timeout_pop_unlocked (GAsyncQueue *queue,
				    guint64      timeout)
{
  gint64 end_time = g_get_monotonic_time () + timeout;

  g_return_val_if_fail (queue != NULL, NULL);

  return g_async_queue_pop_intern_unlocked (queue, TRUE, end_time);
}

/**
 * g_async_queue_timed_pop:
 * @queue: a #GAsyncQueue
 * @end_time: a #GTimeVal, determining the final time
 *
 * Pops data from the @queue. If the queue is empty, blocks until
 * @end_time or until data becomes available.
 *
 * If no data is received before @end_time, %NULL is returned.
 *
 * To easily calculate @end_time, a combination of g_get_real_time()
 * and g_time_val_add() can be used.
 *
 * Returns: (nullable): data from the queue or %NULL, when no data is
 *   received before @end_time.
 *
 * Deprecated: use g_async_queue_timeout_pop().
 */
G_GNUC_BEGIN_IGNORE_DEPRECATIONS
gpointer
g_async_queue_timed_pop (GAsyncQueue *queue,
                         GTimeVal    *end_time)
{
  gint64 m_end_time;
  gpointer retval;

  g_return_val_if_fail (queue, NULL);

  if (end_time != NULL)
    {
      m_end_time = g_get_monotonic_time () +
        ((gint64) end_time->tv_sec * G_USEC_PER_SEC + end_time->tv_usec - g_get_real_time ());
    }
  else
    m_end_time = -1;

  g_mutex_lock (&queue->mutex);
  retval = g_async_queue_pop_intern_unlocked (queue, TRUE, m_end_time);
  g_mutex_unlock (&queue->mutex);

  return retval;
}
G_GNUC_END_IGNORE_DEPRECATIONS

/**
 * g_async_queue_timed_pop_unlocked:
 * @queue: a #GAsyncQueue
 * @end_time: a #GTimeVal, determining the final time
 *
 * Pops data from the @queue. If the queue is empty, blocks until
 * @end_time or until data becomes available.
 *
 * If no data is received before @end_time, %NULL is returned.
 *
 * To easily calculate @end_time, a combination of g_get_real_time()
 * and g_time_val_add() can be used.
 *
 * This function must be called while holding the @queue's lock.
 *
 * Returns: (nullable): data from the queue or %NULL, when no data is
 *   received before @end_time.
 *
 * Deprecated: use g_async_queue_timeout_pop_unlocked().
 */
G_GNUC_BEGIN_IGNORE_DEPRECATIONS
gpointer
g_async_queue_timed_pop_unlocked (GAsyncQueue *queue,
                                  GTimeVal    *end_time)
{
  gint64 m_end_time;

  g_return_val_if_fail (queue, NULL);

  if (end_time != NULL)
    {
      m_end_time = g_get_monotonic_time () +
        ((gint64) end_time->tv_sec * G_USEC_PER_SEC + end_time->tv_usec - g_get_real_time ());
    }
  else
    m_end_time = -1;

  return g_async_queue_pop_intern_unlocked (queue, TRUE, m_end_time);
}
G_GNUC_END_IGNORE_DEPRECATIONS

/**
 * g_async_queue_length:
 * @queue: a #GAsyncQueue.
 *
 * Returns the length of the queue.
 *
 * Actually this function returns the number of data items in
 * the queue minus the number of waiting threads, so a negative
 * value means waiting threads, and a positive value means available
 * entries in the @queue. A return value of 0 could mean n entries
 * in the queue and n threads waiting. This can happen due to locking
 * of the queue or due to scheduling.
 *
 * Returns: the length of the @queue
 */
gint
g_async_queue_length (GAsyncQueue *queue)
{
  gint retval;

  g_return_val_if_fail (queue, 0);

  g_mutex_lock (&queue->mutex);
  retval = queue->queue.length - queue->waiting_threads;
  g_mutex_unlock (&queue->mutex);

  return retval;
}

/**
 * g_async_queue_length_unlocked:
 * @queue: a #GAsyncQueue
 *
 * Returns the length of the queue.
 *
 * Actually this function returns the number of data items in
 * the queue minus the number of waiting threads, so a negative
 * value means waiting threads, and a positive value means available
 * entries in the @queue. A return value of 0 could mean n entries
 * in the queue and n threads waiting. This can happen due to locking
 * of the queue or due to scheduling.
 *
 * This function must be called while holding the @queue's lock.
 *
 * Returns: the length of the @queue.
 */
gint
g_async_queue_length_unlocked (GAsyncQueue *queue)
{
  g_return_val_if_fail (queue, 0);

  return queue->queue.length - queue->waiting_threads;
}

/**
 * g_async_queue_sort:
 * @queue: a #GAsyncQueue
 * @func: (scope call): the #GCompareDataFunc is used to sort @queue
 * @user_data: user data passed to @func
 *
 * Sorts @queue using @func.
 *
 * The sort function @func is passed two elements of the @queue.
 * It should return 0 if they are equal, a negative value if the
 * first element should be higher in the @queue or a positive value
 * if the first element should be lower in the @queue than the second
 * element.
 *
 * This function will lock @queue before it sorts the queue and unlock
 * it when it is finished.
 *
 * If you were sorting a list of priority numbers to make sure the
 * lowest priority would be at the top of the queue, you could use:
 * |[<!-- language="C" -->
 *  gint32 id1;
 *  gint32 id2;
 *
 *  id1 = GPOINTER_TO_INT (element1);
 *  id2 = GPOINTER_TO_INT (element2);
 *
 *  return (id1 > id2 ? +1 : id1 == id2 ? 0 : -1);
 * ]|
 *
 * Since: 2.10
 */
void
g_async_queue_sort (GAsyncQueue      *queue,
                    GCompareDataFunc  func,
                    gpointer          user_data)
{
  g_return_if_fail (queue != NULL);
  g_return_if_fail (func != NULL);

  g_mutex_lock (&queue->mutex);
  g_async_queue_sort_unlocked (queue, func, user_data);
  g_mutex_unlock (&queue->mutex);
}

/**
 * g_async_queue_sort_unlocked:
 * @queue: a #GAsyncQueue
 * @func: (scope call): the #GCompareDataFunc is used to sort @queue
 * @user_data: user data passed to @func
 *
 * Sorts @queue using @func.
 *
 * The sort function @func is passed two elements of the @queue.
 * It should return 0 if they are equal, a negative value if the
 * first element should be higher in the @queue or a positive value
 * if the first element should be lower in the @queue than the second
 * element.
 *
 * This function must be called while holding the @queue's lock.
 *
 * Since: 2.10
 */
void
g_async_queue_sort_unlocked (GAsyncQueue      *queue,
                             GCompareDataFunc  func,
                             gpointer          user_data)
{
  SortData sd;

  g_return_if_fail (queue != NULL);
  g_return_if_fail (func != NULL);

  sd.func = func;
  sd.user_data = user_data;

  g_queue_sort (&queue->queue,
                (GCompareDataFunc)g_async_queue_invert_compare,
                &sd);
}

/**
 * g_async_queue_remove:
 * @queue: a #GAsyncQueue
 * @item: (not nullable): the data to remove from the @queue
 *
 * Remove an item from the queue.
 *
 * Returns: %TRUE if the item was removed
 *
 * Since: 2.46
 */
gboolean
g_async_queue_remove (GAsyncQueue *queue,
                      gpointer     item)
{
  gboolean ret;

  g_return_val_if_fail (queue != NULL, FALSE);
  g_return_val_if_fail (item != NULL, FALSE);

  g_mutex_lock (&queue->mutex);
  ret = g_async_queue_remove_unlocked (queue, item);
  g_mutex_unlock (&queue->mutex);

  return ret;
}

/**
 * g_async_queue_remove_unlocked:
 * @queue: a #GAsyncQueue
 * @item: the data to remove from the @queue
 *
 * Remove an item from the queue.
 *
 * This function must be called while holding the @queue's lock.
 *
 * Returns: %TRUE if the item was removed
 *
 * Since: 2.46
 */
gboolean
g_async_queue_remove_unlocked (GAsyncQueue *queue,
                               gpointer     item)
{
  g_return_val_if_fail (queue != NULL, FALSE);
  g_return_val_if_fail (item != NULL, FALSE);

  return g_queue_remove (&queue->queue, item);
}

/**
 * g_async_queue_push_front:
 * @queue: a #GAsyncQueue
 * @item: (not nullable): data to push into the @queue
 *
 * Pushes the @item into the @queue. @item must not be %NULL.
 * In contrast to g_async_queue_push(), this function
 * pushes the new item ahead of the items already in the queue,
 * so that it will be the next one to be popped off the queue.
 *
 * Since: 2.46
 */
void
g_async_queue_push_front (GAsyncQueue *queue,
                          gpointer     item)
{
  g_return_if_fail (queue != NULL);
  g_return_if_fail (item != NULL);

  g_mutex_lock (&queue->mutex);
  g_async_queue_push_front_unlocked (queue, item);
  g_mutex_unlock (&queue->mutex);
}

/**
 * g_async_queue_push_front_unlocked:
 * @queue: a #GAsyncQueue
 * @item: (not nullable): data to push into the @queue
 *
 * Pushes the @item into the @queue. @item must not be %NULL.
 * In contrast to g_async_queue_push_unlocked(), this function
 * pushes the new item ahead of the items already in the queue,
 * so that it will be the next one to be popped off the queue.
 *
 * This function must be called while holding the @queue's lock.
 *
 * Since: 2.46
 */
void
g_async_queue_push_front_unlocked (GAsyncQueue *queue,
                                   gpointer     item)
{
  g_return_if_fail (queue != NULL);
  g_return_if_fail (item != NULL);

  g_queue_push_tail (&queue->queue, item);
  if (queue->waiting_threads > 0)
    g_cond_signal (&queue->cond);
}

/*
 * Private API
 */

GMutex *
_g_async_queue_get_mutex (GAsyncQueue *queue)
{
  g_return_val_if_fail (queue, NULL);

  return &queue->mutex;
}