11f2f60b6SJames Harrison/* -*- Mode: C++; tab-width: 4; c-basic-offset: 4; indent-tabs-mode: nil -*- */
21f2f60b6SJames Harrison/*
31f2f60b6SJames Harrison *     Copyright 2017 Couchbase, Inc.
41f2f60b6SJames Harrison *
51f2f60b6SJames Harrison *   Licensed under the Apache License, Version 2.0 (the "License");
61f2f60b6SJames Harrison *   you may not use this file except in compliance with the License.
71f2f60b6SJames Harrison *   You may obtain a copy of the License at
81f2f60b6SJames Harrison *
91f2f60b6SJames Harrison *       http://www.apache.org/licenses/LICENSE-2.0
101f2f60b6SJames Harrison *
111f2f60b6SJames Harrison *   Unless required by applicable law or agreed to in writing, software
121f2f60b6SJames Harrison *   distributed under the License is distributed on an "AS IS" BASIS,
131f2f60b6SJames Harrison *   WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
141f2f60b6SJames Harrison *   See the License for the specific language governing permissions and
151f2f60b6SJames Harrison *   limitations under the License.
161f2f60b6SJames Harrison */
171f2f60b6SJames Harrison#pragma once
181f2f60b6SJames Harrison
191f2f60b6SJames Harrison#include <atomic>
20fd7818a5SBen Huddleston#include <limits>
21fd19cf71SDave Rigby#include <stdexcept>
22fd19cf71SDave Rigby#include <string>
231f2f60b6SJames Harrison#include <type_traits>
241f2f60b6SJames Harrison
251f2f60b6SJames Harrisonnamespace cb {
261f2f60b6SJames Harrison
27fd19cf71SDave Rigby/// Policy class for handling underflow by clamping the value at zero.
28fd19cf71SDave Rigbytemplate <class T>
29fd19cf71SDave Rigbystruct ClampAtZeroUnderflowPolicy {
30fd7818a5SBen Huddleston    using SignedT = typename std::make_signed<T>::type;
31fd7818a5SBen Huddleston
32fd7818a5SBen Huddleston    void underflow(T& desired, T current, SignedT arg) {
33d249c49dSBen Huddleston        desired = 0;
34fd19cf71SDave Rigby    }
35fd19cf71SDave Rigby};
36fd19cf71SDave Rigby
37d249c49dSBen Huddleston/// Policy class for handling underflow by throwing an exception. Prints the
38d249c49dSBen Huddleston/// previous value stored in the counter and the argument (the value that we
39d249c49dSBen Huddleston// were attempting to subtract)
40fd19cf71SDave Rigbytemplate <class T>
41fd19cf71SDave Rigbystruct ThrowExceptionUnderflowPolicy {
42fd7818a5SBen Huddleston    using SignedT = typename std::make_signed<T>::type;
43fd7818a5SBen Huddleston
44fd7818a5SBen Huddleston    void underflow(T& desired, T current, SignedT arg) {
45fd19cf71SDave Rigby        using std::to_string;
46d249c49dSBen Huddleston        throw std::underflow_error("ThrowExceptionUnderflowPolicy current:" +
47d249c49dSBen Huddleston                                   to_string(current) + " arg:" +
48d249c49dSBen Huddleston                                   to_string(arg));
49fd19cf71SDave Rigby    }
50fd19cf71SDave Rigby};
51fd19cf71SDave Rigby
5253c9a646SDave Rigby// Default NonNegativeCounter OrdereReversedPolicy (if user doesn't explicitly
5353c9a646SDave Rigby// specify otherwise) - use ClampAtZeroUnderflowPolicy for Release builds, and
5453c9a646SDave Rigby// ThrowExceptionPolicy for Pre-Release builds.
5553c9a646SDave Rigbytemplate <class T>
5653c9a646SDave Rigby#if CB_DEVELOPMENT_ASSERTS
5753c9a646SDave Rigbyusing DefaultUnderflowPolicy = ThrowExceptionUnderflowPolicy<T>;
5853c9a646SDave Rigby#else
5953c9a646SDave Rigbyusing DefaultUnderflowPolicy = ClampAtZeroUnderflowPolicy<T>;
6053c9a646SDave Rigby#endif
61fd19cf71SDave Rigby
621f2f60b6SJames Harrison/**
631f2f60b6SJames Harrison * The NonNegativeCounter class wraps std::atomic<> and prevents it
64fd7818a5SBen Huddleston * underflowing over overflowing. By default will clamp the value at 0 on
65fd7818a5SBen Huddleston * underflow, but behaviour can be customized by specifying a different
66fd7818a5SBen Huddleston * UnderflowPolicy class. Same for overflow.
67fd7818a5SBen Huddleston *
68fd7818a5SBen Huddleston * Even though this counter can only be templated on unsigned types, it has the
69fd7818a5SBen Huddleston * maximum value of the corresponding signed type. This is because we need to
70fd7818a5SBen Huddleston * allow and check the addition of negative values.
711f2f60b6SJames Harrison */
72fd19cf71SDave Rigbytemplate <typename T,
7353c9a646SDave Rigby          template <class> class UnderflowPolicy = DefaultUnderflowPolicy>
74fd19cf71SDave Rigbyclass NonNegativeCounter : public UnderflowPolicy<T> {
751f2f60b6SJames Harrison    static_assert(
761f2f60b6SJames Harrison            std::is_unsigned<T>::value,
771f2f60b6SJames Harrison            "NonNegativeCounter should only be templated over unsigned types");
781f2f60b6SJames Harrison
79fd7818a5SBen Huddleston    using SignedT = typename std::make_signed<T>::type;
80fd7818a5SBen Huddleston
811f2f60b6SJames Harrisonpublic:
82d50100a5SDave Rigby    NonNegativeCounter() noexcept {
831f2f60b6SJames Harrison        store(0);
841f2f60b6SJames Harrison    }
851f2f60b6SJames Harrison
8691143b09SDave Rigby    NonNegativeCounter(T initial) {
871f2f60b6SJames Harrison        store(initial);
881f2f60b6SJames Harrison    }
891f2f60b6SJames Harrison
90d50100a5SDave Rigby    NonNegativeCounter(const NonNegativeCounter& other) noexcept {
911f2f60b6SJames Harrison        store(other.load());
921f2f60b6SJames Harrison    }
931f2f60b6SJames Harrison
94d50100a5SDave Rigby    operator T() const noexcept {
951f2f60b6SJames Harrison        return load();
961f2f60b6SJames Harrison    }
971f2f60b6SJames Harrison
98d50100a5SDave Rigby    T load() const noexcept {
991f2f60b6SJames Harrison        return value.load(std::memory_order_relaxed);
1001f2f60b6SJames Harrison    }
1011f2f60b6SJames Harrison
10291143b09SDave Rigby    void store(T desired) {
10366c06445SDave Rigby        if (desired > T(std::numeric_limits<SignedT>::max())) {
10491143b09SDave Rigby            UnderflowPolicy<T>::underflow(desired, load(), desired);
10591143b09SDave Rigby        }
1061f2f60b6SJames Harrison        value.store(desired, std::memory_order_relaxed);
1071f2f60b6SJames Harrison    }
1081f2f60b6SJames Harrison
109fd7818a5SBen Huddleston    /**
110fd7818a5SBen Huddleston     * Add 'arg' to the current value. If the new value would underflow (i.e. if
111fd7818a5SBen Huddleston     * arg was negative and current less than arg) then calls underflow() on the
112fd7818a5SBen Huddleston     * selected UnderflowPolicy.
113fd7818a5SBen Huddleston     *
114fd7818a5SBen Huddleston     * Note: Not marked 'noexcept' as underflow() could throw.
115fd7818a5SBen Huddleston     */
116fd7818a5SBen Huddleston    T fetch_add(SignedT arg) {
117fd7818a5SBen Huddleston        T current = load();
118fd7818a5SBen Huddleston        T desired;
119fd7818a5SBen Huddleston        do {
120fd7818a5SBen Huddleston            if (arg < 0) {
121fd7818a5SBen Huddleston                desired = current - T(std::abs(arg));
122fd7818a5SBen Huddleston                if (SignedT(current) + arg < 0) {
123fd7818a5SBen Huddleston                    UnderflowPolicy<T>::underflow(desired, current, arg);
124fd7818a5SBen Huddleston                }
125fd7818a5SBen Huddleston            } else {
126fd7818a5SBen Huddleston                desired = current + T(arg);
12766c06445SDave Rigby                if (desired > T(std::numeric_limits<SignedT>::max())) {
128fd7818a5SBen Huddleston                    UnderflowPolicy<T>::underflow(desired, current, arg);
129fd7818a5SBen Huddleston                }
130fd7818a5SBen Huddleston            }
131fd7818a5SBen Huddleston            // Attempt to set the atomic value to desired. If the atomic value
132fd7818a5SBen Huddleston            // is not the same as current then it has changed during
133fd7818a5SBen Huddleston            // operation. compare_exchange_weak will reload the new value
134fd7818a5SBen Huddleston            // into current if it fails, and we will retry.
135fd7818a5SBen Huddleston        } while (!value.compare_exchange_weak(
136fd7818a5SBen Huddleston                current, desired, std::memory_order_relaxed));
137fd7818a5SBen Huddleston
138fd7818a5SBen Huddleston        return current;
1391f2f60b6SJames Harrison    }
1401f2f60b6SJames Harrison
141d50100a5SDave Rigby    /**
142d50100a5SDave Rigby     * Subtract 'arg' from the current value. If the new value would underflow
143d50100a5SDave Rigby     * then calls underflow() on the selected UnderflowPolicy.
144d50100a5SDave Rigby     *
145d50100a5SDave Rigby     * Note: Not marked 'noexcept' as underflow() could throw.
146d50100a5SDave Rigby     */
147fd7818a5SBen Huddleston    T fetch_sub(SignedT arg) {
148d249c49dSBen Huddleston        T current = load();
1491f2f60b6SJames Harrison        T desired;
1501f2f60b6SJames Harrison        do {
151fd7818a5SBen Huddleston            if (arg < 0) {
152fd7818a5SBen Huddleston                desired = current + T(std::abs(arg));
1531f2f60b6SJames Harrison            } else {
154fd7818a5SBen Huddleston                desired = current - T(arg);
155fd7818a5SBen Huddleston            }
156fd7818a5SBen Huddleston
15766c06445SDave Rigby            if (desired > T(std::numeric_limits<SignedT>::max())) {
158fd7818a5SBen Huddleston                UnderflowPolicy<T>::underflow(desired, current, arg);
1591f2f60b6SJames Harrison            }
160d249c49dSBen Huddleston            // Attempt to set the atomic value to desired. If the atomic value
161d249c49dSBen Huddleston            // is not the same as current then it has changed during
162d249c49dSBen Huddleston            // operation. compare_exchange_weak will reload the new value
163d249c49dSBen Huddleston            // into current if it fails, and we will retry.
1641f2f60b6SJames Harrison        } while (!value.compare_exchange_weak(
165d249c49dSBen Huddleston                current, desired, std::memory_order_relaxed));
1661f2f60b6SJames Harrison
167d249c49dSBen Huddleston        return current;
1681f2f60b6SJames Harrison    }
1691f2f60b6SJames Harrison
170d50100a5SDave Rigby    T exchange(T arg) noexcept {
1711f2f60b6SJames Harrison        return value.exchange(arg, std::memory_order_relaxed);
1721f2f60b6SJames Harrison    }
1731f2f60b6SJames Harrison
174d50100a5SDave Rigby    NonNegativeCounter& operator=(const NonNegativeCounter& rhs) noexcept {
17591143b09SDave Rigby        value.store(rhs.load(), std::memory_order_relaxed);
1761f2f60b6SJames Harrison        return *this;
1771f2f60b6SJames Harrison    }
1781f2f60b6SJames Harrison
179fd7818a5SBen Huddleston    NonNegativeCounter& operator+=(const T rhs) {
1801f2f60b6SJames Harrison        fetch_add(rhs);
1811f2f60b6SJames Harrison        return *this;
1821f2f60b6SJames Harrison    }
1831f2f60b6SJames Harrison
184fd7818a5SBen Huddleston    NonNegativeCounter& operator+=(const NonNegativeCounter& rhs) {
1851f2f60b6SJames Harrison        fetch_add(rhs.load());
1861f2f60b6SJames Harrison        return *this;
1871f2f60b6SJames Harrison    }
1881f2f60b6SJames Harrison
1891f2f60b6SJames Harrison    NonNegativeCounter& operator-=(const T rhs) {
1901f2f60b6SJames Harrison        fetch_sub(rhs);
1911f2f60b6SJames Harrison        return *this;
1921f2f60b6SJames Harrison    }
1931f2f60b6SJames Harrison
1941f2f60b6SJames Harrison    NonNegativeCounter& operator-=(const NonNegativeCounter& rhs) {
1951f2f60b6SJames Harrison        fetch_sub(rhs.load());
1961f2f60b6SJames Harrison        return *this;
1971f2f60b6SJames Harrison    }
1981f2f60b6SJames Harrison
199fd7818a5SBen Huddleston    T operator++() {
2001f2f60b6SJames Harrison        return fetch_add(1) + 1;
2011f2f60b6SJames Harrison    }
2021f2f60b6SJames Harrison
203fd7818a5SBen Huddleston    T operator++(int) {
2041f2f60b6SJames Harrison        return fetch_add(1);
2051f2f60b6SJames Harrison    }
2061f2f60b6SJames Harrison
2071f2f60b6SJames Harrison    T operator--() {
2081f2f60b6SJames Harrison        T previous = fetch_sub(1);
2091f2f60b6SJames Harrison        if (previous == 0) {
210d249c49dSBen Huddleston            // If we are doing a clamp underflow we can pass in previous,
211d249c49dSBen Huddleston            // it's already 0 and we are returning 0. If we are going to
212d249c49dSBen Huddleston            // throw, we want to print previous.
213d249c49dSBen Huddleston            UnderflowPolicy<T>::underflow(previous, previous, 1);
2141f2f60b6SJames Harrison            return 0;
2151f2f60b6SJames Harrison        }
2161f2f60b6SJames Harrison        return previous - 1;
2171f2f60b6SJames Harrison    }
2181f2f60b6SJames Harrison
2191f2f60b6SJames Harrison    T operator--(int) {
2201f2f60b6SJames Harrison        return fetch_sub(1);
2211f2f60b6SJames Harrison    }
2221f2f60b6SJames Harrison
22391143b09SDave Rigby    NonNegativeCounter& operator=(T val) {
2241f2f60b6SJames Harrison        store(val);
2251f2f60b6SJames Harrison        return *this;
2261f2f60b6SJames Harrison    }
2271f2f60b6SJames Harrison
2281f2f60b6SJames Harrisonprivate:
2291f2f60b6SJames Harrison    std::atomic<T> value;
2301f2f60b6SJames Harrison};
231fd19cf71SDave Rigby
232fd19cf71SDave Rigby} // namespace cb
233