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