GCC Code Coverage Report

Directory: cvmfs/
File: cvmfs/bigqueue.h
Date: 2025-02-09 02:34:19
Exec Total Coverage
Lines: 81 82 98.8%
Branches: 23 32 71.9%
Line Branch Exec Source
1 /**
2 * This file is part of the CernVM File System.
3 *
4 * Similar to bigvector, but queue semantics. Used by the negative entry
5 * tracker. Allocates with mmap in order to avoid memory fragmentation.
6 */
7
8 #ifndef CVMFS_BIGQUEUE_H_
9 #define CVMFS_BIGQUEUE_H_
10
11 #include <algorithm>
12 #include <cassert>
13 #include <cstdlib>
14 #include <new>
15
16 #include "util/smalloc.h"
17
18 template<class Item>
19 class BigQueue {
20 public:
21 30 BigQueue() {
22 30 Alloc(kNumInit);
23 30 size_ = 0;
24 30 }
25
26 explicit BigQueue(const size_t num_items) {
27 size_t min_items = kNumInit;
28 Alloc(std::max(num_items, min_items));
29 size_ = 0;
30 }
31
32 1 BigQueue(const BigQueue<Item> &other) {
33 1 CopyFrom(other);
34 1 }
35
36 4 BigQueue<Item> &operator= (const BigQueue<Item> &other) {
37
1/2
✗ Branch 0 not taken.
✓ Branch 1 taken 4 times.
 4 if (&other == this)
38 ✗ return *this;
39
40 4 Dealloc();
41 4 CopyFrom(other);
42 4 return *this;
43 }
44
45 30 ~BigQueue() {
46 30 Dealloc();
47 30 }
48
49 20004052 void PushBack(const Item &item) {
50
2/2
✓ Branch 1 taken 58 times.
✓ Branch 2 taken 20003994 times.
 20004052 if (GetAvailableSpace() == 0) {
51 58 Migrate(1.9 * static_cast<float>(capacity_));
52
1/2
✗ Branch 1 not taken.
✓ Branch 2 taken 58 times.
 58 assert(GetAvailableSpace() > 0);
53 }
54
1/2
✓ Branch 2 taken 2052 times.
✗ Branch 3 not taken.
 20004052 new (head_ + size_) Item(item);
55 20004052 size_++;
56 20004052 }
57
58 20001503 void PopFront() {
59
1/2
✗ Branch 1 not taken.
✓ Branch 2 taken 20001503 times.
 20001503 assert(!IsEmpty());
60 20001503 head_++;
61 20001503 size_--;
62
4/4
✓ Branch 0 taken 20001305 times.
✓ Branch 1 taken 198 times.
✓ Branch 2 taken 51 times.
✓ Branch 3 taken 20001254 times.
 20001503 if ((size_ > kCompactThreshold) && (size_ < (capacity_ / 2)))
63 51 Migrate(static_cast<int>(static_cast<float>(capacity_ * 0.6)));
64 20001503 }
65
66 20003576 bool Peek(Item **item) {
67
2/2
✓ Branch 1 taken 14 times.
✓ Branch 2 taken 20003562 times.
 20003576 if (IsEmpty())
68 14 return false;
69 20003562 *item = head_;
70 20003562 return true;
71 }
72
73 40005079 bool IsEmpty() const {
74 40005079 return size_ == 0;
75 }
76
77 4 void Clear() {
78 4 Dealloc();
79 4 Alloc(kNumInit);
80 4 }
81
82 1313 size_t size() const { return size_; }
83 10 size_t capacity() const { return capacity_; }
84
85 private:
86 static const size_t kNumInit = 64;
87 static const size_t kCompactThreshold = 64;
88
89 25006306 size_t GetHeadOffset() const { return head_ - buffer_; }
90 20004110 size_t GetAvailableSpace() const {
91 20004110 return capacity_ - (size_ + GetHeadOffset());
92 }
93
94 148 void Alloc(const size_t num_elements) {
95 148 size_t num_bytes = sizeof(Item) * num_elements;
96 148 buffer_ = static_cast<Item *>(smmap(num_bytes));
97 148 capacity_ = num_elements;
98 148 head_ = buffer_;
99 148 }
100
101 38 void Dealloc() {
102 38 FreeBuffer(buffer_, GetHeadOffset() + size_);
103 38 buffer_ = NULL;
104 38 head_ = NULL;
105 38 capacity_ = 0;
106 38 size_ = 0;
107 38 }
108
109 109 void Migrate(size_t new_capacity) {
110
1/2
✗ Branch 0 not taken.
✓ Branch 1 taken 109 times.
 109 assert(new_capacity > 0);
111
1/2
✗ Branch 0 not taken.
✓ Branch 1 taken 109 times.
 109 assert(new_capacity >= size_);
112
113 109 size_t head_offset = GetHeadOffset();
114 109 Item *old_buffer = buffer_;
115
116 109 Alloc(new_capacity);
117
2/2
✓ Branch 0 taken 56040903 times.
✓ Branch 1 taken 109 times.
 56041012 for (size_t i = 0; i < size_; ++i)
118
1/2
✓ Branch 2 taken 3350 times.
✗ Branch 3 not taken.
 56040903 new (buffer_ + i) Item(old_buffer[head_offset + i]);
119
120 109 FreeBuffer(old_buffer, head_offset + size_);
121 109 }
122
123 147 void FreeBuffer(Item *buf, const size_t nitems) {
124
2/2
✓ Branch 0 taken 81047003 times.
✓ Branch 1 taken 147 times.
 81047150 for (size_t i = 0; i < nitems; ++i)
125 81047003 buf[i].~Item();
126
127
1/2
✓ Branch 0 taken 147 times.
✗ Branch 1 not taken.
 147 if (buf)
128 147 smunmap(buf);
129 147 }
130
131 5 void CopyFrom(const BigQueue<Item> &other) {
132 5 size_t min_items = kNumInit;
133 5 Alloc(std::max(other.size_, min_items));
134
2/2
✓ Branch 0 taken 5002049 times.
✓ Branch 1 taken 5 times.
 5002054 for (size_t i = 0; i < other.size_; ++i) {
135
1/2
✓ Branch 3 taken 2049 times.
✗ Branch 4 not taken.
 5002049 new (buffer_ + i) Item(*(other.buffer_ + other.GetHeadOffset() + i));
136 }
137 5 size_ = other.size_;
138 5 }
139
140 Item *buffer_;
141 Item *head_;
142 size_t size_;
143 size_t capacity_;
144 };
145
146 #endif // CVMFS_BIGQUEUE_H_
147