/*

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

 */

#ifndef RING_NODE_H

#define RING_NODE_H

#include "types.h"

/**

 * A ring node is a member of a doubly-linked circular list.

 *

 * Each node is usually embedded within a data structure that contains the

 * relevant payload. In addition the ring head is also represented by a

 * node where the next field designates the first element of the ring and the

 * prev field designates the last.

 *

 * An empty ring contains next and prev fields that point back to the ring

 * head itself.

 *

 * Typical iteration over a ring, from the front and back:

 *

 * for (RingNode *n = head->next; n != head; n = n->next) { ... }

 * for (RingNode *p = head->prev; p != head; p = p->prev) { ... }

 **/

typedef struct ringNode RingNode;

struct ringNode {

  RingNode *next;

  RingNode *prev;

};

/**

 * Initialize a ring to be empty.

 *

 * @param head The head of the ring

 **/

static inline void initializeRing(RingNode *head)

{

  head->next = head->prev = head;

}

/**

 * Check whether a ring is empty.

 *

 * @param head The head of the ring

 *

 * @return true if the ring is empty

 **/

static inline bool isRingEmpty(const RingNode *head)

{

  return (head->next == head);

}

/**

 * Check whether a ring contains exactly one node.

 *

 * @param head  The head of the ring

 *

 * @return true if the ring contains exactly one member

 **/

static inline bool isRingSingleton(const RingNode *head)

{

  return (!isRingEmpty(head) && (head->prev == head->next));

}

/**

 * Unsplice a contiguous chain of at least one node from its ring.

 *

 * @param first         the first entry in the ring to unsplice

 * @param last          the last entry in the ring to unsplice,

 *                      may be the same as ``first``

 *

 * The effect of this is to create two rings, the one designated

 * by first through last, and the other consisting of anything remaining.

 **/

static inline void unspliceRingChain(RingNode *first,

                                     RingNode *last)

{

  first->prev->next = last->next;

  last->next->prev = first->prev;

  first->prev = last;

  last->next = first;

}

/**

 * Remove a ring node from its ring.

 *

 * @param node  the ring node

 *

 * @return the removed node, for convenience

 **/

static inline RingNode *unspliceRingNode(RingNode *node)

{

  unspliceRingChain(node, node);

  return node;

}

/**

 * Splice a contiguous chain of at least one node after the specified entry,

 * which may be the head of a ring.

 *

 * @param first         the first entry in a contiguous span of nodes

 * @param last          the last entry in a contiguous span of nodes,

 *                      may be the same as ``first``

 * @param where         the entry after which ``first`` through ``last``

 *                      shall appear

 *

 * The effect of this is to unsplice first through last (if necessary) and

 * insert them after ``where`` so that the previous nodes after ``where``

 * now appear after ``last``.

 **/

static inline void spliceRingChainAfter(RingNode *first,

                                        RingNode *last,

                                        RingNode *where)

{

  if (last->next != first) {

    unspliceRingChain(first, last);

  }

  last->next = where->next;

  first->prev = where;

  where->next->prev = last;

  where->next = first;

}

/**

 * Splice a contiguous chain of at least one node before the specified entry,

 * which may be the tail of a list.

 *

 * @param first         the first entry in a contiguous span of nodes

 * @param last          the last entry in a contiguous span of nodes,

 *                      may be the same as ``first``

 * @param where         the entry before which ``first`` through ``last``

 *                      shall appear

 *

 * The effect of this is to unsplice first through last (if necessary) and

 * insert them before ``where`` so that the previous nodes before ``where``

 * now appear before ``first``.

 **/

static inline void spliceRingChainBefore(RingNode *first,

                                         RingNode *last,

                                         RingNode *where)

{

  if (last->next != first) {

    unspliceRingChain(first, last);

  }

  first->prev = where->prev;

  last->next = where;

  where->prev->next = first;

  where->prev = last;

}

/**

 * Push a single node on the end of a ring.

 *

 * @param head The ring head

 * @param node The node to push

 **/

static inline void pushRingNode(RingNode *head, RingNode *node)

{

  spliceRingChainBefore(node, node, head);

}

/**

 * Pop a single node off the end of a ring.

 *

 * @param head  The ring head

 *

 * @return NULL if the ring was empty, otherwise the node that was

 *         removed from the ring (``head->prev``)

 **/

static inline RingNode *popRingNode(RingNode *head)

{

  return (isRingEmpty(head) ? NULL : unspliceRingNode(head->prev));

}

/**

 * Remove a single node off the front of the list

 **/

static inline RingNode *chopRingNode(RingNode *head)

{

  return (isRingEmpty(head) ? NULL : unspliceRingNode(head->next));

}

#endif // RING_NODE_H