HLT/BASE/AliHLTTriggerDomain.cxx

   1 // $Id$
   2 /**************************************************************************
   3  * This file is property of and copyright by the ALICE HLT Project        *
   4  * ALICE Experiment at CERN, All rights reserved.                         *
   5  *                                                                        *
   6  * Primary Authors: Artur Szostak <artursz@iafrica.com>                   *
   7  *                  for The ALICE HLT Project.                            *
   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 /// @file   AliHLTTriggerDomain.cxx
  19 /// @author Artur Szostak <artursz@iafrica.com>
  20 /// @date   19 Nov 2008
  21 /// @brief  Implementation of the AliHLTTriggerDomain class.
  22 ///
  23 /// The trigger domain class is the set of HLT raw data block types that should
  24 /// be readout and sent to HLTOUT.
  25
  26 #include <stdlib.h>
  27
  28 #include "AliHLTTriggerDomain.h"
  29 #include "AliHLTDomainEntry.h"
  30 #include "AliHLTReadoutList.h"
  31 #include "Riostream.h"
  32 #include "TObjArray.h"
  33 #include "TObjString.h"
  34 #include "AliHLTDAQ.h"
  35
  36 ClassImp(AliHLTTriggerDomain)
  37
  38
  39 AliHLTTriggerDomain::AliHLTTriggerDomain() :
  40   TObject(), fEntries(AliHLTDomainEntry::Class(), 10)
  41 {
  42   // Default constructor.
  43 }
  44
  45
  46 AliHLTTriggerDomain::AliHLTTriggerDomain(const char* list) :
  47   TObject(), fEntries(AliHLTDomainEntry::Class(), 10)
  48 {
  49   // Constructs the domain from a list of entries.
  50
  51   TString lst = list;
  52   TObjArray* entries = lst.Tokenize(",");
  53   for (Int_t i = 0; i < entries->GetEntriesFast(); i++)
  54   {
  55     TString entry = static_cast<TObjString*>(entries->UncheckedAt(i))->GetString();
  56     TObjArray* domainStrings = entry.Tokenize(":");
  57     if (domainStrings->GetEntriesFast() <= 0 or domainStrings->GetEntriesFast() > 3)
  58     {
  59       Error("AliHLTTriggerDomain",
  60             "The domain string must contain 1, 2 or 3 fields separated by a ':'."
  61            );
  62       delete domainStrings;
  63       continue;
  64     }
  65
  66     bool inclusiveEntry = true;
  67     TString typeString = "*******";
  68     if (domainStrings->GetEntriesFast() >= 1)
  69     {
  70       typeString = static_cast<TObjString*>(domainStrings->UncheckedAt(0))->GetString();
  71       if (typeString.Length() > 0)
  72       {
  73         if (typeString[0] == '+')
  74         {
  75           inclusiveEntry = true;
  76           typeString.Remove(0, 1);
  77         }
  78         if (typeString[0] == '-')
  79         {
  80           inclusiveEntry = false;
  81           typeString.Remove(0, 1);
  82         }
  83       }
  84     }
  85     TString originString = "***";
  86     if (domainStrings->GetEntriesFast() >= 2)
  87     {
  88       originString = static_cast<TObjString*>(domainStrings->UncheckedAt(1))->GetString();
  89     }
  90     bool usespec = false;
  91     UInt_t spec = 0;
  92     if (domainStrings->GetEntriesFast() == 3)
  93     {
  94       TString specString = static_cast<TObjString*>(domainStrings->UncheckedAt(2))->GetString();
  95       char* error = NULL;
  96       spec = UInt_t( strtoul(specString.Data(), &error, 0) );
  97       if (error == NULL or *error != '\0')
  98       {
  99         Error("AliHLTTriggerDomain",
 100               "The last field of the domain string must be a number, but we received '%s'.",
 101               specString.Data()
 102              );
 103       }
 104       else
 105       {
 106         usespec = true;
 107       }
 108     }
 109
 110     if (usespec)
 111     {
 112       if (inclusiveEntry)
 113         Add(typeString.Data(), originString.Data(), spec);
 114       else
 115         Remove(typeString.Data(), originString.Data(), spec);
 116     }
 117     else
 118     {
 119       if (inclusiveEntry)
 120         Add(typeString.Data(), originString.Data());
 121       else
 122         Remove(typeString.Data(), originString.Data());
 123     }
 124
 125     delete domainStrings;
 126   }
 127   delete entries;
 128 }
 129
 130
 131 AliHLTTriggerDomain::AliHLTTriggerDomain(const AliHLTReadoutList& list) :
 132   TObject(), fEntries(AliHLTDomainEntry::Class(), 10)
 133 {
 134   // Constructor creates a trigger domain from a readout list.
 135   // See header file for more details.
 136
 137   Add(list);
 138 }
 139
 140
 141 AliHLTTriggerDomain::AliHLTTriggerDomain(const AliHLTTriggerDomain& domain) :
 142   TObject(domain),
 143   fEntries(AliHLTDomainEntry::Class(), domain.fEntries.GetEntriesFast())
 144 {
 145   // Copy constructor performs a deep copy.
 146   // See header file for more details.
 147
 148   for (Int_t i = 0; i < domain.fEntries.GetEntriesFast(); i++)
 149   {
 150     const AliHLTDomainEntry* entry = static_cast<const AliHLTDomainEntry*>( domain.fEntries.UncheckedAt(i) );
 151     new (fEntries[fEntries.GetEntriesFast()]) AliHLTDomainEntry(*entry);
 152   }
 153 }
 154
 155
 156 AliHLTTriggerDomain::~AliHLTTriggerDomain()
 157 {
 158   // Default destructor.
 159 }
 160
 161
 162 void AliHLTTriggerDomain::Add(const AliHLTReadoutList& list)
 163 {
 164   // Adds the readout list to the trigger domain.
 165   // See header file for more details.
 166
 167   Int_t detId[] = {
 168       AliHLTReadoutList::kITSSPD, AliHLTReadoutList::kITSSDD, AliHLTReadoutList::kITSSSD,
 169       AliHLTReadoutList::kTPC, AliHLTReadoutList::kTRD, AliHLTReadoutList::kTOF,
 170       AliHLTReadoutList::kHMPID, AliHLTReadoutList::kPHOS, AliHLTReadoutList::kCPV,
 171       AliHLTReadoutList::kPMD, AliHLTReadoutList::kMUONTRK, AliHLTReadoutList::kMUONTRG,
 172       AliHLTReadoutList::kFMD, AliHLTReadoutList::kT0, AliHLTReadoutList::kV0,
 173       AliHLTReadoutList::kZDC, AliHLTReadoutList::kACORDE, AliHLTReadoutList::kTRG,
 174       AliHLTReadoutList::kEMCAL, AliHLTReadoutList::kDAQTEST, AliHLTReadoutList::kHLT
 175     };
 176
 177   for (Int_t deti = 0; deti < (Int_t)AliHLTDAQ::NumberOfDetectors() && deti < (Int_t)(sizeof(detId)/sizeof(Int_t)); deti++)
 178   {
 179     if (list.DetectorEnabled(detId[deti]))
 180     {
 181       Add(kAliHLTDAQRDOUTDataTypeID, AliHLTDAQ::OnlineName(deti));
 182     }
 183     else
 184     {
 185       for (Int_t i = 0; i < AliHLTDAQ::NumberOfDdls(deti); i++)
 186       {
 187         Int_t ddlId = AliHLTDAQ::DdlID(deti, i);
 188         if (list.IsDDLEnabled(ddlId)) Add(kAliHLTDAQRDOUTDataTypeID, AliHLTDAQ::OnlineName(deti), ddlId);
 189       }
 190     }
 191   }
 192 }
 193
 194 void AliHLTTriggerDomain::Add(const AliHLTDomainEntry& entry)
 195 {
 196   // Adds a new domain entry to the trigger domain.
 197   // See header file for more details.
 198
 199   AliHLTDomainEntry intersect;
 200   bool alreadyInSet = false;
 201
 202   // Get the initial size of the fEntries array since we might add things to the
 203   // end during the calculation.
 204   Int_t count = fEntries.GetEntriesFast();
 205
 206   // Go through each entry that is already in fEntries and see if we can remove
 207   // it because it will become redundant, or if we need to patch exclusion entries
 208   // by adding inclusive intersects, or if we do not even need to add the new entry
 209   // because it is already part of the trigger domain.
 210   for (Int_t i = 0; i < count; i++)
 211   {
 212     AliHLTDomainEntry* ientry = static_cast<AliHLTDomainEntry*>(fEntries.UncheckedAt(i));
 213     if (ientry->Inclusive())
 214     {
 215       if (entry.SubsetOf(*ientry))
 216       {
 217         alreadyInSet = true;
 218       }
 219       else if (ientry->SubsetOf(entry))
 220       {
 221         ientry->SetBit(BIT(14), true);  // mark for removal.
 222       }
 223     }
 224     else
 225     {
 226       if (ientry->SubsetOf(entry))
 227       {
 228         ientry->SetBit(BIT(14), true);  // mark for removal.
 229       }
 230       else if (entry.SubsetOf(*ientry))
 231       {
 232         alreadyInSet = false;
 233       }
 234       else if (ientry->IntersectWith(entry, intersect))
 235       {
 236         MarkForDeletionSubsetsOf(intersect, count);
 237         new (fEntries[fEntries.GetEntriesFast()]) AliHLTDomainEntry(kFALSE, intersect);
 238       }
 239     }
 240   }
 241
 242   // Check if we need to add the new entry.
 243   if (not alreadyInSet)
 244   {
 245     MarkForDeletionSubsetsOf(entry, count);
 246     new (fEntries[fEntries.GetEntriesFast()]) AliHLTDomainEntry(kFALSE, entry);
 247   }
 248   RemoveMarkedEntries();
 249 }
 250
 251
 252 void AliHLTTriggerDomain::Add(const AliHLTComponentDataType& datatype)
 253 {
 254   // Adds a new domain entry with the given data type to the trigger domain.
 255   // But the data block specification is set to the any matching wild card.
 256   // See header file for more details.
 257
 258   Add(AliHLTDomainEntry(datatype));
 259 }
 260
 261
 262 void AliHLTTriggerDomain::Add(const char* blocktype, const char* origin)
 263 {
 264   // Adds a new domain entry with the given data type and origin to the trigger domain.
 265   // But the data block specification is set to the any matching wild card.
 266   // See header file for more details.
 267
 268   Add(AliHLTDomainEntry(blocktype, origin));
 269 }
 270
 271
 272 void AliHLTTriggerDomain::Add(const AliHLTComponentDataType& datatype, UInt_t spec)
 273 {
 274   // Adds a new domain entry to the trigger domain with the data type and data block
 275   // specification bits.
 276   // See header file for more details.
 277
 278   Add(AliHLTDomainEntry(datatype, spec));
 279 }
 280
 281
 282 void AliHLTTriggerDomain::Add(const char* blocktype, const char* origin, UInt_t spec)
 283 {
 284   // Adds a new domain entry to the trigger domain with the given data type, origin
 285   // and data block specification bits.
 286   // See header file for more details.
 287
 288   Add(AliHLTDomainEntry(blocktype, origin, spec));
 289 }
 290
 291
 292 void AliHLTTriggerDomain::Remove(const AliHLTReadoutList& list)
 293 {
 294   // Removes the entries in the readout list from the trigger domain that are enabled.
 295   // See header file for more details.
 296
 297   Int_t detId[] = {
 298       AliHLTReadoutList::kITSSPD, AliHLTReadoutList::kITSSDD, AliHLTReadoutList::kITSSSD,
 299       AliHLTReadoutList::kTPC, AliHLTReadoutList::kTRD, AliHLTReadoutList::kTOF,
 300       AliHLTReadoutList::kHMPID, AliHLTReadoutList::kPHOS, AliHLTReadoutList::kCPV,
 301       AliHLTReadoutList::kPMD, AliHLTReadoutList::kMUONTRK, AliHLTReadoutList::kMUONTRG,
 302       AliHLTReadoutList::kFMD, AliHLTReadoutList::kT0, AliHLTReadoutList::kV0,
 303       AliHLTReadoutList::kZDC, AliHLTReadoutList::kACORDE, AliHLTReadoutList::kTRG,
 304       AliHLTReadoutList::kEMCAL, AliHLTReadoutList::kDAQTEST, AliHLTReadoutList::kHLT
 305     };
 306
 307   for (Int_t deti = 0; deti < (Int_t)AliHLTDAQ::NumberOfDetectors() && deti < (Int_t)(sizeof(detId)/sizeof(Int_t)); deti++)
 308   {
 309     if (list.DetectorEnabled(detId[deti]))
 310     {
 311       Remove(kAliHLTDAQRDOUTDataTypeID, AliHLTDAQ::OnlineName(deti));
 312     }
 313     else
 314     {
 315       for (Int_t i = 0; i < AliHLTDAQ::NumberOfDdls(deti); i++)
 316       {
 317         Int_t ddlId = AliHLTDAQ::DdlID(deti, i);
 318         if (list.IsDDLEnabled(ddlId)) Remove(kAliHLTDAQRDOUTDataTypeID, AliHLTDAQ::OnlineName(deti), ddlId);
 319       }
 320     }
 321   }
 322 }
 323
 324
 325 void AliHLTTriggerDomain::Remove(const AliHLTDomainEntry& entry)
 326 {
 327   // Removes the given domain entry from the trigger domain.
 328   // See header file for more details.
 329
 330   AliHLTDomainEntry intersect;
 331   bool addToExcludeSet = false;
 332
 333   // Get the initial size of the fEntries array since we might add things to the
 334   // end during the calculation.
 335   Int_t count = fEntries.GetEntriesFast();
 336
 337   // We need to go through all existing entries and see if they need to be removed
 338   // because they would become redundant when we add the new 'entry' to the end of
 339   // the fEntries list. We also need to check if the new entry needs to be added
 340   // at all because the trigger domain might already not contain those entries.
 341   // Lastly, some intersection entries might need to be added to patch up existing
 342   // inclusive trigger domain entries (rules / patterns).
 343   for (Int_t i = 0; i < count; i++)
 344   {
 345     AliHLTDomainEntry* ientry = static_cast<AliHLTDomainEntry*>(fEntries.UncheckedAt(i));
 346     if (ientry->Inclusive())
 347     {
 348       if (ientry->SubsetOf(entry))
 349       {
 350         ientry->SetBit(BIT(14), true);  // mark for removal.
 351       }
 352       else if (entry.SubsetOf(*ientry))
 353       {
 354         addToExcludeSet = true;
 355       }
 356       else if (ientry->IntersectWith(entry, intersect))
 357       {
 358         new (fEntries[fEntries.GetEntriesFast()]) AliHLTDomainEntry(kTRUE, intersect);
 359       }
 360     }
 361     else
 362     {
 363       if (entry.SubsetOf(*ientry))
 364       {
 365         addToExcludeSet = false;
 366       }
 367       else if (ientry->SubsetOf(entry))
 368       {
 369         ientry->SetBit(BIT(14), true);  // mark for removal.
 370       }
 371     }
 372   }
 373
 374   // Check if we need to add the new entry.
 375   if (addToExcludeSet)
 376   {
 377     MarkForDeletionSubsetsOf(entry, count);
 378     new (fEntries[fEntries.GetEntriesFast()]) AliHLTDomainEntry(kTRUE, entry);
 379   }
 380   RemoveMarkedEntries();
 381 }
 382
 383
 384 void AliHLTTriggerDomain::Remove(const AliHLTComponentDataType& datatype)
 385 {
 386   // Removes the domain entries that have the given data type from the trigger domain.
 387   // See header file for more details.
 388
 389   Remove(AliHLTDomainEntry(datatype));
 390 }
 391
 392
 393 void AliHLTTriggerDomain::Remove(const char* blocktype, const char* origin)
 394 {
 395   // Removes the domain entries that have the given data type and origin from the
 396   // trigger domain.
 397   // See header file for more details.
 398
 399   Remove(AliHLTDomainEntry(blocktype, origin));
 400 }
 401
 402
 403 void AliHLTTriggerDomain::Remove(const AliHLTComponentDataType& datatype, UInt_t spec)
 404 {
 405   // Removes the domain entries that have the given data type and data block
 406   // specification bits from the trigger domain.
 407   // See header file for more details.
 408
 409   Remove(AliHLTDomainEntry(datatype, spec));
 410 }
 411
 412
 413 void AliHLTTriggerDomain::Remove(const char* blocktype, const char* origin, UInt_t spec)
 414 {
 415   // Removes the domain entries that have the given data type, origin and data
 416   // block specification bits from the trigger domain.
 417   // See header file for more details.
 418
 419   Remove(AliHLTDomainEntry(blocktype, origin, spec));
 420 }
 421
 422
 423 bool AliHLTTriggerDomain::Contains(const AliHLTDomainEntry& entry) const
 424 {
 425   // Checks to see if the given domain entry is part of the trigger domain set.
 426   // See header file for more details.
 427
 428   // Simply go through the whole list of fEntries and for each entry see if the
 429   // given domain entry 'entry' being checked matches. If there is a match then
 430   // update the result depending on the entry type. i.e. set to false if the entry
 431   // in fEntries is an exclusion and set to true if it is an inclusion.
 432   bool result = false;
 433   for (Int_t i = 0; i < fEntries.GetEntriesFast(); i++)
 434   {
 435     const AliHLTDomainEntry* ientry = static_cast<const AliHLTDomainEntry*>(fEntries.UncheckedAt(i));
 436     if (ientry->Inclusive())
 437     {
 438       if (*ientry == entry) result = true;
 439     }
 440     else
 441     {
 442       if (entry.SubsetOf(*ientry)) result = false;
 443     }
 444   }
 445   return result;
 446 }
 447
 448
 449 bool AliHLTTriggerDomain::IncludeInReadout(const AliHLTComponentBlockData* block) const
 450 {
 451   // Checks to see if the given data block is part of the trigger domain set and
 452   // should be readout.
 453   // See header file for more details.
 454
 455   // Same algorithm as for Contains() but applied directly to the data block
 456   // descriptor structure.
 457   AliHLTDomainEntry blockEntry(block->fDataType, block->fSpecification);
 458   bool result = false;
 459   for (Int_t i = 0; i < fEntries.GetEntriesFast(); i++)
 460   {
 461     const AliHLTDomainEntry* entry = static_cast<const AliHLTDomainEntry*>(fEntries.UncheckedAt(i));
 462     if (entry->Inclusive())
 463     {
 464       if (*entry == block) result = true;
 465     }
 466     else
 467     {
 468       if (blockEntry.SubsetOf(*entry)) result = false;
 469     }
 470   }
 471   return result;
 472 }
 473
 474
 475 void AliHLTTriggerDomain::Clear(Option_t* option)
 476 {
 477   // Clears the trigger domain (Removes all entries).
 478
 479   fEntries.Clear(option);
 480 }
 481
 482
 483 void AliHLTTriggerDomain::Print(Option_t* /*option*/) const
 484 {
 485   // Prints the trigger domain entries in the order that they are applied.
 486   // See header file for more details.
 487
 488   cout << "Trigger domain rules (applied in order of first to last):" << endl;
 489   for (Int_t i = 0; i < fEntries.GetEntriesFast(); i++)
 490   {
 491     const AliHLTDomainEntry* entry = static_cast<const AliHLTDomainEntry*>( fEntries.UncheckedAt(i) );
 492     if (entry->Inclusive())
 493     {
 494       cout << "Include ";
 495     }
 496     else
 497     {
 498       cout << "Exclude ";
 499     }
 500     entry->Print();
 501   }
 502   if (fEntries.GetEntriesFast() == 0)
 503   {
 504     cout << "(empty)" << endl;
 505   }
 506 }
 507
 508
 509 AliHLTTriggerDomain& AliHLTTriggerDomain::operator = (const AliHLTTriggerDomain& domain)
 510 {
 511   // Assignment operator performs a deep copy.
 512   // See header file for more details.
 513
 514   if (this == &domain) return *this;
 515   TObject::operator = (domain);
 516   fEntries.Clear();
 517   for (Int_t i = 0; i < domain.fEntries.GetEntriesFast(); i++)
 518   {
 519     const AliHLTDomainEntry* entry = static_cast<const AliHLTDomainEntry*>( domain.fEntries.UncheckedAt(i) );
 520     new (fEntries[fEntries.GetEntriesFast()]) AliHLTDomainEntry(*entry);
 521   }
 522   return *this;
 523 }
 524
 525
 526 AliHLTTriggerDomain& AliHLTTriggerDomain::operator |= (const AliHLTTriggerDomain& domain)
 527 {
 528   // This operator performs the set union.
 529   // See header file for more details.
 530
 531   // Note that we partition the fEntries array into 3 regions for this calculation.
 532   //   - 0..entriesCount-1 : contains the initial entries of this trigger domain.
 533   //   - entriesCount..startOfIntersects-1 : is space reserved for the new entries
 534   //       from 'domain'.
 535   //   - startOfIntersects..fEntries.GetEntriesFast()-1 : This will grow as we add
 536   //       all the new domain intersections created during the calculation.
 537   //
 538   // Get the number of entries now before we start adding more entries from 'domain'.
 539   Int_t count = fEntries.GetEntriesFast();
 540   // Mark the start location for new intersection entries.
 541   Int_t startOfIntersects = count + domain.fEntries.GetEntriesFast();
 542   Int_t newIndex = startOfIntersects;
 543
 544   // Allocate and initialise a single block of memory so that we do not call new twice.
 545   bool* buffer = new bool[startOfIntersects];
 546   for (Int_t i = 0; i < startOfIntersects; i++) buffer[i] = false;
 547   bool* removeThisEntry = buffer;
 548   bool* removeDomainEntry = buffer + count;
 549
 550   AliHLTDomainEntry intersect;
 551
 552   // The idea behind this algorithm is that we need to add all inclusion domain
 553   // entries from 'domain' to this object that will not be redundant, but for
 554   // the exclusion entries we patch the fEntries rule set by adding the appropriate
 555   // intersections to the end of fEntries.
 556   for (Int_t i = 0; i < domain.fEntries.GetEntriesFast(); i++)
 557   {
 558     const AliHLTDomainEntry* newEntry = static_cast<const AliHLTDomainEntry*>( domain.fEntries.UncheckedAt(i) );
 559     for (Int_t j = 0; j < count; j++)
 560     {
 561       const AliHLTDomainEntry* currentEntry = static_cast<const AliHLTDomainEntry*>( fEntries.UncheckedAt(j) );
 562       if (currentEntry->Inclusive() and newEntry->Inclusive())
 563       {
 564         // If either entry is a subset of the other then we do not need to add
 565         // both, so make sure to remove the one that is redundant.
 566         if (newEntry->SubsetOf(*currentEntry))
 567         {
 568           removeDomainEntry[i] = true;
 569         }
 570         else if (currentEntry->SubsetOf(*newEntry))
 571         {
 572           removeThisEntry[j] = true;
 573         }
 574       }
 575       else
 576       {
 577         if (newEntry->IntersectWith(*currentEntry, intersect))
 578         {
 579           // We can remove all intersections that were already added that will
 580           // become redundant when this intersection is added to fEntries.
 581           MarkForDeletionSubsetsOf(intersect, startOfIntersects);
 582
 583           // Make the new intersection entry an exclusion if the newEntry and
 584           // currentEntry flags are the same.
 585           bool exclude = newEntry->Exclusive() == currentEntry->Exclusive();
 586           new (fEntries[newIndex++]) AliHLTDomainEntry(exclude, intersect);
 587
 588           // We can also remove entries that are subsets of another entry in the
 589           // opposite list, since they will be redundant when everything is merged
 590           // together. For example, remove entry x from fEntries if it is a subset
 591           // of entry y in domain.fEntries.
 592           if (currentEntry->IdenticalTo(intersect)) removeThisEntry[j] = true;
 593           if (newEntry->IdenticalTo(intersect)) removeDomainEntry[i] = true;
 594         }
 595       }
 596     }
 597   }
 598
 599   MergeEntries(removeThisEntry, count, removeDomainEntry, startOfIntersects, domain);
 600   delete [] buffer;
 601   Optimise();
 602   return *this;
 603 }
 604
 605
 606 AliHLTTriggerDomain& AliHLTTriggerDomain::operator ^= (const AliHLTTriggerDomain& domain)
 607 {
 608   // This operator performs the set union, less the set intersect (something like and xor).
 609   // See header file for more details.
 610
 611   // Note that we partition the fEntries array into 3 regions for this calculation.
 612   //   - 0..entriesCount-1 : contains the initial entries of this trigger domain.
 613   //   - entriesCount..startOfIntersects-1 : is space reserved for the new entries
 614   //       from 'domain'.
 615   //   - startOfIntersects..fEntries.GetEntriesFast()-1 : This will grow as we add
 616   //       all the new domain intersections created during the calculation.
 617   //
 618   // Get the number of entries now before we start adding more entries from 'domain'.
 619   Int_t count = fEntries.GetEntriesFast();
 620   // Mark the start location for new intersection entries.
 621   Int_t startOfIntersects = count + domain.fEntries.GetEntriesFast();
 622   Int_t newIndex = startOfIntersects;
 623
 624   // Allocate and initialise a single block of memory so that we do not call new twice.
 625   bool* buffer = new bool[startOfIntersects];
 626   for (Int_t i = 0; i < startOfIntersects; i++) buffer[i] = false;
 627   bool* removeThisEntry = buffer;
 628   bool* removeDomainEntry = buffer + count;
 629
 630   AliHLTDomainEntry intersect;
 631
 632   // This algorithm is similar to the case for the set union (operator |=), except
 633   // that we make sure to remove from the trigger domain all parts where the entries
 634   // from fEntries and domain.fEntries intersect.
 635   // This is done by adding the intersections to the end of fEntries such that they
 636   // effectively remove those overlapping trigger domain entries when calculating
 637   // IncludeInReadout() or Contains().
 638   for (Int_t i = 0; i < domain.fEntries.GetEntriesFast(); i++)
 639   {
 640     const AliHLTDomainEntry* newEntry = static_cast<const AliHLTDomainEntry*>( domain.fEntries.UncheckedAt(i) );
 641     for (Int_t j = 0; j < count; j++)
 642     {
 643       const AliHLTDomainEntry* currentEntry = static_cast<const AliHLTDomainEntry*>( fEntries.UncheckedAt(j) );
 644       if (newEntry->IntersectWith(*currentEntry, intersect))
 645       {
 646         // We can remove all intersections that were already added that will
 647         // become redundant when this intersection is added to fEntries.
 648         MarkForDeletionSubsetsOf(intersect, startOfIntersects);
 649
 650         // Make the new intersection entry an exclusion if the newEntry and
 651         // currentEntry flags are the same.
 652         bool exclude = newEntry->Exclusive() == currentEntry->Exclusive();
 653         new (fEntries[newIndex++]) AliHLTDomainEntry(exclude, intersect);
 654
 655         // We can also remove entries that are subsets of another entry in the
 656         // opposite list, since they will be redundant when everything is merged
 657         // together. For example, remove entry x from fEntries if it is a subset
 658         // of entry y in domain.fEntries.
 659         if (currentEntry->IdenticalTo(intersect)) removeThisEntry[j] = true;
 660         if (newEntry->IdenticalTo(intersect)) removeDomainEntry[i] = true;
 661       }
 662     }
 663   }
 664
 665   MergeEntries(removeThisEntry, count, removeDomainEntry, startOfIntersects, domain);
 666   delete [] buffer;
 667   Optimise();
 668   return *this;
 669 }
 670
 671
 672 AliHLTTriggerDomain& AliHLTTriggerDomain::operator -= (const AliHLTTriggerDomain& domain)
 673 {
 674   // This operator performs the set difference.
 675   // See header file for more details.
 676
 677   // Mark the number of entries in fEntries now before we start adding more
 678   // entries from 'domain' or intersections.
 679   Int_t startOfIntersects = fEntries.GetEntriesFast();
 680   Int_t newIndex = startOfIntersects;
 681
 682   AliHLTDomainEntry intersect;
 683
 684   // To compute the set difference we need to remove all all parts that overlap
 685   // with 'domain'. i.e. we need to find all the intersects between the domain
 686   // entries in fEntries and those in domain.fEntries, and add the intersects
 687   // to the fEntries list, such that they will cancel or remove the overlapping
 688   // parts of the two trigger domains.
 689   for (Int_t i = 0; i < domain.fEntries.GetEntriesFast(); i++)
 690   {
 691     const AliHLTDomainEntry* checkEntry = static_cast<const AliHLTDomainEntry*>( domain.fEntries.UncheckedAt(i) );
 692     if (checkEntry->Inclusive())
 693     {
 694       // For inclusive entries we need to find the overlaps with the inclusive
 695       // entries in fEntries and add exclusive entries that will remove that
 696       // part of the trigger domain set.
 697       for (Int_t j = 0; j < startOfIntersects; j++)
 698       {
 699         AliHLTDomainEntry* currentEntry = static_cast<AliHLTDomainEntry*>( fEntries.UncheckedAt(j) );
 700
 701         // We only need to consider the case where both entries are inclusive,
 702         // since an exclusion in fEntries already eliminates those data blocks
 703         // from the trigger domain set.
 704         if (currentEntry->Exclusive()) continue;
 705
 706         if (checkEntry->IntersectWith(*currentEntry, intersect))
 707         {
 708           // We can remove all intersections that were already added that will
 709           // become redundant when this intersection is added to fEntries.
 710           MarkForDeletionSubsetsOf(intersect, startOfIntersects);
 711
 712           new (fEntries[newIndex++]) AliHLTDomainEntry(kTRUE, intersect);
 713           if (currentEntry->IdenticalTo(intersect))
 714           {
 715             currentEntry->SetBit(BIT(14), true);
 716           }
 717         }
 718       }
 719     }
 720     else
 721     {
 722       // For an exclusive entry in 'domain' we need to find the intersections with
 723       // all of fEntries and re-apply these with the same exclude flags.
 724       for (Int_t j = 0; j < startOfIntersects; j++)
 725       {
 726         AliHLTDomainEntry* currentEntry = static_cast<AliHLTDomainEntry*>( fEntries.UncheckedAt(j) );
 727         if (checkEntry->IntersectWith(*currentEntry, intersect))
 728         {
 729           // We can remove all intersections that were already added that will
 730           // become redundant when this intersection is added to fEntries.
 731           MarkForDeletionSubsetsOf(intersect, startOfIntersects);
 732
 733           new (fEntries[newIndex++]) AliHLTDomainEntry(currentEntry->Exclusive(), intersect);
 734         }
 735       }
 736     }
 737   }
 738
 739   RemoveMarkedEntries();
 740   Optimise();
 741   return *this;
 742 }
 743
 744
 745 AliHLTTriggerDomain AliHLTTriggerDomain::operator ~ () const
 746 {
 747   // Performs a set complement of the trigger domain.
 748
 749   // The set complement is calculated by creating a new trigger domain which
 750   // accepts all possible data blocks, and then apply all the trigger domain
 751   // entries (rules / patterns) from top to bottom, but apply them with the
 752   // opposite meaning. For example, this->fEntries contains an inclusive domain
 753   // entry then remove it from the new trigger domain 'result', but if it is
 754   // an exclusion then add it.
 755   AliHLTTriggerDomain result;
 756   result.Add(kAliHLTAnyDataType);
 757   for (Int_t i = 0; i < fEntries.GetEntriesFast(); i++)
 758   {
 759     const AliHLTDomainEntry* entry = static_cast<const AliHLTDomainEntry*>( fEntries.UncheckedAt(i) );
 760     if (entry->Inclusive())
 761     {
 762       result.Remove(*entry);
 763     }
 764     else
 765     {
 766       result.Add(*entry);
 767     }
 768   }
 769   return result;
 770 }
 771
 772
 773 AliHLTTriggerDomain AliHLTTriggerDomain::operator & (const AliHLTTriggerDomain& domain) const
 774 {
 775   // This operator finds the set intersect.
 776   // See header file for more details.
 777
 778   AliHLTTriggerDomain result;
 779   Int_t newIndex = 0;
 780   AliHLTDomainEntry intersect;
 781
 782   // To find the set intersect we need to compare each entry in 'domain' to those
 783   // of fEntries. For each inclusive entry in 'domain' we need to add to the result
 784   // the intersect between it and each entry of fEntries, with the same exclude flag
 785   // value as the domain entry from fEntries.
 786   // However, in principle, for the exclusion entries in 'domain' we just add them
 787   // to the result, since those entries do not form part of the 'domain' trigger
 788   // domain set, so they should not form part of the result (remember any data block
 789   // must be contained in both trigger domains for a set intersect).
 790   // In actual fact we just add the intersect of the exclusion entries in 'domain'
 791   // with those of fEntries to the result. This has the same overall effect, but
 792   // makes sure that all exclusion entries are always subsets of inclusion entries.
 793   for (Int_t i = 0; i < domain.fEntries.GetEntriesFast(); i++)
 794   {
 795     const AliHLTDomainEntry* checkEntry = static_cast<const AliHLTDomainEntry*>( domain.fEntries.UncheckedAt(i) );
 796     if (checkEntry->Inclusive())
 797     {
 798       for (Int_t j = 0; j < fEntries.GetEntriesFast(); j++)
 799       {
 800         AliHLTDomainEntry* currentEntry = static_cast<AliHLTDomainEntry*>( fEntries.UncheckedAt(j) );
 801         if (checkEntry->IntersectWith(*currentEntry, intersect))
 802         {
 803           // We can remove all entries that were already added to the result that
 804           // will become redundent because they are subsets of the new entry.
 805           result.MarkForDeletionSubsetsOf(intersect, 0);
 806
 807           new (result.fEntries[newIndex++]) AliHLTDomainEntry(currentEntry->Exclusive(), intersect);
 808         }
 809       }
 810     }
 811     else
 812     {
 813       for (Int_t j = 0; j < fEntries.GetEntriesFast(); j++)
 814       {
 815         AliHLTDomainEntry* currentEntry = static_cast<AliHLTDomainEntry*>( fEntries.UncheckedAt(j) );
 816         if (checkEntry->IntersectWith(*currentEntry, intersect))
 817         {
 818           // We can remove all entries that were already added to the result that
 819           // will become redundant because they are subsets of the new entry.
 820           result.MarkForDeletionSubsetsOf(intersect, 0);
 821
 822           new (result.fEntries[newIndex++]) AliHLTDomainEntry(kTRUE, intersect);
 823         }
 824       }
 825     }
 826   }
 827
 828   result.RemoveMarkedEntries();
 829   result.Optimise();
 830   return result;
 831 }
 832
 833
 834 bool AliHLTTriggerDomain::operator == (const AliHLTTriggerDomain& domain) const
 835 {
 836   // Checks if two domains are the same.
 837
 838   if (fEntries.GetEntriesFast() != domain.fEntries.GetEntriesFast()) return false;
 839
 840   // We need to find for each entry in this domain an identical entry in the domain
 841   // that we are comparing to. Both entries cannot have subset entries further down
 842   // in the entries lists. i.e. for fEntries[n], there cannot be any entry fEntries[m]
 843   // that is a subset of fEntries[n] where m > n. Similarly for domain.fEntries.
 844   // If two such entries are matched and they respect the subset rule mentioned,
 845   // then they are marked. We keep finding matching pairs until no more pairs are
 846   // found and check if there are any unmarked entries in either list. If there are
 847   // any unmatched pairs then the two domains do not match.
 848   //
 849   // Note: We use bit 14 in fBits to mark the entries.
 850   // 2) We traverse fEntries from back to front (i.e. from N-1 down to 0) so that
 851   //    we are guaranteed that fEntries[n] has no subset entries above it that are
 852   //    not marked.
 853   for (Int_t i = fEntries.GetEntriesFast() - 1; i >= 0; --i)
 854   {
 855     AliHLTDomainEntry* entry1 = static_cast<const AliHLTDomainEntry*>( fEntries.UncheckedAt(i) );
 856     // Find identical domain entry in domain.fEntries.
 857     AliHLTDomainEntry* entry2 = NULL;
 858     Int_t entry2index = -1;
 859     for (Int_t j = fEntries.GetEntriesFast() - 1; j >= 0; --j)
 860     {
 861       AliHLTDomainEntry* current = static_cast<const AliHLTDomainEntry*>( domain.fEntries.UncheckedAt(j) );
 862       if (current->TestBit(BIT(14))) continue;  // skip marked entries.
 863       if (entry1->IdenticalTo(*current) and entry1->Exclusive() == current->Exclusive())
 864       {
 865         entry2 = current;
 866         entry2index = j;
 867         break;
 868       }
 869     }
 870     if (entry2 == NULL)
 871     {
 872       // Could not find identical entry in domain.fEntries for fEntries[i] so we
 873       // will have at least one unmatched entry and thus the domains do not match.
 874       return false;
 875     }
 876     // Now check if entry2 has any subset entries below it. If it does then
 877     // it fails our ordering requirements and the domains cannot match.
 878     for (Int_t j = entry2index + 1; j < fEntries.GetEntriesFast(); ++j)
 879     {
 880       AliHLTDomainEntry* current = static_cast<const AliHLTDomainEntry*>( domain.fEntries.UncheckedAt(j) );
 881       if (current->TestBit(BIT(14))) continue;  // skip marked entries.
 882       if (entry1->SubsetOf(*current)) return false;
 883     }
 884     // If we got to this point then entry1 and entry2 are a match and obey the
 885     // ordering rules, so mark them.
 886     entry1->SetBit(BIT(14), true);
 887     entry2->SetBit(BIT(14), true);
 888   }
 889   // At this point we could find all pairs so the domains match.
 890   // We now just need to clear the bits that we set.
 891   for (Int_t i = 0; i < fEntries.GetEntriesFast() - 1; ++i)
 892   {
 893     fEntries[i]->SetBit(BIT(14), false);
 894     domain.fEntries[i]->SetBit(BIT(14), false);
 895   }
 896   return true;
 897 }
 898
 899
 900 AliHLTTriggerDomain::operator AliHLTReadoutList () const
 901 {
 902   // Typecast operator which constructs a readout list from the trigger domain.
 903
 904   AliHLTReadoutList result;
 905   for (Int_t deti = 0; deti < AliHLTDAQ::NumberOfDetectors(); deti++)
 906   {
 907     for (Int_t i = 0; i < AliHLTDAQ::NumberOfDdls(deti); i++)
 908     {
 909       Int_t ddlId = AliHLTDAQ::DdlID(deti, i);
 910       AliHLTComponentDataType type = AliHLTComponentDataTypeInitializer(kAliHLTDAQRDOUTDataTypeID, AliHLTDAQ::OnlineName(deti));
 911       if (Contains(AliHLTDomainEntry(type, ddlId)))
 912       {
 913         result.EnableDDLBit(ddlId);
 914       }
 915     }
 916   }
 917   return result;
 918 }
 919
 920
 921 void AliHLTTriggerDomain::MergeEntries(
 922     const bool* removeThisEntry, Int_t entriesCount,
 923     const bool* removeDomainEntry, Int_t startOfIntersects,
 924     const AliHLTTriggerDomain& domain
 925   )
 926 {
 927   // Merges the entries in this trigger domain with the ones in 'domain', while
 928   // removing all entries that were marked for removal.
 929   // See header file for more information.
 930
 931   bool anythingRemoved = false;
 932
 933   // Remember this method is used at the end of the calculation of the binary operators
 934   // and that fEntries is expected to be partitioned into 3 regions.
 935   //   - 0..entriesCount-1 : contains the original (initial) entries of this trigger domain.
 936   //   - entriesCount..startOfIntersects-1 : is space reserved for the new entries
 937   //       from the given trigger domain 'domain' being processed.
 938   //   - startOfIntersects..fEntries.GetEntriesFast()-1 : contains all new domain entry
 939   //       intersection created and added to fEntries.
 940   //
 941   // First we need to remove all entries marked for removal from the original entries.
 942   for (Int_t i = 0; i < entriesCount; i++)
 943   {
 944     if (removeThisEntry[i])
 945     {
 946       fEntries.RemoveAt(i);
 947       anythingRemoved = true;
 948     }
 949   }
 950
 951   // Now we copy over all the new entries from 'domain' which were not marked for removal
 952   // and indicate anythingRemoved = true since there will now be gaps in the clones array
 953   // that need to be compressed away later.
 954   for (Int_t i = 0; i < domain.fEntries.GetEntriesFast(); i++)
 955   {
 956     if (removeDomainEntry[i])
 957     {
 958       anythingRemoved = true;
 959     }
 960     else
 961     {
 962       const AliHLTDomainEntry* newEntry = static_cast<const AliHLTDomainEntry*>( domain.fEntries.UncheckedAt(i) );
 963       new (fEntries[entriesCount+i]) AliHLTDomainEntry(*newEntry);
 964     }
 965   }
 966
 967   // Finally remove all new intersection entries that were marked for removal by
 968   // the MarkForDeletionSubsetsOf method.
 969   for (Int_t i = startOfIntersects; i < fEntries.GetEntriesFast(); i++)
 970   {
 971     const AliHLTDomainEntry* ientry = static_cast<const AliHLTDomainEntry*>( fEntries.UncheckedAt(i) );
 972     if (ientry->TestBit(BIT(14)))
 973     {
 974       fEntries.RemoveAt(i);
 975       anythingRemoved = true;
 976     }
 977   }
 978   if (anythingRemoved) fEntries.Compress();
 979 }
 980
 981
 982 void AliHLTTriggerDomain::MarkForDeletionSubsetsOf(const AliHLTDomainEntry& entry, Int_t min)
 983 {
 984   // Marks for deletion all the entries in this trigger domain that are subsets
 985   // of the given entry.
 986   // See header file for more information.
 987
 988   AliHLTDomainEntry intersect;
 989   for (Int_t i = min; i < fEntries.GetEntriesFast(); i++)
 990   {
 991     AliHLTDomainEntry* ientry = static_cast<AliHLTDomainEntry*>( fEntries.UncheckedAt(i) );
 992     if (ientry->TestBit(BIT(14))) continue;
 993     if (ientry->SubsetOf(entry))
 994     {
 995       ientry->SetBit(BIT(14), true);
 996     }
 997   }
 998 }
 999
