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