| Directory: | cvmfs/ |
|---|---|
| File: | cvmfs/bigqueue.h |
| Date: | 2025-10-26 02:35:25 |
| 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 | 939 | BigQueue() { | |
| 22 | 939 | Alloc(kNumInit); | |
| 23 | 939 | size_ = 0; | |
| 24 | 939 | } | |
| 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 | 47 | BigQueue(const BigQueue<Item> &other) { CopyFrom(other); } | |
| 33 | |||
| 34 | 176 | BigQueue<Item> &operator=(const BigQueue<Item> &other) { | |
| 35 |
1/2✗ Branch 0 not taken.
✓ Branch 1 taken 176 times.
|
176 | if (&other == this) |
| 36 | ✗ | return *this; | |
| 37 | |||
| 38 | 176 | Dealloc(); | |
| 39 | 176 | CopyFrom(other); | |
| 40 | 176 | return *this; | |
| 41 | } | ||
| 42 | |||
| 43 | 957 | ~BigQueue() { Dealloc(); } | |
| 44 | |||
| 45 | 940194470 | void PushBack(const Item &item) { | |
| 46 |
2/2✓ Branch 1 taken 2746 times.
✓ Branch 2 taken 940191724 times.
|
940194470 | if (GetAvailableSpace() == 0) { |
| 47 | 2746 | Migrate(1.9 * static_cast<float>(capacity_)); | |
| 48 |
1/2✗ Branch 1 not taken.
✓ Branch 2 taken 2746 times.
|
2746 | assert(GetAvailableSpace() > 0); |
| 49 | } | ||
| 50 |
1/2✓ Branch 2 taken 100470 times.
✗ Branch 3 not taken.
|
940194470 | new (head_ + size_) Item(item); |
| 51 | 940194470 | size_++; | |
| 52 | 940194470 | } | |
| 53 | |||
| 54 | 940070589 | void PopFront() { | |
| 55 |
1/2✗ Branch 1 not taken.
✓ Branch 2 taken 940070589 times.
|
940070589 | assert(!IsEmpty()); |
| 56 | 940070589 | head_++; | |
| 57 | 940070589 | size_--; | |
| 58 |
4/4✓ Branch 0 taken 940061335 times.
✓ Branch 1 taken 9254 times.
✓ Branch 2 taken 2397 times.
✓ Branch 3 taken 940058938 times.
|
940070589 | if ((size_ > kCompactThreshold) && (size_ < (capacity_ / 2))) |
| 59 | 2397 | Migrate(static_cast<int>(static_cast<float>(capacity_ * 0.6))); | |
| 60 | 940070589 | } | |
| 61 | |||
| 62 | 940171852 | bool Peek(Item **item) { | |
| 63 |
2/2✓ Branch 1 taken 508 times.
✓ Branch 2 taken 940171344 times.
|
940171852 | if (IsEmpty()) |
| 64 | 508 | return false; | |
| 65 | 940171344 | *item = head_; | |
| 66 | 940171344 | return true; | |
| 67 | } | ||
| 68 | |||
| 69 | 1880242441 | bool IsEmpty() const { return size_ == 0; } | |
| 70 | |||
| 71 | 176 | void Clear() { | |
| 72 | 176 | Dealloc(); | |
| 73 | 176 | Alloc(kNumInit); | |
| 74 | 176 | } | |
| 75 | |||
| 76 | 64171 | size_t size() const { return size_; } | |
| 77 | 470 | 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 | 1175304049 | size_t GetHeadOffset() const { return head_ - buffer_; } | |
| 84 | 940197216 | size_t GetAvailableSpace() const { | |
| 85 | 940197216 | return capacity_ - (size_ + GetHeadOffset()); | |
| 86 | } | ||
| 87 | |||
| 88 | 6481 | void Alloc(const size_t num_elements) { | |
| 89 | 6481 | size_t num_bytes = sizeof(Item) * num_elements; | |
| 90 | 6481 | buffer_ = static_cast<Item *>(smmap(num_bytes)); | |
| 91 | 6481 | capacity_ = num_elements; | |
| 92 | 6481 | head_ = buffer_; | |
| 93 | 6481 | } | |
| 94 | |||
| 95 | 1309 | void Dealloc() { | |
| 96 | 1309 | FreeBuffer(buffer_, GetHeadOffset() + size_); | |
| 97 | 1309 | buffer_ = NULL; | |
| 98 | 1309 | head_ = NULL; | |
| 99 | 1309 | capacity_ = 0; | |
| 100 | 1309 | size_ = 0; | |
| 101 | 1309 | } | |
| 102 | |||
| 103 | 5143 | void Migrate(size_t new_capacity) { | |
| 104 |
1/2✗ Branch 0 not taken.
✓ Branch 1 taken 5143 times.
|
5143 | assert(new_capacity > 0); |
| 105 |
1/2✗ Branch 0 not taken.
✓ Branch 1 taken 5143 times.
|
5143 | assert(new_capacity >= size_); |
| 106 | |||
| 107 | 5143 | size_t head_offset = GetHeadOffset(); | |
| 108 | 5143 | Item *old_buffer = buffer_; | |
| 109 | |||
| 110 | 5143 | Alloc(new_capacity); | |
| 111 |
2/2✓ Branch 0 taken 2633929141 times.
✓ Branch 1 taken 5143 times.
|
2633934284 | for (size_t i = 0; i < size_; ++i) |
| 112 |
1/2✓ Branch 2 taken 164150 times.
✗ Branch 3 not taken.
|
2633929141 | new (buffer_ + i) Item(old_buffer[head_offset + i]); |
| 113 | |||
| 114 | 5143 | FreeBuffer(old_buffer, head_offset + size_); | |
| 115 | 5143 | } | |
| 116 | |||
| 117 | 6452 | void FreeBuffer(Item *buf, const size_t nitems) { | |
| 118 |
2/2✓ Branch 0 taken 3809223963 times.
✓ Branch 1 taken 6452 times.
|
3809230415 | for (size_t i = 0; i < nitems; ++i) |
| 119 | 3809223963 | buf[i].~Item(); | |
| 120 | |||
| 121 |
1/2✓ Branch 0 taken 6452 times.
✗ Branch 1 not taken.
|
6452 | if (buf) |
| 122 | 6452 | smunmap(buf); | |
| 123 | 6452 | } | |
| 124 | |||
| 125 | 223 | void CopyFrom(const BigQueue<Item> &other) { | |
| 126 | 223 | size_t min_items = kNumInit; | |
| 127 | 223 | Alloc(std::max(other.size_, min_items)); | |
| 128 |
2/2✓ Branch 0 taken 235100381 times.
✓ Branch 1 taken 223 times.
|
235100604 | for (size_t i = 0; i < other.size_; ++i) { |
| 129 |
1/2✓ Branch 3 taken 100381 times.
✗ Branch 4 not taken.
|
235100381 | new (buffer_ + i) Item(*(other.buffer_ + other.GetHeadOffset() + i)); |
| 130 | } | ||
| 131 | 223 | size_ = other.size_; | |
| 132 | 223 | } | |
| 133 | |||
| 134 | Item *buffer_; | ||
| 135 | Item *head_; | ||
| 136 | size_t size_; | ||
| 137 | size_t capacity_; | ||
| 138 | }; | ||
| 139 | |||
| 140 | #endif // CVMFS_BIGQUEUE_H_ | ||
| 141 |