]>
Commit | Line | Data |
---|---|---|
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 | */ | |
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 | 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 | { | |
53918c82 | 63 | if (this==&iter) return *this; |
feb10c40 | 64 | fCurrent = iter.fCurrent; |
65 | return *this; | |
66 | } | |
67 | ||
68 | 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 | return a.fCurrent == b.fCurrent; | |
99 | } | |
100 | ||
101 | friend bool operator != (const ConstIterator& a, const ConstIterator& b) | |
102 | { | |
103 | 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 | Iterator() : ConstIterator(), fPrevious(NULL) {} | |
121 | ||
122 | Iterator(const Iterator& iter) : ConstIterator(iter), fPrevious(iter.fPrevious) {} | |
123 | ||
124 | Iterator(Node* current, Node* prev) : ConstIterator(current), fPrevious(prev) {} | |
125 | ||
126 | Iterator& operator = (const Iterator& iter) | |
127 | { | |
53918c82 | 128 | if (this==&iter) return *this; |
feb10c40 | 129 | ConstIterator::operator = (iter); |
130 | fPrevious = iter.fPrevious; | |
131 | return *this; | |
132 | } | |
133 | ||
134 | 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 | 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 | assert( ConstIterator::fCurrent != NULL ); | |
155 | Iterator copy = *this; | |
156 | fPrevious = ConstIterator::fCurrent; | |
157 | ConstIterator::fCurrent = ConstIterator::fCurrent->fNext; | |
158 | return copy; | |
159 | } | |
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 | fFirst(NULL), fNextFree(0), fMaxEntries(maxentries), fEntry(NULL) | |
182 | { | |
183 | // Allocate buffer space. | |
184 | fEntry = reinterpret_cast<NodeEntry*>( | |
185 | malloc( sizeof(NodeEntry) * fMaxEntries ) | |
186 | ); | |
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; | |
191 | } | |
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 | { | |
229 | Node* current = fFirst; | |
230 | while (current != NULL) | |
231 | { | |
232 | Node* temp = current; | |
233 | current = current->fNext; | |
234 | DeleteNode(temp); | |
235 | } | |
236 | // Delete the buffer space after all nodes are deleted, | |
237 | // else we will cause a crash. | |
238 | assert(fEntry != NULL); | |
239 | free(fEntry); | |
240 | } | |
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 | { | |
b1179a48 | 300 | temp = current; |
feb10c40 | 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 | Node* newnode = NewNode(); | |
320 | newnode->fNext = fFirst; | |
321 | fFirst = newnode; | |
322 | 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 | Node* current = fFirst; | |
512 | while (current != NULL) | |
513 | { | |
514 | Node* temp = current; | |
515 | current = current->fNext; | |
516 | DeleteNode(temp); | |
517 | } | |
518 | fFirst = NULL; | |
519 | } | |
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 | 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 | 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 | 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 | { | |
2a35bc39 | 599 | bool fFree; // Indicates if this block is free. |
feb10c40 | 600 | Node fNode; // The node structure. |
601 | }; | |
602 | ||
2a35bc39 | 603 | AliHLTUInt32_t fNextFree; // The next entry that is presumably free. |
feb10c40 | 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 | assert( fNextFree < fMaxEntries ); | |
615 | AliHLTUInt32_t i = fNextFree; | |
616 | while (not fEntry[i].fFree and i < fMaxEntries) i++; | |
617 | if (fEntry[i].fFree) | |
618 | { | |
619 | fEntry[i].fFree = false; | |
620 | fNextFree = (i+1) % fMaxEntries; | |
621 | return new (&fEntry[i].fNode) Node(); | |
622 | } | |
623 | i = 0; | |
624 | while (not fEntry[i].fFree and i < fNextFree) i++; | |
625 | if (fEntry[i].fFree) | |
626 | { | |
627 | fEntry[i].fFree = false; | |
628 | fNextFree = (i+1) % fMaxEntries; | |
629 | return new (&fEntry[i].fNode) Node(); | |
630 | } | |
631 | throw std::bad_alloc(); | |
632 | } | |
633 | ||
2a35bc39 | 634 | Node* NewNode(const DataType& data) throw(std::bad_alloc) |
feb10c40 | 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 | char* p = reinterpret_cast<char*>(node); | |
666 | p -= (sizeof(NodeEntry) - sizeof(Node)); | |
667 | NodeEntry* entry = reinterpret_cast<NodeEntry*>(p); | |
668 | entry->fFree = true; | |
669 | } | |
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 |