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 * Red Hat Author(s): Behdad Esfahbod
25 * Google Author(s): Behdad Esfahbod
26 */
27
28#ifndef HB_VECTOR_HH
29#define HB_VECTOR_HH
30
31#include "hb.hh"
32
33
34template <typename Type, unsigned int StaticSize=8>
35struct hb_vector_t
36{
37 unsigned int len;
38 unsigned int allocated; /* == 0 means allocation failed. */
39 Type *arrayZ;
40 Type static_array[StaticSize];
41
42 void init (void)
43 {
44 len = 0;
45 allocated = ARRAY_LENGTH (static_array);
46 arrayZ = static_array;
47 }
48
49 inline Type& operator [] (unsigned int i)
50 {
51 if (unlikely (i >= len))
52 return Crap (Type);
53 return arrayZ[i];
54 }
55 inline const Type& operator [] (unsigned int i) const
56 {
57 if (unlikely (i >= len))
58 return Null(Type);
59 return arrayZ[i];
60 }
61
62 inline Type *push (void)
63 {
64 if (unlikely (!resize (len + 1)))
65 return &Crap(Type);
66 return &arrayZ[len - 1];
67 }
68 inline Type *push (const Type& v)
69 {
70 Type *p = push ();
71 *p = v;
72 return p;
73 }
74
75 inline bool in_error (void) const { return allocated == 0; }
76
77 /* Allocate for size but don't adjust len. */
78 inline bool alloc (unsigned int size)
79 {
80 if (unlikely (!allocated))
81 return false;
82
83 if (likely (size <= allocated))
84 return true;
85
86 /* Reallocate */
87
88 unsigned int new_allocated = allocated;
89 while (size >= new_allocated)
90 new_allocated += (new_allocated >> 1) + 8;
91
92 Type *new_array = nullptr;
93
94 if (arrayZ == static_array)
95 {
96 new_array = (Type *) calloc (new_allocated, sizeof (Type));
97 if (new_array)
98 memcpy (new_array, arrayZ, len * sizeof (Type));
99 }
100 else
101 {
102 bool overflows = (new_allocated < allocated) || hb_unsigned_mul_overflows (new_allocated, sizeof (Type));
103 if (likely (!overflows))
104 new_array = (Type *) realloc (arrayZ, new_allocated * sizeof (Type));
105 }
106
107 if (unlikely (!new_array))
108 {
109 allocated = 0;
110 return false;
111 }
112
113 arrayZ = new_array;
114 allocated = new_allocated;
115
116 return true;
117 }
118
119 inline bool resize (int size_)
120 {
121 unsigned int size = size_ < 0 ? 0u : (unsigned int) size_;
122 if (!alloc (size))
123 return false;
124
125 if (size > len)
126 memset (arrayZ + len, 0, (size - len) * sizeof (*arrayZ));
127
128 len = size;
129 return true;
130 }
131
132 inline void pop (void)
133 {
134 if (!len) return;
135 len--;
136 }
137
138 inline void remove (unsigned int i)
139 {
140 if (unlikely (i >= len))
141 return;
142 memmove (static_cast<void *> (&arrayZ[i]),
143 static_cast<void *> (&arrayZ[i + 1]),
144 (len - i - 1) * sizeof (Type));
145 len--;
146 }
147
148 inline void shrink (int size_)
149 {
150 unsigned int size = size_ < 0 ? 0u : (unsigned int) size_;
151 if (size < len)
152 len = size;
153 }
154
155 template <typename T>
156 inline Type *find (T v) {
157 for (unsigned int i = 0; i < len; i++)
158 if (arrayZ[i] == v)
159 return &arrayZ[i];
160 return nullptr;
161 }
162 template <typename T>
163 inline const Type *find (T v) const {
164 for (unsigned int i = 0; i < len; i++)
165 if (arrayZ[i] == v)
166 return &arrayZ[i];
167 return nullptr;
168 }
169
170 inline void qsort (int (*cmp)(const void*, const void*))
171 {
172 ::qsort (arrayZ, len, sizeof (Type), cmp);
173 }
174
175 inline void qsort (void)
176 {
177 ::qsort (arrayZ, len, sizeof (Type), Type::cmp);
178 }
179
180 inline void qsort (unsigned int start, unsigned int end)
181 {
182 ::qsort (arrayZ + start, end - start, sizeof (Type), Type::cmp);
183 }
184
185 template <typename T>
186 inline Type *lsearch (const T &x)
187 {
188 for (unsigned int i = 0; i < len; i++)
189 if (0 == this->arrayZ[i].cmp (&x))
190 return &arrayZ[i];
191 return nullptr;
192 }
193
194 template <typename T>
195 inline Type *bsearch (const T &x)
196 {
197 unsigned int i;
198 return bfind (x, &i) ? &arrayZ[i] : nullptr;
199 }
200 template <typename T>
201 inline const Type *bsearch (const T &x) const
202 {
203 unsigned int i;
204 return bfind (x, &i) ? &arrayZ[i] : nullptr;
205 }
206 template <typename T>
207 inline bool bfind (const T &x, unsigned int *i) const
208 {
209 int min = 0, max = (int) this->len - 1;
210 while (min <= max)
211 {
212 int mid = (min + max) / 2;
213 int c = this->arrayZ[mid].cmp (&x);
214 if (c < 0)
215 max = mid - 1;
216 else if (c > 0)
217 min = mid + 1;
218 else
219 {
220 *i = mid;
221 return true;
222 }
223 }
224 if (max < 0 || (max < (int) this->len && this->arrayZ[max].cmp (&x) > 0))
225 max++;
226 *i = max;
227 return false;
228 }
229
230 inline void fini (void)
231 {
232 if (arrayZ != static_array)
233 free (arrayZ);
234 arrayZ = nullptr;
235 allocated = len = 0;
236 }
237};
238
239
240#endif /* HB_VECTOR_HH */
241