diff options
Diffstat (limited to 'base')
-rw-r--r-- | base/CMakeLists.txt | 1 | ||||
-rw-r--r-- | base/base.pro | 1 | ||||
-rw-r--r-- | base/base_tests/CMakeLists.txt | 1 | ||||
-rw-r--r-- | base/base_tests/base_tests.pro | 1 | ||||
-rw-r--r-- | base/base_tests/bits_test.cpp | 20 | ||||
-rw-r--r-- | base/base_tests/small_set_test.cpp | 76 | ||||
-rw-r--r-- | base/base_tests/stl_helpers_test.cpp | 24 | ||||
-rw-r--r-- | base/bits.hpp | 12 | ||||
-rw-r--r-- | base/mem_trie.hpp | 4 | ||||
-rw-r--r-- | base/small_set.hpp | 218 | ||||
-rw-r--r-- | base/stl_helpers.hpp | 32 |
11 files changed, 371 insertions, 19 deletions
diff --git a/base/CMakeLists.txt b/base/CMakeLists.txt index 78b4bc815d..d4e2ad4bd4 100644 --- a/base/CMakeLists.txt +++ b/base/CMakeLists.txt @@ -42,6 +42,7 @@ set( set_operations.hpp shared_buffer_manager.cpp shared_buffer_manager.hpp + small_set.hpp src_point.cpp src_point.hpp stats.hpp diff --git a/base/base.pro b/base/base.pro index d8f90faf79..7eda31055f 100644 --- a/base/base.pro +++ b/base/base.pro @@ -66,6 +66,7 @@ HEADERS += \ scope_guard.hpp \ set_operations.hpp \ shared_buffer_manager.hpp \ + small_set.hpp \ src_point.hpp \ stats.hpp \ std_serialization.hpp \ diff --git a/base/base_tests/CMakeLists.txt b/base/base_tests/CMakeLists.txt index 7d3106daaa..2a31f84d0c 100644 --- a/base/base_tests/CMakeLists.txt +++ b/base/base_tests/CMakeLists.txt @@ -23,6 +23,7 @@ set( regexp_test.cpp rolling_hash_test.cpp scope_guard_test.cpp + small_set_test.cpp stl_add_test.cpp stl_helpers_test.cpp string_format_test.cpp diff --git a/base/base_tests/base_tests.pro b/base/base_tests/base_tests.pro index 32049b5282..a057e05ed7 100644 --- a/base/base_tests/base_tests.pro +++ b/base/base_tests/base_tests.pro @@ -33,6 +33,7 @@ SOURCES += \ regexp_test.cpp \ rolling_hash_test.cpp \ scope_guard_test.cpp \ + small_set_test.cpp \ stl_add_test.cpp \ stl_helpers_test.cpp \ string_format_test.cpp \ diff --git a/base/base_tests/bits_test.cpp b/base/base_tests/bits_test.cpp index c2a43733ea..5263246dae 100644 --- a/base/base_tests/bits_test.cpp +++ b/base/base_tests/bits_test.cpp @@ -120,14 +120,14 @@ UNIT_TEST(PopCount64) UNIT_TEST(CeilLog) { - TEST_EQUAL(0, bits::CeilLog(0x0), ()); - TEST_EQUAL(0, bits::CeilLog(0x1), ()); - TEST_EQUAL(1, bits::CeilLog(0x2), ()); - TEST_EQUAL(1, bits::CeilLog(0x3), ()); - TEST_EQUAL(2, bits::CeilLog(0x4), ()); - - TEST_EQUAL(6, bits::CeilLog(0x7f), ()); - TEST_EQUAL(7, bits::CeilLog(0x80), ()); - TEST_EQUAL(31, bits::CeilLog(0xFFFFFFFF), ()); - TEST_EQUAL(63, bits::CeilLog(0xFFFFFFFFFFFFFFFF), ()); + TEST_EQUAL(0, bits::FloorLog(0x0), ()); + TEST_EQUAL(0, bits::FloorLog(0x1), ()); + TEST_EQUAL(1, bits::FloorLog(0x2), ()); + TEST_EQUAL(1, bits::FloorLog(0x3), ()); + TEST_EQUAL(2, bits::FloorLog(0x4), ()); + + TEST_EQUAL(6, bits::FloorLog(0x7f), ()); + TEST_EQUAL(7, bits::FloorLog(0x80), ()); + TEST_EQUAL(31, bits::FloorLog(0xFFFFFFFF), ()); + TEST_EQUAL(63, bits::FloorLog(0xFFFFFFFFFFFFFFFF), ()); } diff --git a/base/base_tests/small_set_test.cpp b/base/base_tests/small_set_test.cpp new file mode 100644 index 0000000000..41d08935d1 --- /dev/null +++ b/base/base_tests/small_set_test.cpp @@ -0,0 +1,76 @@ +#include "testing/testing.hpp" + +#include "base/small_set.hpp" + +#include <algorithm> +#include <iterator> +#include <vector> + +using namespace base; + +namespace +{ +UNIT_TEST(SmallSet_Empty) +{ + SmallSet<0> set; + TEST_EQUAL(set.Size(), 0, ()); +} + +UNIT_TEST(SmallSet_Smoke) +{ + SmallSet<300> set; + TEST_EQUAL(set.Size(), 0, ()); + for (uint64_t i = 0; i < 300; ++i) + TEST(!set.Contains(i), ()); + + set.Insert(0); + TEST_EQUAL(set.Size(), 1, ()); + TEST(set.Contains(0), ()); + + set.Insert(0); + TEST_EQUAL(set.Size(), 1, ()); + TEST(set.Contains(0), ()); + + set.Insert(5); + TEST_EQUAL(set.Size(), 2, ()); + TEST(set.Contains(0), ()); + TEST(set.Contains(5), ()); + + set.Insert(64); + TEST_EQUAL(set.Size(), 3, ()); + TEST(set.Contains(0), ()); + TEST(set.Contains(5), ()); + TEST(set.Contains(64), ()); + + { + auto cur = set.begin(); + auto end = set.end(); + for (uint64_t i : {0, 5, 64}) + { + TEST(cur != end, ()); + TEST_EQUAL(*cur, i, ()); + ++cur; + } + TEST(cur == end, ()); + } + + set.Remove(5); + TEST_EQUAL(set.Size(), 2, ()); + TEST(set.Contains(0), ()); + TEST(!set.Contains(5), ()); + TEST(set.Contains(64), ()); + + set.Insert(297); + set.Insert(298); + set.Insert(299); + TEST_EQUAL(set.Size(), 5, ()); + + { + std::vector<uint64_t> const actual(set.begin(), set.end()); + std::vector<uint64_t> const expected = {0, 64, 297, 298, 299}; + TEST_EQUAL(actual, expected, ()); + } + + TEST_EQUAL(set.Size(), std::distance(set.begin(), set.end()), ()); +} +} // namespace diff --git a/base/base_tests/stl_helpers_test.cpp b/base/base_tests/stl_helpers_test.cpp index 029df6af98..71462cfbaf 100644 --- a/base/base_tests/stl_helpers_test.cpp +++ b/base/base_tests/stl_helpers_test.cpp @@ -125,4 +125,28 @@ UNIT_TEST(SortUnique_VectorTest) TestSortUnique<vector>(); TestSortUnique<deque>(); } + +UNIT_TEST(IgnoreFirstArgument) +{ + { + int s = 0; + auto f1 = [&](int a, int b) { s += a + b; }; + auto f2 = [&](int a, int b) { s -= a + b; }; + auto f3 = my::MakeIgnoreFirstArgument(f2); + + f1(2, 3); + TEST_EQUAL(s, 5, ()); + f3(1, 2, 3); + TEST_EQUAL(s, 0, ()); + } + + { + auto f1 = [](int a, int b) -> int { return a + b; }; + auto f2 = my::MakeIgnoreFirstArgument(f1); + + auto const x = f1(2, 3); + auto const y = f2("ignored", 2, 3); + TEST_EQUAL(x, y, ()); + } +} } // namespace diff --git a/base/bits.hpp b/base/bits.hpp index f767c85d55..fda447185a 100644 --- a/base/bits.hpp +++ b/base/bits.hpp @@ -63,16 +63,14 @@ namespace bits inline uint32_t PopCount(uint64_t x) noexcept { - x = (x & 0x5555555555555555) + ((x & 0xAAAAAAAAAAAAAAAA) >> 1); - x = (x & 0x3333333333333333) + ((x & 0xCCCCCCCCCCCCCCCC) >> 2); - x = (x & 0x0F0F0F0F0F0F0F0F) + ((x & 0xF0F0F0F0F0F0F0F0) >> 4); - x = (x & 0x00FF00FF00FF00FF) + ((x & 0xFF00FF00FF00FF00) >> 8); - x = (x & 0x0000FFFF0000FFFF) + ((x & 0xFFFF0000FFFF0000) >> 16); - x = x + (x >> 32); + x = x - ((x & 0xAAAAAAAAAAAAAAAA) >> 1); + x = (x & 0x3333333333333333) + ((x >> 2) & 0x3333333333333333); + x = (x + (x >> 4)) & 0x0F0F0F0F0F0F0F0F; + x = (x * 0x0101010101010101) >> 56; return static_cast<uint32_t>(x); } - inline uint8_t CeilLog(uint64_t x) noexcept + inline uint8_t FloorLog(uint64_t x) noexcept { #define CHECK_RSH(x, msb, offset) \ if (x >> offset) \ diff --git a/base/mem_trie.hpp b/base/mem_trie.hpp index fb275c5739..fdd35af365 100644 --- a/base/mem_trie.hpp +++ b/base/mem_trie.hpp @@ -49,7 +49,7 @@ public: ForEachInSubtree(m_root, prefix, std::forward<ToDo>(toDo)); } - // Calls |toDo| for each key-value pair in a node that is reachable + // Calls |toDo| for each key-value pair in the node that is reachable // by |prefix| from the trie root. Does nothing if such node does // not exist. template <typename ToDo> @@ -146,5 +146,5 @@ private: size_t m_numNodes = 1; DISALLOW_COPY(MemTrie); -}; // class MemTrie +}; } // namespace my diff --git a/base/small_set.hpp b/base/small_set.hpp new file mode 100644 index 0000000000..246872d394 --- /dev/null +++ b/base/small_set.hpp @@ -0,0 +1,218 @@ +#pragma once + +#include "base/assert.hpp" +#include "base/bits.hpp" +#include "base/macros.hpp" + +#include <cstdint> +#include <iterator> +#include <sstream> +#include <string> + +namespace base +{ +// A set of nonnegative integers less than |UpperBound|. +// +// Requires UpperBound + O(1) bits of memory. All operations except +// Clear() and iteration are O(1). Clear() and iteration require +// O(UpperBound) steps. +// +// *NOTE* This class *IS NOT* thread safe. +template <uint64_t UpperBound> +class SmallSet +{ +public: + static uint64_t constexpr kNumBlocks = (UpperBound + 63) / 64; + + class Iterator + { + public: + using difference_type = uint64_t; + using value_type = uint64_t; + using pointer = void; + using reference = uint64_t; + using iterator_category = std::forward_iterator_tag; + + Iterator(uint64_t const * blocks, uint64_t current_block_index) + : m_blocks(blocks), m_current_block_index(current_block_index), m_current_block(0) + { + ASSERT_LESS_OR_EQUAL(current_block_index, kNumBlocks, ()); + if (current_block_index < kNumBlocks) + m_current_block = m_blocks[current_block_index]; + SkipZeroes(); + } + + bool operator==(Iterator const & rhs) const + { + return m_blocks == rhs.m_blocks && m_current_block_index == rhs.m_current_block_index && + m_current_block == rhs.m_current_block; + } + + bool operator!=(Iterator const & rhs) const { return !(*this == rhs); } + + uint64_t operator*() const + { + ASSERT_NOT_EQUAL(m_current_block, 0, ()); + auto const bit = m_current_block & -m_current_block; + return bits::FloorLog(bit) + m_current_block_index * 64; + } + + Iterator const & operator++() + { + ASSERT(m_current_block_index < kNumBlocks, ()); + ASSERT_NOT_EQUAL(m_current_block, 0, ()); + m_current_block = m_current_block & (m_current_block - 1); + SkipZeroes(); + return *this; + } + + private: + void SkipZeroes() + { + ASSERT_LESS_OR_EQUAL(m_current_block_index, kNumBlocks, ()); + + if (m_current_block != 0 || m_current_block_index == kNumBlocks) + return; + + do + ++m_current_block_index; + while (m_current_block_index < kNumBlocks && m_blocks[m_current_block_index] == 0); + if (m_current_block_index < kNumBlocks) + m_current_block = m_blocks[m_current_block_index]; + else + m_current_block = 0; + } + + uint64_t const * m_blocks; + uint64_t m_current_block_index; + uint64_t m_current_block; + }; + +#define DEFINE_BLOCK_OFFSET(value) \ + uint64_t const block = value / 64; \ + uint64_t const offset = value % 64 + + // This invalidates all iterators except end(). + void Insert(uint64_t value) + { + ASSERT_LESS(value, UpperBound, ()); + + DEFINE_BLOCK_OFFSET(value); + auto const bit = kOne << offset; + m_size += (m_blocks[block] & bit) == 0; + m_blocks[block] |= bit; + } + + // This invalidates all iterators except end(). + void Remove(uint64_t value) + { + ASSERT_LESS(value, UpperBound, ()); + + DEFINE_BLOCK_OFFSET(value); + auto const bit = kOne << offset; + m_size -= (m_blocks[block] & bit) != 0; + m_blocks[block] &= ~bit; + } + + bool Contains(uint64_t value) const + { + ASSERT_LESS(value, UpperBound, ()); + + DEFINE_BLOCK_OFFSET(value); + return m_blocks[block] & (kOne << offset); + } + +#undef DEFINE_BLOCK_OFFSET + + uint64_t Size() const { return m_size; } + + // This invalidates all iterators except end(). + void Clear() + { + std::fill(std::begin(m_blocks), std::end(m_blocks), static_cast<uint64_t>(0)); + m_size = 0; + } + + Iterator begin() const { return Iterator(m_blocks, 0); } + Iterator cbegin() const { return Iterator(m_blocks, 0); } + + Iterator end() const { return Iterator(m_blocks, kNumBlocks); } + Iterator cend() const { return Iterator(m_blocks, kNumBlocks); } + +private: + static uint64_t constexpr kOne = 1; + + uint64_t m_blocks[kNumBlocks] = {}; + uint64_t m_size = 0; +}; + +// static +template <uint64_t UpperBound> +uint64_t constexpr SmallSet<UpperBound>::kNumBlocks; + +// static +template <uint64_t UpperBound> +uint64_t constexpr SmallSet<UpperBound>::kOne; + +template <uint64_t UpperBound> +std::string DebugPrint(SmallSet<UpperBound> const & set) +{ + std::ostringstream os; + os << "SmallSet<" << UpperBound << "> [" << set.Size() << ": "; + for (auto const & v : set) + os << v << " "; + os << "]"; + return os.str(); +} + +// This is a delegate for SmallSet<>, that checks the validity of +// argument in Insert(), Remove() and Contains() methods and does +// nothing when the argument is not valid. +template <uint64_t UpperBound> +class SafeSmallSet +{ +public: + using Set = SmallSet<UpperBound>; + using Iterator = typename Set::Iterator; + + void Insert(uint64_t value) + { + if (IsValid(value)) + m_set.Insert(value); + } + + void Remove(uint64_t value) + { + if (IsValid(value)) + m_set.Remove(value); + } + + bool Contains(uint64_t value) const { return IsValid(value) && m_set.Contains(value); } + + uint64_t Size() const { return m_set.Size(); } + + void Clear() { m_set.Clear(); } + + Iterator begin() const { return m_set.begin(); } + Iterator cbegin() const { return m_set.cbegin(); } + + Iterator end() const { return m_set.end(); } + Iterator cend() const { return m_set.cend(); } + +private: + bool IsValid(uint64_t value) const { return value < UpperBound; } + + Set m_set; +}; + +template <uint64_t UpperBound> +std::string DebugPrint(SafeSmallSet<UpperBound> const & set) +{ + std::ostringstream os; + os << "SafeSmallSet<" << UpperBound << "> [" << set.Size() << ": "; + for (auto const & v : set) + os << v << " "; + os << "]"; + return os.str(); +} +} // namespace base diff --git a/base/stl_helpers.hpp b/base/stl_helpers.hpp index 7f39e39a59..5ee22b6897 100644 --- a/base/stl_helpers.hpp +++ b/base/stl_helpers.hpp @@ -2,6 +2,7 @@ #include <algorithm> #include <functional> +#include <type_traits> #include <utility> #include <vector> @@ -131,4 +132,35 @@ impl::Equals<false, T, C> EqualsBy(T (C::*p)() const) { return impl::Equals<false, T, C>(p); } + +template <typename T> +typename std::underlying_type<T>::type Key(T value) +{ + return static_cast<typename std::underlying_type<T>::type>(value); +} + +// Use this if you want to make a functor whose first +// argument is ignored and the rest are forwarded to |fn|. +template <typename Fn> +class IgnoreFirstArgument +{ +public: + template <typename Gn> + IgnoreFirstArgument(Gn && gn) : m_fn(std::forward<Gn>(gn)) {} + + template <typename Arg, typename... Args> + typename std::result_of<Fn(Args &&...)>::type operator()(Arg && arg, Args &&... args) + { + return m_fn(std::forward<Args>(args)...); + } + +private: + Fn m_fn; +}; + +template <typename Fn> +IgnoreFirstArgument<Fn> MakeIgnoreFirstArgument(Fn && fn) +{ + return IgnoreFirstArgument<Fn>(std::forward<Fn>(fn)); +} } // namespace my |