1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
|
// Licensed to the .NET Foundation under one or more agreements.
// The .NET Foundation licenses this file to you under the MIT license.
// See the LICENSE file in the project root for more information.
#include "forward_declarations.h"
MSVC_SAVE_WARNING_STATE()
MSVC_DISABLE_WARNING(4127) // conditional expression is constant -- it's intentionally constant
struct DoNothingFailFastPolicy
{
static inline void FailFast();
};
template <typename T, typename FailFastPolicy = DoNothingFailFastPolicy>
struct DefaultSListTraits : public FailFastPolicy
{
typedef DPTR(T) PTR_T;
typedef DPTR(PTR_T) PTR_PTR_T;
static inline PTR_PTR_T GetNextPtr(PTR_T pT);
static inline bool Equals(PTR_T pA, PTR_T pB);
};
//------------------------------------------------------------------------------------------------------------
// class SList, to use a singly linked list.
//
// To use, either expose a field DPTR(T) m_pNext by adding DefaultSListTraits as a friend class, or
// define a new Traits class derived from DefaultSListTraits<T> and override the GetNextPtr function.
//
// SList supports lockless head insert and Remove methods. However, PushHeadInterlocked and
// PopHeadInterlocked must be used very carefully, as the rest of the mutating methods are not
// interlocked. In general, code must be careful to ensure that it will never use more than one
// synchronization mechanism at any given time to control access to a resource, and this is no
// exception. In particular, if synchronized access to other SList operations (such as FindAndRemove)
// are required, than a separate synchronization mechanism (such as a critical section) must be used.
//------------------------------------------------------------------------------------------------------------
template <typename T, typename Traits = DefaultSListTraits<T> >
class SList : public Traits
{
protected:
typedef typename Traits::PTR_T PTR_T;
typedef typename Traits::PTR_PTR_T PTR_PTR_T;
public:
SList();
// Returns true if there are no entries in the list.
bool IsEmpty();
// Returns the value of (but does not remove) the first element in the list.
PTR_T GetHead();
// Inserts pItem at the front of the list. See class header for more information.
void PushHead(PTR_T pItem);
void PushHeadInterlocked(PTR_T pItem);
// Removes and returns the first entry in the list. See class header for more information.
PTR_T PopHead();
class Iterator
{
friend SList<T, Traits>;
public:
Iterator(Iterator const &it);
Iterator& operator=(Iterator const &it);
PTR_T operator->();
PTR_T operator*();
Iterator & operator++();
Iterator operator++(int);
bool operator==(Iterator const &rhs);
bool operator==(PTR_T pT);
bool operator!=(Iterator const &rhs);
private:
Iterator(PTR_PTR_T ppItem);
Iterator Insert(PTR_T pItem);
Iterator Remove();
static Iterator End();
PTR_PTR_T m_ppCur;
#ifdef _DEBUG
mutable bool m_fIsValid;
#endif
PTR_T _Value() const;
enum e_ValidateOperation
{
e_CanCompare, // Will assert in debug if m_fIsValid == false.
e_CanInsert, // i.e., not the fake End() value of m_ppCur == NULL
e_HasValue, // i.e., m_ppCur != NULL && *m_ppCur != NULL
};
void _Validate(e_ValidateOperation op) const;
};
Iterator Begin();
Iterator End();
// Returns iterator to first list item matching pItem
Iterator FindFirst(PTR_T pItem);
bool RemoveFirst(PTR_T pItem);
// Inserts pItem *before* it. Returns iterator pointing to inserted item.
Iterator Insert(Iterator & it, PTR_T pItem);
// Removes item pointed to by it from the list. Returns iterator pointing
// to following item.
Iterator Remove(Iterator & it);
private:
PTR_T m_pHead;
};
MSVC_RESTORE_WARNING_STATE()
|
