GCC Code Coverage Report

Directory: cvmfs/
File: cvmfs/bigvector.h
Date: 2025-02-02 02:34:22
Exec Total Coverage
Lines: 108 109 99.1%
Branches: 30 44 68.2%
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 223 BigVector() {
19 223 buffer_ = Alloc(kNumInit);
20 223 size_ = 0;
21 223 shared_buffer_ = false;
22 223 }
23
24 253259 explicit BigVector(const size_t num_items) {
25
1/2
✗ Branch 0 not taken.
✓ Branch 1 taken 253259 times.
 253259 assert(num_items > 0);
26 253259 buffer_ = Alloc(num_items);
27 253259 size_ = 0;
28 253259 shared_buffer_ = false;
29 253259 }
30
31 500099 BigVector(const BigVector<Item> &other) {
32 500099 CopyFrom(other);
33 500093 }
34
35 3 BigVector<Item> &operator= (const BigVector<Item> &other) {
36
1/2
✗ Branch 0 not taken.
✓ Branch 1 taken 3 times.
 3 if (&other == this)
37 ✗ return *this;
38
39
1/2
✓ Branch 0 taken 3 times.
✗ Branch 1 not taken.
 3 if (!shared_buffer_)
40 3 Dealloc();
41 3 CopyFrom(other);
42 3 return *this;
43 }
44
45 1505891 ~BigVector() {
46
1/2
✓ Branch 0 taken 752966 times.
✗ Branch 1 not taken.
 1505891 if (!shared_buffer_)
47 1505926 Dealloc();
48 1506117 }
49
50 30014798 Item At(const size_t index) const {
51
1/2
✗ Branch 0 not taken.
✓ Branch 1 taken 30011797 times.
 30014798 assert(index < size_);
52 30014798 return buffer_[index];
53 }
54
55 20001744 const Item *AtPtr(const size_t index) const {
56
1/2
✗ Branch 0 not taken.
✓ Branch 1 taken 20000872 times.
 20001744 assert(index < size_);
57 20001744 return &buffer_[index];
58 }
59
60 40009641 void PushBack(const Item &item) {
61
2/2
✓ Branch 0 taken 216 times.
✓ Branch 1 taken 40008409 times.
 40009641 if (size_ == capacity_)
62 222 DoubleCapacity();
63
1/2
✓ Branch 2 taken 11 times.
✗ Branch 3 not taken.
 40009641 new (buffer_ + size_) Item(item);
64 40009641 size_++;
65 40009641 }
66
67 2004 void Replace(size_t index, const Item &item) {
68
1/2
✗ Branch 0 not taken.
✓ Branch 1 taken 2004 times.
 2004 assert(index < size_);
69 2004 buffer_[index] = item;
70 2004 }
71
72 3 bool IsEmpty() const {
73 3 return size_ == 0;
74 }
75
76 5 void Clear() {
77 5 Dealloc();
78 5 buffer_ = Alloc(kNumInit);
79 5 }
80
81 1 void ShareBuffer(Item **duplicate, bool *large_alloc) {
82 1 *duplicate = buffer_;
83 1 *large_alloc = large_alloc_;
84 1 shared_buffer_ = true;
85 1 }
86
87 222 void DoubleCapacity() {
88 222 Item *old_buffer = buffer_;
89 222 bool old_large_alloc = large_alloc_;
90
91
1/2
✗ Branch 0 not taken.
✓ Branch 1 taken 216 times.
 222 assert(capacity_ > 0);
92 222 buffer_ = Alloc(capacity_ * 2);
93
2/2
✓ Branch 0 taken 67117160 times.
✓ Branch 1 taken 216 times.
 67118390 for (size_t i = 0; i < size_; ++i)
94
0/2
✗ Branch 2 not taken.
✗ Branch 3 not taken.
 67118168 new (buffer_ + i) Item(old_buffer[i]);
95
96 222 FreeBuffer(old_buffer, size_, old_large_alloc);
97 222 }
98
99 1006 void ShrinkIfOversized() {
100
1/2
✗ Branch 0 not taken.
✓ Branch 1 taken 1006 times.
 1006 assert(!shared_buffer_);
101
102
2/2
✓ Branch 0 taken 21 times.
✓ Branch 1 taken 985 times.
 1006 if (size_ <= kNumInit)
103 21 return;
104
2/2
✓ Branch 0 taken 980 times.
✓ Branch 1 taken 5 times.
 985 if (static_cast<float>(size_) >= (0.25 * static_cast<float>(capacity_)))
105 980 return;
106
107 5 bool old_large_alloc = large_alloc_;
108 5 Item *new_buffer = Alloc(0.5 * static_cast<float>(capacity_));
109
2/2
✓ Branch 0 taken 576 times.
✓ Branch 1 taken 5 times.
 581 for (size_t i = 0; i < size_; ++i)
110 576 new (new_buffer + i) Item(buffer_[i]);
111 5 FreeBuffer(buffer_, size_, old_large_alloc);
112 5 buffer_ = new_buffer;
113 }
114
115 // Careful! Only for externally modified buffer.
116 1006 void SetSize(const size_t new_size) {
117
1/2
✗ Branch 0 not taken.
✓ Branch 1 taken 1006 times.
 1006 assert(new_size <= capacity_);
118 1006 size_ = new_size;
119 1006 }
120
121 1009327 size_t size() const { return size_; }
122 16 size_t capacity() const { return capacity_; }
123
124 private:
125 static const size_t kNumInit = 16;
126 static const size_t kMmapThreshold = 128*1024;
127
128 1504108 Item *Alloc(const size_t num_elements) {
129 Item *result;
130 1504108 size_t num_bytes = sizeof(Item) * num_elements;
131
2/2
✓ Branch 0 taken 44 times.
✓ Branch 1 taken 752124 times.
 1504108 if (num_bytes >= kMmapThreshold) {
132 45 result = static_cast<Item *>(smmap(num_bytes));
133 45 large_alloc_ = true;
134 } else {
135 1504063 result = static_cast<Item *>(smalloc(num_bytes));
136 1504075 large_alloc_ = false;
137 }
138 1504120 capacity_ = num_elements;
139 1504120 return result;
140 }
141
142 1505870 void Dealloc() {
143 1505870 FreeBuffer(buffer_, size_, large_alloc_);
144 1506306 buffer_ = NULL;
145 1506306 capacity_ = 0;
146 1506306 size_ = 0;
147 1506306 }
148
149 1506189 void FreeBuffer(Item *buf, const size_t size, const bool large) {
150
2/2
✓ Branch 0 taken 97125179 times.
✓ Branch 1 taken 753173 times.
 98638501 for (size_t i = 0; i < size; ++i)
151 97132312 buf[i].~Item();
152
153
1/2
✓ Branch 0 taken 753189 times.
✗ Branch 1 not taken.
 1506189 if (buf) {
154
2/2
✓ Branch 0 taken 41 times.
✓ Branch 1 taken 753148 times.
 1506221 if (large) {
155 42 smunmap(buf);
156 } else {
157 1506179 free(buf);
158 }
159 }
160 1506189 }
161
162 500101 void CopyFrom(const BigVector<Item> &other) {
163 500101 buffer_ = Alloc(other.capacity_);
164
2/2
✓ Branch 0 taken 20000823 times.
✓ Branch 1 taken 500103 times.
 20500926 for (size_t i = 0; i < other.size_; ++i) {
165 20000823 new (buffer_ + i) Item(*other.AtPtr(i));
166 }
167 500103 size_ = other.size_;
168 500103 shared_buffer_ = false;
169 500103 }
170
171 Item *buffer_;
172 size_t size_;
173 size_t capacity_;
174 bool large_alloc_;
175 bool shared_buffer_;
176 };
177
178 #endif // CVMFS_BIGVECTOR_H_
179