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)  

hb-map.hh
Go to the documentation of this file.
1 /*
2  * Copyright © 2018 Google, Inc.
3  *
4  * This is part of HarfBuzz, a text shaping library.
5  *
6  * Permission is hereby granted, without written agreement and without
7  * license or royalty fees, to use, copy, modify, and distribute this
8  * software and its documentation for any purpose, provided that the
9  * above copyright notice and the following two paragraphs appear in
10  * all copies of this software.
11  *
12  * IN NO EVENT SHALL THE COPYRIGHT HOLDER BE LIABLE TO ANY PARTY FOR
13  * DIRECT, INDIRECT, SPECIAL, INCIDENTAL, OR CONSEQUENTIAL DAMAGES
14  * ARISING OUT OF THE USE OF THIS SOFTWARE AND ITS DOCUMENTATION, EVEN
15  * IF THE COPYRIGHT HOLDER HAS BEEN ADVISED OF THE POSSIBILITY OF SUCH
16  * DAMAGE.
17  *
18  * THE COPYRIGHT HOLDER SPECIFICALLY DISCLAIMS ANY WARRANTIES, INCLUDING,
19  * BUT NOT LIMITED TO, THE IMPLIED WARRANTIES OF MERCHANTABILITY AND
20  * FITNESS FOR A PARTICULAR PURPOSE. THE SOFTWARE PROVIDED HEREUNDER IS
21  * ON AN "AS IS" BASIS, AND THE COPYRIGHT HOLDER HAS NO OBLIGATION TO
22  * PROVIDE MAINTENANCE, SUPPORT, UPDATES, ENHANCEMENTS, OR MODIFICATIONS.
23  *
24  * Google Author(s): Behdad Esfahbod
25  */
26 
27 #ifndef HB_MAP_HH
28 #define HB_MAP_HH
29 
30 #include "hb.hh"
31 
32 
33 /*
34  * hb_hashmap_t
35  */
36 
37 template <typename K, typename V,
38  K kINVALID = hb_is_pointer (K) ? 0 : hb_is_signed (K) ? hb_int_min (K) : (K) -1,
39  V vINVALID = hb_is_pointer (V) ? 0 : hb_is_signed (V) ? hb_int_min (V) : (V) -1>
40 struct hb_hashmap_t
41 {
43  hb_hashmap_t () { init (); }
44  ~hb_hashmap_t () { fini (); }
45 
48 
49  struct item_t
50  {
51  K key;
52  V value;
53  uint32_t hash;
54 
55  void clear () { key = kINVALID; value = vINVALID; hash = 0; }
56 
57  bool operator == (const K &o) { return hb_deref (key) == hb_deref (o); }
58  bool operator == (const item_t &o) { return *this == o.key; }
59  bool is_unused () const { return key == kINVALID; }
60  bool is_tombstone () const { return key != kINVALID && value == vINVALID; }
61  bool is_real () const { return key != kINVALID && value != vINVALID; }
63  };
64 
66  bool successful; /* Allocations successful */
67  unsigned int population; /* Not including tombstones. */
68  unsigned int occupancy; /* Including tombstones. */
69  unsigned int mask;
70  unsigned int prime;
71  item_t *items;
72 
73  void init_shallow ()
74  {
75  successful = true;
76  population = occupancy = 0;
77  mask = 0;
78  prime = 0;
79  items = nullptr;
80  }
81  void init ()
82  {
83  hb_object_init (this);
84  init_shallow ();
85  }
86  void fini_shallow ()
87  {
88  free (items);
89  items = nullptr;
90  population = occupancy = 0;
91  }
92  void fini ()
93  {
94  hb_object_fini (this);
95  fini_shallow ();
96  }
97 
98  void reset ()
99  {
100  if (unlikely (hb_object_is_immutable (this)))
101  return;
102  successful = true;
103  clear ();
104  }
105 
106  bool in_error () const { return !successful; }
107 
108  bool resize ()
109  {
110  if (unlikely (!successful)) return false;
111 
112  unsigned int power = hb_bit_storage (population * 2 + 8);
113  unsigned int new_size = 1u << power;
114  item_t *new_items = (item_t *) malloc ((size_t) new_size * sizeof (item_t));
115  if (unlikely (!new_items))
116  {
117  successful = false;
118  return false;
119  }
120  for (auto &_ : hb_iter (new_items, new_size))
121  _.clear ();
122 
123  unsigned int old_size = mask + 1;
124  item_t *old_items = items;
125 
126  /* Switch to new, empty, array. */
127  population = occupancy = 0;
128  mask = new_size - 1;
129  prime = prime_for (power);
130  items = new_items;
131 
132  /* Insert back old items. */
133  if (old_items)
134  for (unsigned int i = 0; i < old_size; i++)
135  if (old_items[i].is_real ())
136  set_with_hash (old_items[i].key,
137  old_items[i].hash,
138  old_items[i].value);
139 
140  free (old_items);
141 
142  return true;
143  }
144 
145  void set (K key, V value)
146  {
147  set_with_hash (key, hb_hash (key), value);
148  }
149 
150  V get (K key) const
151  {
152  if (unlikely (!items)) return vINVALID;
153  unsigned int i = bucket_for (key);
154  return items[i].is_real () && items[i] == key ? items[i].value : vINVALID;
155  }
156 
157  void del (K key) { set (key, vINVALID); }
158 
159  /* Has interface. */
160  static constexpr V SENTINEL = vINVALID;
161  typedef V value_t;
162  value_t operator [] (K k) const { return get (k); }
163  bool has (K k, V *vp = nullptr) const
164  {
165  V v = (*this)[k];
166  if (vp) *vp = v;
167  return v != SENTINEL;
168  }
169  /* Projection. */
170  V operator () (K k) const { return get (k); }
171 
172  void clear ()
173  {
174  if (unlikely (hb_object_is_immutable (this)))
175  return;
176  if (items)
177  for (auto &_ : hb_iter (items, mask + 1))
178  _.clear ();
179 
180  population = occupancy = 0;
181  }
182 
183  bool is_empty () const { return population == 0; }
184 
185  unsigned int get_population () const { return population; }
186 
187  /*
188  * Iterator
189  */
191  (
192  + hb_array (items, mask ? mask + 1 : 0)
193  | hb_filter (&item_t::is_real)
194  | hb_map (&item_t::get_pair)
195  )
197  (
198  + hb_array (items, mask ? mask + 1 : 0)
199  | hb_filter (&item_t::is_real)
200  | hb_map (&item_t::key)
201  | hb_map (hb_ridentity)
202  )
204  (
205  + hb_array (items, mask ? mask + 1 : 0)
206  | hb_filter (&item_t::is_real)
207  | hb_map (&item_t::value)
208  | hb_map (hb_ridentity)
209  )
210 
211  /* Sink interface. */
213  { set (v.first, v.second); return *this; }
214 
215  protected:
216 
218  {
219  if (unlikely (!successful)) return;
220  if (unlikely (key == kINVALID)) return;
221  if ((occupancy + occupancy / 2) >= mask && !resize ()) return;
222  unsigned int i = bucket_for_hash (key, hash);
223 
224  if (value == vINVALID && items[i].key != key)
225  return; /* Trying to delete non-existent key. */
226 
227  if (!items[i].is_unused ())
228  {
229  occupancy--;
230  if (items[i].is_tombstone ())
231  population--;
232  }
233 
234  items[i].key = key;
235  items[i].value = value;
236  items[i].hash = hash;
237 
238  occupancy++;
239  if (!items[i].is_tombstone ())
240  population++;
241  }
242 
243  unsigned int bucket_for (K key) const
244  {
245  return bucket_for_hash (key, hb_hash (key));
246  }
247 
248  unsigned int bucket_for_hash (K key, uint32_t hash) const
249  {
250  unsigned int i = hash % prime;
251  unsigned int step = 0;
252  unsigned int tombstone = (unsigned) -1;
253  while (!items[i].is_unused ())
254  {
255  if (items[i].hash == hash && items[i] == key)
256  return i;
257  if (tombstone == (unsigned) -1 && items[i].is_tombstone ())
258  tombstone = i;
259  i = (i + ++step) & mask;
260  }
261  return tombstone == (unsigned) -1 ? i : tombstone;
262  }
263 
264  static unsigned int prime_for (unsigned int shift)
265  {
266  /* Following comment and table copied from glib. */
267  /* Each table size has an associated prime modulo (the first prime
268  * lower than the table size) used to find the initial bucket. Probing
269  * then works modulo 2^n. The prime modulo is necessary to get a
270  * good distribution with poor hash functions.
271  */
272  /* Not declaring static to make all kinds of compilers happy... */
273  /*static*/ const unsigned int prime_mod [32] =
274  {
275  1, /* For 1 << 0 */
276  2,
277  3,
278  7,
279  13,
280  31,
281  61,
282  127,
283  251,
284  509,
285  1021,
286  2039,
287  4093,
288  8191,
289  16381,
290  32749,
291  65521, /* For 1 << 16 */
292  131071,
293  262139,
294  524287,
295  1048573,
296  2097143,
297  4194301,
298  8388593,
299  16777213,
300  33554393,
301  67108859,
302  134217689,
303  268435399,
304  536870909,
305  1073741789,
306  2147483647 /* For 1 << 31 */
307  };
308 
309  if (unlikely (shift >= ARRAY_LENGTH (prime_mod)))
310  return prime_mod[ARRAY_LENGTH (prime_mod) - 1];
311 
312  return prime_mod[shift];
313  }
314 };
315 
316 /*
317  * hb_map_t
318  */
319 
324 
325 
326 #endif /* HB_MAP_HH */
static boolean prime(int x)
Definition: aptex-src.c:286
#define hash
Definition: aptex.h:388
static void step(struct edge *edge)
#define ARRAY_LENGTH(__array)
Definition: cairoint.h:137
#define static_assert(c, msg)
Definition: cff.cc:31
#define free(a)
Definition: decNumber.cpp:310
int v
Definition: dviconv.c:10
long power[32]
Definition: dvi2xx.h:609
#define shift
Definition: exp3.c:154
cmd_t K[128]
Definition: fmtutil.c:72
#define _(String)
Definition: ftxerr18.c:64
static void clear()
#define unlikely(x)
Definition: jbig2arith.cc:116
small capitals from c petite p scientific i
Definition: afcover.h:80
#define const
Definition: ftzconf.h:91
unsigned int uint32_t
Definition: stdint.h:80
union hdr header
Definition: pbmtomacp.c:291
#define malloc
Definition: alloca.c:91
union value value
Definition: obx.h:44
int k
Definition: otp-parser.c:70
#define V
Definition: pgmcrater.c:68
static int items
Definition: pgmtofs.c:86
set set set set set set set macro pixldst1 abits if abits op else op endif endm macro pixldst2 abits if abits op else op endif endm macro pixldst4 abits if abits op else op endif endm macro pixldst0 abits op endm macro pixldst3 mem_operand op endm macro pixldst30 mem_operand op endm macro pixldst abits if abits elseif abits elseif abits elseif abits elseif abits pixldst0 abits else pixldst0 abits pixldst0 abits pixldst0 abits pixldst0 abits endif elseif abits else pixldst0 abits pixldst0 abits endif elseif abits else error unsupported bpp *numpix else pixst endif endm macro pixld1_s mem_operand if asr adds SRC_WIDTH_FIXED bpl add asl mov asr adds SRC_WIDTH_FIXED bpl add asl mov asr adds SRC_WIDTH_FIXED bpl add asl mov asr adds SRC_WIDTH_FIXED bpl add asl elseif asr adds SRC_WIDTH_FIXED bpl add asl mov asr adds SRC_WIDTH_FIXED bpl add asl else error unsupported endif endm macro pixld2_s mem_operand if mov asr add asl add asl mov asr sub UNIT_X add asl mov asr add asl add asl mov asr add UNIT_X add asl else pixld1_s mem_operand pixld1_s mem_operand endif endm macro pixld0_s mem_operand if asr adds SRC_WIDTH_FIXED bpl add asl elseif asr adds SRC_WIDTH_FIXED bpl add asl endif endm macro pixld_s_internal mem_operand if mem_operand pixld2_s mem_operand pixdeinterleave basereg elseif mem_operand elseif mem_operand elseif mem_operand elseif mem_operand pixld0_s mem_operand else pixld0_s mem_operand pixld0_s mem_operand pixld0_s mem_operand pixld0_s mem_operand endif elseif mem_operand else pixld0_s mem_operand pixld0_s mem_operand endif elseif mem_operand else error unsupported mem_operand if bpp mem_operand endif endm macro vuzp8 reg2 vuzp d d &reg2 endm macro vzip8 reg2 vzip d d &reg2 endm macro pixdeinterleave basereg basereg basereg basereg basereg endif endm macro pixinterleave basereg basereg basereg basereg basereg endif endm macro PF boost_increment endif if endif PF tst PF addne PF subne PF cmp ORIG_W if endif if endif if endif PF subge ORIG_W PF subges if endif if endif if endif endif endm macro cache_preload_simple endif if dst_r_bpp pld[DST_R, #(PREFETCH_DISTANCE_SIMPLE *dst_r_bpp/8)] endif if mask_bpp pld init[MASK, #(PREFETCH_DISTANCE_SIMPLE *mask_bpp/8)] endif endif endm macro fetch_mask_pixblock pixld mask_basereg pixblock_size MASK endm macro ensure_destination_ptr_alignment process_pixblock_tail_head if beq irp skip1 beq endif SRC MASK if dst_r_bpp DST_R else add endif PF add sub src_basereg pixdeinterleave mask_basereg pixdeinterleave dst_r_basereg process_pixblock_head pixblock_size cache_preload_simple process_pixblock_tail pixinterleave dst_w_basereg irp beq endif process_pixblock_tail_head tst beq irp if pixblock_size chunk_size tst beq pixld_src SRC pixld MASK if DST_R else pixld DST_R endif if src_basereg pixdeinterleave mask_basereg pixdeinterleave dst_r_basereg process_pixblock_head if pixblock_size cache_preload_simple endif process_pixblock_tail pixinterleave dst_w_basereg irp if pixblock_size chunk_size tst beq if DST_W else pixst DST_W else mov ORIG_W endif add lsl if lsl endif if lsl endif lsl endif lsl endif lsl endif subs mov DST_W if regs_shortage str endif bge start_of_loop_label endm macro generate_composite_function
struct @1017 hb_hash
static unsigned int hb_bit_storage(T v)
Definition: hb-algs.hh:420
struct @1015 hb_ridentity
hb_array_t< T > hb_array(T *array, unsigned int length)
Definition: hb-array.hh:263
uint32_t hb_codepoint_t
Definition: hb-common.h:106
struct @1039 hb_iter
struct @1044 hb_filter
struct @1041 hb_map
struct hb_map_t hb_map_t
Definition: hb-map.h:50
#define HB_MAP_VALUE_INVALID
Definition: hb-map.h:42
#define hb_int_min(T)
Definition: hb-meta.hh:279
struct @1061 hb_deref
#define hb_is_signed(T)
Definition: hb-meta.hh:260
#define hb_is_pointer(T)
Definition: hb-meta.hh:122
#define HB_AUTO_RETURN(E)
Definition: hb-meta.hh:68
hb_conditional< hb_is_arithmetic< T >::value, hb_bool_constant<(T) -1<(T) 0 >, hb_false_type > hb_is_signed
Definition: hb-meta.hh:259
static void hb_object_fini(Type *obj)
Definition: hb-object.hh:287
static bool hb_object_is_immutable(const Type *obj)
Definition: hb-object.hh:254
static void hb_object_init(Type *obj)
Definition: hb-object.hh:237
#define HB_DELETE_COPY_ASSIGN(TypeName)
Definition: hb.hh:462
static void resize(lua_State *L, Table *t, int nasize, int nhsize)
Definition: minilua.c:1513
#define mask(n)
Definition: lbitlib.c:93
static int get(const char **sp)
Definition: sscanffuns.c:91
bool operator==(const String &a, const String &b)
Compares two strings for equality.
Definition: string.hh:739
bool is_real() const
Definition: hb-map.hh:61
bool is_tombstone() const
Definition: hb-map.hh:60
hb_pair_t< K, V > get_pair() const
Definition: hb-map.hh:62
bool is_unused() const
Definition: hb-map.hh:59
void init_shallow()
Definition: hb-map.hh:73
hb_hashmap_t()
Definition: hb-map.hh:43
void set(K key, V value)
Definition: hb-map.hh:145
void init()
Definition: hb-map.hh:81
void reset()
Definition: hb-map.hh:98
V get(K key) const
Definition: hb-map.hh:150
bool in_error() const
Definition: hb-map.hh:106
unsigned int bucket_for_hash(K key, uint32_t hash) const
Definition: hb-map.hh:248
void del(K key)
Definition: hb-map.hh:157
unsigned int bucket_for(K key) const
Definition: hb-map.hh:243
auto iter() const -> decltype((+hb_array(items, mask ? mask+1 :0)|hb_filter(&item_t::is_real)|hb_map(&item_t::get_pair)))
Definition: hb-map.hh:190
bool is_empty() const
Definition: hb-map.hh:183
unsigned int get_population() const
Definition: hb-map.hh:185
void fini_shallow()
Definition: hb-map.hh:86
bool resize()
Definition: hb-map.hh:108
~hb_hashmap_t()
Definition: hb-map.hh:44
bool has(K k, V *vp=nullptr) const
Definition: hb-map.hh:163
static unsigned int prime_for(unsigned int shift)
Definition: hb-map.hh:264
void clear()
Definition: hb-map.hh:172
void fini()
Definition: hb-map.hh:92
void set_with_hash(K key, uint32_t hash, V value)
Definition: hb-map.hh:217
Definition: psspecial.c:52
Definition: epdf.c:232
#define key
Definition: tex2xindy.c:753
Definition: obx.h:51
static void new_size(int size, int block)
Definition: gc.c:702