/*
* 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 <code>true</code> 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 <code>true</code> 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