1 #ifndef ALIHLTMUONLIST_H
2 #define ALIHLTMUONLIST_H
3 /**************************************************************************
4 * Copyright(c) 1998-2007, ALICE Experiment at CERN, All rights reserved. *
6 * Author: The ALICE Off-line Project. *
7 * Contributors are mentioned in the code where appropriate. *
9 * Permission to use, copy, modify and distribute this software and its *
10 * documentation strictly for non-commercial purposes is hereby granted *
11 * without fee, provided that the above copyright notice appears in all *
12 * copies and that both the copyright notice and this permission notice *
13 * appear in the supporting documentation. The authors make no claims *
14 * about the suitability of this software for any purpose. It is *
15 * provided "as is" without express or implied warranty. *
16 **************************************************************************/
21 * @file AliHLTMUONList.h
22 * @author Artur Szostak <artursz@iafrica.com>
24 * @brief Declaration of a singly linked-list class which preallocates memory to give faster online performance.
27 #include "AliHLTDataTypes.h"
34 * The AliHLTMUONList class is a unidirectional linked-list which preallocates
35 * a large memory buffer where it stores its elements. This strategy gives higher
38 template <typename DataType>
43 struct Node; // forward declaration for ConstIterator and Iterator
48 * This is an iterator class which allows one to iterate through the list
49 * using the prefix or postfix operators ++.
55 ConstIterator() : fCurrent(NULL) {}
57 ConstIterator(const ConstIterator& iter) : fCurrent(iter.fCurrent) {}
59 ConstIterator(Node* node) : fCurrent(node) {}
61 ConstIterator& operator = (const ConstIterator& iter)
63 if (this==&iter) return *this;
64 fCurrent = iter.fCurrent;
68 virtual ~ConstIterator() {} // Just to make gcc -Weffc++ option shutup.
70 // Dereference operator returns the elements data.
71 const DataType& operator * () const { return fCurrent->fData; }
73 // Pointer dereferencing returns the elements data.
74 const DataType* operator -> () const { return &fCurrent->fData; }
76 // Move to the next element in the list.
77 ConstIterator& operator ++ ()
79 assert( fCurrent != NULL );
80 fCurrent = fCurrent->fNext;
84 // Move to the next element in the list.
85 ConstIterator operator ++ (int)
87 assert( fCurrent != NULL );
88 ConstIterator copy = *this;
89 fCurrent = fCurrent->fNext;
93 // Typecast operator returns a pointer to the data.
94 operator const DataType* () const { return &fCurrent->fData; }
96 friend bool operator == (const ConstIterator& a, const ConstIterator& b)
98 return a.fCurrent == b.fCurrent;
101 friend bool operator != (const ConstIterator& a, const ConstIterator& b)
103 return a.fCurrent != b.fCurrent;
108 friend class AliHLTMUONList;
109 Node* fCurrent; // The pointer to the current element selected by the iterator.
113 * This is an iterator class which allows one to iterate through the list
114 * just like ConstIterator, but also allows modification of the elements.
116 class Iterator : public ConstIterator
120 Iterator() : ConstIterator(), fPrevious(NULL) {}
122 Iterator(const Iterator& iter) : ConstIterator(iter), fPrevious(iter.fPrevious) {}
124 Iterator(Node* current, Node* prev) : ConstIterator(current), fPrevious(prev) {}
126 Iterator& operator = (const Iterator& iter)
128 if (this==&iter) return *this;
129 ConstIterator::operator = (iter);
130 fPrevious = iter.fPrevious;
134 virtual ~Iterator() {} // Just to make gcc -Weffc++ option shutup.
136 // Dereference operator returns the elements data.
137 DataType& operator * () { return ConstIterator::fCurrent->fData; }
139 // Pointer dereferencing returns the elements data.
140 DataType* operator -> () { return &ConstIterator::fCurrent->fData; }
142 // Move to the next element in the list.
143 Iterator& operator ++ ()
145 assert( ConstIterator::fCurrent != NULL );
146 fPrevious = ConstIterator::fCurrent;
147 ConstIterator::fCurrent = ConstIterator::fCurrent->fNext;
151 // Move to the next element in the list.
152 Iterator operator ++ (int)
154 assert( ConstIterator::fCurrent != NULL );
155 Iterator copy = *this;
156 fPrevious = ConstIterator::fCurrent;
157 ConstIterator::fCurrent = ConstIterator::fCurrent->fNext;
161 // Typecast operator returns a pointer to the data.
162 operator DataType* ()
164 if (ConstIterator::fCurrent != NULL)
165 return &ConstIterator::fCurrent->fData;
172 friend class AliHLTMUONList;
173 Node* fPrevious; // The pointer to the previous element.
177 * Constructor allocates a buffer to hold at least 'minentries' number
178 * of nodes for the list.
180 AliHLTMUONList(AliHLTUInt32_t maxentries = 1024*4) :
181 fFirst(NULL), fNextFree(0), fMaxEntries(maxentries), fEntry(NULL)
183 // Allocate buffer space.
184 fEntry = reinterpret_cast<NodeEntry*>(
185 malloc( sizeof(NodeEntry) * fMaxEntries )
187 if (fEntry == NULL) throw std::bad_alloc();
188 // Set the availability flags.
189 for (AliHLTUInt32_t i = 0; i < fMaxEntries; i++)
190 fEntry[i].fFree = true;
194 * Deep copy the list.
196 AliHLTMUONList(const AliHLTMUONList& list) :
197 fFirst(NULL), fNextFree(0), fMaxEntries(list.fMaxEntries),
200 if (list.fFirst != NULL)
202 // First allocate the buffer space.
203 fEntry = reinterpret_cast<NodeEntry*>(
204 malloc( sizeof(NodeEntry) * fMaxEntries )
206 if (fEntry == NULL) throw std::bad_alloc();
207 // Set the availability flags.
208 for (AliHLTUInt32_t i = 0; i < fMaxEntries; i++)
209 fEntry[i].fFree = true;
211 // Now copy the list by adding new node entries.
212 Add(list.fFirst->fData);
213 Node* current = fFirst;
214 Node* listcurrent = list.fFirst->fNext;
215 while (listcurrent != NULL)
217 current->fNext = NewNode(listcurrent->fData);
218 current = current->fNext;
219 listcurrent = listcurrent->fNext;
225 * Delete the list and release all allocated memory.
227 virtual ~AliHLTMUONList()
229 Node* current = fFirst;
230 while (current != NULL)
232 Node* temp = current;
233 current = current->fNext;
236 // Delete the buffer space after all nodes are deleted,
237 // else we will cause a crash.
238 assert(fEntry != NULL);
243 * Deep copy the list.
245 AliHLTMUONList& operator = (const AliHLTMUONList& list)
247 if (list.fFirst == NULL)
254 // The list in 'this' object is empty so we need to create
255 // new nodes for everything.
256 Add(list.fFirst->fData);
257 Node* current = fFirst;
258 Node* listcurrent = list.fFirst->fNext;
259 while (listcurrent != NULL)
261 current->fNext = NewNode(listcurrent->fData);
262 current = current->fNext;
263 listcurrent = listcurrent->fNext;
268 // At least the first node does not need to be created.
269 fFirst->fData = list.fFirst->fData;
271 Node* current = fFirst;
272 Node* listcurrent = list.fFirst->fNext;
273 while (listcurrent != NULL)
275 if (current->fNext == NULL)
277 // The list of 'this' object is shorter so we need
278 // to create new nodes.
281 current->fNext = NewNode(listcurrent->fData);
282 current = current->fNext;
283 listcurrent = listcurrent->fNext;
285 while (listcurrent != NULL);
288 current->fNext->fData = listcurrent->fData;
289 current = current->fNext;
290 listcurrent = listcurrent->fNext;
293 // Unlink the remaining nodes.
294 Node* temp = current->fNext;
295 current->fNext = NULL;
297 // Remove any excess nodes from 'this' list.
298 while (current != NULL)
301 current = current->fNext;
309 * Returns true if the list is empty and false otherwise.
311 bool Empty() const { return fFirst == NULL; }
314 * Adds a new element to the start of the linked list.
315 * @return The pointer to the new element to fill its fields.
319 Node* newnode = NewNode();
320 newnode->fNext = fFirst;
322 return &newnode->fData;
326 * Adds a new element to the start of the linked list and fills it with
327 * the data specified in 'data'.
328 * @param data The value to set the new element to.
330 void Add(const DataType& data)
332 Node* newnode = NewNode(data);
333 newnode->fNext = fFirst;
338 * Searches the list if the element 'data' is already in the list. If it
339 * is then a pointer to the existing element is returned, otherwise a new
340 * element is created and a pointer to it is returned.
341 * @param data The value to search for or set the new element to.
342 * @return A pointer to the existing or new element.
344 DataType* AddUniquely(const DataType& data)
346 Iterator result = Find(data);
347 if (result == ConstIterator(NULL))
349 DataType* newdata = Add();
358 * Removes the index'th element from the list.
359 * No error checking is done so there better be at least 'index' number
360 * of entries in the list. You can use Count() to find out how many
363 void Remove(const AliHLTUInt32_t index)
365 Node* previous = NULL;
366 Node* current = fFirst;
367 for (AliHLTUInt32_t i = 0; i < index; i++)
369 assert( current != NULL );
371 current = current->fNext;
374 if (previous == NULL)
377 fFirst = fFirst->fNext;
382 previous->fNext = current->fNext;
388 * Looks for the entry with the same values as 'data' and removes it
389 * from the list. If the entry could not be found then false is returned.
390 * However if it is found then it is deleted and true is returned.
392 bool Remove(const DataType& data)
394 Iterator current = Find(data);
395 if (current != ConstIterator(NULL))
405 * Removes the entry pointed to by the iterator which must have been
406 * extracted from the list with a call to First() and/or several calls
407 * to the iterators increment operators.
408 * @param iter The entry to remove from the list.
410 void Remove(Iterator& iter)
412 Node* previous = iter.fPrevious;
413 Node* current = iter.fCurrent;
414 assert( current != NULL );
417 if (previous == NULL)
420 fFirst = fFirst->fNext;
425 previous->fNext = current->fNext;
431 * Finds the first element with the same value as 'data' and returns an
432 * iterator to it. The iterator points to the end of the list i.e. End()
433 * if nothing was found.
434 * @param data The value to look for.
435 * @return The iterator pointing to the found element or End().
437 Iterator Find(const DataType& data)
439 Node* previous = NULL;
440 Node* current = fFirst;
441 while (current != NULL)
443 if (current->fData == data)
444 return Iterator(current, previous);
446 current = current->fNext;
451 ConstIterator Find(const DataType& data) const
453 Node* current = fFirst;
454 while (current != NULL)
456 if (current->fData == data)
457 return ConstIterator(current);
458 current = current->fNext;
464 * Finds the first element in the list that returns true for the predicate.
465 * That is, the first element for which the data evaluates to true in the
466 * test: predicate(fData). The iterator points to the end of the list
467 * i.e. End() if nothing was found.
468 * @param predicate Predicate that the data must return true for.
469 * This can usually be some one variable function.
470 * @return The iterator pointing to the found element or End().
472 template <typename PredicateType>
473 Iterator Find(PredicateType predicate)
475 Node* previous = NULL;
476 Node* current = fFirst;
477 while (current != NULL)
479 if ( predicate(current->fData) )
480 return Iterator(current, previous);
482 current = current->fNext;
487 template <typename PredicateType>
488 ConstIterator Find(PredicateType predicate) const
490 Node* current = fFirst;
491 while (current != NULL)
493 if ( predicate(current->fData) )
494 return ConstIterator(current);
495 current = current->fNext;
501 * Returns true if the list contains the specified element, else false.
502 * @param data The value to search for in the list.
504 bool Contains(const DataType& data) const { return Find(data) != End(); }
507 * This deletes all elements from the list.
511 Node* current = fFirst;
512 while (current != NULL)
514 Node* temp = current;
515 current = current->fNext;
522 * This deletes all elements from the list and resizes the buffer which
523 * is used to store the entries for the list.
525 void Clear(AliHLTUInt32_t maxentries) throw(std::bad_alloc)
529 NodeEntry* newp = reinterpret_cast<NodeEntry*>(
530 realloc(fEntry, sizeof(NodeEntry) * fMaxEntries)
532 if (newp == NULL) throw std::bad_alloc();
534 // Set the availability flags for the node entries
535 for (AliHLTUInt32_t i = fMaxEntries; i < maxentries; i++)
536 fEntry[i].fFree = true;
539 fMaxEntries = maxentries;
544 * Returns an iterator to the first element of the list.
546 Iterator First() { return Iterator(fFirst, NULL); }
547 ConstIterator First() const { return fFirst; }
550 * Returns an iterator pointing to the end of the list. The returned
551 * iterator does not actually point to a real data value but rather a
552 * sentinel value, and so it should not be dereferenced directly.
554 Iterator End() { return Iterator(NULL, NULL); }
555 ConstIterator End() const { return ConstIterator(NULL); }
558 * Counts and returns the number of elements in the list.
560 AliHLTUInt32_t Count() const
562 AliHLTUInt32_t n = 0;
563 Node* current = fFirst;
564 while (current != NULL)
567 current = current->fNext;
575 * The internal node structure for the linked list.
579 Node* fNext; // Next element in the list.
580 DataType fData; // The data for the current link.
582 Node() : fNext(NULL), fData() {};
583 Node(const DataType& data) : fNext(NULL), fData(data) {};
584 Node(const Node& node) : fNext(node.fNext), fData(node.data) {};
586 // Shallow copy the node.
587 Node& operator = (const Node& node)
595 Node* fFirst; // The first element in the linked list.
599 bool fFree; // Indicates if this block is free.
600 Node fNode; // The node structure.
603 AliHLTUInt32_t fNextFree; // The next entry that is presumably free.
604 AliHLTUInt32_t fMaxEntries; // The number of node entries that can be stored in fEntries.
605 NodeEntry* fEntry; // Buffer of preallocated node entries.
608 * Locates the next free location in the fEntry buffer, creates a new node
609 * at that location and returns the pointer.
611 Node* NewNode() throw(std::bad_alloc)
614 assert( fNextFree < fMaxEntries );
615 AliHLTUInt32_t i = fNextFree;
616 while (not fEntry[i].fFree and i < fMaxEntries) i++;
619 fEntry[i].fFree = false;
620 fNextFree = (i+1) % fMaxEntries;
621 return new (&fEntry[i].fNode) Node();
624 while (not fEntry[i].fFree and i < fNextFree) i++;
627 fEntry[i].fFree = false;
628 fNextFree = (i+1) % fMaxEntries;
629 return new (&fEntry[i].fNode) Node();
631 throw std::bad_alloc();
634 Node* NewNode(const DataType& data) throw(std::bad_alloc)
636 //return new Node(data);
637 assert( fNextFree < fMaxEntries );
638 AliHLTUInt32_t i = fNextFree;
639 while (not fEntry[i].fFree and i < fMaxEntries) i++;
642 fEntry[i].fFree = false;
643 fNextFree = (i+1) % fMaxEntries;
644 return new (&fEntry[i].fNode) Node(data);
647 while (not fEntry[i].fFree and i < fNextFree) i++;
650 fEntry[i].fFree = false;
651 fNextFree = (i+1) % fMaxEntries;
652 return new (&fEntry[i].fNode) Node(data);
654 throw std::bad_alloc();
658 * Destructs the node object.
660 void DeleteNode(Node* node)
664 // Now mark the entry as free.
665 char* p = reinterpret_cast<char*>(node);
666 p -= (sizeof(NodeEntry) - sizeof(Node));
667 NodeEntry* entry = reinterpret_cast<NodeEntry*>(p);
674 * Stream operator to write the list to std::ostream. The output is printed in
675 * the following format: [element1, element2, ..., elementN]
677 template <typename DataType>
678 std::ostream& operator << (
679 std::ostream& stream, const AliHLTMUONList<DataType>& list
682 typename AliHLTMUONList<DataType>::ConstIterator current;
683 current = list.First();
685 if (current == list.End())
690 stream << (*current++);
691 while (current != list.End())
692 stream << ", " << (*current++);
697 #endif // ALIHLTMUONLIST_H