Sparse.h (4765B)
1 /* GRAPHITE2 LICENSING 2 3 Copyright 2011, 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 #pragma once 28 #include <iterator> 29 #include <utility> 30 31 #include "inc/Main.h" 32 33 namespace graphite2 { 34 35 36 // A read-only packed fast sparse array of uint16 with uint16 keys. 37 // Like most container classes this has capacity and size properties and these 38 // refer to the number of stored entries and the number of addressable entries 39 // as normal. However due the sparse nature the capacity is always <= than the 40 // size. 41 class sparse 42 { 43 public: 44 typedef uint16 key_type; 45 typedef uint16 mapped_type; 46 typedef std::pair<const key_type, mapped_type> value_type; 47 48 private: 49 typedef unsigned long mask_t; 50 51 static const unsigned char SIZEOF_CHUNK = (sizeof(mask_t) - sizeof(key_type))*8; 52 53 struct chunk 54 { 55 mask_t mask:SIZEOF_CHUNK; 56 key_type offset; 57 }; 58 59 static const chunk empty_chunk; 60 sparse(const sparse &); 61 sparse & operator = (const sparse &); 62 63 public: 64 template<typename I> 65 sparse(I first, const I last); 66 sparse() throw(); 67 ~sparse() throw(); 68 69 operator bool () const throw(); 70 mapped_type operator [] (const key_type k) const throw(); 71 72 size_t capacity() const throw(); 73 size_t size() const throw(); 74 75 size_t _sizeof() const throw(); 76 77 CLASS_NEW_DELETE; 78 79 private: 80 union { 81 chunk * map; 82 mapped_type * values; 83 } m_array; 84 key_type m_nchunks; 85 }; 86 87 88 inline 89 sparse::sparse() throw() : m_nchunks(0) 90 { 91 m_array.map = const_cast<graphite2::sparse::chunk *>(&empty_chunk); 92 } 93 94 95 template <typename I> 96 sparse::sparse(I attr, const I last) 97 : m_nchunks(0) 98 { 99 m_array.map = 0; 100 101 // Find the maximum extent of the key space. 102 size_t n_values=0; 103 long lastkey = -1; 104 for (I i = attr; i != last; ++i, ++n_values) 105 { 106 const typename std::iterator_traits<I>::value_type v = *i; 107 if (v.second == 0) { --n_values; continue; } 108 if (v.first <= lastkey) { m_nchunks = 0; return; } 109 110 lastkey = v.first; 111 const key_type k = v.first / SIZEOF_CHUNK; 112 if (k >= m_nchunks) m_nchunks = k+1; 113 } 114 if (m_nchunks == 0) 115 { 116 m_array.map=const_cast<graphite2::sparse::chunk *>(&empty_chunk); 117 return; 118 } 119 120 m_array.values = grzeroalloc<mapped_type>((m_nchunks*sizeof(chunk) + sizeof(mapped_type)-1) 121 / sizeof(mapped_type) 122 + n_values); 123 124 if (m_array.values == 0) 125 return; 126 127 // coverity[forward_null : FALSE] Since m_array is union and m_array.values is not NULL 128 chunk * ci = m_array.map; 129 ci->offset = (m_nchunks*sizeof(chunk) + sizeof(mapped_type)-1)/sizeof(mapped_type); 130 mapped_type * vi = m_array.values + ci->offset; 131 for (; attr != last; ++attr, ++vi) 132 { 133 const typename std::iterator_traits<I>::value_type v = *attr; 134 if (v.second == 0) { --vi; continue; } 135 136 chunk * const ci_ = m_array.map + v.first/SIZEOF_CHUNK; 137 138 if (ci != ci_) 139 { 140 ci = ci_; 141 ci->offset = key_type(vi - m_array.values); 142 } 143 144 ci->mask |= 1UL << (SIZEOF_CHUNK - 1 - (v.first % SIZEOF_CHUNK)); 145 *vi = v.second; 146 } 147 } 148 149 150 inline 151 sparse::operator bool () const throw() 152 { 153 return m_array.map != 0; 154 } 155 156 inline 157 size_t sparse::size() const throw() 158 { 159 return m_nchunks*SIZEOF_CHUNK; 160 } 161 162 inline 163 size_t sparse::_sizeof() const throw() 164 { 165 return sizeof(sparse) + capacity()*sizeof(mapped_type) + m_nchunks*sizeof(chunk); 166 } 167 168 } // namespace graphite2