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-set.hh
Go to the documentation of this file.
1 /*
2  * Copyright © 2012,2017 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_SET_HH
28 #define HB_SET_HH
29 
30 #include "hb.hh"
31 #include "hb-machinery.hh"
32 
33 
34 /*
35  * hb_set_t
36  */
37 
38 /* TODO Keep a free-list so we can free pages that are completely zeroed. At that
39  * point maybe also use a sentinel value for "all-1" pages? */
40 
41 struct hb_set_t
42 {
44  hb_set_t () { init (); }
45  ~hb_set_t () { fini (); }
46 
47  struct page_map_t
48  {
49  int cmp (const page_map_t &o) const { return (int) o.major - (int) major; }
50 
53  };
54 
55  struct page_t
56  {
57  void init0 () { v.clear (); }
58  void init1 () { v.clear (0xFF); }
59 
60  unsigned int len () const
61  { return ARRAY_LENGTH_CONST (v); }
62 
63  bool is_empty () const
64  {
65  for (unsigned int i = 0; i < len (); i++)
66  if (v[i])
67  return false;
68  return true;
69  }
70 
71  void add (hb_codepoint_t g) { elt (g) |= mask (g); }
72  void del (hb_codepoint_t g) { elt (g) &= ~~mask (g); }
73  bool get (hb_codepoint_t g) const { return elt (g) & mask (g); }
74 
76  {
77  elt_t *la = &elt (a);
78  elt_t *lb = &elt (b);
79  if (la == lb)
80  *la |= (mask (b) << 1) - mask(a);
81  else
82  {
83  *la |= ~(mask (a) - 1);
84  la++;
85 
86  memset (la, 0xff, (char *) lb - (char *) la);
87 
88  *lb |= ((mask (b) << 1) - 1);
89  }
90  }
91 
93  {
94  elt_t *la = &elt (a);
95  elt_t *lb = &elt (b);
96  if (la == lb)
97  *la &= ~((mask (b) << 1) - mask(a));
98  else
99  {
100  *la &= mask (a) - 1;
101  la++;
102 
103  memset (la, 0, (char *) lb - (char *) la);
104 
105  *lb &= ~((mask (b) << 1) - 1);
106  }
107  }
108 
109  bool is_equal (const page_t *other) const
110  {
111  return 0 == hb_memcmp (&v, &other->v, sizeof (v));
112  }
113 
114  unsigned int get_population () const
115  {
116  unsigned int pop = 0;
117  for (unsigned int i = 0; i < len (); i++)
118  pop += hb_popcount (v[i]);
119  return pop;
120  }
121 
123  {
124  unsigned int m = (*codepoint + 1) & MASK;
125  if (!m)
126  {
127  *codepoint = INVALID;
128  return false;
129  }
130  unsigned int i = m / ELT_BITS;
131  unsigned int j = m & ELT_MASK;
132 
133  const elt_t vv = v[i] & ~((elt_t (1) << j) - 1);
134  for (const elt_t *p = &vv; i < len (); p = &v[++i])
135  if (*p)
136  {
137  *codepoint = i * ELT_BITS + elt_get_min (*p);
138  return true;
139  }
140 
141  *codepoint = INVALID;
142  return false;
143  }
145  {
146  unsigned int m = (*codepoint - 1) & MASK;
147  if (m == MASK)
148  {
149  *codepoint = INVALID;
150  return false;
151  }
152  unsigned int i = m / ELT_BITS;
153  unsigned int j = m & ELT_MASK;
154 
155  /* Fancy mask to avoid shifting by elt_t bitsize, which is undefined. */
156  const elt_t mask = j < 8 * sizeof (elt_t) - 1 ?
157  ((elt_t (1) << (j + 1)) - 1) :
158  (elt_t) -1;
159  const elt_t vv = v[i] & mask;
160  const elt_t *p = &vv;
161  while (true)
162  {
163  if (*p)
164  {
165  *codepoint = i * ELT_BITS + elt_get_max (*p);
166  return true;
167  }
168  if ((int) i <= 0) break;
169  p = &v[--i];
170  }
171 
172  *codepoint = INVALID;
173  return false;
174  }
176  {
177  for (unsigned int i = 0; i < len (); i++)
178  if (v[i])
179  return i * ELT_BITS + elt_get_min (v[i]);
180  return INVALID;
181  }
183  {
184  for (int i = len () - 1; i >= 0; i--)
185  if (v[i])
186  return i * ELT_BITS + elt_get_max (v[i]);
187  return 0;
188  }
189 
190  typedef unsigned long long elt_t;
191  static constexpr unsigned PAGE_BITS = 512;
192  static_assert ((PAGE_BITS & ((PAGE_BITS) - 1)) == 0, "");
193 
194  static unsigned int elt_get_min (const elt_t &elt) { return hb_ctz (elt); }
195  static unsigned int elt_get_max (const elt_t &elt) { return hb_bit_storage (elt) - 1; }
196 
198 
199  static constexpr unsigned ELT_BITS = sizeof (elt_t) * 8;
200  static constexpr unsigned ELT_MASK = ELT_BITS - 1;
201  static constexpr unsigned BITS = sizeof (vector_t) * 8;
202  static constexpr unsigned MASK = BITS - 1;
203  static_assert ((unsigned) PAGE_BITS == (unsigned) BITS, "");
204 
205  elt_t &elt (hb_codepoint_t g) { return v[(g & MASK) / ELT_BITS]; }
206  elt_t const &elt (hb_codepoint_t g) const { return v[(g & MASK) / ELT_BITS]; }
207  elt_t mask (hb_codepoint_t g) const { return elt_t (1) << (g & ELT_MASK); }
208 
209  vector_t v;
210  };
211  static_assert (page_t::PAGE_BITS == sizeof (page_t) * 8, "");
212 
214  bool successful; /* Allocations successful */
215  mutable unsigned int population;
218 
219  void init_shallow ()
220  {
221  successful = true;
222  population = 0;
223  page_map.init ();
224  pages.init ();
225  }
226  void init ()
227  {
228  hb_object_init (this);
229  init_shallow ();
230  }
231  void fini_shallow ()
232  {
233  population = 0;
234  page_map.fini ();
235  pages.fini ();
236  }
237  void fini ()
238  {
239  hb_object_fini (this);
240  fini_shallow ();
241  }
242 
243  bool in_error () const { return !successful; }
244 
245  bool resize (unsigned int count)
246  {
247  if (unlikely (!successful)) return false;
248  if (!pages.resize (count) || !page_map.resize (count))
249  {
250  pages.resize (page_map.length);
251  successful = false;
252  return false;
253  }
254  return true;
255  }
256 
257  void reset ()
258  {
259  if (unlikely (hb_object_is_immutable (this)))
260  return;
261  clear ();
262  successful = true;
263  }
264 
265  void clear ()
266  {
267  if (unlikely (hb_object_is_immutable (this)))
268  return;
269  population = 0;
270  page_map.resize (0);
271  pages.resize (0);
272  }
273  bool is_empty () const
274  {
275  unsigned int count = pages.length;
276  for (unsigned int i = 0; i < count; i++)
277  if (!pages[i].is_empty ())
278  return false;
279  return true;
280  }
281 
282  void dirty () { population = UINT_MAX; }
283 
285  {
286  if (unlikely (!successful)) return;
287  if (unlikely (g == INVALID)) return;
288  dirty ();
289  page_t *page = page_for_insert (g); if (unlikely (!page)) return;
290  page->add (g);
291  }
293  {
294  if (unlikely (!successful)) return true; /* https://github.com/harfbuzz/harfbuzz/issues/657 */
295  if (unlikely (a > b || a == INVALID || b == INVALID)) return false;
296  dirty ();
297  unsigned int ma = get_major (a);
298  unsigned int mb = get_major (b);
299  if (ma == mb)
300  {
301  page_t *page = page_for_insert (a); if (unlikely (!page)) return false;
302  page->add_range (a, b);
303  }
304  else
305  {
306  page_t *page = page_for_insert (a); if (unlikely (!page)) return false;
307  page->add_range (a, major_start (ma + 1) - 1);
308 
309  for (unsigned int m = ma + 1; m < mb; m++)
310  {
311  page = page_for_insert (major_start (m)); if (unlikely (!page)) return false;
312  page->init1 ();
313  }
314 
315  page = page_for_insert (b); if (unlikely (!page)) return false;
316  page->add_range (major_start (mb), b);
317  }
318  return true;
319  }
320 
321  template <typename T>
322  void add_array (const T *array, unsigned int count, unsigned int stride=sizeof(T))
323  {
324  if (unlikely (!successful)) return;
325  if (!count) return;
326  dirty ();
328  while (count)
329  {
330  unsigned int m = get_major (g);
331  page_t *page = page_for_insert (g); if (unlikely (!page)) return;
332  unsigned int start = major_start (m);
333  unsigned int end = major_start (m + 1);
334  do
335  {
336  page->add (g);
337 
338  array = &StructAtOffsetUnaligned<T> (array, stride);
339  count--;
340  }
341  while (count && (g = *array, start <= g && g < end));
342  }
343  }
344 
345  /* Might return false if array looks unsorted.
346  * Used for faster rejection of corrupt data. */
347  template <typename T>
348  bool add_sorted_array (const T *array, unsigned int count, unsigned int stride=sizeof(T))
349  {
350  if (unlikely (!successful)) return true; /* https://github.com/harfbuzz/harfbuzz/issues/657 */
351  if (!count) return true;
352  dirty ();
354  hb_codepoint_t last_g = g;
355  while (count)
356  {
357  unsigned int m = get_major (g);
358  page_t *page = page_for_insert (g); if (unlikely (!page)) return false;
359  unsigned int end = major_start (m + 1);
360  do
361  {
362  /* If we try harder we can change the following comparison to <=;
363  * Not sure if it's worth it. */
364  if (g < last_g) return false;
365  last_g = g;
366  page->add (g);
367 
368  array = (const T *) ((const char *) array + stride);
369  count--;
370  }
371  while (count && (g = *array, g < end));
372  }
373  return true;
374  }
375 
377  {
378  /* TODO perform op even if !successful. */
379  if (unlikely (!successful)) return;
380  page_t *page = page_for (g);
381  if (!page)
382  return;
383  dirty ();
384  page->del (g);
385  }
386 
387  private:
388  void del_pages (int ds, int de)
389  {
390  if (ds <= de)
391  {
392  unsigned int write_index = 0;
393  for (unsigned int i = 0; i < page_map.length; i++)
394  {
395  int m = (int) page_map[i].major;
396  if (m < ds || de < m)
397  page_map[write_index++] = page_map[i];
398  }
399  compact (write_index);
400  resize (write_index);
401  }
402  }
403 
404  public:
406  {
407  /* TODO perform op even if !successful. */
408  if (unlikely (!successful)) return;
409  if (unlikely (a > b || a == INVALID || b == INVALID)) return;
410  dirty ();
411  unsigned int ma = get_major (a);
412  unsigned int mb = get_major (b);
413  /* Delete pages from ds through de if ds <= de. */
414  int ds = (a == major_start (ma))? (int) ma: (int) (ma + 1);
415  int de = (b + 1 == major_start (mb + 1))? (int) mb: ((int) mb - 1);
416  if (ds > de || (int) ma < ds)
417  {
418  page_t *page = page_for (a);
419  if (page)
420  {
421  if (ma == mb)
422  page->del_range (a, b);
423  else
424  page->del_range (a, major_start (ma + 1) - 1);
425  }
426  }
427  if (de < (int) mb && ma != mb)
428  {
429  page_t *page = page_for (b);
430  if (page)
431  page->del_range (major_start (mb), b);
432  }
433  del_pages (ds, de);
434  }
435 
436  bool get (hb_codepoint_t g) const
437  {
438  const page_t *page = page_for (g);
439  if (!page)
440  return false;
441  return page->get (g);
442  }
443 
444  /* Has interface. */
445  static constexpr bool SENTINEL = false;
446  typedef bool value_t;
447  value_t operator [] (hb_codepoint_t k) const { return get (k); }
448  bool has (hb_codepoint_t k) const { return (*this)[k] != SENTINEL; }
449  /* Predicate. */
450  bool operator () (hb_codepoint_t k) const { return has (k); }
451 
452  /* Sink interface. */
454  { add (v); return *this; }
456  { add_range (range.first, range.second); return *this; }
457 
459  {
460  hb_codepoint_t c = first - 1;
461  return next (&c) && c <= last;
462  }
463  void set (const hb_set_t *other)
464  {
465  if (unlikely (!successful)) return;
466  unsigned int count = other->pages.length;
467  if (!resize (count))
468  return;
469  population = other->population;
470  memcpy ((void *) pages, (const void *) other->pages, count * pages.item_size);
471  memcpy ((void *) page_map, (const void *) other->page_map, count * page_map.item_size);
472  }
473 
474  bool is_equal (const hb_set_t *other) const
475  {
476  if (get_population () != other->get_population ())
477  return false;
478 
479  unsigned int na = pages.length;
480  unsigned int nb = other->pages.length;
481 
482  unsigned int a = 0, b = 0;
483  for (; a < na && b < nb; )
484  {
485  if (page_at (a).is_empty ()) { a++; continue; }
486  if (other->page_at (b).is_empty ()) { b++; continue; }
487  if (page_map[a].major != other->page_map[b].major ||
488  !page_at (a).is_equal (&other->page_at (b)))
489  return false;
490  a++;
491  b++;
492  }
493  for (; a < na; a++)
494  if (!page_at (a).is_empty ()) { return false; }
495  for (; b < nb; b++)
496  if (!other->page_at (b).is_empty ()) { return false; }
497 
498  return true;
499  }
500 
501  bool is_subset (const hb_set_t *larger_set) const
502  {
503  if (get_population () > larger_set->get_population ())
504  return false;
505 
506  /* TODO Optimize to use pages. */
508  while (next (&c))
509  if (!larger_set->has (c))
510  return false;
511 
512  return true;
513  }
514 
515  void compact (unsigned int length)
516  {
517  hb_vector_t<uint32_t> old_index_to_page_map_index;
518  old_index_to_page_map_index.resize(pages.length);
519  for (uint32_t i = 0; i < old_index_to_page_map_index.length; i++)
520  old_index_to_page_map_index[i] = 0xFFFFFFFF;
521 
522  for (uint32_t i = 0; i < length; i++)
523  old_index_to_page_map_index[page_map[i].index] = i;
524 
525  compact_pages (old_index_to_page_map_index);
526  }
527 
528  void compact_pages (const hb_vector_t<uint32_t>& old_index_to_page_map_index)
529  {
530  unsigned int write_index = 0;
531  for (unsigned int i = 0; i < pages.length; i++)
532  {
533  if (old_index_to_page_map_index[i] == 0xFFFFFFFF) continue;
534 
535  if (write_index < i)
536  pages[write_index] = pages[i];
537 
538  page_map[old_index_to_page_map_index[i]].index = write_index;
539  write_index++;
540  }
541  }
542 
543  template <typename Op>
544  void process (const Op& op, const hb_set_t *other)
545  {
546  if (unlikely (!successful)) return;
547 
548  dirty ();
549 
550  unsigned int na = pages.length;
551  unsigned int nb = other->pages.length;
552  unsigned int next_page = na;
553 
554  unsigned int count = 0, newCount = 0;
555  unsigned int a = 0, b = 0;
556  unsigned int write_index = 0;
557  for (; a < na && b < nb; )
558  {
559  if (page_map[a].major == other->page_map[b].major)
560  {
561  if (!Op::passthru_left)
562  {
563  // Move page_map entries that we're keeping from the left side set
564  // to the front of the page_map vector. This isn't necessary if
565  // passthru_left is set since no left side pages will be removed
566  // in that case.
567  if (write_index < a)
568  page_map[write_index] = page_map[a];
569  write_index++;
570  }
571 
572  count++;
573  a++;
574  b++;
575  }
576  else if (page_map[a].major < other->page_map[b].major)
577  {
578  if (Op::passthru_left)
579  count++;
580  a++;
581  }
582  else
583  {
584  if (Op::passthru_right)
585  count++;
586  b++;
587  }
588  }
589  if (Op::passthru_left)
590  count += na - a;
591  if (Op::passthru_right)
592  count += nb - b;
593 
594  if (!Op::passthru_left)
595  {
596  na = write_index;
597  next_page = write_index;
598  compact (write_index);
599  }
600 
601  if (!resize (count))
602  return;
603 
604  newCount = count;
605 
606  /* Process in-place backward. */
607  a = na;
608  b = nb;
609  for (; a && b; )
610  {
611  if (page_map[a - 1].major == other->page_map[b - 1].major)
612  {
613  a--;
614  b--;
615  count--;
616  page_map[count] = page_map[a];
617  page_at (count).v = op (page_at (a).v, other->page_at (b).v);
618  }
619  else if (page_map[a - 1].major > other->page_map[b - 1].major)
620  {
621  a--;
622  if (Op::passthru_left)
623  {
624  count--;
625  page_map[count] = page_map[a];
626  }
627  }
628  else
629  {
630  b--;
631  if (Op::passthru_right)
632  {
633  count--;
634  page_map[count].major = other->page_map[b].major;
635  page_map[count].index = next_page++;
636  page_at (count).v = other->page_at (b).v;
637  }
638  }
639  }
640  if (Op::passthru_left)
641  while (a)
642  {
643  a--;
644  count--;
645  page_map[count] = page_map [a];
646  }
647  if (Op::passthru_right)
648  while (b)
649  {
650  b--;
651  count--;
652  page_map[count].major = other->page_map[b].major;
653  page_map[count].index = next_page++;
654  page_at (count).v = other->page_at (b).v;
655  }
656  assert (!count);
657  if (pages.length > newCount)
658  resize (newCount);
659  }
660 
661  void union_ (const hb_set_t *other)
662  {
664  }
665  void intersect (const hb_set_t *other)
666  {
668  }
669  void subtract (const hb_set_t *other)
670  {
672  }
674  {
676  }
678  {
679  if (unlikely (*codepoint == INVALID)) {
680  *codepoint = get_min ();
681  return *codepoint != INVALID;
682  }
683 
684  page_map_t map = {get_major (*codepoint), 0};
685  unsigned int i;
687  if (i < page_map.length && page_map[i].major == map.major)
688  {
690  {
691  *codepoint += page_map[i].major * page_t::PAGE_BITS;
692  return true;
693  }
694  i++;
695  }
696  for (; i < page_map.length; i++)
697  {
698  hb_codepoint_t m = pages[page_map[i].index].get_min ();
699  if (m != INVALID)
700  {
701  *codepoint = page_map[i].major * page_t::PAGE_BITS + m;
702  return true;
703  }
704  }
705  *codepoint = INVALID;
706  return false;
707  }
709  {
710  if (unlikely (*codepoint == INVALID)) {
711  *codepoint = get_max ();
712  return *codepoint != INVALID;
713  }
714 
715  page_map_t map = {get_major (*codepoint), 0};
716  unsigned int i;
718  if (i < page_map.length && page_map[i].major == map.major)
719  {
721  {
722  *codepoint += page_map[i].major * page_t::PAGE_BITS;
723  return true;
724  }
725  }
726  i--;
727  for (; (int) i >= 0; i--)
728  {
729  hb_codepoint_t m = pages[page_map[i].index].get_max ();
730  if (m != INVALID)
731  {
732  *codepoint = page_map[i].major * page_t::PAGE_BITS + m;
733  return true;
734  }
735  }
736  *codepoint = INVALID;
737  return false;
738  }
740  {
742 
743  i = *last;
744  if (!next (&i))
745  {
746  *last = *first = INVALID;
747  return false;
748  }
749 
750  /* TODO Speed up. */
751  *last = *first = i;
752  while (next (&i) && i == *last + 1)
753  (*last)++;
754 
755  return true;
756  }
758  {
760 
761  i = *first;
762  if (!previous (&i))
763  {
764  *last = *first = INVALID;
765  return false;
766  }
767 
768  /* TODO Speed up. */
769  *last = *first = i;
770  while (previous (&i) && i == *first - 1)
771  (*first)--;
772 
773  return true;
774  }
775 
776  unsigned int get_population () const
777  {
778  if (population != UINT_MAX)
779  return population;
780 
781  unsigned int pop = 0;
782  unsigned int count = pages.length;
783  for (unsigned int i = 0; i < count; i++)
784  pop += pages[i].get_population ();
785 
786  population = pop;
787  return pop;
788  }
790  {
791  unsigned int count = pages.length;
792  for (unsigned int i = 0; i < count; i++)
793  if (!page_at (i).is_empty ())
794  return page_map[i].major * page_t::PAGE_BITS + page_at (i).get_min ();
795  return INVALID;
796  }
798  {
799  unsigned int count = pages.length;
800  for (int i = count - 1; i >= 0; i++)
801  if (!page_at (i).is_empty ())
802  return page_map[(unsigned) i].major * page_t::PAGE_BITS + page_at (i).get_max ();
803  return INVALID;
804  }
805 
806  static constexpr hb_codepoint_t INVALID = HB_SET_VALUE_INVALID;
807 
808  /*
809  * Iterator implementation.
810  */
811  struct iter_t : hb_iter_with_fallback_t<iter_t, hb_codepoint_t>
812  {
813  static constexpr bool is_sorted_iterator = true;
814  iter_t (const hb_set_t &s_ = Null (hb_set_t),
815  bool init = true) : s (&s_), v (INVALID), l(0)
816  {
817  if (init)
818  {
819  l = s->get_population () + 1;
820  __next__ ();
821  }
822  }
823 
825  hb_codepoint_t __item__ () const { return v; }
826  bool __more__ () const { return v != INVALID; }
827  void __next__ () { s->next (&v); if (l) l--; }
828  void __prev__ () { s->previous (&v); }
829  unsigned __len__ () const { return l; }
830  iter_t end () const { return iter_t (*s, false); }
831  bool operator != (const iter_t& o) const
832  { return s != o.s || v != o.v; }
833 
834  protected:
835  const hb_set_t *s;
837  unsigned l;
838  };
839  iter_t iter () const { return iter_t (*this); }
840  operator iter_t () const { return iter (); }
841 
842  protected:
843 
845  {
846  page_map_t map = {get_major (g), pages.length};
847  unsigned int i;
849  {
850  if (!resize (pages.length + 1))
851  return nullptr;
852 
853  pages[map.index].init0 ();
854  memmove (page_map + i + 1,
855  page_map + i,
856  (page_map.length - 1 - i) * page_map.item_size);
857  page_map[i] = map;
858  }
859  return &pages[page_map[i].index];
860  }
862  {
863  page_map_t key = {get_major (g)};
864  const page_map_t *found = page_map.bsearch (key);
865  if (found)
866  return &pages[found->index];
867  return nullptr;
868  }
870  {
871  page_map_t key = {get_major (g)};
872  const page_map_t *found = page_map.bsearch (key);
873  if (found)
874  return &pages[found->index];
875  return nullptr;
876  }
877  page_t &page_at (unsigned int i) { return pages[page_map[i].index]; }
878  const page_t &page_at (unsigned int i) const { return pages[page_map[i].index]; }
879  unsigned int get_major (hb_codepoint_t g) const { return g / page_t::PAGE_BITS; }
880  hb_codepoint_t major_start (unsigned int major) const { return major * page_t::PAGE_BITS; }
881 };
882 
883 
884 #endif /* HB_SET_HH */
#define count(a)
Definition: aptex-macros.h:781
static struct brw_reg stride(struct brw_reg reg, uint32_t vstride, uint32_t width, uint32_t hstride)
#define static_assert(c, msg)
Definition: cff.cc:31
#define b
Definition: jpegint.h:372
int v
Definition: dviconv.c:10
long vv
Definition: dvi2xx.h:581
#define T
Definition: fmt.h:20
#define c(n)
Definition: gpos-common.c:150
#define a(n)
Definition: gpos-common.c:148
#define memmove(d, s, n)
Definition: gsftopk.c:65
#define memcpy(d, s, n)
Definition: gsftopk.c:64
assert(pcxLoadImage24((char *)((void *) 0), fp, pinfo, hdr))
#define unlikely(x)
Definition: jbig2arith.cc:116
small capitals from c petite p
Definition: afcover.h:72
small capitals from c petite p scientific i
Definition: afcover.h:80
sizeof(AF_ModuleRec)
unsigned int uint32_t
Definition: stdint.h:80
int major
Definition: pdfcolor.c:526
#define UINT_MAX
Definition: c-minmax.h:56
#define length(c)
Definition: ctangleboot.c:65
@ other
Definition: mtxline.h:22
int k
Definition: otp-parser.c:70
integer nb
Definition: pmxab.c:180
static int32_t last
Definition: ppagelist.c:29
static int32_t first
Definition: ppagelist.c:29
int g
Definition: ppmqvga.c:68
bstring c int memset(void *s, int c, int length)
#define map
#define pop()
Definition: opcodes.h:78
static unsigned int hb_bit_storage(T v)
Definition: hb-algs.hh:420
static unsigned int hb_popcount(T v)
Definition: hb-algs.hh:379
static unsigned int hb_ctz(T v)
Definition: hb-algs.hh:494
#define ARRAY_LENGTH_CONST(__array)
Definition: hb-algs.hh:595
static int hb_memcmp(const void *a, const void *b, unsigned int len)
Definition: hb-algs.hh:599
@ HB_BFIND_NOT_FOUND_STORE_CLOSEST
Definition: hb-array.hh:273
uint32_t hb_codepoint_t
Definition: hb-common.h:106
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_SET_VALUE_INVALID
Definition: hb-set.h:42
#define HB_DELETE_COPY_ASSIGN(TypeName)
Definition: hb.hh:462
static int codepoint(lua_State *L)
Definition: lutf8lib.c:100
bool
Definition: hb-null.hh:81
void __next__()
Definition: hb-set.hh:827
const hb_set_t * s
Definition: hb-set.hh:835
bool __more__() const
Definition: hb-set.hh:826
hb_codepoint_t __item_t__
Definition: hb-set.hh:824
hb_codepoint_t v
Definition: hb-set.hh:836
unsigned __len__() const
Definition: hb-set.hh:829
static constexpr bool is_sorted_iterator
Definition: hb-set.hh:813
unsigned l
Definition: hb-set.hh:837
iter_t(const hb_set_t &s_=NullHelper< hb_set_t >::get_null(), bool init=true)
Definition: hb-set.hh:814
void __prev__()
Definition: hb-set.hh:828
hb_codepoint_t __item__() const
Definition: hb-set.hh:825
iter_t end() const
Definition: hb-set.hh:830
bool operator!=(const iter_t &o) const
Definition: hb-set.hh:831
uint32_t major
Definition: hb-set.hh:51
uint32_t index
Definition: hb-set.hh:52
int cmp(const page_map_t &o) const
Definition: hb-set.hh:49
bool is_empty() const
Definition: hb-set.hh:63
static unsigned int elt_get_min(const elt_t &elt)
Definition: hb-set.hh:194
elt_t mask(hb_codepoint_t g) const
Definition: hb-set.hh:207
hb_codepoint_t get_min() const
Definition: hb-set.hh:175
unsigned int get_population() const
Definition: hb-set.hh:114
void del_range(hb_codepoint_t a, hb_codepoint_t b)
Definition: hb-set.hh:92
hb_vector_size_t< elt_t, PAGE_BITS/8 > vector_t
Definition: hb-set.hh:197
unsigned long long elt_t
Definition: hb-set.hh:190
void del(hb_codepoint_t g)
Definition: hb-set.hh:72
static constexpr unsigned MASK
Definition: hb-set.hh:202
bool is_equal(const page_t *other) const
Definition: hb-set.hh:109
bool previous(hb_codepoint_t *codepoint) const
Definition: hb-set.hh:144
static constexpr unsigned PAGE_BITS
Definition: hb-set.hh:191
static constexpr unsigned ELT_BITS
Definition: hb-set.hh:199
bool get(hb_codepoint_t g) const
Definition: hb-set.hh:73
static constexpr unsigned ELT_MASK
Definition: hb-set.hh:200
vector_t v
Definition: hb-set.hh:209
elt_t const & elt(hb_codepoint_t g) const
Definition: hb-set.hh:206
void add(hb_codepoint_t g)
Definition: hb-set.hh:71
static constexpr unsigned BITS
Definition: hb-set.hh:201
void init0()
Definition: hb-set.hh:57
void init1()
Definition: hb-set.hh:58
void add_range(hb_codepoint_t a, hb_codepoint_t b)
Definition: hb-set.hh:75
hb_codepoint_t get_max() const
Definition: hb-set.hh:182
unsigned int len() const
Definition: hb-set.hh:60
elt_t & elt(hb_codepoint_t g)
Definition: hb-set.hh:205
bool next(hb_codepoint_t *codepoint) const
Definition: hb-set.hh:122
static unsigned int elt_get_max(const elt_t &elt)
Definition: hb-set.hh:195
const page_t & page_at(unsigned int i) const
Definition: hb-set.hh:878
bool next_range(hb_codepoint_t *first, hb_codepoint_t *last) const
Definition: hb-set.hh:739
void symmetric_difference(const hb_set_t *other)
Definition: hb-set.hh:673
void intersect(const hb_set_t *other)
Definition: hb-set.hh:665
void fini()
Definition: hb-set.hh:237
const page_t * page_for(hb_codepoint_t g) const
Definition: hb-set.hh:869
unsigned int population
Definition: hb-set.hh:215
void compact_pages(const hb_vector_t< uint32_t > &old_index_to_page_map_index)
Definition: hb-set.hh:528
void add(hb_codepoint_t g)
Definition: hb-set.hh:284
void set(const hb_set_t *other)
Definition: hb-set.hh:463
bool get(hb_codepoint_t g) const
Definition: hb-set.hh:436
bool next(hb_codepoint_t *codepoint) const
Definition: hb-set.hh:677
void subtract(const hb_set_t *other)
Definition: hb-set.hh:669
hb_codepoint_t major_start(unsigned int major) const
Definition: hb-set.hh:880
bool operator()(hb_codepoint_t k) const
Definition: hb-set.hh:450
~hb_set_t()
Definition: hb-set.hh:45
bool successful
Definition: hb-set.hh:214
bool is_subset(const hb_set_t *larger_set) const
Definition: hb-set.hh:501
bool intersects(hb_codepoint_t first, hb_codepoint_t last) const
Definition: hb-set.hh:458
bool in_error() const
Definition: hb-set.hh:243
void init_shallow()
Definition: hb-set.hh:219
hb_set_t & operator<<(hb_codepoint_t v)
Definition: hb-set.hh:453
bool value_t
Definition: hb-set.hh:446
void compact(unsigned int length)
Definition: hb-set.hh:515
bool is_equal(const hb_set_t *other) const
Definition: hb-set.hh:474
void reset()
Definition: hb-set.hh:257
bool is_empty() const
Definition: hb-set.hh:273
void clear()
Definition: hb-set.hh:265
iter_t iter() const
Definition: hb-set.hh:839
bool resize(unsigned int count)
Definition: hb-set.hh:245
void init()
Definition: hb-set.hh:226
void del(hb_codepoint_t g)
Definition: hb-set.hh:376
void process(const Op &op, const hb_set_t *other)
Definition: hb-set.hh:544
bool previous_range(hb_codepoint_t *first, hb_codepoint_t *last) const
Definition: hb-set.hh:757
void fini_shallow()
Definition: hb-set.hh:231
void dirty()
Definition: hb-set.hh:282
static constexpr bool SENTINEL
Definition: hb-set.hh:445
bool previous(hb_codepoint_t *codepoint) const
Definition: hb-set.hh:708
static constexpr hb_codepoint_t INVALID
Definition: hb-set.hh:806
bool has(hb_codepoint_t k) const
Definition: hb-set.hh:448
unsigned int get_population() const
Definition: hb-set.hh:776
page_t * page_for_insert(hb_codepoint_t g)
Definition: hb-set.hh:844
void del_pages(int ds, int de)
Definition: hb-set.hh:388
hb_sorted_vector_t< page_map_t > page_map
Definition: hb-set.hh:216
page_t & page_at(unsigned int i)
Definition: hb-set.hh:877
hb_set_t()
Definition: hb-set.hh:44
void del_range(hb_codepoint_t a, hb_codepoint_t b)
Definition: hb-set.hh:405
hb_object_header_t header
Definition: hb-set.hh:211
hb_codepoint_t get_min() const
Definition: hb-set.hh:789
hb_vector_t< page_t > pages
Definition: hb-set.hh:217
bool add_sorted_array(const T *array, unsigned int count, unsigned int stride=sizeof(T))
Definition: hb-set.hh:348
hb_codepoint_t get_max() const
Definition: hb-set.hh:797
bool add_range(hb_codepoint_t a, hb_codepoint_t b)
Definition: hb-set.hh:292
unsigned int get_major(hb_codepoint_t g) const
Definition: hb-set.hh:879
page_t * page_for(hb_codepoint_t g)
Definition: hb-set.hh:861
void add_array(const T *array, unsigned int count, unsigned int stride=sizeof(T))
Definition: hb-set.hh:322
value_t operator[](hb_codepoint_t k) const
Definition: hb-set.hh:447
void union_(const hb_set_t *other)
Definition: hb-set.hh:661
void clear(unsigned char v=0)
Definition: hb-algs.hh:1094
bool resize(int size_)
Definition: hb-vector.hh:216
unsigned int length
Definition: hb-vector.hh:60
Definition: mendex.h:20
Definition: sh.h:1226
Definition: mendex.h:14
Definition: pdfdoc.c:79
int j
Definition: t4ht.c:1589
#define key
Definition: tex2xindy.c:753
found
Definition: tex4ht.c:5000
m
Definition: tex4ht.c:3990
op
Definition: tex4ht.c:3129
return() int(((double) *(font_tbl[cur_fnt].wtbl+(int)(*(font_tbl[cur_fnt].char_wi+(int)(ch - font_tbl[cur_fnt].char_f)% 256)))/(double)(1L<< 20)) *(double) font_tbl[cur_fnt].scale)
@ start
Definition: preamble.c:52
@ range
Definition: preamble.c:52
#define end(cp)
Definition: zic.c:71