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                         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                 {
 298                         temp = current;
 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
 570 protected:
 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         {
 597                 bool fFree; // Indicates if this block is free.
 598                 Node fNode; // The node structure.
 599         };
 600
 601         AliHLTUInt32_t fNextFree;   // The next entry that is presumably free.
 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
 632         Node* NewNode(const DataType& data) throw(std::bad_alloc)
 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  */
 675 template <typename DataType>
 676 std::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