LinkedList.h
// LinkedList.h
//
// Author David Barrett-Lennard
// (C)opyright Cedanet Pty Ltd 2004
#pragma once
#ifndef Ceda_cxUtils_LinkedList_H
#define Ceda_cxUtils_LinkedList_H
#include "CedaAssert.h"
#include "cxUtils.h"
namespace ceda
{
///////////////////////////////////////////////////////////////////////////////////////////////////
// LinkedList<T>
/*
An alternative to the std::list<> that seems more appropriate in a number of circumstances.
Example
-------
Suppose we require a doubly linked list of 64k buffers which we will call "pages". Let these be
evicted using an LRU algorithm.
Consider an implementation using an std::list<Page>, where
const ssize_t PAGE_SIZE = 64 * 1024;
struct Page : public xvector<char>
{
Page() : xvector<char>(PAGE_SIZE) {}
};
Page is an xvector<char> used to represent a 64k block. When the list destructs it will delete
all the memory for us. However there is a serious deficiency. To make the std::list<Page> grow,
we call push_back(const Page& page). Unfortunately this makes a copy of the 64k page! This is
unreasonable because a page is expensive to copy.
Therefore we use std::list<Page*>. However this now means we get three heap allocations per page!
One for the internal node allocated by the std::list, one for the Page object, and one for the 64k
buffer (assuming we use a xvector<char> to implement a Page. Furthermore, we now need to make
sure we explicitly delete the pages that are no longer in use.
We can avoid one of the heap allocations by avoiding the use of the xvector<char> to implement a
Page object, and instead we use an std::list<Page*> where
struct Page { char m_buffer[PAGE_SIZE]; }
Nevertheless, this approach involves two heap allocations per page.
The list is ordered by access to the pages. Each time a page is accessed it needs to be moved
from its current position to the back of the list for the LRU evicition policy. Unfortunately given
a pointer to a Page there is no fast way to get an iterator to the Page (needed for a call to erase).
It is necessary to iterate through the list each time a page is accessed!
A LinkedList<Page> offers a superior solution for this problem. We define Page as follows
struct Page : public LinkedList<Page>::NodeBase { char m_buffer[PAGE_SIZE]; }
Note that we inherit the pointers to the previous and next pages in the doubly linked list.
The LinkedList<Page> has the following advantages
* The LinkedList will automatically delete the pages (allocated on the heap) for us
when it destructs
* There are only as many heap allocations as pages
* A page can be removed very quickly from the list without the need for a linear scan, making it
ideal for implementing an LRU eviction policy.
*/
template <typename T> // Is is assumed that T inherits from LinkedList<T>::NodeBase
class LinkedList
{
public:
struct NodeBase
{
NodeBase() : prev_(nullptr), next_(nullptr) {}
NodeBase(const NodeBase& other) : prev_(nullptr), next_(nullptr) {}
NodeBase& operator=(const NodeBase& other)
{
if (this != &other)
{
prev_ = nullptr;
next_ = nullptr;
}
return *this;
}
T* prev_;
T* next_;
};
LinkedList() : first_(nullptr), last_(nullptr), size_(0) {}
~LinkedList() { Clear(); }
void Clear()
{
T* p = first_;
while(p)
{
T* q = p->next_;
delete p;
p = q;
}
first_ = nullptr;
last_ = nullptr;
size_ = 0;
}
ssize_t GetSize() const { return size_; }
bool IsEmpty() const { return size_ == 0; }
// Returns true if the given node is an element of this list
bool HasElement(const T* node) const
{
cxAssert(node);
const T* p = first_;
while(p)
{
if (p == node) return true;
p = p->next_;
}
return false;
}
// Remove the given node from this list. The given node is not deleted by this function.
void Remove(T* p)
{
cxAssert(p);
// cxAssert(HasElement(p)); // slows down debug build too much to assert this
if (p->prev_)
{
cxAssert(p->prev_->next_ == p);
p->prev_->next_ = p->next_;
}
else
{
cxAssert(first_ == p);
first_ = p->next_;
}
if (p->next_)
{
cxAssert(p->next_->prev_ == p);
p->next_->prev_ = p->prev_;
}
else
{
cxAssert(last_ == p);
last_ = p->prev_;
}
p->prev_ = nullptr;
p->next_ = nullptr;
--size_;
}
void Erase(T* p)
{
Remove(p);
delete p;
}
// It is an error to call this function if the list is empty. The node at the front of the
// list is removed but not deleted by this function.
T* RemoveFront()
{
cxAssert(first_);
cxAssert(last_);
T* p = first_;
if (first_ == last_)
{
cxAssert(size_ == 1);
first_ = last_ = nullptr;
}
else
{
cxAssert(size_ > 1);
first_ = first_->next_;
cxAssert(first_);
first_->prev_ = nullptr;
}
p->prev_ = nullptr;
p->next_ = nullptr;
--size_;
return p;
}
void PopFront()
{
delete RemoveFront();
}
// It is an error to call this function if the list is empty. The node at the front of the
// list is removed but not deleted by this function.
T* RemoveBack()
{
cxAssert(first_);
cxAssert(last_);
T* p = last_;
if (first_ == last_)
{
cxAssert(size_ == 1);
first_ = last_ = nullptr;
}
else
{
cxAssert(size_ > 1);
last_ = last_->prev_;
cxAssert(last_);
last_->next_ = nullptr;
}
p->prev_ = nullptr;
p->next_ = nullptr;
--size_;
return p;
}
void PopBack()
{
delete RemoveBack();
}
// The given node must have been allocated on the heap. This linked list takes ownership of
// the given node
void PushBack(T* p)
{
cxAssert(p);
cxAssert(p->prev_ == nullptr);
cxAssert(p->next_ == nullptr);
if (last_)
{
cxAssert(last_ != p);
cxAssert(first_);
cxAssert(last_->next_ == nullptr);
last_->next_ = p;
p->prev_ = last_;
}
else
{
cxAssert(first_ == nullptr);
first_ = p;
}
last_ = p;
++size_;
}
// The given node must have been allocated on the heap. This linked list takes ownership of
// the given node
void PushFront(T* p)
{
cxAssert(p);
cxAssert(p->prev_ == nullptr);
cxAssert(p->next_ == nullptr);
if (first_)
{
cxAssert(first_ != p);
cxAssert(last_);
cxAssert(first_->prev_ == nullptr);
first_->prev_ = p;
p->next_ = first_;
}
else
{
cxAssert(last_ == nullptr);
last_ = p;
}
first_ = p;
++size_;
}
class const_iterator
{
public:
const_iterator(T* node) : node_(node) {}
operator const T*() const { return node_; }
const T& operator*() const { cxAssert(node_); return *node_; }
const T* operator->() const { cxAssert(node_); return node_; }
const_iterator& operator++() { cxAssert(node_); node_ = node_->next_; return *this; }
const const_iterator operator++(int) { const_iterator it = *this; ++(*this); return it; }
const_iterator& operator--() { cxAssert(node_); node_ = node_->prev_; return *this; }
const const_iterator operator--(int) { const_iterator it = *this; --(*this); return it; }
bool operator==(const const_iterator& other) const { return node_ == other.node_; }
bool operator!=(const const_iterator& other) const { return node_ != other.node_; }
protected:
T* node_;
};
class iterator : public const_iterator
{
public:
iterator(T* node) : const_iterator(node) {}
operator T*() const { return node_; }
T& operator*() const { cxAssert(node_); return *node_; }
T* operator->() const { cxAssert(node_); return node_; }
iterator& operator++() { cxAssert(node_); node_ = node_->next_; return *this; }
const iterator operator++(int) { iterator it = *this; ++(*this); return it; }
iterator& operator--() { cxAssert(node_); node_ = node_->prev_; return *this; }
const iterator operator--(int) { iterator it = *this; --(*this); return it; }
};
// Insert node p immediately before the given position
void InsertBefore(iterator pos, T* p)
{
cxAssert(p);
cxAssert(p->prev_ == nullptr);
cxAssert(p->next_ == nullptr);
if ((T*)pos)
{
// cxAssert(HasElement(pos)); // slows down debug build too much to assert this
p->prev_ = pos->prev_;
p->next_ = pos;
if (pos->prev_)
{
cxAssert(pos->prev_->next_ == pos);
pos->prev_->next_ = p;
}
else
{
cxAssert(first_ == pos);
first_ = p;
}
pos->prev_ = p;
++size_;
}
else
{
PushBack(p);
}
}
const_iterator begin() const { return const_iterator(first_); }
const_iterator end() const { return const_iterator(nullptr); }
iterator begin() { return iterator(first_); }
iterator end() { return iterator(nullptr); }
T* GetFirst() const { return first_; }
T* GetLast() const { return last_; }
private:
T* first_;
T* last_;
ssize_t size_;
};
} // namespace ceda
#endif // include guard