CernVM-FS  2.12.0
 All Classes Namespaces Files Functions Variables Typedefs Enumerations Enumerator Friends Macros Pages
bigvector.h
Go to the documentation of this file.
1 
7 #ifndef CVMFS_BIGVECTOR_H_
8 #define CVMFS_BIGVECTOR_H_
9 
10 #include <cassert>
11 #include <cstdlib>
12 
13 #include "util/smalloc.h"
14 
15 template<class Item>
16 class BigVector {
17  public:
20  size_ = 0;
21  shared_buffer_ = false;
22  }
23 
24  explicit BigVector(const size_t num_items) {
25  assert(num_items > 0);
26  buffer_ = Alloc(num_items);
27  size_ = 0;
28  shared_buffer_ = false;
29  }
30 
31  BigVector(const BigVector<Item> &other) {
32  CopyFrom(other);
33  }
34 
36  if (&other == this)
37  return *this;
38 
39  if (!shared_buffer_)
40  Dealloc();
41  CopyFrom(other);
42  return *this;
43  }
44 
46  if (!shared_buffer_)
47  Dealloc();
48  }
49 
50  Item At(const size_t index) const {
51  assert(index < size_);
52  return buffer_[index];
53  }
54 
55  const Item *AtPtr(const size_t index) const {
56  assert(index < size_);
57  return &buffer_[index];
58  }
59 
60  void PushBack(const Item &item) {
61  if (size_ == capacity_)
63  new (buffer_ + size_) Item(item);
64  size_++;
65  }
66 
67  void Replace(size_t index, const Item &item) {
68  assert(index < size_);
69  buffer_[index] = item;
70  }
71 
72  bool IsEmpty() const {
73  return size_ == 0;
74  }
75 
76  void Clear() {
77  Dealloc();
79  }
80 
81  void ShareBuffer(Item **duplicate, bool *large_alloc) {
82  *duplicate = buffer_;
83  *large_alloc = large_alloc_;
84  shared_buffer_ = true;
85  }
86 
87  void DoubleCapacity() {
88  Item *old_buffer = buffer_;
89  bool old_large_alloc = large_alloc_;
90 
91  assert(capacity_ > 0);
92  buffer_ = Alloc(capacity_ * 2);
93  for (size_t i = 0; i < size_; ++i)
94  new (buffer_ + i) Item(old_buffer[i]);
95 
96  FreeBuffer(old_buffer, size_, old_large_alloc);
97  }
98 
101 
102  if (size_ <= kNumInit)
103  return;
104  if (static_cast<float>(size_) >= (0.25 * static_cast<float>(capacity_)))
105  return;
106 
107  bool old_large_alloc = large_alloc_;
108  Item *new_buffer = Alloc(0.5 * static_cast<float>(capacity_));
109  for (size_t i = 0; i < size_; ++i)
110  new (new_buffer + i) Item(buffer_[i]);
111  FreeBuffer(buffer_, size_, old_large_alloc);
112  buffer_ = new_buffer;
113  }
114 
115  // Careful! Only for externally modified buffer.
116  void SetSize(const size_t new_size) {
117  assert(new_size <= capacity_);
118  size_ = new_size;
119  }
120 
121  size_t size() const { return size_; }
122  size_t capacity() const { return capacity_; }
123 
124  private:
125  static const size_t kNumInit = 16;
126  static const size_t kMmapThreshold = 128*1024;
127 
128  Item *Alloc(const size_t num_elements) {
129  Item *result;
130  size_t num_bytes = sizeof(Item) * num_elements;
131  if (num_bytes >= kMmapThreshold) {
132  result = static_cast<Item *>(smmap(num_bytes));
133  large_alloc_ = true;
134  } else {
135  result = static_cast<Item *>(smalloc(num_bytes));
136  large_alloc_ = false;
137  }
138  capacity_ = num_elements;
139  return result;
140  }
141 
142  void Dealloc() {
144  buffer_ = NULL;
145  capacity_ = 0;
146  size_ = 0;
147  }
148 
149  void FreeBuffer(Item *buf, const size_t size, const bool large) {
150  for (size_t i = 0; i < size; ++i)
151  buf[i].~Item();
152 
153  if (buf) {
154  if (large) {
155  smunmap(buf);
156  } else {
157  free(buf);
158  }
159  }
160  }
161 
162  void CopyFrom(const BigVector<Item> &other) {
163  buffer_ = Alloc(other.capacity_);
164  for (size_t i = 0; i < other.size_; ++i) {
165  new (buffer_ + i) Item(*other.AtPtr(i));
166  }
167  size_ = other.size_;
168  shared_buffer_ = false;
169  }
170 
171  Item *buffer_;
172  size_t size_;
173  size_t capacity_;
176 };
177 
178 #endif // CVMFS_BIGVECTOR_H_
Item At(const size_t index) const
Definition: bigvector.h:50
void ShareBuffer(Item **duplicate, bool *large_alloc)
Definition: bigvector.h:81
size_t size_
Definition: bigvector.h:172
bool shared_buffer_
Definition: bigvector.h:175
assert((mem||(size==0))&&"Out Of Memory")
~BigVector()
Definition: bigvector.h:45
Item * buffer_
Definition: bigvector.h:171
void Dealloc()
Definition: bigvector.h:142
void FreeBuffer(Item *buf, const size_t size, const bool large)
Definition: bigvector.h:149
void DoubleCapacity()
Definition: bigvector.h:87
BigVector(const BigVector< Item > &other)
Definition: bigvector.h:31
void CopyFrom(const BigVector< Item > &other)
Definition: bigvector.h:162
BigVector< Item > & operator=(const BigVector< Item > &other)
Definition: bigvector.h:35
void SetSize(const size_t new_size)
Definition: bigvector.h:116
void Clear()
Definition: bigvector.h:76
void ShrinkIfOversized()
Definition: bigvector.h:99
size_t capacity() const
Definition: bigvector.h:122
BigVector(const size_t num_items)
Definition: bigvector.h:24
bool IsEmpty() const
Definition: bigvector.h:72
static const size_t kNumInit
Definition: bigvector.h:125
void PushBack(const Item &item)
Definition: bigvector.h:60
BigVector()
Definition: bigvector.h:18
static const size_t kMmapThreshold
Definition: bigvector.h:126
Item * Alloc(const size_t num_elements)
Definition: bigvector.h:128
void Replace(size_t index, const Item &item)
Definition: bigvector.h:67
bool large_alloc_
Definition: bigvector.h:174
size_t capacity_
Definition: bigvector.h:173
const Item * AtPtr(const size_t index) const
Definition: bigvector.h:55
size_t size() const
Definition: bigvector.h:121