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
sparse()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>
sparse(I attr,const I last)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
throw()151 sparse::operator bool () const throw()
152 {
153 return m_array.map != 0;
154 }
155
156 inline
size()157 size_t sparse::size() const throw()
158 {
159 return m_nchunks*SIZEOF_CHUNK;
160 }
161
162 inline
_sizeof()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
169