1 /// 2 /// @file malloc_vector 3 /// 4 /// Copyright (C) 2020 Kim Walisch, <kim.walisch@gmail.com> 5 /// 6 /// This file is distributed under the BSD License. See the COPYING 7 /// file in the top level directory. 8 /// 9 10 #ifndef MALLOC_VECTOR_HPP 11 #define MALLOC_VECTOR_HPP 12 13 #include <stdlib.h> 14 #include <algorithm> 15 #include <cstddef> 16 #include <new> 17 18 namespace { 19 20 /// malloc_vector is a dynamically growing array. 21 /// It has the same API (though not complete) as std::vector but it 22 /// uses malloc as its allocator. 23 /// 24 template <typename T> 25 class malloc_vector 26 { 27 public: malloc_vector()28 malloc_vector() 29 { 30 resize(16); 31 } 32 malloc_vector(std::size_t n)33 malloc_vector(std::size_t n) 34 { 35 resize(n); 36 } 37 ~malloc_vector()38 ~malloc_vector() 39 { 40 if (is_free_) 41 free((void*) array_); 42 } 43 push_back(const T & val)44 void push_back(const T& val) 45 { 46 array_[size_++] = val; 47 if (size_ >= capacity_) 48 resize(size_ * 2); 49 } 50 reserve(std::size_t n)51 void reserve(std::size_t n) 52 { 53 if (n > capacity_) 54 resize(n); 55 } 56 resize(std::size_t n)57 void resize(std::size_t n) 58 { 59 n = std::max(n, (std::size_t) 16); 60 T* new_array = (T*) realloc((void*) array_, n * sizeof(T)); 61 62 if (!new_array) 63 throw std::bad_alloc(); 64 65 array_ = new_array; 66 capacity_ = n; 67 size_ = std::min(size_, capacity_); 68 } 69 operator [](T n)70 T& operator[] (T n) 71 { 72 return array_[n]; 73 } 74 data()75 T* data() 76 { 77 return array_; 78 } 79 size() const80 std::size_t size() const 81 { 82 return size_; 83 } 84 disable_free()85 void disable_free() 86 { 87 is_free_ = false; 88 } 89 90 public: 91 using value_type = T; 92 93 private: 94 T* array_ = nullptr; 95 std::size_t size_ = 0; 96 std::size_t capacity_ = 0; 97 bool is_free_ = true; 98 }; 99 100 } // namespace 101 102 #endif 103