Debian Codegraph @

src/inc/Sparse.h

raw
1 // SPDX-License-Identifier: MIT OR MPL-2.0 OR LGPL-2.1-or-later OR GPL-2.0-or-later
2 // Copyright 2011, SIL International, All rights reserved.
3
4 #pragma once
5 #include <iterator>
6 #include <utility>
7
8 #include "inc/Main.h"
9
10 namespace graphite2 {
11
12
13 // A read-only packed fast sparse array of uint16 with uint16 keys.
14 // Like most container classes this has capacity and size properties and these
15 // refer to the number of stored entries and the number of addressable entries
16 // as normal. However due the sparse nature the capacity is always <= than the
17 // size.
18 class sparse
19 {
20 public:
21 typedef uint16 key_type;
22 typedef uint16 mapped_type;
23 typedef std::pair<const key_type, mapped_type> value_type;
24
25 private:
26 typedef unsigned long mask_t;
27
28 static const unsigned char SIZEOF_CHUNK = (sizeof(mask_t) - sizeof(key_type))*8;
29
30 struct chunk
31 {
32 mask_t mask:SIZEOF_CHUNK;
33 key_type offset;
34 };
35
36 static const chunk empty_chunk;
37 sparse(const sparse &);
38 sparse & operator = (const sparse &);
39
40 public:
41 template<typename I>
42 sparse(I first, const I last);
43 sparse() throw();
44 ~sparse() throw();
45
46 operator bool () const throw();
47 mapped_type operator [] (const key_type k) const throw();
48
49 size_t capacity() const throw();
50 size_t size() const throw();
51
52 size_t _sizeof() const throw();
53
54 CLASS_NEW_DELETE;
55
56 private:
57 union {
58 chunk * map;
59 mapped_type * values;
60 } m_array;
61 key_type m_nchunks;
62 };
63
64
65 inline
66 sparse::sparse() throw() : m_nchunks(0)
67 {
68 m_array.map = const_cast<graphite2::sparse::chunk *>(&empty_chunk);
69 }
70
71
72 template <typename I>
73 sparse::sparse(I attr, const I last)
74 : m_nchunks(0)
75 {
76 m_array.map = 0;
77
78 // Find the maximum extent of the key space.
79 size_t n_values=0;
80 long lastkey = -1;
81 for (I i = attr; i != last; ++i, ++n_values)
82 {
83 const typename std::iterator_traits<I>::value_type v = *i;
84 if (v.second == 0) { --n_values; continue; }
85 if (v.first <= lastkey) { m_nchunks = 0; return; }
86
87 lastkey = v.first;
88 const key_type k = v.first / SIZEOF_CHUNK;
89 if (k >= m_nchunks) m_nchunks = k+1;
90 }
91 if (m_nchunks == 0)
92 {
93 m_array.map=const_cast<graphite2::sparse::chunk *>(&empty_chunk);
94 return;
95 }
96
97 m_array.values = grzeroalloc<mapped_type>((m_nchunks*sizeof(chunk) + sizeof(mapped_type)-1)
98 / sizeof(mapped_type)
99 + n_values);
100
101 if (m_array.values == 0)
102 return;
103
104 // coverity[forward_null : FALSE] Since m_array is union and m_array.values is not NULL
105 chunk * ci = m_array.map;
106 ci->offset = (m_nchunks*sizeof(chunk) + sizeof(mapped_type)-1)/sizeof(mapped_type);
107 mapped_type * vi = m_array.values + ci->offset;
108 for (; attr != last; ++attr, ++vi)
109 {
110 const typename std::iterator_traits<I>::value_type v = *attr;
111 if (v.second == 0) { --vi; continue; }
112
113 chunk * const ci_ = m_array.map + v.first/SIZEOF_CHUNK;
114
115 if (ci != ci_)
116 {
117 ci = ci_;
118 ci->offset = key_type(vi - m_array.values);
119 }
120
121 ci->mask |= 1UL << (SIZEOF_CHUNK - 1 - (v.first % SIZEOF_CHUNK));
122 *vi = v.second;
123 }
124 }
125
126
127 inline
128 sparse::operator bool () const throw()
129 {
130 return m_array.map != 0;
131 }
132
133 inline
134 size_t sparse::size() const throw()
135 {
136 return m_nchunks*SIZEOF_CHUNK;
137 }
138
139 inline
140 size_t sparse::_sizeof() const throw()
141 {
142 return sizeof(sparse) + capacity()*sizeof(mapped_type) + m_nchunks*sizeof(chunk);
143 }
144
145 } // namespace graphite2