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 static constexpr bool realloc_move = true;
51
52 /*
53 * Constructors.
54 */
55 hb_array_t () = default;
56 hb_array_t (const hb_array_t&) = default;
57 ~hb_array_t () = default;
58 hb_array_t& operator= (const hb_array_t&) = default;
59 hb_array_t& operator= (hb_array_t&&) = default;
60
hb_array_thb_array_t61 constexpr hb_array_t (Type *array_, unsigned int length_) : arrayZ (array_), length (length_) {}
62 template <unsigned int length_>
hb_array_thb_array_t63 constexpr hb_array_t (Type (&array_)[length_]) : hb_array_t (array_, length_) {}
64
65 template <typename U,
66 hb_enable_if (hb_is_cr_convertible(U, Type))>
hb_array_thb_array_t67 constexpr hb_array_t (const hb_array_t<U> &o) :
68 hb_iter_with_fallback_t<hb_array_t, Type&> (),
69 arrayZ (o.arrayZ), length (o.length), backwards_length (o.backwards_length) {}
70 template <typename U,
71 hb_enable_if (hb_is_cr_convertible(U, Type))>
operator =hb_array_t72 hb_array_t& operator = (const hb_array_t<U> &o)
73 { arrayZ = o.arrayZ; length = o.length; backwards_length = o.backwards_length; return *this; }
74
75 /*
76 * Iterator implementation.
77 */
78 typedef Type& __item_t__;
79 static constexpr bool is_random_access_iterator = true;
80 static constexpr bool has_fast_len = true;
__item__hb_array_t81 Type& __item__ () const
82 {
83 if (unlikely (!length)) return CrapOrNull (Type);
84 return *arrayZ;
85 }
__item_at__hb_array_t86 Type& __item_at__ (unsigned i) const
87 {
88 if (unlikely (i >= length)) return CrapOrNull (Type);
89 return arrayZ[i];
90 }
__next__hb_array_t91 void __next__ ()
92 {
93 if (unlikely (!length))
94 return;
95 length--;
96 backwards_length++;
97 arrayZ++;
98 }
__forward__hb_array_t99 void __forward__ (unsigned n)
100 {
101 if (unlikely (n > length))
102 n = length;
103 length -= n;
104 backwards_length += n;
105 arrayZ += n;
106 }
__prev__hb_array_t107 void __prev__ ()
108 {
109 if (unlikely (!backwards_length))
110 return;
111 length++;
112 backwards_length--;
113 arrayZ--;
114 }
__rewind__hb_array_t115 void __rewind__ (unsigned n)
116 {
117 if (unlikely (n > backwards_length))
118 n = backwards_length;
119 length += n;
120 backwards_length -= n;
121 arrayZ -= n;
122 }
__len__hb_array_t123 unsigned __len__ () const { return length; }
124 /* Ouch. The operator== compares the contents of the array. For range-based for loops,
125 * it's best if we can just compare arrayZ, though comparing contents is still fast,
126 * but also would require that Type has operator==. As such, we optimize this operator
127 * for range-based for loop and just compare arrayZ and length.
128 *
129 * The above comment is outdated now because we implemented separate begin/end to
130 * objects that were using hb_array_t for range-based loop before. */
operator !=hb_array_t131 bool operator != (const hb_array_t& o) const
132 { return this->arrayZ != o.arrayZ || this->length != o.length; }
133
134 /* Faster range-based for loop without bounds-check. */
beginhb_array_t135 Type *begin () const { return arrayZ; }
endhb_array_t136 Type *end () const { return arrayZ + length; }
137
138
139 /* Extra operators.
140 */
operator &hb_array_t141 Type * operator & () const { return arrayZ; }
operator hb_array_t<const Type>hb_array_t142 operator hb_array_t<const Type> () { return hb_array_t<const Type> (arrayZ, length); }
operator T*hb_array_t143 template <typename T> operator T * () const { return arrayZ; }
144
145 HB_INTERNAL bool operator == (const hb_array_t &o) const;
146
hashhb_array_t147 uint32_t hash () const
148 {
149 // FNV-1a hash function
150 // https://github.com/harfbuzz/harfbuzz/pull/4228
151 uint32_t current = /*cbf29ce4*/0x84222325;
152 for (auto &v : *this)
153 {
154 current = current ^ hb_hash (v);
155 current = current * 16777619;
156 }
157 return current;
158 }
159
160 /*
161 * Compare, Sort, and Search.
162 */
163
164 /* Note: our compare is NOT lexicographic; it also does NOT call Type::cmp. */
cmphb_array_t165 int cmp (const hb_array_t &a) const
166 {
167 if (length != a.length)
168 return (int) a.length - (int) length;
169 return hb_memcmp (a.arrayZ, arrayZ, get_size ());
170 }
cmphb_array_t171 HB_INTERNAL static int cmp (const void *pa, const void *pb)
172 {
173 hb_array_t *a = (hb_array_t *) pa;
174 hb_array_t *b = (hb_array_t *) pb;
175 return b->cmp (*a);
176 }
177
178 template <typename T>
lsearchhb_array_t179 Type *lsearch (const T &x, Type *not_found = nullptr)
180 {
181 unsigned i;
182 return lfind (x, &i) ? &this->arrayZ[i] : not_found;
183 }
184 template <typename T>
lsearchhb_array_t185 const Type *lsearch (const T &x, const Type *not_found = nullptr) const
186 {
187 unsigned i;
188 return lfind (x, &i) ? &this->arrayZ[i] : not_found;
189 }
190 template <typename T>
lfindhb_array_t191 bool lfind (const T &x, unsigned *pos = nullptr,
192 hb_not_found_t not_found = HB_NOT_FOUND_DONT_STORE,
193 unsigned int to_store = (unsigned int) -1) const
194 {
195 for (unsigned i = 0; i < length; ++i)
196 if (hb_equal (x, this->arrayZ[i]))
197 {
198 if (pos)
199 *pos = i;
200 return true;
201 }
202
203 if (pos)
204 {
205 switch (not_found)
206 {
207 case HB_NOT_FOUND_DONT_STORE:
208 break;
209
210 case HB_NOT_FOUND_STORE:
211 *pos = to_store;
212 break;
213
214 case HB_NOT_FOUND_STORE_CLOSEST:
215 *pos = length;
216 break;
217 }
218 }
219 return false;
220 }
221
qsorthb_array_t222 hb_sorted_array_t<Type> qsort (int (*cmp_)(const void*, const void*))
223 {
224 //static_assert (hb_enable_if (hb_is_trivially_copy_assignable(Type)), "");
225 if (likely (length))
226 hb_qsort (arrayZ, length, this->get_item_size (), cmp_);
227 return hb_sorted_array_t<Type> (*this);
228 }
qsorthb_array_t229 hb_sorted_array_t<Type> qsort ()
230 {
231 //static_assert (hb_enable_if (hb_is_trivially_copy_assignable(Type)), "");
232 if (likely (length))
233 hb_qsort (arrayZ, length, this->get_item_size (), Type::cmp);
234 return hb_sorted_array_t<Type> (*this);
235 }
236
237 /*
238 * Other methods.
239 */
240
get_sizehb_array_t241 unsigned int get_size () const { return length * this->get_item_size (); }
242
243 /*
244 * Reverse the order of items in this array in the range [start, end).
245 */
reversehb_array_t246 void reverse (unsigned start = 0, unsigned end = -1)
247 {
248 start = hb_min (start, length);
249 end = hb_min (end, length);
250
251 if (end < start + 2)
252 return;
253
254 for (unsigned lhs = start, rhs = end - 1; lhs < rhs; lhs++, rhs--)
255 hb_swap (arrayZ[rhs], arrayZ[lhs]);
256 }
257
sub_arrayhb_array_t258 hb_array_t sub_array (unsigned int start_offset = 0, unsigned int *seg_count = nullptr /* IN/OUT */) const
259 {
260 if (!start_offset && !seg_count)
261 return *this;
262
263 unsigned int count = length;
264 if (unlikely (start_offset > count))
265 count = 0;
266 else
267 count -= start_offset;
268 if (seg_count)
269 count = *seg_count = hb_min (count, *seg_count);
270 return hb_array_t (arrayZ + start_offset, count);
271 }
sub_arrayhb_array_t272 hb_array_t sub_array (unsigned int start_offset, unsigned int seg_count) const
273 { return sub_array (start_offset, &seg_count); }
274
truncatehb_array_t275 hb_array_t truncate (unsigned length) const { return sub_array (0, length); }
276
277 template <typename T,
278 unsigned P = sizeof (Type),
279 hb_enable_if (P == 1)>
ashb_array_t280 const T *as () const
281 { return length < hb_min_size (T) ? &Null (T) : reinterpret_cast<const T *> (arrayZ); }
282
283 template <typename T,
284 unsigned P = sizeof (Type),
285 hb_enable_if (P == 1)>
check_rangehb_array_t286 bool check_range (const T *p, unsigned int size = T::static_size) const
287 {
288 return arrayZ <= ((const char *) p)
289 && ((const char *) p) <= arrayZ + length
290 && (unsigned int) (arrayZ + length - (const char *) p) >= size;
291 }
292
293 /* Only call if you allocated the underlying array using hb_malloc() or similar. */
finihb_array_t294 void fini ()
295 { hb_free ((void *) arrayZ); arrayZ = nullptr; length = 0; }
296
297 template <typename hb_serialize_context_t,
298 typename U = Type,
299 hb_enable_if (!(sizeof (U) < sizeof (long long) && hb_is_trivially_copy_assignable(hb_decay<Type>)))>
copyhb_array_t300 hb_array_t copy (hb_serialize_context_t *c) const
301 {
302 TRACE_SERIALIZE (this);
303 auto* out = c->start_embed (arrayZ);
304 if (unlikely (!c->extend_size (out, get_size (), false))) return_trace (hb_array_t ());
305 for (unsigned i = 0; i < length; i++)
306 out[i] = arrayZ[i]; /* TODO: add version that calls c->copy() */
307 return_trace (hb_array_t (out, length));
308 }
309
310 template <typename hb_serialize_context_t,
311 typename U = Type,
312 hb_enable_if (sizeof (U) < sizeof (long long) && hb_is_trivially_copy_assignable(hb_decay<Type>))>
copyhb_array_t313 hb_array_t copy (hb_serialize_context_t *c) const
314 {
315 TRACE_SERIALIZE (this);
316 auto* out = c->start_embed (arrayZ);
317 if (unlikely (!c->extend_size (out, get_size (), false))) return_trace (hb_array_t ());
318 hb_memcpy (out, arrayZ, get_size ());
319 return_trace (hb_array_t (out, length));
320 }
321
322 template <typename hb_sanitize_context_t>
sanitizehb_array_t323 bool sanitize (hb_sanitize_context_t *c) const
324 { return c->check_array (arrayZ, length); }
325
326 /*
327 * Members
328 */
329
330 public:
331 Type *arrayZ = nullptr;
332 unsigned int length = 0;
333 unsigned int backwards_length = 0;
334 };
335 template <typename T> inline hb_array_t<T>
hb_array()336 hb_array ()
337 { return hb_array_t<T> (); }
338 template <typename T> inline hb_array_t<T>
hb_array(T * array,unsigned int length)339 hb_array (T *array, unsigned int length)
340 { return hb_array_t<T> (array, length); }
341 template <typename T, unsigned int length_> inline hb_array_t<T>
hb_array(T (& array_)[length_])342 hb_array (T (&array_)[length_])
343 { return hb_array_t<T> (array_); }
344
345 template <typename Type>
346 struct hb_sorted_array_t :
347 hb_array_t<Type>,
348 hb_iter_t<hb_sorted_array_t<Type>, Type&>
349 {
350 typedef hb_iter_t<hb_sorted_array_t, Type&> iter_base_t;
351 HB_ITER_USING (iter_base_t);
352 static constexpr bool is_random_access_iterator = true;
353 static constexpr bool is_sorted_iterator = true;
354 static constexpr bool has_fast_len = true;
355
356 hb_sorted_array_t () = default;
357 hb_sorted_array_t (const hb_sorted_array_t&) = default;
358 ~hb_sorted_array_t () = default;
359 hb_sorted_array_t& operator= (const hb_sorted_array_t&) = default;
360 hb_sorted_array_t& operator= (hb_sorted_array_t&&) = default;
361
hb_sorted_array_thb_sorted_array_t362 constexpr hb_sorted_array_t (Type *array_, unsigned int length_) : hb_array_t<Type> (array_, length_) {}
363 template <unsigned int length_>
hb_sorted_array_thb_sorted_array_t364 constexpr hb_sorted_array_t (Type (&array_)[length_]) : hb_array_t<Type> (array_) {}
365
366 template <typename U,
367 hb_enable_if (hb_is_cr_convertible(U, Type))>
hb_sorted_array_thb_sorted_array_t368 constexpr hb_sorted_array_t (const hb_array_t<U> &o) :
369 hb_array_t<Type> (o),
370 hb_iter_t<hb_sorted_array_t, Type&> () {}
371 template <typename U,
372 hb_enable_if (hb_is_cr_convertible(U, Type))>
operator =hb_sorted_array_t373 hb_sorted_array_t& operator = (const hb_array_t<U> &o)
374 { hb_array_t<Type> (*this) = o; return *this; }
375
376 /* Iterator implementation. */
377
378 /* See comment in hb_array_of::operator != */
operator !=hb_sorted_array_t379 bool operator != (const hb_sorted_array_t& o) const
380 { return this->arrayZ != o.arrayZ || this->length != o.length; }
381
382 /* Faster range-based for loop without bounds-check. */
beginhb_sorted_array_t383 Type *begin () const { return this->arrayZ; }
endhb_sorted_array_t384 Type *end () const { return this->arrayZ + this->length; }
385
386
sub_arrayhb_sorted_array_t387 hb_sorted_array_t sub_array (unsigned int start_offset, unsigned int *seg_count /* IN/OUT */) const
388 { return hb_sorted_array_t (((const hb_array_t<Type> *) (this))->sub_array (start_offset, seg_count)); }
sub_arrayhb_sorted_array_t389 hb_sorted_array_t sub_array (unsigned int start_offset, unsigned int seg_count) const
390 { return sub_array (start_offset, &seg_count); }
391
truncatehb_sorted_array_t392 hb_sorted_array_t truncate (unsigned length) const { return sub_array (0, length); }
393
394 template <typename T>
bsearchhb_sorted_array_t395 Type *bsearch (const T &x, Type *not_found = nullptr)
396 {
397 unsigned int i;
398 return bfind (x, &i) ? &this->arrayZ[i] : not_found;
399 }
400 template <typename T>
bsearchhb_sorted_array_t401 const Type *bsearch (const T &x, const Type *not_found = nullptr) const
402 {
403 unsigned int i;
404 return bfind (x, &i) ? &this->arrayZ[i] : not_found;
405 }
406 template <typename T>
bfindhb_sorted_array_t407 bool bfind (const T &x, unsigned int *i = nullptr,
408 hb_not_found_t not_found = HB_NOT_FOUND_DONT_STORE,
409 unsigned int to_store = (unsigned int) -1) const
410 {
411 unsigned pos;
412
413 if (bsearch_impl (x, &pos))
414 {
415 if (i)
416 *i = pos;
417 return true;
418 }
419
420 if (i)
421 {
422 switch (not_found)
423 {
424 case HB_NOT_FOUND_DONT_STORE:
425 break;
426
427 case HB_NOT_FOUND_STORE:
428 *i = to_store;
429 break;
430
431 case HB_NOT_FOUND_STORE_CLOSEST:
432 *i = pos;
433 break;
434 }
435 }
436 return false;
437 }
438 template <typename T, typename ...Ts>
bsearch_implhb_sorted_array_t439 bool bsearch_impl (const T &x, unsigned *pos, Ts... ds) const
440 {
441 return hb_bsearch_impl (pos,
442 x,
443 this->arrayZ,
444 this->length,
445 sizeof (Type),
446 _hb_cmp_method<T, Type, Ts...>,
447 std::forward<Ts> (ds)...);
448 }
449 };
450 template <typename T> inline hb_sorted_array_t<T>
hb_sorted_array(T * array,unsigned int length)451 hb_sorted_array (T *array, unsigned int length)
452 { return hb_sorted_array_t<T> (array, length); }
453 template <typename T, unsigned int length_> inline hb_sorted_array_t<T>
hb_sorted_array(T (& array_)[length_])454 hb_sorted_array (T (&array_)[length_])
455 { return hb_sorted_array_t<T> (array_); }
456
457 template <typename T>
operator ==(const hb_array_t<T> & o) const458 inline bool hb_array_t<T>::operator == (const hb_array_t<T> &o) const
459 {
460 if (o.length != this->length) return false;
461 for (unsigned int i = 0; i < this->length; i++) {
462 if (this->arrayZ[i] != o.arrayZ[i]) return false;
463 }
464 return true;
465 }
466 template <>
operator ==(const hb_array_t<const char> & o) const467 inline bool hb_array_t<const char>::operator == (const hb_array_t<const char> &o) const
468 {
469 if (o.length != this->length) return false;
470 return 0 == hb_memcmp (arrayZ, o.arrayZ, length);
471 }
472 template <>
operator ==(const hb_array_t<const unsigned char> & o) const473 inline bool hb_array_t<const unsigned char>::operator == (const hb_array_t<const unsigned char> &o) const
474 {
475 if (o.length != this->length) return false;
476 return 0 == hb_memcmp (arrayZ, o.arrayZ, length);
477 }
478
479
480 /* Specialize hash() for byte arrays. */
481
482 #ifndef HB_OPTIMIZE_SIZE_MORE
483 template <>
hash() const484 inline uint32_t hb_array_t<const char>::hash () const
485 {
486 // https://github.com/harfbuzz/harfbuzz/pull/4228
487 return fasthash32(arrayZ, length, 0xf437ffe6 /* magic? */);
488 }
489
490 template <>
hash() const491 inline uint32_t hb_array_t<const unsigned char>::hash () const
492 {
493 // https://github.com/harfbuzz/harfbuzz/pull/4228
494 return fasthash32(arrayZ, length, 0xf437ffe6 /* magic? */);
495 }
496 #endif
497
498
499 typedef hb_array_t<const char> hb_bytes_t;
500 typedef hb_array_t<const unsigned char> hb_ubytes_t;
501
502
503
504 #endif /* HB_ARRAY_HH */
505