1000
1001 void AliHLTTriggerDomain::RemoveMarkedEntries()
1002 {
1003   // Removes all entries in this trigger domain which were marked for removal.
1004   // See header file for more information.
1005
1006   bool anythingRemoved = false;
1007   for (Int_t i = 0; i < fEntries.GetEntriesFast(); i++)
1008   {
1009     const AliHLTDomainEntry* ientry = static_cast<const AliHLTDomainEntry*>( fEntries.UncheckedAt(i) );
1010     if (ientry->TestBit(BIT(14)))
1011     {
1012       fEntries.RemoveAt(i);
1013       anythingRemoved = true;
1014     }
1015   }
1016   if (anythingRemoved) fEntries.Compress();
1017 }
1018
1019
1020 void AliHLTTriggerDomain::Optimise()
1021 {
1022   // Removes redundant trigger domain entries from the trigger domain.
1023   // See header file for more information.
1024
1025   AliHLTDomainEntry intersect;
1026
1027   // Check that the first entry is not and exclusion which would be redundent.
1028   if (fEntries.GetEntriesFast() == 0) return;
1029   AliHLTDomainEntry* firstEntry = static_cast<AliHLTDomainEntry*>( fEntries[0] );
1030   if (firstEntry->Exclusive()) firstEntry->SetBit(BIT(14), true);
1031
1032   for (Int_t i = 1; i < fEntries.GetEntriesFast(); i++)
1033   {
1034     AliHLTDomainEntry* ientry = static_cast<AliHLTDomainEntry*>( fEntries.UncheckedAt(i) );
1035
1036     // For the i'th entry in fEntries, compare it in reverse order with all other
1037     // entries that are before it and look for redundant ones, i.e. that are subsets
1038     // of the i'th entry.
1039     for (Int_t j = i-1; j >= 0; j--)
1040     {
1041       AliHLTDomainEntry* jentry = static_cast<AliHLTDomainEntry*>( fEntries.UncheckedAt(j) );
1042       if (jentry->TestBit(BIT(14))) continue;
1043       // Find entries that intersect
1044       if (jentry->SubsetOf(*ientry))
1045       {
1046         // jentry is a subset of ientry so it is redundant because for all values
1047         // ientry will override jentry when calling IncludeInReadout.
1048         jentry->SetBit(BIT(14), true);
1049       }
1050       else if (*ientry == *jentry)
1051       {
1052         // If intersecting entries have opposite exclude flags then search no further,
1053         // we know that we will need this entry for correct behaviour of IncludeInReadout.
1054         if (ientry->Inclusive() == jentry->Exclusive()) goto processNextEntry;
1055
1056         if (ientry->SubsetOf(*jentry))
1057         {
1058           ientry->SetBit(BIT(14), true);
1059           goto processNextEntry;
1060         }
1061       }
1062     }
1063
1064     // If we got to this point then we hit the top of the trigger domain rules
1065     // (pattern matching) list without hitting any and overlapping entries.
1066     // So now we need to check if ientry is an exclusion. If it is, then it is
1067     // redundant and we can mark it for removal.
1068     if (ientry->Exclusive()) ientry->SetBit(BIT(14), true);
1069
1070     processNextEntry: ;
1071   }
1072
1073   RemoveMarkedEntries();
1074 }
1075
1076 const AliHLTDomainEntry& AliHLTTriggerDomain::operator[](int index) const
1077 {
1078   // Access individual entry of the domain
1079   return static_cast<AliHLTDomainEntry&>(*fEntries[index]);
1080 }