diff options
| -rw-r--r-- | contrib/epee/include/rolling_median.h | 236 | ||||
| -rw-r--r-- | src/cryptonote_core/blockchain.cpp | 56 | ||||
| -rw-r--r-- | src/cryptonote_core/blockchain.h | 13 | ||||
| -rw-r--r-- | src/daemon/rpc_command_executor.cpp | 2 | ||||
| -rw-r--r-- | tests/unit_tests/CMakeLists.txt | 1 | ||||
| -rw-r--r-- | tests/unit_tests/rolling_median.cpp | 202 |
6 files changed, 476 insertions, 34 deletions
diff --git a/contrib/epee/include/rolling_median.h b/contrib/epee/include/rolling_median.h new file mode 100644 index 000000000..8b5a82a84 --- /dev/null +++ b/contrib/epee/include/rolling_median.h @@ -0,0 +1,236 @@ +// Copyright (c) 2019, The Monero Project +// +// All rights reserved. +// +// Redistribution and use in source and binary forms, with or without modification, are +// permitted provided that the following conditions are met: +// +// 1. Redistributions of source code must retain the above copyright notice, this list of +// conditions and the following disclaimer. +// +// 2. Redistributions in binary form must reproduce the above copyright notice, this list +// of conditions and the following disclaimer in the documentation and/or other +// materials provided with the distribution. +// +// 3. Neither the name of the copyright holder nor the names of its contributors may be +// used to endorse or promote products derived from this software without specific +// prior written permission. +// +// THIS SOFTWARE IS PROVIDED BY THE COPYRIGHT HOLDERS AND CONTRIBUTORS "AS IS" AND ANY +// EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE IMPLIED WARRANTIES OF +// MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE ARE DISCLAIMED. IN NO EVENT SHALL +// THE COPYRIGHT HOLDER OR CONTRIBUTORS BE LIABLE FOR ANY DIRECT, INDIRECT, INCIDENTAL, +// SPECIAL, EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING, BUT NOT LIMITED TO, +// PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES; LOSS OF USE, DATA, OR PROFITS; OR BUSINESS +// INTERRUPTION) HOWEVER CAUSED AND ON ANY THEORY OF LIABILITY, WHETHER IN CONTRACT, +// STRICT LIABILITY, OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT OF +// THE USE OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE. +// +// Adapted from source by AShelly: +// Copyright (c) 2011 ashelly.myopenid.com, licenced under the MIT licence +// https://stackoverflow.com/questions/5527437/rolling-median-in-c-turlach-implementation +// https://stackoverflow.com/questions/1309263/rolling-median-algorithm-in-c +// https://ideone.com/XPbl6 + +#pragma once + +#include <stdlib.h> +#include <stdint.h> + +namespace epee +{ +namespace misc_utils +{ + +template<typename Item> +struct rolling_median_t +{ +private: + Item* data; //circular queue of values + int* pos; //index into `heap` for each value + int* heap; //max/median/min heap holding indexes into `data`. + int N; //allocated size. + int idx; //position in circular queue + int minCt; //count of items in min heap + int maxCt; //count of items in max heap + int sz; //count of items in heap + +private: + + //returns true if heap[i] < heap[j] + bool mmless(int i, int j) const + { + return data[heap[i]] < data[heap[j]]; + } + + //swaps items i&j in heap, maintains indexes + bool mmexchange(int i, int j) + { + const int t = heap[i]; + heap[i] = heap[j]; + heap[j] = t; + pos[heap[i]] = i; + pos[heap[j]] = j; + return 1; + } + + //swaps items i&j if i<j; returns true if swapped + bool mmCmpExch(int i, int j) + { + return mmless(i, j) && mmexchange(i, j); + } + + //maintains minheap property for all items below i. + void minSortDown(int i) + { + for (i *= 2; i <= minCt; i *= 2) + { + if (i < minCt && mmless(i + 1, i)) + ++i; + if (!mmCmpExch(i, i / 2)) + break; + } + } + + //maintains maxheap property for all items below i. (negative indexes) + void maxSortDown(int i) + { + for (i *= 2; i >= -maxCt; i *= 2) + { + if (i > -maxCt && mmless(i, i - 1)) + --i; + if (!mmCmpExch(i / 2, i)) + break; + } + } + + //maintains minheap property for all items above i, including median + //returns true if median changed + bool minSortUp(int i) + { + while (i > 0 && mmCmpExch(i, i / 2)) + i /= 2; + return i == 0; + } + + //maintains maxheap property for all items above i, including median + //returns true if median changed + bool maxSortUp(int i) + { + while (i < 0 && mmCmpExch(i / 2, i)) + i /= 2; + return i == 0; + } + +protected: + rolling_median_t &operator=(const rolling_median_t&) = delete; + rolling_median_t(const rolling_median_t&) = delete; + +public: + //creates new rolling_median_t: to calculate `nItems` running median. + rolling_median_t(size_t N): N(N) + { + int size = N * (sizeof(Item) + sizeof(int) * 2); + data = (Item*)malloc(size); + pos = (int*) (data + N); + heap = pos + N + (N / 2); //points to middle of storage. + clear(); + } + + rolling_median_t(rolling_median_t &&m) + { + free(data); + memcpy(this, &m, sizeof(rolling_median_t)); + m.data = NULL; + } + rolling_median_t &operator=(rolling_median_t &&m) + { + free(data); + memcpy(this, &m, sizeof(rolling_median_t)); + m.data = NULL; + return *this; + } + + ~rolling_median_t() + { + free(data); + } + + void clear() + { + idx = 0; + minCt = 0; + maxCt = 0; + sz = 0; + int nItems = N; + while (nItems--) //set up initial heap fill pattern: median,max,min,max,... + { + pos[nItems] = ((nItems + 1) / 2) * ((nItems & 1) ? -1 : 1); + heap[pos[nItems]] = nItems; + } + } + + int size() const + { + return sz; + } + + //Inserts item, maintains median in O(lg nItems) + void insert(Item v) + { + int p = pos[idx]; + Item old = data[idx]; + data[idx] = v; + idx = (idx + 1) % N; + sz = std::min<int>(sz + 1, N); + if (p > 0) //new item is in minHeap + { + if (minCt < (N - 1) / 2) + { + ++minCt; + } + else if (v > old) + { + minSortDown(p); + return; + } + if (minSortUp(p) && mmCmpExch(0, -1)) + maxSortDown(-1); + } + else if (p < 0) //new item is in maxheap + { + if (maxCt < N / 2) + { + ++maxCt; + } + else if (v < old) + { + maxSortDown(p); + return; + } + if (maxSortUp(p) && minCt && mmCmpExch(1, 0)) + minSortDown(1); + } + else //new item is at median + { + if (maxCt && maxSortUp(-1)) + maxSortDown(-1); + if (minCt && minSortUp(1)) + minSortDown(1); + } + } + + //returns median item (or average of 2 when item count is even) + Item median() const + { + Item v = data[heap[0]]; + if (minCt < maxCt) + { + v = (v + data[heap[-1]]) / 2; + } + return v; + } +}; + +} +} diff --git a/src/cryptonote_core/blockchain.cpp b/src/cryptonote_core/blockchain.cpp index f733efb2f..32e94ad09 100644 --- a/src/cryptonote_core/blockchain.cpp +++ b/src/cryptonote_core/blockchain.cpp @@ -179,6 +179,7 @@ Blockchain::Blockchain(tx_memory_pool& tx_pool) : m_long_term_block_weights_window(CRYPTONOTE_LONG_TERM_BLOCK_WEIGHT_WINDOW_SIZE), m_long_term_effective_median_block_weight(0), m_long_term_block_weights_cache_tip_hash(crypto::null_hash), + m_long_term_block_weights_cache_rolling_median(CRYPTONOTE_LONG_TERM_BLOCK_WEIGHT_WINDOW_SIZE), m_difficulty_for_next_block_top_hash(crypto::null_hash), m_difficulty_for_next_block(1), m_btc_valid(false) @@ -519,7 +520,10 @@ bool Blockchain::init(BlockchainDB* db, const network_type nettype, bool offline } if (test_options && test_options->long_term_block_weight_window) + { m_long_term_block_weights_window = test_options->long_term_block_weight_window; + m_long_term_block_weights_cache_rolling_median = epee::misc_utils::rolling_median_t<uint64_t>(m_long_term_block_weights_window); + } { db_txn_guard txn_guard(m_db, m_db->is_read_only()); @@ -1283,21 +1287,20 @@ void Blockchain::get_last_n_blocks_weights(std::vector<uint64_t>& weights, size_ weights = m_db->get_block_weights(start_offset, count); } //------------------------------------------------------------------ -void Blockchain::get_long_term_block_weights(std::vector<uint64_t>& weights, uint64_t start_height, size_t count) const +uint64_t Blockchain::get_long_term_block_weight_median(uint64_t start_height, size_t count) const { LOG_PRINT_L3("Blockchain::" << __func__); CRITICAL_REGION_LOCAL(m_blockchain_lock); PERF_TIMER(get_long_term_block_weights); - if (count == 0) - return; + CHECK_AND_ASSERT_THROW_MES(count > 0, "count == 0"); bool cached = false; uint64_t blockchain_height = m_db->height(); uint64_t tip_height = start_height + count - 1; crypto::hash tip_hash = crypto::null_hash; - if (tip_height < blockchain_height && count == m_long_term_block_weights_cache.size()) + if (tip_height < blockchain_height && count == (size_t)m_long_term_block_weights_cache_rolling_median.size()) { tip_hash = m_db->get_block_hash_from_height(tip_height); cached = tip_hash == m_long_term_block_weights_cache_tip_hash; @@ -1306,32 +1309,30 @@ void Blockchain::get_long_term_block_weights(std::vector<uint64_t>& weights, uin if (cached) { MTRACE("requesting " << count << " from " << start_height << ", cached"); - weights = m_long_term_block_weights_cache; - return; + return m_long_term_block_weights_cache_rolling_median.median(); } // in the vast majority of uncached cases, most is still cached, // as we just move the window one block up: - if (tip_height > 0 && count == m_long_term_block_weights_cache.size() && tip_height < blockchain_height) + if (tip_height > 0 && count == (size_t)m_long_term_block_weights_cache_rolling_median.size() && tip_height < blockchain_height) { crypto::hash old_tip_hash = m_db->get_block_hash_from_height(tip_height - 1); if (old_tip_hash == m_long_term_block_weights_cache_tip_hash) { - weights = m_long_term_block_weights_cache; - for (size_t i = 1; i < weights.size(); ++i) - weights[i - 1] = weights[i]; MTRACE("requesting " << count << " from " << start_height << ", incremental"); - weights.back() = m_db->get_block_long_term_weight(tip_height); - m_long_term_block_weights_cache = weights; m_long_term_block_weights_cache_tip_hash = tip_hash; - return; + m_long_term_block_weights_cache_rolling_median.insert(m_db->get_block_long_term_weight(tip_height)); + return m_long_term_block_weights_cache_rolling_median.median(); } } MTRACE("requesting " << count << " from " << start_height << ", uncached"); - weights = m_db->get_long_term_block_weights(start_height, count); - m_long_term_block_weights_cache = weights; + std::vector<uint64_t> weights = m_db->get_long_term_block_weights(start_height, count); m_long_term_block_weights_cache_tip_hash = tip_hash; + m_long_term_block_weights_cache_rolling_median.clear(); + for (uint64_t w: weights) + m_long_term_block_weights_cache_rolling_median.insert(w); + return m_long_term_block_weights_cache_rolling_median.median(); } //------------------------------------------------------------------ uint64_t Blockchain::get_current_cumulative_block_weight_limit() const @@ -3934,9 +3935,7 @@ uint64_t Blockchain::get_next_long_term_block_weight(uint64_t block_weight) cons if (hf_version < HF_VERSION_LONG_TERM_BLOCK_WEIGHT) return block_weight; - std::vector<uint64_t> weights; - get_long_term_block_weights(weights, db_height - nblocks, nblocks); - uint64_t long_term_median = epee::misc_utils::median(weights); + uint64_t long_term_median = get_long_term_block_weight_median(db_height - nblocks, nblocks); uint64_t long_term_effective_median_block_weight = std::max<uint64_t>(CRYPTONOTE_BLOCK_GRANTED_FULL_REWARD_ZONE_V5, long_term_median); uint64_t short_term_constraint = long_term_effective_median_block_weight + long_term_effective_median_block_weight * 2 / 5; @@ -3968,7 +3967,6 @@ bool Blockchain::update_next_cumulative_weight_limit(uint64_t *long_term_effecti { const uint64_t block_weight = m_db->get_block_weight(db_height - 1); - std::vector<uint64_t> weights, new_weights; uint64_t long_term_median; if (db_height == 1) { @@ -3979,9 +3977,7 @@ bool Blockchain::update_next_cumulative_weight_limit(uint64_t *long_term_effecti uint64_t nblocks = std::min<uint64_t>(m_long_term_block_weights_window, db_height); if (nblocks == db_height) --nblocks; - get_long_term_block_weights(weights, db_height - nblocks - 1, nblocks); - new_weights = weights; - long_term_median = epee::misc_utils::median(weights); + long_term_median = get_long_term_block_weight_median(db_height - nblocks - 1, nblocks); } m_long_term_effective_median_block_weight = std::max<uint64_t>(CRYPTONOTE_BLOCK_GRANTED_FULL_REWARD_ZONE_V5, long_term_median); @@ -3989,13 +3985,19 @@ bool Blockchain::update_next_cumulative_weight_limit(uint64_t *long_term_effecti uint64_t short_term_constraint = m_long_term_effective_median_block_weight + m_long_term_effective_median_block_weight * 2 / 5; long_term_block_weight = std::min<uint64_t>(block_weight, short_term_constraint); - if (new_weights.empty()) - new_weights.resize(1); - new_weights[0] = long_term_block_weight; - long_term_median = epee::misc_utils::median(new_weights); + if (db_height == 1) + { + long_term_median = long_term_block_weight; + } + else + { + m_long_term_block_weights_cache_tip_hash = m_db->get_block_hash_from_height(db_height - 1); + m_long_term_block_weights_cache_rolling_median.insert(long_term_block_weight); + long_term_median = m_long_term_block_weights_cache_rolling_median.median(); + } m_long_term_effective_median_block_weight = std::max<uint64_t>(CRYPTONOTE_BLOCK_GRANTED_FULL_REWARD_ZONE_V5, long_term_median); - weights.clear(); + std::vector<uint64_t> weights; get_last_n_blocks_weights(weights, CRYPTONOTE_REWARD_BLOCKS_WINDOW); uint64_t short_term_median = epee::misc_utils::median(weights); diff --git a/src/cryptonote_core/blockchain.h b/src/cryptonote_core/blockchain.h index 244e2a89a..6200ec87e 100644 --- a/src/cryptonote_core/blockchain.h +++ b/src/cryptonote_core/blockchain.h @@ -37,7 +37,6 @@ #include <boost/multi_index/global_fun.hpp> #include <boost/multi_index/hashed_index.hpp> #include <boost/multi_index/member.hpp> -#include <boost/circular_buffer.hpp> #include <atomic> #include <functional> #include <unordered_map> @@ -46,6 +45,7 @@ #include "span.h" #include "syncobj.h" #include "string_tools.h" +#include "rolling_median.h" #include "cryptonote_basic/cryptonote_basic.h" #include "common/util.h" #include "cryptonote_protocol/cryptonote_protocol_defs.h" @@ -1064,7 +1064,7 @@ namespace cryptonote uint64_t m_long_term_block_weights_window; uint64_t m_long_term_effective_median_block_weight; mutable crypto::hash m_long_term_block_weights_cache_tip_hash; - mutable std::vector<uint64_t> m_long_term_block_weights_cache; + mutable epee::misc_utils::rolling_median_t<uint64_t> m_long_term_block_weights_cache_rolling_median; epee::critical_section m_difficulty_lock; crypto::hash m_difficulty_for_next_block_top_hash; @@ -1314,15 +1314,16 @@ namespace cryptonote void get_last_n_blocks_weights(std::vector<uint64_t>& weights, size_t count) const; /** - * @brief gets recent block long term weights for median calculation + * @brief gets block long term weight median * - * get the block long term weights of the last <count> blocks, and return by reference <weights>. + * get the block long term weight median of <count> blocks starting at <start_height> * - * @param weights return-by-reference the list of weights * @param start_height the block height of the first block to query * @param count the number of blocks to get weights for + * + * @return the long term median block weight */ - void get_long_term_block_weights(std::vector<uint64_t>& weights, uint64_t start_height, size_t count) const; + uint64_t get_long_term_block_weight_median(uint64_t start_height, size_t count) const; /** * @brief checks if a transaction is unlocked (its outputs spendable) diff --git a/src/daemon/rpc_command_executor.cpp b/src/daemon/rpc_command_executor.cpp index 186296dc9..151baa33f 100644 --- a/src/daemon/rpc_command_executor.cpp +++ b/src/daemon/rpc_command_executor.cpp @@ -722,7 +722,7 @@ bool t_rpc_command_executor::print_blockchain_info(uint64_t start_block_index, u tools::msg_writer() << "" << std::endl; tools::msg_writer() << "height: " << header.height << ", timestamp: " << header.timestamp << " (" << tools::get_human_readable_timestamp(header.timestamp) << ")" - << ", size: " << header.block_size << ", weight: " << header.block_weight << ", transactions: " << header.num_txes << std::endl + << ", size: " << header.block_size << ", weight: " << header.block_weight << " (long term " << header.long_term_weight << "), transactions: " << header.num_txes << std::endl << "major version: " << (unsigned)header.major_version << ", minor version: " << (unsigned)header.minor_version << std::endl << "block id: " << header.hash << ", previous block id: " << header.prev_hash << std::endl << "difficulty: " << header.difficulty << ", nonce " << header.nonce << ", reward " << cryptonote::print_money(header.reward) << std::endl; diff --git a/tests/unit_tests/CMakeLists.txt b/tests/unit_tests/CMakeLists.txt index 56a1f8c4d..1c4c4384c 100644 --- a/tests/unit_tests/CMakeLists.txt +++ b/tests/unit_tests/CMakeLists.txt @@ -72,6 +72,7 @@ set(unit_tests_sources parse_amount.cpp pruning.cpp random.cpp + rolling_median.cpp serialization.cpp sha256.cpp slow_memmem.cpp diff --git a/tests/unit_tests/rolling_median.cpp b/tests/unit_tests/rolling_median.cpp new file mode 100644 index 000000000..6d6adcc7d --- /dev/null +++ b/tests/unit_tests/rolling_median.cpp @@ -0,0 +1,202 @@ +// Copyright (c) 2019, The Monero Project +// +// All rights reserved. +// +// Redistribution and use in source and binary forms, with or without modification, are +// permitted provided that the following conditions are met: +// +// 1. Redistributions of source code must retain the above copyright notice, this list of +// conditions and the following disclaimer. +// +// 2. Redistributions in binary form must reproduce the above copyright notice, this list +// of conditions and the following disclaimer in the documentation and/or other +// materials provided with the distribution. +// +// 3. Neither the name of the copyright holder nor the names of its contributors may be +// used to endorse or promote products derived from this software without specific +// prior written permission. +// +// THIS SOFTWARE IS PROVIDED BY THE COPYRIGHT HOLDERS AND CONTRIBUTORS "AS IS" AND ANY +// EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE IMPLIED WARRANTIES OF +// MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE ARE DISCLAIMED. IN NO EVENT SHALL +// THE COPYRIGHT HOLDER OR CONTRIBUTORS BE LIABLE FOR ANY DIRECT, INDIRECT, INCIDENTAL, +// SPECIAL, EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING, BUT NOT LIMITED TO, +// PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES; LOSS OF USE, DATA, OR PROFITS; OR BUSINESS +// INTERRUPTION) HOWEVER CAUSED AND ON ANY THEORY OF LIABILITY, WHETHER IN CONTRACT, +// STRICT LIABILITY, OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT OF +// THE USE OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE. + +#include <random> +#include "gtest/gtest.h" +#include "misc_language.h" +#include "rolling_median.h" +#include "crypto/crypto.h" + +TEST(rolling_median, one) +{ + epee::misc_utils::rolling_median_t<uint64_t> m(1); + m.insert(42); + ASSERT_EQ(m.median(), 42); + m.insert(18); + ASSERT_EQ(m.median(), 18); + m.insert(7483); + ASSERT_EQ(m.median(), 7483); +} + +TEST(rolling_median, two) +{ + epee::misc_utils::rolling_median_t<uint64_t> m(2); + m.insert(42); + ASSERT_EQ(m.median(), 42); + m.insert(45); + ASSERT_EQ(m.median(), 43); + m.insert(49); + ASSERT_EQ(m.median(), 47); + m.insert(41); + ASSERT_EQ(m.median(), 45); + m.insert(43); + ASSERT_EQ(m.median(), 42); + m.insert(40); + ASSERT_EQ(m.median(), 41); + m.insert(41); + ASSERT_EQ(m.median(), 40); +} + +TEST(rolling_median, series) +{ + epee::misc_utils::rolling_median_t<uint64_t> m(100); + std::vector<uint64_t> v; + v.reserve(100); + for (int i = 0; i < 10000; ++i) + { + uint64_t r = rand(); + v.push_back(r); + if (v.size() > 100) + v.erase(v.begin()); + m.insert(r); + std::vector<uint64_t> vcopy = v; + ASSERT_EQ(m.median(), epee::misc_utils::median(vcopy)); + } +} + +TEST(rolling_median, clear_whole) +{ + epee::misc_utils::rolling_median_t<uint64_t> m(100); + std::vector<uint64_t> random, median; + random.reserve(10000); + median.reserve(10000); + for (int i = 0; i < 10000; ++i) + { + random.push_back(rand()); + m.insert(random.back()); + median.push_back(m.median()); + } + m.clear(); + for (int i = 0; i < 10000; ++i) + { + m.insert(random[i]); + ASSERT_EQ(median[i], m.median()); + } +} + +TEST(rolling_median, clear_partway) +{ + epee::misc_utils::rolling_median_t<uint64_t> m(100); + std::vector<uint64_t> random, median; + random.reserve(10000); + median.reserve(10000); + for (int i = 0; i < 10000; ++i) + { + random.push_back(rand()); + m.insert(random.back()); + median.push_back(m.median()); + } + m.clear(); + for (int i = 10000 - 100; i < 10000; ++i) + { + m.insert(random[i]); + } + ASSERT_EQ(median[10000-1], m.median()); +} + +TEST(rolling_median, order) +{ + epee::misc_utils::rolling_median_t<uint64_t> m(1000); + std::vector<uint64_t> random; + random.reserve(1000); + for (int i = 0; i < 1000; ++i) + { + random.push_back(rand()); + m.insert(random.back()); + } + const uint64_t med = m.median(); + + std::sort(random.begin(), random.end(), [](uint64_t a, uint64_t b) { return a < b; }); + m.clear(); + for (int i = 0; i < 1000; ++i) + m.insert(random[i]); + ASSERT_EQ(med, m.median()); + + std::sort(random.begin(), random.end(), [](uint64_t a, uint64_t b) { return a > b; }); + m.clear(); + for (int i = 0; i < 1000; ++i) + m.insert(random[i]); + ASSERT_EQ(med, m.median()); + + std::shuffle(random.begin(), random.end(), std::default_random_engine(crypto::rand<unsigned>())); + m.clear(); + for (int i = 0; i < 1000; ++i) + m.insert(random[i]); + ASSERT_EQ(med, m.median()); +} + +TEST(rolling_median, history_blind) +{ + epee::misc_utils::rolling_median_t<uint64_t> m(10); + + uint64_t median = 0; + for (int i = 0; i < 1000; ++i) + { + m.clear(); + int history_length = 743723 % (i+1); + while (history_length--) + m.insert(743284 % (i+1)); + for (int j = 0; j < 10; ++j) + m.insert(8924829384 % (j+1)); + if (i == 0) + median = m.median(); + else + ASSERT_EQ(median, m.median()); + } +} + +TEST(rolling_median, size) +{ + epee::misc_utils::rolling_median_t<uint64_t> m(10); + + ASSERT_EQ(m.size(), 0); + m.insert(1); + ASSERT_EQ(m.size(), 1); + m.insert(2); + ASSERT_EQ(m.size(), 2); + m.clear(); + ASSERT_EQ(m.size(), 0); + for (int i = 0; i < 10; ++i) + { + m.insert(80 % (i + 1)); + ASSERT_EQ(m.size(), i + 1); + } + m.insert(1); + ASSERT_EQ(m.size(), 10); + m.insert(2); + ASSERT_EQ(m.size(), 10); + m.clear(); + ASSERT_EQ(m.size(), 0); + m.insert(4); + ASSERT_EQ(m.size(), 1); + for (int i = 0; i < 1000; ++i) + { + m.insert(80 % (i + 1)); + ASSERT_EQ(m.size(), std::min<int>(10, i + 2)); + } +} |