Directory: | cvmfs/ |
---|---|
File: | cvmfs/bigqueue.h |
Date: | 2025-08-31 02:39:21 |
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 | 531 | BigQueue() { | |
22 | 531 | Alloc(kNumInit); | |
23 | 531 | size_ = 0; | |
24 | 531 | } | |
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 | 11 | BigQueue(const BigQueue<Item> &other) { CopyFrom(other); } | |
33 | |||
34 | 156 | BigQueue<Item> &operator=(const BigQueue<Item> &other) { | |
35 |
1/2✗ Branch 0 not taken.
✓ Branch 1 taken 156 times.
|
156 | if (&other == this) |
36 | ✗ | return *this; | |
37 | |||
38 | 156 | Dealloc(); | |
39 | 156 | CopyFrom(other); | |
40 | 156 | return *this; | |
41 | } | ||
42 | |||
43 | 530 | ~BigQueue() { Dealloc(); } | |
44 | |||
45 | 220120358 | void PushBack(const Item &item) { | |
46 |
2/2✓ Branch 1 taken 1008 times.
✓ Branch 2 taken 220119350 times.
|
220120358 | if (GetAvailableSpace() == 0) { |
47 | 1008 | Migrate(1.9 * static_cast<float>(capacity_)); | |
48 |
1/2✗ Branch 1 not taken.
✓ Branch 2 taken 1008 times.
|
1008 | assert(GetAvailableSpace() > 0); |
49 | } | ||
50 |
1/2✓ Branch 2 taken 98358 times.
✗ Branch 3 not taken.
|
220120358 | new (head_ + size_) Item(item); |
51 | 220120358 | size_++; | |
52 | 220120358 | } | |
53 | |||
54 | 220016542 | void PopFront() { | |
55 |
1/2✗ Branch 1 not taken.
✓ Branch 2 taken 220016542 times.
|
220016542 | assert(!IsEmpty()); |
56 | 220016542 | head_++; | |
57 | 220016542 | size_--; | |
58 |
4/4✓ Branch 0 taken 220014355 times.
✓ Branch 1 taken 2187 times.
✓ Branch 2 taken 561 times.
✓ Branch 3 taken 220013794 times.
|
220016542 | if ((size_ > kCompactThreshold) && (size_ < (capacity_ / 2))) |
59 | 561 | Migrate(static_cast<int>(static_cast<float>(capacity_ * 0.6))); | |
60 | 220016542 | } | |
61 | |||
62 | 220115385 | bool Peek(Item **item) { | |
63 |
2/2✓ Branch 1 taken 253 times.
✓ Branch 2 taken 220115132 times.
|
220115385 | if (IsEmpty()) |
64 | 253 | return false; | |
65 | 220115132 | *item = head_; | |
66 | 220115132 | return true; | |
67 | } | ||
68 | |||
69 | 440131927 | bool IsEmpty() const { return size_ == 0; } | |
70 | |||
71 | 156 | void Clear() { | |
72 | 156 | Dealloc(); | |
73 | 156 | Alloc(kNumInit); | |
74 | 156 | } | |
75 | |||
76 | 61963 | size_t size() const { return size_; } | |
77 | 110 | 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 | 275222093 | size_t GetHeadOffset() const { return head_ - buffer_; } | |
84 | 220121366 | size_t GetAvailableSpace() const { | |
85 | 220121366 | return capacity_ - (size_ + GetHeadOffset()); | |
86 | } | ||
87 | |||
88 | 2423 | void Alloc(const size_t num_elements) { | |
89 | 2423 | size_t num_bytes = sizeof(Item) * num_elements; | |
90 | 2423 | buffer_ = static_cast<Item *>(smmap(num_bytes)); | |
91 | 2423 | capacity_ = num_elements; | |
92 | 2423 | head_ = buffer_; | |
93 | 2423 | } | |
94 | |||
95 | 842 | void Dealloc() { | |
96 | 842 | FreeBuffer(buffer_, GetHeadOffset() + size_); | |
97 | 842 | buffer_ = NULL; | |
98 | 842 | head_ = NULL; | |
99 | 842 | capacity_ = 0; | |
100 | 842 | size_ = 0; | |
101 | 842 | } | |
102 | |||
103 | 1569 | void Migrate(size_t new_capacity) { | |
104 |
1/2✗ Branch 0 not taken.
✓ Branch 1 taken 1569 times.
|
1569 | assert(new_capacity > 0); |
105 |
1/2✗ Branch 0 not taken.
✓ Branch 1 taken 1569 times.
|
1569 | assert(new_capacity >= size_); |
106 | |||
107 | 1569 | size_t head_offset = GetHeadOffset(); | |
108 | 1569 | Item *old_buffer = buffer_; | |
109 | |||
110 | 1569 | Alloc(new_capacity); | |
111 |
2/2✓ Branch 0 taken 616573883 times.
✓ Branch 1 taken 1569 times.
|
616575452 | for (size_t i = 0; i < size_; ++i) |
112 |
1/2✓ Branch 2 taken 160800 times.
✗ Branch 3 not taken.
|
616573883 | new (buffer_ + i) Item(old_buffer[head_offset + i]); |
113 | |||
114 | 1569 | FreeBuffer(old_buffer, head_offset + size_); | |
115 | 1569 | } | |
116 | |||
117 | 2411 | void FreeBuffer(Item *buf, const size_t nitems) { | |
118 |
2/2✓ Branch 0 taken 891792545 times.
✓ Branch 1 taken 2411 times.
|
891794956 | for (size_t i = 0; i < nitems; ++i) |
119 | 891792545 | buf[i].~Item(); | |
120 | |||
121 |
1/2✓ Branch 0 taken 2411 times.
✗ Branch 1 not taken.
|
2411 | if (buf) |
122 | 2411 | smunmap(buf); | |
123 | 2411 | } | |
124 | |||
125 | 167 | void CopyFrom(const BigQueue<Item> &other) { | |
126 | 167 | size_t min_items = kNumInit; | |
127 | 167 | Alloc(std::max(other.size_, min_items)); | |
128 |
2/2✓ Branch 0 taken 55098316 times.
✓ Branch 1 taken 167 times.
|
55098483 | for (size_t i = 0; i < other.size_; ++i) { |
129 |
1/2✓ Branch 3 taken 98316 times.
✗ Branch 4 not taken.
|
55098316 | new (buffer_ + i) Item(*(other.buffer_ + other.GetHeadOffset() + i)); |
130 | } | ||
131 | 167 | size_ = other.size_; | |
132 | 167 | } | |
133 | |||
134 | Item *buffer_; | ||
135 | Item *head_; | ||
136 | size_t size_; | ||
137 | size_t capacity_; | ||
138 | }; | ||
139 | |||
140 | #endif // CVMFS_BIGQUEUE_H_ | ||
141 |