GCC Code Coverage Report

Directory: cvmfs/
File: cvmfs/bigvector.h
Date: 2025-11-30 02:35:17
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 3936 BigVector() {
19 3936 buffer_ = Alloc(kNumInit);
20 3936 size_ = 0;
21 3936 shared_buffer_ = false;
22 3936 }
23
24 11609330 explicit BigVector(const size_t num_items) {
25
1/2
✗ Branch 0 not taken.
✓ Branch 1 taken 11609330 times.
 11609330 assert(num_items > 0);
26 11609330 buffer_ = Alloc(num_items);
27 11609330 size_ = 0;
28 11609330 shared_buffer_ = false;
29 11609330 }
30
31 23004870 BigVector(const BigVector<Item> &other) { CopyFrom(other); }
32
33 138 BigVector<Item> &operator=(const BigVector<Item> &other) {
34
1/2
✗ Branch 0 not taken.
✓ Branch 1 taken 138 times.
 138 if (&other == this)
35 ✗ return *this;
36
37
1/2
✓ Branch 0 taken 138 times.
✗ Branch 1 not taken.
 138 if (!shared_buffer_)
38 138 Dealloc();
39 138 CopyFrom(other);
40 138 return *this;
41 }
42
43 69211259 ~BigVector() {
44
1/2
✓ Branch 0 taken 34605838 times.
✗ Branch 1 not taken.
 69211259 if (!shared_buffer_)
45 69211575 Dealloc();
46 69215243 }
47
48 1380264575 Item At(const size_t index) const {
49
1/2
✗ Branch 0 not taken.
✓ Branch 1 taken 1380237579 times.
 1380264575 assert(index < size_);
50 1380264575 return buffer_[index];
51 }
52
53 920076576 const Item *AtPtr(const size_t index) const {
54
1/2
✗ Branch 0 not taken.
✓ Branch 1 taken 920038288 times.
 920076576 assert(index < size_);
55 920076576 return &buffer_[index];
56 }
57
58 1840207512 void PushBack(const Item &item) {
59
2/2
✓ Branch 0 taken 7875 times.
✓ Branch 1 taken 1840190570 times.
 1840207512 if (size_ == capacity_)
60 7929 DoubleCapacity();
61
1/2
✓ Branch 2 taken 18 times.
✗ Branch 3 not taken.
 1840207512 new (buffer_ + size_) Item(item);
62 1840207512 size_++;
63 1840207512 }
64
65 55039 void Replace(size_t index, const Item &item) {
66
1/2
✗ Branch 0 not taken.
✓ Branch 1 taken 55039 times.
 55039 assert(index < size_);
67 55039 buffer_[index] = item;
68 55039 }
69
70 6 bool IsEmpty() const { return size_ == 0; }
71
72 125 void Clear() {
73 125 Dealloc();
74 125 buffer_ = Alloc(kNumInit);
75 125 }
76
77 46 void ShareBuffer(Item **duplicate, bool *large_alloc) {
78 46 *duplicate = buffer_;
79 46 *large_alloc = large_alloc_;
80 46 shared_buffer_ = true;
81 46 }
82
83 7929 void DoubleCapacity() {
84 7929 Item *old_buffer = buffer_;
85 7929 const bool old_large_alloc = large_alloc_;
86
87
1/2
✗ Branch 0 not taken.
✓ Branch 1 taken 7875 times.
 7929 assert(capacity_ > 0);
88 7929 buffer_ = Alloc(capacity_ * 2);
89
2/2
✓ Branch 0 taken 3087201088 times.
✓ Branch 1 taken 7875 times.
 3087218089 for (size_t i = 0; i < size_; ++i)
90
0/2
✗ Branch 2 not taken.
✗ Branch 3 not taken.
 3087210160 new (buffer_ + i) Item(old_buffer[i]);
91
92 7929 FreeBuffer(old_buffer, size_, old_large_alloc);
93 7929 }
94
95 9131 void ShrinkIfOversized() {
96
1/2
✗ Branch 0 not taken.
✓ Branch 1 taken 9131 times.
 9131 assert(!shared_buffer_);
97
98
2/2
✓ Branch 0 taken 192 times.
✓ Branch 1 taken 8939 times.
 9131 if (size_ <= kNumInit)
99 192 return;
100
2/2
✓ Branch 0 taken 8857 times.
✓ Branch 1 taken 82 times.
 8939 if (static_cast<float>(size_) >= (0.25 * static_cast<float>(capacity_)))
101 8857 return;
102
103 82 bool old_large_alloc = large_alloc_;
104 82 Item *new_buffer = Alloc(0.5 * static_cast<float>(capacity_));
105
2/2
✓ Branch 0 taken 8884 times.
✓ Branch 1 taken 82 times.
 8966 for (size_t i = 0; i < size_; ++i)
106 8884 new (new_buffer + i) Item(buffer_[i]);
107 82 FreeBuffer(buffer_, size_, old_large_alloc);
108 82 buffer_ = new_buffer;
109 }
110
111 // Careful! Only for externally modified buffer.
112 9131 void SetSize(const size_t new_size) {
113
1/2
✗ Branch 0 not taken.
✓ Branch 1 taken 9131 times.
 9131 assert(new_size <= capacity_);
114 9131 size_ = new_size;
115 9131 }
116
117 46098199 size_t size() const { return size_; }
118 736 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 69170058 Item *Alloc(const size_t num_elements) {
125 Item *result;
126 69170058 const size_t num_bytes = sizeof(Item) * num_elements;
127
2/2
✓ Branch 0 taken 1987 times.
✓ Branch 1 taken 34586485 times.
 69170058 if (num_bytes >= kMmapThreshold) {
128 1996 result = static_cast<Item *>(smmap(num_bytes));
129 1996 large_alloc_ = true;
130 } else {
131 69168062 result = static_cast<Item *>(smalloc(num_bytes));
132 69167050 large_alloc_ = false;
133 }
134 69169046 capacity_ = num_elements;
135 69169046 return result;
136 }
137
138 69208954 void Dealloc() {
139 69208954 FreeBuffer(buffer_, size_, large_alloc_);
140 69218220 buffer_ = NULL;
141 69218220 capacity_ = 0;
142 69218220 size_ = 0;
143 69218220 }
144
145 69218503 void FreeBuffer(Item *buf, const size_t size, const bool large) {
146
2/2
✓ Branch 0 taken 4467391232 times.
✓ Branch 1 taken 34611889 times.
 4536785248 for (size_t i = 0; i < size; ++i)
147 4467566745 buf[i].~Item();
148
149
2/2
✓ Branch 0 taken 34611843 times.
✓ Branch 1 taken 46 times.
 69218503 if (buf) {
150
2/2
✓ Branch 0 taken 1849 times.
✓ Branch 1 taken 34609994 times.
 69218411 if (large) {
151 1858 smunmap(buf);
152 } else {
153 69216553 free(buf);
154 }
155 }
156 69218503 }
157
158 23004778 void CopyFrom(const BigVector<Item> &other) {
159 23004778 buffer_ = Alloc(other.capacity_);
160
2/2
✓ Branch 0 taken 920037858 times.
✓ Branch 1 taken 23005100 times.
 943042958 for (size_t i = 0; i < other.size_; ++i) {
161 920037858 new (buffer_ + i) Item(*other.AtPtr(i));
162 }
163 23005100 size_ = other.size_;
164 23005100 shared_buffer_ = false;
165 23005100 }
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