1.1 --- /dev/null Thu Jan 01 00:00:00 1970 +0000
1.2 +++ b/gfx/graphite2/src/inc/Sparse.h Wed Dec 31 06:09:35 2014 +0100
1.3 @@ -0,0 +1,170 @@
1.4 +/* GRAPHITE2 LICENSING
1.5 +
1.6 + Copyright 2011, 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 +#pragma once
1.31 +#include <iterator>
1.32 +#include <utility>
1.33 +
1.34 +#include "inc/Main.h"
1.35 +
1.36 +namespace graphite2 {
1.37 +
1.38 +
1.39 +// A read-only packed fast sparse array of uint16 with uint16 keys.
1.40 +// Like most container classes this has capacity and size properties and these
1.41 +// refer to the number of stored entries and the number of addressable entries
1.42 +// as normal. However due the sparse nature the capacity is always <= than the
1.43 +// size.
1.44 +class sparse
1.45 +{
1.46 +public:
1.47 + typedef uint16 key_type;
1.48 + typedef uint16 mapped_type;
1.49 + typedef std::pair<const key_type, mapped_type> value_type;
1.50 +
1.51 +private:
1.52 + typedef unsigned long mask_t;
1.53 +
1.54 + static const unsigned char SIZEOF_CHUNK = (sizeof(mask_t) - sizeof(key_type))*8;
1.55 +
1.56 + struct chunk
1.57 + {
1.58 + mask_t mask:SIZEOF_CHUNK;
1.59 + key_type offset;
1.60 + };
1.61 +
1.62 + static chunk empty_chunk;
1.63 + sparse(const sparse &);
1.64 + sparse & operator = (const sparse &);
1.65 +
1.66 +public:
1.67 + template<typename I>
1.68 + sparse(I first, const I last);
1.69 + sparse() throw();
1.70 + ~sparse() throw();
1.71 +
1.72 + operator bool () const throw();
1.73 + mapped_type operator [] (const key_type k) const throw();
1.74 +
1.75 + size_t capacity() const throw();
1.76 + size_t size() const throw();
1.77 +
1.78 + size_t _sizeof() const throw();
1.79 +
1.80 + CLASS_NEW_DELETE;
1.81 +
1.82 +private:
1.83 + union {
1.84 + chunk * map;
1.85 + mapped_type * values;
1.86 + } m_array;
1.87 + key_type m_nchunks;
1.88 +};
1.89 +
1.90 +
1.91 +inline
1.92 +sparse::sparse() throw() : m_nchunks(0)
1.93 +{
1.94 + m_array.map = &empty_chunk;
1.95 +}
1.96 +
1.97 +
1.98 +template <typename I>
1.99 +sparse::sparse(I attr, const I last)
1.100 +: m_nchunks(0)
1.101 +{
1.102 + m_array.map = 0;
1.103 +
1.104 + // Find the maximum extent of the key space.
1.105 + size_t n_values=0;
1.106 + long lastkey = -1;
1.107 + for (I i = attr; i != last; ++i, ++n_values)
1.108 + {
1.109 + const typename std::iterator_traits<I>::value_type v = *i;
1.110 + if (v.second == 0) { --n_values; continue; }
1.111 + if (v.first <= lastkey) { m_nchunks = 0; return; }
1.112 +
1.113 + lastkey = v.first;
1.114 + const key_type k = v.first / SIZEOF_CHUNK;
1.115 + if (k >= m_nchunks) m_nchunks = k+1;
1.116 + }
1.117 + if (m_nchunks == 0)
1.118 + {
1.119 + m_array.map=&empty_chunk;
1.120 + return;
1.121 + }
1.122 +
1.123 + m_array.values = grzeroalloc<mapped_type>((m_nchunks*sizeof(chunk) + sizeof(mapped_type)-1)
1.124 + / sizeof(mapped_type)
1.125 + + n_values);
1.126 +
1.127 + if (m_array.values == 0)
1.128 + {
1.129 + free(m_array.values); m_array.map=0;
1.130 + return;
1.131 + }
1.132 +
1.133 + chunk * ci = m_array.map;
1.134 + ci->offset = (m_nchunks*sizeof(chunk) + sizeof(mapped_type)-1)/sizeof(mapped_type);
1.135 + mapped_type * vi = m_array.values + ci->offset;
1.136 + for (; attr != last; ++attr, ++vi)
1.137 + {
1.138 + const typename std::iterator_traits<I>::value_type v = *attr;
1.139 + if (v.second == 0) { --vi; continue; }
1.140 +
1.141 + chunk * const ci_ = m_array.map + v.first/SIZEOF_CHUNK;
1.142 +
1.143 + if (ci != ci_)
1.144 + {
1.145 + ci = ci_;
1.146 + ci->offset = vi - m_array.values;
1.147 + }
1.148 +
1.149 + ci->mask |= 1UL << (SIZEOF_CHUNK - 1 - (v.first % SIZEOF_CHUNK));
1.150 + *vi = v.second;
1.151 + }
1.152 +}
1.153 +
1.154 +
1.155 +inline
1.156 +sparse::operator bool () const throw()
1.157 +{
1.158 + return m_array.map != 0;
1.159 +}
1.160 +
1.161 +inline
1.162 +size_t sparse::size() const throw()
1.163 +{
1.164 + return m_nchunks*SIZEOF_CHUNK;
1.165 +}
1.166 +
1.167 +inline
1.168 +size_t sparse::_sizeof() const throw()
1.169 +{
1.170 + return sizeof(sparse) + capacity()*sizeof(mapped_type) + m_nchunks*sizeof(chunk);
1.171 +}
1.172 +
1.173 +} // namespace graphite2
