//-----------------------------------------------------------------------------
// File: Linklist.h
// Desc: Linked list class.
//
// THIS CODE AND INFORMATION IS PROVIDED "AS IS" WITHOUT WARRANTY OF
// ANY KIND, EITHER EXPRESSED OR IMPLIED, INCLUDING BUT NOT LIMITED TO
// THE IMPLIED WARRANTIES OF MERCHANTABILITY AND/OR FITNESS FOR A
// PARTICULAR PURPOSE.
//
// Copyright (C) Microsoft Corporation. All rights reserved.
//-----------------------------------------------------------------------------
#pragma once
// Notes:
//
// The List class template implements a simple double-linked list.
// It uses STL's copy semantics.
// There are two versions of the Clear() method:
// Clear(void) clears the list w/out cleaning up the object.
// Clear(FN fn) takes a functor object that releases the objects, if they need cleanup.
// The List class supports enumeration. Example of usage:
//
// List<T>::POSIITON pos = list.GetFrontPosition();
// while (pos != list.GetEndPosition())
// {
// T item;
// hr = list.GetItemPos(&item);
// pos = list.Next(pos);
// }
// The ComPtrList class template derives from List<> and implements a list of COM pointers.
template <class T>
struct NoOp
{
void operator()(T& t)
{
}
};
template <class T>
class List
{
protected:
// Nodes in the linked list
struct Node
{
Node *prev;
Node *next;
T item;
Node() : prev(nullptr), next(nullptr)
{
}
Node(T item) : prev(nullptr), next(nullptr)
{
this->item = item;
}
T Item() const { return item; }
};
public:
// Object for enumerating the list.
class POSITION
{
friend class List<T>;
public:
POSITION() : pNode(nullptr)
{
}
bool operator==(const POSITION &p) const
{
return pNode == p.pNode;
}
bool operator!=(const POSITION &p) const
{
return pNode != p.pNode;
}
private:
const Node *pNode;
POSITION(Node *p) : pNode(p)
{
}
};
protected:
Node m_anchor; // Anchor node for the linked list.
DWORD m_count; // Number of items in the list.
Node* Front() const
{
return m_anchor.next;
}
Node* Back() const
{
return m_anchor.prev;
}
virtual HRESULT InsertAfter(T item, Node *pBefore)
{
if (pBefore == nullptr)
{
return E_POINTER;
}
Node *pNode = new Node(item);
if (pNode == nullptr)
{
return E_OUTOFMEMORY;
}
Node *pAfter = pBefore->next;
pBefore->next = pNode;
pAfter->prev = pNode;
pNode->prev = pBefore;
pNode->next = pAfter;
m_count++;
return S_OK;
}
virtual HRESULT GetItem(const Node *pNode, T* ppItem)
{
if (pNode == nullptr || ppItem == nullptr)
{
return E_POINTER;
}
*ppItem = pNode->item;
return S_OK;
}
// RemoveItem:
// Removes a node and optionally returns the item.
// ppItem can be nullptr.
virtual HRESULT RemoveItem(Node *pNode, T *ppItem)
{
if (pNode == nullptr)
{
return E_POINTER;
}
assert(pNode != &m_anchor); // We should never try to remove the anchor node.
if (pNode == &m_anchor)
{
return E_INVALIDARG;
}
T item;
// The next node's previous is this node's previous.
pNode->next->prev = pNode->prev;
// The previous node's next is this node's next.
pNode->prev->next = pNode->next;
item = pNode->item;
delete pNode;
m_count--;
if (ppItem)
{
*ppItem = item;
}
return S_OK;
}
public:
List()
{
m_anchor.next = &m_anchor;
m_anchor.prev = &m_anchor;
m_count = 0;
}
virtual ~List()
{
Clear();
}
// Insertion functions
HRESULT InsertBack(T item)
{
return InsertAfter(item, m_anchor.prev);
}
HRESULT InsertFront(T item)
{
return InsertAfter(item, &m_anchor);
}
HRESULT InsertPos(POSITION pos, T item)
{
if (pos.pNode == nullptr)
{
return InsertBack(item);
}
return InsertAfter(item, pos.pNode->prev);
}
// RemoveBack: Removes the tail of the list and returns the value.
// ppItem can be nullptr if you don't want the item back. (But the method does not release the item.)
HRESULT RemoveBack(T *ppItem)
{
if (IsEmpty())
{
return E_FAIL;
}
else
{
return RemoveItem(Back(), ppItem);
}
}
// RemoveFront: Removes the head of the list and returns the value.
// ppItem can be nullptr if you don't want the item back. (But the method does not release the item.)
HRESULT RemoveFront(T *ppItem)
{
if (IsEmpty())
{
return E_FAIL;
}
else
{
return RemoveItem(Front(), ppItem);
}
}
// GetBack: Gets the tail item.
HRESULT GetBack(T *ppItem)
{
if (IsEmpty())
{
return E_FAIL;
}
else
{
return GetItem(Back(), ppItem);
}
}
// GetFront: Gets the front item.
HRESULT GetFront(T *ppItem)
{
if (IsEmpty())
{
return E_FAIL;
}
else
{
return GetItem(Front(), ppItem);
}
}
// GetCount: Returns the number of items in the list.
DWORD GetCount() const { return m_count; }
bool IsEmpty() const
{
return (GetCount() == 0);
}
// Clear: Takes a functor object whose operator()
// frees the object on the list.
template <class FN>
void Clear(FN& clear_fn)
{
Node *n = m_anchor.next;
// Delete the nodes
while (n != &m_anchor)
{
clear_fn(n->item);
Node *tmp = n->next;
delete n;
n = tmp;
}
// Reset the anchor to point at itself
m_anchor.next = &m_anchor;
m_anchor.prev = &m_anchor;
m_count = 0;
}
// Clear: Clears the list. (Does not delete or release the list items.)
virtual void Clear()
{
NoOp<T> clearOp;
Clear<>(clearOp);
}
// Enumerator functions
POSITION FrontPosition()
{
if (IsEmpty())
{
return POSITION(nullptr);
}
else
{
return POSITION(Front());
}
}
POSITION EndPosition() const
{
return POSITION();
}
HRESULT GetItemPos(POSITION pos, T *ppItem)
{
if (pos.pNode)
{
return GetItem(pos.pNode, ppItem);
}
else
{
return E_FAIL;
}
}
POSITION Next(const POSITION pos)
{
if (pos.pNode && (pos.pNode->next != &m_anchor))
{
return POSITION(pos.pNode->next);
}
else
{
return POSITION(nullptr);
}
}
// Remove an item at a position.
// The item is returns in ppItem, unless ppItem is nullptr.
// NOTE: This method invalidates the POSITION object.
HRESULT Remove(POSITION& pos, T *ppItem)
{
if (pos.pNode)
{
// Remove const-ness temporarily...
Node *pNode = const_cast<Node*>(pos.pNode);
pos = POSITION();
return RemoveItem(pNode, ppItem);
}
else
{
return E_INVALIDARG;
}
}
};
// Typical functors for Clear method.
// ComAutoRelease: Releases COM pointers.
// MemDelete: Deletes pointers to new'd memory.
class ComAutoRelease
{
public:
void operator()(IUnknown *p)
{
if (p)
{
p->Release();
}
}
};
class MemDelete
{
public:
void operator()(void *p)
{
if (p)
{
delete p;
}
}
};
// ComPtrList class
// Derived class that makes it safer to store COM pointers in the List<> class.
// It automatically AddRef's the pointers that are inserted onto the list
// (unless the insertion method fails).
//
// T must be a COM interface type.
// example: ComPtrList<IUnknown>
//
// NULLABLE: If true, client can insert nullptr pointers. This means GetItem can
// succeed but return a nullptr pointer. By default, the list does not allow nullptr
// pointers.
template <class T, bool NULLABLE = FALSE>
class ComPtrList : public List<T*>
{
public:
typedef T* Ptr;
void Clear()
{
ComAutoRelease car;
List<Ptr>::Clear(car);
}
~ComPtrList()
{
Clear();
}
protected:
HRESULT InsertAfter(Ptr item, Node *pBefore)
{
// Do not allow nullptr item pointers unless NULLABLE is true.
if (item == nullptr && !NULLABLE)
{
return E_POINTER;
}
if (item)
{
item->AddRef();
}
HRESULT hr = List<Ptr>::InsertAfter(item, pBefore);
if (FAILED(hr) && item != nullptr)
{
item->Release();
}
return hr;
}
HRESULT GetItem(const Node *pNode, Ptr* ppItem)
{
Ptr pItem = nullptr;
// The base class gives us the pointer without AddRef'ing it.
// If we return the pointer to the caller, we must AddRef().
HRESULT hr = List<Ptr>::GetItem(pNode, &pItem);
if (SUCCEEDED(hr))
{
assert(pItem || NULLABLE);
if (pItem)
{
*ppItem = pItem;
(*ppItem)->AddRef();
}
}
return hr;
}
HRESULT RemoveItem(Node *pNode, Ptr *ppItem)
{
// ppItem can be nullptr, but we need to get the
// item so that we can release it.
// If ppItem is not nullptr, we will AddRef it on the way out.
Ptr pItem = nullptr;
HRESULT hr = List<Ptr>::RemoveItem(pNode, &pItem);
if (SUCCEEDED(hr))
{
assert(pItem || NULLABLE);
if (ppItem && pItem)
{
*ppItem = pItem;
(*ppItem)->AddRef();
}
if (pItem)
{
pItem->Release();
pItem = nullptr;
}
}
return hr;
}
};