/**
 * @file list.h
 * @author Greg Methvin <greg@methvin.net>
 * @date November 2, 2009
 *
 * @brief An implementation of a circular doubly linked list, along
 * with functions to manipulate it in C.
 *
 * @section LICENSE
 *
 * Redistribution and use in source and binary forms, with or without
 * modification, are permitted provided that the following conditions are
 * met:
 *
 *  * Redistributions of source code must retain the above copyright
 *    notice, this list of conditions and the following disclaimer.
 *
 *  * Redistributions in binary form must reproduce the above
 *    copyright notice, this list of conditions and the following
 *    disclaimer in the documentation and/or other materials provided
 *    with the distribution.
 *
 *  * The name of the author may not be used to endorse or promote
 *    products derived from this software without specific prior
 *    written permission
 *
 * THIS SOFTWARE IS PROVIDED BY THE AUTHOR "AS IS" AND ANY EXPRESS OR
 * IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE IMPLIED
 * WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE
 * ARE DISCLAIMED.  IN NO EVENT SHALL THE AUTHOR BE LIABLE FOR ANY
 * DIRECT, INDIRECT, INCIDENTAL, SPECIAL, EXEMPLARY, OR CONSEQUENTIAL
 * DAMAGES (INCLUDING, BUT NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE
 * GOODS OR SERVICES; LOSS OF USE, DATA, OR PROFITS; OR BUSINESS
 * INTERRUPTION) HOWEVER CAUSED AND ON ANY THEORY OF LIABILITY,
 * WHETHER IN CONTRACT, STRICT LIABILITY, OR TORT (INCLUDING
 * NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT OF THE USE OF THIS
 * SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE.
 *
 * @section DESCRIPTION
 *
 * This file defines a list_t struct, which can be included in any
 * struct of which you wish to create a linked list. The functions in
 * this file manipulate this struct and allow you to create linked
 * lists of them.
 *
 * We can create linked lists of any struct which has a list_t as one
 * of its members by using a macro (called list_item) which takes a
 * pointer to a list_t struct, finds the outer struct, and casts it to
 * the proper data type. The lists themselves are of the inner list_t,
 * but since we know the type and the name of the member in the
 * struct, we can use it to get a pointer to the outer struct given a
 * pointer to the inner list node.
 *
 * To use this library to define a linked list. We define a variable
 * of type list_t which serves as the "head" of the list, meaning it
 * contains no data. A pointer to this value can be used in the
 * functions and macros defined below to add, remove, and traverse the
 * items in the list.
 */
#ifndef _LIST_H_
#define _LIST_H_

#define NULL ((void *)0)

/**
 * @brief list_t data structure to be used for circular linked list
 * heads and nodes.
 *
 * Generally you will declare one of these as the head, which will
 * have no data at it. This will point to other nodes which are
 * contained within structs. A list_t which points to itself is
 * considered an "empty" list.
 */
typedef struct list_t {
  /** @brief a pointer to the next node */
  struct list_t *next;
  /** @brief a pointer to the previous node */
  struct list_t *prev;
} list_t;

/**
 * @brief Initialize the linked list head
 *
 * @param list a pointer to the head that is initialized. This is
 * initialized as a pointer with a head and a tail that point to
 * itself.
 */
static inline void list_init(list_t * list)
{
  list->next = list->prev = list;
}

/**
 * @brief Add a node to the linked list between two given nodes.
 *
 * @param node the new item to add
 * @param prev the previous node
 * @param next the next node
 */
static inline void list_add(list_t * node, list_t * prev,
                            list_t * next)
{
  next->prev = node;
  node->next = next;
  node->prev = prev;
  prev->next = node;
}

/**
 * @brief Prepend a node on the linked list, before the first item.
 *
 * @param hd the head of the linked list
 * @param node the new item to prepend
 */
static inline void list_prepend(list_t * hd, list_t * node)
{
  list_add(node, hd, hd->next);
}

/**
 * @brief append a node on the linked list, after the last item.
 *
 * @param hd the head of the linked list
 * @param node the new item to prepend
 */
static inline void list_append(list_t * hd, list_t * node)
{
  list_add(node, hd->prev, hd);
}

/**
 * @brief Remove one or more nodes from the linked list, without
 * modifying the prev or next pointers of the removed node(s).
 *
 * @param prev the item before the first removed item
 * @param next the item after the last removed item
 *
 * @return the first node that we removed. Use of list_item on a
 * removed node is defined, so you can then get the data of the
 * item.
 */
static inline list_t *list_remove(list_t * prev, list_t * next)
{
  list_t *h = prev->next;
  next->prev = prev;
  prev->next = next;
  return h;
}

/**
 * @brief Remove a given node from the list.
 *
 * @param node the node to remove
 */
static inline list_t *list_remove_node(list_t * node)
{
  list_t *n = list_remove(node->prev, node->next);
  node->next = node->prev = node;
  return n;
}

