src/hb-vector.hh

/*
 * Copyright © 2017,2018  Google, Inc.
 *
 *  This is part of HarfBuzz, a text shaping library.
 *
 * Permission is hereby granted, without written agreement and without
 * license or royalty fees, to use, copy, modify, and distribute this
 * software and its documentation for any purpose, provided that the
 * above copyright notice and the following two paragraphs appear in
 * all copies of this software.
 *
 * IN NO EVENT SHALL THE COPYRIGHT HOLDER BE LIABLE TO ANY PARTY FOR
 * DIRECT, INDIRECT, SPECIAL, INCIDENTAL, OR CONSEQUENTIAL DAMAGES
 * ARISING OUT OF THE USE OF THIS SOFTWARE AND ITS DOCUMENTATION, EVEN
 * IF THE COPYRIGHT HOLDER HAS BEEN ADVISED OF THE POSSIBILITY OF SUCH
 * DAMAGE.
 *
 * THE COPYRIGHT HOLDER SPECIFICALLY DISCLAIMS ANY WARRANTIES, INCLUDING,
 * BUT NOT LIMITED TO, THE IMPLIED WARRANTIES OF MERCHANTABILITY AND
 * FITNESS FOR A PARTICULAR PURPOSE.  THE SOFTWARE PROVIDED HEREUNDER IS
 * ON AN "AS IS" BASIS, AND THE COPYRIGHT HOLDER HAS NO OBLIGATION TO
 * PROVIDE MAINTENANCE, SUPPORT, UPDATES, ENHANCEMENTS, OR MODIFICATIONS.
 *
 * Google Author(s): Behdad Esfahbod
 */

#ifndef HB_VECTOR_HH
#define HB_VECTOR_HH

#include "hb.hh"
#include "hb-array.hh"
#include "hb-null.hh"


template <typename Type>
struct hb_vector_t
{
  typedef Type item_t;
  static constexpr unsigned item_size = hb_static_size (Type);

  hb_vector_t ()  { init (); }
  hb_vector_t (const hb_vector_t &o)
  {
    init ();
    alloc (o.length);
    hb_copy (o, *this);
  }
  hb_vector_t (hb_vector_t &&o)
  {
    allocated = o.allocated;
    length = o.length;
    arrayZ = o.arrayZ;
    o.init ();
  }
  ~hb_vector_t () { fini (); }

  private:
  int allocated; /* == -1 means allocation failed. */
  public:
  unsigned int length;
  public:
  Type *arrayZ;

  void init ()
  {
    allocated = length = 0;
    arrayZ = nullptr;
  }

  void fini ()
  {
    hb_free (arrayZ);
    init ();
  }
  void fini_deep ()
  {
    unsigned int count = length;
    for (unsigned int i = 0; i < count; i++)
      arrayZ[i].fini ();
    fini ();
  }

  void reset ()
  {
    if (unlikely (in_error ()))
      allocated = length; // Big hack!
    resize (0);
  }

  friend void swap (hb_vector_t& a, hb_vector_t& b)
  {
    hb_swap (a.allocated, b.allocated);
    hb_swap (a.length, b.length);
    hb_swap (a.arrayZ, b.arrayZ);
  }

  hb_vector_t& operator = (const hb_vector_t &o)
  {
    reset ();
    alloc (o.length);
    hb_copy (o, *this);
    return *this;
  }
  hb_vector_t& operator = (hb_vector_t &&o)
  {
    fini ();
    allocated = o.allocated;
    length = o.length;
    arrayZ = o.arrayZ;
    o.init ();
    return *this;
  }

  hb_bytes_t as_bytes () const
  { return hb_bytes_t ((const char *) arrayZ, length * item_size); }

  bool operator == (const hb_vector_t &o) const { return as_array () == o.as_array (); }
  bool operator != (const hb_vector_t &o) const { return !(*this == o); }
  uint32_t hash () const { return as_array ().hash (); }

  Type& operator [] (int i_)
  {
    unsigned int i = (unsigned int) i_;
    if (unlikely (i >= length))
      return Crap (Type);
    return arrayZ[i];
  }
  const Type& operator [] (int i_) const
  {
    unsigned int i = (unsigned int) i_;
    if (unlikely (i >= length))
      return Null (Type);
    return arrayZ[i];
  }

  Type& tail () { return (*this)[length - 1]; }
  const Type& tail () const { return (*this)[length - 1]; }

  explicit operator bool () const { return length; }
  unsigned get_size () const { return length * item_size; }

  /* Sink interface. */
  template <typename T>
  hb_vector_t& operator << (T&& v) { push (hb_forward<T> (v)); return *this; }

  hb_array_t<      Type> as_array ()       { return hb_array (arrayZ, length); }
  hb_array_t<const Type> as_array () const { return hb_array (arrayZ, length); }

  /* Iterator. */
  typedef hb_array_t<const Type>   iter_t;
  typedef hb_array_t<      Type> writer_t;
    iter_t   iter () const { return as_array (); }
  writer_t writer ()       { return as_array (); }
  operator   iter_t () const { return   iter (); }
  operator writer_t ()       { return writer (); }

  hb_array_t<const Type> sub_array (unsigned int start_offset, unsigned int count) const
  { return as_array ().sub_array (start_offset, count); }
  hb_array_t<const Type> sub_array (unsigned int start_offset, unsigned int *count = nullptr /* IN/OUT */) const
  { return as_array ().sub_array (start_offset, count); }
  hb_array_t<Type> sub_array (unsigned int start_offset, unsigned int count)
  { return as_array ().sub_array (start_offset, count); }
  hb_array_t<Type> sub_array (unsigned int start_offset, unsigned int *count = nullptr /* IN/OUT */)
  { return as_array ().sub_array (start_offset, count); }

