HLT/MUON/AliHLTMUONList.h

   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                 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                         if (this==&iter) return *this;
  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                 {
 128                         if (this==&iter) return *this;
 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                 {
 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                 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         {
 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                 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
 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                 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