1 /* 2 * Copyright © 2012 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_PRIVATE_HH 28 #define HB_SET_PRIVATE_HH 29 30 #include "hb-private.hh" 31 #include "hb-object-private.hh" 32 33 34 /* 35 * The set digests here implement various "filters" that support 36 * "approximate member query". Conceptually these are like Bloom 37 * Filter and Quotient Filter, however, much smaller, faster, and 38 * designed to fit the requirements of our uses for glyph coverage 39 * queries. 40 * 41 * Our filters are highly accurate if the lookup covers fairly local 42 * set of glyphs, but fully flooded and ineffective if coverage is 43 * all over the place. 44 * 45 * The frozen-set can be used instead of a digest, to trade more 46 * memory for 100% accuracy, but in practice, that doesn't look like 47 * an attractive trade-off. 48 */ 49 50 template <typename mask_t, unsigned int shift> 51 struct hb_set_digest_lowest_bits_t 52 { 53 ASSERT_POD (); 54 55 static const unsigned int mask_bytes = sizeof (mask_t); 56 static const unsigned int mask_bits = sizeof (mask_t) * 8; 57 static const unsigned int num_bits = 0 58 + (mask_bytes >= 1 ? 3 : 0) 59 + (mask_bytes >= 2 ? 1 : 0) 60 + (mask_bytes >= 4 ? 1 : 0) 61 + (mask_bytes >= 8 ? 1 : 0) 62 + (mask_bytes >= 16? 1 : 0) 63 + 0; 64 65 ASSERT_STATIC (shift < sizeof (hb_codepoint_t) * 8); 66 ASSERT_STATIC (shift + num_bits <= sizeof (hb_codepoint_t) * 8); 67 68 inline void init (void) { 69 mask = 0; 70 } 71 72 inline void add (hb_codepoint_t g) { 73 mask |= mask_for (g); 74 } 75 76 inline void add_range (hb_codepoint_t a, hb_codepoint_t b) { 77 if ((b >> shift) - (a >> shift) >= mask_bits - 1) 78 mask = (mask_t) -1; 79 else { 80 mask_t ma = mask_for (a); 81 mask_t mb = mask_for (b); 82 mask |= mb + (mb - ma) - (mb < ma); 83 } 84 } 85 86 inline bool may_have (hb_codepoint_t g) const { 87 return !!(mask & mask_for (g)); 88 } 89 90 private: 91 92 static inline mask_t mask_for (hb_codepoint_t g) { 93 return ((mask_t) 1) << ((g >> shift) & (mask_bits - 1)); 94 } 95 mask_t mask; 96 }; 97 98 template <typename head_t, typename tail_t> 99 struct hb_set_digest_combiner_t 100 { 101 ASSERT_POD (); 102 103 inline void init (void) { 104 head.init (); 105 tail.init (); 106 } 107 108 inline void add (hb_codepoint_t g) { 109 head.add (g); 110 tail.add (g); 111 } 112 113 inline void add_range (hb_codepoint_t a, hb_codepoint_t b) { 114 head.add_range (a, b); 115 tail.add_range (a, b); 116 } 117 118 inline bool may_have (hb_codepoint_t g) const { 119 return head.may_have (g) && tail.may_have (g); 120 } 121 122 private: 123 head_t head; 124 tail_t tail; 125 }; 126 127 128 /* 129 * hb_set_digest_t 130 * 131 * This is a combination of digests that performs "best". 132 * There is not much science to this: it's a result of intuition 133 * and testing. 134 */ 135 typedef hb_set_digest_combiner_t 136 < 137 hb_set_digest_lowest_bits_t<unsigned long, 4>, 138 hb_set_digest_combiner_t 139 < 140 hb_set_digest_lowest_bits_t<unsigned long, 0>, 141 hb_set_digest_lowest_bits_t<unsigned long, 9> 142 > 143 > hb_set_digest_t; 144 145 146 147 /* 148 * hb_set_t 149 */ 150 151 152 /* TODO Make this faster and memmory efficient. */ 153 154 struct hb_set_t 155 { 156 friend struct hb_frozen_set_t; 157 158 hb_object_header_t header; 159 ASSERT_POD (); 160 bool in_error; 161 162 inline void init (void) { 163 hb_object_init (this); 164 clear (); 165 } 166 inline void fini (void) { 167 } 168 inline void clear (void) { 169 if (unlikely (hb_object_is_inert (this))) 170 return; 171 in_error = false; 172 memset (elts, 0, sizeof elts); 173 } 174 inline bool is_empty (void) const { 175 for (unsigned int i = 0; i < ARRAY_LENGTH (elts); i++) 176 if (elts[i]) 177 return false; 178 return true; 179 } 180 inline void add (hb_codepoint_t g) 181 { 182 if (unlikely (in_error)) return; 183 if (unlikely (g == INVALID)) return; 184 if (unlikely (g > MAX_G)) return; 185 elt (g) |= mask (g); 186 } 187 inline void add_range (hb_codepoint_t a, hb_codepoint_t b) 188 { 189 if (unlikely (in_error)) return; 190 /* TODO Speedup */ 191 for (unsigned int i = a; i < b + 1; i++) 192 add (i); 193 } 194 inline void del (hb_codepoint_t g) 195 { 196 if (unlikely (in_error)) return; 197 if (unlikely (g > MAX_G)) return; 198 elt (g) &= ~mask (g); 199 } 200 inline void del_range (hb_codepoint_t a, hb_codepoint_t b) 201 { 202 if (unlikely (in_error)) return; 203 /* TODO Speedup */ 204 for (unsigned int i = a; i < b + 1; i++) 205 del (i); 206 } 207 inline bool has (hb_codepoint_t g) const 208 { 209 if (unlikely (g > MAX_G)) return false; 210 return !!(elt (g) & mask (g)); 211 } 212 inline bool intersects (hb_codepoint_t first, 213 hb_codepoint_t last) const 214 { 215 if (unlikely (first > MAX_G)) return false; 216 if (unlikely (last > MAX_G)) last = MAX_G; 217 unsigned int end = last + 1; 218 for (hb_codepoint_t i = first; i < end; i++) 219 if (has (i)) 220 return true; 221 return false; 222 } 223 inline bool is_equal (const hb_set_t *other) const 224 { 225 for (unsigned int i = 0; i < ELTS; i++) 226 if (elts[i] != other->elts[i]) 227 return false; 228 return true; 229 } 230 inline void set (const hb_set_t *other) 231 { 232 if (unlikely (in_error)) return; 233 for (unsigned int i = 0; i < ELTS; i++) 234 elts[i] = other->elts[i]; 235 } 236 inline void union_ (const hb_set_t *other) 237 { 238 if (unlikely (in_error)) return; 239 for (unsigned int i = 0; i < ELTS; i++) 240 elts[i] |= other->elts[i]; 241 } 242 inline void intersect (const hb_set_t *other) 243 { 244 if (unlikely (in_error)) return; 245 for (unsigned int i = 0; i < ELTS; i++) 246 elts[i] &= other->elts[i]; 247 } 248 inline void subtract (const hb_set_t *other) 249 { 250 if (unlikely (in_error)) return; 251 for (unsigned int i = 0; i < ELTS; i++) 252 elts[i] &= ~other->elts[i]; 253 } 254 inline void symmetric_difference (const hb_set_t *other) 255 { 256 if (unlikely (in_error)) return; 257 for (unsigned int i = 0; i < ELTS; i++) 258 elts[i] ^= other->elts[i]; 259 } 260 inline void invert (void) 261 { 262 if (unlikely (in_error)) return; 263 for (unsigned int i = 0; i < ELTS; i++) 264 elts[i] = ~elts[i]; 265 } 266 inline bool next (hb_codepoint_t *codepoint) const 267 { 268 if (unlikely (*codepoint == INVALID)) { 269 hb_codepoint_t i = get_min (); 270 if (i != INVALID) { 271 *codepoint = i; 272 return true; 273 } else { 274 *codepoint = INVALID; 275 return false; 276 } 277 } 278 for (hb_codepoint_t i = *codepoint + 1; i < MAX_G + 1; i++) 279 if (has (i)) { 280 *codepoint = i; 281 return true; 282 } 283 *codepoint = INVALID; 284 return false; 285 } 286 inline bool next_range (hb_codepoint_t *first, hb_codepoint_t *last) const 287 { 288 hb_codepoint_t i; 289 290 i = *last; 291 if (!next (&i)) 292 { 293 *last = *first = INVALID; 294 return false; 295 } 296 297 *last = *first = i; 298 while (next (&i) && i == *last + 1) 299 (*last)++; 300 301 return true; 302 } 303 304 inline unsigned int get_population (void) const 305 { 306 unsigned int count = 0; 307 for (unsigned int i = 0; i < ELTS; i++) 308 count += _hb_popcount32 (elts[i]); 309 return count; 310 } 311 inline hb_codepoint_t get_min (void) const 312 { 313 for (unsigned int i = 0; i < ELTS; i++) 314 if (elts[i]) 315 for (unsigned int j = 0; j < BITS; j++) 316 if (elts[i] & (1u << j)) 317 return i * BITS + j; 318 return INVALID; 319 } 320 inline hb_codepoint_t get_max (void) const 321 { 322 for (unsigned int i = ELTS; i; i--) 323 if (elts[i - 1]) 324 for (unsigned int j = BITS; j; j--) 325 if (elts[i - 1] & (1u << (j - 1))) 326 return (i - 1) * BITS + (j - 1); 327 return INVALID; 328 } 329 330 typedef uint32_t elt_t; 331 static const unsigned int MAX_G = 65536 - 1; /* XXX Fix this... */ 332 static const unsigned int SHIFT = 5; 333 static const unsigned int BITS = (1 << SHIFT); 334 static const unsigned int MASK = BITS - 1; 335 static const unsigned int ELTS = (MAX_G + 1 + (BITS - 1)) / BITS; 336 static const hb_codepoint_t INVALID = HB_SET_VALUE_INVALID; 337 338 elt_t &elt (hb_codepoint_t g) { return elts[g >> SHIFT]; } 339 elt_t const &elt (hb_codepoint_t g) const { return elts[g >> SHIFT]; } 340 elt_t mask (hb_codepoint_t g) const { return elt_t (1) << (g & MASK); } 341 342 elt_t elts[ELTS]; /* XXX 8kb */ 343 344 ASSERT_STATIC (sizeof (elt_t) * 8 == BITS); 345 ASSERT_STATIC (sizeof (elt_t) * 8 * ELTS > MAX_G); 346 }; 347 348 struct hb_frozen_set_t 349 { 350 static const unsigned int SHIFT = hb_set_t::SHIFT; 351 static const unsigned int BITS = hb_set_t::BITS; 352 static const unsigned int MASK = hb_set_t::MASK; 353 typedef hb_set_t::elt_t elt_t; 354 355 inline void init (const hb_set_t &set) 356 { 357 start = count = 0; 358 elts = NULL; 359 360 unsigned int max = set.get_max (); 361 if (max == set.INVALID) 362 return; 363 unsigned int min = set.get_min (); 364 const elt_t &min_elt = set.elt (min); 365 366 start = min & ~MASK; 367 count = max - start + 1; 368 unsigned int num_elts = (count + BITS - 1) / BITS; 369 unsigned int elts_size = num_elts * sizeof (elt_t); 370 elts = (elt_t *) malloc (elts_size); 371 if (unlikely (!elts)) 372 { 373 start = count = 0; 374 return; 375 } 376 memcpy (elts, &min_elt, elts_size); 377 } 378 379 inline void fini (void) 380 { 381 if (elts) 382 free (elts); 383 } 384 385 inline bool has (hb_codepoint_t g) const 386 { 387 /* hb_codepoint_t is unsigned. */ 388 g -= start; 389 if (unlikely (g > count)) return false; 390 return !!(elt (g) & mask (g)); 391 } 392 393 elt_t const &elt (hb_codepoint_t g) const { return elts[g >> SHIFT]; } 394 elt_t mask (hb_codepoint_t g) const { return elt_t (1) << (g & MASK); } 395 396 private: 397 hb_codepoint_t start, count; 398 elt_t *elts; 399 }; 400 401 402 #endif /* HB_SET_PRIVATE_HH */ | 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_PRIVATE_HH 28 #define HB_SET_PRIVATE_HH 29 30 #include "hb-private.hh" 31 #include "hb-object-private.hh" 32 33 34 /* 35 * hb_set_t 36 */ 37 38 struct hb_set_t 39 { 40 struct page_map_t 41 { 42 inline int cmp (const page_map_t *o) const { return (int) o->major - (int) major; } 43 44 uint32_t major; 45 uint32_t index; 46 }; 47 48 struct page_t 49 { 50 inline void init (void) { 51 memset (&v, 0, sizeof (v)); 52 } 53 54 inline unsigned int len (void) const 55 { return ARRAY_LENGTH_CONST (v); } 56 57 inline bool is_empty (void) const 58 { 59 for (unsigned int i = 0; i < len (); i++) 60 if (v[i]) 61 return false; 62 return true; 63 } 64 65 inline void add (hb_codepoint_t g) { elt (g) |= mask (g); } 66 inline void del (hb_codepoint_t g) { elt (g) &= ~mask (g); } 67 inline bool has (hb_codepoint_t g) const { return !!(elt (g) & mask (g)); } 68 69 inline bool is_equal (const page_t *other) const 70 { 71 return 0 == memcmp (&v, &other->v, sizeof (v)); 72 } 73 74 inline unsigned int get_population (void) const 75 { 76 unsigned int pop = 0; 77 for (unsigned int i = 0; i < len (); i++) 78 pop += _hb_popcount (v[i]); 79 return pop; 80 } 81 82 inline bool next (hb_codepoint_t *codepoint) const 83 { 84 unsigned int m = (*codepoint + 1) & MASK; 85 if (!m) 86 { 87 *codepoint = INVALID; 88 return false; 89 } 90 unsigned int i = m / ELT_BITS; 91 unsigned int j = m & ELT_MASK; 92 93 for (; j < ELT_BITS; j++) 94 if (v[i] & (elt_t (1) << j)) 95 goto found; 96 for (i++; i < len (); i++) 97 if (v[i]) 98 for (j = 0; j < ELT_BITS; j++) 99 if (v[i] & (elt_t (1) << j)) 100 goto found; 101 102 *codepoint = INVALID; 103 return false; 104 105 found: 106 *codepoint = i * ELT_BITS + j; 107 return true; 108 } 109 inline hb_codepoint_t get_min (void) const 110 { 111 for (unsigned int i = 0; i < len (); i++) 112 if (v[i]) 113 { 114 elt_t e = v[i]; 115 for (unsigned int j = 0; j < ELT_BITS; j++) 116 if (e & (elt_t (1) << j)) 117 return i * ELT_BITS + j; 118 } 119 return INVALID; 120 } 121 inline hb_codepoint_t get_max (void) const 122 { 123 for (int i = len () - 1; i >= 0; i--) 124 if (v[i]) 125 { 126 elt_t e = v[i]; 127 for (int j = ELT_BITS - 1; j >= 0; j--) 128 if (e & (elt_t (1) << j)) 129 return i * ELT_BITS + j; 130 } 131 return 0; 132 } 133 134 static const unsigned int PAGE_BITS = 512; /* Use to tune. */ 135 static_assert ((PAGE_BITS & ((PAGE_BITS) - 1)) == 0, ""); 136 137 typedef uint64_t elt_t; 138 139 #if 0 && HAVE_VECTOR_SIZE 140 /* The vectorized version does not work with clang as non-const 141 * elt() errs "non-const reference cannot bind to vector element". */ 142 typedef elt_t vector_t __attribute__((vector_size (PAGE_BITS / 8))); 143 #else 144 typedef hb_vector_size_t<elt_t, PAGE_BITS / 8> vector_t; 145 #endif 146 147 vector_t v; 148 149 static const unsigned int ELT_BITS = sizeof (elt_t) * 8; 150 static const unsigned int ELT_MASK = ELT_BITS - 1; 151 static const unsigned int BITS = sizeof (vector_t) * 8; 152 static const unsigned int MASK = BITS - 1; 153 static_assert (PAGE_BITS == BITS, ""); 154 155 elt_t &elt (hb_codepoint_t g) { return v[(g & MASK) / ELT_BITS]; } 156 elt_t const &elt (hb_codepoint_t g) const { return v[(g & MASK) / ELT_BITS]; } 157 elt_t mask (hb_codepoint_t g) const { return elt_t (1) << (g & ELT_MASK); } 158 }; 159 static_assert (page_t::PAGE_BITS == sizeof (page_t) * 8, ""); 160 161 hb_object_header_t header; 162 ASSERT_POD (); 163 bool in_error; 164 hb_prealloced_array_t<page_map_t, 8> page_map; 165 hb_prealloced_array_t<page_t, 8> pages; 166 167 inline bool resize (unsigned int count) 168 { 169 if (unlikely (in_error)) return false; 170 if (!pages.resize (count) || !page_map.resize (count)) 171 { 172 pages.resize (page_map.len); 173 in_error = true; 174 return false; 175 } 176 return true; 177 } 178 179 inline void clear (void) { 180 if (unlikely (hb_object_is_inert (this))) 181 return; 182 in_error = false; 183 page_map.resize (0); 184 pages.resize (0); 185 } 186 inline bool is_empty (void) const { 187 unsigned int count = pages.len; 188 for (unsigned int i = 0; i < count; i++) 189 if (!pages[i].is_empty ()) 190 return false; 191 return true; 192 } 193 194 inline void add (hb_codepoint_t g) 195 { 196 if (unlikely (in_error)) return; 197 if (unlikely (g == INVALID)) return; 198 page_t *page = page_for_insert (g); 199 if (!page) 200 return; 201 page->add (g); 202 } 203 inline void add_range (hb_codepoint_t a, hb_codepoint_t b) 204 { 205 if (unlikely (in_error)) return; 206 /* TODO Speedup */ 207 for (unsigned int i = a; i < b + 1; i++) 208 add (i); 209 } 210 inline void del (hb_codepoint_t g) 211 { 212 if (unlikely (in_error)) return; 213 page_t *p = page_for (g); 214 if (!p) 215 return; 216 p->del (g); 217 } 218 inline void del_range (hb_codepoint_t a, hb_codepoint_t b) 219 { 220 if (unlikely (in_error)) return; 221 for (unsigned int i = a; i < b + 1; i++) 222 del (i); 223 } 224 inline bool has (hb_codepoint_t g) const 225 { 226 const page_t *p = page_for (g); 227 if (!p) 228 return false; 229 return p->has (g); 230 } 231 inline bool intersects (hb_codepoint_t first, 232 hb_codepoint_t last) const 233 { 234 hb_codepoint_t c = first - 1; 235 return next (&c) && c <= last; 236 } 237 inline void set (const hb_set_t *other) 238 { 239 if (unlikely (in_error)) return; 240 unsigned int count = other->pages.len; 241 if (!resize (count)) 242 return; 243 244 memcpy (pages.array, other->pages.array, count * sizeof (pages.array[0])); 245 memcpy (page_map.array, other->page_map.array, count * sizeof (page_map.array[0])); 246 } 247 248 inline bool is_equal (const hb_set_t *other) const 249 { 250 unsigned int na = pages.len; 251 unsigned int nb = other->pages.len; 252 253 unsigned int a = 0, b = 0; 254 for (; a < na && b < nb; ) 255 { 256 if (page_at (a).is_empty ()) { a++; continue; } 257 if (other->page_at (b).is_empty ()) { b++; continue; } 258 if (page_map[a].major != other->page_map[b].major || 259 !page_at (a).is_equal (&other->page_at (b))) 260 return false; 261 a++; 262 b++; 263 } 264 for (; a < na; a++) 265 if (!page_at (a).is_empty ()) { return false; } 266 for (; b < nb; b++) 267 if (!other->page_at (b).is_empty ()) { return false; } 268 269 return true; 270 } 271 272 template <class Op> 273 inline void process (const hb_set_t *other) 274 { 275 if (unlikely (in_error)) return; 276 277 unsigned int na = pages.len; 278 unsigned int nb = other->pages.len; 279 280 unsigned int count = 0; 281 unsigned int a = 0, b = 0; 282 for (; a < na && b < nb; ) 283 { 284 if (page_map[a].major == other->page_map[b].major) 285 { 286 count++; 287 a++; 288 b++; 289 } 290 else if (page_map[a].major < other->page_map[b].major) 291 { 292 if (Op::passthru_left) 293 count++; 294 a++; 295 } 296 else 297 { 298 if (Op::passthru_right) 299 count++; 300 b++; 301 } 302 } 303 if (Op::passthru_left) 304 count += na - a; 305 if (Op::passthru_right) 306 count += nb - b; 307 308 if (!resize (count)) 309 return; 310 311 /* Process in-place backward. */ 312 a = na; 313 b = nb; 314 for (; a && b; ) 315 { 316 if (page_map[a - 1].major == other->page_map[b - 1].major) 317 { 318 a--; 319 b--; 320 Op::process (page_at (--count).v, page_at (a).v, other->page_at (b).v); 321 } 322 else if (page_map[a - 1].major > other->page_map[b - 1].major) 323 { 324 a--; 325 if (Op::passthru_left) 326 page_at (--count).v = page_at (a).v; 327 } 328 else 329 { 330 b--; 331 if (Op::passthru_right) 332 page_at (--count).v = other->page_at (b).v; 333 } 334 } 335 if (Op::passthru_left) 336 while (a) 337 page_at (--count).v = page_at (--a).v; 338 if (Op::passthru_right) 339 while (b) 340 page_at (--count).v = other->page_at (--b).v; 341 assert (!count); 342 } 343 344 inline void union_ (const hb_set_t *other) 345 { 346 process<HbOpOr> (other); 347 } 348 inline void intersect (const hb_set_t *other) 349 { 350 process<HbOpAnd> (other); 351 } 352 inline void subtract (const hb_set_t *other) 353 { 354 process<HbOpMinus> (other); 355 } 356 inline void symmetric_difference (const hb_set_t *other) 357 { 358 process<HbOpXor> (other); 359 } 360 inline bool next (hb_codepoint_t *codepoint) const 361 { 362 if (unlikely (*codepoint == INVALID)) { 363 *codepoint = get_min (); 364 return *codepoint != INVALID; 365 } 366 367 page_map_t map = {get_major (*codepoint), 0}; 368 unsigned int i; 369 page_map.bfind (&map, &i); 370 if (i < page_map.len) 371 { 372 if (pages[page_map[i].index].next (codepoint)) 373 { 374 *codepoint += page_map[i].major * page_t::PAGE_BITS; 375 return true; 376 } 377 i++; 378 } 379 for (; i < page_map.len; i++) 380 { 381 hb_codepoint_t m = pages[page_map[i].index].get_min (); 382 if (m != INVALID) 383 { 384 *codepoint = page_map[i].major * page_t::PAGE_BITS + m; 385 return true; 386 } 387 } 388 *codepoint = INVALID; 389 return false; 390 } 391 inline bool next_range (hb_codepoint_t *first, hb_codepoint_t *last) const 392 { 393 hb_codepoint_t i; 394 395 i = *last; 396 if (!next (&i)) 397 { 398 *last = *first = INVALID; 399 return false; 400 } 401 402 *last = *first = i; 403 while (next (&i) && i == *last + 1) 404 (*last)++; 405 406 return true; 407 } 408 409 inline unsigned int get_population (void) const 410 { 411 unsigned int pop = 0; 412 unsigned int count = pages.len; 413 for (unsigned int i = 0; i < count; i++) 414 pop += pages[i].get_population (); 415 return pop; 416 } 417 inline hb_codepoint_t get_min (void) const 418 { 419 unsigned int count = pages.len; 420 for (unsigned int i = 0; i < count; i++) 421 if (!page_at (i).is_empty ()) 422 return page_map[i].major * page_t::PAGE_BITS + page_at (i).get_min (); 423 return INVALID; 424 } 425 inline hb_codepoint_t get_max (void) const 426 { 427 unsigned int count = pages.len; 428 for (int i = count - 1; i >= 0; i++) 429 if (!page_at (i).is_empty ()) 430 return page_map[i].major * page_t::PAGE_BITS + page_at (i).get_max (); 431 return INVALID; 432 } 433 434 static const hb_codepoint_t INVALID = HB_SET_VALUE_INVALID; 435 436 page_t *page_for_insert (hb_codepoint_t g) 437 { 438 page_map_t map = {get_major (g), pages.len}; 439 unsigned int i; 440 if (!page_map.bfind (&map, &i)) 441 { 442 if (!resize (pages.len + 1)) 443 return nullptr; 444 445 pages[map.index].init (); 446 memmove (&page_map[i + 1], &page_map[i], (page_map.len - 1 - i) * sizeof (page_map[0])); 447 page_map[i] = map; 448 } 449 return &pages[page_map[i].index]; 450 } 451 page_t *page_for (hb_codepoint_t g) 452 { 453 page_map_t key = {get_major (g)}; 454 const page_map_t *found = page_map.bsearch (&key); 455 if (found) 456 return &pages[found->index]; 457 return nullptr; 458 } 459 const page_t *page_for (hb_codepoint_t g) const 460 { 461 page_map_t key = {get_major (g)}; 462 const page_map_t *found = page_map.bsearch (&key); 463 if (found) 464 return &pages[found->index]; 465 return nullptr; 466 } 467 page_t &page_at (unsigned int i) { return pages[page_map[i].index]; } 468 const page_t &page_at (unsigned int i) const { return pages[page_map[i].index]; } 469 unsigned int get_major (hb_codepoint_t g) const { return g / page_t::PAGE_BITS; } 470 }; 471 472 473 #endif /* HB_SET_PRIVATE_HH */ |