circularlist.h

/*
 * Copyright (c) 2018-2021 Heng Yuan
 *
 * Licensed under the Apache License, Version 2.0 (the "License");
 * you may not use this file except in compliance with the License.
 * You may obtain a copy of the License at
 *
 *     http://www.apache.org/licenses/LICENSE-2.0
 *
 * Unless required by applicable law or agreed to in writing, software
 * distributed under the License is distributed on an "AS IS" BASIS,
 * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
 * See the License for the specific language governing permissions and
 * limitations under the License.
 */
#ifndef COOK_MEM_CIRCULAR_LIST_H
#define COOK_MEM_CIRCULAR_LIST_H
 
#include "exception.h"
 
namespace cookmem
{
 
template<class Node>
class CircularList
{
public:
    CircularList () : m_head (nullptr) {}
 
    void
    add (Node* ptr)
    {
        if (m_head)
        {
            Node* curr = m_head;
            Node* next = m_head->next;
            curr->next = ptr;
            next->prev = ptr;
            ptr->next = next;
            ptr->prev = curr;
        }
        else
        {
            ptr->next = ptr;
            ptr->prev = ptr;
            m_head = ptr;
        }
    }
 
    Node*
    remove ()
    {
        if (m_head == nullptr)
        {
            return nullptr;
        }
 
        Node* prev = m_head->prev;
        Node* next = m_head->next;
        Node* head = m_head;
 
        if (m_head == prev)
        {
            COOKMEM_ASSERT(m_head == next);
            m_head = nullptr;
        }
        else
        {
            prev->next = next;
            next->prev = prev;
            m_head = next;
        }
 
        return head;
    }
 
    bool
    remove (Node* chunk)
    {
        Node* prev = chunk->prev;
        Node* next = chunk->next;
 
        if (prev == chunk)
        {
            COOKMEM_ASSERT(m_head == chunk && next == chunk);
            m_head = nullptr;
            return true;
        }
        else
        {
            if (m_head == chunk)
            {
                m_head = next;
            }
            prev->next = next;
            next->prev = prev;
            return false;
        }
    }
 
    bool
    contains (Node* chunk)
    {
        if (m_head == nullptr)
        {
            return false;
        }
        Node* node = m_head;
        do
        {
            if (node == chunk)
            {
                return true;
            }
            node = node->next;
        }
        while (node != m_head);
        return false;
    }
 
    bool isEmpty () const { return m_head == nullptr; }
 
private:
    Node*   m_head;
};
 
}   // namespace cookmem
 
#endif  // COOK_MEM_CIRCULAR_LIST_H