susumu.yata
null+****@clear*****
Mon Dec 1 17:34:49 JST 2014
susumu.yata 2014-12-01 17:34:49 +0900 (Mon, 01 Dec 2014) New Revision: 06d7f3f7acf964772ee0098dd75dcd5e9516d0c1 https://github.com/groonga/grnxx/commit/06d7f3f7acf964772ee0098dd75dcd5e9516d0c1 Message: Update Array to use realloc() for trivial types. (#123) Modified files: include/grnxx/array.hpp Modified: include/grnxx/array.hpp (+245 -2) =================================================================== --- include/grnxx/array.hpp 2014-12-01 15:33:00 +0900 (abd51a9) +++ include/grnxx/array.hpp 2014-12-01 17:34:49 +0900 (0d217c9) @@ -2,7 +2,9 @@ #define GRNXX_ARRAY_HPP #include <cstdlib> +#include <cstring> #include <new> +#include <type_traits> #include <utility> namespace grnxx { @@ -137,8 +139,12 @@ class ArrayRef { size_t size_; }; +template <typename T, bool IS_TRIVIAL = std::is_trivial<T>::value> +class Array; + +// The Array implementation for non-trivial types. template <typename T> -class Array { +class Array<T, false> { public: using Value = T; @@ -355,7 +361,7 @@ class Array { size_t new_buffer_size = sizeof(Value) * new_capacity; Value *new_buffer = static_cast<Value *>(std::malloc(new_buffer_size)); if (!new_buffer) { - throw "Failed"; // TODO + throw "Memory allocation failed"; // TODO } for (size_t i = 0; i < size_; ++i) { new (&new_buffer[i]) Value(std::move(buffer()[i])); @@ -366,6 +372,243 @@ class Array { } }; +// The Array implementation for trivial types. +template <typename T> +class Array<T, true> { + public: + using Value = T; + + Array() : buffer_(nullptr), size_(0), capacity_(0) {} + ~Array() { + std::free(buffer_); + } + + Array(const Array &) = delete; + Array &operator=(const Array &) & = delete; + + // Move the ownership of an array. + Array(Array &&array) + : buffer_(array.buffer_), + size_(array.size_), + capacity_(array.capacity_) { + array.buffer_ = nullptr; + array.size_ = 0; + array.capacity_ = 0; + } + // Move the ownership of an array. + Array &operator=(Array &&array) & { + std::free(buffer_); + buffer_ = array.buffer_; + size_ = array.size_; + capacity_ = array.capacity_; + array.buffer_ = nullptr; + array.size_ = 0; + array.capacity_ = 0; + return *this; + } + + // Create a reference to "this". + operator ArrayCRef<Value>() const { + return cref(); + } + + // Create a reference to a part of "this". + ArrayCRef<Value> cref(size_t offset = 0) const { + return ArrayCRef<Value>(data() + offset, size_ - offset); + } + // Create a reference to a part of "this". + ArrayCRef<Value> cref(size_t offset, size_t size) const { + return ArrayCRef<Value>(data() + offset, size); + } + + // Create a reference to a part of "this". + ArrayRef<Value> ref(size_t offset = 0) { + return ArrayRef<Value>(buffer() + offset, size_ - offset); + } + // Create a reference to a part of "this". + ArrayRef<Value> ref(size_t offset, size_t size) { + return ArrayRef<Value>(buffer() + offset, size); + } + + // Return a reference to the "i"-th value. + const Value &get(size_t i) const { + return data()[i]; + } + // Set the "i"-th value. + void set(size_t i, const Value &value) { + buffer()[i] = value; + } + // Set the "i"-th value. + void set(size_t i, Value &&value) { + buffer()[i] = std::move(value); + } + + // Return a reference to the "i"-th value. + Value &operator[](size_t i) { + return buffer()[i]; + } + // Return a reference to the "i"-th value. + const Value &operator[](size_t i) const { + return data()[i]; + } + + // Return a reference to the first value. + Value &front() { + return *buffer(); + } + // Return a reference to the first value. + const Value &front() const { + return *data(); + } + + // Return a reference to the last value. + Value &back() { + return buffer()[size_ - 1]; + } + // Return a reference to the last value. + const Value &back() const { + return data()[size_ - 1]; + } + + // Return a pointer to the buffer. + Value *buffer() { + return static_cast<Value *>(buffer_); + } + // Return a pointer to the contents. + const Value *data() const { + return static_cast<const Value *>(buffer_); + } + + // Return whether the array is empty or not. + bool is_empty() const { + return size_ == 0; + } + // Return the number of values. + size_t size() const { + return size_; + } + // Return the number of values can be stored in the buffer. + size_t capacity() const { + return capacity_; + } + + // Reserve memory for at least "new_size" values. + // + // On failure, throws an exception. + void reserve(size_t new_size) { + if (new_size > capacity_) { + resize_buffer(new_size); + } + } + + // Resize "this". + // + // On failure, throws an exception. + void resize(size_t new_size) { + if (new_size > capacity_) { + resize_buffer(new_size); + } + for (size_t i = new_size; i < size_; ++i) { + buffer()[i].~Value(); + } + for (size_t i = size_; i < new_size; ++i) { + new (&buffer()[i]) Value; + } + size_ = new_size; + } + // Resize "this" and fill the new values with "value". + // + // On failure, throws an exception. + void resize(size_t new_size, const Value &value) { + if (new_size > capacity_) { + resize_buffer(new_size); + } + for (size_t i = new_size; i < size_; ++i) { + buffer()[i].~Value(); + } + for (size_t i = size_; i < new_size; ++i) { + new (&buffer()[i]) Value(value); + } + size_ = new_size; + } + + // Clear the contents. + void clear() { + for (size_t i = 0; i < size_; ++i) { + buffer()[i].~Value(); + } + size_ = 0; + } + + // Remove the "i"-th value. + void erase(size_t i) { + for (size_t j = i + 1; j < size_; ++j) { + buffer()[j - 1] = std::move(buffer()[j]); + } + buffer()[size_ - 1].~Value(); + --size_; + } + + // Append "value" to the end. + // + // On failure, throws an exception. + void push_back(const Value &value) { + if (size_ == capacity_) { + resize_buffer(size_ + 1); + } + new (&buffer()[size_]) Value(value); + ++size_; + } + // Append "value" to the end. + // + // On failure, throws an exception. + void push_back(Value &&value) { + if (size_ == capacity_) { + resize_buffer(size_ + 1); + } + new (&buffer()[size_]) Value(std::move(value)); + ++size_; + } + // Remove the last value. + void pop_back() { + buffer()[size_ - 1].~Value(); + --size_; + } + + private: + void *buffer_; + size_t size_; + size_t capacity_; + + // Resize the buffer for at least "new_size" values. + // + // Assumes that "new_size" is greater than "capacity_". + void resize_buffer(size_t new_size) { + if (capacity_ != 0) { + size_t new_capacity = capacity_ * 2; + if (new_size > new_capacity) { + new_capacity = new_size; + } + size_t new_buffer_size = sizeof(Value) * new_capacity; + Value *new_buffer = + static_cast<Value *>(std::realloc(buffer_, new_buffer_size)); + if (!new_buffer) { + throw "Memory allocation failed"; // TODO + } + buffer_ = new_buffer; + capacity_ = new_capacity; + } else { + size_t new_buffer_size = sizeof(Value) * new_size; + Value *new_buffer = static_cast<Value *>(std::malloc(new_buffer_size)); + if (!new_buffer) { + throw "Memory allocation failed"; // TODO + } + buffer_ = new_buffer; + capacity_ = new_size; + } + } +}; + } // namespace grnxx #endif // GRNXX_ARRAY_HPP -------------- next part -------------- HTML����������������������������...ダウンロード
