bernsteinbear.com
this repo has no description
1/* Copyright (c) Facebook, Inc. and its affiliates. (http://www.facebook.com) */
2#pragma once
3
4#include <algorithm>
5#include <cstddef>
6#include <cstdlib>
7#include <cstring>
8#include <type_traits>
9#include <utility>
10
11#include "globals.h"
12#include "utils.h"
13
14namespace py {
15
16// A partial clone of std::vector<>. Only supports POD types. Based on llvm's
17// SmallVector, but simpler.
18//
19// Use `const Vector<T>&` in functions that wish to accept a vector reference.
20template <typename T>
21class Vector {
22 // We can add support for non-POD types but its a lot harder to get right, so
23 // we'll start with the simple thing.
24 static_assert(IS_TRIVIALLY_COPYABLE(T), "Vector only supports POD types");
25
26 public:
27 using size_type = word;
28 using iterator = T*;
29 using const_iterator = const T*;
30
31 Vector() = default;
32
33 ~Vector() { release(); }
34
35 Vector(const Vector& other) { *this = other; }
36
37 Vector& operator=(const Vector& other) {
38 clear();
39 auto const s = other.size();
40 reserve(s);
41 end_ = begin_ + s;
42 DCHECK(end_ <= end_storage_, "vector assignment overflow");
43 std::memcpy(begin_, other.begin_, s * sizeof(T));
44 return *this;
45 }
46
47 Vector(Vector&& other) { *this = std::move(other); }
48
49 Vector& operator=(Vector&& other) {
50 // If the other vector's storage is heap allocated, the simplest possible
51 // thing is to just take ownership of its storage. Even if the current
52 // vector is small, and has sufficient capacity, the malloc has already
53 // been paid for.
54 release();
55 std::swap(begin_, other.begin_);
56 std::swap(end_, other.end_);
57 std::swap(end_storage_, other.end_storage_);
58 return *this;
59 }
60
61 iterator begin() { return begin_; }
62 const_iterator begin() const { return begin_; }
63 iterator end() { return end_; }
64 const_iterator end() const { return end_; }
65
66 T& operator[](size_type idx) {
67 DCHECK_INDEX(idx, size());
68 return begin()[idx];
69 }
70 const T& operator[](size_type idx) const {
71 DCHECK_INDEX(idx, size());
72 return begin()[idx];
73 }
74
75 T& front() {
76 DCHECK(!empty(), "front on empty");
77 return begin()[0];
78 }
79 const T& front() const {
80 DCHECK(!empty(), "front on empty");
81 return begin()[0];
82 }
83
84 T& back() {
85 DCHECK(!empty(), "back on empty");
86 return end()[-1];
87 }
88 const T& back() const {
89 DCHECK(!empty(), "back on empty");
90 return end()[-1];
91 }
92
93 size_type size() const { return end_ - begin_; }
94
95 bool empty() const { return size() == 0; }
96
97 size_type capacity() const { return end_storage_ - begin_; }
98
99 void reserve(size_type new_capacity) {
100 DCHECK(new_capacity > 0, "invalid new_capacity %ld", new_capacity);
101 if (new_capacity <= 0) {
102 return;
103 }
104 grow(new_capacity);
105 }
106
107 void clear() { end_ = begin_; }
108
109 void push_back(const T& t) { // NOLINT
110 if (end_ >= end_storage_) {
111 grow(0);
112 }
113 *end_ = t;
114 end_++;
115 }
116
117 void pop_back() { // NOLINT
118 DCHECK(!empty(), "pop back on empty");
119 end_--;
120 }
121
122 void release() {
123 std::free(begin_);
124 begin_ = nullptr;
125 end_ = nullptr;
126 end_storage_ = nullptr;
127 }
128
129 private:
130 static constexpr int kGrowthFactor = 2;
131
132 void grow(size_type new_cap) {
133 auto const old_cap = capacity();
134 auto const old_size = size();
135
136 if (new_cap == 0) {
137 if (old_cap == 0) {
138 new_cap = 4;
139 } else {
140 new_cap = old_cap * kGrowthFactor;
141 }
142 }
143
144 if (old_cap >= new_cap) {
145 return;
146 }
147
148 auto old_begin = begin_;
149
150 begin_ = static_cast<T*>(std::malloc(new_cap * sizeof(T)));
151 DCHECK(begin_ != nullptr, "out of memory");
152 end_storage_ = begin_ + new_cap;
153 end_ = begin_ + old_size;
154
155 if (old_begin != nullptr) {
156 std::memcpy(begin_, old_begin, old_size * sizeof(T));
157 std::free(old_begin);
158 }
159 }
160
161 T* begin_ = nullptr;
162 T* end_storage_ = nullptr;
163 T* end_ = nullptr;
164};
165
166} // namespace py