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
|
// Copyright Vespa.ai. Licensed under the terms of the Apache 2.0 license. See LICENSE in the project root.
#include <vespa/vespalib/stllike/hashtable.hpp>
#include <algorithm>
namespace {
static const unsigned long __stl_prime_list[] =
{
7ul, 17ul, 53ul, 97ul, 193ul,
389ul, 769ul, 1543ul, 3079ul, 6151ul,
12289ul, 24593ul, 49157ul, 98317ul, 196613ul,
393241ul, 786433ul, 1572869ul, 3145739ul, 6291469ul,
12582917ul, 25165843ul, 50331653ul, 100663319ul, 201326611ul,
402653189ul, 805306457ul, 1610612741ul, 3221225473ul, 4294967291ul
};
}
namespace vespalib {
size_t
hashtable_base::getModulo(size_t newSize, const unsigned long * list, size_t sz) noexcept
{
const unsigned long* first = list;
const unsigned long* last = list + sz;
const unsigned long* pos = std::lower_bound(first, last, newSize);
return (pos == last) ? *(last - 1) : *pos;
}
size_t
hashtable_base::getModuloStl(size_t size) noexcept
{
return getModulo(size, __stl_prime_list, sizeof(__stl_prime_list)/sizeof(__stl_prime_list[0]));
}
}
|