1//-----------------------------------------------------------------------------
2// File: Linklist.h
3// Desc: Linked list class.
4//
5// THIS CODE AND INFORMATION IS PROVIDED "AS IS" WITHOUT WARRANTY OF
6// ANY KIND, EITHER EXPRESSED OR IMPLIED, INCLUDING BUT NOT LIMITED TO
7// THE IMPLIED WARRANTIES OF MERCHANTABILITY AND/OR FITNESS FOR A
8// PARTICULAR PURPOSE.
9//
10//  Copyright (C) Microsoft Corporation. All rights reserved.
11//-----------------------------------------------------------------------------
12
13#pragma once
14
15// Notes:
16//
17// The List class template implements a simple double-linked list.
18// It uses STL's copy semantics.
19
20// There are two versions of the Clear() method:
21//  Clear(void) clears the list w/out cleaning up the object.
22//  Clear(FN fn) takes a functor object that releases the objects, if they need cleanup.
23
24// The List class supports enumeration. Example of usage:
25//
26// List<T>::POSIITON pos = list.GetFrontPosition();
27// while (pos != list.GetEndPosition())
28// {
29//     T item;
30//     hr = list.GetItemPos(&item);
31//     pos = list.Next(pos);
32// }
33
34// The ComPtrList class template derives from List<> and implements a list of COM pointers.
35
36template <class T>
37struct NoOp
38{
39    void operator()(T& t)
40    {
41    }
42};
43
44template <class T>
45class List
46{
47protected:
48
49    // Nodes in the linked list
50    struct Node
51    {
52        Node *prev;
53        Node *next;
54        T    item;
55
56        Node() : prev(nullptr), next(nullptr)
57        {
58        }
59
60        Node(T item) : prev(nullptr), next(nullptr)
61        {
62            this->item = item;
63        }
64
65        T Item() const { return item; }
66    };
67
68public:
69
70    // Object for enumerating the list.
71    class POSITION
72    {
73        friend class List<T>;
74
75    public:
76        POSITION() : pNode(nullptr)
77        {
78        }
79
80        bool operator==(const POSITION &p) const
81        {
82            return pNode == p.pNode;
83        }
84
85        bool operator!=(const POSITION &p) const
86        {
87            return pNode != p.pNode;
88        }
89
90    private:
91        const Node *pNode;
92
93        POSITION(Node *p) : pNode(p)
94        {
95        }
96    };
97
98protected:
99    Node    m_anchor;  // Anchor node for the linked list.
100    DWORD   m_count;   // Number of items in the list.
101
102    Node* Front() const
103    {
104        return m_anchor.next;
105    }
106
107    Node* Back() const
108    {
109        return m_anchor.prev;
110    }
111
112    virtual HRESULT InsertAfter(T item, Node *pBefore)
113    {
114        if (pBefore == nullptr)
115        {
116            return E_POINTER;
117        }
118
119        Node *pNode = new Node(item);
120        if (pNode == nullptr)
121        {
122            return E_OUTOFMEMORY;
123        }
124
125        Node *pAfter = pBefore->next;
126
127        pBefore->next = pNode;
128        pAfter->prev = pNode;
129
130        pNode->prev = pBefore;
131        pNode->next = pAfter;
132
133        m_count++;
134
135        return S_OK;
136    }
137
138    virtual HRESULT GetItem(const Node *pNode, T* ppItem)
139    {
140        if (pNode == nullptr || ppItem == nullptr)
141        {
142            return E_POINTER;
143        }
144
145        *ppItem = pNode->item;
146        return S_OK;
147    }
148
149    // RemoveItem:
150    // Removes a node and optionally returns the item.
151    // ppItem can be nullptr.
152    virtual HRESULT RemoveItem(Node *pNode, T *ppItem)
153    {
154        if (pNode == nullptr)
155        {
156            return E_POINTER;
157        }
158
159        assert(pNode != &m_anchor); // We should never try to remove the anchor node.
160        if (pNode == &m_anchor)
161        {
162            return E_INVALIDARG;
163        }
164
165
166        T item;
167
168        // The next node's previous is this node's previous.
169        pNode->next->prev = pNode->prev;
170
171        // The previous node's next is this node's next.
172        pNode->prev->next = pNode->next;
173
174        item = pNode->item;
175        delete pNode;
176
177        m_count--;
178
179        if (ppItem)
180        {
181            *ppItem = item;
182        }
183
184        return S_OK;
185    }
186
187public:
188
189    List()
190    {
191        m_anchor.next = &m_anchor;
192        m_anchor.prev = &m_anchor;
193
194        m_count = 0;
195    }
196
197    virtual ~List()
198    {
199        Clear();
200    }
201
202    // Insertion functions
203    HRESULT InsertBack(T item)
204    {
205        return InsertAfter(item, m_anchor.prev);
206    }
207
208
209    HRESULT InsertFront(T item)
210    {
211        return InsertAfter(item, &m_anchor);
212    }
213
214    HRESULT InsertPos(POSITION pos, T item)
215    {
216        if (pos.pNode == nullptr)
217        {
218            return InsertBack(item);
219        }
220
221        return InsertAfter(item, pos.pNode->prev);
222    }
223
224    // RemoveBack: Removes the tail of the list and returns the value.
225    // ppItem can be nullptr if you don't want the item back. (But the method does not release the item.)
226    HRESULT RemoveBack(T *ppItem)
227    {
228        if (IsEmpty())
229        {
230            return E_FAIL;
231        }
232        else
233        {
234            return RemoveItem(Back(), ppItem);
235        }
236    }
237
238    // RemoveFront: Removes the head of the list and returns the value.
239    // ppItem can be nullptr if you don't want the item back. (But the method does not release the item.)
240    HRESULT RemoveFront(T *ppItem)
241    {
242        if (IsEmpty())
243        {
244            return E_FAIL;
245        }
246        else
247        {
248            return RemoveItem(Front(), ppItem);
249        }
250    }
251
252    // GetBack: Gets the tail item.
253    HRESULT GetBack(T *ppItem)
254    {
255        if (IsEmpty())
256        {
257            return E_FAIL;
258        }
259        else
260        {
261            return GetItem(Back(), ppItem);
262        }
263    }
264
265    // GetFront: Gets the front item.
266    HRESULT GetFront(T *ppItem)
267    {
268        if (IsEmpty())
269        {
270            return E_FAIL;
271        }
272        else
273        {
274            return GetItem(Front(), ppItem);
275        }
276    }
277
278
279    // GetCount: Returns the number of items in the list.
280    DWORD GetCount() const { return m_count; }
281
282    bool IsEmpty() const
283    {
284        return (GetCount() == 0);
285    }
286
287    // Clear: Takes a functor object whose operator()
288    // frees the object on the list.
289    template <class FN>
290    void Clear(FN& clear_fn)
291    {
292        Node *n = m_anchor.next;
293
294        // Delete the nodes
295        while (n != &m_anchor)
296        {
297            clear_fn(n->item);
298
299            Node *tmp = n->next;
300            delete n;
301            n = tmp;
302        }
303
304        // Reset the anchor to point at itself
305        m_anchor.next = &m_anchor;
306        m_anchor.prev = &m_anchor;
307
308        m_count = 0;
309    }
310
311    // Clear: Clears the list. (Does not delete or release the list items.)
312    virtual void Clear()
313    {
314        NoOp<T> clearOp;
315        Clear<>(clearOp);
316    }
317
318
319    // Enumerator functions
320
321    POSITION FrontPosition()
322    {
323        if (IsEmpty())
324        {
325            return POSITION(nullptr);
326        }
327        else
328        {
329            return POSITION(Front());
330        }
331    }
332
333    POSITION EndPosition() const
334    {
335        return POSITION();
336    }
337
338    HRESULT GetItemPos(POSITION pos, T *ppItem)
339    {
340        if (pos.pNode)
341        {
342            return GetItem(pos.pNode, ppItem);
343        }
344        else
345        {
346            return E_FAIL;
347        }
348    }
349
350    POSITION Next(const POSITION pos)
351    {
352        if (pos.pNode && (pos.pNode->next != &m_anchor))
353        {
354            return POSITION(pos.pNode->next);
355        }
356        else
357        {
358            return POSITION(nullptr);
359        }
360    }
361
362    // Remove an item at a position.
363    // The item is returns in ppItem, unless ppItem is nullptr.
364    // NOTE: This method invalidates the POSITION object.
365    HRESULT Remove(POSITION& pos, T *ppItem)
366    {
367        if (pos.pNode)
368        {
369            // Remove const-ness temporarily...
370            Node *pNode = const_cast<Node*>(pos.pNode);
371
372            pos = POSITION();
373
374            return RemoveItem(pNode, ppItem);
375        }
376        else
377        {
378            return E_INVALIDARG;
379        }
380    }
381
382};
383
384
385
386// Typical functors for Clear method.
387
388// ComAutoRelease: Releases COM pointers.
389// MemDelete: Deletes pointers to new'd memory.
390
391class ComAutoRelease
392{
393public:
394    void operator()(IUnknown *p)
395    {
396        if (p)
397        {
398            p->Release();
399        }
400    }
401};
402
403class MemDelete
404{
405public:
406    void operator()(void *p)
407    {
408        if (p)
409        {
410            delete p;
411        }
412    }
413};
414
415
416// ComPtrList class
417// Derived class that makes it safer to store COM pointers in the List<> class.
418// It automatically AddRef's the pointers that are inserted onto the list
419// (unless the insertion method fails).
420//
421// T must be a COM interface type.
422// example: ComPtrList<IUnknown>
423//
424// NULLABLE: If true, client can insert nullptr pointers. This means GetItem can
425// succeed but return a nullptr pointer. By default, the list does not allow nullptr
426// pointers.
427
428template <class T, bool NULLABLE = FALSE>
429class ComPtrList : public List<T*>
430{
431public:
432
433    typedef T* Ptr;
434
435    void Clear()
436    {
437        ComAutoRelease car;
438        List<Ptr>::Clear(car);
439    }
440
441    ~ComPtrList()
442    {
443        Clear();
444    }
445
446protected:
447    HRESULT InsertAfter(Ptr item, Node *pBefore)
448    {
449        // Do not allow nullptr item pointers unless NULLABLE is true.
450        if (item == nullptr && !NULLABLE)
451        {
452            return E_POINTER;
453        }
454
455        if (item)
456        {
457            item->AddRef();
458        }
459
460        HRESULT hr = List<Ptr>::InsertAfter(item, pBefore);
461        if (FAILED(hr) && item != nullptr)
462        {
463            item->Release();
464        }
465        return hr;
466    }
467
468    HRESULT GetItem(const Node *pNode, Ptr* ppItem)
469    {
470        Ptr pItem = nullptr;
471
472        // The base class gives us the pointer without AddRef'ing it.
473        // If we return the pointer to the caller, we must AddRef().
474        HRESULT hr = List<Ptr>::GetItem(pNode, &pItem);
475        if (SUCCEEDED(hr))
476        {
477            assert(pItem || NULLABLE);
478            if (pItem)
479            {
480                *ppItem = pItem;
481                (*ppItem)->AddRef();
482            }
483        }
484        return hr;
485    }
486
487    HRESULT RemoveItem(Node *pNode, Ptr *ppItem)
488    {
489        // ppItem can be nullptr, but we need to get the
490        // item so that we can release it.
491
492        // If ppItem is not nullptr, we will AddRef it on the way out.
493
494        Ptr pItem = nullptr;
495
496        HRESULT hr = List<Ptr>::RemoveItem(pNode, &pItem);
497
498        if (SUCCEEDED(hr))
499        {
500            assert(pItem || NULLABLE);
501            if (ppItem && pItem)
502            {
503                *ppItem = pItem;
504                (*ppItem)->AddRef();
505            }
506
507            if (pItem)
508            {
509                pItem->Release();
510                pItem = nullptr;
511            }
512        }
513
514        return hr;
515    }
516};
517