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
32
33 template <typename Type>
34 struct hb_sorted_array_t;
35
36 template <typename Type>
37 struct hb_array_t
38 {
39 typedef Type ItemType;
40 enum { item_size = hb_static_size (Type) };
41
42 /*
43 * Constructors.
44 */
hb_array_thb_array_t45 hb_array_t () : arrayZ (nullptr), len (0) {}
hb_array_thb_array_t46 hb_array_t (const hb_array_t &o) : arrayZ (o.arrayZ), len (o.len) {}
hb_array_thb_array_t47 hb_array_t (Type *array_, unsigned int len_) : arrayZ (array_), len (len_) {}
hb_array_thb_array_t48 template <unsigned int len_> hb_array_t (Type (&array_)[len_]) : arrayZ (array_), len (len_) {}
49
50 /*
51 * Operators.
52 */
53
operator []hb_array_t54 Type& operator [] (int i_) const
55 {
56 unsigned int i = (unsigned int) i_;
57 if (unlikely (i >= len)) return CrapOrNull(Type);
58 return arrayZ[i];
59 }
60
61 explicit_operator bool () const { return len; }
operator &hb_array_t62 Type * operator & () const { return arrayZ; }
operator *hb_array_t63 Type & operator * () { return (this->operator [])[0]; }
operator hb_array_t<const Type>hb_array_t64 operator hb_array_t<const Type> () { return hb_array_t<const Type> (arrayZ, len); }
operator T*hb_array_t65 template <typename T> operator T * () const { return arrayZ; }
66
operator +=hb_array_t67 hb_array_t<Type> & operator += (unsigned int count)
68 {
69 if (unlikely (count > len))
70 count = len;
71 len -= count;
72 arrayZ += count;
73 return *this;
74 }
operator -=hb_array_t75 hb_array_t<Type> & operator -= (unsigned int count)
76 {
77 if (unlikely (count > len))
78 count = len;
79 len -= count;
80 return *this;
81 }
operator ++hb_array_t82 hb_array_t<Type> & operator ++ () { *this += 1; }
operator --hb_array_t83 hb_array_t<Type> & operator -- () { *this -= 1; }
operator +hb_array_t84 hb_array_t<Type> operator + (unsigned int count)
85 { hb_array_t<Type> copy (*this); *this += count; return copy; }
operator -hb_array_t86 hb_array_t<Type> operator - (unsigned int count)
87 { hb_array_t<Type> copy (*this); *this -= count; return copy; }
operator ++hb_array_t88 hb_array_t<Type> operator ++ (int)
89 { hb_array_t<Type> copy (*this); ++*this; return copy; }
operator --hb_array_t90 hb_array_t<Type> operator -- (int)
91 { hb_array_t<Type> copy (*this); --*this; return copy; }
92
93 /*
94 * Compare, Sort, and Search.
95 */
96
97 /* Note: our compare is NOT lexicographic; it also does NOT call Type::cmp. */
cmphb_array_t98 int cmp (const hb_array_t<Type> &a) const
99 {
100 if (len != a.len)
101 return (int) a.len - (int) len;
102 return hb_memcmp (a.arrayZ, arrayZ, get_size ());
103 }
cmphb_array_t104 static int cmp (const void *pa, const void *pb)
105 {
106 hb_array_t<Type> *a = (hb_array_t<Type> *) pa;
107 hb_array_t<Type> *b = (hb_array_t<Type> *) pb;
108 return b->cmp (*a);
109 }
110
111 template <typename T>
lsearchhb_array_t112 Type *lsearch (const T &x, Type *not_found = nullptr)
113 {
114 unsigned int count = len;
115 for (unsigned int i = 0; i < count; i++)
116 if (!this->arrayZ[i].cmp (x))
117 return &this->arrayZ[i];
118 return not_found;
119 }
120 template <typename T>
lsearchhb_array_t121 const Type *lsearch (const T &x, const Type *not_found = nullptr) const
122 {
123 unsigned int count = len;
124 for (unsigned int i = 0; i < count; i++)
125 if (!this->arrayZ[i].cmp (x))
126 return &this->arrayZ[i];
127 return not_found;
128 }
129
qsorthb_array_t130 hb_sorted_array_t<Type> qsort (int (*cmp_)(const void*, const void*))
131 {
132 ::qsort (arrayZ, len, item_size, cmp_);
133 return hb_sorted_array_t<Type> (*this);
134 }
qsorthb_array_t135 hb_sorted_array_t<Type> qsort ()
136 {
137 ::qsort (arrayZ, len, item_size, Type::cmp);
138 return hb_sorted_array_t<Type> (*this);
139 }
qsorthb_array_t140 void qsort (unsigned int start, unsigned int end)
141 {
142 end = MIN (end, len);
143 assert (start <= end);
144 ::qsort (arrayZ + start, end - start, item_size, Type::cmp);
145 }
146
147 /*
148 * Other methods.
149 */
150
get_sizehb_array_t151 unsigned int get_size () const { return len * item_size; }
152
sub_arrayhb_array_t153 hb_array_t<Type> sub_array (unsigned int start_offset = 0, unsigned int *seg_count = nullptr /* IN/OUT */) const
154 {
155 if (!start_offset && !seg_count)
156 return *this;
157
158 unsigned int count = len;
159 if (unlikely (start_offset > count))
160 count = 0;
161 else
162 count -= start_offset;
163 if (seg_count)
164 count = *seg_count = MIN (count, *seg_count);
165 return hb_array_t<Type> (arrayZ + start_offset, count);
166 }
sub_arrayhb_array_t167 hb_array_t<Type> sub_array (unsigned int start_offset, unsigned int seg_count) const
168 { return sub_array (start_offset, &seg_count); }
169
170 /* Only call if you allocated the underlying array using malloc() or similar. */
freehb_array_t171 void free ()
172 { ::free ((void *) arrayZ); arrayZ = nullptr; len = 0; }
173
174 template <typename hb_sanitize_context_t>
sanitizehb_array_t175 bool sanitize (hb_sanitize_context_t *c) const
176 { return c->check_array (arrayZ, len); }
177
178 /*
179 * Members
180 */
181
182 public:
183 Type *arrayZ;
184 unsigned int len;
185 };
186 template <typename T>
hb_array(T * array,unsigned int len)187 inline hb_array_t<T> hb_array (T *array, unsigned int len)
188 { return hb_array_t<T> (array, len); }
189
190
191 enum hb_bfind_not_found_t
192 {
193 HB_BFIND_NOT_FOUND_DONT_STORE,
194 HB_BFIND_NOT_FOUND_STORE,
195 HB_BFIND_NOT_FOUND_STORE_CLOSEST,
196 };
197
198 template <typename Type>
199 struct hb_sorted_array_t : hb_array_t<Type>
200 {
hb_sorted_array_thb_sorted_array_t201 hb_sorted_array_t () : hb_array_t<Type> () {}
hb_sorted_array_thb_sorted_array_t202 hb_sorted_array_t (const hb_array_t<Type> &o) : hb_array_t<Type> (o) {}
hb_sorted_array_thb_sorted_array_t203 hb_sorted_array_t (Type *array_, unsigned int len_) : hb_array_t<Type> (array_, len_) {}
204
sub_arrayhb_sorted_array_t205 hb_sorted_array_t<Type> sub_array (unsigned int start_offset, unsigned int *seg_count /* IN/OUT */) const
206 { return hb_sorted_array_t<Type> (((const hb_array_t<Type> *) (this))->sub_array (start_offset, seg_count)); }
sub_arrayhb_sorted_array_t207 hb_sorted_array_t<Type> sub_array (unsigned int start_offset, unsigned int seg_count) const
208 { return sub_array (start_offset, &seg_count); }
209
210 template <typename T>
bsearchhb_sorted_array_t211 Type *bsearch (const T &x, Type *not_found = nullptr)
212 {
213 unsigned int i;
214 return bfind (x, &i) ? &this->arrayZ[i] : not_found;
215 }
216 template <typename T>
bsearchhb_sorted_array_t217 const Type *bsearch (const T &x, const Type *not_found = nullptr) const
218 {
219 unsigned int i;
220 return bfind (x, &i) ? &this->arrayZ[i] : not_found;
221 }
222 template <typename T>
bfindhb_sorted_array_t223 bool bfind (const T &x, unsigned int *i = nullptr,
224 hb_bfind_not_found_t not_found = HB_BFIND_NOT_FOUND_DONT_STORE,
225 unsigned int to_store = (unsigned int) -1) const
226 {
227 int min = 0, max = (int) this->len - 1;
228 const Type *array = this->arrayZ;
229 while (min <= max)
230 {
231 int mid = ((unsigned int) min + (unsigned int) max) / 2;
232 int c = array[mid].cmp (x);
233 if (c < 0)
234 max = mid - 1;
235 else if (c > 0)
236 min = mid + 1;
237 else
238 {
239 if (i)
240 *i = mid;
241 return true;
242 }
243 }
244 if (i)
245 {
246 switch (not_found)
247 {
248 case HB_BFIND_NOT_FOUND_DONT_STORE:
249 break;
250
251 case HB_BFIND_NOT_FOUND_STORE:
252 *i = to_store;
253 break;
254
255 case HB_BFIND_NOT_FOUND_STORE_CLOSEST:
256 if (max < 0 || (max < (int) this->len && array[max].cmp (x) > 0))
257 max++;
258 *i = max;
259 break;
260 }
261 }
262 return false;
263 }
264 };
265 template <typename T>
hb_sorted_array(T * array,unsigned int len)266 inline hb_sorted_array_t<T> hb_sorted_array (T *array, unsigned int len)
267 { return hb_sorted_array_t<T> (array, len); }
268
269
270 typedef hb_array_t<const char> hb_bytes_t;
271 typedef hb_array_t<const unsigned char> hb_ubytes_t;
272
273
274 #endif /* HB_ARRAY_HH */
275