vector.h revision a715cb1840f9a0c813c90707a351687f7a77950e 
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
20extern "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
30namespace 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.
36template <typename ElementType> class Vector {
37 public:
38  Vector() = default;
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;
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  }
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
80  ElementType* begin() { return data_; }
81  ElementType* end() { return data_ + size_; }
82
83  const ElementType* begin() const { return data_; }
84  const ElementType* end() const { return data_ + size_; }
85
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.
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.
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.
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