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
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
|
// Copyright Vespa.ai. Licensed under the terms of the Apache 2.0 license. See LICENSE in the project root.
#include "allocatedbitvector.h"
#include <cstring>
#include <cassert>
namespace search {
namespace {
size_t computeCapacity(size_t capacity, size_t allocatedBytes) {
size_t possibleCapacity = (allocatedBytes * 8) - 1;
assert(possibleCapacity >= capacity);
return possibleCapacity;
}
// This is to ensure that we only read size and capacity once during copy
// to ensure that they do not change unexpectedly under our feet due to resizing in different thread.
std::pair<BitVector::Index, BitVector::Index>
extract_size_size(const BitVector & bv) {
BitVector::Index size = bv.size();
return std::pair<BitVector::Index, BitVector::Index>(size, size);
}
std::pair<BitVector::Index, BitVector::Index>
extract_size_capacity(const AllocatedBitVector & bv) {
BitVector::Index size = bv.size();
BitVector::Index capacity = bv.capacity();
while (capacity < size) {
// Since size and capacity might be changed in another thread we need
// this fallback to avoid inconsistency during shrink.
std::atomic_thread_fence(std::memory_order_seq_cst);
size = bv.size();
capacity = bv.capacity();
}
return std::pair<BitVector::Index, BitVector::Index>(size, capacity);
}
}
AllocatedBitVector::AllocatedBitVector(Index numberOfElements) :
BitVector(),
_capacityBits(numberOfElements),
_alloc(allocatePaddedAndAligned(numberOfElements))
{
_capacityBits = computeCapacity(_capacityBits, _alloc.size());
init(_alloc.get(), 0, numberOfElements);
clear();
}
AllocatedBitVector::AllocatedBitVector(Index numberOfElements, Alloc buffer, size_t offset) :
BitVector(static_cast<char *>(buffer.get()) + offset, numberOfElements),
_capacityBits(numberOfElements),
_alloc(std::move(buffer))
{
}
AllocatedBitVector::AllocatedBitVector(Index numberOfElements, Index capacityBits, const void * rhsBuf, size_t rhsSize, const Alloc* init_alloc) :
BitVector(),
_capacityBits(capacityBits),
_alloc(allocatePaddedAndAligned(0, numberOfElements, capacityBits, init_alloc))
{
_capacityBits = computeCapacity(_capacityBits, _alloc.size());
init(_alloc.get(), 0, numberOfElements);
clear();
if (rhsSize > 0) {
size_t minCount = std::min(static_cast<size_t>(numberOfElements), rhsSize);
memcpy(getStart(), rhsBuf, numBytes(minCount));
if (minCount/8 == numberOfElements/8) {
static_cast<Word *>(getStart())[numWords()-1] &= ~endBits(minCount);
}
set_bit_no_range_check(size()); // Guard bit
}
updateCount();
}
AllocatedBitVector::AllocatedBitVector(const AllocatedBitVector & rhs) :
AllocatedBitVector(rhs, extract_size_capacity(rhs))
{ }
AllocatedBitVector::AllocatedBitVector(const BitVector & rhs) :
AllocatedBitVector(rhs, extract_size_size(rhs))
{ }
AllocatedBitVector::AllocatedBitVector(const BitVector & rhs, std::pair<Index, Index> size_capacity) :
BitVector(),
_capacityBits(size_capacity.second),
_alloc(allocatePaddedAndAligned(0, size_capacity.first, size_capacity.second))
{
_capacityBits = computeCapacity(_capacityBits, _alloc.size());
memcpy(_alloc.get(), rhs.getStart(), numBytes(size_capacity.first - rhs.getStartIndex()));
init(_alloc.get(), 0, size_capacity.first);
set_bit_no_range_check(size());
updateCount();
}
//////////////////////////////////////////////////////////////////////
// Destructor
//////////////////////////////////////////////////////////////////////
AllocatedBitVector::~AllocatedBitVector() = default;
void
AllocatedBitVector::resize(Index newLength)
{
_alloc = allocatePaddedAndAligned(0, newLength, newLength, &_alloc);
_capacityBits = computeCapacity(newLength, _alloc.size());
init(_alloc.get(), 0, newLength);
clear();
}
} // namespace search
|
