1 //===-- A self contained equivalent of std::vector --------------*- C++ -*-===//
2 //
3 // Part of the LLVM Project, under the Apache License v2.0 with LLVM Exceptions.
4 // See https://llvm.org/LICENSE.txt for license information.
5 // SPDX-License-Identifier: Apache-2.0 WITH LLVM-exception
6 //
7 //===----------------------------------------------------------------------===//
8 
9 #ifndef LLVM_LIBC_SRC_SUPPORT_CPP_VECTOR_H
10 #define LLVM_LIBC_SRC_SUPPORT_CPP_VECTOR_H
11 
12 #include <stddef.h> // For size_t.
13 
14 #include <stdlib.h> // For malloc/realloc/free
15 
16 namespace __llvm_libc {
17 namespace cpp {
18 
19 // This implementation does not have a templated allocator since that feature
20 // isn't relevant for a libc setting.
21 
22 // Vector is a templated dynamically resizable array. This implementation is
23 // only meant for primitives or structs, and will not call destructors on held
24 // objects.
25 template <class T> class vector {
26   T *data_array;
27   size_t array_size;
28   size_t num_elements = 0;
29   static constexpr size_t DEFAULT_SIZE = 16;
30   static constexpr size_t GROWTH_FACTOR = 2;
31   static constexpr size_t MAX_SIZE = ~size_t(0);
32 
33 public:
34   constexpr vector<T>() : array_size{DEFAULT_SIZE} {
35     data_array = static_cast<T *>(malloc(DEFAULT_SIZE * sizeof(T)));
36   }
37 
38   constexpr vector<T>(const vector<T> &other) = delete;
39   constexpr vector<T>(const vector<T> &&other) = delete;
40 
~vector()41   ~vector() { free(data_array); }
42 
43   constexpr vector &operator=(vector &other) = delete;
44   constexpr vector &operator=(vector &&other) = delete;
45 
reserve(size_t new_size)46   constexpr void reserve(size_t new_size) {
47     if (new_size >= array_size)
48       increase_size(new_size + 1);
49   }
50 
push_back(const T & value)51   constexpr void push_back(const T &value) {
52     if (num_elements >= array_size)
53       increase_size(num_elements + 1);
54     data_array[num_elements] = value;
55     ++num_elements;
56   }
57 
58   constexpr T &operator[](size_t pos) { return data_array[pos]; }
data()59   constexpr T *data() { return data_array; }
data()60   constexpr const T *data() const { return data_array; }
61 
empty()62   constexpr bool empty() const { return num_elements == 0; }
63 
size()64   constexpr size_t size() const { return num_elements; }
max_size()65   constexpr size_t max_size() const { return MAX_SIZE; }
66 
capacity()67   constexpr size_t capacity() const { return array_size; }
68 
69 private:
70   static constexpr size_t MAX_DIV_BY_GROWTH = MAX_SIZE / GROWTH_FACTOR;
71 
72   // new_size is treated as the minimum size for the new array. This function
73   // will increase array_size by GROWTH_FACTOR until there is space for new_size
74   // items.
increase_size(size_t new_size)75   constexpr void increase_size(size_t new_size) {
76     size_t temp_size = array_size;
77     if (new_size >= MAX_DIV_BY_GROWTH) {
78       temp_size = new_size;
79     } else {
80       if (temp_size == 0)
81         temp_size = 1;
82       while (temp_size <= new_size)
83         temp_size = temp_size * GROWTH_FACTOR;
84     }
85     array_size = temp_size;
86     data_array = static_cast<T *>(realloc(data_array, array_size * sizeof(T)));
87   }
88 };
89 } // namespace cpp
90 } // namespace __llvm_libc
91 
92 #endif // LLVM_LIBC_SRC_SUPPORT_CPP_VECTOR_H
93