List.h

/*
 * Copyright (c) 2008-2014, Pedigree Developers
 *
 * Please see the CONTRIB file in the root of the source tree for a full
 * list of contributors.
 *
 * Permission to use, copy, modify, and distribute this software for any
 * purpose with or without fee is hereby granted, provided that the above
 * copyright notice and this permission notice appear in all copies.
 *
 * THE SOFTWARE IS PROVIDED "AS IS" AND THE AUTHOR DISCLAIMS ALL WARRANTIES
 * WITH REGARD TO THIS SOFTWARE INCLUDING ALL IMPLIED WARRANTIES OF
 * MERCHANTABILITY AND FITNESS. IN NO EVENT SHALL THE AUTHOR BE LIABLE FOR
 * ANY SPECIAL, DIRECT, INDIRECT, OR CONSEQUENTIAL DAMAGES OR ANY DAMAGES
 * WHATSOEVER RESULTING FROM LOSS OF USE, DATA OR PROFITS, WHETHER IN AN
 * ACTION OF CONTRACT, NEGLIGENCE OR OTHER TORTIOUS ACTION, ARISING OUT OF
 * OR IN CONNECTION WITH THE USE OR PERFORMANCE OF THIS SOFTWARE.
 */
 
#ifndef KERNEL_UTILITIES_LIST_H
#define KERNEL_UTILITIES_LIST_H
 
#include "pedigree/kernel/compiler.h"
#include "pedigree/kernel/processor/types.h"
#include "pedigree/kernel/utilities/Iterator.h"
#include "pedigree/kernel/utilities/ObjectPool.h"
#include "pedigree/kernel/utilities/assert.h"
#include "pedigree/kernel/utilities/utility.h"
 
template <typename T>
struct _ListNode_t {
  // static_assert(sizeof(T) <= 16, "List<T> should not be used with large
  // objects");
 
  _ListNode_t* next() {
    return m_Next;
  }
  _ListNode_t* previous() {
    return m_Previous;
  }
 
  _ListNode_t* m_Next;
  _ListNode_t* m_Previous;
  T value;
};
 
template <class T, size_t nodePoolSize = 16>
class EXPORTED_PUBLIC List {
  typedef _ListNode_t<T> node_t;
 
 public:
  typedef ::Iterator<T, node_t> Iterator;
  typedef typename Iterator::Const ConstIterator;
  typedef typename Iterator::Reverse ReverseIterator;
  typedef typename Iterator::ConstReverse ConstReverseIterator;
 
  List();
  List(const List& x);
  ~List();
 
  List& operator=(const List& x);
 
  size_t size() const;
  size_t count() const;
  void pushBack(const T& value);
  void pushBack(T&& value);
  bool tryPushBack(const T& value);
  bool tryPushBack(T&& value);
  T popBack();
  void pushFront(const T& value);
  void pushFront(T&& value);
  T popFront();
  Iterator erase(Iterator& Iter);
  ReverseIterator erase(ReverseIterator& Iter);
 
  inline Iterator begin() {
    return Iterator(m_First);
  }
  inline ConstIterator begin() const {
    return ConstIterator(m_First);
  }
  inline Iterator end() {
    return Iterator(0);
  }
  inline ConstIterator end() const {
    return ConstIterator(0);
  }
  inline ReverseIterator rbegin() {
    return ReverseIterator(m_Last);
  }
  inline ConstReverseIterator rbegin() const {
    return ConstReverseIterator(m_Last);
  }
  inline ReverseIterator rend() {
    return ReverseIterator(0);
  }
  inline ConstReverseIterator rend() const {
    return ConstReverseIterator(0);
  }
 
  void clear();
  void assign(const List& x);
 
 private:
  size_t m_Count;
  node_t* m_First;
  node_t* m_Last;
 
  uint32_t m_Magic;
 
  ObjectPool<node_t, nodePoolSize> m_NodePool;
};
 
