blob: d110586cdcbc6d6e4282d33680ebd0c76a486280 (
plain)
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
|
#ifndef hVYFXl0fhRtHkuIHnrxmZOhDCeI
#define hVYFXl0fhRtHkuIHnrxmZOhDCeI
#include <assert.h>
#include <string>
#include "time.hpp"
#include "checkpoint.hpp"
#include "simlimits.hpp"
#include "template_helpers.hpp"
#include "vector.hpp"
// TODO: update r/w-barriers in vector
using std::string;
template<typename Quant>
struct Index;
template<typename Ptr>
struct CommonIndex {
CommonIndex() = delete;
CommonIndex(const string name, Ptr max);
// type and const defs
typedef Ptr ptr_t;
static constexpr ptr_t nil() {
BOOST_STATIC_ASSERT(( (ptr_t) -1 > 0 ));
return -1;
}
// read operations
// HINT: time refers to creation time, not delievery time; the
// later is handled by Filter<>
inline ptr_t last(); // returns the latest known event
ptr_t last(Time t); // ... before (or at) time t
inline ptr_t first(); // ... after (or at) ...
ptr_t first(Time t);
ptr_t binarySearch(Time t);
virtual void sync() {
time.barrierRead() = time.barrierWrite();
time.sync();
}
// vector storing timing
Vector<Time> time;
// writing
inline ptr_t add(Time t);
};
template<typename Ptr>
inline typename CommonIndex<Ptr>::ptr_t CommonIndex<Ptr>::last() {
// get ptr from any barrier (all should be the same!)
ptr_t id = time.barrierWrite.get();
if (id==0)
return nil();
else
return id - 1;
}
template<typename Ptr>
inline typename CommonIndex<Ptr>::ptr_t CommonIndex<Ptr>::first() {
// get ptr from any barrier (all should be the same!)
ptr_t id = time.barrierWrite.get();
if (id==0)
return nil();
else
return 0;
}
template<typename Ptr>
CommonIndex<Ptr>::CommonIndex(const string name, ptr_t max) :
time(name, max)
{}
template<typename Ptr>
typename CommonIndex<Ptr>::ptr_t CommonIndex<Ptr>::last(Time t) {
ptr_t cur = binarySearch(t);
if ((cur == nil()) or (time(cur) > t))
return nil();
// there may be several elements with time = t; go to the last one
while ((cur < last()) && (time(cur + 1) == t))
cur++;
return cur;
}
template<typename Ptr>
typename CommonIndex<Ptr>::ptr_t CommonIndex<Ptr>::first(Time t) {
ptr_t cur = binarySearch(t);
if (cur == nil())
return nil();
if ((time(cur) < t) && (cur < last()))
cur = cur + 1;
if (time(cur) < t)
return nil();
// there may be several elements with time = t; go to the first one
while ((cur > first()) && (time(cur - 1) == t))
cur--;
return cur;
}
template<typename Ptr>
typename CommonIndex<Ptr>::ptr_t CommonIndex<Ptr>::binarySearch(Time t) {
// TODO (optimize): use a constant frequency approximation to
// initialize min, max and pivot (w/ proper fallback)
// get the limits of the heap
ptr_t max = last();
if (max == nil()) return nil(); // no elements, yet
ptr_t min = first();
// check if t \in [min, max]
if (t > time(max)) return max;
if (t < time(min)) return min;
// binary search in the heap
// invariant: min <= target <= max
while ((time(min) != time(max))) {
ptr_t pivot = (min + max + 1) / 2;
if (t >= time(pivot)) {
min = pivot;
}else{
max = pivot - 1;
}
}
return max; // min would be ok, too
}
template<typename Ptr>
inline typename CommonIndex<Ptr>::ptr_t CommonIndex<Ptr>::add(Time aTime) {
ptr_t id = last() + 1; // get position to write
time.set(id, aTime); // add new record
time.barrierWrite.set(id + 1); // increase write barrier
return id;
}
#endif // hVYFXl0fhRtHkuIHnrxmZOhDCeI
|
