1 #ifndef _SINGLY_LINKED_LIST_H_ 2 #define _SINGLY_LINKED_LIST_H_ 3 4 #include "MallocFreeAllocator.h" 5 #include "SupportDefs.h" 6 7 namespace Strategy { 8 namespace SinglyLinkedList { 9 //! Automatic node strategy (works like STL containers do) 10 namespace Private { 11 template <class Value> 12 class ListNode 13 { 14 public: 15 typedef Value ValueType; 16 17 ListNode(const ValueType &data) 18 : data(data) 19 , next(NULL) 20 { 21 } 22 23 ValueType data; 24 ListNode<Value> *next; 25 }; 26 } // namespace Private 27 28 template <typename Value, template <class> class Allocator = MallocFreeAllocator> 29 class Auto 30 { 31 public: 32 typedef Private::ListNode<Value> NodeType; 33 typedef Value ValueType; 34 35 inline NodeType *Allocate(const ValueType &data) 36 { 37 NodeType* result = fAllocator.Allocate(); 38 fAllocator.Construct(result, data); 39 return result; 40 } 41 42 inline void Free(NodeType *node) 43 { 44 fAllocator.Destruct(node); 45 fAllocator.Deallocate(node); 46 } 47 48 inline ValueType& GetValue(NodeType *node) const { 49 return node->data; 50 } 51 52 inline NodeType* GetNext(NodeType *node) const { 53 return node->next; 54 } 55 56 inline NodeType* SetNext(NodeType *node, NodeType* next) const { 57 return node->next = next; 58 } 59 60 inline NodeType* GetPrevious(NodeType *node) const { 61 return node->previous; 62 } 63 64 inline NodeType* SetPrevious(NodeType *node, NodeType* previous) const { 65 return node->previous = previous; 66 } 67 68 protected: 69 Allocator<NodeType> fAllocator; 70 }; 71 72 73 //! User managed node strategy (user is responsible for node allocation/deallocation) 74 template <class Node, Node* Node::* NextMember = &Node::next> 75 class User; 76 } 77 } 78 79 template <class Value, class Reference, class Pointer, class Parent> 80 class SinglyLinkedListIterator; 81 82 template <class Value, class NodeStrategy = Strategy::SinglyLinkedList::Auto<Value> > 83 class SinglyLinkedList 84 { 85 public: 86 typedef SinglyLinkedList<Value, NodeStrategy> Type; 87 88 typedef typename NodeStrategy::NodeType NodeType; 89 typedef typename NodeStrategy::ValueType ValueType; 90 91 typedef NodeType* NodeType::* NodePointerMember; 92 93 typedef SinglyLinkedListIterator<ValueType, ValueType&, ValueType*, Type> Iterator; 94 typedef SinglyLinkedListIterator<ValueType, const ValueType&, const ValueType*, const Type> ConstIterator; 95 96 SinglyLinkedList() 97 : fFirst(NULL) 98 , fLast(NULL) 99 , fCount(0) 100 { 101 } 102 ~SinglyLinkedList(); 103 104 ssize_t Count() const; 105 bool IsEmpty() const; 106 void MakeEmpty(); 107 108 status_t PushFront(const ValueType &data); 109 status_t PushBack(const ValueType &data); 110 111 void PopFront(); 112 113 Iterator Begin(); 114 ConstIterator Begin() const; 115 Iterator End(); 116 ConstIterator End() const; 117 Iterator Null(); 118 ConstIterator Null() const; 119 120 ssize_t Remove(const ValueType &value); 121 Iterator Erase(Iterator &pos); 122 123 protected: 124 friend class Iterator; 125 friend class ConstIterator; 126 127 inline NodeType *Allocate(const ValueType &data) { return fStrategy.Allocate(data); } 128 inline void Free(NodeType *node) { fStrategy.Free(node); } 129 inline ValueType& GetValue(NodeType *node) const { return fStrategy.GetValue(node); } 130 inline NodeType* GetNext(NodeType *node) const { return fStrategy.GetNext(node); } 131 inline NodeType* SetNext(NodeType *node, NodeType* next) const { return fStrategy.SetNext(node, next); } 132 133 NodeStrategy fStrategy; 134 135 NodeType *fFirst; 136 NodeType *fLast; 137 138 ssize_t fCount; 139 }; 140 141 //-------------------------------------------------------------------------- 142 // SinglyLinkedListIterator 143 //-------------------------------------------------------------------------- 144 145 template <class Value, class Reference, class Pointer, class Parent> 146 class SinglyLinkedListIterator { 147 public: 148 typedef SinglyLinkedListIterator<Value, Reference, Pointer, Parent> IteratorType; 149 typedef typename Parent::NodeType NodeType; 150 151 SinglyLinkedListIterator(); 152 SinglyLinkedListIterator(Parent *parent, NodeType *node, NodeType *previous); 153 SinglyLinkedListIterator(const IteratorType &ref); 154 155 bool operator==(const IteratorType &ref) const; 156 bool operator!=(const IteratorType &ref) const; 157 IteratorType &operator=(const IteratorType &ref); 158 inline Reference operator*() const; 159 inline Pointer operator->() const; 160 IteratorType &operator++(); 161 IteratorType operator++(int); 162 163 private: 164 Parent *fParent; 165 NodeType *fNode; 166 NodeType *fPrevious; 167 }; 168 169 #define _ITERATOR_TEMPLATE_LIST template <class Value, class Reference, class Pointer, class Parent> 170 #define _ITERATOR SinglyLinkedListIterator<Value, Reference, Pointer, Parent> 171 172 _ITERATOR_TEMPLATE_LIST 173 _ITERATOR::SinglyLinkedListIterator() 174 : fParent(NULL) 175 , fNode(NULL) 176 , fPrevious(NULL) 177 { 178 } 179 180 _ITERATOR_TEMPLATE_LIST 181 _ITERATOR::SinglyLinkedListIterator(Parent *parent, NodeType *node, NodeType *previous) 182 : fParent(parent) 183 , fNode(node) 184 , fPrevious(previous) 185 { 186 } 187 188 _ITERATOR_TEMPLATE_LIST 189 _ITERATOR::SinglyLinkedListIterator(const IteratorType &ref) 190 : fParent(ref.fParent) 191 , fNode(ref.fNode) 192 , fPrevious(ref.fPrevious) 193 { 194 } 195 196 _ITERATOR_TEMPLATE_LIST 197 bool 198 _ITERATOR::operator==(const _ITERATOR &ref) const 199 { 200 return fParent == ref.fParent && fNode == ref.fNode && fPrevious == ref.fPrevious; 201 } 202 203 _ITERATOR_TEMPLATE_LIST 204 bool 205 _ITERATOR::operator!=(const _ITERATOR &ref) const 206 { 207 return !operator==(ref); 208 } 209 210 _ITERATOR_TEMPLATE_LIST 211 _ITERATOR& 212 _ITERATOR::operator=(const _ITERATOR &ref) 213 { 214 fParent = ref.fParent; 215 fNode = ref.fNode; 216 fPrevious = ref.fPrevious; 217 return *this; 218 } 219 220 _ITERATOR_TEMPLATE_LIST 221 inline 222 Reference 223 _ITERATOR::operator*() const 224 { 225 return fParent->GetValue(fNode); 226 } 227 228 _ITERATOR_TEMPLATE_LIST 229 Pointer 230 _ITERATOR::operator->() const 231 { 232 return &(operator*()); 233 } 234 235 _ITERATOR_TEMPLATE_LIST 236 _ITERATOR& 237 _ITERATOR::operator++() { 238 if (fNode) { 239 fPrevious = fNode; 240 fNode = fParent->GetNext(fNode); 241 } 242 return *this; 243 } 244 245 _ITERATOR_TEMPLATE_LIST 246 _ITERATOR 247 _ITERATOR::operator++(int) { 248 IteratorType old = *this; 249 ++*this; 250 return old; 251 } 252 253 //-------------------------------------------------------------------------- 254 // SinglyLinkedList implementation 255 //-------------------------------------------------------------------------- 256 257 #define _SINGLY_LINKED_LIST_TEMPLATE_LIST template <class Value, class NodeStrategy> 258 #define _SINGLY_LINKED_LIST SinglyLinkedList<Value, NodeStrategy> 259 260 _SINGLY_LINKED_LIST_TEMPLATE_LIST 261 _SINGLY_LINKED_LIST::~SinglyLinkedList() 262 { 263 MakeEmpty(); 264 } 265 266 _SINGLY_LINKED_LIST_TEMPLATE_LIST 267 ssize_t 268 _SINGLY_LINKED_LIST::Count() const 269 { 270 return fCount; 271 } 272 273 _SINGLY_LINKED_LIST_TEMPLATE_LIST 274 bool 275 _SINGLY_LINKED_LIST::IsEmpty() const 276 { 277 return Count() == 0; 278 } 279 280 _SINGLY_LINKED_LIST_TEMPLATE_LIST 281 void 282 _SINGLY_LINKED_LIST::MakeEmpty() 283 { 284 for (NodeType *node = fFirst; node; ) { 285 NodeType* next = GetNext(node); 286 Free(node); 287 node = next; 288 } 289 fFirst = fLast = NULL; 290 fCount = 0; 291 } 292 293 _SINGLY_LINKED_LIST_TEMPLATE_LIST 294 status_t 295 _SINGLY_LINKED_LIST::PushFront(const ValueType &data) 296 { 297 status_t err = B_OK; 298 299 if (!fFirst) { 300 fFirst = fLast = Allocate(data); 301 if (fFirst) 302 SetNext(fFirst, NULL); 303 else 304 err = B_NO_MEMORY; 305 } else { 306 NodeType* node = Allocate(data); 307 if (node) { 308 SetNext(node, fFirst); 309 fFirst = node; 310 } else 311 err = B_NO_MEMORY; 312 } 313 314 if (!err) 315 ++fCount; 316 317 return err; 318 } 319 320 _SINGLY_LINKED_LIST_TEMPLATE_LIST 321 status_t 322 _SINGLY_LINKED_LIST::PushBack(const ValueType &data) 323 { 324 status_t err = B_OK; 325 326 if (!fLast) { 327 fFirst = fLast = Allocate(data); 328 if (fFirst) 329 SetNext(fFirst, NULL); 330 else 331 err = B_NO_MEMORY; 332 } else { 333 NodeType* node = Allocate(data); 334 if (node) { 335 SetNext(fLast, node); 336 SetNext(node, NULL); 337 fLast = node; 338 } else 339 err = B_NO_MEMORY; 340 } 341 342 if (!err) 343 ++fCount; 344 345 return err; 346 } 347 348 _SINGLY_LINKED_LIST_TEMPLATE_LIST 349 void 350 _SINGLY_LINKED_LIST::PopFront() 351 { 352 if (fFirst) { 353 if (fFirst == fLast) 354 fLast = NULL; 355 NodeType* temp = fFirst; 356 fFirst = GetNext(fFirst); 357 Free(temp); 358 --fCount; 359 } 360 } 361 362 _SINGLY_LINKED_LIST_TEMPLATE_LIST 363 _SINGLY_LINKED_LIST::Iterator 364 _SINGLY_LINKED_LIST::Begin() 365 { 366 return Iterator(this, fFirst, NULL); 367 } 368 369 _SINGLY_LINKED_LIST_TEMPLATE_LIST 370 _SINGLY_LINKED_LIST::ConstIterator 371 _SINGLY_LINKED_LIST::Begin() const 372 { 373 return ConstIterator(this, fFirst, NULL); 374 } 375 376 _SINGLY_LINKED_LIST_TEMPLATE_LIST 377 _SINGLY_LINKED_LIST::Iterator 378 _SINGLY_LINKED_LIST::End() 379 { 380 return Iterator(this, NULL, fLast); 381 } 382 383 _SINGLY_LINKED_LIST_TEMPLATE_LIST 384 _SINGLY_LINKED_LIST::ConstIterator 385 _SINGLY_LINKED_LIST::End() const 386 { 387 return ConstIterator(this, NULL, fLast); 388 } 389 390 _SINGLY_LINKED_LIST_TEMPLATE_LIST 391 _SINGLY_LINKED_LIST::Iterator 392 _SINGLY_LINKED_LIST::Null() 393 { 394 return Iterator(this, NULL, NULL); 395 } 396 397 _SINGLY_LINKED_LIST_TEMPLATE_LIST 398 _SINGLY_LINKED_LIST::ConstIterator 399 _SINGLY_LINKED_LIST::Null() const 400 { 401 return ConstIterator(this, NULL, NULL); 402 } 403 404 /*! \brief Removes all elements in the list whose value 405 matches \c value. 406 407 \return The number of elements removed. 408 */ 409 _SINGLY_LINKED_LIST_TEMPLATE_LIST 410 ssize_t 411 _SINGLY_LINKED_LIST::Remove(const ValueType &value) 412 { 413 ssize_t count = 0; 414 for (Iterator i = Begin(); i != End(); ) { 415 if (*i == value) { 416 i = Erase(i); 417 ++count; 418 } else { 419 ++i; 420 } 421 } 422 return count; 423 } 424 425 /*! \brief Removes the specified item from the list, returning 426 the item that previously followed \c pos. 427 428 Note that this operation invalidates any previously valid 429 iterators for the given container. 430 431 \return An iterator pointing to the item following \c pos 432 before the removal, or End() if pos is an invalid argument. 433 */ 434 _SINGLY_LINKED_LIST_TEMPLATE_LIST 435 _SINGLY_LINKED_LIST::Iterator 436 _SINGLY_LINKED_LIST::Erase(Iterator &pos) 437 { 438 if (pos.fNode) { 439 if (pos.fNode == fStart) { 440 if (pos.fNode != fLast) { 441 // Strictly first node in the list 442 fFirst = GetNext(pos.fNode); 443 Free(pos.fNode); 444 --fCount; 445 return Begin(); 446 } else { 447 // Only node in the list 448 fFist = fLast = NULL; 449 Free(pos.fNode); 450 --fCount; 451 return End(); 452 } 453 } else if (pos.fNode == fLast) { 454 // Strictly last node in the list 455 fLast = pos.fPrevious; 456 SetNext(fLast, NULL); 457 Free(pos.fNode); 458 --fCount; 459 return End(); 460 } else if (pos.fPrevious) { 461 // Neither first nor last, but at least valid 462 NodeType *next = GetNext(pos.fNode); 463 SetNext(pos.fPrevious, next); // fPrev->next = fNode->next 464 Free(pos.fNode); 465 --fCount; 466 return Iterator(this, next, pos.fPrevious); 467 } 468 } 469 470 // Invalid position for erasing 471 return End(); // Better to return Null()? 472 } 473 474 //------------------------------------------------------------------------------ 475 // Strategies 476 //------------------------------------------------------------------------------ 477 478 namespace Strategy { 479 namespace SinglyLinkedList { 480 481 template <class Node, Node* Node::* NextMember> 482 class User 483 { 484 public: 485 typedef Node NodeType; 486 typedef Node ValueType; 487 488 inline NodeType *Allocate(const ValueType &data) 489 { 490 return (NodeType*)&data; 491 } 492 493 inline void Free(NodeType *node) 494 { 495 } 496 497 inline ValueType& GetValue(NodeType *node) const { 498 return *node; 499 } 500 501 inline NodeType* GetNext(NodeType *node) const { 502 return node->*NextMember; 503 } 504 505 inline NodeType* SetNext(NodeType *node, NodeType* next) const { 506 return node->*NextMember = next; 507 } 508 }; 509 510 } // namespace SinglyLinkedList 511 } // namespace Strategy 512 513 #endif // #ifndef _SINGLY_LINKED_LIST_H_ 514