Line data Source code
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 0 : sparse::sparse() throw() : m_nchunks(0)
90 : {
91 0 : m_array.map = const_cast<graphite2::sparse::chunk *>(&empty_chunk);
92 0 : }
93 :
94 :
95 : template <typename I>
96 0 : sparse::sparse(I attr, const I last)
97 0 : : m_nchunks(0)
98 : {
99 0 : m_array.map = 0;
100 :
101 : // Find the maximum extent of the key space.
102 0 : size_t n_values=0;
103 0 : long lastkey = -1;
104 0 : for (I i = attr; i != last; ++i, ++n_values)
105 : {
106 0 : const typename std::iterator_traits<I>::value_type v = *i;
107 0 : if (v.second == 0) { --n_values; continue; }
108 0 : if (v.first <= lastkey) { m_nchunks = 0; return; }
109 :
110 0 : lastkey = v.first;
111 0 : const key_type k = v.first / SIZEOF_CHUNK;
112 0 : if (k >= m_nchunks) m_nchunks = k+1;
113 : }
114 0 : if (m_nchunks == 0)
115 : {
116 0 : m_array.map=const_cast<graphite2::sparse::chunk *>(&empty_chunk);
117 0 : return;
118 : }
119 :
120 0 : m_array.values = grzeroalloc<mapped_type>((m_nchunks*sizeof(chunk) + sizeof(mapped_type)-1)
121 0 : / sizeof(mapped_type)
122 : + n_values);
123 :
124 0 : if (m_array.values == 0)
125 : {
126 0 : free(m_array.values); m_array.map=0;
127 0 : return;
128 : }
129 :
130 : // coverity[forward_null : FALSE] Since m_array is union and m_array.values is not NULL
131 0 : chunk * ci = m_array.map;
132 0 : ci->offset = (m_nchunks*sizeof(chunk) + sizeof(mapped_type)-1)/sizeof(mapped_type);
133 0 : mapped_type * vi = m_array.values + ci->offset;
134 0 : for (; attr != last; ++attr, ++vi)
135 : {
136 0 : const typename std::iterator_traits<I>::value_type v = *attr;
137 0 : if (v.second == 0) { --vi; continue; }
138 :
139 0 : chunk * const ci_ = m_array.map + v.first/SIZEOF_CHUNK;
140 :
141 0 : if (ci != ci_)
142 : {
143 0 : ci = ci_;
144 0 : ci->offset = vi - m_array.values;
145 : }
146 :
147 0 : ci->mask |= 1UL << (SIZEOF_CHUNK - 1 - (v.first % SIZEOF_CHUNK));
148 0 : *vi = v.second;
149 : }
150 : }
151 :
152 :
153 : inline
154 0 : sparse::operator bool () const throw()
155 : {
156 0 : return m_array.map != 0;
157 : }
158 :
159 : inline
160 : size_t sparse::size() const throw()
161 : {
162 : return m_nchunks*SIZEOF_CHUNK;
163 : }
164 :
165 : inline
166 : size_t sparse::_sizeof() const throw()
167 : {
168 : return sizeof(sparse) + capacity()*sizeof(mapped_type) + m_nchunks*sizeof(chunk);
169 : }
170 :
171 : } // namespace graphite2
|
