1.1 --- /dev/null Thu Jan 01 00:00:00 1970 +0000
1.2 +++ b/gfx/graphite2/src/inc/List.h Wed Dec 31 06:09:35 2014 +0100
1.3 @@ -0,0 +1,155 @@
1.4 +/* GRAPHITE2 LICENSING
1.5 +
1.6 + Copyright 2010, SIL International
1.7 + All rights reserved.
1.8 +
1.9 + This library is free software; you can redistribute it and/or modify
1.10 + it under the terms of the GNU Lesser General Public License as published
1.11 + by the Free Software Foundation; either version 2.1 of License, or
1.12 + (at your option) any later version.
1.13 +
1.14 + This program is distributed in the hope that it will be useful,
1.15 + but WITHOUT ANY WARRANTY; without even the implied warranty of
1.16 + MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the GNU
1.17 + Lesser General Public License for more details.
1.18 +
1.19 + You should also have received a copy of the GNU Lesser General Public
1.20 + License along with this library in the file named "LICENSE".
1.21 + If not, write to the Free Software Foundation, 51 Franklin Street,
1.22 + Suite 500, Boston, MA 02110-1335, USA or visit their web page on the
1.23 + internet at http://www.fsf.org/licenses/lgpl.html.
1.24 +
1.25 +Alternatively, the contents of this file may be used under the terms of the
1.26 +Mozilla Public License (http://mozilla.org/MPL) or the GNU General Public
1.27 +License, as published by the Free Software Foundation, either version 2
1.28 +of the License or (at your option) any later version.
1.29 +*/
1.30 +
1.31 +// designed to have a limited subset of the std::vector api
1.32 +#pragma once
1.33 +
1.34 +#include <cstddef>
1.35 +#include <cassert>
1.36 +#include <cstring>
1.37 +#include <cstdlib>
1.38 +#include <new>
1.39 +
1.40 +
1.41 +namespace graphite2 {
1.42 +
1.43 +template <typename T>
1.44 +inline
1.45 +ptrdiff_t distance(T* first, T* last) { return last-first; }
1.46 +
1.47 +
1.48 +template <typename T>
1.49 +class Vector
1.50 +{
1.51 + T * m_first, *m_last, *m_end;
1.52 +public:
1.53 + typedef T & reference;
1.54 + typedef const T & const_reference;
1.55 + typedef T * iterator;
1.56 + typedef const T * const_iterator;
1.57 +
1.58 + Vector() : m_first(0), m_last(0), m_end(0) {}
1.59 + Vector(size_t n, const T& value = T()) : m_first(0), m_last(0), m_end(0) { insert(begin(), n, value); }
1.60 + Vector(const Vector<T> &rhs) : m_first(0), m_last(0), m_end(0) { insert(begin(), rhs.begin(), rhs.end()); }
1.61 + template <typename I>
1.62 + Vector(I first, const I last) : m_first(0), m_last(0), m_end(0) { insert(begin(), first, last); }
1.63 + ~Vector() { clear(); free(m_first); }
1.64 +
1.65 + iterator begin() { return m_first; }
1.66 + const_iterator begin() const { return m_first; }
1.67 +
1.68 + iterator end() { return m_last; }
1.69 + const_iterator end() const { return m_last; }
1.70 +
1.71 + bool empty() const { return m_first == m_last; }
1.72 + size_t size() const { return m_last - m_first; }
1.73 + size_t capacity() const{ return m_end - m_first; }
1.74 +
1.75 + void reserve(size_t n);
1.76 +
1.77 + reference front() { assert(size() > 0); return *begin(); }
1.78 + const_reference front() const { assert(size() > 0); return *begin(); }
1.79 + reference back() { assert(size() > 0); return *(end()-1); }
1.80 + const_reference back() const { assert(size() > 0); return *(end()-1); }
1.81 +
1.82 + Vector<T> & operator = (const Vector<T> & rhs) { assign(rhs.begin(), rhs.end()); return *this; }
1.83 + reference operator [] (size_t n) { assert(size() > n); return m_first[n]; }
1.84 + const_reference operator [] (size_t n) const { assert(size() > n); return m_first[n]; }
1.85 +
1.86 + void assign(size_t n, const T& u) { clear(); insert(begin(), n, u); }
1.87 + void assign(const_iterator first, const_iterator last) { clear(); insert(begin(), first, last); }
1.88 + iterator insert(iterator p, const T & x) { p = _insert_default(p, 1); *p = x; return p; }
1.89 + void insert(iterator p, size_t n, const T & x);
1.90 + void insert(iterator p, const_iterator first, const_iterator last);
1.91 + void pop_back() { assert(size() > 0); --m_last; }
1.92 + void push_back(const T &v) { if (m_last == m_end) reserve(size()+1); new (m_last++) T(v); }
1.93 +
1.94 + void clear() { erase(begin(), end()); }
1.95 + iterator erase(iterator p) { return erase(p, p+1); }
1.96 + iterator erase(iterator first, iterator last);
1.97 +
1.98 +private:
1.99 + iterator _insert_default(iterator p, size_t n);
1.100 +};
1.101 +
1.102 +template <typename T>
1.103 +inline
1.104 +void Vector<T>::reserve(size_t n)
1.105 +{
1.106 + if (n > capacity())
1.107 + {
1.108 + const ptrdiff_t sz = size();
1.109 + m_first = static_cast<T*>(realloc(m_first, n*sizeof(T)));
1.110 + m_last = m_first + sz;
1.111 + m_end = m_first + n;
1.112 + }
1.113 +}
1.114 +
1.115 +template<typename T>
1.116 +inline
1.117 +typename Vector<T>::iterator Vector<T>::_insert_default(iterator p, size_t n)
1.118 +{
1.119 + assert(begin() <= p && p <= end());
1.120 + const ptrdiff_t i = p - begin();
1.121 + reserve((size() + n + 7) >> 3 << 3);
1.122 + p = begin() + i;
1.123 + // Move tail if there is one
1.124 + if (p != end()) memmove(p + n, p, distance(p,end())*sizeof(T));
1.125 + m_last += n;
1.126 + return p;
1.127 +}
1.128 +
1.129 +template<typename T>
1.130 +inline
1.131 +void Vector<T>::insert(iterator p, size_t n, const T & x)
1.132 +{
1.133 + p = _insert_default(p, n);
1.134 + // Copy in elements
1.135 + for (; n; --n, ++p) { new (p) T(x); }
1.136 +}
1.137 +
1.138 +template<typename T>
1.139 +inline
1.140 +void Vector<T>::insert(iterator p, const_iterator first, const_iterator last)
1.141 +{
1.142 + p = _insert_default(p, distance(first, last));
1.143 + // Copy in elements
1.144 + for (;first != last; ++first, ++p) { new (p) T(*first); }
1.145 +}
1.146 +
1.147 +template<typename T>
1.148 +inline
1.149 +typename Vector<T>::iterator Vector<T>::erase(iterator first, iterator last)
1.150 +{
1.151 + for (iterator e = first; e != last; ++e) e->~T();
1.152 + const size_t sz = distance(first, last);
1.153 + if (m_last != last) memmove(first, last, distance(last,end())*sizeof(T));
1.154 + m_last -= sz;
1.155 + return first;
1.156 +}
1.157 +
1.158 +} // namespace graphite2
