IntrusiveList.cpp

#include <cstdlib>
#include <cassert>
#include "IntrusiveList.h"
 
namespace {
 
 
  size_t count(Cogs::IntrusiveList* list)
  {
 
    size_t n = 0;
    for(auto * item : *list) {
      (void)item;
//    for (auto item = list->head; item != (Cogs::IntrusiveNode*)&list->tail; item = item->next) {
      n++;
    }
    return n;
  }
 
}
 
 
Cogs::IntrusiveList::IntrusiveList()
{
  head = (IntrusiveNode*)&tail;
  tail = nullptr;
  tailPrev = (IntrusiveNode*)&head;
 
  assert(count(this) == 0);
}
 
bool Cogs::IntrusiveList::empty() const
{
  return tailPrev == (IntrusiveNode*)&head;
}
 
void Cogs::IntrusiveList::pushFront(IntrusiveNode* node)
{
  assert(node->next == nullptr);
  assert(node->prev == nullptr);
 
  auto n = count(this);
 
  node->next = head;
  node->prev = (IntrusiveNode*)&head;
  head->prev = node;
  head = node;
 
  auto m = count(this);
  assert(n + 1 == m);
 
  assert(head->prev != nullptr);
  assert(tailPrev != (IntrusiveNode*)&head);
}
 
void Cogs::IntrusiveList::pushBack(IntrusiveNode* node)
{
  assert(node->next == nullptr);
  assert(node->prev == nullptr);
 
  auto n = count(this);
 
  node->next = (IntrusiveNode*)&tail;
  node->prev = tailPrev;
  tailPrev->next = node;
  tailPrev = node;
 
  auto m = count(this);
  assert(n + 1 == m);
 
  assert(head->prev != nullptr);
  assert(tailPrev != (IntrusiveNode*)&head);
}
 
void Cogs::IntrusiveList::insert(IntrusiveNode* prev, IntrusiveNode* node)
{
  assert(prev->next);
  assert(prev->prev);
  assert(node->next == nullptr);
  assert(node->prev == nullptr);
  assert(head->prev != nullptr && "List is empty");
  assert(tailPrev != (IntrusiveNode*)&head && "List is empty");
 
  auto n = count(this);
 
  if (prev->next) {
    node->next = prev->next;
    node->prev = prev;
    prev->next->prev = node;
    prev->next = node;
  }
  else {  // tail node
    node->next = (IntrusiveNode*)&tail;
    node->prev = tailPrev;
    tailPrev->next = node;
    tailPrev = node;
  }
 
  auto m = count(this);
  assert(n + 1 == m);
 
  assert(head->prev != nullptr);
  assert(tailPrev != (IntrusiveNode*)&head);
}
 
Cogs::IntrusiveNode* Cogs::IntrusiveList::popFront()
{
  IntrusiveNode* node = head->next;
  if (node) {
 
    auto n = count(this);
 
    node->prev = (IntrusiveNode*)&head;
    node = head;
    head = node->next;
 
    node->next = nullptr;
    node->prev = nullptr;
 
    auto m = count(this);
    assert(n == m + 1);
  }
  return node;
}
 
Cogs::IntrusiveNode* Cogs::IntrusiveList::back()
{
  if (tailPrev != (IntrusiveNode*)&head) {
    return tailPrev;
  }
  else {
    return nullptr;
  }
}
 
void Cogs::IntrusiveList::remove(IntrusiveNode* node)
{
  assert(node);
 
  auto n = count(this);
 
  node->prev->next = node->next;
  node->next->prev = node->prev;
  node->next = nullptr;
  node->prev = nullptr;
 
  auto m = count(this);
  assert(n == m + 1);
}
 
Cogs::IntrusiveNode* Cogs::IntrusiveList::IntrusiveList::popBack()
{
  IntrusiveNode* node = back();
  if (node) {
    remove(node);
  }
  return node;
}