Line data Source code
1 : #ifndef ALIHLTMUONLIST_H
2 : #define ALIHLTMUONLIST_H
3 : /**************************************************************************
4 : * Copyright(c) 1998-2007, ALICE Experiment at CERN, All rights reserved. *
5 : * *
6 : * Author: The ALICE Off-line Project. *
7 : * Contributors are mentioned in the code where appropriate. *
8 : * *
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 : **************************************************************************/
17 :
18 : // $Id$
19 :
20 : /**
21 : * @file AliHLTMUONList.h
22 : * @author Artur Szostak <artursz@iafrica.com>
23 : * @date 29 May 2007
24 : * @brief Declaration of a singly linked-list class which preallocates memory to give faster online performance.
25 : */
26 :
27 : #include "AliHLTDataTypes.h"
28 : #include <ostream>
29 : #include <cassert>
30 : #include <cstdlib>
31 : #include <new>
32 :
33 : /**
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
36 : * online performance.
37 : */
38 : template <typename DataType>
39 : class AliHLTMUONList
40 : {
41 : protected:
42 :
43 : struct Node; // forward declaration for ConstIterator and Iterator
44 :
45 : public:
46 :
47 : /**
48 : * This is an iterator class which allows one to iterate through the list
49 : * using the prefix or postfix operators ++.
50 : */
51 : class ConstIterator
52 : {
53 : public:
54 :
55 0 : ConstIterator() : fCurrent(NULL) {}
56 :
57 0 : ConstIterator(const ConstIterator& iter) : fCurrent(iter.fCurrent) {}
58 :
59 0 : ConstIterator(Node* node) : fCurrent(node) {}
60 :
61 : ConstIterator& operator = (const ConstIterator& iter)
62 : {
63 0 : if (this==&iter) return *this;
64 0 : fCurrent = iter.fCurrent;
65 0 : return *this;
66 0 : }
67 :
68 0 : virtual ~ConstIterator() {} // Just to make gcc -Weffc++ option shutup.
69 :
70 : // Dereference operator returns the elements data.
71 : const DataType& operator * () const { return fCurrent->fData; }
72 :
73 : // Pointer dereferencing returns the elements data.
74 : const DataType* operator -> () const { return &fCurrent->fData; }
75 :
76 : // Move to the next element in the list.
77 : ConstIterator& operator ++ ()
78 : {
79 : assert( fCurrent != NULL );
80 : fCurrent = fCurrent->fNext;
81 : return *this;
82 : }
83 :
84 : // Move to the next element in the list.
85 : ConstIterator operator ++ (int)
86 : {
87 : assert( fCurrent != NULL );
88 : ConstIterator copy = *this;
89 : fCurrent = fCurrent->fNext;
90 : return copy;
91 : }
92 :
93 : // Typecast operator returns a pointer to the data.
94 : operator const DataType* () const { return &fCurrent->fData; }
95 :
96 : friend bool operator == (const ConstIterator& a, const ConstIterator& b)
97 : {
98 0 : return a.fCurrent == b.fCurrent;
99 : }
100 :
101 : friend bool operator != (const ConstIterator& a, const ConstIterator& b)
102 : {
103 0 : return a.fCurrent != b.fCurrent;
104 : }
105 :
106 : protected:
107 :
108 : friend class AliHLTMUONList;
109 : Node* fCurrent; // The pointer to the current element selected by the iterator.
110 : };
111 :
112 : /**
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.
115 : */
116 : class Iterator : public ConstIterator
117 : {
118 : public:
119 :
120 0 : Iterator() : ConstIterator(), fPrevious(NULL) {}
121 :
122 0 : Iterator(const Iterator& iter) : ConstIterator(iter), fPrevious(iter.fPrevious) {}
123 :
124 0 : Iterator(Node* current, Node* prev) : ConstIterator(current), fPrevious(prev) {}
125 :
126 : Iterator& operator = (const Iterator& iter)
127 : {
128 0 : if (this==&iter) return *this;
129 0 : ConstIterator::operator = (iter);
130 0 : fPrevious = iter.fPrevious;
131 0 : return *this;
132 0 : }
133 :
134 0 : virtual ~Iterator() {} // Just to make gcc -Weffc++ option shutup.
135 :
136 : // Dereference operator returns the elements data.
137 : DataType& operator * () { return ConstIterator::fCurrent->fData; }
138 :
139 : // Pointer dereferencing returns the elements data.
140 0 : DataType* operator -> () { return &ConstIterator::fCurrent->fData; }
141 :
142 : // Move to the next element in the list.
143 : Iterator& operator ++ ()
144 : {
145 : assert( ConstIterator::fCurrent != NULL );
146 : fPrevious = ConstIterator::fCurrent;
147 : ConstIterator::fCurrent = ConstIterator::fCurrent->fNext;
148 : return *this;
149 : }
150 :
151 : // Move to the next element in the list.
152 : Iterator operator ++ (int)
153 : {
154 0 : assert( ConstIterator::fCurrent != NULL );
155 0 : Iterator copy = *this;
156 0 : fPrevious = ConstIterator::fCurrent;
157 0 : ConstIterator::fCurrent = ConstIterator::fCurrent->fNext;
158 : return copy;
159 0 : }
160 :
161 : // Typecast operator returns a pointer to the data.
162 : operator DataType* ()
163 : {
164 : if (ConstIterator::fCurrent != NULL)
165 : return &ConstIterator::fCurrent->fData;
166 : else
167 : return NULL;
168 : }
169 :
170 : protected:
171 :
172 : friend class AliHLTMUONList;
173 : Node* fPrevious; // The pointer to the previous element.
174 : };
175 :
176 : /**
177 : * Constructor allocates a buffer to hold at least 'minentries' number
178 : * of nodes for the list.
179 : */
180 : AliHLTMUONList(AliHLTUInt32_t maxentries = 1024*4) :
181 0 : fFirst(NULL), fNextFree(0), fMaxEntries(maxentries), fEntry(NULL)
182 0 : {
183 : // Allocate buffer space.
184 0 : fEntry = reinterpret_cast<NodeEntry*>(
185 0 : malloc( sizeof(NodeEntry) * fMaxEntries )
186 : );
187 0 : if (fEntry == NULL) throw std::bad_alloc();
188 : // Set the availability flags.
189 0 : for (AliHLTUInt32_t i = 0; i < fMaxEntries; i++)
190 0 : fEntry[i].fFree = true;
191 0 : }
192 :
193 : /**
194 : * Deep copy the list.
195 : */
196 : AliHLTMUONList(const AliHLTMUONList& list) :
197 : fFirst(NULL), fNextFree(0), fMaxEntries(list.fMaxEntries),
198 : fEntry(NULL)
199 : {
200 : if (list.fFirst != NULL)
201 : {
202 : // First allocate the buffer space.
203 : fEntry = reinterpret_cast<NodeEntry*>(
204 : malloc( sizeof(NodeEntry) * fMaxEntries )
205 : );
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;
210 :
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)
216 : {
217 : current->fNext = NewNode(listcurrent->fData);
218 : current = current->fNext;
219 : listcurrent = listcurrent->fNext;
220 : }
221 : }
222 : }
223 :
224 : /**
225 : * Delete the list and release all allocated memory.
226 : */
227 : virtual ~AliHLTMUONList()
228 0 : {
229 0 : Node* current = fFirst;
230 0 : while (current != NULL)
231 : {
232 : Node* temp = current;
233 0 : current = current->fNext;
234 0 : DeleteNode(temp);
235 : }
236 : // Delete the buffer space after all nodes are deleted,
237 : // else we will cause a crash.
238 0 : assert(fEntry != NULL);
239 0 : free(fEntry);
240 0 : }
241 :
242 : /**
243 : * Deep copy the list.
244 : */
245 : AliHLTMUONList& operator = (const AliHLTMUONList& list)
246 : {
247 : if (list.fFirst == NULL)
248 : {
249 : Clear();
250 : return *this;
251 : }
252 : if (fFirst == NULL)
253 : {
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)
260 : {
261 : current->fNext = NewNode(listcurrent->fData);
262 : current = current->fNext;
263 : listcurrent = listcurrent->fNext;
264 : }
265 : return *this;
266 : }
267 :
268 : // At least the first node does not need to be created.
269 : fFirst->fData = list.fFirst->fData;
270 :
271 : Node* current = fFirst;
272 : Node* listcurrent = list.fFirst->fNext;
273 : while (listcurrent != NULL)
274 : {
275 : if (current->fNext == NULL)
276 : {
277 : // The list of 'this' object is shorter so we need
278 : // to create new nodes.
279 : do
280 : {
281 : current->fNext = NewNode(listcurrent->fData);
282 : current = current->fNext;
283 : listcurrent = listcurrent->fNext;
284 : }
285 : while (listcurrent != NULL);
286 : break;
287 : }
288 : current->fNext->fData = listcurrent->fData;
289 : current = current->fNext;
290 : listcurrent = listcurrent->fNext;
291 : }
292 :
293 : // Unlink the remaining nodes.
294 : Node* temp = current->fNext;
295 : current->fNext = NULL;
296 : current = temp;
297 : // Remove any excess nodes from 'this' list.
298 : while (current != NULL)
299 : {
300 : temp = current;
301 : current = current->fNext;
302 : DeleteNode(temp);
303 : }
304 :
305 : return *this;
306 : }
307 :
308 : /**
309 : * Returns true if the list is empty and false otherwise.
310 : */
311 : bool Empty() const { return fFirst == NULL; }
312 :
313 : /**
314 : * Adds a new element to the start of the linked list.
315 : * @return The pointer to the new element to fill its fields.
316 : */
317 : DataType* Add()
318 : {
319 0 : Node* newnode = NewNode();
320 0 : newnode->fNext = fFirst;
321 0 : fFirst = newnode;
322 0 : return &newnode->fData;
323 : }
324 :
325 : /**
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.
329 : */
330 : void Add(const DataType& data)
331 : {
332 : Node* newnode = NewNode(data);
333 : newnode->fNext = fFirst;
334 : fFirst = newnode;
335 : }
336 :
337 : /**
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.
343 : */
344 : DataType* AddUniquely(const DataType& data)
345 : {
346 : Iterator result = Find(data);
347 : if (result == ConstIterator(NULL))
348 : {
349 : DataType* newdata = Add();
350 : *newdata = data;
351 : return newdata;
352 : }
353 : else
354 : return result;
355 : }
356 :
357 : /**
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
361 : * entries there are.
362 : */
363 : void Remove(const AliHLTUInt32_t index)
364 : {
365 : Node* previous = NULL;
366 : Node* current = fFirst;
367 : for (AliHLTUInt32_t i = 0; i < index; i++)
368 : {
369 : assert( current != NULL );
370 : previous = current;
371 : current = current->fNext;
372 : }
373 : Node* temp;
374 : if (previous == NULL)
375 : {
376 : temp = fFirst;
377 : fFirst = fFirst->fNext;
378 : }
379 : else
380 : {
381 : temp = current;
382 : previous->fNext = current->fNext;
383 : }
384 : DeleteNode(temp);
385 : }
386 :
387 : /**
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.
391 : */
392 : bool Remove(const DataType& data)
393 : {
394 : Iterator current = Find(data);
395 : if (current != ConstIterator(NULL))
396 : {
397 : Remove(current);
398 : return true;
399 : }
400 : else
401 : return false;
402 : }
403 :
404 : /**
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.
409 : */
410 : void Remove(Iterator& iter)
411 : {
412 : Node* previous = iter.fPrevious;
413 : Node* current = iter.fCurrent;
414 : assert( current != NULL );
415 :
416 : Node* temp;
417 : if (previous == NULL)
418 : {
419 : temp = fFirst;
420 : fFirst = fFirst->fNext;
421 : }
422 : else
423 : {
424 : temp = current;
425 : previous->fNext = current->fNext;
426 : }
427 : DeleteNode(temp);
428 : }
429 :
430 : /**
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().
436 : */
437 : Iterator Find(const DataType& data)
438 : {
439 : Node* previous = NULL;
440 : Node* current = fFirst;
441 : while (current != NULL)
442 : {
443 : if (current->fData == data)
444 : return Iterator(current, previous);
445 : previous = current;
446 : current = current->fNext;
447 : }
448 : return End();
449 : }
450 :
451 : ConstIterator Find(const DataType& data) const
452 : {
453 : Node* current = fFirst;
454 : while (current != NULL)
455 : {
456 : if (current->fData == data)
457 : return ConstIterator(current);
458 : current = current->fNext;
459 : };
460 : return End();
461 : }
462 :
463 : /**
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().
471 : */
472 : template <typename PredicateType>
473 : Iterator Find(PredicateType predicate)
474 : {
475 : Node* previous = NULL;
476 : Node* current = fFirst;
477 : while (current != NULL)
478 : {
479 : if ( predicate(current->fData) )
480 : return Iterator(current, previous);
481 : previous = current;
482 : current = current->fNext;
483 : }
484 : return End();
485 : }
486 :
487 : template <typename PredicateType>
488 : ConstIterator Find(PredicateType predicate) const
489 : {
490 : Node* current = fFirst;
491 : while (current != NULL)
492 : {
493 : if ( predicate(current->fData) )
494 : return ConstIterator(current);
495 : current = current->fNext;
496 : }
497 : return End();
498 : }
499 :
500 : /**
501 : * Returns true if the list contains the specified element, else false.
502 : * @param data The value to search for in the list.
503 : */
504 : bool Contains(const DataType& data) const { return Find(data) != End(); }
505 :
506 : /**
507 : * This deletes all elements from the list.
508 : */
509 : void Clear()
510 : {
511 0 : Node* current = fFirst;
512 0 : while (current != NULL)
513 : {
514 : Node* temp = current;
515 0 : current = current->fNext;
516 0 : DeleteNode(temp);
517 : }
518 0 : fFirst = NULL;
519 0 : }
520 :
521 : /**
522 : * This deletes all elements from the list and resizes the buffer which
523 : * is used to store the entries for the list.
524 : */
525 : void Clear(AliHLTUInt32_t maxentries) throw(std::bad_alloc)
526 : {
527 : Clear();
528 :
529 : NodeEntry* newp = reinterpret_cast<NodeEntry*>(
530 : realloc(fEntry, sizeof(NodeEntry) * fMaxEntries)
531 : );
532 : if (newp == NULL) throw std::bad_alloc();
533 :
534 : // Set the availability flags for the node entries
535 : for (AliHLTUInt32_t i = fMaxEntries; i < maxentries; i++)
536 : fEntry[i].fFree = true;
537 :
538 : fEntry = newp;
539 : fMaxEntries = maxentries;
540 : fNextFree = 0;
541 : }
542 :
543 : /**
544 : * Returns an iterator to the first element of the list.
545 : */
546 0 : Iterator First() { return Iterator(fFirst, NULL); }
547 : ConstIterator First() const { return fFirst; }
548 :
549 : /**
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.
553 : */
554 0 : Iterator End() { return Iterator(NULL, NULL); }
555 : ConstIterator End() const { return ConstIterator(NULL); }
556 :
557 : /**
558 : * Counts and returns the number of elements in the list.
559 : */
560 : AliHLTUInt32_t Count() const
561 : {
562 : AliHLTUInt32_t n = 0;
563 : Node* current = fFirst;
564 : while (current != NULL)
565 : {
566 : n++;
567 : current = current->fNext;
568 : }
569 : return n;
570 : }
571 :
572 : protected:
573 :
574 : /**
575 : * The internal node structure for the linked list.
576 : */
577 : struct Node
578 : {
579 : Node* fNext; // Next element in the list.
580 : DataType fData; // The data for the current link.
581 :
582 0 : Node() : fNext(NULL), fData() {};
583 : Node(const DataType& data) : fNext(NULL), fData(data) {};
584 : Node(const Node& node) : fNext(node.fNext), fData(node.data) {};
585 :
586 : // Shallow copy the node.
587 : Node& operator = (const Node& node)
588 : {
589 : fNext = node.fNext;
590 : fData = node.fData;
591 : return *this;
592 : }
593 : };
594 :
595 : Node* fFirst; // The first element in the linked list.
596 :
597 : struct NodeEntry
598 : {
599 : bool fFree; // Indicates if this block is free.
600 : Node fNode; // The node structure.
601 : };
602 :
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.
606 :
607 : /**
608 : * Locates the next free location in the fEntry buffer, creates a new node
609 : * at that location and returns the pointer.
610 : */
611 : Node* NewNode() throw(std::bad_alloc)
612 : {
613 : //return new Node();
614 0 : assert( fNextFree < fMaxEntries );
615 : AliHLTUInt32_t i = fNextFree;
616 0 : while (not fEntry[i].fFree and i < fMaxEntries) i++;
617 0 : if (fEntry[i].fFree)
618 : {
619 0 : fEntry[i].fFree = false;
620 0 : fNextFree = (i+1) % fMaxEntries;
621 0 : return new (&fEntry[i].fNode) Node();
622 : }
623 : i = 0;
624 0 : while (not fEntry[i].fFree and i < fNextFree) i++;
625 0 : if (fEntry[i].fFree)
626 : {
627 0 : fEntry[i].fFree = false;
628 0 : fNextFree = (i+1) % fMaxEntries;
629 0 : return new (&fEntry[i].fNode) Node();
630 : }
631 0 : throw std::bad_alloc();
632 0 : }
633 :
634 : Node* NewNode(const DataType& data) throw(std::bad_alloc)
635 : {
636 : //return new Node(data);
637 : assert( fNextFree < fMaxEntries );
638 : AliHLTUInt32_t i = fNextFree;
639 : while (not fEntry[i].fFree and i < fMaxEntries) i++;
640 : if (fEntry[i].fFree)
641 : {
642 : fEntry[i].fFree = false;
643 : fNextFree = (i+1) % fMaxEntries;
644 : return new (&fEntry[i].fNode) Node(data);
645 : }
646 : i = 0;
647 : while (not fEntry[i].fFree and i < fNextFree) i++;
648 : if (fEntry[i].fFree)
649 : {
650 : fEntry[i].fFree = false;
651 : fNextFree = (i+1) % fMaxEntries;
652 : return new (&fEntry[i].fNode) Node(data);
653 : }
654 : throw std::bad_alloc();
655 : }
656 :
657 : /**
658 : * Destructs the node object.
659 : */
660 : void DeleteNode(Node* node)
661 : {
662 : //delete node;
663 : node->~Node();
664 : // Now mark the entry as free.
665 0 : char* p = reinterpret_cast<char*>(node);
666 0 : p -= (sizeof(NodeEntry) - sizeof(Node));
667 0 : NodeEntry* entry = reinterpret_cast<NodeEntry*>(p);
668 0 : entry->fFree = true;
669 0 : }
670 : };
671 :
672 :
673 : /**
674 : * Stream operator to write the list to std::ostream. The output is printed in
675 : * the following format: [element1, element2, ..., elementN]
676 : */
677 : template <typename DataType>
678 : std::ostream& operator << (
679 : std::ostream& stream, const AliHLTMUONList<DataType>& list
680 : )
681 : {
682 : typename AliHLTMUONList<DataType>::ConstIterator current;
683 : current = list.First();
684 : stream << "[";
685 : if (current == list.End())
686 : {
687 : stream << "]";
688 : return stream;
689 : }
690 : stream << (*current++);
691 : while (current != list.End())
692 : stream << ", " << (*current++);
693 : stream << "]";
694 : return stream;
695 : }
696 :
697 : #endif // ALIHLTMUONLIST_H
|
