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
10namespace 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.
18class sparse
19{
20public:
21 typedef uint16 key_type;
22 typedef uint16 mapped_type;
23 typedef std::pair<const key_type, mapped_type> value_type;
24
25private:
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
40public:
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
56private:
57 union {
58 chunk * map;
59 mapped_type * values;
60 } m_array;
61 key_type m_nchunks;
62};
63
64
65inline
66sparse::sparse() throw() : m_nchunks(0)
67{
68 m_array.map = const_cast<graphite2::sparse::chunk *>(&empty_chunk);
69}
70
71
72template <typename I>
73sparse::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
127inline
128sparse::operator bool () const throw()
129{
130 return m_array.map != 0;
131}
132
133inline
134size_t sparse::size() const throw()
135{
136 return m_nchunks*SIZEOF_CHUNK;
137}
138
139inline
140size_t sparse::_sizeof() const throw()
141{
142 return sizeof(sparse) + capacity()*sizeof(mapped_type) + m_nchunks*sizeof(chunk);
143}
144
145} // namespace graphite2
146