HLT/trigger/AliHLTTriggerDomain.cxx

   1 /**************************************************************************
   2  * This file is property of and copyright by the ALICE HLT Project        *
   3  * ALICE Experiment at CERN, All rights reserved.                         *
   4  *                                                                        *
   5  * Primary Authors: Artur Szostak <artursz@iafrica.com>                   *
   6  *                  for The ALICE HLT Project.                            *
   7  *                                                                        *
   8  * Permission to use, copy, modify and distribute this software and its   *
   9  * documentation strictly for non-commercial purposes is hereby granted   *
  10  * without fee, provided that the above copyright notice appears in all   *
  11  * copies and that both the copyright notice and this permission notice   *
  12  * appear in the supporting documentation. The authors make no claims     *
  13  * about the suitability of this software for any purpose. It is          *
  14  * provided "as is" without express or implied warranty.                  *
  15  **************************************************************************/
  16
  17 /// @file   AliHLTTriggerDomain.cxx
  18 /// @author Artur Szostak <artursz@iafrica.com>
  19 /// @date   19 Nov 2008
  20 /// @brief  Implementation of the AliHLTTriggerDomain class.
  21 ///
  22 /// The trigger domain class is the set of HLT raw data block types that should
  23 /// be readout and sent to HLTOUT.
  24
  25 #include "AliHLTTriggerDomain.h"
  26 #include "AliHLTDomainEntry.h"
  27 #include "Riostream.h"
  28
  29 ClassImp(AliHLTTriggerDomain)
  30
  31
  32 AliHLTTriggerDomain::AliHLTTriggerDomain() :
  33   TObject(), fEntries(AliHLTDomainEntry::Class(), 10)
  34 {
  35   // Default constructor.
  36 }
  37
  38
  39 AliHLTTriggerDomain::AliHLTTriggerDomain(const AliHLTTriggerDomain& domain) :
  40   TObject(domain),
  41   fEntries(AliHLTDomainEntry::Class(), domain.fEntries.GetEntriesFast())
  42 {
  43   // Copy constructor performs a deep copy.
  44   // See header file for more details.
  45
  46   for (Int_t i = 0; i < domain.fEntries.GetEntriesFast(); i++)
  47   {
  48     const AliHLTDomainEntry* entry = static_cast<const AliHLTDomainEntry*>( domain.fEntries[i] );
  49     new (fEntries[fEntries.GetEntriesFast()]) AliHLTDomainEntry(*entry);
  50   }
  51 }
  52
  53
  54 AliHLTTriggerDomain::~AliHLTTriggerDomain()
  55 {
  56   // Default destructor.
  57 }
  58
  59
  60 void AliHLTTriggerDomain::Add(const AliHLTDomainEntry& entry)
  61 {
  62   // Adds a new domain entry to the trigger domain.
  63   // See header file for more details.
  64
  65   AliHLTDomainEntry intersect;
  66   bool alreadyInSet = false;
  67
  68   // Get the initial size of the fEntries array since we might add things to the
  69   // end during the calculation.
  70   Int_t count = fEntries.GetEntriesFast();
  71
  72   // Go through each entry that is already in fEntries and see if we can remove
  73   // it because it will become redundant, or if we need to patch exclusion entries
  74   // by adding inclusive intersects, or if we do not even need to add the new entry
  75   // because it is already part of the trigger domain.
  76   for (Int_t i = 0; i < count; i++)
  77   {
  78     AliHLTDomainEntry* ientry = static_cast<AliHLTDomainEntry*>(fEntries[i]);
  79     if (ientry->Inclusive())
  80     {
  81       if (entry.SubsetOf(*ientry))
  82       {
  83         alreadyInSet = true;
  84       }
  85       else if (ientry->SubsetOf(entry))
  86       {
  87         ientry->SetBit(14, true);  // mark for removal.
  88       }
  89     }
  90     else
  91     {
  92       if (ientry->SubsetOf(entry))
  93       {
  94         ientry->SetBit(14, true);  // mark for removal.
  95       }
  96       else if (entry.SubsetOf(*ientry))
  97       {
  98         alreadyInSet = false;
  99       }
 100       else if (ientry->IntersectWith(entry, intersect))
 101       {
 102         MarkForDeletionSubsetsOf(intersect, count);
 103         new (fEntries[fEntries.GetEntriesFast()]) AliHLTDomainEntry(kFALSE, intersect);
 104       }
 105     }
 106   }
 107
 108   // Check if we need to add the new entry.
 109   if (not alreadyInSet)
 110   {
 111     MarkForDeletionSubsetsOf(entry, count);
 112     new (fEntries[fEntries.GetEntriesFast()]) AliHLTDomainEntry(kFALSE, entry);
 113   }
 114   RemoveMarkedEntries();
 115 }
 116
 117
 118 void AliHLTTriggerDomain::Add(const AliHLTComponentDataType& datatype)
 119 {
 120   // Adds a new domain entry with the given data type to the trigger domain.
 121   // But the data block specification is set to the any matching wild card.
 122   // See header file for more details.
 123
 124   Add(AliHLTDomainEntry(datatype));
 125 }
 126
 127
 128 void AliHLTTriggerDomain::Add(const char* blocktype, const char* origin)
 129 {
 130   // Adds a new domain entry with the given data type and origin to the trigger domain.
 131   // But the data block specification is set to the any matching wild card.
 132   // See header file for more details.
 133
 134   Add(AliHLTDomainEntry(blocktype, origin));
 135 }
 136
 137
 138 void AliHLTTriggerDomain::Add(const AliHLTComponentDataType& datatype, UInt_t spec)
 139 {
 140   // Adds a new domain entry to the trigger domain with the data type and data block
 141   // specification bits.
 142   // See header file for more details.
 143
 144   Add(AliHLTDomainEntry(datatype, spec));
 145 }
 146
 147
 148 void AliHLTTriggerDomain::Add(const char* blocktype, const char* origin, UInt_t spec)
 149 {
 150   // Adds a new domain entry to the trigger domain with the given data type, origin
 151   // and data block specification bits.
 152   // See header file for more details.
 153
 154   Add(AliHLTDomainEntry(blocktype, origin, spec));
 155 }
 156
 157
 158 void AliHLTTriggerDomain::Remove(const AliHLTDomainEntry& entry)
 159 {
 160   // Removes the given domain entry from the trigger domain.
 161   // See header file for more details.
 162
 163   AliHLTDomainEntry intersect;
 164   bool addToExcludeSet = false;
 165
 166   // Get the initial size of the fEntries array since we might add things to the
 167   // end during the calculation.
 168   Int_t count = fEntries.GetEntriesFast();
 169
 170   // We need to go through all existing entries and see if they need to be removed
 171   // because they would become redundant when we add the new 'entry' to the end of
 172   // the fEntries list. We also need to check if the new entry needs to be added
 173   // at all because the trigger domain might already not contain those entries.
 174   // Lastly, some intersection entries might need to be added to patch up existing
 175   // inclusive trigger domain entries (rules / patterns).
 176   for (Int_t i = 0; i < count; i++)
 177   {
 178     AliHLTDomainEntry* ientry = static_cast<AliHLTDomainEntry*>(fEntries[i]);
 179     if (ientry->Inclusive())
 180     {
 181       if (ientry->SubsetOf(entry))
 182       {
 183         ientry->SetBit(14, true);  // mark for removal.
 184       }
 185       else if (entry.SubsetOf(*ientry))
 186       {
 187         addToExcludeSet = true;
 188       }
 189       else if (ientry->IntersectWith(entry, intersect))
 190       {
 191         new (fEntries[fEntries.GetEntriesFast()]) AliHLTDomainEntry(kTRUE, intersect);
 192       }
 193     }
 194     else
 195     {
 196       if (entry.SubsetOf(*ientry))
 197       {
 198         addToExcludeSet = false;
 199       }
 200       else if (ientry->SubsetOf(entry))
 201       {
 202         ientry->SetBit(14, true);  // mark for removal.
 203       }
 204     }
 205   }
 206
 207   // Check if we need to add the new entry.
 208   if (addToExcludeSet)
 209   {
 210     MarkForDeletionSubsetsOf(entry, count);
 211     new (fEntries[fEntries.GetEntriesFast()]) AliHLTDomainEntry(kTRUE, entry);
 212   }
 213   RemoveMarkedEntries();
 214 }
 215
 216
 217 void AliHLTTriggerDomain::Remove(const AliHLTComponentDataType& datatype)
 218 {
 219   // Removes the domain entries that have the given data type from the trigger domain.
 220   // See header file for more details.
 221
 222   Remove(AliHLTDomainEntry(datatype));
 223 }
 224
 225
 226 void AliHLTTriggerDomain::Remove(const char* blocktype, const char* origin)
 227 {
 228   // Removes the domain entries that have the given data type and origin from the
 229   // trigger domain.
 230   // See header file for more details.
 231
 232   Remove(AliHLTDomainEntry(blocktype, origin));
 233 }
 234
 235
 236 void AliHLTTriggerDomain::Remove(const AliHLTComponentDataType& datatype, UInt_t spec)
 237 {
 238   // Removes the domain entries that have the given data type and data block
 239   // specification bits from the trigger domain.
 240   // See header file for more details.
 241
 242   Remove(AliHLTDomainEntry(datatype, spec));
 243 }
 244
 245
 246 void AliHLTTriggerDomain::Remove(const char* blocktype, const char* origin, UInt_t spec)
 247 {
 248   // Removes the domain entries that have the given data type, origin and data
 249   // block specification bits from the trigger domain.
 250   // See header file for more details.
 251
 252   Remove(AliHLTDomainEntry(blocktype, origin, spec));
 253 }
 254
 255
 256 bool AliHLTTriggerDomain::Contains(const AliHLTDomainEntry& entry) const
 257 {
 258   // Checks to see if the given domain entry is part of the trigger domain set.
 259   // See header file for more details.
 260
 261   // Simply go through the whole list of fEntries and for each entry see if the
 262   // given domain entry 'entry' being checked matches. If there is a match then
 263   // update the result depending on the entry type. i.e. set to false if the entry
 264   // in fEntries is an exclusion and set to true if it is an inclusion.
 265   bool result = false;
 266   for (Int_t i = 0; i < fEntries.GetEntriesFast(); i++)
 267   {
 268     const AliHLTDomainEntry* ientry = static_cast<const AliHLTDomainEntry*>(fEntries[i]);
 269     if (ientry->Inclusive())
 270     {
 271       if (*ientry == entry) result = true;
 272     }
 273     else
 274     {
 275       if (entry.SubsetOf(*ientry)) result = false;
 276     }
 277   }
 278   return result;
 279 }
 280
 281
 282 bool AliHLTTriggerDomain::IncludeInReadout(const AliHLTComponentBlockData* block) const
 283 {
 284   // Checks to see if the given data block is part of the trigger domain set and
 285   // should be readout.
 286   // See header file for more details.
 287
 288   // Same algorithm as for Contains() but applied directly to the data block
 289   // descriptor structure.
 290   AliHLTDomainEntry blockEntry(block->fDataType, block->fSpecification);
 291   bool result = false;
 292   for (Int_t i = 0; i < fEntries.GetEntriesFast(); i++)
 293   {
 294     const AliHLTDomainEntry* entry = static_cast<const AliHLTDomainEntry*>(fEntries[i]);
 295     if (entry->Inclusive())
 296     {
 297       if (*entry == block) result = true;
 298     }
 299     else
 300     {
 301       if (blockEntry.SubsetOf(*entry)) result = false;
 302     }
 303   }
 304   return result;
 305 }
 306
 307
 308 void AliHLTTriggerDomain::Clear(Option_t* option)
 309 {
 310   // Clears the trigger domain (Removes all entries).
 311
 312   fEntries.Clear(option);
 313 }
 314
 315
 316 void AliHLTTriggerDomain::Print(Option_t* /*option*/) const
 317 {
 318   // Prints the trigger domain entries in the order that they are applied.
 319   // See header file for more details.
 320
 321   cout << "Trigger domain rules (applied in order of first to last):" << endl;
 322   for (Int_t i = 0; i < fEntries.GetEntriesFast(); i++)
 323   {
 324     const AliHLTDomainEntry* entry = static_cast<const AliHLTDomainEntry*>( fEntries[i] );
 325     if (entry->Inclusive())
 326     {
 327       cout << "Include ";
 328     }
 329     else
 330     {
 331       cout << "Exclude ";
 332     }
 333     entry->Print();
 334   }
 335   if (fEntries.GetEntriesFast() == 0)
 336   {
 337     cout << "(empty)" << endl;
 338   }
 339 }
 340
 341
 342 AliHLTTriggerDomain& AliHLTTriggerDomain::operator = (const AliHLTTriggerDomain& domain)
 343 {
 344   // Assignment operator performs a deep copy.
 345   // See header file for more details.
 346
 347   if (this == &domain) return *this;
 348   TObject::operator = (domain);
 349   fEntries.Clear();
 350   for (Int_t i = 0; i < domain.fEntries.GetEntriesFast(); i++)
 351   {
 352     const AliHLTDomainEntry* entry = static_cast<const AliHLTDomainEntry*>( domain.fEntries[i] );
 353     new (fEntries[fEntries.GetEntriesFast()]) AliHLTDomainEntry(*entry);
 354   }
 355   return *this;
 356 }
 357
 358
 359 AliHLTTriggerDomain& AliHLTTriggerDomain::operator |= (const AliHLTTriggerDomain& domain)
 360 {
 361   // This operator performs the set union.
 362   // See header file for more details.
 363
 364   // Note that we partition the fEntries array into 3 regions for this calculation.
 365   //   - 0..entriesCount-1 : contains the initial entries of this trigger domain.
 366   //   - entriesCount..startOfIntersects-1 : is space reserved for the new entries
 367   //       from 'domain'.
 368   //   - startOfIntersects..fEntries.GetEntriesFast()-1 : This will grow as we add
 369   //       all the new domain intersections created during the calculation.
 370   //
 371   // Get the number of entries now before we start adding more entries from 'domain'.
 372   Int_t count = fEntries.GetEntriesFast();
 373   // Mark the start location for new intersection entries.
 374   Int_t startOfIntersects = count + domain.fEntries.GetEntriesFast();
 375   Int_t newIndex = startOfIntersects;
 376
 377   // Allocate and initialise a single block of memory so that we do not call new twice.
 378   bool* buffer = new bool[startOfIntersects];
 379   for (Int_t i = 0; i < startOfIntersects; i++) buffer[i] = false;
 380   bool* removeThisEntry = buffer;
 381   bool* removeDomainEntry = buffer + count;
 382
 383   AliHLTDomainEntry intersect;
 384
 385   // The idea behind this algorithm is that we need to add all inclusion domain
 386   // entries from 'domain' to this object that will not be redundant, but for
 387   // the exclusion entries we patch the fEntries rule set by adding the appropriate
 388   // intersections to the end of fEntries.
 389   for (Int_t i = 0; i < domain.fEntries.GetEntriesFast(); i++)
 390   {
 391     const AliHLTDomainEntry* newEntry = static_cast<const AliHLTDomainEntry*>( domain.fEntries[i] );
 392     for (Int_t j = 0; j < count; j++)
 393     {
 394       const AliHLTDomainEntry* currentEntry = static_cast<const AliHLTDomainEntry*>( fEntries[j] );
 395       if (currentEntry->Inclusive() and newEntry->Inclusive())
 396       {
 397         // If either entry is a subset of the other then we do not need to add
 398         // both, so make sure to remove the one that is redundant.
 399         if (newEntry->SubsetOf(*currentEntry))
 400         {
 401           removeDomainEntry[i] = true;
 402         }
 403         else if (currentEntry->SubsetOf(*newEntry))
 404         {
 405           removeThisEntry[j] = true;
 406         }
 407       }
 408       else
 409       {
 410         if (newEntry->IntersectWith(*currentEntry, intersect))
 411         {
 412           // We can remove all intersections that were already added that will
 413           // become redundant when this intersection is added to fEntries.
 414           MarkForDeletionSubsetsOf(intersect, startOfIntersects);
 415
 416           // Make the new intersection entry an exclusion if the newEntry and
 417           // currentEntry flags are the same.
 418           bool exclude = newEntry->Exclusive() == currentEntry->Exclusive();
 419           new (fEntries[newIndex++]) AliHLTDomainEntry(exclude, intersect);
 420
 421           // We can also remove entries that are subsets of another entry in the
 422           // opposite list, since they will be redundant when everything is merged
 423           // together. For example, remove entry x from fEntries if it is a subset
 424           // of entry y in domain.fEntries.
 425           if (currentEntry->IdenticalTo(intersect)) removeThisEntry[j] = true;
 426           if (newEntry->IdenticalTo(intersect)) removeDomainEntry[i] = true;
 427         }
 428       }
 429     }
 430   }
 431
 432   MergeEntries(removeThisEntry, count, removeDomainEntry, startOfIntersects, domain);
 433   delete [] buffer;
 434   Optimise();
 435   return *this;
 436 }
 437
 438
 439 AliHLTTriggerDomain& AliHLTTriggerDomain::operator ^= (const AliHLTTriggerDomain& domain)
 440 {
 441   // This operator performs the set union, less the set intersect (something like and xor).
 442   // See header file for more details.
 443
 444   // Note that we partition the fEntries array into 3 regions for this calculation.
 445   //   - 0..entriesCount-1 : contains the initial entries of this trigger domain.
 446   //   - entriesCount..startOfIntersects-1 : is space reserved for the new entries
 447   //       from 'domain'.
 448   //   - startOfIntersects..fEntries.GetEntriesFast()-1 : This will grow as we add
 449   //       all the new domain intersections created during the calculation.
 450   //
 451   // Get the number of entries now before we start adding more entries from 'domain'.
 452   Int_t count = fEntries.GetEntriesFast();
 453   // Mark the start location for new intersection entries.
 454   Int_t startOfIntersects = count + domain.fEntries.GetEntriesFast();
 455   Int_t newIndex = startOfIntersects;
 456
 457   // Allocate and initialise a single block of memory so that we do not call new twice.
 458   bool* buffer = new bool[startOfIntersects];
 459   for (Int_t i = 0; i < startOfIntersects; i++) buffer[i] = false;
 460   bool* removeThisEntry = buffer;
 461   bool* removeDomainEntry = buffer + count;
 462
 463   AliHLTDomainEntry intersect;
 464
 465   // This algorithm is similar to the case for the set union (operator |=), except
 466   // that we make sure to remove from the trigger domain all parts where the entries
 467   // from fEntries and domain.fEntries intersect.
 468   // This is done by adding the intersections to the end of fEntries such that they
 469   // effectively remove those overlapping trigger domain entries when calculating
 470   // IncludeInReadout() or Contains().
 471   for (Int_t i = 0; i < domain.fEntries.GetEntriesFast(); i++)
 472   {
 473     const AliHLTDomainEntry* newEntry = static_cast<const AliHLTDomainEntry*>( domain.fEntries[i] );
 474     for (Int_t j = 0; j < count; j++)
 475     {
 476       const AliHLTDomainEntry* currentEntry = static_cast<const AliHLTDomainEntry*>( fEntries[j] );
 477       if (newEntry->IntersectWith(*currentEntry, intersect))
 478       {
 479         // We can remove all intersections that were already added that will
 480         // become redundant when this intersection is added to fEntries.
 481         MarkForDeletionSubsetsOf(intersect, startOfIntersects);
 482
 483         // Make the new intersection entry an exclusion if the newEntry and
 484         // currentEntry flags are the same.
 485         bool exclude = newEntry->Exclusive() == currentEntry->Exclusive();
 486         new (fEntries[newIndex++]) AliHLTDomainEntry(exclude, intersect);
 487
 488         // We can also remove entries that are subsets of another entry in the
 489         // opposite list, since they will be redundant when everything is merged
 490         // together. For example, remove entry x from fEntries if it is a subset
 491         // of entry y in domain.fEntries.
 492         if (currentEntry->IdenticalTo(intersect)) removeThisEntry[j] = true;
 493         if (newEntry->IdenticalTo(intersect)) removeDomainEntry[i] = true;
 494       }
 495     }
 496   }
 497
 498   MergeEntries(removeThisEntry, count, removeDomainEntry, startOfIntersects, domain);
 499   delete [] buffer;
 500   Optimise();
 501   return *this;
 502 }
 503
 504
 505 AliHLTTriggerDomain& AliHLTTriggerDomain::operator -= (const AliHLTTriggerDomain& domain)
 506 {
 507   // This operator performs the set difference.
 508   // See header file for more details.
 509
 510   // Mark the number of entries in fEntries now before we start adding more
 511   // entries from 'domain' or intersections.
 512   Int_t startOfIntersects = fEntries.GetEntriesFast();
 513   Int_t newIndex = startOfIntersects;
 514
 515   AliHLTDomainEntry intersect;
 516
 517   // To compute the set difference we need to remove all all parts that overlap
 518   // with 'domain'. i.e. we need to find all the intersects between the domain
 519   // entries in fEntries and those in domain.fEntries, and add the intersects
 520   // to the fEntries list, such that they will cancel or remove the overlapping
 521   // parts of the two trigger domains.
 522   for (Int_t i = 0; i < domain.fEntries.GetEntriesFast(); i++)
 523   {
 524     const AliHLTDomainEntry* checkEntry = static_cast<const AliHLTDomainEntry*>( domain.fEntries[i] );
 525     if (checkEntry->Inclusive())
 526     {
 527       // For inclusive entries we need to find the overlaps with the inclusive
 528       // entries in fEntries and add exclusive entries that will remove that
 529       // part of the trigger domain set.
 530       for (Int_t j = 0; j < startOfIntersects; j++)
 531       {
 532         AliHLTDomainEntry* currentEntry = static_cast<AliHLTDomainEntry*>( fEntries[j] );
 533
 534         // We only need to consider the case where both entries are inclusive,
 535         // since an exclusion in fEntries already eliminates those data blocks
 536         // from the trigger domain set.
 537         if (currentEntry->Exclusive()) continue;
 538
 539         if (checkEntry->IntersectWith(*currentEntry, intersect))
 540         {
 541           // We can remove all intersections that were already added that will
 542           // become redundant when this intersection is added to fEntries.
 543           MarkForDeletionSubsetsOf(intersect, startOfIntersects);
 544
 545           new (fEntries[newIndex++]) AliHLTDomainEntry(kTRUE, intersect);
 546           if (currentEntry->IdenticalTo(intersect))
 547           {
 548             currentEntry->SetBit(14, true);
 549           }
 550         }
 551       }
 552     }
 553     else
 554     {
 555       // For an exclusive entry in 'domain' we need to find the intersections with
 556       // all of fEntries and re-apply these with the same exclude flags.
 557       for (Int_t j = 0; j < startOfIntersects; j++)
 558       {
 559         AliHLTDomainEntry* currentEntry = static_cast<AliHLTDomainEntry*>( fEntries[j] );
 560         if (checkEntry->IntersectWith(*currentEntry, intersect))
 561         {
 562           // We can remove all intersections that were already added that will
 563           // become redundant when this intersection is added to fEntries.
 564           MarkForDeletionSubsetsOf(intersect, startOfIntersects);
 565
 566           new (fEntries[newIndex++]) AliHLTDomainEntry(currentEntry->Exclusive(), intersect);
 567         }
 568       }
 569     }
 570   }
 571
 572   RemoveMarkedEntries();
 573   Optimise();
 574   return *this;
 575 }
 576
 577
 578 AliHLTTriggerDomain AliHLTTriggerDomain::operator ~ () const
 579 {
 580   // Performs a set complement of the trigger domain.
 581
 582   // The set complement is calculated by creating a new trigger domain which
 583   // accepts all possible data blocks, and then apply all the trigger domain
 584   // entries (rules / patterns) from top to bottom, but apply them with the
 585   // opposite meaning. For example, this->fEntries contains an inclusive domain
 586   // entry then remove it from the new trigger domain 'result', but if it is
 587   // an exclusion then add it.
 588   AliHLTTriggerDomain result;
 589   result.Add(kAliHLTAnyDataType);
 590   for (Int_t i = 0; i < fEntries.GetEntriesFast(); i++)
 591   {
 592     const AliHLTDomainEntry* entry = static_cast<const AliHLTDomainEntry*>( fEntries[i] );
 593     if (entry->Inclusive())
 594     {
 595       result.Remove(*entry);
 596     }
 597     else
 598     {
 599       result.Add(*entry);
 600     }
 601   }
 602   return result;
 603 }
 604
 605
 606 AliHLTTriggerDomain AliHLTTriggerDomain::operator & (const AliHLTTriggerDomain& domain) const
 607 {
 608   // This operator finds the set intersect.
 609   // See header file for more details.
 610
 611   AliHLTTriggerDomain result;
 612   Int_t newIndex = 0;
 613   AliHLTDomainEntry intersect;
 614
 615   // To find the set intersect we need to compare each entry in 'domain' to those
 616   // of fEntries. For each inclusive entry in 'domain' we need to add to the result
 617   // the intersect between it and each entry of fEntries, with the same exclude flag
 618   // value as the domain entry from fEntries.
 619   // However, in principle, for the exclusion entries in 'domain' we just add them
 620   // to the result, since those entries do not form part of the 'domain' trigger
 621   // domain set, so they should not form part of the result (remember any data block
 622   // must be contained in both trigger domains for a set intersect).
 623   // In actual fact we just add the intersect of the exclusion entries in 'domain'
 624   // with those of fEntries to the result. This has the same overall effect, but
 625   // makes sure that all exclusion entries are always subsets of inclusion entries.
 626   for (Int_t i = 0; i < domain.fEntries.GetEntriesFast(); i++)
 627   {
 628     const AliHLTDomainEntry* checkEntry = static_cast<const AliHLTDomainEntry*>( domain.fEntries[i] );
 629     if (checkEntry->Inclusive())
 630     {
 631       for (Int_t j = 0; j < fEntries.GetEntriesFast(); j++)
 632       {
 633         AliHLTDomainEntry* currentEntry = static_cast<AliHLTDomainEntry*>( fEntries[j] );
 634         if (checkEntry->IntersectWith(*currentEntry, intersect))
 635         {
 636           // We can remove all entries that were already added to the result that
 637           // will become redundent because they are subsets of the new entry.
 638           result.MarkForDeletionSubsetsOf(intersect, 0);
 639
 640           new (result.fEntries[newIndex++]) AliHLTDomainEntry(currentEntry->Exclusive(), intersect);
 641         }
 642       }
 643     }
 644     else
 645     {
 646       for (Int_t j = 0; j < fEntries.GetEntriesFast(); j++)
 647       {
 648         AliHLTDomainEntry* currentEntry = static_cast<AliHLTDomainEntry*>( fEntries[j] );
 649         if (checkEntry->IntersectWith(*currentEntry, intersect))
 650         {
 651           // We can remove all entries that were already added to the result that
 652           // will become redundant because they are subsets of the new entry.
 653           result.MarkForDeletionSubsetsOf(intersect, 0);
 654
 655           new (result.fEntries[newIndex++]) AliHLTDomainEntry(kTRUE, intersect);
 656         }
 657       }
 658     }
 659   }
 660
 661   result.RemoveMarkedEntries();
 662   result.Optimise();
 663   return result;
 664 }
 665
 666
 667 void AliHLTTriggerDomain::MergeEntries(
 668     const bool* removeThisEntry, Int_t entriesCount,
 669     const bool* removeDomainEntry, Int_t startOfIntersects,
 670     const AliHLTTriggerDomain& domain
 671   )
 672 {
 673   // Merges the entries in this trigger domain with the ones in 'domain', while
 674   // removing all entries that were marked for removal.
 675   // See header file for more information.
 676
 677   bool anythingRemoved = false;
 678
 679   // Remember this method is used at the end of the calculation of the binary operators
 680   // and that fEntries is expected to be partitioned into 3 regions.
 681   //   - 0..entriesCount-1 : contains the original (initial) entries of this trigger domain.
 682   //   - entriesCount..startOfIntersects-1 : is space reserved for the new entries
 683   //       from the given trigger domain 'domain' being processed.
 684   //   - startOfIntersects..fEntries.GetEntriesFast()-1 : contains all new domain entry
 685   //       intersection created and added to fEntries.
 686   //
 687   // First we need to remove all entries marked for removal from the original entries.
 688   for (Int_t i = 0; i < entriesCount; i++)
 689   {
 690     if (removeThisEntry[i])
 691     {
 692       fEntries.RemoveAt(i);
 693       anythingRemoved = true;
 694     }
 695   }
 696
 697   // Now we copy over all the new entries from 'domain' which were not marked for removal
 698   // and indicate anythingRemoved = true since there will now be gaps in the clones array
 699   // that need to be compressed away later.
 700   for (Int_t i = 0; i < domain.fEntries.GetEntriesFast(); i++)
 701   {
 702     if (removeDomainEntry[i])
 703     {
 704       anythingRemoved = true;
 705     }
 706     else
 707     {
 708       const AliHLTDomainEntry* newEntry = static_cast<const AliHLTDomainEntry*>( domain.fEntries[i] );
 709       new (fEntries[entriesCount+i]) AliHLTDomainEntry(*newEntry);
 710     }
 711   }
 712
 713   // Finally remove all new intersection entries that were marked for removal by
 714   // the MarkForDeletionSubsetsOf method.
 715   for (Int_t i = startOfIntersects; i < fEntries.GetEntriesFast(); i++)
 716   {
 717     const AliHLTDomainEntry* ientry = static_cast<const AliHLTDomainEntry*>( fEntries[i] );
 718     if (ientry->TestBit(14))
 719     {
 720       fEntries.RemoveAt(i);
 721       anythingRemoved = true;
 722     }
 723   }
 724   if (anythingRemoved) fEntries.Compress();
 725 }
 726
 727
 728 void AliHLTTriggerDomain::MarkForDeletionSubsetsOf(const AliHLTDomainEntry& entry, Int_t min)
 729 {
 730   // Marks for deletion all the entries in this trigger domain that are subsets
 731   // of the given entry.
 732   // See header file for more information.
 733
 734   AliHLTDomainEntry intersect;
 735   for (Int_t i = min; i < fEntries.GetEntriesFast(); i++)
 736   {
 737     AliHLTDomainEntry* ientry = static_cast<AliHLTDomainEntry*>( fEntries[i] );
 738     if (ientry->TestBit(14)) continue;
 739     if (ientry->SubsetOf(entry))
 740     {
 741       ientry->SetBit(14, true);
 742     }
 743   }
 744 }
 745
 746
 747 void AliHLTTriggerDomain::RemoveMarkedEntries()
 748 {
 749   // Removes all entries in this trigger domain which were marked for removal.
 750   // See header file for more information.
 751
 752   bool anythingRemoved = false;
 753   for (Int_t i = 0; i < fEntries.GetEntriesFast(); i++)
 754   {
 755     const AliHLTDomainEntry* ientry = static_cast<const AliHLTDomainEntry*>( fEntries[i] );
 756     if (ientry->TestBit(14))
 757     {
 758       fEntries.RemoveAt(i);
 759       anythingRemoved = true;
 760     }
 761   }
 762   if (anythingRemoved) fEntries.Compress();
 763 }
 764
 765
 766 void AliHLTTriggerDomain::Optimise()
 767 {
 768   // Removes redundant trigger domain entries from the trigger domain.
 769   // See header file for more information.
 770
 771   AliHLTDomainEntry intersect;
 772
 773   // Check that the first entry is not and exclusion which would be redundent.
 774   if (fEntries.GetEntriesFast() == 0) return;
 775   AliHLTDomainEntry* firstEntry = static_cast<AliHLTDomainEntry*>( fEntries[0] );
 776   if (firstEntry->Exclusive()) firstEntry->SetBit(14, true);
 777
 778   for (Int_t i = 1; i < fEntries.GetEntriesFast(); i++)
 779   {
 780     AliHLTDomainEntry* ientry = static_cast<AliHLTDomainEntry*>( fEntries[i] );
 781
 782     // For the i'th entry in fEntries, compare it in reverse order with all other
 783     // entries that are before it and look for redundant ones, i.e. that are subsets
 784     // of the i'th entry.
 785     for (Int_t j = i-1; j >= 0; j--)
 786     {
 787       AliHLTDomainEntry* jentry = static_cast<AliHLTDomainEntry*>( fEntries[j] );
 788       if (jentry->TestBit(14)) continue;
 789       // Find entries that intersect
 790       if (jentry->SubsetOf(*ientry))
 791       {
 792         // jentry is a subset of ientry so it is redundant because for all values
 793         // ientry will override jentry when calling IncludeInReadout.
 794         jentry->SetBit(14, true);
 795       }
 796       else if (*ientry == *jentry)
 797       {
 798         // If intersecting entries have opposite exclude flags then search no further,
 799         // we know that we will need this entry for correct behaviour of IncludeInReadout.
 800         if (ientry->Inclusive() == jentry->Exclusive()) goto processNextEntry;
 801
 802         if (ientry->SubsetOf(*jentry))
 803         {
 804           ientry->SetBit(14, true);
 805           goto processNextEntry;
 806         }
 807       }
 808     }
 809
 810     // If we got to this point then we hit the top of the trigger domain rules
 811     // (pattern matching) list without hitting any and overlapping entries.
 812     // So now we need to check if ientry is an exclusion. If it is, then it is
 813     // redundant and we can mark it for removal.
 814     if (ientry->Exclusive()) ientry->SetBit(14, true);
 815
 816     processNextEntry: ;
 817   }
 818
 819   RemoveMarkedEntries();
 820 }
 821