View | Details | Raw Unified | Return to bug 2498
Collapse All | Expand All

(-)a/src/core/model/calendar-scheduler.cc (-6 / +7 lines)
 Lines 16-21    Link Here 
16 
 * Foundation, Inc., 59 Temple Place, Suite 330, Boston, MA  02111-1307  USA
 16 
 * Foundation, Inc., 59 Temple Place, Suite 330, Boston, MA  02111-1307  USA
17 
 *
 17 
 *
18 
 * Author: Mathieu Lacage <mathieu.lacage@sophia.inria.fr>
 18 
 * Author: Mathieu Lacage <mathieu.lacage@sophia.inria.fr>
19 
 * Author: Alexander Krotov <krotov@iitp.ru>
19 
 */
 20 
 */
20 

          21
          

        

        

          21
          
#include "calendar-scheduler.h"

          22
          
#include "calendar-scheduler.h"

        

  

    

    

       Lines 108-114
       
    
  Link Here 
    

  

        

          108
          
  Bucket::iterator end = m_buckets[bucket].end ();

          109
          
  Bucket::iterator end = m_buckets[bucket].end ();

        

        

          109
          
  for (Bucket::iterator i = m_buckets[bucket].begin (); i != end; ++i)

          110
          
  for (Bucket::iterator i = m_buckets[bucket].begin (); i != end; ++i)

        

        

          110
          
    {

          111
          
    {

        

          
            

              111
              
      if (ev.key < i->key)


              112
              
      if (ev.key > i->key)

            

        

          112
          
        {

          113
          
        {

        

        

          113
          
          m_buckets[bucket].insert (i, ev);

          114
          
          m_buckets[bucket].insert (i, ev);

        

        

          114
          
          return;

          115
          
          return;

        

  

    

    

       Lines 147-153
       
    
  Link Here 
    

  

        

          147
          
    {

          148
          
    {

        

        

          148
          
      if (!m_buckets[i].empty ())

          149
          
      if (!m_buckets[i].empty ())

        

        

          149
          
        {

          150
          
        {

        

          
            

              150
              
          Scheduler::Event next = m_buckets[i].front ();


              151
              
          Scheduler::Event next = m_buckets[i].back ();

            

        

          151
          
          if (next.key.m_ts < bucketTop)

          152
          
          if (next.key.m_ts < bucketTop)

        

        

          152
          
            {

          153
          
            {

        

        

          153
          
              return next;

          154
          
              return next;

        

  

    

    

       Lines 183-195
       
    
  Link Here 
    

  

        

          183
          
    {

          184
          
    {

        

        

          184
          
      if (!m_buckets[i].empty ())

          185
          
      if (!m_buckets[i].empty ())

        

        

          185
          
        {

          186
          
        {

        

          
            

              186
              
          Scheduler::Event next = m_buckets[i].front ();


              187
              
          Scheduler::Event next = m_buckets[i].back ();

            

        

          187
          
          if (next.key.m_ts < bucketTop)

          188
          
          if (next.key.m_ts < bucketTop)

        

        

          188
          
            {

          189
          
            {

        

        

          189
          
              m_lastBucket = i;

          190
          
              m_lastBucket = i;

        

        

          190
          
              m_lastPrio = next.key.m_ts;

          191
          
              m_lastPrio = next.key.m_ts;

        

        

          191
          
              m_bucketTop = bucketTop;

          192
          
              m_bucketTop = bucketTop;

        

          
            

              192
              
              m_buckets[i].pop_front ();


              193
              
              m_buckets[i].pop_back ();

            

        

          193
          
              return next;

          194
          
              return next;

        

        

          194
          
            }

          195
          
            }

        

        

          195
          
          if (next.key < minKey)

          196
          
          if (next.key < minKey)

        

  

    

    

       Lines 207-214
       
    
  Link Here 
    

  

        

          207
          
  m_lastPrio = minKey.m_ts;

          208
          
  m_lastPrio = minKey.m_ts;

        

        

          208
          
  m_lastBucket = Hash (minKey.m_ts);

          209
          
  m_lastBucket = Hash (minKey.m_ts);

        

        

          209
          
  m_bucketTop = (minKey.m_ts / m_width + 1) * m_width;

          210
          
  m_bucketTop = (minKey.m_ts / m_width + 1) * m_width;

        

          
            

              210
              
  Scheduler::Event next = m_buckets[minBucket].front();


              211
              
  Scheduler::Event next = m_buckets[minBucket].back ();

            

            

              211
              
  m_buckets[minBucket].pop_front ();


              212
              
  m_buckets[minBucket].pop_back ();

            

        

          212
          

          213
          

        

        

          213
          
  return next;

          214
          
  return next;

        

        

          214
          
}

          215
          
}

        



(-)a/src/core/model/calendar-scheduler.h
      (-5 / +8 lines)




  

    

    

       Lines 16-21
       
    
  Link Here 
    

  

        

          16
          
 * Foundation, Inc., 59 Temple Place, Suite 330, Boston, MA  02111-1307  USA

          16
          
 * Foundation, Inc., 59 Temple Place, Suite 330, Boston, MA  02111-1307  USA

        

        

          17
          
 *

          17
          
 *

        

        

          18
          
 * Author: Mathieu Lacage <mathieu.lacage@sophia.inria.fr>

          18
          
 * Author: Mathieu Lacage <mathieu.lacage@sophia.inria.fr>

        

            

              
              
              19
              
 * Author: Alexander Krotov <krotov@iitp.ru>

            

        

          19
          
 */

          20
          
 */

        

        

          20
          

          21
          

        

        

          21
          
#ifndef CALENDAR_SCHEDULER_H

          22
          
#ifndef CALENDAR_SCHEDULER_H

        

  

    

    

       Lines 47-57
       
    
  Link Here 
    

  

        

          47
          
 * the original algorithm (to the best of my knowledge).

          48
          
 * the original algorithm (to the best of my knowledge).

        

        

          48
          
 *

          49
          
 *

        

        

          49
          
 * \note

          50
          
 * \note

        

          
            

              50
              
 * This queue is much slower than I expected (much slower than the


              51
              
 * While inserion sort is not discussed in the original article, its

            

            

              51
              
 * std::map queue) and this seems to be because the original resizing policy


              52
              
 * implementation appears to dramatically affect performance.

            

            

              52
              
 * is horribly bad.  This is most likely the reason why there have been


              53
              
 * CalendarScheduler sorts buckets in \em reverse chronological order.

            

            

              53
              
 * so many variations published which all slightly tweak the resizing


              54
              
 * This heuristic, originating in NS-2 implementation of

            

            

              54
              
 * heuristics to obtain a better distribution of events across buckets.


              55
              
 * calendar scheduler, reduces enqueue time, as it is likely that

            

            

              
              

              56
              
 * timestamp of new event is greater than timestamp of already

            

            


              57
              
 * scheduled event.

            

        

          55
          
 */

          58
          
 */

        

        

          56
          
class CalendarScheduler : public Scheduler

          59
          
class CalendarScheduler : public Scheduler

        

        

          57
          
{

          60
          
{

        






  

  Return to bug 2498