| 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 |