The Tor Browser / file comparison
comparison: gfx/graphite2/src/inc/Sparse.h
gfx/graphite2/src/inc/Sparse.h
- branch
- TOR_BUG_9701
- changeset 15
- b8a032363ba2
equal
deleted
inserted
replaced
| -1:000000000000 | 0:35f49fd43455 |
|---|---|
| 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 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 = &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=&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 { | |
| 126 free(m_array.values); m_array.map=0; | |
| 127 return; | |
| 128 } | |
| 129 | |
| 130 chunk * ci = m_array.map; | |
| 131 ci->offset = (m_nchunks*sizeof(chunk) + sizeof(mapped_type)-1)/sizeof(mapped_type); | |
| 132 mapped_type * vi = m_array.values + ci->offset; | |
| 133 for (; attr != last; ++attr, ++vi) | |
| 134 { | |
| 135 const typename std::iterator_traits<I>::value_type v = *attr; | |
| 136 if (v.second == 0) { --vi; continue; } | |
| 137 | |
| 138 chunk * const ci_ = m_array.map + v.first/SIZEOF_CHUNK; | |
| 139 | |
| 140 if (ci != ci_) | |
| 141 { | |
| 142 ci = ci_; | |
| 143 ci->offset = vi - m_array.values; | |
| 144 } | |
| 145 | |
| 146 ci->mask |= 1UL << (SIZEOF_CHUNK - 1 - (v.first % SIZEOF_CHUNK)); | |
| 147 *vi = v.second; | |
| 148 } | |
| 149 } | |
| 150 | |
| 151 | |
| 152 inline | |
| 153 sparse::operator bool () const throw() | |
| 154 { | |
| 155 return m_array.map != 0; | |
| 156 } | |
| 157 | |
| 158 inline | |
| 159 size_t sparse::size() const throw() | |
| 160 { | |
| 161 return m_nchunks*SIZEOF_CHUNK; | |
| 162 } | |
| 163 | |
| 164 inline | |
| 165 size_t sparse::_sizeof() const throw() | |
| 166 { | |
| 167 return sizeof(sparse) + capacity()*sizeof(mapped_type) + m_nchunks*sizeof(chunk); | |
| 168 } | |
| 169 | |
| 170 } // namespace graphite2 |
