w32tex
About: TeX Live provides a comprehensive TeX system including all the major TeX-related programs, macro packages, and fonts that are free software. Windows sources.
  Fossies Dox: w32tex-src.tar.xz  ("unofficial" and yet experimental doxygen-generated source code documentation)  

Sparse.h
Go to the documentation of this file.
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;
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  {
57  };
58 
59  static const chunk empty_chunk;
60  sparse(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();
71 
72  size_t capacity() const throw();
73  size_t size() const throw();
74 
75  size_t _sizeof() const throw();
76 
78 
79 private:
80  union {
81  chunk * map;
85 };
86 
87 
88 inline
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>
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
151 sparse::operator bool () const throw()
152 {
153  return m_array.map != 0;
154 }
155 
156 inline
157 size_t sparse::size() const throw()
158 {
159  return m_nchunks*SIZEOF_CHUNK;
160 }
161 
162 inline
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
#define bool
Definition: autosp.c:101
mapped_type * values
Definition: Sparse.h:82
union graphite2::sparse::@989 m_array
static const chunk empty_chunk
Definition: Sparse.h:59
size_t _sizeof() const
Definition: Sparse.h:163
key_type m_nchunks
Definition: Sparse.h:84
unsigned long mask_t
Definition: Sparse.h:49
size_t size() const
Definition: Sparse.h:157
std::pair< const key_type, mapped_type > value_type
Definition: Sparse.h:46
sparse & operator=(const sparse &)
sparse(I first, const I last)
chunk * map
Definition: Sparse.h:81
static const unsigned char SIZEOF_CHUNK
Definition: Sparse.h:51
uint16 key_type
Definition: Sparse.h:44
size_t capacity() const
Definition: Sparse.cpp:53
uint16 mapped_type
Definition: Sparse.h:45
sparse(const sparse &)
int v
Definition: dviconv.c:10
small capitals from c petite p scientific i
Definition: afcover.h:80
#define I(x, y, z)
Definition: md5.c:55
#define const
Definition: ftzconf.h:91
Definition: bits.h:30
gr_uint16 uint16
Definition: Main.h:40
int k
Definition: otp-parser.c:70
static int32_t last
Definition: ppagelist.c:29
static int32_t first
Definition: ppagelist.c:29
static void chunk(LexState *ls)
Definition: minilua.c:4678
Definition: epdf.c:232
Definition: psfont.h:67