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 template <typename Type> struct hb_sorted_array_t;
36
37 template <typename Type> struct hb_array_t : hb_iter_with_fallback_t<hb_array_t<Type>, Type &>
38 {
39 /*
40 * Constructors.
41 */
hb_array_thb_array_t42 hb_array_t()
43 : arrayZ(nullptr)
44 , length(0)
45 , backwards_length(0)
46 {
47 }
hb_array_thb_array_t48 hb_array_t(Type *array_, unsigned int length_)
49 : arrayZ(array_)
50 , length(length_)
51 , backwards_length(0)
52 {
53 }
54 template <unsigned int length_>
hb_array_thb_array_t55 hb_array_t(Type (&array_)[length_])
56 : arrayZ(array_)
57 , length(length_)
58 , backwards_length(0)
59 {
60 }
61
62 template <typename U, hb_enable_if(hb_is_cr_convertible(U, Type))>
hb_array_thb_array_t63 hb_array_t(const hb_array_t<U> &o)
64 : hb_iter_with_fallback_t<hb_array_t, Type &>()
65 , arrayZ(o.arrayZ)
66 , length(o.length)
67 , backwards_length(o.backwards_length)
68 {
69 }
operator =hb_array_t70 template <typename U, hb_enable_if(hb_is_cr_convertible(U, Type))> hb_array_t &operator=(const hb_array_t<U> &o)
71 {
72 arrayZ = o.arrayZ;
73 length = o.length;
74 backwards_length = o.backwards_length;
75 return *this;
76 }
77
78 /*
79 * Iterator implementation.
80 */
81 typedef Type &__item_t__;
82 static constexpr bool is_random_access_iterator = true;
__item_at__hb_array_t83 Type &__item_at__(unsigned i) const
84 {
85 if (unlikely(i >= length))
86 return CrapOrNull(Type);
87 return arrayZ[i];
88 }
__forward__hb_array_t89 void __forward__(unsigned n)
90 {
91 if (unlikely(n > length))
92 n = length;
93 length -= n;
94 backwards_length += n;
95 arrayZ += n;
96 }
__rewind__hb_array_t97 void __rewind__(unsigned n)
98 {
99 if (unlikely(n > backwards_length))
100 n = backwards_length;
101 length += n;
102 backwards_length -= n;
103 arrayZ -= n;
104 }
__len__hb_array_t105 unsigned __len__() const
106 {
107 return length;
108 }
109 /* Ouch. The operator== compares the contents of the array. For range-based for loops,
110 * it's best if we can just compare arrayZ, though comparing contents is still fast,
111 * but also would require that Type has operator==. As such, we optimize this operator
112 * for range-based for loop and just compare arrayZ. No need to compare length, as we
113 * assume we're only compared to .end(). */
operator !=hb_array_t114 bool operator!=(const hb_array_t &o) const
115 {
116 return arrayZ != o.arrayZ;
117 }
118
119 /* Extra operators.
120 */
operator &hb_array_t121 Type *operator&() const
122 {
123 return arrayZ;
124 }
operator hb_array_t<const Type>hb_array_t125 operator hb_array_t<const Type>()
126 {
127 return hb_array_t<const Type>(arrayZ, length);
128 }
operator T*hb_array_t129 template <typename T> operator T *() const
130 {
131 return arrayZ;
132 }
133
134 HB_INTERNAL bool operator==(const hb_array_t &o) const;
135
hashhb_array_t136 uint32_t hash() const
137 {
138 uint32_t current = 0;
139 for (unsigned int i = 0; i < this->length; i++) {
140 current = current * 31 + hb_hash(this->arrayZ[i]);
141 }
142 return current;
143 }
144
145 /*
146 * Compare, Sort, and Search.
147 */
148
149 /* Note: our compare is NOT lexicographic; it also does NOT call Type::cmp. */
cmphb_array_t150 int cmp(const hb_array_t &a) const
151 {
152 if (length != a.length)
153 return (int)a.length - (int)length;
154 return hb_memcmp(a.arrayZ, arrayZ, get_size());
155 }
cmphb_array_t156 HB_INTERNAL static int cmp(const void *pa, const void *pb)
157 {
158 hb_array_t *a = (hb_array_t *)pa;
159 hb_array_t *b = (hb_array_t *)pb;
160 return b->cmp(*a);
161 }
162
lsearchhb_array_t163 template <typename T> Type *lsearch(const T &x, Type *not_found = nullptr)
164 {
165 unsigned int count = length;
166 for (unsigned int i = 0; i < count; i++)
167 if (!this->arrayZ[i].cmp(x))
168 return &this->arrayZ[i];
169 return not_found;
170 }
lsearchhb_array_t171 template <typename T> const Type *lsearch(const T &x, const Type *not_found = nullptr) const
172 {
173 unsigned int count = length;
174 for (unsigned int i = 0; i < count; i++)
175 if (!this->arrayZ[i].cmp(x))
176 return &this->arrayZ[i];
177 return not_found;
178 }
179
qsorthb_array_t180 hb_sorted_array_t<Type> qsort(int (*cmp_)(const void *, const void *))
181 {
182 if (likely(length))
183 hb_qsort(arrayZ, length, this->get_item_size(), cmp_);
184 return hb_sorted_array_t<Type>(*this);
185 }
qsorthb_array_t186 hb_sorted_array_t<Type> qsort()
187 {
188 if (likely(length))
189 hb_qsort(arrayZ, length, this->get_item_size(), Type::cmp);
190 return hb_sorted_array_t<Type>(*this);
191 }
qsorthb_array_t192 void qsort(unsigned int start, unsigned int end)
193 {
194 end = hb_min(end, length);
195 assert(start <= end);
196 if (likely(start < end))
197 hb_qsort(arrayZ + start, end - start, this->get_item_size(), Type::cmp);
198 }
199
200 /*
201 * Other methods.
202 */
203
get_sizehb_array_t204 unsigned int get_size() const
205 {
206 return length * this->get_item_size();
207 }
208
209 /*
210 * Reverse the order of items in this array in the range [start, end).
211 */
reversehb_array_t212 void reverse(unsigned start = 0, unsigned end = -1)
213 {
214 start = hb_min(start, length);
215 end = hb_min(end, length);
216
217 if (end < start + 2)
218 return;
219
220 for (unsigned lhs = start, rhs = end - 1; lhs < rhs; lhs++, rhs--) {
221 Type temp = arrayZ[rhs];
222 arrayZ[rhs] = arrayZ[lhs];
223 arrayZ[lhs] = temp;
224 }
225 }
226
sub_arrayhb_array_t227 hb_array_t sub_array(unsigned int start_offset = 0, unsigned int *seg_count = nullptr /* IN/OUT */) const
228 {
229 if (!start_offset && !seg_count)
230 return *this;
231
232 unsigned int count = length;
233 if (unlikely(start_offset > count))
234 count = 0;
235 else
236 count -= start_offset;
237 if (seg_count)
238 count = *seg_count = hb_min(count, *seg_count);
239 return hb_array_t(arrayZ + start_offset, count);
240 }
sub_arrayhb_array_t241 hb_array_t sub_array(unsigned int start_offset, unsigned int seg_count) const
242 {
243 return sub_array(start_offset, &seg_count);
244 }
245
truncatehb_array_t246 hb_array_t truncate(unsigned length) const
247 {
248 return sub_array(0, length);
249 }
250
ashb_array_t251 template <typename T, unsigned P = sizeof(Type), hb_enable_if(P == 1)> const T *as() const
252 {
253 return length < hb_null_size(T) ? &Null(T) : reinterpret_cast<const T *>(arrayZ);
254 }
255
256 template <typename T, unsigned P = sizeof(Type), hb_enable_if(P == 1)>
check_rangehb_array_t257 bool check_range(const T *p, unsigned int size = T::static_size) const
258 {
259 return arrayZ <= ((const char *)p) && ((const char *)p) <= arrayZ + length &&
260 (unsigned int)(arrayZ + length - (const char *)p) >= size;
261 }
262
263 /* Only call if you allocated the underlying array using malloc() or similar. */
freehb_array_t264 void free()
265 {
266 ::free((void *)arrayZ);
267 arrayZ = nullptr;
268 length = 0;
269 }
270
copyhb_array_t271 template <typename hb_serialize_context_t> hb_array_t copy(hb_serialize_context_t *c) const
272 {
273 TRACE_SERIALIZE(this);
274 auto *out = c->start_embed(arrayZ);
275 if (unlikely(!c->extend_size(out, get_size())))
276 return_trace(hb_array_t());
277 for (unsigned i = 0; i < length; i++)
278 out[i] = arrayZ[i]; /* TODO: add version that calls c->copy() */
279 return_trace(hb_array_t(out, length));
280 }
281
sanitizehb_array_t282 template <typename hb_sanitize_context_t> bool sanitize(hb_sanitize_context_t *c) const
283 {
284 return c->check_array(arrayZ, length);
285 }
286
287 /*
288 * Members
289 */
290
291 public:
292 Type *arrayZ;
293 unsigned int length;
294 unsigned int backwards_length;
295 };
hb_array(T * array,unsigned int length)296 template <typename T> inline hb_array_t<T> hb_array(T *array, unsigned int length)
297 {
298 return hb_array_t<T>(array, length);
299 }
hb_array(T (& array_)[length_])300 template <typename T, unsigned int length_> inline hb_array_t<T> hb_array(T (&array_)[length_])
301 {
302 return hb_array_t<T>(array_);
303 }
304
305 enum hb_bfind_not_found_t {
306 HB_BFIND_NOT_FOUND_DONT_STORE,
307 HB_BFIND_NOT_FOUND_STORE,
308 HB_BFIND_NOT_FOUND_STORE_CLOSEST,
309 };
310
311 template <typename Type> struct hb_sorted_array_t : hb_iter_t<hb_sorted_array_t<Type>, Type &>, hb_array_t<Type>
312 {
313 typedef hb_iter_t<hb_sorted_array_t, Type &> iter_base_t;
314 HB_ITER_USING(iter_base_t);
315 static constexpr bool is_random_access_iterator = true;
316 static constexpr bool is_sorted_iterator = true;
317
hb_sorted_array_thb_sorted_array_t318 hb_sorted_array_t()
319 : hb_array_t<Type>()
320 {
321 }
hb_sorted_array_thb_sorted_array_t322 hb_sorted_array_t(Type *array_, unsigned int length_)
323 : hb_array_t<Type>(array_, length_)
324 {
325 }
326 template <unsigned int length_>
hb_sorted_array_thb_sorted_array_t327 hb_sorted_array_t(Type (&array_)[length_])
328 : hb_array_t<Type>(array_)
329 {
330 }
331
332 template <typename U, hb_enable_if(hb_is_cr_convertible(U, Type))>
hb_sorted_array_thb_sorted_array_t333 hb_sorted_array_t(const hb_array_t<U> &o)
334 : hb_iter_t<hb_sorted_array_t, Type &>()
335 , hb_array_t<Type>(o)
336 {
337 }
338 template <typename U, hb_enable_if(hb_is_cr_convertible(U, Type))>
operator =hb_sorted_array_t339 hb_sorted_array_t &operator=(const hb_array_t<U> &o)
340 {
341 hb_array_t<Type>(*this) = o;
342 return *this;
343 }
344
345 /* Iterator implementation. */
operator !=hb_sorted_array_t346 bool operator!=(const hb_sorted_array_t &o) const
347 {
348 return this->arrayZ != o.arrayZ || this->length != o.length;
349 }
350
sub_arrayhb_sorted_array_t351 hb_sorted_array_t sub_array(unsigned int start_offset, unsigned int *seg_count /* IN/OUT */) const
352 {
353 return hb_sorted_array_t(((const hb_array_t<Type> *)(this))->sub_array(start_offset, seg_count));
354 }
sub_arrayhb_sorted_array_t355 hb_sorted_array_t sub_array(unsigned int start_offset, unsigned int seg_count) const
356 {
357 return sub_array(start_offset, &seg_count);
358 }
359
truncatehb_sorted_array_t360 hb_sorted_array_t truncate(unsigned length) const
361 {
362 return sub_array(0, length);
363 }
364
bsearchhb_sorted_array_t365 template <typename T> Type *bsearch(const T &x, Type *not_found = nullptr)
366 {
367 unsigned int i;
368 return bfind(x, &i) ? &this->arrayZ[i] : not_found;
369 }
bsearchhb_sorted_array_t370 template <typename T> const Type *bsearch(const T &x, const Type *not_found = nullptr) const
371 {
372 unsigned int i;
373 return bfind(x, &i) ? &this->arrayZ[i] : not_found;
374 }
375 template <typename T>
bfindhb_sorted_array_t376 bool bfind(const T &x,
377 unsigned int *i = nullptr,
378 hb_bfind_not_found_t not_found = HB_BFIND_NOT_FOUND_DONT_STORE,
379 unsigned int to_store = (unsigned int)-1) const
380 {
381 unsigned pos;
382
383 if (bsearch_impl(x, &pos)) {
384 if (i)
385 *i = pos;
386 return true;
387 }
388
389 if (i) {
390 switch (not_found) {
391 case HB_BFIND_NOT_FOUND_DONT_STORE:
392 break;
393
394 case HB_BFIND_NOT_FOUND_STORE:
395 *i = to_store;
396 break;
397
398 case HB_BFIND_NOT_FOUND_STORE_CLOSEST:
399 *i = pos;
400 break;
401 }
402 }
403 return false;
404 }
bsearch_implhb_sorted_array_t405 template <typename T> bool bsearch_impl(const T &x, unsigned *pos) const
406 {
407 return hb_bsearch_impl(pos, x, this->arrayZ, this->length, sizeof(Type), _hb_cmp_method<T, Type>);
408 }
409 };
hb_sorted_array(T * array,unsigned int length)410 template <typename T> inline hb_sorted_array_t<T> hb_sorted_array(T *array, unsigned int length)
411 {
412 return hb_sorted_array_t<T>(array, length);
413 }
hb_sorted_array(T (& array_)[length_])414 template <typename T, unsigned int length_> inline hb_sorted_array_t<T> hb_sorted_array(T (&array_)[length_])
415 {
416 return hb_sorted_array_t<T>(array_);
417 }
418
operator ==(const hb_array_t<T> & o) const419 template <typename T> bool hb_array_t<T>::operator==(const hb_array_t<T> &o) const
420 {
421 if (o.length != this->length)
422 return false;
423 for (unsigned int i = 0; i < this->length; i++) {
424 if (this->arrayZ[i] != o.arrayZ[i])
425 return false;
426 }
427 return true;
428 }
429
430 /* TODO Specialize opeator== for hb_bytes_t and hb_ubytes_t. */
431
hash() const432 template <> inline uint32_t hb_array_t<const char>::hash() const
433 {
434 uint32_t current = 0;
435 for (unsigned int i = 0; i < this->length; i++)
436 current = current * 31 + (uint32_t)(this->arrayZ[i] * 2654435761u);
437 return current;
438 }
439
hash() const440 template <> inline uint32_t hb_array_t<const unsigned char>::hash() const
441 {
442 uint32_t current = 0;
443 for (unsigned int i = 0; i < this->length; i++)
444 current = current * 31 + (uint32_t)(this->arrayZ[i] * 2654435761u);
445 return current;
446 }
447
448 typedef hb_array_t<const char> hb_bytes_t;
449 typedef hb_array_t<const unsigned char> hb_ubytes_t;
450
451 #endif /* HB_ARRAY_HH */
452