1 | // SPDX-License-Identifier: MIT OR MPL-2.0 OR LGPL-2.1-or-later OR GPL-2.0-or-later |
2 | // Copyright 2010, SIL International, All rights reserved. |
3 | |
4 | |
5 | // designed to have a limited subset of the std::vector api |
6 | #pragma once |
7 | |
8 | #include <cstddef> |
9 | #include <cassert> |
10 | #include <cstring> |
11 | #include <cstdlib> |
12 | #include <new> |
13 | |
14 | #include "Main.h" |
15 | |
16 | namespace graphite2 { |
17 | |
18 | template <typename T> |
19 | inline |
20 | ptrdiff_t distance(T* first, T* last) { return last-first; } |
21 | |
22 | |
23 | template <typename T> |
24 | class Vector |
25 | { |
26 | T * m_first, *m_last, *m_end; |
27 | public: |
28 | typedef T & reference; |
29 | typedef const T & const_reference; |
30 | typedef T * iterator; |
31 | typedef const T * const_iterator; |
32 | |
33 | Vector() : m_first(0), m_last(0), m_end(0) {} |
34 | Vector(size_t n, const T& value = T()) : m_first(0), m_last(0), m_end(0) { insert(begin(), n, value); } |
35 | Vector(const Vector<T> &rhs) : m_first(0), m_last(0), m_end(0) { insert(begin(), rhs.begin(), rhs.end()); } |
36 | template <typename I> |
37 | Vector(I first, const I last) : m_first(0), m_last(0), m_end(0) { insert(begin(), first, last); } |
38 | ~Vector() { clear(); free(m_first); } |
39 | |
40 | iterator begin() { return m_first; } |
41 | const_iterator begin() const { return m_first; } |
42 | |
43 | iterator end() { return m_last; } |
44 | const_iterator end() const { return m_last; } |
45 | |
46 | bool empty() const { return m_first == m_last; } |
47 | size_t size() const { return m_last - m_first; } |
48 | size_t capacity() const{ return m_end - m_first; } |
49 | |
50 | void reserve(size_t n); |
51 | void resize(size_t n, const T & v = T()); |
52 | |
53 | reference front() { assert(size() > 0); return *begin(); } |
54 | const_reference front() const { assert(size() > 0); return *begin(); } |
55 | reference back() { assert(size() > 0); return *(end()-1); } |
56 | const_reference back() const { assert(size() > 0); return *(end()-1); } |
57 | |
58 | Vector<T> & operator = (const Vector<T> & rhs) { assign(rhs.begin(), rhs.end()); return *this; } |
59 | reference operator [] (size_t n) { assert(size() > n); return m_first[n]; } |
60 | const_reference operator [] (size_t n) const { assert(size() > n); return m_first[n]; } |
61 | |
62 | void assign(size_t n, const T& u) { clear(); insert(begin(), n, u); } |
63 | void assign(const_iterator first, const_iterator last) { clear(); insert(begin(), first, last); } |
64 | iterator insert(iterator p, const T & x) { p = _insert_default(p, 1); new (p) T(x); return p; } |
65 | void insert(iterator p, size_t n, const T & x); |
66 | void insert(iterator p, const_iterator first, const_iterator last); |
67 | void pop_back() { assert(size() > 0); --m_last; } |
68 | void push_back(const T &v) { if (m_last == m_end) reserve(size()+1); new (m_last++) T(v); } |
69 | |
70 | void clear() { erase(begin(), end()); } |
71 | iterator erase(iterator p) { return erase(p, p+1); } |
72 | iterator erase(iterator first, iterator last); |
73 | |
74 | private: |
75 | iterator _insert_default(iterator p, size_t n); |
76 | }; |
77 | |
78 | template <typename T> |
79 | inline |
80 | void Vector<T>::reserve(size_t n) |
81 | { |
82 | if (n > capacity()) |
83 | { |
84 | const ptrdiff_t sz = size(); |
85 | size_t requested; |
86 | if (checked_mul(n,sizeof(T), requested)) std::abort(); |
87 | m_first = static_cast<T*>(realloc(m_first, requested)); |
88 | if (!m_first) std::abort(); |
89 | m_last = m_first + sz; |
90 | m_end = m_first + n; |
91 | } |
92 | } |
93 | |
94 | template <typename T> |
95 | inline |
96 | void Vector<T>::resize(size_t n, const T & v) { |
97 | const ptrdiff_t d = n-size(); |
98 | if (d < 0) erase(end()+d, end()); |
99 | else if (d > 0) insert(end(), d, v); |
100 | } |
101 | |
102 | template<typename T> |
103 | inline |
104 | typename Vector<T>::iterator Vector<T>::_insert_default(iterator p, size_t n) |
105 | { |
106 | assert(begin() <= p && p <= end()); |
107 | const ptrdiff_t i = p - begin(); |
108 | reserve(((size() + n + 7) >> 3) << 3); |
109 | p = begin() + i; |
110 | // Move tail if there is one |
111 | if (p != end()) memmove(p + n, p, distance(p,end())*sizeof(T)); |
112 | m_last += n; |
113 | return p; |
114 | } |
115 | |
116 | template<typename T> |
117 | inline |
118 | void Vector<T>::insert(iterator p, size_t n, const T & x) |
119 | { |
120 | p = _insert_default(p, n); |
121 | // Copy in elements |
122 | for (; n; --n, ++p) { new (p) T(x); } |
123 | } |
124 | |
125 | template<typename T> |
126 | inline |
127 | void Vector<T>::insert(iterator p, const_iterator first, const_iterator last) |
128 | { |
129 | p = _insert_default(p, distance(first, last)); |
130 | // Copy in elements |
131 | for (;first != last; ++first, ++p) { new (p) T(*first); } |
132 | } |
133 | |
134 | template<typename T> |
135 | inline |
136 | typename Vector<T>::iterator Vector<T>::erase(iterator first, iterator last) |
137 | { |
138 | for (iterator e = first; e != last; ++e) e->~T(); |
139 | const size_t sz = distance(first, last); |
140 | if (m_last != last) memmove(first, last, distance(last,end())*sizeof(T)); |
141 | m_last -= sz; |
142 | return first; |
143 | } |
144 | |
145 | } // namespace graphite2 |
146 | |