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