545 lines
16 KiB
C++
545 lines
16 KiB
C++
//========= Copyright Valve Corporation, All rights reserved. ============//
|
|
//
|
|
// Purpose: N-way tree container class
|
|
//
|
|
// $Revision: $
|
|
// $NoKeywords: $
|
|
//=============================================================================//
|
|
|
|
#ifndef UTLNTREE_H
|
|
#define UTLNTREE_H
|
|
|
|
#ifdef _WIN32
|
|
#pragma once
|
|
#endif
|
|
|
|
#include "basetypes.h"
|
|
#include "tier0/dbg.h"
|
|
#include "utlmemory.h"
|
|
|
|
#define INVALID_NTREE_IDX ((I)~0)
|
|
|
|
//-----------------------------------------------------------------------------
|
|
// class CUtlNTree:
|
|
// description:
|
|
// A lovely index-based linked list! T is the class type, I is the
|
|
//index type, which usually should be an unsigned short or smaller.
|
|
//-----------------------------------------------------------------------------
|
|
template <class T, class I = unsigned short>
|
|
class CUtlNTree {
|
|
public:
|
|
typedef T ElemType_t;
|
|
typedef I IndexType_t;
|
|
|
|
// constructor, destructor
|
|
CUtlNTree(int growSize = 0, int initSize = 0);
|
|
CUtlNTree(void* pMemory, int memsize);
|
|
~CUtlNTree();
|
|
|
|
// gets particular elements
|
|
T& Element(I i);
|
|
const T& Element(I i) const;
|
|
T& operator[](I i);
|
|
const T& operator[](I i) const;
|
|
|
|
// Make sure we have a particular amount of memory
|
|
void EnsureCapacity(int num);
|
|
|
|
// Clears the tree, doesn't deallocate memory
|
|
void RemoveAll();
|
|
|
|
// Memory deallocation
|
|
void Purge();
|
|
|
|
// Allocation/deallocation methods
|
|
I Alloc();
|
|
void Free(I elem);
|
|
void FreeSubTree(I elem);
|
|
|
|
// list modification
|
|
void SetRoot(I root);
|
|
void LinkChildBefore(I parent, I before, I elem);
|
|
void LinkChildAfter(I parent, I after, I elem);
|
|
void Unlink(I elem);
|
|
|
|
// Alloc + link combined
|
|
I InsertChildBefore(I parent, I before);
|
|
I InsertChildAfter(I parent, I after);
|
|
I InsertChildBefore(I parent, I before, const T& elem);
|
|
I InsertChildAfter(I parent, I after, const T& elem);
|
|
|
|
// Unlink + free combined
|
|
void Remove(I elem);
|
|
void RemoveSubTree(I elem);
|
|
|
|
// invalid index
|
|
inline static I InvalidIndex() { return INVALID_NTREE_IDX; }
|
|
inline static size_t ElementSize() { return sizeof(Node_t); }
|
|
|
|
// list statistics
|
|
int Count() const;
|
|
I MaxElementIndex() const;
|
|
|
|
// Traversing the list
|
|
I Root() const;
|
|
I FirstChild(I i) const;
|
|
I PrevSibling(I i) const;
|
|
I NextSibling(I i) const;
|
|
I Parent(I i) const;
|
|
|
|
// Are nodes in the list or valid?
|
|
bool IsValidIndex(I i) const;
|
|
bool IsInTree(I i) const;
|
|
|
|
protected:
|
|
// What the linked list element looks like
|
|
struct Node_t {
|
|
T m_Element;
|
|
I m_Parent;
|
|
I m_FirstChild;
|
|
I m_PrevSibling;
|
|
I m_NextSibling;
|
|
|
|
private:
|
|
// No copy constructor for these...
|
|
Node_t(const Node_t&);
|
|
};
|
|
|
|
// constructs the class
|
|
void ConstructList();
|
|
|
|
// Allocates the element, doesn't call the constructor
|
|
I AllocInternal();
|
|
|
|
// Gets at the node element....
|
|
Node_t& InternalNode(I i) { return m_Memory[i]; }
|
|
const Node_t& InternalNode(I i) const { return m_Memory[i]; }
|
|
|
|
void ResetDbgInfo() { m_pElements = m_Memory.Base(); }
|
|
|
|
// copy constructors not allowed
|
|
CUtlNTree(CUtlNTree<T, I> const& tree) { Assert(0); }
|
|
|
|
CUtlMemory<Node_t> m_Memory;
|
|
I m_Root;
|
|
I m_FirstFree;
|
|
I m_ElementCount; // The number actually in the tree
|
|
I m_MaxElementIndex; // The max index we've ever assigned
|
|
|
|
// For debugging purposes;
|
|
// it's in release builds so this can be used in libraries correctly
|
|
Node_t* m_pElements;
|
|
};
|
|
|
|
//-----------------------------------------------------------------------------
|
|
// constructor, destructor
|
|
//-----------------------------------------------------------------------------
|
|
|
|
template <class T, class I>
|
|
CUtlNTree<T, I>::CUtlNTree(int growSize, int initSize)
|
|
: m_Memory(growSize, initSize) {
|
|
ConstructList();
|
|
ResetDbgInfo();
|
|
}
|
|
|
|
template <class T, class I>
|
|
CUtlNTree<T, I>::CUtlNTree(void* pMemory, int memsize)
|
|
: m_Memory(pMemory, memsize / sizeof(T)) {
|
|
ConstructList();
|
|
ResetDbgInfo();
|
|
}
|
|
|
|
template <class T, class I>
|
|
CUtlNTree<T, I>::~CUtlNTree() {
|
|
RemoveAll();
|
|
}
|
|
|
|
template <class T, class I>
|
|
void CUtlNTree<T, I>::ConstructList() {
|
|
m_Root = InvalidIndex();
|
|
m_FirstFree = InvalidIndex();
|
|
m_ElementCount = m_MaxElementIndex = 0;
|
|
}
|
|
|
|
//-----------------------------------------------------------------------------
|
|
// gets particular elements
|
|
//-----------------------------------------------------------------------------
|
|
template <class T, class I>
|
|
inline T& CUtlNTree<T, I>::Element(I i) {
|
|
return m_Memory[i].m_Element;
|
|
}
|
|
|
|
template <class T, class I>
|
|
inline const T& CUtlNTree<T, I>::Element(I i) const {
|
|
return m_Memory[i].m_Element;
|
|
}
|
|
|
|
template <class T, class I>
|
|
inline T& CUtlNTree<T, I>::operator[](I i) {
|
|
return m_Memory[i].m_Element;
|
|
}
|
|
|
|
template <class T, class I>
|
|
inline const T& CUtlNTree<T, I>::operator[](I i) const {
|
|
return m_Memory[i].m_Element;
|
|
}
|
|
|
|
//-----------------------------------------------------------------------------
|
|
// list statistics
|
|
//-----------------------------------------------------------------------------
|
|
template <class T, class I>
|
|
inline int CUtlNTree<T, I>::Count() const {
|
|
return m_ElementCount;
|
|
}
|
|
|
|
template <class T, class I>
|
|
inline I CUtlNTree<T, I>::MaxElementIndex() const {
|
|
return m_MaxElementIndex;
|
|
}
|
|
|
|
//-----------------------------------------------------------------------------
|
|
// Traversing the list
|
|
//-----------------------------------------------------------------------------
|
|
template <class T, class I>
|
|
inline I CUtlNTree<T, I>::Root() const {
|
|
return m_Root;
|
|
}
|
|
|
|
template <class T, class I>
|
|
inline I CUtlNTree<T, I>::FirstChild(I i) const {
|
|
Assert(IsInTree(i));
|
|
return InternalNode(i).m_FirstChild;
|
|
}
|
|
|
|
template <class T, class I>
|
|
inline I CUtlNTree<T, I>::PrevSibling(I i) const {
|
|
Assert(IsInTree(i));
|
|
return InternalNode(i).m_PrevSibling;
|
|
}
|
|
|
|
template <class T, class I>
|
|
inline I CUtlNTree<T, I>::NextSibling(I i) const {
|
|
Assert(IsInTree(i));
|
|
return InternalNode(i).m_NextSibling;
|
|
}
|
|
|
|
template <class T, class I>
|
|
inline I CUtlNTree<T, I>::Parent(I i) const {
|
|
Assert(IsInTree(i));
|
|
return InternalNode(i).m_Parent;
|
|
}
|
|
|
|
//-----------------------------------------------------------------------------
|
|
// Are nodes in the list or valid?
|
|
//-----------------------------------------------------------------------------
|
|
template <class T, class I>
|
|
inline bool CUtlNTree<T, I>::IsValidIndex(I i) const {
|
|
return (i < m_MaxElementIndex) && (i >= 0);
|
|
}
|
|
|
|
template <class T, class I>
|
|
inline bool CUtlNTree<T, I>::IsInTree(I i) const {
|
|
return (i < m_MaxElementIndex) && (i >= 0) &&
|
|
(InternalNode(i).m_PrevSibling != i);
|
|
}
|
|
|
|
//-----------------------------------------------------------------------------
|
|
// Makes sure we have enough memory allocated to store a requested # of elements
|
|
//-----------------------------------------------------------------------------
|
|
template <class T, class I>
|
|
void CUtlNTree<T, I>::EnsureCapacity(int num) {
|
|
MEM_ALLOC_CREDIT_CLASS();
|
|
m_Memory.EnsureCapacity(num);
|
|
ResetDbgInfo();
|
|
}
|
|
|
|
//-----------------------------------------------------------------------------
|
|
// Deallocate memory
|
|
//-----------------------------------------------------------------------------
|
|
template <class T, class I>
|
|
void CUtlNTree<T, I>::Purge() {
|
|
RemoveAll();
|
|
m_Memory.Purge();
|
|
m_FirstFree = InvalidIndex();
|
|
m_MaxElementIndex = 0;
|
|
ResetDbgInfo();
|
|
}
|
|
|
|
//-----------------------------------------------------------------------------
|
|
// Node allocation/deallocation
|
|
//-----------------------------------------------------------------------------
|
|
template <class T, class I>
|
|
I CUtlNTree<T, I>::AllocInternal() {
|
|
I elem;
|
|
if (m_FirstFree == INVALID_NTREE_IDX) {
|
|
// Nothing in the free list; add.
|
|
// Since nothing is in the free list, m_MaxElementIndex == total # of
|
|
// elements the list knows about.
|
|
if ((int)m_MaxElementIndex == m_Memory.NumAllocated()) {
|
|
MEM_ALLOC_CREDIT_CLASS();
|
|
m_Memory.Grow();
|
|
}
|
|
|
|
Assert(m_MaxElementIndex != INVALID_NTREE_IDX);
|
|
|
|
elem = (I)m_MaxElementIndex;
|
|
++m_MaxElementIndex;
|
|
|
|
if (elem == InvalidIndex()) {
|
|
Error("CUtlNTree overflow!\n");
|
|
}
|
|
} else {
|
|
elem = m_FirstFree;
|
|
m_FirstFree = InternalNode(m_FirstFree).m_NextSibling;
|
|
}
|
|
|
|
Node_t& node = InternalNode(elem);
|
|
node.m_NextSibling = node.m_PrevSibling = node.m_Parent =
|
|
node.m_FirstChild = INVALID_NTREE_IDX;
|
|
ResetDbgInfo();
|
|
|
|
// one more element baby
|
|
++m_ElementCount;
|
|
|
|
return elem;
|
|
}
|
|
|
|
template <class T, class I>
|
|
I CUtlNTree<T, I>::Alloc() {
|
|
I elem = AllocInternal();
|
|
Construct(&Element(elem));
|
|
return elem;
|
|
}
|
|
|
|
template <class T, class I>
|
|
void CUtlNTree<T, I>::Free(I elem) {
|
|
Assert(IsInTree(elem));
|
|
Unlink(elem);
|
|
|
|
// If there's children, this will result in leaks. Use FreeSubTree instead.
|
|
Assert(FirstChild(elem) == INVALID_NTREE_IDX);
|
|
|
|
Node_t& node = InternalNode(elem);
|
|
Destruct(&node.m_Element);
|
|
node.m_NextSibling = m_FirstFree;
|
|
node.m_PrevSibling = elem; // Marks it as being in the free list
|
|
node.m_Parent = node.m_FirstChild = INVALID_NTREE_IDX;
|
|
m_FirstFree = elem;
|
|
|
|
// one less element baby
|
|
--m_ElementCount;
|
|
}
|
|
|
|
template <class T, class I>
|
|
void CUtlNTree<T, I>::FreeSubTree(I elem) {
|
|
Assert(IsValidIndex(elem));
|
|
|
|
I child = FirstChild(elem);
|
|
while (child != INVALID_NTREE_IDX) {
|
|
I next = NextSibling(child);
|
|
FreeSubTree(child);
|
|
child = next;
|
|
}
|
|
|
|
Free(elem);
|
|
}
|
|
|
|
//-----------------------------------------------------------------------------
|
|
// Clears the tree
|
|
//-----------------------------------------------------------------------------
|
|
template <class T, class I>
|
|
void CUtlNTree<T, I>::RemoveAll() {
|
|
if (m_MaxElementIndex == 0) return;
|
|
|
|
// Put everything into the free list (even unlinked things )
|
|
I prev = InvalidIndex();
|
|
for (int i = (int)m_MaxElementIndex; --i >= 0; prev = (I)i) {
|
|
Node_t& node = InternalNode(i);
|
|
if (IsInTree(i)) {
|
|
Destruct(&node.m_Element);
|
|
}
|
|
|
|
node.m_NextSibling = prev;
|
|
node.m_PrevSibling = (I)i; // Marks it as being in the free list
|
|
node.m_Parent = node.m_FirstChild = INVALID_NTREE_IDX;
|
|
}
|
|
|
|
// First free points to the first element
|
|
m_FirstFree = 0;
|
|
|
|
// Clear everything else out
|
|
m_Root = INVALID_NTREE_IDX;
|
|
m_ElementCount = 0;
|
|
}
|
|
|
|
//-----------------------------------------------------------------------------
|
|
// list modification
|
|
//-----------------------------------------------------------------------------
|
|
template <class T, class I>
|
|
void CUtlNTree<T, I>::SetRoot(I root) {
|
|
// Resetting the root while it's got stuff in it is bad...
|
|
Assert(m_Root == InvalidIndex());
|
|
m_Root = root;
|
|
}
|
|
|
|
//-----------------------------------------------------------------------------
|
|
// Links a node after a particular node
|
|
//-----------------------------------------------------------------------------
|
|
template <class T, class I>
|
|
void CUtlNTree<T, I>::LinkChildAfter(I parent, I after, I elem) {
|
|
Assert(IsInTree(elem));
|
|
|
|
// Unlink it if it's in the list at the moment
|
|
Unlink(elem);
|
|
|
|
Node_t& newElem = InternalNode(elem);
|
|
newElem.m_Parent = parent;
|
|
newElem.m_PrevSibling = after;
|
|
if (after != INVALID_NTREE_IDX) {
|
|
Node_t& prevSiblingNode = InternalNode(after);
|
|
newElem.m_NextSibling = prevSiblingNode.m_NextSibling;
|
|
prevSiblingNode.m_NextSibling = elem;
|
|
} else {
|
|
if (parent != INVALID_NTREE_IDX) {
|
|
Node_t& parentNode = InternalNode(parent);
|
|
newElem.m_NextSibling = parentNode.m_FirstChild;
|
|
parentNode.m_FirstChild = elem;
|
|
} else {
|
|
newElem.m_NextSibling = m_Root;
|
|
if (m_Root != INVALID_NTREE_IDX) {
|
|
Node_t& rootNode = InternalNode(m_Root);
|
|
rootNode.m_PrevSibling = elem;
|
|
}
|
|
m_Root = elem;
|
|
}
|
|
}
|
|
|
|
if (newElem.m_NextSibling != INVALID_NTREE_IDX) {
|
|
Node_t& nextSiblingNode = InternalNode(newElem.m_NextSibling);
|
|
nextSiblingNode.m_PrevSibling = elem;
|
|
}
|
|
}
|
|
|
|
//-----------------------------------------------------------------------------
|
|
// Links a node before a particular node
|
|
//-----------------------------------------------------------------------------
|
|
template <class T, class I>
|
|
void CUtlNTree<T, I>::LinkChildBefore(I parent, I before, I elem) {
|
|
Assert(IsValidIndex(elem));
|
|
|
|
if (before != INVALID_NTREE_IDX) {
|
|
LinkChildAfter(parent, InternalNode(before).m_PrevSibling, elem);
|
|
return;
|
|
}
|
|
|
|
// NOTE: I made the choice to do an O(n) operation here
|
|
// instead of store more data per node (LastChild).
|
|
// This might not be the right choice. Revisit if we get perf problems.
|
|
I after;
|
|
if (parent != INVALID_NTREE_IDX) {
|
|
after = InternalNode(parent).m_FirstChild;
|
|
} else {
|
|
after = m_Root;
|
|
}
|
|
|
|
if (after == INVALID_NTREE_IDX) {
|
|
LinkChildAfter(parent, after, elem);
|
|
return;
|
|
}
|
|
|
|
I next = InternalNode(after).m_NextSibling;
|
|
while (next != InvalidIndex()) {
|
|
after = next;
|
|
next = InternalNode(next).m_NextSibling;
|
|
}
|
|
|
|
LinkChildAfter(parent, after, elem);
|
|
}
|
|
|
|
//-----------------------------------------------------------------------------
|
|
// Unlinks a node from the tree
|
|
//-----------------------------------------------------------------------------
|
|
template <class T, class I>
|
|
void CUtlNTree<T, I>::Unlink(I elem) {
|
|
Assert(IsInTree(elem));
|
|
|
|
Node_t* pOldNode = &InternalNode(elem);
|
|
|
|
// If we're the first guy, reset the head
|
|
// otherwise, make our previous node's next pointer = our next
|
|
if (pOldNode->m_PrevSibling != INVALID_NTREE_IDX) {
|
|
InternalNode(pOldNode->m_PrevSibling).m_NextSibling =
|
|
pOldNode->m_NextSibling;
|
|
} else {
|
|
if (pOldNode->m_Parent != INVALID_NTREE_IDX) {
|
|
InternalNode(pOldNode->m_Parent).m_FirstChild =
|
|
pOldNode->m_NextSibling;
|
|
} else if (m_Root == elem) {
|
|
m_Root = pOldNode->m_NextSibling;
|
|
}
|
|
}
|
|
|
|
// If we're the last guy, reset the tail
|
|
// otherwise, make our next node's prev pointer = our prev
|
|
if (pOldNode->m_NextSibling != INVALID_NTREE_IDX) {
|
|
InternalNode(pOldNode->m_NextSibling).m_PrevSibling =
|
|
pOldNode->m_PrevSibling;
|
|
}
|
|
|
|
// Unlink everything except children
|
|
pOldNode->m_Parent = pOldNode->m_PrevSibling = pOldNode->m_NextSibling =
|
|
INVALID_NTREE_IDX;
|
|
}
|
|
|
|
//-----------------------------------------------------------------------------
|
|
// Alloc + link combined
|
|
//-----------------------------------------------------------------------------
|
|
template <class T, class I>
|
|
I CUtlNTree<T, I>::InsertChildBefore(I parent, I before) {
|
|
I elem = AllocInternal();
|
|
Construct(&Element(elem));
|
|
LinkChildBefore(parent, before, elem);
|
|
return elem;
|
|
}
|
|
|
|
template <class T, class I>
|
|
I CUtlNTree<T, I>::InsertChildAfter(I parent, I after) {
|
|
I elem = AllocInternal();
|
|
Construct(&Element(elem));
|
|
LinkChildAfter(parent, after, elem);
|
|
return elem;
|
|
}
|
|
|
|
template <class T, class I>
|
|
I CUtlNTree<T, I>::InsertChildBefore(I parent, I before, const T& data) {
|
|
I elem = AllocInternal();
|
|
CopyConstruct(&Element(elem), data);
|
|
LinkChildBefore(parent, before, elem);
|
|
return elem;
|
|
}
|
|
|
|
template <class T, class I>
|
|
I CUtlNTree<T, I>::InsertChildAfter(I parent, I after, const T& data) {
|
|
I elem = AllocInternal();
|
|
CopyConstruct(&Element(elem), data);
|
|
LinkChildAfter(parent, after, elem);
|
|
return elem;
|
|
}
|
|
|
|
//-----------------------------------------------------------------------------
|
|
// Unlink + free combined
|
|
//-----------------------------------------------------------------------------
|
|
template <class T, class I>
|
|
void CUtlNTree<T, I>::Remove(I elem) {
|
|
Unlink(elem);
|
|
Free(elem);
|
|
}
|
|
|
|
template <class T, class I>
|
|
void CUtlNTree<T, I>::RemoveSubTree(I elem) {
|
|
UnlinkSubTree(elem);
|
|
Free(elem);
|
|
}
|
|
|
|
#endif // UTLNTREE_H
|