kc3-lang/harfbuzz/src/hb-map.hh

• Show log

  Commit

• Hash : ef33b5d1
  Author :
  Date : 2019-03-30T14:39:21
  

  [map] Deref pointers before equality check
  

Download

• src/hb-map.hh

• /*
   * Copyright © 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_MAP_HH
  #define HB_MAP_HH
  
  #include "hb.hh"
  
  
  /*
   * hb_hashmap_t
   */
  
  template <typename K, typename V,
  	  K kINVALID = hb_is_pointer (K) ? 0 : (K) -1,
  	  V vINVALID = hb_is_pointer (V) ? 0 : (V) -1>
  struct hb_hashmap_t
  {
    HB_NO_COPY_ASSIGN (hb_hashmap_t);
    hb_hashmap_t ()  { init (); }
    ~hb_hashmap_t () { fini (); }
  
    static_assert (hb_is_integer (K) || hb_is_pointer (K), "");
    static_assert (hb_is_integer (V) || hb_is_pointer (V), "");
  
    struct item_t
    {
      K key;
      V value;
  
      bool operator== (K o) { return hb_deref_pointer (key) == hb_deref_pointer (o); }
      bool operator== (const item_t &o) { return *this == o.key; }
      bool is_unused () const    { return key == kINVALID; }
      bool is_tombstone () const { return key != kINVALID && value == vINVALID; }
    };
  
    hb_object_header_t header;
    bool successful; /* Allocations successful */
    unsigned int population; /* Not including tombstones. */
    unsigned int occupancy; /* Including tombstones. */
    unsigned int mask;
    unsigned int prime;
    item_t *items;
  
    void init_shallow ()
    {
      successful = true;
      population = occupancy = 0;
      mask = 0;
      prime = 0;
      items = nullptr;
    }
    void init ()
    {
      hb_object_init (this);
      init_shallow ();
    }
    void fini_shallow ()
    {
      free (items);
      items = nullptr;
    }
    void fini ()
    {
      population = occupancy = 0;
      hb_object_fini (this);
      fini_shallow ();
    }
  
    bool in_error () const { return !successful; }
  
    bool resize ()
    {
      if (unlikely (!successful)) return false;
  
      unsigned int power = hb_bit_storage (population * 2 + 8);
      unsigned int new_size = 1u << power;
      item_t *new_items = (item_t *) malloc ((size_t) new_size * sizeof (item_t));
      if (unlikely (!new_items))
      {
        successful = false;
        return false;
      }
      memset (new_items, 0xFF, (size_t) new_size * sizeof (item_t));
  
      unsigned int old_size = mask + 1;
      item_t *old_items = items;
  
      /* Switch to new, empty, array. */
      population = occupancy = 0;
      mask = new_size - 1;
      prime = prime_for (power);
      items = new_items;
  
      /* Insert back old items. */
      if (old_items)
        for (unsigned int i = 0; i < old_size; i++)
  	if (old_items[i].key != kINVALID && old_items[i].value != vINVALID)
  	  set (old_items[i].key, old_items[i].value);
  
      free (old_items);
  
      return true;
    }
  
    void set (K key, V value)
    {
      if (unlikely (!successful)) return;
      if (unlikely (key == kINVALID)) return;
      if ((occupancy + occupancy / 2) >= mask && !resize ()) return;
      unsigned int i = bucket_for (key);
  
      if (value == vINVALID && items[i].key != key)
        return; /* Trying to delete non-existent key. */
  
      if (!items[i].is_unused ())
      {
        occupancy--;
        if (items[i].is_tombstone ())
  	population--;
      }
  
      items[i].key = key;
      items[i].value = value;
  
      occupancy++;
      if (!items[i].is_tombstone ())
        population++;
  
    }
    V get (K key) const
    {
      if (unlikely (!items)) return vINVALID;
      unsigned int i = bucket_for (key);
      return items[i] == key ? items[i].value : vINVALID;
    }
  
    void del (K key) { set (key, vINVALID); }
  
    /* Has interface. */
    static constexpr V SENTINEL = vINVALID;
    typedef V value_t;
    value_t operator [] (K k) const { return get (k); }
    bool has (K k) const { return (*this)[k] != SENTINEL; }
    /* Projection. */
    V operator () (K k) const { return get (k); }
  
    void clear ()
    {
      if (items) memset (items, 0xFF, ((size_t) mask + 1) * sizeof (item_t));
      population = occupancy = 0;
    }
  
    bool is_empty () const { return population == 0; }
  
    unsigned int get_population () const { return population; }
  
    protected:
  
    unsigned int bucket_for (K key) const
    {
      unsigned int i = hb_hash (key) % prime;
      unsigned int step = 0;
      unsigned int tombstone = (unsigned) -1;
      while (!items[i].is_unused ())
      {
        if (items[i] == key)
          return i;
        if (tombstone == (unsigned) -1 && items[i].is_tombstone ())
          tombstone = i;
        i = (i + ++step) & mask;
      }
      return tombstone == (unsigned) -1 ? i : tombstone;
    }
  
    static unsigned int prime_for (unsigned int shift)
    {
      /* Following comment and table copied from glib. */
      /* Each table size has an associated prime modulo (the first prime
       * lower than the table size) used to find the initial bucket. Probing
       * then works modulo 2^n. The prime modulo is necessary to get a
       * good distribution with poor hash functions.
       */
      /* Not declaring static to make all kinds of compilers happy... */
      /*static*/ const unsigned int prime_mod [32] =
      {
        1,          /* For 1 << 0 */
        2,
        3,
        7,
        13,
        31,
        61,
        127,
        251,
        509,
        1021,
        2039,
        4093,
        8191,
        16381,
        32749,
        65521,      /* For 1 << 16 */
        131071,
        262139,
        524287,
        1048573,
        2097143,
        4194301,
        8388593,
        16777213,
        33554393,
        67108859,
        134217689,
        268435399,
        536870909,
        1073741789,
        2147483647  /* For 1 << 31 */
      };
  
      if (unlikely (shift >= ARRAY_LENGTH (prime_mod)))
        return prime_mod[ARRAY_LENGTH (prime_mod) - 1];
  
      return prime_mod[shift];
    }
  };
  
  struct hb_map_t : hb_hashmap_t<hb_codepoint_t,
  			       hb_codepoint_t,
  			       HB_MAP_VALUE_INVALID,
  			       HB_MAP_VALUE_INVALID> {};
  
  
  #endif /* HB_MAP_HH */
  

Download