//
// List<T> implementation
//
 
template <typename T, size_t nodePoolSize>
List<T, nodePoolSize>::List()
    : m_Count(0), m_First(0), m_Last(0), m_Magic(0x1BADB002), m_NodePool() {}
 
template <typename T, size_t nodePoolSize>
List<T, nodePoolSize>::List(const List& x)
    : m_Count(0), m_First(0), m_Last(0), m_Magic(0x1BADB002), m_NodePool() {
  assign(x);
}
template <typename T, size_t nodePoolSize>
List<T, nodePoolSize>::~List() {
  assert(m_Magic == 0x1BADB002);
  clear();
}
 
template <typename T, size_t nodePoolSize>
List<T, nodePoolSize>& List<T, nodePoolSize>::operator=(const List& x) {
  assign(x);
  return *this;
}
 
template <typename T, size_t nodePoolSize>
size_t List<T, nodePoolSize>::size() const {
  return m_Count;
}
template <typename T, size_t nodePoolSize>
size_t List<T, nodePoolSize>::count() const {
  return m_Count;
}
template <typename T, size_t nodePoolSize>
void List<T, nodePoolSize>::pushBack(const T& value) {
  node_t* newNode = m_NodePool.allocate();
  newNode->m_Next = 0;
  newNode->m_Previous = m_Last;
  newNode->value = value;
 
  if (m_Last == 0)
    m_First = newNode;
  else
    m_Last->m_Next = newNode;
 
  m_Last = newNode;
  ++m_Count;
}
template <typename T, size_t nodePoolSize>
void List<T, nodePoolSize>::pushBack(T&& value) {
  node_t* newNode = m_NodePool.allocate();
  newNode->m_Next = 0;
  newNode->m_Previous = m_Last;
  newNode->value = pedigree_std::move(value);
 
  if (m_Last == 0)
    m_First = newNode;
  else
    m_Last->m_Next = newNode;
 
  m_Last = newNode;
  ++m_Count;
}
template <typename T, size_t nodePoolSize>
bool List<T, nodePoolSize>::tryPushBack(const T& value) {
  node_t* newNode = m_NodePool.tryAllocate();
  if (!newNode)
    return false;
  newNode->m_Next = nullptr;
  newNode->m_Previous = m_Last;
  newNode->value = value;
  if (m_Last)
    m_Last->m_Next = newNode;
  else
    m_First = newNode;
  m_Last = newNode;
  ++m_Count;
  return true;
}
template <typename T, size_t nodePoolSize>
bool List<T, nodePoolSize>::tryPushBack(T&& value) {
  node_t* newNode = m_NodePool.tryAllocate();
  if (!newNode)
    return false;
  newNode->m_Next = nullptr;
  newNode->m_Previous = m_Last;
  newNode->value = pedigree_std::move(value);
  if (m_Last)
    m_Last->m_Next = newNode;
  else
    m_First = newNode;
  m_Last = newNode;
  ++m_Count;
  return true;
}
template <typename T, size_t nodePoolSize>
T List<T, nodePoolSize>::popBack() {
  // Handle an extremely unusual case
  if (!m_Last && !m_First)
    return T();
 
  node_t* node = m_Last;
  if (m_Last)
    m_Last = m_Last->m_Previous;
  if (m_Last != 0)
    m_Last->m_Next = 0;
  else
    m_First = 0;
  --m_Count;
 
  if (!node)
    return T();
 
  T value = node->value;
  m_NodePool.deallocate(node);
  return value;
}
template <typename T, size_t nodePoolSize>
void List<T, nodePoolSize>::pushFront(const T& value) {
  node_t* newNode = m_NodePool.allocate();
  newNode->m_Next = m_First;
  newNode->m_Previous = 0;
  newNode->value = value;
 
  if (m_First == 0)
    m_Last = newNode;
  else
    m_First->m_Previous = newNode;
 
  m_First = newNode;
  ++m_Count;
}
template <typename T, size_t nodePoolSize>
void List<T, nodePoolSize>::pushFront(T&& value) {
  node_t* newNode = m_NodePool.allocate();
  newNode->m_Next = m_First;
  newNode->m_Previous = 0;
  newNode->value = pedigree_std::move(value);
 
  if (m_First == 0)
    m_Last = newNode;
  else
    m_First->m_Previous = newNode;
 
  m_First = newNode;
  ++m_Count;
}
template <typename T, size_t nodePoolSize>
T List<T, nodePoolSize>::popFront() {
  // Handle an extremely unusual case
  if (!m_Last && !m_First)
    return T();
 
  node_t* node = m_First;
  if (m_First)
    m_First = m_First->m_Next;
  if (m_First != 0)
    m_First->m_Previous = 0;
  else
    m_Last = 0;
  --m_Count;
 
  if (!node)
    return T();
 
  T value = node->value;
  m_NodePool.deallocate(node);
  return value;
}
template <typename T, size_t nodePoolSize>
typename List<T, nodePoolSize>::Iterator List<T, nodePoolSize>::erase(Iterator& Iter) {
  node_t* Node = Iter.__getNode();
  if (!Node)
    return end();
 
  if (Node->m_Previous == 0)
    m_First = Node->m_Next;
  else
    Node->m_Previous->m_Next = Node->m_Next;
  if (Node->m_Next == 0)
    m_Last = Node->m_Previous;
  else
    Node->m_Next->m_Previous = Node->m_Previous;
  --m_Count;
 
  node_t* pNext = Node->m_Next;
  // If pNext is NULL, this will be the same as 'end()'.
  Iterator tmp(pNext);
  m_NodePool.deallocate(Node);
  return tmp;
}
 
