libretro-common/queues/generic_queue.c

/* Copyright  (C) 2010-2020 The RetroArch team
 *
 * ---------------------------------------------------------------------------------------
 * The following license statement only applies to this file (generic_queue.c).
 * ---------------------------------------------------------------------------------------
 *
 * Permission is hereby granted, free of charge,
 * to any person obtaining a copy of this software and associated documentation files (the "Software"),
 * to deal in the Software without restriction, including without limitation the rights to
 * use, copy, modify, merge, publish, distribute, sublicense, and/or sell copies of the Software,
 * and to permit persons to whom the Software is furnished to do so, subject to the following conditions:
 *
 * The above copyright notice and this permission notice shall be included in all copies or substantial portions of the Software.
 *
 * THE SOFTWARE IS PROVIDED "AS IS", WITHOUT WARRANTY OF ANY KIND, EXPRESS OR IMPLIED,
 * INCLUDING BUT NOT LIMITED TO THE WARRANTIES OF MERCHANTABILITY,
 * FITNESS FOR A PARTICULAR PURPOSE AND NONINFRINGEMENT.
 * IN NO EVENT SHALL THE AUTHORS OR COPYRIGHT HOLDERS BE LIABLE FOR ANY CLAIM, DAMAGES OR OTHER LIABILITY,
 * WHETHER IN AN ACTION OF CONTRACT, TORT OR OTHERWISE, ARISING FROM,
 * OUT OF OR IN CONNECTION WITH THE SOFTWARE OR THE USE OR OTHER DEALINGS IN THE SOFTWARE.
 */

#include <boolean.h>
#include <stddef.h>
#include <stdlib.h>

#include <queues/generic_queue.h>

struct generic_queue_item_t
{
   void *value;
   struct generic_queue_item_t *previous;
   struct generic_queue_item_t *next;
};

struct generic_queue
{
   struct generic_queue_item_t *first_item;
   struct generic_queue_item_t *last_item;
   size_t length;
};

struct generic_queue_iterator
{
   generic_queue_t *queue;
   struct generic_queue_item_t *item;
   bool forward;
};

generic_queue_t *generic_queue_new(void)
{
   return (generic_queue_t *)calloc(1, sizeof(generic_queue_t));
}

void generic_queue_free(generic_queue_t *queue, void (*free_value)(void *value))
{
   struct generic_queue_item_t *next_item;

   if (!queue)
      return;

   while (queue->first_item)
   {
      if (free_value)
         free_value(queue->first_item->value);

      next_item = queue->first_item->next;
      free(queue->first_item);
      queue->first_item = next_item;
   }

   free(queue);
}

void generic_queue_push(generic_queue_t *queue, void *value)
{
   struct generic_queue_item_t *new_item;

   new_item = (struct generic_queue_item_t *)calloc(1, sizeof(struct generic_queue_item_t));
   new_item->value = value;
   new_item->previous = queue->last_item;
   new_item->next = NULL;

   queue->last_item = new_item;
   queue->length++;

   if (!queue->first_item)
      queue->first_item = new_item;
   else
      new_item->previous->next = new_item;
}

void *generic_queue_pop(generic_queue_t *queue)
{
   void *value;
   struct generic_queue_item_t *item;

   if (!queue || !queue->last_item)
      return NULL;

   item = queue->last_item;
   queue->last_item = queue->last_item->previous;
   queue->length--;

   if (queue->length == 0)
      queue->first_item = NULL;

   value = item->value;
   free(item);

   return value;
}

void *generic_queue_peek(generic_queue_t *queue)
{
   if (!queue || !queue->last_item)
      return NULL;

   return queue->last_item->value;
}

void *generic_queue_peek_first(generic_queue_t *queue)
{
   if (!queue || !queue->first_item)
      return NULL;

   return queue->first_item->value;
}

void generic_queue_shift(generic_queue_t *queue, void *value)
{
   struct generic_queue_item_t *new_item;

   if (!queue)
      return;

   new_item = (struct generic_queue_item_t *)calloc(1, sizeof(struct generic_queue_item_t));
   new_item->value = value;
   new_item->previous = NULL;
   new_item->next = queue->first_item;

   queue->first_item = new_item;
   queue->length++;

   if (!queue->last_item)
      queue->last_item = new_item;
   else
      new_item->next->previous = new_item;
}

void *generic_queue_unshift(generic_queue_t *queue)
{
   void *value;
   struct generic_queue_item_t *item;

   if (!queue || !queue->first_item)
      return NULL;

   item = queue->first_item;
   queue->first_item = queue->first_item->next;
   queue->length--;

   if (queue->length == 0)
      queue->last_item = NULL;

   value = item->value;
   free(item);

   return value;
}

size_t generic_queue_length(generic_queue_t *queue)
{
   if (queue)
      return queue->length;

   return 0;
}

void *generic_queue_remove(generic_queue_t *queue, void *value)
{
   struct generic_queue_item_t *item;

   if (!queue)
      return NULL;

   for (item = queue->first_item; item; item = item->next)
   {
      if (item->value == value)
      {
         if (item->previous)
            item->previous->next = item->next;
         else
            queue->first_item = item->next;

         if (item->next)
            item->next->previous = item->previous;
         else
            queue->last_item = item->previous;

         free(item);
         queue->length--;

         return value;
      }
   }

   return NULL;
}

generic_queue_iterator_t *generic_queue_iterator(generic_queue_t *queue, bool forward)
{
   if (queue && queue->first_item)
   {
      generic_queue_iterator_t *iterator;

      iterator = (generic_queue_iterator_t *)malloc(sizeof(generic_queue_iterator_t));
      iterator->queue = queue;
      iterator->item = forward ? queue->first_item : queue->last_item;
      iterator->forward = forward;

      return iterator;
   }

   return NULL;
}

generic_queue_iterator_t *generic_queue_iterator_next(generic_queue_iterator_t *iterator)
{
   if (iterator)
   {
      struct generic_queue_item_t *item;

      item = iterator->forward ? iterator->item->next : iterator->item->previous;
      if (item)
      {
         iterator->item = item;
         return iterator;
      } else
      {
         free(iterator);
         return NULL;
      }
   }

   return NULL;
}

void *generic_queue_iterator_value(generic_queue_iterator_t *iterator)
{
   if (iterator)
      return iterator->item->value;

   return NULL;
}

generic_queue_iterator_t *generic_queue_iterator_remove(generic_queue_iterator_t *iterator)
{
   struct generic_queue_item_t *item;

   if (!iterator)
      return NULL;

   item = iterator->forward ? iterator->queue->first_item : iterator->queue->last_item;
   while (item)
   {
      if (iterator->item == item)
      {
         if (iterator->queue->first_item == item)
            iterator->queue->first_item = item->next;
         else
            item->previous->next = item->next;

         if (iterator->queue->last_item == item)
            iterator->queue->last_item = item->previous;
         else
            item->next->previous = item->previous;

         iterator->queue->length--;

         iterator->item = iterator->forward ? item->next : item->previous;
         free(item);
         if (iterator->item)
         {
            return iterator;
         } else
         {
            free(iterator);
            return NULL;
         }
      }

      item = iterator->forward ? item->next : item->previous;
   }

   return iterator;
}

void generic_queue_iterator_free(generic_queue_iterator_t *iterator)
{
   if (iterator)
      free(iterator);
}