LinkList.h

//-----------------------------------------------------------------------------
// 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;
    }
};