This is an automated email from the ASF dual-hosted git repository. alexey pushed a commit to branch master in repository https://gitbox.apache.org/repos/asf/kudu.git
commit 9668525c725a9dced7b6ace93967a8156df0c94c Author: Bankim Bhavsar <[email protected]> AuthorDate: Wed Feb 5 12:11:40 2020 -0800 [util] Add a function to generate random unique 32-bit/64-bit integers Change-Id: I512cb649021802aa7595117ad6b29d3fb4a762b3 Reviewed-on: http://gerrit.cloudera.org:8080/15166 Tested-by: Kudu Jenkins Reviewed-by: Adar Dembo <[email protected]> --- src/kudu/util/random.h | 15 +++++++++++++++ src/kudu/util/random_util-test.cc | 34 ++++++++++++++++++++++++++++++++++ src/kudu/util/random_util.h | 28 ++++++++++++++++++++++++++-- 3 files changed, 75 insertions(+), 2 deletions(-) diff --git a/src/kudu/util/random.h b/src/kudu/util/random.h index a3179fe..51e578b 100644 --- a/src/kudu/util/random.h +++ b/src/kudu/util/random.h @@ -206,6 +206,21 @@ inline double Random::Normal(double mean, double std_dev) { return nd(gen); } +// Generate next random integer with data-type specified by IntType template +// parameter which must be a 32-bit or 64-bit integer. This constexpr function +// is useful when generating random numbers in a loop with template parameter +// and avoids the run-time cost of determining Next32() v/s Next64() in RNG. +// +// Note: This constexpr function can't be a member function of +// Random/ThreadSafeRandom class because it invokes non-const member function. +template<typename IntType, class RNG> +constexpr IntType GetNextRandom(RNG* rand) { + static_assert( + std::is_integral<IntType>::value && (sizeof(IntType) == 4 || sizeof(IntType) == 8), + "Only 32-bit and 64-bit integers supported"); + return sizeof(IntType) == 4 ? rand->Next32() : rand->Next64(); +} + } // namespace kudu #endif // KUDU_UTIL_RANDOM_H_ diff --git a/src/kudu/util/random_util-test.cc b/src/kudu/util/random_util-test.cc index 993ef15..cf17225 100644 --- a/src/kudu/util/random_util-test.cc +++ b/src/kudu/util/random_util-test.cc @@ -17,15 +17,20 @@ #include "kudu/util/random_util.h" +#include <cstdint> #include <cstring> #include <ostream> +#include <unordered_set> #include <glog/logging.h> #include <gtest/gtest.h> +#include "kudu/gutil/map-util.h" #include "kudu/util/random.h" #include "kudu/util/test_util.h" +using std::unordered_set; + namespace kudu { class RandomUtilTest : public KuduTest { @@ -72,4 +77,33 @@ TEST_F(RandomUtilTest, TestRandomString) { CheckEmpty(start, 0, 0, kLenMax); } +template<typename IntType> +class TemplateRandomUtilTest : public RandomUtilTest { + public: + void RunCreateRandomUniqueIntegers() { + static constexpr int kMaxNumVals = 1000; + for (int i = 0; i < kNumTrials; ++i) { + unordered_set<IntType> avoid; + for (int j = 0; j < i; ++j) { + avoid.insert(j); + } + int num_vals = rng_.Uniform(kMaxNumVals); + auto vals = CreateRandomUniqueIntegers<IntType>(num_vals, avoid, &rng_); + ASSERT_EQ(num_vals, vals.size()); + for (const auto& v : vals) { + ASSERT_FALSE(ContainsKey(avoid, v)); + } + } + } +}; + +// Testing with char, short data-types will result in compile-time error, as expected. +// Hence no run-time unit tests for non-32/64-bit integers. +typedef ::testing::Types<int32_t, uint32_t, int64_t, uint64_t> IntTypes; +TYPED_TEST_CASE(TemplateRandomUtilTest, IntTypes); + +TYPED_TEST(TemplateRandomUtilTest, RunCreateRandomUniqueIntegers) { + this->RunCreateRandomUniqueIntegers(); +} + } // namespace kudu diff --git a/src/kudu/util/random_util.h b/src/kudu/util/random_util.h index 73eafd0..3998cb6 100644 --- a/src/kudu/util/random_util.h +++ b/src/kudu/util/random_util.h @@ -22,11 +22,12 @@ #include <set> #include <string> +#include <unordered_set> #include <vector> -namespace kudu { +#include "kudu/util/random.h" -class Random; +namespace kudu { // Writes exactly n random bytes to dest using the parameter Random generator. // Note RandomString() does not null-terminate its strings, though '\0' could @@ -98,5 +99,28 @@ void ReservoirSample(const Collection& c, int k, const Set& avoid, } } +// Generates random and unique 32-bit or 64-bit integers that are not present in +// the "avoid" set. +template<typename IntType, class Set, class RNG> +std::unordered_set<IntType> CreateRandomUniqueIntegers(const int num_values, + const Set& avoid, + RNG* rand) { + static_assert( + std::is_integral<IntType>::value && (sizeof(IntType) == 4 || sizeof(IntType) == 8), + "Only 32-bit and 64-bit integers generated"); + + std::unordered_set<IntType> result; + while (result.size() < num_values) { + const IntType val = GetNextRandom<IntType>(rand); + if (ContainsKey(avoid, val)) { + continue; + } + if (!ContainsKey(result, val)) { + result.insert(val); + } + } + return result; +} + } // namespace kudu
