modules/core/include/dpl/task.h

   1 /*
   2  * Copyright (c) 2011 Samsung Electronics Co., Ltd All Rights Reserved
   3  *
   4  *    Licensed under the Apache License, Version 2.0 (the "License");
   5  *    you may not use this file except in compliance with the License.
   6  *    You may obtain a copy of the License at
   7  *
   8  *        http://www.apache.org/licenses/LICENSE-2.0
   9  *
  10  *    Unless required by applicable law or agreed to in writing, software
  11  *    distributed under the License is distributed on an "AS IS" BASIS,
  12  *    WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
  13  *    See the License for the specific language governing permissions and
  14  *    limitations under the License.
  15  */
  16 /*
  17  * @file    task.h
  18  * @author  Przemyslaw Dobrowolski (p.dobrowolsk@samsung.com)
  19  * @author  Radoslaw Wicik (r.wicik@samsung.com)
  20  * @version 1.0
  21  * @brief   Header file for abstaract task definition
  22  */
  23 #ifndef DPL_TASK_H
  24 #define DPL_TASK_H
  25
  26 #include <dpl/scoped_array.h>
  27 #include <dpl/noncopyable.h>
  28 #include <dpl/union_cast.h>
  29 #include <dpl/semaphore.h>
  30 #include <dpl/foreach.h>
  31 #include <dpl/mutex.h>
  32 #include <dpl/assert.h>
  33 #include <dpl/log/log.h>
  34 #include <algorithm>
  35 #include <sstream>
  36 #include <iomanip>
  37 #include <list>
  38 #include <stack>
  39 #include <cctype>
  40
  41 namespace DPL
  42 {
  43 class TaskList;
  44
  45 class Task
  46     : private Noncopyable
  47 {
  48 public:
  49     virtual ~Task() {}
  50
  51     virtual bool NextStep() = 0;
  52     virtual bool Abort() = 0;
  53     virtual size_t GetStepCount() const = 0;
  54 };
  55
  56 template<typename Impl>
  57 class TaskDecl
  58     : public Task
  59 {
  60 protected:
  61     typedef void (Impl::*Step)();
  62
  63 private:
  64     typedef std::list<Step> StepList;
  65
  66     StepList m_steps;
  67     StepList m_abortSteps;
  68     typename StepList::iterator m_currentStep;
  69     typename StepList::iterator m_nextStep;
  70     bool m_switched;
  71
  72     Impl *m_impl;
  73     bool m_running;
  74
  75 protected:
  76     void AddStep(Step step)
  77     {
  78         Assert(!m_running && "AddStep is not allowed after calling NextStep!");
  79         Assert(m_steps.end() == std::find(m_steps.begin(), m_steps.end(), step) && "The same step started twice is not supported");
  80         m_steps.push_back(step);
  81         m_nextStep = m_steps.begin();
  82     }
  83
  84     void AddAbortStep(Step step)
  85     {
  86         Assert(!m_running && "AddAbortStep is not allowed after calling NextStep!");
  87         Assert(m_abortSteps.end() == std::find(m_abortSteps.begin(), m_abortSteps.end(), step) && "The same step started twice is not supported");
  88         m_abortSteps.push_front(step);
  89     }
  90
  91     void SwitchToStep(Step step)
  92     {
  93         /// @TODO There can be problem here if user sets the same method two times in task list.
  94         typename StepList::iterator i = std::find(m_steps.begin(), m_steps.end(), step);
  95         Assert(i != m_steps.end());
  96         m_nextStep = i;
  97         m_switched = true;
  98     }
  99
 100     Step GetCurrentStep() const
 101     {
 102         if(m_currentStep == m_steps.end())
 103             return NULL;
 104
 105         return *m_currentStep;
 106     }
 107
 108 public:
 109     TaskDecl(Impl *impl)
 110         : m_switched(false),
 111           m_impl(impl),
 112           m_running(false)
 113     {
 114         Assert(this == m_impl);
 115         m_currentStep = m_steps.end();
 116         m_nextStep = m_steps.end();
 117     }
 118
 119     bool NextStep()
 120     {
 121         m_running = true;
 122
 123         Assert(m_nextStep != m_steps.end() && "Step list is empty or all steps done");
 124
 125         m_switched = false;
 126
 127         Step call = *m_nextStep;
 128         (*m_impl.*call)();
 129
 130         m_currentStep = m_nextStep;
 131
 132         if (m_switched)
 133             return true;
 134         else
 135             return ++m_nextStep != m_steps.end();
 136     }
 137
 138     bool Abort()
 139     {
 140         m_running = true;
 141
 142         m_steps.clear();
 143
 144         if (m_abortSteps.empty())
 145             return false;
 146
 147         FOREACH (it, m_abortSteps)
 148             m_steps.push_back(*it);
 149
 150         m_nextStep = m_steps.begin();
 151
 152         m_abortSteps.clear();
 153
 154         return true;
 155     }
 156
 157     size_t GetStepCount() const
 158     {
 159         return static_cast<size_t>(m_steps.size());
 160     }
 161 };
 162
 163 template<typename ImplementationType>
 164 class MultiTaskDecl
 165     : public Task
 166 {
 167 protected:
 168     typedef void (ImplementationType::*Step)();
 169     typedef std::list<Step> StepList;
 170     typedef std::stack<Step> StepStack;
 171
 172 private:
 173     static std::string StepToString(Step step)
 174     {
 175         std::ostringstream pseudoAddressStream;
 176         pseudoAddressStream << std::hex << union_cast<size_t>(step);
 177
 178         std::string pseudoAddress = pseudoAddressStream.str();
 179
 180         std::transform(pseudoAddress.begin(), pseudoAddress.end(),
 181                        pseudoAddress.begin(), ::toupper);
 182
 183         return std::string("0x") + pseudoAddress;
 184     }
 185
 186     struct ConditionalStep
 187     {
 188         Step step;
 189
 190         // Depencency lists
 191         StepList unsatisfiedDependencies;
 192         StepList satisfiedDependencies;
 193
 194         ConditionalStep()
 195             : step(NULL)
 196         {
 197         }
 198
 199         ConditionalStep(Step stepArg,
 200                         StepList dependenciesArg)
 201             : step(stepArg),
 202               unsatisfiedDependencies(dependenciesArg)
 203         {
 204         }
 205     };
 206
 207     typedef std::list<ConditionalStep> ConditionalStepList;
 208
 209     // Synchronization
 210     Semaphore m_activeStepsSemaphore;
 211     mutable Mutex m_dependencyListMutex;
 212
 213     // Those steps that have their dependency lists satified and are ready
 214     // to be executed
 215     // Current step is defined to be the front of satisfied list
 216     ConditionalStepList m_satisfiedSteps;
 217
 218     // Those steps that are going to be executed but their dependency
 219     // lists have not been satified
 220     ConditionalStepList m_unsatisfiedSteps;
 221
 222     // Those steps that have their dependency lists satified and are currently
 223     // being executed
 224     ConditionalStepList m_executingSteps;
 225
 226     // Those steps that have been executed with their dependency lists
 227     // satisfied
 228     ConditionalStepList m_historicSteps;
 229
 230     ///< Growing list of submitted abort steps
 231     StepStack m_abortSteps;
 232
 233     // Deriving implementation
 234     ImplementationType *m_implementation;
 235
 236     // Max parallel steps
 237     size_t m_maxParallelCount;
 238
 239     ///< Valid in dependency list mutex only
 240     void SatisfyDependencies(const ConditionalStep &conditionalStep)
 241     {
 242         LogPedantic("Satisfying steps with dependecy to step: "
 243                     << StepToString(conditionalStep.step));
 244
 245         // Can satisfy conditional steps if and only if there are no more
 246         // satisfied, unsatisfied or running same steps
 247         // There is at least one historic step - this one
 248         if (IsContainingStep(conditionalStep.step, m_unsatisfiedSteps) ||
 249             IsContainingStep(conditionalStep.step, m_satisfiedSteps) ||
 250             IsContainingStep(conditionalStep.step, m_executingSteps))
 251         {
 252             LogPedantic("Step " << StepToString(conditionalStep.step)
 253                         << " cannot satify other steps yet");
 254
 255             return;
 256         }
 257
 258         LogPedantic("Step " << StepToString(conditionalStep.step)
 259                     << " can satify other steps");
 260
 261         // Do satisfy
 262         typename ConditionalStepList::iterator unsatisfiedStepIterator =
 263             m_unsatisfiedSteps.begin();;
 264
 265         while (unsatisfiedStepIterator != m_unsatisfiedSteps.end())
 266         {
 267             typename StepList::iterator iterator =
 268                 std::find(
 269                     unsatisfiedStepIterator->unsatisfiedDependencies.begin(),
 270                     unsatisfiedStepIterator->unsatisfiedDependencies.end(),
 271                     conditionalStep.step);
 272
 273             // Does this conditional step need to be satisfied ?
 274             if (iterator ==
 275                 unsatisfiedStepIterator->unsatisfiedDependencies.end())
 276             {
 277                 continue;
 278             }
 279
 280             LogPedantic("Satisfying step "
 281                         << StepToString(unsatisfiedStepIterator->step)
 282                         << " dependency to step "
 283                         << StepToString(conditionalStep.step));
 284
 285             // Satisfy dependency
 286             unsatisfiedStepIterator->unsatisfiedDependencies.erase(
 287                 iterator);
 288
 289             unsatisfiedStepIterator->satisfiedDependencies.push_back(
 290                 conditionalStep.step);
 291
 292             // If step is fully satisfied, transfer it to the satisfied
 293             // steps list
 294             if (unsatisfiedStepIterator->unsatisfiedDependencies.empty())
 295             {
 296                 LogPedantic("Step "
 297                             << StepToString(unsatisfiedStepIterator->step)
 298                             << " is fully satisfied");
 299
 300                 // Move step
 301                 m_satisfiedSteps.push_back(*unsatisfiedStepIterator);
 302
 303                 unsatisfiedStepIterator =
 304                     m_unsatisfiedSteps.erase(unsatisfiedStepIterator);
 305
 306                 continue;
 307             }
 308
 309             // Check next unsatisfied step
 310             ++unsatisfiedStepIterator;
 311         }
 312     }
 313
 314     ///< Valid in dependency list mutex only
 315     bool IsContainingStep(Step step, const ConditionalStepList &dependencies) const
 316     {
 317         FOREACH (iterator, dependencies)
 318             if (iterator->step == step)
 319                 return true;
 320
 321         return false;
 322     }
 323
 324     ///< Valid in dependency list mutex only
 325     bool IsStepDependecyListSatisfied(
 326         const StepList &dependencies) const
 327     {
 328         // All dependant step must be historic
 329         FOREACH (iterator, dependencies)
 330             if (!IsContainingStep(*iterator, m_historicSteps))
 331                 return false;
 332
 333         // Also, none dependant step can exist in
 334         // unsatisfied/satisfied/inProgress lists
 335         FOREACH (iterator, dependencies)
 336         {
 337             if (IsContainingStep(*iterator, m_unsatisfiedSteps) ||
 338                 IsContainingStep(*iterator, m_satisfiedSteps) ||
 339                 IsContainingStep(*iterator, m_executingSteps))
 340             {
 341                 return false;
 342             }
 343         }
 344
 345         return true;
 346     }
 347
 348     bool AbortInternal()
 349     {
 350         // Clear all steps and construct
 351         // a single-dependency list of abort steps
 352         m_unsatisfiedSteps.clear();
 353         m_satisfiedSteps.clear();
 354         m_executingSteps.clear();
 355         m_historicSteps.clear();
 356
 357         if (m_abortSteps.empty())
 358             return false;
 359
 360         // Register last abort step as satisfied
 361         m_satisfiedSteps.push_back(
 362             ConditionalStep(
 363                 m_abortSteps.top(),
 364                 StepList()));
 365
 366         Step lastStep = m_abortSteps.top();
 367         m_abortSteps.pop();
 368
 369         // Create abort step list
 370         while (!m_abortSteps.empty())
 371         {
 372             // Add next unsatisfied step
 373             StepList dependencies;
 374             dependencies.push_back(lastStep);
 375
 376             m_unsatisfiedSteps.push_back(
 377                 ConditionalStep(
 378                     m_abortSteps.top(),
 379                     dependencies));
 380
 381             // Remove top abort step
 382             lastStep = m_abortSteps.top();
 383             m_abortSteps.pop();
 384         }
 385
 386         return true;
 387     }
 388
 389 protected:
 390     void AddStep(Step step,
 391                  const StepList &dependencies)
 392     {
 393         Mutex::ScopedLock lock(&m_dependencyListMutex);
 394
 395         LogPedantic("Adding step: " << StepToString(step));
 396
 397         FOREACH (iterator, dependencies)
 398             LogPedantic("  Dependency: " << StepToString(*iterator));
 399
 400         // Add step to proper list
 401         if (IsStepDependecyListSatisfied(dependencies))
 402         {
 403             m_satisfiedSteps.push_back(ConditionalStep(step, dependencies));
 404
 405             LogPedantic("Step " << StepToString(step) << " is satisfied");
 406         }
 407         else
 408         {
 409             m_unsatisfiedSteps.push_back(ConditionalStep(step, dependencies));
 410
 411             LogPedantic("Step " << StepToString(step) << " is unsatisfied");
 412         }
 413
 414         LogPedantic("Satisfied step count: " << m_satisfiedSteps.size());
 415         LogPedantic("Unsatisfied step count: " << m_unsatisfiedSteps.size());
 416     }
 417
 418     void AddAbortStep(Step step)
 419     {
 420         Mutex::ScopedLock lock(&m_dependencyListMutex);
 421
 422         m_abortSteps.push_front(step);
 423
 424         LogPedantic("Abort step count: " << m_abortSteps.size());
 425     }
 426
 427 public:
 428     MultiTaskDecl(ImplementationType *implementation,
 429                   size_t maxParallelCount)
 430         : m_activeStepsSemaphore(maxParallelCount),
 431           m_implementation(implementation),
 432           m_maxParallelCount(maxParallelCount)
 433     {
 434     }
 435
 436     bool NextStep()
 437     {
 438         ConditionalStep stepToExecute;
 439         typename ConditionalStepList::iterator executingStepIterator;
 440
 441         // Take the main semaphore lock
 442         Semaphore::ScopedLock semaphoreLock(&m_activeStepsSemaphore);
 443
 444         // Take the dependency list lock
 445         {
 446             Mutex::ScopedLock listLock(&m_dependencyListMutex);
 447
 448             // Get next step to execute
 449             if (m_satisfiedSteps.empty())
 450             {
 451                 LogPedantic("No more satisfied steps to execute");
 452                 return false;
 453             }
 454
 455             // Get next satisfied step to execute
 456             stepToExecute = m_satisfiedSteps.front();
 457             m_satisfiedSteps.pop_front();
 458
 459             // Register it in executing step list
 460             m_executingSteps.push_back(stepToExecute);
 461             executingStepIterator = --m_executingSteps.end();
 462
 463             // Leave the dependency list lock
 464         }
 465
 466         // Execute step
 467         (*m_implementation.*stepToExecute.step)();
 468
 469         // Take a lock again
 470         {
 471             Mutex::ScopedLock listLock(&m_dependencyListMutex);
 472
 473             // Unregister executing step
 474             m_executingSteps.erase(executingStepIterator);
 475
 476             // Add historic step
 477             m_historicSteps.push_back(stepToExecute);
 478
 479             // Satisfy dependencies
 480             SatisfyDependencies(stepToExecute);
 481
 482             // Leave lock
 483         }
 484
 485         // Done
 486         return true;
 487     }
 488
 489     bool Abort()
 490     {
 491         // Wait until all active steps are done
 492         // This is achieved by taking all semaphore slots
 493         ScopedArray<Semaphore::ScopedLock *> semaphoreLocks(
 494             new Semaphore::ScopedLock *[m_maxParallelCount]);
 495
 496         for (size_t i = 0; i < m_maxParallelCount; ++i)
 497             semaphoreLocks[i] = new Semaphore::ScopedLock(
 498                 &m_activeStepsSemaphore);
 499
 500         // Result
 501         bool result;
 502
 503         // Take step lists lock
 504         {
 505             Mutex::ScopedLock mutexLock(&m_dependencyListMutex);
 506
 507             // Do internal abort
 508             result = AbortInternal();
 509
 510             // Leave steps list lock
 511         }
 512
 513         // Leave semaphore locks
 514         for (size_t i = 0; i < m_maxParallelCount; ++i)
 515             delete semaphoreLocks[i];
 516
 517         // Return result
 518         return result;
 519     }
 520
 521     size_t GetStepCount() const
 522     {
 523         // Return sum of sizes of all lists
 524         Mutex::ScopedLock lock(&m_dependencyListMutex);
 525
 526         return static_cast<size_t>(
 527             m_unsatisfiedSteps.size() +
 528             m_satisfiedSteps.size() +
 529             m_executingSteps.size() +
 530             m_historicSteps.size());
 531     }
 532 };
 533 } // namespace DPL
 534
 535 #endif // DPL_TASK_H