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_ARRAY_HH
28 #define HB_ARRAY_HH
29
30 #include "hb.hh"
31 #include "hb-algs.hh"
32 #include "hb-iter.hh"
33 #include "hb-null.hh"
34
35
36 template <typename Type>
37 struct hb_sorted_array_t;
38
39 enum hb_not_found_t
40 {
41 HB_NOT_FOUND_DONT_STORE,
42 HB_NOT_FOUND_STORE,
43 HB_NOT_FOUND_STORE_CLOSEST,
44 };
45
46
47 template <typename Type>
48 struct hb_array_t : hb_iter_with_fallback_t<hb_array_t<Type>, Type&>
49 {
50 /*
51 * Constructors.
52 */
53 hb_array_t () = default;
54 hb_array_t (const hb_array_t&) = default;
55 ~hb_array_t () = default;
56 hb_array_t& operator= (const hb_array_t&) = default;
57 hb_array_t& operator= (hb_array_t&&) = default;
58
hb_array_thb_array_t59 constexpr hb_array_t (Type *array_, unsigned int length_) : arrayZ (array_), length (length_) {}
60 template <unsigned int length_>
hb_array_thb_array_t61 constexpr hb_array_t (Type (&array_)[length_]) : hb_array_t (array_, length_) {}
62
63 template <typename U,
64 hb_enable_if (hb_is_cr_convertible(U, Type))>
hb_array_thb_array_t65 constexpr hb_array_t (const hb_array_t<U> &o) :
66 hb_iter_with_fallback_t<hb_array_t, Type&> (),
67 arrayZ (o.arrayZ), length (o.length), backwards_length (o.backwards_length) {}
68 template <typename U,
69 hb_enable_if (hb_is_cr_convertible(U, Type))>
operator =hb_array_t70 hb_array_t& operator = (const hb_array_t<U> &o)
71 { arrayZ = o.arrayZ; length = o.length; backwards_length = o.backwards_length; return *this; }
72
73 /*
74 * Iterator implementation.
75 */
76 typedef Type& __item_t__;
77 static constexpr bool is_random_access_iterator = true;
78 static constexpr bool has_fast_len = true;
__item__hb_array_t79 Type& __item__ () const
80 {
81 if (unlikely (!length)) return CrapOrNull (Type);
82 return *arrayZ;
83 }
__item_at__hb_array_t84 Type& __item_at__ (unsigned i) const
85 {
86 if (unlikely (i >= length)) return CrapOrNull (Type);
87 return arrayZ[i];
88 }
__next__hb_array_t89 void __next__ ()
90 {
91 if (unlikely (!length))
92 return;
93 length--;
94 backwards_length++;
95 arrayZ++;
96 }
__forward__hb_array_t97 void __forward__ (unsigned n)
98 {
99 if (unlikely (n > length))
100 n = length;
101 length -= n;
102 backwards_length += n;
103 arrayZ += n;
104 }
__prev__hb_array_t105 void __prev__ ()
106 {
107 if (unlikely (!backwards_length))
108 return;
109 length++;
110 backwards_length--;
111 arrayZ--;
112 }
__rewind__hb_array_t113 void __rewind__ (unsigned n)
114 {
115 if (unlikely (n > backwards_length))
116 n = backwards_length;
117 length += n;
118 backwards_length -= n;
119 arrayZ -= n;
120 }
__len__hb_array_t121 unsigned __len__ () const { return length; }
122 /* Ouch. The operator== compares the contents of the array. For range-based for loops,
123 * it's best if we can just compare arrayZ, though comparing contents is still fast,
124 * but also would require that Type has operator==. As such, we optimize this operator
125 * for range-based for loop and just compare arrayZ and length.
126 *
127 * The above comment is outdated now because we implemented separate begin/end to
128 * objects that were using hb_array_t for range-based loop before. */
operator !=hb_array_t129 bool operator != (const hb_array_t& o) const
130 { return this->arrayZ != o.arrayZ || this->length != o.length; }
131
132 /* Faster range-based for loop without bounds-check. */
beginhb_array_t133 Type *begin () const { return arrayZ; }
endhb_array_t134 Type *end () const { return arrayZ + length; }
135
136
137 /* Extra operators.
138 */
operator &hb_array_t139 Type * operator & () const { return arrayZ; }
operator hb_array_t<const Type>hb_array_t140 operator hb_array_t<const Type> () { return hb_array_t<const Type> (arrayZ, length); }
operator T*hb_array_t141 template <typename T> operator T * () const { return arrayZ; }
142
143 HB_INTERNAL bool operator == (const hb_array_t &o) const;
144
hashhb_array_t145 uint32_t hash () const
146 {
147 // FNV-1a hash function
148 // https://github.com/harfbuzz/harfbuzz/pull/4228
149 uint32_t current = /*cbf29ce4*/0x84222325;
150 for (auto &v : *this)
151 {
152 current = current ^ hb_hash (v);
153 current = current * 16777619;
154 }
155 return current;
156 }
157
158 /*
159 * Compare, Sort, and Search.
160 */
161
162 /* Note: our compare is NOT lexicographic; it also does NOT call Type::cmp. */
cmphb_array_t163 int cmp (const hb_array_t &a) const
164 {
165 if (length != a.length)
166 return (int) a.length - (int) length;
167 return hb_memcmp (a.arrayZ, arrayZ, get_size ());
168 }
cmphb_array_t169 HB_INTERNAL static int cmp (const void *pa, const void *pb)
170 {
171 hb_array_t *a = (hb_array_t *) pa;
172 hb_array_t *b = (hb_array_t *) pb;
173 return b->cmp (*a);
174 }
175
176 template <typename T>
lsearchhb_array_t177 Type *lsearch (const T &x, Type *not_found = nullptr)
178 {
179 unsigned i;
180 return lfind (x, &i) ? &this->arrayZ[i] : not_found;
181 }
182 template <typename T>
lsearchhb_array_t183 const Type *lsearch (const T &x, const Type *not_found = nullptr) const
184 {
185 unsigned i;
186 return lfind (x, &i) ? &this->arrayZ[i] : not_found;
187 }
188 template <typename T>
lfindhb_array_t189 bool lfind (const T &x, unsigned *pos = nullptr,
190 hb_not_found_t not_found = HB_NOT_FOUND_DONT_STORE,
191 unsigned int to_store = (unsigned int) -1) const
192 {
193 for (unsigned i = 0; i < length; ++i)
194 if (hb_equal (x, this->arrayZ[i]))
195 {
196 if (pos)
197 *pos = i;
198 return true;
199 }
200
201 if (pos)
202 {
203 switch (not_found)
204 {
205 case HB_NOT_FOUND_DONT_STORE:
206 break;
207
208 case HB_NOT_FOUND_STORE:
209 *pos = to_store;
210 break;
211
212 case HB_NOT_FOUND_STORE_CLOSEST:
213 *pos = length;
214 break;
215 }
216 }
217 return false;
218 }
219
qsorthb_array_t220 hb_sorted_array_t<Type> qsort (int (*cmp_)(const void*, const void*))
221 {
222 //static_assert (hb_enable_if (hb_is_trivially_copy_assignable(Type)), "");
223 if (likely (length))
224 hb_qsort (arrayZ, length, this->get_item_size (), cmp_);
225 return hb_sorted_array_t<Type> (*this);
226 }
qsorthb_array_t227 hb_sorted_array_t<Type> qsort ()
228 {
229 //static_assert (hb_enable_if (hb_is_trivially_copy_assignable(Type)), "");
230 if (likely (length))
231 hb_qsort (arrayZ, length, this->get_item_size (), Type::cmp);
232 return hb_sorted_array_t<Type> (*this);
233 }
234
235 /*
236 * Other methods.
237 */
238
get_sizehb_array_t239 unsigned int get_size () const { return length * this->get_item_size (); }
240
241 /*
242 * Reverse the order of items in this array in the range [start, end).
243 */
reversehb_array_t244 void reverse (unsigned start = 0, unsigned end = -1)
245 {
246 start = hb_min (start, length);
247 end = hb_min (end, length);
248
249 if (end < start + 2)
250 return;
251
252 for (unsigned lhs = start, rhs = end - 1; lhs < rhs; lhs++, rhs--)
253 hb_swap (arrayZ[rhs], arrayZ[lhs]);
254 }
255
sub_arrayhb_array_t256 hb_array_t sub_array (unsigned int start_offset = 0, unsigned int *seg_count = nullptr /* IN/OUT */) const
257 {
258 if (!start_offset && !seg_count)
259 return *this;
260
261 unsigned int count = length;
262 if (unlikely (start_offset > count))
263 count = 0;
264 else
265 count -= start_offset;
266 if (seg_count)
267 count = *seg_count = hb_min (count, *seg_count);
268 return hb_array_t (arrayZ + start_offset, count);
269 }
sub_arrayhb_array_t270 hb_array_t sub_array (unsigned int start_offset, unsigned int seg_count) const
271 { return sub_array (start_offset, &seg_count); }
272
truncatehb_array_t273 hb_array_t truncate (unsigned length) const { return sub_array (0, length); }
274
275 template <typename T,
276 unsigned P = sizeof (Type),
277 hb_enable_if (P == 1)>
ashb_array_t278 const T *as () const
279 { return length < hb_min_size (T) ? &Null (T) : reinterpret_cast<const T *> (arrayZ); }
280
281 template <typename T,
282 unsigned P = sizeof (Type),
283 hb_enable_if (P == 1)>
check_rangehb_array_t284 bool check_range (const T *p, unsigned int size = T::static_size) const
285 {
286 return arrayZ <= ((const char *) p)
287 && ((const char *) p) <= arrayZ + length
288 && (unsigned int) (arrayZ + length - (const char *) p) >= size;
289 }
290
291 /* Only call if you allocated the underlying array using hb_malloc() or similar. */
finihb_array_t292 void fini ()
293 { hb_free ((void *) arrayZ); arrayZ = nullptr; length = 0; }
294
295 template <typename hb_serialize_context_t,
296 typename U = Type,
297 hb_enable_if (!(sizeof (U) < sizeof (long long) && hb_is_trivially_copy_assignable(hb_decay<Type>)))>
copyhb_array_t298 hb_array_t copy (hb_serialize_context_t *c) const
299 {
300 TRACE_SERIALIZE (this);
301 auto* out = c->start_embed (arrayZ);
302 if (unlikely (!c->extend_size (out, get_size (), false))) return_trace (hb_array_t ());
303 for (unsigned i = 0; i < length; i++)
304 out[i] = arrayZ[i]; /* TODO: add version that calls c->copy() */
305 return_trace (hb_array_t (out, length));
306 }
307
308 template <typename hb_serialize_context_t,
309 typename U = Type,
310 hb_enable_if (sizeof (U) < sizeof (long long) && hb_is_trivially_copy_assignable(hb_decay<Type>))>
copyhb_array_t311 hb_array_t copy (hb_serialize_context_t *c) const
312 {
313 TRACE_SERIALIZE (this);
314 auto* out = c->start_embed (arrayZ);
315 if (unlikely (!c->extend_size (out, get_size (), false))) return_trace (hb_array_t ());
316 hb_memcpy (out, arrayZ, get_size ());
317 return_trace (hb_array_t (out, length));
318 }
319
320 template <typename hb_sanitize_context_t>
sanitizehb_array_t321 bool sanitize (hb_sanitize_context_t *c) const
322 { return c->check_array (arrayZ, length); }
323
324 /*
325 * Members
326 */
327
328 public:
329 Type *arrayZ = nullptr;
330 unsigned int length = 0;
331 unsigned int backwards_length = 0;
332 };
333 template <typename T> inline hb_array_t<T>
hb_array()334 hb_array ()
335 { return hb_array_t<T> (); }
336 template <typename T> inline hb_array_t<T>
hb_array(T * array,unsigned int length)337 hb_array (T *array, unsigned int length)
338 { return hb_array_t<T> (array, length); }
339 template <typename T, unsigned int length_> inline hb_array_t<T>
hb_array(T (& array_)[length_])340 hb_array (T (&array_)[length_])
341 { return hb_array_t<T> (array_); }
342
343 template <typename Type>
344 struct hb_sorted_array_t :
345 hb_array_t<Type>,
346 hb_iter_t<hb_sorted_array_t<Type>, Type&>
347 {
348 typedef hb_iter_t<hb_sorted_array_t, Type&> iter_base_t;
349 HB_ITER_USING (iter_base_t);
350 static constexpr bool is_random_access_iterator = true;
351 static constexpr bool is_sorted_iterator = true;
352 static constexpr bool has_fast_len = true;
353
354 hb_sorted_array_t () = default;
355 hb_sorted_array_t (const hb_sorted_array_t&) = default;
356 ~hb_sorted_array_t () = default;
357 hb_sorted_array_t& operator= (const hb_sorted_array_t&) = default;
358 hb_sorted_array_t& operator= (hb_sorted_array_t&&) = default;
359
hb_sorted_array_thb_sorted_array_t360 constexpr hb_sorted_array_t (Type *array_, unsigned int length_) : hb_array_t<Type> (array_, length_) {}
361 template <unsigned int length_>
hb_sorted_array_thb_sorted_array_t362 constexpr hb_sorted_array_t (Type (&array_)[length_]) : hb_array_t<Type> (array_) {}
363
364 template <typename U,
365 hb_enable_if (hb_is_cr_convertible(U, Type))>
hb_sorted_array_thb_sorted_array_t366 constexpr hb_sorted_array_t (const hb_array_t<U> &o) :
367 hb_array_t<Type> (o),
368 hb_iter_t<hb_sorted_array_t, Type&> () {}
369 template <typename U,
370 hb_enable_if (hb_is_cr_convertible(U, Type))>
operator =hb_sorted_array_t371 hb_sorted_array_t& operator = (const hb_array_t<U> &o)
372 { hb_array_t<Type> (*this) = o; return *this; }
373
374 /* Iterator implementation. */
375
376 /* See comment in hb_array_of::operator != */
operator !=hb_sorted_array_t377 bool operator != (const hb_sorted_array_t& o) const
378 { return this->arrayZ != o.arrayZ || this->length != o.length; }
379
380 /* Faster range-based for loop without bounds-check. */
beginhb_sorted_array_t381 Type *begin () const { return this->arrayZ; }
endhb_sorted_array_t382 Type *end () const { return this->arrayZ + this->length; }
383
384
sub_arrayhb_sorted_array_t385 hb_sorted_array_t sub_array (unsigned int start_offset, unsigned int *seg_count /* IN/OUT */) const
386 { return hb_sorted_array_t (((const hb_array_t<Type> *) (this))->sub_array (start_offset, seg_count)); }
sub_arrayhb_sorted_array_t387 hb_sorted_array_t sub_array (unsigned int start_offset, unsigned int seg_count) const
388 { return sub_array (start_offset, &seg_count); }
389
truncatehb_sorted_array_t390 hb_sorted_array_t truncate (unsigned length) const { return sub_array (0, length); }
391
392 template <typename T>
bsearchhb_sorted_array_t393 Type *bsearch (const T &x, Type *not_found = nullptr)
394 {
395 unsigned int i;
396 return bfind (x, &i) ? &this->arrayZ[i] : not_found;
397 }
398 template <typename T>
bsearchhb_sorted_array_t399 const Type *bsearch (const T &x, const Type *not_found = nullptr) const
400 {
401 unsigned int i;
402 return bfind (x, &i) ? &this->arrayZ[i] : not_found;
403 }
404 template <typename T>
bfindhb_sorted_array_t405 bool bfind (const T &x, unsigned int *i = nullptr,
406 hb_not_found_t not_found = HB_NOT_FOUND_DONT_STORE,
407 unsigned int to_store = (unsigned int) -1) const
408 {
409 unsigned pos;
410
411 if (bsearch_impl (x, &pos))
412 {
413 if (i)
414 *i = pos;
415 return true;
416 }
417
418 if (i)
419 {
420 switch (not_found)
421 {
422 case HB_NOT_FOUND_DONT_STORE:
423 break;
424
425 case HB_NOT_FOUND_STORE:
426 *i = to_store;
427 break;
428
429 case HB_NOT_FOUND_STORE_CLOSEST:
430 *i = pos;
431 break;
432 }
433 }
434 return false;
435 }
436 template <typename T, typename ...Ts>
bsearch_implhb_sorted_array_t437 bool bsearch_impl (const T &x, unsigned *pos, Ts... ds) const
438 {
439 return hb_bsearch_impl (pos,
440 x,
441 this->arrayZ,
442 this->length,
443 sizeof (Type),
444 _hb_cmp_method<T, Type, Ts...>,
445 std::forward<Ts> (ds)...);
446 }
447 };
448 template <typename T> inline hb_sorted_array_t<T>
hb_sorted_array(T * array,unsigned int length)449 hb_sorted_array (T *array, unsigned int length)
450 { return hb_sorted_array_t<T> (array, length); }
451 template <typename T, unsigned int length_> inline hb_sorted_array_t<T>
hb_sorted_array(T (& array_)[length_])452 hb_sorted_array (T (&array_)[length_])
453 { return hb_sorted_array_t<T> (array_); }
454
455 template <typename T>
operator ==(const hb_array_t<T> & o) const456 inline bool hb_array_t<T>::operator == (const hb_array_t<T> &o) const
457 {
458 if (o.length != this->length) return false;
459 for (unsigned int i = 0; i < this->length; i++) {
460 if (this->arrayZ[i] != o.arrayZ[i]) return false;
461 }
462 return true;
463 }
464 template <>
operator ==(const hb_array_t<const char> & o) const465 inline bool hb_array_t<const char>::operator == (const hb_array_t<const char> &o) const
466 {
467 if (o.length != this->length) return false;
468 return 0 == hb_memcmp (arrayZ, o.arrayZ, length);
469 }
470 template <>
operator ==(const hb_array_t<const unsigned char> & o) const471 inline bool hb_array_t<const unsigned char>::operator == (const hb_array_t<const unsigned char> &o) const
472 {
473 if (o.length != this->length) return false;
474 return 0 == hb_memcmp (arrayZ, o.arrayZ, length);
475 }
476
477
478 /* Specialize hash() for byte arrays. */
479
480 #ifndef HB_OPTIMIZE_SIZE_MORE
481 template <>
hash() const482 inline uint32_t hb_array_t<const char>::hash () const
483 {
484 // https://github.com/harfbuzz/harfbuzz/pull/4228
485 return fasthash32(arrayZ, length, 0xf437ffe6 /* magic? */);
486 }
487
488 template <>
hash() const489 inline uint32_t hb_array_t<const unsigned char>::hash () const
490 {
491 // https://github.com/harfbuzz/harfbuzz/pull/4228
492 return fasthash32(arrayZ, length, 0xf437ffe6 /* magic? */);
493 }
494 #endif
495
496
497 typedef hb_array_t<const char> hb_bytes_t;
498 typedef hb_array_t<const unsigned char> hb_ubytes_t;
499
500
501
502 #endif /* HB_ARRAY_HH */
503