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_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 */