← Back to branch summary

~ps10gel/ubuntu/xenial/trafficserver/6.2.0

« back to all changes in this revision

Viewing changes to iocore/eventsystem/I_PriorityEventQueue.h

  • Committer: Bazaar Package Importer
  • Author(s): Arno Toell
  • Date: 2011-01-13 11:49:18 UTC
  • Revision ID: james.westby@ubuntu.com-20110113114918-vu422h8dknrgkj15
Tags: upstream-2.1.5-unstable
Import upstream version 2.1.5-unstable

Show diffs side-by-side

added added

removed removed

Lines of Context:
iocore/eventsystem/I_PriorityEventQueue.h
 
1
/** @file
 
2
 
 
3
  Queue of Events sorted by the "at_timeout" field
 
4
 
 
5
  @section license License
 
6
 
 
7
  Licensed to the Apache Software Foundation (ASF) under one
 
8
  or more contributor license agreements.  See the NOTICE file
 
9
  distributed with this work for additional information
 
10
  regarding copyright ownership.  The ASF licenses this file
 
11
  to you under the Apache License, Version 2.0 (the
 
12
  "License"); you may not use this file except in compliance
 
13
  with the License.  You may obtain a copy of the License at
 
14
 
 
15
      http://www.apache.org/licenses/LICENSE-2.0
 
16
 
 
17
  Unless required by applicable law or agreed to in writing, software
 
18
  distributed under the License is distributed on an "AS IS" BASIS,
 
19
  WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
 
20
  See the License for the specific language governing permissions and
 
21
  limitations under the License.
 
22
 */
 
23
 
 
24
#ifndef _I_PriorityEventQueue_h_
 
25
#define _I_PriorityEventQueue_h_
 
26
 
 
27
#include "libts.h"
 
28
#include "I_ProxyAllocator.h"
 
29
#include "I_Event.h"
 
30
 
 
31
 
 
32
// <5ms, 10, 20, 40, 80, 160, 320, 640, 1280, 2560, 5120
 
33
#define N_PQ_LIST        10
 
34
#define PQ_BUCKET_TIME(_i) (HRTIME_MSECONDS(5) << (_i))
 
35
 
 
36
class EThread;
 
37
 
 
38
struct PriorityEventQueue
 
39
{
 
40
 
 
41
  Que(Event, link) after[N_PQ_LIST];
 
42
  ink_hrtime last_check_time;
 
43
  uint32_t last_check_buckets;
 
44
 
 
45
  void enqueue(Event * e, ink_hrtime now)
 
46
  {
 
47
    ink_hrtime t = e->timeout_at - now;
 
48
    int i = 0;
 
49
    // equivalent but faster
 
50
    if (t <= PQ_BUCKET_TIME(3))
 
51
    {
 
52
      if (t <= PQ_BUCKET_TIME(1)) {
 
53
        if (t <= PQ_BUCKET_TIME(0)) {
 
54
          i = 0;
 
55
        } else
 
56
        {
 
57
          i = 1;
 
58
        }
 
59
      } else {
 
60
        if (t <= PQ_BUCKET_TIME(2)) {
 
61
          i = 2;
 
62
        } else {
 
63
          i = 3;
 
64
        }
 
65
      }
 
66
    } else {
 
67
      if (t <= PQ_BUCKET_TIME(7)) {
 
68
        if (t <= PQ_BUCKET_TIME(5)) {
 
69
          if (t <= PQ_BUCKET_TIME(4)) {
 
70
            i = 4;
 
71
          } else {
 
72
            i = 5;
 
73
          }
 
74
        } else {
 
75
          if (t <= PQ_BUCKET_TIME(6)) {
 
76
            i = 6;
 
77
          } else {
 
78
            i = 7;
 
79
          }
 
80
        }
 
81
      } else {
 
82
        if (t <= PQ_BUCKET_TIME(8)) {
 
83
          i = 8;
 
84
        } else {
 
85
          i = 9;
 
86
        }
 
87
      }
 
88
    }
 
89
    e->in_the_priority_queue = 1;
 
90
    e->in_heap = i;
 
91
    after[i].enqueue(e);
 
92
  }
 
93
 
 
94
  void remove(Event * e)
 
95
  {
 
96
    ink_assert(e->in_the_priority_queue);
 
97
    e->in_the_priority_queue = 0;
 
98
    after[e->in_heap].remove(e);
 
99
  }
 
100
 
 
101
  Event *dequeue_ready(ink_hrtime t)
 
102
  {
 
103
    (void) t;
 
104
    Event *e = after[0].dequeue();
 
105
    if (e) {
 
106
      ink_assert(e->in_the_priority_queue);
 
107
      e->in_the_priority_queue = 0;
 
108
    }
 
109
    return e;
 
110
  }
 
111
 
 
112
  void check_ready(ink_hrtime now, EThread * t);
 
113
 
 
114
  ink_hrtime earliest_timeout()
 
115
  {
 
116
    for (int i = 0; i < N_PQ_LIST; i++) {
 
117
      if (after[i].head)
 
118
        return last_check_time + (PQ_BUCKET_TIME(i) / 2);
 
119
    }
 
120
    return last_check_time + HRTIME_FOREVER;
 
121
  }
 
122
 
 
123
  PriorityEventQueue();
 
124
};
 
125
 
 
126
#endif