template <typename T, size_t nodePoolSize>
typename List<T, nodePoolSize>::ReverseIterator List<T, nodePoolSize>::erase(
    ReverseIterator& Iter) {
  node_t* Node = Iter.__getNode();
  if (!Node)
    return rend();
 
  if (Node->m_Previous == 0)
    m_First = Node->m_Next;
  else
    Node->m_Previous->m_Next = Node->m_Next;
  if (Node->m_Next == 0)
    m_Last = Node->m_Previous;
  else
    Node->m_Next->m_Previous = Node->m_Previous;
  --m_Count;
 
  node_t* pNext = Node->m_Previous;
  // If pNext is NULL, this will be the same as 'rend()'.
  ReverseIterator tmp(pNext);
  m_NodePool.deallocate(Node);
  return tmp;
}
 
template <typename T, size_t nodePoolSize>
void List<T, nodePoolSize>::clear() {
  node_t* cur = m_First;
  for (size_t i = 0; i < m_Count; i++) {
    node_t* tmp = cur;
    cur = cur->m_Next;
    m_NodePool.deallocate(tmp);
  }
 
  m_Count = 0;
  m_First = 0;
  m_Last = 0;
}
template <typename T, size_t nodePoolSize>
void List<T, nodePoolSize>::assign(const List& x) {
  if (this == &x)
    return;
 
  if (m_Count != 0)
    clear();
 
  ConstIterator Cur(x.begin());
  ConstIterator End(x.end());
  for (; Cur != End; ++Cur)
    pushBack(*Cur);
}
 
extern template class List<void*>;     // IWYU pragma: keep
extern template class List<uint64_t>;  // IWYU pragma: keep
extern template class List<uint32_t>;  // IWYU pragma: keep
extern template class List<uint16_t>;  // IWYU pragma: keep
extern template class List<uint8_t>;   // IWYU pragma: keep
extern template class List<int64_t>;   // IWYU pragma: keep
extern template class List<int32_t>;   // IWYU pragma: keep
extern template class List<int16_t>;   // IWYU pragma: keep
extern template class List<int8_t>;    // IWYU pragma: keep
 
#endif