1 #ifndef MARISA_GRIMOIRE_VECTOR_VECTOR_H_ 2 #define MARISA_GRIMOIRE_VECTOR_VECTOR_H_ 3 4 #include <new> 5 6 #include "marisa/grimoire/io.h" 7 8 namespace marisa { 9 namespace grimoire { 10 namespace vector { 11 12 template <typename T> 13 class Vector { 14 public: Vector()15 Vector() 16 : buf_(), objs_(NULL), const_objs_(NULL), 17 size_(0), capacity_(0), fixed_(false) {} ~Vector()18 ~Vector() { 19 if (objs_ != NULL) { 20 for (std::size_t i = 0; i < size_; ++i) { 21 objs_[i].~T(); 22 } 23 } 24 } 25 map(Mapper & mapper)26 void map(Mapper &mapper) { 27 Vector temp; 28 temp.map_(mapper); 29 swap(temp); 30 } 31 read(Reader & reader)32 void read(Reader &reader) { 33 Vector temp; 34 temp.read_(reader); 35 swap(temp); 36 } 37 write(Writer & writer)38 void write(Writer &writer) const { 39 write_(writer); 40 } 41 push_back(const T & x)42 void push_back(const T &x) { 43 MARISA_DEBUG_IF(fixed_, MARISA_STATE_ERROR); 44 MARISA_DEBUG_IF(size_ == max_size(), MARISA_SIZE_ERROR); 45 reserve(size_ + 1); 46 new (&objs_[size_]) T(x); 47 ++size_; 48 } 49 pop_back()50 void pop_back() { 51 MARISA_DEBUG_IF(fixed_, MARISA_STATE_ERROR); 52 MARISA_DEBUG_IF(size_ == 0, MARISA_STATE_ERROR); 53 objs_[--size_].~T(); 54 } 55 56 // resize() assumes that T's placement new does not throw an exception. resize(std::size_t size)57 void resize(std::size_t size) { 58 MARISA_DEBUG_IF(fixed_, MARISA_STATE_ERROR); 59 reserve(size); 60 for (std::size_t i = size_; i < size; ++i) { 61 new (&objs_[i]) T; 62 } 63 for (std::size_t i = size; i < size_; ++i) { 64 objs_[i].~T(); 65 } 66 size_ = size; 67 } 68 69 // resize() assumes that T's placement new does not throw an exception. resize(std::size_t size,const T & x)70 void resize(std::size_t size, const T &x) { 71 MARISA_DEBUG_IF(fixed_, MARISA_STATE_ERROR); 72 reserve(size); 73 for (std::size_t i = size_; i < size; ++i) { 74 new (&objs_[i]) T(x); 75 } 76 for (std::size_t i = size; i < size_; ++i) { 77 objs_[i].~T(); 78 } 79 size_ = size; 80 } 81 reserve(std::size_t capacity)82 void reserve(std::size_t capacity) { 83 MARISA_DEBUG_IF(fixed_, MARISA_STATE_ERROR); 84 if (capacity <= capacity_) { 85 return; 86 } 87 MARISA_DEBUG_IF(capacity > max_size(), MARISA_SIZE_ERROR); 88 std::size_t new_capacity = capacity; 89 if (capacity_ > (capacity / 2)) { 90 if (capacity_ > (max_size() / 2)) { 91 new_capacity = max_size(); 92 } else { 93 new_capacity = capacity_ * 2; 94 } 95 } 96 realloc(new_capacity); 97 } 98 shrink()99 void shrink() { 100 MARISA_THROW_IF(fixed_, MARISA_STATE_ERROR); 101 if (size_ != capacity_) { 102 realloc(size_); 103 } 104 } 105 fix()106 void fix() { 107 MARISA_THROW_IF(fixed_, MARISA_STATE_ERROR); 108 fixed_ = true; 109 } 110 begin()111 const T *begin() const { 112 return const_objs_; 113 } end()114 const T *end() const { 115 return const_objs_ + size_; 116 } 117 const T &operator[](std::size_t i) const { 118 MARISA_DEBUG_IF(i >= size_, MARISA_BOUND_ERROR); 119 return const_objs_[i]; 120 } front()121 const T &front() const { 122 MARISA_DEBUG_IF(size_ == 0, MARISA_STATE_ERROR); 123 return const_objs_[0]; 124 } back()125 const T &back() const { 126 MARISA_DEBUG_IF(size_ == 0, MARISA_STATE_ERROR); 127 return const_objs_[size_ - 1]; 128 } 129 begin()130 T *begin() { 131 MARISA_DEBUG_IF(fixed_, MARISA_STATE_ERROR); 132 return objs_; 133 } end()134 T *end() { 135 MARISA_DEBUG_IF(fixed_, MARISA_STATE_ERROR); 136 return objs_ + size_; 137 } 138 T &operator[](std::size_t i) { 139 MARISA_DEBUG_IF(fixed_, MARISA_STATE_ERROR); 140 MARISA_DEBUG_IF(i >= size_, MARISA_BOUND_ERROR); 141 return objs_[i]; 142 } front()143 T &front() { 144 MARISA_DEBUG_IF(fixed_, MARISA_STATE_ERROR); 145 MARISA_DEBUG_IF(size_ == 0, MARISA_STATE_ERROR); 146 return objs_[0]; 147 } back()148 T &back() { 149 MARISA_DEBUG_IF(fixed_, MARISA_STATE_ERROR); 150 MARISA_DEBUG_IF(size_ == 0, MARISA_STATE_ERROR); 151 return objs_[size_ - 1]; 152 } 153 size()154 std::size_t size() const { 155 return size_; 156 } capacity()157 std::size_t capacity() const { 158 return capacity_; 159 } fixed()160 bool fixed() const { 161 return fixed_; 162 } 163 empty()164 bool empty() const { 165 return size_ == 0; 166 } total_size()167 std::size_t total_size() const { 168 return sizeof(T) * size_; 169 } io_size()170 std::size_t io_size() const { 171 return sizeof(UInt64) + ((total_size() + 7) & ~(std::size_t)0x07); 172 } 173 clear()174 void clear() { 175 Vector().swap(*this); 176 } swap(Vector & rhs)177 void swap(Vector &rhs) { 178 buf_.swap(rhs.buf_); 179 marisa::swap(objs_, rhs.objs_); 180 marisa::swap(const_objs_, rhs.const_objs_); 181 marisa::swap(size_, rhs.size_); 182 marisa::swap(capacity_, rhs.capacity_); 183 marisa::swap(fixed_, rhs.fixed_); 184 } 185 max_size()186 static std::size_t max_size() { 187 return MARISA_SIZE_MAX / sizeof(T); 188 } 189 190 private: 191 scoped_array<char> buf_; 192 T *objs_; 193 const T *const_objs_; 194 std::size_t size_; 195 std::size_t capacity_; 196 bool fixed_; 197 map_(Mapper & mapper)198 void map_(Mapper &mapper) { 199 UInt64 total_size; 200 mapper.map(&total_size); 201 MARISA_THROW_IF(total_size > MARISA_SIZE_MAX, MARISA_SIZE_ERROR); 202 MARISA_THROW_IF((total_size % sizeof(T)) != 0, MARISA_FORMAT_ERROR); 203 const std::size_t size = (std::size_t)(total_size / sizeof(T)); 204 mapper.map(&const_objs_, size); 205 mapper.seek((std::size_t)((8 - (total_size % 8)) % 8)); 206 size_ = size; 207 fix(); 208 } read_(Reader & reader)209 void read_(Reader &reader) { 210 UInt64 total_size; 211 reader.read(&total_size); 212 MARISA_THROW_IF(total_size > MARISA_SIZE_MAX, MARISA_SIZE_ERROR); 213 MARISA_THROW_IF((total_size % sizeof(T)) != 0, MARISA_FORMAT_ERROR); 214 const std::size_t size = (std::size_t)(total_size / sizeof(T)); 215 resize(size); 216 reader.read(objs_, size); 217 reader.seek((std::size_t)((8 - (total_size % 8)) % 8)); 218 } write_(Writer & writer)219 void write_(Writer &writer) const { 220 writer.write((UInt64)total_size()); 221 writer.write(const_objs_, size_); 222 writer.seek((8 - (total_size() % 8)) % 8); 223 } 224 225 // realloc() assumes that T's placement new does not throw an exception. realloc(std::size_t new_capacity)226 void realloc(std::size_t new_capacity) { 227 MARISA_DEBUG_IF(new_capacity > max_size(), MARISA_SIZE_ERROR); 228 229 scoped_array<char> new_buf( 230 new (std::nothrow) char[sizeof(T) * new_capacity]); 231 MARISA_DEBUG_IF(new_buf.get() == NULL, MARISA_MEMORY_ERROR); 232 T *new_objs = reinterpret_cast<T *>(new_buf.get()); 233 234 for (std::size_t i = 0; i < size_; ++i) { 235 new (&new_objs[i]) T(objs_[i]); 236 } 237 for (std::size_t i = 0; i < size_; ++i) { 238 objs_[i].~T(); 239 } 240 241 buf_.swap(new_buf); 242 objs_ = new_objs; 243 const_objs_ = new_objs; 244 capacity_ = new_capacity; 245 } 246 247 // Disallows copy and assignment. 248 Vector(const Vector &); 249 Vector &operator=(const Vector &); 250 }; 251 252 } // namespace vector 253 } // namespace grimoire 254 } // namespace marisa 255 256 #endif // MARISA_GRIMOIRE_VECTOR_VECTOR_H_ 257