1 /* GRAPHITE2 LICENSING
2
3 Copyright 2010, SIL International
4 All rights reserved.
5
6 This library is free software; you can redistribute it and/or modify
7 it under the terms of the GNU Lesser General Public License as published
8 by the Free Software Foundation; either version 2.1 of License, or
9 (at your option) any later version.
10
11 This program is distributed in the hope that it will be useful,
12 but WITHOUT ANY WARRANTY; without even the implied warranty of
13 MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the GNU
14 Lesser General Public License for more details.
15
16 You should also have received a copy of the GNU Lesser General Public
17 License along with this library in the file named "LICENSE".
18 If not, write to the Free Software Foundation, 51 Franklin Street,
19 Suite 500, Boston, MA 02110-1335, USA or visit their web page on the
20 internet at http://www.fsf.org/licenses/lgpl.html.
21
22 Alternatively, the contents of this file may be used under the terms of the
23 Mozilla Public License (http://mozilla.org/MPL) or the GNU General Public
24 License, as published by the Free Software Foundation, either version 2
25 of the License or (at your option) any later version.
26 */
27
28 // designed to have a limited subset of the std::vector api
29 #pragma once
30
31 #include <cstddef>
32 #include <cassert>
33 #include <cstring>
34 #include <cstdlib>
35 #include <new>
36
37 #include "Main.h"
38
39 namespace graphite2 {
40
41 template <typename T>
42 inline
distance(T * first,T * last)43 ptrdiff_t distance(T* first, T* last) { return last-first; }
44
45
46 template <typename T>
47 class Vector
48 {
49 T * m_first, *m_last, *m_end;
50 public:
51 typedef T & reference;
52 typedef const T & const_reference;
53 typedef T * iterator;
54 typedef const T * const_iterator;
55
Vector()56 Vector() : m_first(0), m_last(0), m_end(0) {}
57 Vector(size_t n, const T& value = T()) : m_first(0), m_last(0), m_end(0) { insert(begin(), n, value); }
Vector(const Vector<T> & rhs)58 Vector(const Vector<T> &rhs) : m_first(0), m_last(0), m_end(0) { insert(begin(), rhs.begin(), rhs.end()); }
59 template <typename I>
Vector(I first,const I last)60 Vector(I first, const I last) : m_first(0), m_last(0), m_end(0) { insert(begin(), first, last); }
~Vector()61 ~Vector() { clear(); free(m_first); }
62
begin()63 iterator begin() { return m_first; }
begin()64 const_iterator begin() const { return m_first; }
65
end()66 iterator end() { return m_last; }
end()67 const_iterator end() const { return m_last; }
68
empty()69 bool empty() const { return m_first == m_last; }
size()70 size_t size() const { return m_last - m_first; }
capacity()71 size_t capacity() const{ return m_end - m_first; }
72
73 void reserve(size_t n);
74 void resize(size_t n, const T & v = T());
75
front()76 reference front() { assert(size() > 0); return *begin(); }
front()77 const_reference front() const { assert(size() > 0); return *begin(); }
back()78 reference back() { assert(size() > 0); return *(end()-1); }
back()79 const_reference back() const { assert(size() > 0); return *(end()-1); }
80
81 Vector<T> & operator = (const Vector<T> & rhs) { assign(rhs.begin(), rhs.end()); return *this; }
82 reference operator [] (size_t n) { assert(size() > n); return m_first[n]; }
83 const_reference operator [] (size_t n) const { assert(size() > n); return m_first[n]; }
84
assign(size_t n,const T & u)85 void assign(size_t n, const T& u) { clear(); insert(begin(), n, u); }
assign(const_iterator first,const_iterator last)86 void assign(const_iterator first, const_iterator last) { clear(); insert(begin(), first, last); }
insert(iterator p,const T & x)87 iterator insert(iterator p, const T & x) { p = _insert_default(p, 1); new (p) T(x); return p; }
88 void insert(iterator p, size_t n, const T & x);
89 void insert(iterator p, const_iterator first, const_iterator last);
pop_back()90 void pop_back() { assert(size() > 0); --m_last; }
push_back(const T & v)91 void push_back(const T &v) { if (m_last == m_end) reserve(size()+1); new (m_last++) T(v); }
92
clear()93 void clear() { erase(begin(), end()); }
erase(iterator p)94 iterator erase(iterator p) { return erase(p, p+1); }
95 iterator erase(iterator first, iterator last);
96
97 private:
98 iterator _insert_default(iterator p, size_t n);
99 };
100
101 template <typename T>
102 inline
reserve(size_t n)103 void Vector<T>::reserve(size_t n)
104 {
105 if (n > capacity())
106 {
107 const ptrdiff_t sz = size();
108 size_t requested;
109 if (checked_mul(n,sizeof(T), requested)) std::abort();
110 m_first = static_cast<T*>(realloc(m_first, requested));
111 if (!m_first) std::abort();
112 m_last = m_first + sz;
113 m_end = m_first + n;
114 }
115 }
116
117 template <typename T>
118 inline
resize(size_t n,const T & v)119 void Vector<T>::resize(size_t n, const T & v) {
120 const ptrdiff_t d = n-size();
121 if (d < 0) erase(end()+d, end());
122 else if (d > 0) insert(end(), d, v);
123 }
124
125 template<typename T>
126 inline
_insert_default(iterator p,size_t n)127 typename Vector<T>::iterator Vector<T>::_insert_default(iterator p, size_t n)
128 {
129 assert(begin() <= p && p <= end());
130 const ptrdiff_t i = p - begin();
131 reserve(((size() + n + 7) >> 3) << 3);
132 p = begin() + i;
133 // Move tail if there is one
134 if (p != end()) memmove(p + n, p, distance(p,end())*sizeof(T));
135 m_last += n;
136 return p;
137 }
138
139 template<typename T>
140 inline
insert(iterator p,size_t n,const T & x)141 void Vector<T>::insert(iterator p, size_t n, const T & x)
142 {
143 p = _insert_default(p, n);
144 // Copy in elements
145 for (; n; --n, ++p) { new (p) T(x); }
146 }
147
148 template<typename T>
149 inline
insert(iterator p,const_iterator first,const_iterator last)150 void Vector<T>::insert(iterator p, const_iterator first, const_iterator last)
151 {
152 p = _insert_default(p, distance(first, last));
153 // Copy in elements
154 for (;first != last; ++first, ++p) { new (p) T(*first); }
155 }
156
157 template<typename T>
158 inline
erase(iterator first,iterator last)159 typename Vector<T>::iterator Vector<T>::erase(iterator first, iterator last)
160 {
161 for (iterator e = first; e != last; ++e) e->~T();
162 const size_t sz = distance(first, last);
163 if (m_last != last) memmove(first, last, distance(last,end())*sizeof(T));
164 m_last -= sz;
165 return first;
166 }
167
168 } // namespace graphite2
169