1 /*
2  * Copyright (C) 2016 The Android Open Source Project
3  *
4  * Licensed under the Apache License, Version 2.0 (the "License");
5  * you may not use this file except in compliance with the License.
6  * You may obtain a copy of the License at
7  *
8  *      http://www.apache.org/licenses/LICENSE-2.0
9  *
10  * Unless required by applicable law or agreed to in writing, software
11  * distributed under the License is distributed on an "AS IS" BASIS,
12  * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
13  * See the License for the specific language governing permissions and
14  * limitations under the License.
15  */
16 
17 #ifndef NVRAM_MESSAGES_VECTOR_H_
18 #define NVRAM_MESSAGES_VECTOR_H_
19 
20 extern "C" {
21 #include <stddef.h>
22 #include <stdint.h>
23 #include <stdlib.h>
24 }
25 
26 #include <new>
27 
28 #include <nvram/messages/compiler.h>
29 
30 namespace nvram {
31 
32 // A bare-bones dynamically-sized array container, similar to std::vector.
33 //
34 // This class is intended for use in restricted environments where the C++
35 // standard library is not available. Prefer std::vector wherever possible.
36 template <typename ElementType> class Vector {
37  public:
38   Vector() = default;
~Vector()39   ~Vector() {
40     for (size_t i = 0; i < size_; ++i) {
41       data_[i].~ElementType();
42     }
43     free(data_);
44     data_ = nullptr;
45     size_ = 0;
46     capacity_ = 0;
47   }
48 
49   // Vector is not copyable as this would require memory allocations that may
50   // fail. However, Vector supports move semantics.
51   Vector(const Vector<ElementType>& other) = delete;
52   Vector<ElementType>& operator=(const Vector<ElementType>& other) = delete;
Vector(Vector<ElementType> && other)53   Vector(Vector<ElementType>&& other) : Vector() {
54     swap(*this, other);
55   }
56   Vector<ElementType>& operator=(Vector<ElementType>&& other) {
57     swap(*this, other);
58     return *this;
59   }
swap(Vector<ElementType> & first,Vector<ElementType> & second)60   friend void swap(Vector<ElementType>& first, Vector<ElementType>& second) {
61     // This does not use std::swap since it needs to work in environments that
62     // are lacking a standard library.
63     ElementType* tmp_data = first.data_;
64     size_t tmp_size = first.size_;
65     first.data_ = second.data_;
66     first.size_ = second.size_;
67     second.data_ = tmp_data;
68     second.size_ = tmp_size;
69   }
70 
71   ElementType& operator[](size_t pos) {
72     NVRAM_CHECK(pos < size_);
73     return data_[pos];
74   }
75   const ElementType& operator[](size_t pos) const {
76     NVRAM_CHECK(pos < size_);
77     return data_[pos];
78   }
79 
begin()80   ElementType* begin() { return data_; }
end()81   ElementType* end() { return data_ + size_; }
82 
begin()83   const ElementType* begin() const { return data_; }
end()84   const ElementType* end() const { return data_ + size_; }
85 
size()86   size_t size() const { return size_; }
87 
88   // Resizes the Vector. Truncates if |size| decreases. Pads the Vector with
89   // value-constructed entries if |size| increases.
Resize(size_t size)90   bool Resize(size_t size) NVRAM_WARN_UNUSED_RESULT {
91     // Check for capacity change.
92     size_t new_capacity = capacity_;
93     if (size < capacity_ / 2) {
94       new_capacity = size;
95     } else if (size > capacity_) {
96       new_capacity = capacity_ * 2 > size ? capacity_ * 2 : size;
97     }
98     NVRAM_CHECK(new_capacity >= size);
99 
100     // Allocate new memory if necessary.
101     ElementType* new_data = nullptr;
102     if (new_capacity != capacity_) {
103       if (new_capacity == 0) {
104         new_data = nullptr;
105       } else {
106         new_data = static_cast<ElementType*>(
107             calloc(new_capacity, sizeof(ElementType)));
108         if (!new_data) {
109           return false;
110         }
111       }
112     } else {
113       new_data = data_;
114     }
115 
116     size_t min_size = (size < size_) ? size : size_;
117     if (new_data != data_) {
118       // Move elements that remain valid.
119       for (size_t i = 0; i < min_size; ++i) {
120         new (&new_data[i]) ElementType(static_cast<ElementType&&>(data_[i]));
121       }
122     }
123 
124     // Destroy elements that are no longer part of the list.
125     for (size_t i = min_size; i < size_; ++i) {
126       data_[i].~ElementType();
127     }
128 
129     // Construct new elements that got appended.
130     for (size_t i = min_size; i < size; ++i) {
131       new (&new_data[i]) ElementType;
132     }
133 
134     if (new_data != data_) {
135       free(data_);
136     }
137     data_ = new_data;
138     capacity_ = new_capacity;
139     size_ = size;
140     return true;
141   }
142 
143   // Appends an element.
Append(const ElementType & element)144   bool Append(const ElementType& element) NVRAM_WARN_UNUSED_RESULT {
145     if (!Resize(size_ + 1)) {
146       return false;
147     }
148     data_[size_ - 1] = element;
149     return true;
150   }
151 
152   // Rvalue-reference version of Append.
Append(ElementType && element)153   bool Append(ElementType&& element) NVRAM_WARN_UNUSED_RESULT {
154     if (!Resize(size_ + 1)) {
155       return false;
156     }
157     data_[size_ - 1] = element;
158     return true;
159   }
160 
161  private:
162   size_t size_ = 0;
163   size_t capacity_ = 0;
164   ElementType* data_ = nullptr;
165 };
166 
167 }  // namespace nvram
168 
169 #endif  // NVRAM_MESSAGES_VECTOR_H_
170