List.h (6148B)
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 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 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); } 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> 60 Vector(I first, const I last) : m_first(0), m_last(0), m_end(0) { insert(begin(), first, last); } 61 ~Vector() { clear(); free(m_first); } 62 63 iterator begin() { return m_first; } 64 const_iterator begin() const { return m_first; } 65 66 iterator end() { return m_last; } 67 const_iterator end() const { return m_last; } 68 69 bool empty() const { return m_first == m_last; } 70 size_t size() const { return m_last - m_first; } 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 76 reference front() { assert(size() > 0); return *begin(); } 77 const_reference front() const { assert(size() > 0); return *begin(); } 78 reference back() { assert(size() > 0); return *(end()-1); } 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 85 void assign(size_t n, const T& u) { clear(); insert(begin(), n, u); } 86 void assign(const_iterator first, const_iterator last) { clear(); insert(begin(), first, last); } 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); 90 void pop_back() { assert(size() > 0); --m_last; } 91 void push_back(const T &v) { if (m_last == m_end) reserve(size()+1); new (m_last++) T(v); } 92 93 void clear() { erase(begin(), end()); } 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 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 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 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 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 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 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