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
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
|
/* -*- Mode: C++; tab-width: 8; indent-tabs-mode: nil; c-basic-offset: 2 -*- */
/* vim: set ts=8 sts=2 et sw=2 tw=80: */
/* This Source Code Form is subject to the terms of the Mozilla Public
* License, v. 2.0. If a copy of the MPL was not distributed with this
* file, You can obtain one at http://mozilla.org/MPL/2.0/. */
#ifndef mozilla_RollingNumber_h_
#define mozilla_RollingNumber_h_
#include "mozilla/Assertions.h"
#include "mozilla/Attributes.h"
#include <limits>
namespace mozilla {
// Unsigned number suited to index elements in a never-ending queue, as
// order-comparison behaves nicely around the overflow.
//
// Additive operators work the same as for the underlying value type, but
// expect "small" jumps, as should normally happen when manipulating indices.
//
// Comparison functions are different, they keep the ordering based on the
// distance between numbers, modulo the value type range:
// If the distance is less than half the range of the value type, the usual
// ordering stays.
// 0 < 1, 2^23 < 2^24
// However if the distance is more than half the range, we assume that we are
// continuing along the queue, and therefore consider the smaller number to
// actually be greater!
// uint(-1) < 0.
//
// The expected usage is to always work on nearby rolling numbers: slowly
// incrementing/decrementing them, and translating&comparing them within a
// small window.
// To enforce this usage during development, debug-build assertions catch API
// calls involving distances of more than a *quarter* of the type range.
// In non-debug builds, all APIs will still work as consistently as possible
// without crashing, but performing operations on "distant" nunbers could lead
// to unexpected results.
template <typename T>
class RollingNumber {
static_assert(!std::numeric_limits<T>::is_signed,
"RollingNumber only accepts unsigned number types");
public:
using ValueType = T;
RollingNumber() : mIndex(0) {}
explicit RollingNumber(ValueType aIndex) : mIndex(aIndex) {}
RollingNumber(const RollingNumber&) = default;
RollingNumber& operator=(const RollingNumber&) = default;
ValueType Value() const { return mIndex; }
// Normal increments/decrements.
RollingNumber& operator++() {
++mIndex;
return *this;
}
RollingNumber operator++(int) { return RollingNumber{mIndex++}; }
RollingNumber& operator--() {
--mIndex;
return *this;
}
RollingNumber operator--(int) { return RollingNumber{mIndex--}; }
RollingNumber& operator+=(const ValueType& aIncrement) {
MOZ_ASSERT(aIncrement <= MaxDiff);
mIndex += aIncrement;
return *this;
}
RollingNumber operator+(const ValueType& aIncrement) const {
RollingNumber n = *this;
return n += aIncrement;
}
RollingNumber& operator-=(const ValueType& aDecrement) {
MOZ_ASSERT(aDecrement <= MaxDiff);
mIndex -= aDecrement;
return *this;
}
// Translate a RollingNumber by a negative value.
RollingNumber operator-(const ValueType& aDecrement) const {
RollingNumber n = *this;
return n -= aDecrement;
}
// Distance between two RollingNumbers, giving a value.
ValueType operator-(const RollingNumber& aOther) const {
ValueType diff = mIndex - aOther.mIndex;
MOZ_ASSERT(diff <= MaxDiff);
return diff;
}
// Normal (in)equality operators.
bool operator==(const RollingNumber& aOther) const {
return mIndex == aOther.mIndex;
}
bool operator!=(const RollingNumber& aOther) const {
return !(*this == aOther);
}
// Modified comparison operators.
bool operator<(const RollingNumber& aOther) const {
const T& a = mIndex;
const T& b = aOther.mIndex;
// static_cast needed because of possible integer promotion
// (e.g., from uint8_t to int, which would make the test useless).
const bool lessThanOther = static_cast<ValueType>(a - b) > MidWay;
MOZ_ASSERT((lessThanOther ? (b - a) : (a - b)) <= MaxDiff);
return lessThanOther;
}
bool operator<=(const RollingNumber& aOther) const {
const T& a = mIndex;
const T& b = aOther.mIndex;
const bool lessishThanOther = static_cast<ValueType>(b - a) <= MidWay;
MOZ_ASSERT((lessishThanOther ? (b - a) : (a - b)) <= MaxDiff);
return lessishThanOther;
}
bool operator>=(const RollingNumber& aOther) const {
const T& a = mIndex;
const T& b = aOther.mIndex;
const bool greaterishThanOther = static_cast<ValueType>(a - b) <= MidWay;
MOZ_ASSERT((greaterishThanOther ? (a - b) : (b - a)) <= MaxDiff);
return greaterishThanOther;
}
bool operator>(const RollingNumber& aOther) const {
const T& a = mIndex;
const T& b = aOther.mIndex;
const bool greaterThanOther = static_cast<ValueType>(b - a) > MidWay;
MOZ_ASSERT((greaterThanOther ? (a - b) : (b - a)) <= MaxDiff);
return greaterThanOther;
}
private:
// MidWay is used to split the type range in two, to decide how two numbers
// are ordered.
static const T MidWay = std::numeric_limits<T>::max() / 2;
#ifdef DEBUG
// MaxDiff is the expected maximum difference between two numbers, either
// during comparisons, or when adding/subtracting.
// This is only used during debugging, to highlight algorithmic issues.
static const T MaxDiff = std::numeric_limits<T>::max() / 4;
#endif
ValueType mIndex;
};
} // namespace mozilla
#endif // mozilla_RollingNumber_h_
|
