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_NO_COPY_ASSIGN_TEMPLATE (hb_vector_t, Type);
42 hb_vector_t () { init (); }
43 ~hb_vector_t () { fini (); }
44
45 unsigned int length;
46 private:
47 int allocated; /* == -1 means allocation failed. */
48 Type *arrayZ_;
49 public:
50
51 void init ()
52 {
53 allocated = length = 0;
54 arrayZ_ = nullptr;
55 }
56
57 void fini ()
58 {
59 if (arrayZ_)
60 free (arrayZ_);
61 init ();
62 }
63 void fini_deep ()
64 {
65 Type *array = arrayZ();
66 unsigned int count = length;
67 for (unsigned int i = 0; i < count; i++)
68 array[i].fini ();
69 fini ();
70 }
71
72 const Type * arrayZ () const { return arrayZ_; }
73 Type * arrayZ () { return arrayZ_; }
74
75 Type& operator [] (int i_)
76 {
77 unsigned int i = (unsigned int) i_;
78 if (unlikely (i >= length))
79 return Crap (Type);
80 return arrayZ()[i];
81 }
82 const Type& operator [] (int i_) const
83 {
84 unsigned int i = (unsigned int) i_;
85 if (unlikely (i >= length))
86 return Null(Type);
87 return arrayZ()[i];
88 }
89
90 explicit_operator bool () const { return length; }
91
92 hb_array_t<Type> as_array ()
93 { return hb_array (arrayZ(), length); }
94 hb_array_t<const Type> as_array () const
95 { return hb_array (arrayZ(), length); }
96
97 hb_array_t<const Type> sub_array (unsigned int start_offset, unsigned int count) const
98 { return as_array ().sub_array (start_offset, count);}
99 hb_array_t<const Type> sub_array (unsigned int start_offset, unsigned int *count = nullptr /* IN/OUT */) const
100 { return as_array ().sub_array (start_offset, count);}
101 hb_array_t<Type> sub_array (unsigned int start_offset, unsigned int count)
102 { return as_array ().sub_array (start_offset, count);}
103 hb_array_t<Type> sub_array (unsigned int start_offset, unsigned int *count = nullptr /* IN/OUT */)
104 { return as_array ().sub_array (start_offset, count);}
105
106 hb_sorted_array_t<Type> as_sorted_array ()
107 { return hb_sorted_array (arrayZ(), length); }
108 hb_sorted_array_t<const Type> as_sorted_array () const
109 { return hb_sorted_array (arrayZ(), length); }
110
111 hb_array_t<const Type> sorted_sub_array (unsigned int start_offset, unsigned int count) const
112 { return as_sorted_array ().sorted_sub_array (start_offset, count);}
113 hb_array_t<const Type> sorted_sub_array (unsigned int start_offset, unsigned int *count = nullptr /* IN/OUT */) const
114 { return as_sorted_array ().sorted_sub_array (start_offset, count);}
115 hb_array_t<Type> sorted_sub_array (unsigned int start_offset, unsigned int count)
116 { return as_sorted_array ().sorted_sub_array (start_offset, count);}
117 hb_array_t<Type> sorted_sub_array (unsigned int start_offset, unsigned int *count = nullptr /* IN/OUT */)
118 { return as_sorted_array ().sorted_sub_array (start_offset, count);}
119
120 template <typename T> explicit_operator T * () { return arrayZ(); }
121 template <typename T> explicit_operator const T * () const { return arrayZ(); }
122 operator hb_array_t<Type> () { return as_array (); }
123 operator hb_array_t<const Type> () const { return as_array (); }
124
125 Type * operator + (unsigned int i) { return arrayZ() + i; }
126 const Type * operator + (unsigned int i) const { return arrayZ() + i; }
127
128 Type *push ()
129 {
130 if (unlikely (!resize (length + 1)))
131 return &Crap(Type);
132 return &arrayZ()[length - 1];
133 }
134 Type *push (const Type& v)
135 {
136 Type *p = push ();
137 *p = v;
138 return p;
139 }
140
141 bool in_error () const { return allocated < 0; }
142
143 /* Allocate for size but don't adjust length. */
144 bool alloc (unsigned int size)
145 {
146 if (unlikely (allocated < 0))
147 return false;
148
149 if (likely (size <= (unsigned) allocated))
150 return true;
151
152 /* Reallocate */
153
154 unsigned int new_allocated = allocated;
155 while (size >= new_allocated)
156 new_allocated += (new_allocated >> 1) + 8;
157
158 Type *new_array = nullptr;
159 bool overflows =
160 (int) new_allocated < 0 ||
161 (new_allocated < (unsigned) allocated) ||
162 hb_unsigned_mul_overflows (new_allocated, sizeof (Type));
163 if (likely (!overflows))
164 new_array = (Type *) realloc (arrayZ_, new_allocated * sizeof (Type));
165
166 if (unlikely (!new_array))
167 {
168 allocated = -1;
169 return false;
170 }
171
172 arrayZ_ = new_array;
173 allocated = new_allocated;
174
175 return true;
176 }
177
178 bool resize (int size_)
179 {
180 unsigned int size = size_ < 0 ? 0u : (unsigned int) size_;
181 if (!alloc (size))
182 return false;
183
184 if (size > length)
185 memset (arrayZ() + length, 0, (size - length) * sizeof (*arrayZ()));
186
187 length = size;
188 return true;
189 }
190
191 void pop ()
192 {
193 if (!length) return;
194 length--;
195 }
196
197 void remove (unsigned int i)
198 {
199 if (unlikely (i >= length))
200 return;
201 Type *array = arrayZ();
202 memmove (static_cast<void *> (&array[i]),
203 static_cast<void *> (&array[i + 1]),
204 (length - i - 1) * sizeof (Type));
205 length--;
206 }
207
208 void shrink (int size_)
209 {
210 unsigned int size = size_ < 0 ? 0u : (unsigned int) size_;
211 if (size < length)
212 length = size;
213 }
214
215 template <typename T>
216 Type *find (T v)
217 {
218 Type *array = arrayZ();
219 for (unsigned int i = 0; i < length; i++)
220 if (array[i] == v)
221 return &array[i];
222 return nullptr;
223 }
224 template <typename T>
225 const Type *find (T v) const
226 {
227 const Type *array = arrayZ();
228 for (unsigned int i = 0; i < length; i++)
229 if (array[i] == v)
230 return &array[i];
231 return nullptr;
232 }
233
234 void qsort (int (*cmp)(const void*, const void*))
235 { as_array ().qsort (cmp); }
236 void qsort (unsigned int start = 0, unsigned int end = (unsigned int) -1)
237 { as_array ().qsort (start, end); }
238
239 template <typename T>
240 Type *lsearch (const T &x, Type *not_found = nullptr)
241 { return as_array ().lsearch (x, not_found); }
242 template <typename T>
243 const Type *lsearch (const T &x, const Type *not_found = nullptr) const
244 { return as_array ().lsearch (x, not_found); }
245
246 template <typename T>
247 Type *bsearch (const T &x, Type *not_found = nullptr)
248 { return as_sorted_array ().bsearch (x, not_found); }
249 template <typename T>
250 const Type *bsearch (const T &x, const Type *not_found = nullptr) const
251 { return as_sorted_array ().bsearch (x, not_found); }
252 template <typename T>
253 bool bfind (const T &x, unsigned int *i = nullptr,
254 hb_bfind_not_found_t not_found = HB_BFIND_NOT_FOUND_DONT_STORE,
255 unsigned int to_store = (unsigned int) -1) const
256 { return as_sorted_array ().bfind (x, i, not_found, to_store); }
257};
258
259
260#endif /* HB_VECTOR_HH */
261