  hb_sorted_array_t<Type> as_sorted_array ()
  { return hb_sorted_array (arrayZ, length); }
  hb_sorted_array_t<const Type> as_sorted_array () const
  { return hb_sorted_array (arrayZ, length); }

  template <typename T> explicit operator T * () { return arrayZ; }
  template <typename T> explicit operator const T * () const { return arrayZ; }

  Type * operator  + (unsigned int i) { return arrayZ + i; }
  const Type * operator  + (unsigned int i) const { return arrayZ + i; }

  Type *push ()
  {
    if (unlikely (!resize (length + 1)))
      return &Crap (Type);
    return &arrayZ[length - 1];
  }
  template <typename T>
  Type *push (T&& v)
  {
    Type *p = push ();
    if (p == &Crap (Type))
      // If push failed to allocate then don't copy v, since this may cause
      // the created copy to leak memory since we won't have stored a
      // reference to it.
      return p;
    *p = hb_forward<T> (v);
    return p;
  }

  bool in_error () const { return allocated < 0; }

  /* Allocate for size but don't adjust length. */
  bool alloc (unsigned int size)
  {
    if (unlikely (in_error ()))
      return false;

    if (likely (size <= (unsigned) allocated))
      return true;

    /* Reallocate */

    unsigned int new_allocated = allocated;
    while (size >= new_allocated)
      new_allocated += (new_allocated >> 1) + 8;

    Type *new_array = nullptr;
    bool overflows =
      (int) in_error () ||
      (new_allocated < (unsigned) allocated) ||
      hb_unsigned_mul_overflows (new_allocated, sizeof (Type));
    if (likely (!overflows))
      new_array = (Type *) hb_realloc (arrayZ, new_allocated * sizeof (Type));

    if (unlikely (!new_array))
    {
      allocated = -1;
      return false;
    }

    arrayZ = new_array;
    allocated = new_allocated;

    return true;
  }

  bool resize (int size_)
  {
    unsigned int size = size_ < 0 ? 0u : (unsigned int) size_;
    if (!alloc (size))
      return false;

    if (size > length)
      memset (arrayZ + length, 0, (size - length) * sizeof (*arrayZ));

    length = size;
    return true;
  }

  Type pop ()
  {
    if (!length) return Null (Type);
    return hb_move (arrayZ[--length]); /* Does this move actually work? */
  }

  void remove (unsigned int i)
  {
    if (unlikely (i >= length))
      return;
    memmove (static_cast<void *> (&arrayZ[i]),
	     static_cast<void *> (&arrayZ[i + 1]),
	     (length - i - 1) * sizeof (Type));
    length--;
  }

  void shrink (int size_)
  {
    unsigned int size = size_ < 0 ? 0u : (unsigned int) size_;
     if (size < length)
       length = size;
  }

  template <typename T>
  Type *find (T v)
  {
    for (unsigned int i = 0; i < length; i++)
      if (arrayZ[i] == v)
	return &arrayZ[i];
    return nullptr;
  }
  template <typename T>
  const Type *find (T v) const
  {
    for (unsigned int i = 0; i < length; i++)
      if (arrayZ[i] == v)
	return &arrayZ[i];
    return nullptr;
  }

  void qsort (int (*cmp)(const void*, const void*))
  { as_array ().qsort (cmp); }
  void qsort (unsigned int start = 0, unsigned int end = (unsigned int) -1)
  { as_array ().qsort (start, end); }

  template <typename T>
  Type *lsearch (const T &x, Type *not_found = nullptr)
  { return as_array ().lsearch (x, not_found); }
  template <typename T>
  const Type *lsearch (const T &x, const Type *not_found = nullptr) const
  { return as_array ().lsearch (x, not_found); }
  template <typename T>
  bool lfind (const T &x, unsigned *pos = nullptr) const
  { return as_array ().lfind (x, pos); }
};

template <typename Type>
struct hb_sorted_vector_t : hb_vector_t<Type>
{
  hb_sorted_array_t<      Type> as_array ()       { return hb_sorted_array (this->arrayZ, this->length); }
  hb_sorted_array_t<const Type> as_array () const { return hb_sorted_array (this->arrayZ, this->length); }

  /* Iterator. */
  typedef hb_sorted_array_t<const Type> const_iter_t;
  typedef hb_sorted_array_t<      Type>       iter_t;
  const_iter_t  iter () const { return as_array (); }
  const_iter_t citer () const { return as_array (); }
	iter_t  iter ()       { return as_array (); }
  operator       iter_t ()       { return iter (); }
  operator const_iter_t () const { return iter (); }

  template <typename T>
  Type *bsearch (const T &x, Type *not_found = nullptr)
  { return as_array ().bsearch (x, not_found); }
  template <typename T>
  const Type *bsearch (const T &x, const Type *not_found = nullptr) const
  { return as_array ().bsearch (x, not_found); }
  template <typename T>
  bool bfind (const T &x, unsigned int *i = nullptr,
	      hb_not_found_t not_found = HB_NOT_FOUND_DONT_STORE,
	      unsigned int to_store = (unsigned int) -1) const
  { return as_array ().bfind (x, i, not_found, to_store); }
};

#endif /* HB_VECTOR_HH */