/**
 * @brief Remove the front item of a nonempty list.
 *
 * @param hd the list head
 * 
 * @return the list node of the front item.
 */
static inline list_t *list_remove_front(list_t * hd)
{
  return list_remove_node(hd->next);
}

/**
 * @brief Remove the tail item of a nonempty list.
 *
 * @param hd the list head
 * 
 * @return the list node of the last item.
 */
static inline list_t *list_remove_tail(list_t * hd)
{
  return list_remove_node(hd->prev);
}

/**
 * @brief Replace a list node with another list node.
 *
 * @param old a pointer to the old list node
 * @param new a pointer to the new list node
 *
 */
static inline void list_replace(list_t * old, list_t * new)
{
  new->next = old->next;
  new->next->prev = new;
  new->prev = old->prev;
  new->prev->next = new;
}


/**
 * @brief Check if a node is the first in the list.
 *
 * @param hd the head pointer of the list
 * @param node the node in the list
 *
 * @return 1 if the node is the first in the list, 0 otherwise.
 */
static inline int list_is_front(const list_t * hd,
                                const list_t * node)
{
  return node == hd->next;
}

/**
 * @brief Check if a node is the last in the list.
 *
 * @param hd the head pointer of the list
 * @param node the node in the list
 *
 * @return 1 if the node is the last in the list, 0 otherwise
 */
static inline int list_is_tail(const list_t * hd, const list_t * node)
{
  return node->next == hd;
}


/**
 * @brief Check if a list is empty.
 *
 * @param hd the head pointer of the list
 * 
 * @return 1 if the list is empty, 0 otherwise
 */
static inline int list_is_empty(const list_t * hd)
{
  return hd->next == hd;
}

/**
 * @brief Check if a list contains exactly one item.
 *
 * @param hd the head pointer of the list
 * 
 * @return 1 if the list has exactly one item, 0 otherwise
 */
static inline int list_has_one_item(const list_t * hd)
{
  return !list_is_empty(hd) && hd->next == hd->prev;
}

/**
 * @brief Get the actual data item for a given list node.
 *
 * @param ptr a pointer to the list node
 * @param type the type of the list node
 * @param mname the name of the member of the struct which is used for
 * the list node
 *
 * @return An item of the given type such that ptr is a pointer to the
 * member mname of the struct.
 */
#define list_item(ptr, type, mname)                         \
  ( (type *)( (char *)(ptr) -                               \
              (unsigned long)(&((type *)NULL)->mname) ) )

/**
 * @brief Get a pointer to the first data item in a list, given we
 * know that the list is not empty.
 *
 * @param ptr a pointer to the list node
 * @param type the type of the list node
 * @param mname the name of the member of the struct which is used for
 * the list node
 *
 * @return the first data item in the list of the given type with list
 * node member mname.
 */
#define list_first_item(hd, type, mname)        \
  list_item((hd)->next, type, mname)

/**
 * @brief Get a pointer to the last data item in a list, given we know
 * that the list is not empty.
 *
 * @param ptr a pointer to the list node
 * @param type the type of the list node
 * @param mname the name of the member of the struct which is used for
 * the list node
 *
 * @return the first data item in the list of the given type with list
 * node member mname.
 */
#define list_last_item(hd, type, mname)         \
  list_item((hd)->prev, type, mname)

/**
 * @brief macro to generate a for loop that iterates through the list
 * nodes
 *
 * @param cp a variable to use as the current pointer
 * @param hd the head pointer
 */
#define list_foreach(cp, hd)                        \
  for (cp = (hd)->next; cp != (hd); cp = cp->next)


/**
 * @brief macro to generate a for loop that iterates through the list
 * nodes, starting at the last item
 *
 * @param cp a variable to use as the current pointer
 * @param hd the head pointer
 */
#define list_foreach_rev(cp, hd)                    \
  for (cp = (hd)->prev; cp != (hd); cp = cp->prev)


/**
 * @brief macro to generate a for loop that iterates through the
 * actual data items in the list
 *
 * @param cp a variable to use as the current pointer to a data item
 * @param hd the head pointer
 * @param mname the name of the member of the struct which contains
 * the list node
 */
#define list_foreach_item(cp, hd, mname)                    \
  for (cp = list_item((hd)->next, typeof(*cp), mname);      \
       &cp->mname != (hd);                                  \
       cp = list_item(cp->mname.next, typeof(*cp), mname))


/**
 * @brief macro to generate a for loop that iterates through the
 * actual data items in the list, starting at the last item
 *
 * @param cp a variable to use as the current pointer to a data item
 * @param hd the head pointer
 * @param mname the name of the member of the struct which contains
 * the list node
 */
#define list_foreach_item_rev(cp, hd, mname)                \
  for (cp = list_item((hd)->prev, typeof(*cp), mname);      \
       &cp->mname != (hd);                                  \
       cp = list_item(cp->mname.prev, typeof(*cp), mname))

#endif