Directory: | cvmfs/ |
---|---|
File: | cvmfs/bigvector.h |
Date: | 2025-09-28 02:35:26 |
Exec | Total | Coverage | |
---|---|---|---|
Lines: | 105 | 106 | 99.1% |
Branches: | 31 | 44 | 70.5% |
Line | Branch | Exec | Source |
---|---|---|---|
1 | /** | ||
2 | * This file is part of the CernVM File System. | ||
3 | * | ||
4 | * Dynamic array, allocate with mmap for large arrays. | ||
5 | */ | ||
6 | |||
7 | #ifndef CVMFS_BIGVECTOR_H_ | ||
8 | #define CVMFS_BIGVECTOR_H_ | ||
9 | |||
10 | #include <cassert> | ||
11 | #include <cstdlib> | ||
12 | |||
13 | #include "util/smalloc.h" | ||
14 | |||
15 | template<class Item> | ||
16 | class BigVector { | ||
17 | public: | ||
18 | 4725 | BigVector() { | |
19 | 4725 | buffer_ = Alloc(kNumInit); | |
20 | 4725 | size_ = 0; | |
21 | 4725 | shared_buffer_ = false; | |
22 | 4725 | } | |
23 | |||
24 | 806075 | explicit BigVector(const size_t num_items) { | |
25 |
1/2✗ Branch 0 not taken.
✓ Branch 1 taken 806075 times.
|
806075 | assert(num_items > 0); |
26 | 806075 | buffer_ = Alloc(num_items); | |
27 | 806075 | size_ = 0; | |
28 | 806075 | shared_buffer_ = false; | |
29 | 806075 | } | |
30 | |||
31 | 1504003 | BigVector(const BigVector<Item> &other) { CopyFrom(other); } | |
32 | |||
33 | 45 | BigVector<Item> &operator=(const BigVector<Item> &other) { | |
34 |
1/2✗ Branch 0 not taken.
✓ Branch 1 taken 45 times.
|
45 | if (&other == this) |
35 | ✗ | return *this; | |
36 | |||
37 |
1/2✓ Branch 0 taken 45 times.
✗ Branch 1 not taken.
|
45 | if (!shared_buffer_) |
38 | 45 | Dealloc(); | |
39 | 45 | CopyFrom(other); | |
40 | 45 | return *this; | |
41 | } | ||
42 | |||
43 | 4622377 | ~BigVector() { | |
44 |
2/2✓ Branch 0 taken 2311221 times.
✓ Branch 1 taken 9 times.
|
4622377 | if (!shared_buffer_) |
45 | 4622398 | Dealloc(); | |
46 | 4622873 | } | |
47 | |||
48 | 1170328951 | Item At(const size_t index) const { | |
49 |
1/2✗ Branch 0 not taken.
✓ Branch 1 taken 1170227082 times.
|
1170328951 | assert(index < size_); |
50 | 1170328951 | return buffer_[index]; | |
51 | } | ||
52 | |||
53 | 780007680 | const Item *AtPtr(const size_t index) const { | |
54 |
1/2✗ Branch 0 not taken.
✓ Branch 1 taken 780003840 times.
|
780007680 | assert(index < size_); |
55 | 780007680 | return &buffer_[index]; | |
56 | } | ||
57 | |||
58 | 1560173078 | void PushBack(const Item &item) { | |
59 |
2/2✓ Branch 0 taken 4614 times.
✓ Branch 1 taken 1560134257 times.
|
1560173078 | if (size_ == capacity_) |
60 | 4818 | DoubleCapacity(); | |
61 |
1/2✓ Branch 2 taken 33 times.
✗ Branch 3 not taken.
|
1560173078 | new (buffer_ + size_) Item(item); |
62 | 1560173078 | size_++; | |
63 | 1560173078 | } | |
64 | |||
65 | 73139 | void Replace(size_t index, const Item &item) { | |
66 |
1/2✗ Branch 0 not taken.
✓ Branch 1 taken 73139 times.
|
73139 | assert(index < size_); |
67 | 73139 | buffer_[index] = item; | |
68 | 73139 | } | |
69 | |||
70 | 9 | bool IsEmpty() const { return size_ == 0; } | |
71 | |||
72 | 81 | void Clear() { | |
73 | 81 | Dealloc(); | |
74 | 81 | buffer_ = Alloc(kNumInit); | |
75 | 81 | } | |
76 | |||
77 | 39 | void ShareBuffer(Item **duplicate, bool *large_alloc) { | |
78 | 39 | *duplicate = buffer_; | |
79 | 39 | *large_alloc = large_alloc_; | |
80 | 39 | shared_buffer_ = true; | |
81 | 39 | } | |
82 | |||
83 | 4818 | void DoubleCapacity() { | |
84 | 4818 | Item *old_buffer = buffer_; | |
85 | 4818 | const bool old_large_alloc = large_alloc_; | |
86 | |||
87 |
1/2✗ Branch 0 not taken.
✓ Branch 1 taken 4614 times.
|
4818 | assert(capacity_ > 0); |
88 | 4818 | buffer_ = Alloc(capacity_ * 2); | |
89 |
2/2✓ Branch 0 taken 2617379268 times.
✓ Branch 1 taken 4614 times.
|
2617418358 | for (size_t i = 0; i < size_; ++i) |
90 |
0/2✗ Branch 2 not taken.
✗ Branch 3 not taken.
|
2617413540 | new (buffer_ + i) Item(old_buffer[i]); |
91 | |||
92 | 4818 | FreeBuffer(old_buffer, size_, old_large_alloc); | |
93 | 4818 | } | |
94 | |||
95 | 34217 | void ShrinkIfOversized() { | |
96 |
1/2✗ Branch 0 not taken.
✓ Branch 1 taken 34217 times.
|
34217 | assert(!shared_buffer_); |
97 | |||
98 |
2/2✓ Branch 0 taken 717 times.
✓ Branch 1 taken 33500 times.
|
34217 | if (size_ <= kNumInit) |
99 | 717 | return; | |
100 |
2/2✓ Branch 0 taken 33325 times.
✓ Branch 1 taken 175 times.
|
33500 | if (static_cast<float>(size_) >= (0.25 * static_cast<float>(capacity_))) |
101 | 33325 | return; | |
102 | |||
103 | 175 | bool old_large_alloc = large_alloc_; | |
104 | 175 | Item *new_buffer = Alloc(0.5 * static_cast<float>(capacity_)); | |
105 |
2/2✓ Branch 0 taken 20084 times.
✓ Branch 1 taken 175 times.
|
20259 | for (size_t i = 0; i < size_; ++i) |
106 | 20084 | new (new_buffer + i) Item(buffer_[i]); | |
107 | 175 | FreeBuffer(buffer_, size_, old_large_alloc); | |
108 | 175 | buffer_ = new_buffer; | |
109 | } | ||
110 | |||
111 | // Careful! Only for externally modified buffer. | ||
112 | 34217 | void SetSize(const size_t new_size) { | |
113 |
1/2✗ Branch 0 not taken.
✓ Branch 1 taken 34217 times.
|
34217 | assert(new_size <= capacity_); |
114 | 34217 | size_ = new_size; | |
115 | 34217 | } | |
116 | |||
117 | 3287225 | size_t size() const { return size_; } | |
118 | 624 | size_t capacity() const { return capacity_; } | |
119 | |||
120 | private: | ||
121 | static const size_t kNumInit = 16; | ||
122 | static const size_t kMmapThreshold = 128 * 1024; | ||
123 | |||
124 | 4623311 | Item *Alloc(const size_t num_elements) { | |
125 | Item *result; | ||
126 | 4623311 | const size_t num_bytes = sizeof(Item) * num_elements; | |
127 |
2/2✓ Branch 0 taken 1711 times.
✓ Branch 1 taken 2312617 times.
|
4623311 | if (num_bytes >= kMmapThreshold) { |
128 | 1745 | result = static_cast<Item *>(smmap(num_bytes)); | |
129 | 1745 | large_alloc_ = true; | |
130 | } else { | ||
131 | 4621566 | result = static_cast<Item *>(smalloc(num_bytes)); | |
132 | 4621122 | large_alloc_ = false; | |
133 | } | ||
134 | 4622867 | capacity_ = num_elements; | |
135 | 4622867 | return result; | |
136 | } | ||
137 | |||
138 | 4622436 | void Dealloc() { | |
139 | 4622436 | FreeBuffer(buffer_, size_, large_alloc_); | |
140 | 4623382 | buffer_ = NULL; | |
141 | 4623382 | capacity_ = 0; | |
142 | 4623382 | size_ = 0; | |
143 | 4623382 | } | |
144 | |||
145 | 4627732 | void FreeBuffer(Item *buf, const size_t size, const bool large) { | |
146 |
2/2✓ Branch 0 taken 3787467549 times.
✓ Branch 1 taken 2316108 times.
|
3792191335 | for (size_t i = 0; i < size; ++i) |
147 | 3787563603 | buf[i].~Item(); | |
148 | |||
149 |
1/2✓ Branch 0 taken 2316137 times.
✗ Branch 1 not taken.
|
4627732 | if (buf) { |
150 |
2/2✓ Branch 0 taken 1594 times.
✓ Branch 1 taken 2314543 times.
|
4627790 | if (large) { |
151 | 1628 | smunmap(buf); | |
152 | } else { | ||
153 | 4626162 | free(buf); | |
154 | } | ||
155 | } | ||
156 | 4627732 | } | |
157 | |||
158 | 1504063 | void CopyFrom(const BigVector<Item> &other) { | |
159 | 1504063 | buffer_ = Alloc(other.capacity_); | |
160 |
2/2✓ Branch 0 taken 780002469 times.
✓ Branch 1 taken 1504084 times.
|
781506553 | for (size_t i = 0; i < other.size_; ++i) { |
161 | 780002469 | new (buffer_ + i) Item(*other.AtPtr(i)); | |
162 | } | ||
163 | 1504084 | size_ = other.size_; | |
164 | 1504084 | shared_buffer_ = false; | |
165 | 1504084 | } | |
166 | |||
167 | Item *buffer_; | ||
168 | size_t size_; | ||
169 | size_t capacity_; | ||
170 | bool large_alloc_; | ||
171 | bool shared_buffer_; | ||
172 | }; | ||
173 | |||
174 | #endif // CVMFS_BIGVECTOR_H_ | ||
175 |