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
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
|
// Copyright 2019 The Abseil Authors.
//
// Licensed under the Apache License, Version 2.0 (the "License");
// you may not use this file except in compliance with the License.
// You may obtain a copy of the License at
//
// https://www.apache.org/licenses/LICENSE-2.0
//
// Unless required by applicable law or agreed to in writing, software
// distributed under the License is distributed on an "AS IS" BASIS,
// WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
// See the License for the specific language governing permissions and
// limitations under the License.
#ifndef ABSL_CONTAINER_INTERNAL_INLINED_VECTOR_INTERNAL_H_
#define ABSL_CONTAINER_INTERNAL_INLINED_VECTOR_INTERNAL_H_
#include <cstddef>
#include <iterator>
#include <memory>
#include "absl/meta/type_traits.h"
namespace absl {
namespace inlined_vector_internal {
template <typename InlinedVector>
class Storage;
template <template <typename, size_t, typename> class InlinedVector, typename T,
size_t N, typename A>
class Storage<InlinedVector<T, N, A>> {
public:
using allocator_type = A;
using value_type = typename allocator_type::value_type;
using pointer = typename allocator_type::pointer;
using const_pointer = typename allocator_type::const_pointer;
using reference = typename allocator_type::reference;
using const_reference = typename allocator_type::const_reference;
using rvalue_reference = typename allocator_type::value_type&&;
using size_type = typename allocator_type::size_type;
using difference_type = typename allocator_type::difference_type;
using iterator = pointer;
using const_iterator = const_pointer;
using reverse_iterator = std::reverse_iterator<iterator>;
using const_reverse_iterator = std::reverse_iterator<const_iterator>;
explicit Storage(const allocator_type& a) : allocator_and_tag_(a) {}
// TODO(johnsoncj): Make the below types and members private after migration
// Holds whether the vector is allocated or not in the lowest bit and the size
// in the high bits:
// `size_ = (size << 1) | is_allocated;`
class Tag {
size_type size_;
public:
Tag() : size_(0) {}
size_type size() const { return size_ / 2; }
void add_size(size_type n) { size_ += n * 2; }
void set_inline_size(size_type n) { size_ = n * 2; }
void set_allocated_size(size_type n) { size_ = (n * 2) + 1; }
bool allocated() const { return size_ % 2; }
};
// Derives from `allocator_type` to use the empty base class optimization.
// If the `allocator_type` is stateless, we can store our instance for free.
class AllocatorAndTag : private allocator_type {
Tag tag_;
public:
explicit AllocatorAndTag(const allocator_type& a) : allocator_type(a) {}
Tag& tag() { return tag_; }
const Tag& tag() const { return tag_; }
allocator_type& allocator() { return *this; }
const allocator_type& allocator() const { return *this; }
};
class Allocation {
size_type capacity_;
pointer buffer_;
public:
Allocation(allocator_type& a, size_type capacity)
: capacity_(capacity), buffer_(Create(a, capacity)) {}
void Dealloc(allocator_type& a) {
std::allocator_traits<allocator_type>::deallocate(a, buffer_, capacity_);
}
size_type capacity() const { return capacity_; }
const_pointer buffer() const { return buffer_; }
pointer buffer() { return buffer_; }
static pointer Create(allocator_type& a, size_type n) {
return std::allocator_traits<allocator_type>::allocate(a, n);
}
};
// Stores either the inlined or allocated representation
union Rep {
using ValueTypeBuffer =
absl::aligned_storage_t<sizeof(value_type), alignof(value_type)>;
using AllocationBuffer =
absl::aligned_storage_t<sizeof(Allocation), alignof(Allocation)>;
// Structs wrap the buffers to perform indirection that solves a bizarre
// compilation error on Visual Studio (all known versions).
struct InlinedRep {
ValueTypeBuffer inlined[N];
};
struct AllocatedRep {
AllocationBuffer allocation;
};
InlinedRep inlined_storage;
AllocatedRep allocation_storage;
};
AllocatorAndTag allocator_and_tag_;
Rep rep_;
};
} // namespace inlined_vector_internal
} // namespace absl
#endif // ABSL_CONTAINER_INTERNAL_INLINED_VECTOR_INTERNAL_H_
|
