CernVM-FS  2.10.0
 All Classes Namespaces Files Functions Variables Typedefs Enumerations Enumerator Friends Macros Pages
bigqueue.h
Go to the documentation of this file.
1 
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 "smalloc.h"
17 
18 template<class Item>
19 class BigQueue {
20  public:
22  Alloc(kNumInit);
23  size_ = 0;
24  }
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  BigQueue(const BigQueue<Item> &other) {
33  CopyFrom(other);
34  }
35 
37  if (&other == this)
38  return *this;
39 
40  Dealloc();
41  CopyFrom(other);
42  return *this;
43  }
44 
46  Dealloc();
47  }
48 
49  void PushBack(const Item &item) {
50  if (GetAvailableSpace() == 0) {
51  Migrate(1.9 * static_cast<float>(capacity_));
53  }
54  new (head_ + size_) Item(item);
55  size_++;
56  }
57 
58  void PopFront() {
59  assert(!IsEmpty());
60  head_++;
61  size_--;
62  if ((size_ > kCompactThreshold) && (size_ < (capacity_ / 2)))
63  Migrate(static_cast<int>(static_cast<float>(capacity_ * 0.6)));
64  }
65 
66  bool Peek(Item **item) {
67  if (IsEmpty())
68  return false;
69  *item = head_;
70  return true;
71  }
72 
73  bool IsEmpty() const {
74  return size_ == 0;
75  }
76 
77  void Clear() {
78  Dealloc();
79  Alloc(kNumInit);
80  }
81 
82  size_t size() const { return size_; }
83  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  size_t GetHeadOffset() const { return head_ - buffer_; }
90  size_t GetAvailableSpace() const {
91  return capacity_ - (size_ + GetHeadOffset());
92  }
93 
94  void Alloc(const size_t num_elements) {
95  size_t num_bytes = sizeof(Item) * num_elements;
96  buffer_ = static_cast<Item *>(smmap(num_bytes));
97  capacity_ = num_elements;
98  head_ = buffer_;
99  }
100 
101  void Dealloc() {
103  buffer_ = NULL;
104  head_ = NULL;
105  capacity_ = 0;
106  size_ = 0;
107  }
108 
109  void Migrate(size_t new_capacity) {
110  assert(new_capacity > 0);
111  assert(new_capacity >= size_);
112 
113  size_t head_offset = GetHeadOffset();
114  Item *old_buffer = buffer_;
115 
116  Alloc(new_capacity);
117  for (size_t i = 0; i < size_; ++i)
118  new (buffer_ + i) Item(old_buffer[head_offset + i]);
119 
120  FreeBuffer(old_buffer, head_offset + size_);
121  }
122 
123  void FreeBuffer(Item *buf, const size_t nitems) {
124  for (size_t i = 0; i < nitems; ++i)
125  buf[i].~Item();
126 
127  if (buf)
128  smunmap(buf);
129  }
130 
131  void CopyFrom(const BigQueue<Item> &other) {
132  size_t min_items = kNumInit;
133  Alloc(std::max(other.size_, min_items));
134  for (size_t i = 0; i < other.size_; ++i) {
135  new (buffer_ + i) Item(*(other.buffer_ + other.GetHeadOffset() + i));
136  }
137  size_ = other.size_;
138  }
139 
140  Item *buffer_;
141  Item *head_;
142  size_t size_;
143  size_t capacity_;
144 };
145 
146 #endif // CVMFS_BIGQUEUE_H_
BigQueue(const size_t num_items)
Definition: bigqueue.h:26
void PopFront()
Definition: bigqueue.h:58
size_t capacity_
Definition: bigqueue.h:143
void Migrate(size_t new_capacity)
Definition: bigqueue.h:109
void Alloc(const size_t num_elements)
Definition: bigqueue.h:94
~BigQueue()
Definition: bigqueue.h:45
assert((mem||(size==0))&&"Out Of Memory")
BigQueue< Item > & operator=(const BigQueue< Item > &other)
Definition: bigqueue.h:36
void PushBack(const Item &item)
Definition: bigqueue.h:49
static const size_t kCompactThreshold
Definition: bigqueue.h:87
void Clear()
Definition: bigqueue.h:77
void Dealloc()
Definition: bigqueue.h:101
size_t capacity() const
Definition: bigqueue.h:83
size_t GetAvailableSpace() const
Definition: bigqueue.h:90
static const size_t kNumInit
Definition: bigqueue.h:86
size_t size() const
Definition: bigqueue.h:82
bool Peek(Item **item)
Definition: bigqueue.h:66
bool IsEmpty() const
Definition: bigqueue.h:73
size_t GetHeadOffset() const
Definition: bigqueue.h:89
void FreeBuffer(Item *buf, const size_t nitems)
Definition: bigqueue.h:123
size_t size_
Definition: bigqueue.h:142
void CopyFrom(const BigQueue< Item > &other)
Definition: bigqueue.h:131
BigQueue()
Definition: bigqueue.h:21
Item * buffer_
Definition: bigqueue.h:140
BigQueue(const BigQueue< Item > &other)
Definition: bigqueue.h:32
Item * head_
Definition: bigqueue.h:141