1 /*
2  * COPYRIGHT:   See COPYING in the top level directory
3  * PROJECT:     ReactOS HTTP Daemon
4  * FILE:        include/list.h
5  */
6 #ifndef __LIST_H
7 #define __LIST_H
8 
9 #include <windows.h>
10 #include <iterator.h>
11 
12 class CListNode {
13 public:
14 	CListNode();
15 	CListNode(VOID *element, CListNode *next, CListNode *prev);
~CListNode()16 	~CListNode() {};
17     void* operator new(size_t s);
18     VOID  operator delete(void* p);
19 
20 	VOID SetElement(PVOID element);
21 	VOID SetNext(CListNode *next);
22 	VOID SetPrev(CListNode *prev);
23 	PVOID GetElement();
24 	CListNode *GetNext();
25 	CListNode *GetPrev();
26 private:
27 	PVOID Element;
28 	CListNode *Next;
29 	CListNode *Prev;
30     static HANDLE hHeap;
31     static INT nRef;
32 };
33 
34 template <class Item> class CList {
35 public:
36 	//CList(CList&);
37 	CList();
38 	~CList();
39 	CList& operator=(CList&);
40 
41 	CIterator<Item> *CreateIterator() const;
42 	LONG Count() const;
43 	Item& Get(const LONG index) const;
44 	// Can throw bad_alloc
45 	VOID Insert(Item& element);
46 	VOID Remove(Item& element);
47 	VOID RemoveAll();
48 	CListNode *GetHeader() const;
49 	CListNode *GetTrailer() const;
50 private:
51 	CListNode *Search(Item& element) const;
52 	LONG NodeCount;
53 	CListNode *Header;
54 	CListNode *Trailer;
55 };
56 
57 template <class Item> class CListIterator : public CIterator<Item> {
58 public:
59 	CListIterator(const CList<Item> *list);
60 	virtual VOID First();
61 	virtual VOID Next();
62 	virtual BOOL IsDone() const;
63 	virtual Item CurrentItem() const;
64 private:
65 	const CList<Item> *List;
66 	CListNode *Current;
67 };
68 
69 // ****************************** CList ******************************
70 
71 // Default constructor
72 template <class Item>
CList()73 CList<Item>::CList()
74 {
75 	// Create dummy nodes
76 	Trailer = new CListNode;
77 	Header = new CListNode;
78 	Header->SetNext(Trailer);
79 	Trailer->SetPrev(Header);
80 }
81 
82 // Default destructor
83 template <class Item>
~CList()84 CList<Item>::~CList()
85 {
86 	RemoveAll();
87 	delete Trailer;
88 	delete Header;
89 }
90 
91 // Create an iterator for the list
92 template <class Item>
CreateIterator()93 CIterator<Item> *CList<Item>::CreateIterator() const
94 {
95 	return new CListIterator<Item>((CList<Item> *) this);
96 }
97 
98 // Return number of elements in list
99 template <class Item>
Count()100 LONG CList<Item>::Count() const
101 {
102 	return NodeCount;
103 }
104 
105 // Return element at index
106 template <class Item>
Get(const LONG index)107 Item& CList<Item>::Get(const LONG index) const
108 {
109 	CListNode *node;
110 
111 	if ((index < 0) || (index >= NodeCount))
112 		return NULL;
113 
114 	node = Header;
115 	for (int i = 0; i <= index; i++)
116 		node = node->GetNext();
117 
118 	return (Item *) node->GetElement();
119 }
120 
121 // Insert an element into the list
122 template <class Item>
Insert(Item & element)123 VOID CList<Item>::Insert(Item& element)
124 {
125 	CListNode *node;
126 
127 	node = new CListNode((PVOID)element, Trailer, Trailer->GetPrev());
128 	Trailer->GetPrev()->SetNext(node);
129 	Trailer->SetPrev(node);
130 	NodeCount++;
131 }
132 
133 // Remove an element from the list
134 template <class Item>
Remove(Item & element)135 VOID CList<Item>::Remove(Item& element)
136 {
137 	CListNode *node;
138 
139 	node = Search(element);
140 	if (node != NULL) {
141 		node->GetPrev()->SetNext(node->GetNext());
142 		node->GetNext()->SetPrev(node->GetPrev());
143 		NodeCount--;
144 		delete node;
145 	}
146 }
147 
148 // Remove all elements in list
149 template <class Item>
RemoveAll()150 VOID CList<Item>::RemoveAll()
151 {
152 	CListNode *node;
153 	CListNode *tmp;
154 
155 	node = Header->GetNext();
156 	while (node != Trailer) {
157 		tmp = node->GetNext();
158 		delete node;
159 		node = tmp;
160 	}
161 	Header->SetNext(Trailer);
162 	Trailer->SetPrev(Header);
163 	NodeCount = 0;
164 }
165 
166 // Return header node
167 template <class Item>
GetHeader()168 CListNode *CList<Item>::GetHeader() const
169 {
170 	return Header;
171 }
172 
173 // Return trailer node
174 template <class Item>
GetTrailer()175 CListNode *CList<Item>::GetTrailer() const
176 {
177 	return Trailer;
178 }
179 
180 // Searches for a node that contains the element. Returns NULL if element is not found
181 template <class Item>
Search(Item & element)182 CListNode *CList<Item>::Search(Item& element) const
183 {
184 	CListNode *node;
185 
186 	node = Header;
187 	while (((node = node->GetNext()) != Trailer) && (node->GetElement() != element));
188 	if (node != Trailer)
189 		return node;
190 	else
191 		return NULL;
192 }
193 
194 
195 // ************************** CListIterator **************************
196 
197 // Default constructor
198 template <class Item>
CListIterator(const CList<Item> * list)199 CListIterator<Item>::CListIterator(const CList<Item> *list) : List(list)
200 {
201 	First();
202 }
203 
204 // Go to first element in list
205 template <class Item>
First()206 VOID CListIterator<Item>::First()
207 {
208 	Current = List->GetHeader()->GetNext();
209 }
210 
211 // Go to next element in list
212 template <class Item>
Next()213 VOID CListIterator<Item>::Next()
214 {
215 	if (!IsDone())
216 		Current = Current->GetNext();
217 }
218 
219 // Return FALSE when there are more elements in list and TRUE when there are no more
220 template <class Item>
IsDone()221 BOOL CListIterator<Item>::IsDone() const
222 {
223 	return (Current == List->GetTrailer());
224 }
225 
226 // Return current element
227 template <class Item>
CurrentItem()228 Item CListIterator<Item>::CurrentItem() const
229 {
230 	return IsDone()? NULL : (Item) Current->GetElement();
231 }
232 
233 #endif /* __LIST_H */
234