• Home
  • Line#
  • Scopes#
  • Navigate#
  • Raw
  • Download
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 
35 template <typename Type>
36 struct hb_vector_t
37 {
38   typedef Type item_t;
39   static constexpr unsigned item_size = hb_static_size (Type);
40 
41   hb_vector_t () = default;
hb_vector_thb_vector_t42   hb_vector_t (std::initializer_list<Type> lst) : hb_vector_t ()
43   {
44     alloc (lst.size ());
45     for (auto&& item : lst)
46       push (item);
47   }
48   template <typename Iterable,
49 	    hb_requires (hb_is_iterable (Iterable))>
hb_vector_thb_vector_t50   hb_vector_t (const Iterable &o) : hb_vector_t ()
51   {
52     if (hb_iter (o).is_random_access_iterator)
53       alloc (hb_len (hb_iter (o)));
54     hb_copy (o, *this);
55   }
hb_vector_thb_vector_t56   hb_vector_t (const hb_vector_t &o) : hb_vector_t ()
57   {
58     alloc (o.length);
59     hb_copy (o, *this);
60   }
hb_vector_thb_vector_t61   hb_vector_t (hb_vector_t &&o)
62   {
63     allocated = o.allocated;
64     length = o.length;
65     arrayZ = o.arrayZ;
66     o.init ();
67   }
~hb_vector_thb_vector_t68   ~hb_vector_t () { fini (); }
69 
70   private:
71   int allocated = 0; /* == -1 means allocation failed. */
72   public:
73   unsigned int length = 0;
74   public:
75   Type *arrayZ = nullptr;
76 
inithb_vector_t77   void init ()
78   {
79     allocated = length = 0;
80     arrayZ = nullptr;
81   }
82 
finihb_vector_t83   void fini ()
84   {
85     hb_free (arrayZ);
86     init ();
87   }
fini_deephb_vector_t88   void fini_deep ()
89   {
90     unsigned int count = length;
91     for (unsigned int i = 0; i < count; i++)
92       arrayZ[i].fini ();
93     fini ();
94   }
95 
resethb_vector_t96   void reset ()
97   {
98     if (unlikely (in_error ()))
99       allocated = length; // Big hack!
100     resize (0);
101   }
102 
swap(hb_vector_t & a,hb_vector_t & b)103   friend void swap (hb_vector_t& a, hb_vector_t& b)
104   {
105     hb_swap (a.allocated, b.allocated);
106     hb_swap (a.length, b.length);
107     hb_swap (a.arrayZ, b.arrayZ);
108   }
109 
operator =hb_vector_t110   hb_vector_t& operator = (const hb_vector_t &o)
111   {
112     reset ();
113     alloc (o.length);
114     hb_copy (o, *this);
115     return *this;
116   }
operator =hb_vector_t117   hb_vector_t& operator = (hb_vector_t &&o)
118   {
119     hb_swap (*this, o);
120     return *this;
121   }
122 
as_byteshb_vector_t123   hb_bytes_t as_bytes () const
124   { return hb_bytes_t ((const char *) arrayZ, length * item_size); }
125 
operator ==hb_vector_t126   bool operator == (const hb_vector_t &o) const { return as_array () == o.as_array (); }
operator !=hb_vector_t127   bool operator != (const hb_vector_t &o) const { return !(*this == o); }
hashhb_vector_t128   uint32_t hash () const { return as_array ().hash (); }
129 
operator []hb_vector_t130   Type& operator [] (int i_)
131   {
132     unsigned int i = (unsigned int) i_;
133     if (unlikely (i >= length))
134       return Crap (Type);
135     return arrayZ[i];
136   }
operator []hb_vector_t137   const Type& operator [] (int i_) const
138   {
139     unsigned int i = (unsigned int) i_;
140     if (unlikely (i >= length))
141       return Null (Type);
142     return arrayZ[i];
143   }
144 
tailhb_vector_t145   Type& tail () { return (*this)[length - 1]; }
tailhb_vector_t146   const Type& tail () const { return (*this)[length - 1]; }
147 
operator boolhb_vector_t148   explicit operator bool () const { return length; }
get_sizehb_vector_t149   unsigned get_size () const { return length * item_size; }
150 
151   /* Sink interface. */
152   template <typename T>
operator <<hb_vector_t153   hb_vector_t& operator << (T&& v) { push (std::forward<T> (v)); return *this; }
154 
as_arrayhb_vector_t155   hb_array_t<      Type> as_array ()       { return hb_array (arrayZ, length); }
as_arrayhb_vector_t156   hb_array_t<const Type> as_array () const { return hb_array (arrayZ, length); }
157 
158   /* Iterator. */
159   typedef hb_array_t<const Type>   iter_t;
160   typedef hb_array_t<      Type> writer_t;
iterhb_vector_t161     iter_t   iter () const { return as_array (); }
writerhb_vector_t162   writer_t writer ()       { return as_array (); }
operator iter_thb_vector_t163   operator   iter_t () const { return   iter (); }
operator writer_thb_vector_t164   operator writer_t ()       { return writer (); }
165 
sub_arrayhb_vector_t166   hb_array_t<const Type> sub_array (unsigned int start_offset, unsigned int count) const
167   { return as_array ().sub_array (start_offset, count); }
sub_arrayhb_vector_t168   hb_array_t<const Type> sub_array (unsigned int start_offset, unsigned int *count = nullptr /* IN/OUT */) const
169   { return as_array ().sub_array (start_offset, count); }
sub_arrayhb_vector_t170   hb_array_t<Type> sub_array (unsigned int start_offset, unsigned int count)
171   { return as_array ().sub_array (start_offset, count); }
sub_arrayhb_vector_t172   hb_array_t<Type> sub_array (unsigned int start_offset, unsigned int *count = nullptr /* IN/OUT */)
173   { return as_array ().sub_array (start_offset, count); }
174 
as_sorted_arrayhb_vector_t175   hb_sorted_array_t<Type> as_sorted_array ()
176   { return hb_sorted_array (arrayZ, length); }
as_sorted_arrayhb_vector_t177   hb_sorted_array_t<const Type> as_sorted_array () const
178   { return hb_sorted_array (arrayZ, length); }
179 
operator T*hb_vector_t180   template <typename T> explicit operator T * () { return arrayZ; }
operator const T*hb_vector_t181   template <typename T> explicit operator const T * () const { return arrayZ; }
182 
operator +hb_vector_t183   Type * operator  + (unsigned int i) { return arrayZ + i; }
operator +hb_vector_t184   const Type * operator  + (unsigned int i) const { return arrayZ + i; }
185 
pushhb_vector_t186   Type *push ()
187   {
188     if (unlikely (!resize (length + 1)))
189       return &Crap (Type);
190     return &arrayZ[length - 1];
191   }
192   template <typename T>
pushhb_vector_t193   Type *push (T&& v)
194   {
195     Type *p = push ();
196     if (p == &Crap (Type))
197       // If push failed to allocate then don't copy v, since this may cause
198       // the created copy to leak memory since we won't have stored a
199       // reference to it.
200       return p;
201     *p = std::forward<T> (v);
202     return p;
203   }
204 
in_errorhb_vector_t205   bool in_error () const { return allocated < 0; }
206 
207   /* Allocate for size but don't adjust length. */
allochb_vector_t208   bool alloc (unsigned int size)
209   {
210     if (unlikely (in_error ()))
211       return false;
212 
213     if (likely (size <= (unsigned) allocated))
214       return true;
215 
216     /* Reallocate */
217 
218     unsigned int new_allocated = allocated;
219     while (size >= new_allocated)
220       new_allocated += (new_allocated >> 1) + 8;
221 
222     Type *new_array = nullptr;
223     bool overflows =
224       (int) in_error () ||
225       (new_allocated < (unsigned) allocated) ||
226       hb_unsigned_mul_overflows (new_allocated, sizeof (Type));
227     if (likely (!overflows))
228       new_array = (Type *) hb_realloc (arrayZ, new_allocated * sizeof (Type));
229 
230     if (unlikely (!new_array))
231     {
232       allocated = -1;
233       return false;
234     }
235 
236     arrayZ = new_array;
237     allocated = new_allocated;
238 
239     return true;
240   }
241 
resizehb_vector_t242   bool resize (int size_)
243   {
244     unsigned int size = size_ < 0 ? 0u : (unsigned int) size_;
245     if (!alloc (size))
246       return false;
247 
248     if (size > length)
249       memset (arrayZ + length, 0, (size - length) * sizeof (*arrayZ));
250 
251     length = size;
252     return true;
253   }
254 
pophb_vector_t255   Type pop ()
256   {
257     if (!length) return Null (Type);
258     return std::move (arrayZ[--length]); /* Does this move actually work? */
259   }
260 
removehb_vector_t261   void remove (unsigned int i)
262   {
263     if (unlikely (i >= length))
264       return;
265     memmove (static_cast<void *> (&arrayZ[i]),
266 	     static_cast<void *> (&arrayZ[i + 1]),
267 	     (length - i - 1) * sizeof (Type));
268     length--;
269   }
270 
shrinkhb_vector_t271   void shrink (int size_)
272   {
273     unsigned int size = size_ < 0 ? 0u : (unsigned int) size_;
274      if (size < length)
275        length = size;
276   }
277 
278   template <typename T>
findhb_vector_t279   Type *find (T v)
280   {
281     for (unsigned int i = 0; i < length; i++)
282       if (arrayZ[i] == v)
283 	return &arrayZ[i];
284     return nullptr;
285   }
286   template <typename T>
findhb_vector_t287   const Type *find (T v) const
288   {
289     for (unsigned int i = 0; i < length; i++)
290       if (arrayZ[i] == v)
291 	return &arrayZ[i];
292     return nullptr;
293   }
294 
qsorthb_vector_t295   void qsort (int (*cmp)(const void*, const void*))
296   { as_array ().qsort (cmp); }
qsorthb_vector_t297   void qsort (unsigned int start = 0, unsigned int end = (unsigned int) -1)
298   { as_array ().qsort (start, end); }
299 
300   template <typename T>
lsearchhb_vector_t301   Type *lsearch (const T &x, Type *not_found = nullptr)
302   { return as_array ().lsearch (x, not_found); }
303   template <typename T>
lsearchhb_vector_t304   const Type *lsearch (const T &x, const Type *not_found = nullptr) const
305   { return as_array ().lsearch (x, not_found); }
306   template <typename T>
lfindhb_vector_t307   bool lfind (const T &x, unsigned *pos = nullptr) const
308   { return as_array ().lfind (x, pos); }
309 };
310 
311 template <typename Type>
312 struct hb_sorted_vector_t : hb_vector_t<Type>
313 {
314   hb_sorted_vector_t () = default;
315   ~hb_sorted_vector_t () = default;
316   hb_sorted_vector_t (hb_sorted_vector_t& o) = default;
317   hb_sorted_vector_t (hb_sorted_vector_t &&o) = default;
hb_sorted_vector_thb_sorted_vector_t318   hb_sorted_vector_t (std::initializer_list<Type> lst) : hb_vector_t<Type> (lst) {}
319   template <typename Iterable,
320 	    hb_requires (hb_is_iterable (Iterable))>
hb_sorted_vector_thb_sorted_vector_t321   hb_sorted_vector_t (const Iterable &o) : hb_vector_t<Type> (o) {}
322   hb_sorted_vector_t& operator = (const hb_sorted_vector_t &o) = default;
323   hb_sorted_vector_t& operator = (hb_sorted_vector_t &&o) = default;
swap(hb_sorted_vector_t & a,hb_sorted_vector_t & b)324   friend void swap (hb_sorted_vector_t& a, hb_sorted_vector_t& b)
325   { hb_swap ((hb_vector_t<Type>&) (a), (hb_vector_t<Type>&) (b)); }
326 
as_arrayhb_sorted_vector_t327   hb_sorted_array_t<      Type> as_array ()       { return hb_sorted_array (this->arrayZ, this->length); }
as_arrayhb_sorted_vector_t328   hb_sorted_array_t<const Type> as_array () const { return hb_sorted_array (this->arrayZ, this->length); }
329 
330   /* Iterator. */
331   typedef hb_sorted_array_t<const Type> const_iter_t;
332   typedef hb_sorted_array_t<      Type>       iter_t;
iterhb_sorted_vector_t333   const_iter_t  iter () const { return as_array (); }
citerhb_sorted_vector_t334   const_iter_t citer () const { return as_array (); }
iterhb_sorted_vector_t335 	iter_t  iter ()       { return as_array (); }
operator iter_thb_sorted_vector_t336   operator       iter_t ()       { return iter (); }
operator const_iter_thb_sorted_vector_t337   operator const_iter_t () const { return iter (); }
338 
339   template <typename T>
bsearchhb_sorted_vector_t340   Type *bsearch (const T &x, Type *not_found = nullptr)
341   { return as_array ().bsearch (x, not_found); }
342   template <typename T>
bsearchhb_sorted_vector_t343   const Type *bsearch (const T &x, const Type *not_found = nullptr) const
344   { return as_array ().bsearch (x, not_found); }
345   template <typename T>
bfindhb_sorted_vector_t346   bool bfind (const T &x, unsigned int *i = nullptr,
347 	      hb_not_found_t not_found = HB_NOT_FOUND_DONT_STORE,
348 	      unsigned int to_store = (unsigned int) -1) const
349   { return as_array ().bfind (x, i, not_found, to_store); }
350 };
351 
352 #endif /* HB_VECTOR_HH */
353