GCC Code Coverage Report

Directory: cvmfs/
File: cvmfs/bigqueue.h
Date: 2026-09-27 02:40:09
Exec Total Coverage
Lines: 76 77 98.7%
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 1138 BigQueue() {
22 1138 Alloc(kNumInit);
23 1138 size_ = 0;
24 1138 }
25
26 explicit BigQueue(const size_t num_items) {
27 const size_t min_items = kNumInit;
28 Alloc(std::max(num_items, min_items));
29 size_ = 0;
30 }
31
32 34 BigQueue(const BigQueue<Item> &other) { CopyFrom(other); }
33
34 108 BigQueue<Item> &operator=(const BigQueue<Item> &other) {
35
1/2
✗ Branch 0 not taken.
✓ Branch 1 taken 108 times.
 108 if (&other == this)
36 ✗ return *this;
37
38 108 Dealloc();
39 108 CopyFrom(other);
40 108 return *this;
41 }
42
43 1166 ~BigQueue() { Dealloc(); }
44
45 680137660 void PushBack(const Item &item) {
46
2/2
✓ Branch 1 taken 1972 times.
✓ Branch 2 taken 680135688 times.
 680137660 if (GetAvailableSpace() == 0) {
47 1972 Migrate(1.9 * static_cast<float>(capacity_));
48
1/2
✗ Branch 1 not taken.
✓ Branch 2 taken 1972 times.
 1972 assert(GetAvailableSpace() > 0);
49 }
50
1/2
✓ Branch 2 taken 69660 times.
✗ Branch 3 not taken.
 680137660 new (head_ + size_) Item(item);
51 680137660 size_++;
52 680137660 }
53
54 680051022 void PopFront() {
55
1/2
✗ Branch 1 not taken.
✓ Branch 2 taken 680051022 times.
 680051022 assert(!IsEmpty());
56 680051022 head_++;
57 680051022 size_--;
58
4/4
✓ Branch 0 taken 680044370 times.
✓ Branch 1 taken 6652 times.
✓ Branch 2 taken 1734 times.
✓ Branch 3 taken 680042636 times.
 680051022 if ((size_ > kCompactThreshold) && (size_ < (capacity_ / 2)))
59 1734 Migrate(static_cast<int>(static_cast<float>(capacity_ * 0.6)));
60 680051022 }
61
62 680121070 bool Peek(Item **item) {
63
2/2
✓ Branch 1 taken 232 times.
✓ Branch 2 taken 680120838 times.
 680121070 if (IsEmpty())
64 232 return false;
65 680120838 *item = head_;
66 680120838 return true;
67 }
68
69 1360172092 bool IsEmpty() const { return size_ == 0; }
70
71 108 void Clear() {
72 108 Dealloc();
73 108 Alloc(kNumInit);
74 108 }
75
76 44480 size_t size() const { return size_; }
77 340 size_t capacity() const { return capacity_; }
78
79 private:
80 static const size_t kNumInit = 64;
81 static const size_t kCompactThreshold = 64;
82
83 850214358 size_t GetHeadOffset() const { return head_ - buffer_; }
84 680139632 size_t GetAvailableSpace() const {
85 680139632 return capacity_ - (size_ + GetHeadOffset());
86 }
87
88 5094 void Alloc(const size_t num_elements) {
89 5094 size_t const num_bytes = sizeof(Item) * num_elements;
90 5094 buffer_ = static_cast<Item *>(smmap(num_bytes));
91 5094 capacity_ = num_elements;
92 5094 head_ = buffer_;
93 5094 }
94
95 1382 void Dealloc() {
96 1382 FreeBuffer(buffer_, GetHeadOffset() + size_);
97 1382 buffer_ = NULL;
98 1382 head_ = NULL;
99 1382 capacity_ = 0;
100 1382 size_ = 0;
101 1382 }
102
103 3706 void Migrate(size_t new_capacity) {
104
1/2
✗ Branch 0 not taken.
✓ Branch 1 taken 3706 times.
 3706 assert(new_capacity > 0);
105
1/2
✗ Branch 0 not taken.
✓ Branch 1 taken 3706 times.
 3706 assert(new_capacity >= size_);
106
107 3706 size_t const head_offset = GetHeadOffset();
108 3706 Item *old_buffer = buffer_;
109
110 3706 Alloc(new_capacity);
111
2/2
✓ Branch 0 taken 1905390702 times.
✓ Branch 1 taken 3706 times.
 1905394408 for (size_t i = 0; i < size_; ++i)
112
1/2
✓ Branch 2 taken 113900 times.
✗ Branch 3 not taken.
 1905390702 new (buffer_ + i) Item(old_buffer[head_offset + i]);
113
114 3706 FreeBuffer(old_buffer, head_offset + size_);
115 3706 }
116
117 5088 void FreeBuffer(Item *buf, const size_t nitems) {
118
2/2
✓ Branch 0 taken 2755597994 times.
✓ Branch 1 taken 5088 times.
 2755603082 for (size_t i = 0; i < nitems; ++i)
119 2755597994 buf[i].~Item();
120
121
1/2
✓ Branch 0 taken 5088 times.
✗ Branch 1 not taken.
 5088 if (buf)
122 5088 smunmap(buf);
123 5088 }
124
125 142 void CopyFrom(const BigQueue<Item> &other) {
126 142 size_t const min_items = kNumInit;
127 142 Alloc(std::max(other.size_, min_items));
128
2/2
✓ Branch 0 taken 170069638 times.
✓ Branch 1 taken 142 times.
 170069780 for (size_t i = 0; i < other.size_; ++i) {
129
1/2
✓ Branch 3 taken 69638 times.
✗ Branch 4 not taken.
 170069638 new (buffer_ + i) Item(*(other.buffer_ + other.GetHeadOffset() + i));
130 }
131 142 size_ = other.size_;
132 142 }
133
134 Item *buffer_;
135 Item *head_;
136 size_t size_;
137 size_t capacity_;
138 };
139
140 #endif // CVMFS_BIGQUEUE_H_
141