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