/src/skia/third_party/externals/harfbuzz/src/hb-map.hh

Source (jump to first uncovered line)
/*
 * 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 : hb_is_signed (K) ? hb_int_min (K) : (K) -1,
    V vINVALID = hb_is_pointer (V) ? 0 : hb_is_signed (V) ? hb_int_min (V) : (V) -1>
struct hb_hashmap_t
{
  HB_DELETE_COPY_ASSIGN (hb_hashmap_t);
  hb_hashmap_t ()  { init (); }
  ~hb_hashmap_t () { fini (); }

  static_assert (hb_is_integral (K) || hb_is_pointer (K), "");
  static_assert (hb_is_integral (V) || hb_is_pointer (V), "");

  struct item_t
  {
    K key;
    V value;
    uint32_t hash;

    void clear () { key = kINVALID; value = vINVALID; hash = 0; }

    bool operator == (const K &o) { return hb_deref (key) == hb_deref (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; }
    bool is_real () const { return key != kINVALID && value != vINVALID; }
    hb_pair_t<K, V> get_pair() const { return hb_pair_t<K, V> (key, value); }
  };

  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 ()
  {
    hb_free (items);
    items = nullptr;
    population = occupancy = 0;
  }
  void fini ()
  {
    hb_object_fini (this);
    fini_shallow ();
  }

  void reset ()
  {
    successful = true;
    clear ();
  }

  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 *) hb_malloc ((size_t) new_size * sizeof (item_t));
    if (unlikely (!new_items))
    {
      successful = false;
      return false;
    }
    for (auto &_ : hb_iter (new_items, new_size))
      _.clear ();

    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].is_real ())
    set_with_hash (old_items[i].key,
       old_items[i].hash,
       old_items[i].value);

    hb_free (old_items);

    return true;
  }

  bool set (K key, V value)
  {
    return set_with_hash (key, hb_hash (key), value);
  }

  V get (K key) const
  {
    if (unlikely (!items)) return vINVALID;
    unsigned int i = bucket_for (key);
    return items[i].is_real () && 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, V *vp = nullptr) const
  {
    V v = (*this)[k];
    if (vp) *vp = v;
    return v != SENTINEL;
  }
  /* Projection. */
  V operator () (K k) const { return get (k); }

  void clear ()
  {
    if (items)
      for (auto &_ : hb_iter (items, mask + 1))
  _.clear ();

    population = occupancy = 0;
  }

  bool is_empty () const { return population == 0; }
  explicit operator bool () const { return !is_empty (); }

  unsigned int get_population () const { return population; }

  /*
   * Iterator
   */
  auto iter () const HB_AUTO_RETURN
  (
    + hb_array (items, mask ? mask + 1 : 0)
    | hb_filter (&item_t::is_real)
    | hb_map (&item_t::get_pair)
  )
  auto keys () const HB_AUTO_RETURN
  (
    + hb_array (items, mask ? mask + 1 : 0)
    | hb_filter (&item_t::is_real)
    | hb_map (&item_t::key)
    | hb_map (hb_ridentity)
  )
  auto values () const HB_AUTO_RETURN
  (
    + hb_array (items, mask ? mask + 1 : 0)
    | hb_filter (&item_t::is_real)
    | hb_map (&item_t::value)
    | hb_map (hb_ridentity)
  )

  /* Sink interface. */
  hb_hashmap_t& operator << (const hb_pair_t<K, V>& v)
  { set (v.first, v.second); return *this; }

  protected:

  bool set_with_hash (K key, uint32_t hash, V value)
  {
    if (unlikely (!successful)) return false;
    if (unlikely (key == kINVALID)) return true;
    if (unlikely ((occupancy + occupancy / 2) >= mask && !resize ())) return false;
    unsigned int i = bucket_for_hash (key, hash);

    if (value == vINVALID && items[i].key != key)
      return true; /* 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;
    items[i].hash = hash;

    occupancy++;
    if (!items[i].is_tombstone ())
      population++;

    return true;
  }

  unsigned int bucket_for (K key) const
  {
    return bucket_for_hash (key, hb_hash (key));
  }

  unsigned int bucket_for_hash (K key, uint32_t hash) const
  {
    unsigned int i = hash % prime;
    unsigned int step = 0;
    unsigned int tombstone = (unsigned) -1;
    while (!items[i].is_unused ())
    {
      if (items[i].hash == hash && 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];
  }
};

/*
 * hb_map_t
 */

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

Coverage Report

Created: 2021-08-22 09:07

Line	Count	Source (jump to first uncovered line)
1		/*
2		* Copyright © 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_MAP_HH
28		#define HB_MAP_HH
29
30		#include "hb.hh"
31
32
33		/*
34		* hb_hashmap_t
35		*/
36
37		template <typename K, typename V,
38		K kINVALID = hb_is_pointer (K) ? 0 : hb_is_signed (K) ? hb_int_min (K) : (K) -1,
39		V vINVALID = hb_is_pointer (V) ? 0 : hb_is_signed (V) ? hb_int_min (V) : (V) -1>
40		struct hb_hashmap_t
41		{
42		HB_DELETE_COPY_ASSIGN (hb_hashmap_t);
43	0	hb_hashmap_t () { init (); } Unexecuted instantiation: hb_hashmap_t<hb_serialize_context_t::object_t const, unsigned int, (hb_serialize_context_t::object_t const)0, 0u>::hb_hashmap_t() Unexecuted instantiation: hb_hashmap_t<unsigned int, unsigned int, 4294967295u, 4294967295u>::hb_hashmap_t() Unexecuted instantiation: hb_hashmap_t<unsigned int, hb_set_t, 4294967295u, (hb_set_t)0>::hb_hashmap_t()
44	0	~hb_hashmap_t () { fini (); } Unexecuted instantiation: hb_hashmap_t<hb_serialize_context_t::object_t const, unsigned int, (hb_serialize_context_t::object_t const)0, 0u>::~hb_hashmap_t() Unexecuted instantiation: hb_hashmap_t<unsigned int, unsigned int, 4294967295u, 4294967295u>::~hb_hashmap_t() Unexecuted instantiation: hb_hashmap_t<unsigned int, hb_set_t, 4294967295u, (hb_set_t)0>::~hb_hashmap_t()
45
46		static_assert (hb_is_integral (K) \|\| hb_is_pointer (K), "");
47		static_assert (hb_is_integral (V) \|\| hb_is_pointer (V), "");
48
49		struct item_t
50		{
51		K key;
52		V value;
53		uint32_t hash;
54
55	0	void clear () { key = kINVALID; value = vINVALID; hash = 0; } Unexecuted instantiation: hb_hashmap_t<hb_serialize_context_t::object_t const, unsigned int, (hb_serialize_context_t::object_t const)0, 0u>::item_t::clear() Unexecuted instantiation: hb_hashmap_t<unsigned int, unsigned int, 4294967295u, 4294967295u>::item_t::clear() Unexecuted instantiation: hb_hashmap_t<unsigned int, hb_set_t, 4294967295u, (hb_set_t)0>::item_t::clear()
56
57	0	bool operator == (const K &o) { return hb_deref (key) == hb_deref (o); } Unexecuted instantiation: hb_hashmap_t<hb_serialize_context_t::object_t const, unsigned int, (hb_serialize_context_t::object_t const)0, 0u>::item_t::operator==(hb_serialize_context_t::object_t const* const&) Unexecuted instantiation: hb_hashmap_t<unsigned int, unsigned int, 4294967295u, 4294967295u>::item_t::operator==(unsigned int const&) Unexecuted instantiation: hb_hashmap_t<unsigned int, hb_set_t, 4294967295u, (hb_set_t)0>::item_t::operator==(unsigned int const&)
58		bool operator == (const item_t &o) { return *this == o.key; }
59	0	bool is_unused () const { return key == kINVALID; } Unexecuted instantiation: hb_hashmap_t<hb_serialize_context_t::object_t const, unsigned int, (hb_serialize_context_t::object_t const)0, 0u>::item_t::is_unused() const Unexecuted instantiation: hb_hashmap_t<unsigned int, unsigned int, 4294967295u, 4294967295u>::item_t::is_unused() const Unexecuted instantiation: hb_hashmap_t<unsigned int, hb_set_t, 4294967295u, (hb_set_t)0>::item_t::is_unused() const
60	0	bool is_tombstone () const { return key != kINVALID && value == vINVALID; } Unexecuted instantiation: hb_hashmap_t<hb_serialize_context_t::object_t const, unsigned int, (hb_serialize_context_t::object_t const)0, 0u>::item_t::is_tombstone() const Unexecuted instantiation: hb_hashmap_t<unsigned int, unsigned int, 4294967295u, 4294967295u>::item_t::is_tombstone() const Unexecuted instantiation: hb_hashmap_t<unsigned int, hb_set_t, 4294967295u, (hb_set_t)0>::item_t::is_tombstone() const
61	0	bool is_real () const { return key != kINVALID && value != vINVALID; } Unexecuted instantiation: hb_hashmap_t<hb_serialize_context_t::object_t const, unsigned int, (hb_serialize_context_t::object_t const)0, 0u>::item_t::is_real() const Unexecuted instantiation: hb_hashmap_t<unsigned int, unsigned int, 4294967295u, 4294967295u>::item_t::is_real() const Unexecuted instantiation: hb_hashmap_t<unsigned int, hb_set_t, 4294967295u, (hb_set_t)0>::item_t::is_real() const
62	0	hb_pair_t<K, V> get_pair() const { return hb_pair_t<K, V> (key, value); } Unexecuted instantiation: hb_hashmap_t<unsigned int, hb_set_t, 4294967295u, (hb_set_t)0>::item_t::get_pair() const Unexecuted instantiation: hb_hashmap_t<unsigned int, unsigned int, 4294967295u, 4294967295u>::item_t::get_pair() const
63		};
64
65		hb_object_header_t header;
66		bool successful; /* Allocations successful */
67		unsigned int population; /* Not including tombstones. */
68		unsigned int occupancy; /* Including tombstones. */
69		unsigned int mask;
70		unsigned int prime;
71		item_t *items;
72
73		void init_shallow ()
74	0	{
75	0	successful = true;
76	0	population = occupancy = 0;
77	0	mask = 0;
78	0	prime = 0;
79	0	items = nullptr;
80	0	} Unexecuted instantiation: hb_hashmap_t<hb_serialize_context_t::object_t const, unsigned int, (hb_serialize_context_t::object_t const)0, 0u>::init_shallow() Unexecuted instantiation: hb_hashmap_t<unsigned int, unsigned int, 4294967295u, 4294967295u>::init_shallow() Unexecuted instantiation: hb_hashmap_t<unsigned int, hb_set_t, 4294967295u, (hb_set_t)0>::init_shallow()
81		void init ()
82	0	{
83	0	hb_object_init (this);
84	0	init_shallow ();
85	0	} Unexecuted instantiation: hb_hashmap_t<hb_serialize_context_t::object_t const, unsigned int, (hb_serialize_context_t::object_t const)0, 0u>::init() Unexecuted instantiation: hb_hashmap_t<unsigned int, unsigned int, 4294967295u, 4294967295u>::init() Unexecuted instantiation: hb_hashmap_t<unsigned int, hb_set_t, 4294967295u, (hb_set_t)0>::init()
86		void fini_shallow ()
87	0	{
88	0	hb_free (items);
89	0	items = nullptr;
90	0	population = occupancy = 0;
91	0	} Unexecuted instantiation: hb_hashmap_t<hb_serialize_context_t::object_t const, unsigned int, (hb_serialize_context_t::object_t const)0, 0u>::fini_shallow() Unexecuted instantiation: hb_hashmap_t<unsigned int, unsigned int, 4294967295u, 4294967295u>::fini_shallow() Unexecuted instantiation: hb_hashmap_t<unsigned int, hb_set_t, 4294967295u, (hb_set_t)0>::fini_shallow()
92		void fini ()
93	0	{
94	0	hb_object_fini (this);
95	0	fini_shallow ();
96	0	} Unexecuted instantiation: hb_hashmap_t<hb_serialize_context_t::object_t const, unsigned int, (hb_serialize_context_t::object_t const)0, 0u>::fini() Unexecuted instantiation: hb_hashmap_t<unsigned int, unsigned int, 4294967295u, 4294967295u>::fini() Unexecuted instantiation: hb_hashmap_t<unsigned int, hb_set_t, 4294967295u, (hb_set_t)0>::fini()
97
98		void reset ()
99	0	{
100	0	successful = true;
101	0	clear ();
102	0	}
103
104	0	bool in_error () const { return !successful; } Unexecuted instantiation: hb_hashmap_t<hb_serialize_context_t::object_t const, unsigned int, (hb_serialize_context_t::object_t const)0, 0u>::in_error() const Unexecuted instantiation: hb_hashmap_t<unsigned int, unsigned int, 4294967295u, 4294967295u>::in_error() const Unexecuted instantiation: hb_hashmap_t<unsigned int, hb_set_t, 4294967295u, (hb_set_t)0>::in_error() const
105
106		bool resize ()
107	0	{
108	0	if (unlikely (!successful)) return false;
109
110	0	unsigned int power = hb_bit_storage (population * 2 + 8);
111	0	unsigned int new_size = 1u << power;
112	0	item_t new_items = (item_t ) hb_malloc ((size_t) new_size * sizeof (item_t));
113	0	if (unlikely (!new_items))
114	0	{
115	0	successful = false;
116	0	return false;
117	0	}
118	0	for (auto &_ : hb_iter (new_items, new_size))
119	0	_.clear ();
120
121	0	unsigned int old_size = mask + 1;
122	0	item_t *old_items = items;
123
124		/* Switch to new, empty, array. */
125	0	population = occupancy = 0;
126	0	mask = new_size - 1;
127	0	prime = prime_for (power);
128	0	items = new_items;
129
130		/* Insert back old items. */
131	0	if (old_items)
132	0	for (unsigned int i = 0; i < old_size; i++)
133	0	if (old_items[i].is_real ())
134	0	set_with_hash (old_items[i].key,
135	0	old_items[i].hash,
136	0	old_items[i].value);
137
138	0	hb_free (old_items);
139
140	0	return true;
141	0	} Unexecuted instantiation: hb_hashmap_t<hb_serialize_context_t::object_t const, unsigned int, (hb_serialize_context_t::object_t const)0, 0u>::resize() Unexecuted instantiation: hb_hashmap_t<unsigned int, unsigned int, 4294967295u, 4294967295u>::resize() Unexecuted instantiation: hb_hashmap_t<unsigned int, hb_set_t, 4294967295u, (hb_set_t)0>::resize()
142
143		bool set (K key, V value)
144	0	{
145	0	return set_with_hash (key, hb_hash (key), value);
146	0	} Unexecuted instantiation: hb_hashmap_t<hb_serialize_context_t::object_t const, unsigned int, (hb_serialize_context_t::object_t const)0, 0u>::set(hb_serialize_context_t::object_t const, unsigned int) Unexecuted instantiation: hb_hashmap_t<unsigned int, unsigned int, 4294967295u, 4294967295u>::set(unsigned int, unsigned int) Unexecuted instantiation: hb_hashmap_t<unsigned int, hb_set_t, 4294967295u, (hb_set_t)0>::set(unsigned int, hb_set_t)
147
148		V get (K key) const
149	0	{
150	0	if (unlikely (!items)) return vINVALID;
151	0	unsigned int i = bucket_for (key);
152	0	return items[i].is_real () && items[i] == key ? items[i].value : vINVALID;
153	0	} Unexecuted instantiation: hb_hashmap_t<hb_serialize_context_t::object_t const, unsigned int, (hb_serialize_context_t::object_t const)0, 0u>::get(hb_serialize_context_t::object_t const) const Unexecuted instantiation: hb_hashmap_t<unsigned int, unsigned int, 4294967295u, 4294967295u>::get(unsigned int) const Unexecuted instantiation: hb_hashmap_t<unsigned int, hb_set_t, 4294967295u, (hb_set_t*)0>::get(unsigned int) const
154
155	0	void del (K key) { set (key, vINVALID); } Unexecuted instantiation: hb_hashmap_t<hb_serialize_context_t::object_t const, unsigned int, (hb_serialize_context_t::object_t const)0, 0u>::del(hb_serialize_context_t::object_t const*) Unexecuted instantiation: hb_hashmap_t<unsigned int, unsigned int, 4294967295u, 4294967295u>::del(unsigned int)
156
157		/* Has interface. */
158		static constexpr V SENTINEL = vINVALID;
159		typedef V value_t;
160	0	value_t operator [] (K k) const { return get (k); } Unexecuted instantiation: hb_hashmap_t<unsigned int, unsigned int, 4294967295u, 4294967295u>::operator[](unsigned int) const Unexecuted instantiation: hb_hashmap_t<unsigned int, hb_set_t, 4294967295u, (hb_set_t)0>::operator[](unsigned int) const
161		bool has (K k, V *vp = nullptr) const
162	0	{
163	0	V v = (*this)[k];
164	0	if (vp) *vp = v;
165	0	return v != SENTINEL;
166	0	} Unexecuted instantiation: hb_hashmap_t<unsigned int, unsigned int, 4294967295u, 4294967295u>::has(unsigned int, unsigned int) const Unexecuted instantiation: hb_hashmap_t<unsigned int, hb_set_t, 4294967295u, (hb_set_t)0>::has(unsigned int, hb_set_t*) const
167		/* Projection. */
168		V operator () (K k) const { return get (k); }
169
170		void clear ()
171	0	{
172	0	if (items)
173	0	for (auto &_ : hb_iter (items, mask + 1))
174	0	_.clear ();
175	0
176	0	population = occupancy = 0;
177	0	}
178
179	0	bool is_empty () const { return population == 0; }
180		explicit operator bool () const { return !is_empty (); }
181
182	0	unsigned int get_population () const { return population; }
183
184		/*
185		* Iterator
186		*/
187		auto iter () const HB_AUTO_RETURN
188		(
189		+ hb_array (items, mask ? mask + 1 : 0)
190		\| hb_filter (&item_t::is_real)
191		\| hb_map (&item_t::get_pair)
192		)
193		auto keys () const HB_AUTO_RETURN
194		(
195		+ hb_array (items, mask ? mask + 1 : 0)
196		\| hb_filter (&item_t::is_real)
197		\| hb_map (&item_t::key)
198		\| hb_map (hb_ridentity)
199		)
200		auto values () const HB_AUTO_RETURN
201		(
202		+ hb_array (items, mask ? mask + 1 : 0)
203		\| hb_filter (&item_t::is_real)
204		\| hb_map (&item_t::value)
205		\| hb_map (hb_ridentity)
206		)
207
208		/* Sink interface. */
209		hb_hashmap_t& operator << (const hb_pair_t<K, V>& v)
210	0	{ set (v.first, v.second); return *this; }
211
212		protected:
213
214		bool set_with_hash (K key, uint32_t hash, V value)
215	0	{
216	0	if (unlikely (!successful)) return false;
217	0	if (unlikely (key == kINVALID)) return true;
218	0	if (unlikely ((occupancy + occupancy / 2) >= mask && !resize ())) return false;
219	0	unsigned int i = bucket_for_hash (key, hash);
220
221	0	if (value == vINVALID && items[i].key != key)
222	0	return true; /* Trying to delete non-existent key. */
223
224	0	if (!items[i].is_unused ())
225	0	{
226	0	occupancy--;
227	0	if (items[i].is_tombstone ())
228	0	population--;
229	0	}
230
231	0	items[i].key = key;
232	0	items[i].value = value;
233	0	items[i].hash = hash;
234
235	0	occupancy++;
236	0	if (!items[i].is_tombstone ())
237	0	population++;
238
239	0	return true;
240	0	} Unexecuted instantiation: hb_hashmap_t<hb_serialize_context_t::object_t const, unsigned int, (hb_serialize_context_t::object_t const)0, 0u>::set_with_hash(hb_serialize_context_t::object_t const, unsigned int, unsigned int) Unexecuted instantiation: hb_hashmap_t<unsigned int, unsigned int, 4294967295u, 4294967295u>::set_with_hash(unsigned int, unsigned int, unsigned int) Unexecuted instantiation: hb_hashmap_t<unsigned int, hb_set_t, 4294967295u, (hb_set_t)0>::set_with_hash(unsigned int, unsigned int, hb_set_t)
241
242		unsigned int bucket_for (K key) const
243	0	{
244	0	return bucket_for_hash (key, hb_hash (key));
245	0	} Unexecuted instantiation: hb_hashmap_t<hb_serialize_context_t::object_t const, unsigned int, (hb_serialize_context_t::object_t const)0, 0u>::bucket_for(hb_serialize_context_t::object_t const) const Unexecuted instantiation: hb_hashmap_t<unsigned int, unsigned int, 4294967295u, 4294967295u>::bucket_for(unsigned int) const Unexecuted instantiation: hb_hashmap_t<unsigned int, hb_set_t, 4294967295u, (hb_set_t*)0>::bucket_for(unsigned int) const
246
247		unsigned int bucket_for_hash (K key, uint32_t hash) const
248	0	{
249	0	unsigned int i = hash % prime;
250	0	unsigned int step = 0;
251	0	unsigned int tombstone = (unsigned) -1;
252	0	while (!items[i].is_unused ())
253	0	{
254	0	if (items[i].hash == hash && items[i] == key)
255	0	return i;
256	0	if (tombstone == (unsigned) -1 && items[i].is_tombstone ())
257	0	tombstone = i;
258	0	i = (i + ++step) & mask;
259	0	}
260	0	return tombstone == (unsigned) -1 ? i : tombstone;
261	0	} Unexecuted instantiation: hb_hashmap_t<hb_serialize_context_t::object_t const, unsigned int, (hb_serialize_context_t::object_t const)0, 0u>::bucket_for_hash(hb_serialize_context_t::object_t const, unsigned int) const Unexecuted instantiation: hb_hashmap_t<unsigned int, unsigned int, 4294967295u, 4294967295u>::bucket_for_hash(unsigned int, unsigned int) const Unexecuted instantiation: hb_hashmap_t<unsigned int, hb_set_t, 4294967295u, (hb_set_t*)0>::bucket_for_hash(unsigned int, unsigned int) const
262
263		static unsigned int prime_for (unsigned int shift)
264	0	{
265		/* Following comment and table copied from glib. */
266		/* Each table size has an associated prime modulo (the first prime
267		* lower than the table size) used to find the initial bucket. Probing
268		* then works modulo 2^n. The prime modulo is necessary to get a
269		* good distribution with poor hash functions.
270		*/
271		/* Not declaring static to make all kinds of compilers happy... */
272	0	/static/ const unsigned int prime_mod [32] =
273	0	{
274	0	1, /* For 1 << 0 */
275	0	2,
276	0	3,
277	0	7,
278	0	13,
279	0	31,
280	0	61,
281	0	127,
282	0	251,
283	0	509,
284	0	1021,
285	0	2039,
286	0	4093,
287	0	8191,
288	0	16381,
289	0	32749,
290	0	65521, /* For 1 << 16 */
291	0	131071,
292	0	262139,
293	0	524287,
294	0	1048573,
295	0	2097143,
296	0	4194301,
297	0	8388593,
298	0	16777213,
299	0	33554393,
300	0	67108859,
301	0	134217689,
302	0	268435399,
303	0	536870909,
304	0	1073741789,
305	0	2147483647 /* For 1 << 31 */
306	0	};
307
308	0	if (unlikely (shift >= ARRAY_LENGTH (prime_mod)))
309	0	return prime_mod[ARRAY_LENGTH (prime_mod) - 1];
310
311	0	return prime_mod[shift];
312	0	} Unexecuted instantiation: hb_hashmap_t<hb_serialize_context_t::object_t const, unsigned int, (hb_serialize_context_t::object_t const)0, 0u>::prime_for(unsigned int) Unexecuted instantiation: hb_hashmap_t<unsigned int, unsigned int, 4294967295u, 4294967295u>::prime_for(unsigned int) Unexecuted instantiation: hb_hashmap_t<unsigned int, hb_set_t, 4294967295u, (hb_set_t)0>::prime_for(unsigned int)
313		};
314
315		/*
316		* hb_map_t
317		*/
318
319		struct hb_map_t : hb_hashmap_t<hb_codepoint_t,
320		hb_codepoint_t,
321		HB_MAP_VALUE_INVALID,
322		HB_MAP_VALUE_INVALID> {};
323
324
325		#endif /* HB_MAP_HH */