1/*
2 * Copyright © 2017,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_VECTOR_HH
28#define HB_VECTOR_HH
29
30#include "hb.hh"
31#include "hb-array.hh"
32#include "hb-null.hh"
33
34
35template <typename Type>
36struct hb_vector_t
37{
38 typedef Type item_t;
39 static constexpr unsigned item_size = hb_static_size (Type);
40
41 hb_vector_t () { init (); }
42 hb_vector_t (const hb_vector_t &o)
43 {
44 init ();
45 alloc (o.length);
46 hb_copy (o, *this);
47 }
48 hb_vector_t (hb_vector_t &&o)
49 {
50 allocated = o.allocated;
51 length = o.length;
52 arrayZ = o.arrayZ;
53 o.init ();
54 }
55 ~hb_vector_t () { fini (); }
56
57 private:
58 int allocated; /* == -1 means allocation failed. */
59 public:
60 unsigned int length;
61 public:
62 Type *arrayZ;
63
64 void init ()
65 {
66 allocated = length = 0;
67 arrayZ = nullptr;
68 }
69
70 void fini ()
71 {
72 free (arrayZ);
73 init ();
74 }
75 void fini_deep ()
76 {
77 unsigned int count = length;
78 for (unsigned int i = 0; i < count; i++)
79 arrayZ[i].fini ();
80 fini ();
81 }
82
83 void reset () { resize (0); }
84
85 hb_vector_t& operator = (const hb_vector_t &o)
86 {
87 reset ();
88 alloc (o.length);
89 hb_copy (o, *this);
90 return *this;
91 }
92 hb_vector_t& operator = (hb_vector_t &&o)
93 {
94 fini ();
95 allocated = o.allocated;
96 length = o.length;
97 arrayZ = o.arrayZ;
98 o.init ();
99 return *this;
100 }
101
102 hb_bytes_t as_bytes () const
103 { return hb_bytes_t ((const char *) arrayZ, length * item_size); }
104
105 bool operator == (const hb_vector_t &o) const { return as_array () == o.as_array (); }
106 bool operator != (const hb_vector_t &o) const { return !(*this == o); }
107 uint32_t hash () const { return as_array ().hash (); }
108
109 Type& operator [] (int i_)
110 {
111 unsigned int i = (unsigned int) i_;
112 if (unlikely (i >= length))
113 return Crap (Type);
114 return arrayZ[i];
115 }
116 const Type& operator [] (int i_) const
117 {
118 unsigned int i = (unsigned int) i_;
119 if (unlikely (i >= length))
120 return Null(Type);
121 return arrayZ[i];
122 }
123
124 Type& tail () { return (*this)[length - 1]; }
125 const Type& tail () const { return (*this)[length - 1]; }
126
127 explicit operator bool () const { return length; }
128 unsigned get_size () const { return length * item_size; }
129
130 /* Sink interface. */
131 template <typename T>
132 hb_vector_t& operator << (T&& v) { push (hb_forward<T> (v)); return *this; }
133
134 hb_array_t< Type> as_array () { return hb_array (arrayZ, length); }
135 hb_array_t<const Type> as_array () const { return hb_array (arrayZ, length); }
136
137 /* Iterator. */
138 typedef hb_array_t<const Type> iter_t;
139 typedef hb_array_t< Type> writer_t;
140 iter_t iter () const { return as_array (); }
141 writer_t writer () { return as_array (); }
142 operator iter_t () const { return iter (); }
143 operator writer_t () { return writer (); }
144
145 hb_array_t<const Type> sub_array (unsigned int start_offset, unsigned int count) const
146 { return as_array ().sub_array (start_offset, count); }
147 hb_array_t<const Type> sub_array (unsigned int start_offset, unsigned int *count = nullptr /* IN/OUT */) const
148 { return as_array ().sub_array (start_offset, count); }
149 hb_array_t<Type> sub_array (unsigned int start_offset, unsigned int count)
150 { return as_array ().sub_array (start_offset, count); }
151 hb_array_t<Type> sub_array (unsigned int start_offset, unsigned int *count = nullptr /* IN/OUT */)
152 { return as_array ().sub_array (start_offset, count); }
153
154 hb_sorted_array_t<Type> as_sorted_array ()
155 { return hb_sorted_array (arrayZ, length); }
156 hb_sorted_array_t<const Type> as_sorted_array () const
157 { return hb_sorted_array (arrayZ, length); }
158
159 template <typename T> explicit operator T * () { return arrayZ; }
160 template <typename T> explicit operator const T * () const { return arrayZ; }
161
162 Type * operator + (unsigned int i) { return arrayZ + i; }
163 const Type * operator + (unsigned int i) const { return arrayZ + i; }
164
165 Type *push ()
166 {
167 if (unlikely (!resize (length + 1)))
168 return &Crap(Type);
169 return &arrayZ[length - 1];
170 }
171 template <typename T>
172 Type *push (T&& v)
173 {
174 Type *p = push ();
175 *p = hb_forward<T> (v);
176 return p;
177 }
178
179 bool in_error () const { return allocated < 0; }
180
181 /* Allocate for size but don't adjust length. */
182 bool alloc (unsigned int size)
183 {
184 if (unlikely (allocated < 0))
185 return false;
186
187 if (likely (size <= (unsigned) allocated))
188 return true;
189
190 /* Reallocate */
191
192 unsigned int new_allocated = allocated;
193 while (size >= new_allocated)
194 new_allocated += (new_allocated >> 1) + 8;
195
196 Type *new_array = nullptr;
197 bool overflows =
198 (int) new_allocated < 0 ||
199 (new_allocated < (unsigned) allocated) ||
200 hb_unsigned_mul_overflows (new_allocated, sizeof (Type));
201 if (likely (!overflows))
202 new_array = (Type *) realloc (arrayZ, new_allocated * sizeof (Type));
203
204 if (unlikely (!new_array))
205 {
206 allocated = -1;
207 return false;
208 }
209
210 arrayZ = new_array;
211 allocated = new_allocated;
212
213 return true;
214 }
215
216 bool resize (int size_)
217 {
218 unsigned int size = size_ < 0 ? 0u : (unsigned int) size_;
219 if (!alloc (size))
220 return false;
221
222 if (size > length)
223 memset (arrayZ + length, 0, (size - length) * sizeof (*arrayZ));
224
225 length = size;
226 return true;
227 }
228
229 Type pop ()
230 {
231 if (!length) return Null(Type);
232 return hb_move (arrayZ[--length]); /* Does this move actually work? */
233 }
234
235 void remove (unsigned int i)
236 {
237 if (unlikely (i >= length))
238 return;
239 memmove (static_cast<void *> (&arrayZ[i]),
240 static_cast<void *> (&arrayZ[i + 1]),
241 (length - i - 1) * sizeof (Type));
242 length--;
243 }
244
245 void shrink (int size_)
246 {
247 unsigned int size = size_ < 0 ? 0u : (unsigned int) size_;
248 if (size < length)
249 length = size;
250 }
251
252 template <typename T>
253 Type *find (T v)
254 {
255 for (unsigned int i = 0; i < length; i++)
256 if (arrayZ[i] == v)
257 return &arrayZ[i];
258 return nullptr;
259 }
260 template <typename T>
261 const Type *find (T v) const
262 {
263 for (unsigned int i = 0; i < length; i++)
264 if (arrayZ[i] == v)
265 return &arrayZ[i];
266 return nullptr;
267 }
268
269 void qsort (int (*cmp)(const void*, const void*))
270 { as_array ().qsort (cmp); }
271 void qsort (unsigned int start = 0, unsigned int end = (unsigned int) -1)
272 { as_array ().qsort (start, end); }
273
274 template <typename T>
275 Type *lsearch (const T &x, Type *not_found = nullptr)
276 { return as_array ().lsearch (x, not_found); }
277 template <typename T>
278 const Type *lsearch (const T &x, const Type *not_found = nullptr) const
279 { return as_array ().lsearch (x, not_found); }
280};
281
282template <typename Type>
283struct hb_sorted_vector_t : hb_vector_t<Type>
284{
285 hb_sorted_array_t< Type> as_array () { return hb_sorted_array (this->arrayZ, this->length); }
286 hb_sorted_array_t<const Type> as_array () const { return hb_sorted_array (this->arrayZ, this->length); }
287
288 /* Iterator. */
289 typedef hb_sorted_array_t<const Type> const_iter_t;
290 typedef hb_sorted_array_t< Type> iter_t;
291 const_iter_t iter () const { return as_array (); }
292 const_iter_t citer () const { return as_array (); }
293 iter_t iter () { return as_array (); }
294 operator iter_t () { return iter (); }
295 operator const_iter_t () const { return iter (); }
296
297 template <typename T>
298 Type *bsearch (const T &x, Type *not_found = nullptr)
299 { return as_array ().bsearch (x, not_found); }
300 template <typename T>
301 const Type *bsearch (const T &x, const Type *not_found = nullptr) const
302 { return as_array ().bsearch (x, not_found); }
303 template <typename T>
304 bool bfind (const T &x, unsigned int *i = nullptr,
305 hb_bfind_not_found_t not_found = HB_BFIND_NOT_FOUND_DONT_STORE,
306 unsigned int to_store = (unsigned int) -1) const
307 { return as_array ().bfind (x, i, not_found, to_store); }
308};
309
310#endif /* HB_VECTOR_HH */
311