[thirdparty/gcc.git] / libgomp / hashtab.h

/* An expandable hash tables datatype.
   Copyright (C) 1999-2024 Free Software Foundation, Inc.
   Contributed by Vladimir Makarov <vmakarov@cygnus.com>.

   This file is part of the GNU Offloading and Multi Processing Library
   (libgomp).

   Libgomp is free software; you can redistribute it and/or modify it
   under the terms of the GNU General Public License as published by
   the Free Software Foundation; either version 3, or (at your option)
   any later version.

   Libgomp is distributed in the hope that it will be useful, but WITHOUT ANY
   WARRANTY; without even the implied warranty of MERCHANTABILITY or FITNESS
   FOR A PARTICULAR PURPOSE.  See the GNU General Public License for
   more details.

   Under Section 7 of GPL version 3, you are granted additional
   permissions described in the GCC Runtime Library Exception, version
   3.1, as published by the Free Software Foundation.

   You should have received a copy of the GNU General Public License and
   a copy of the GCC Runtime Library Exception along with this program;
   see the files COPYING3 and COPYING.RUNTIME respectively.  If not, see
   <http://www.gnu.org/licenses/>.  */

/* The hash table code copied from include/hashtab.[hc] and adjusted,
   so that the hash table entries are in the flexible array at the end
   of the control structure, no callbacks are used and the elements in the
   table are of the hash_entry_type type.
   Before including this file, define hash_entry_type type and
   htab_alloc and htab_free functions.  After including it, define
   htab_hash and htab_eq inline functions.   */

/* This package implements basic hash table functionality.  It is possible
   to search for an entry, create an entry and destroy an entry.

   Elements in the table are generic pointers.

   The size of the table is not fixed; if the occupancy of the table
   grows too high the hash table will be expanded.

   The abstract data implementation is based on generalized Algorithm D
   from Knuth's book "The art of computer programming".  Hash table is
   expanded by creation of new hash table and transferring elements from
   the old table to the new table.  */

/* The type for a hash code.  */
typedef unsigned int hashval_t;

static inline hashval_t htab_hash (hash_entry_type);
static inline bool htab_eq (hash_entry_type, hash_entry_type);

/* This macro defines reserved value for empty table entry.  */

#define HTAB_EMPTY_ENTRY    ((hash_entry_type) 0)

/* This macro defines reserved value for table entry which contained
   a deleted element. */

#define HTAB_DELETED_ENTRY  ((hash_entry_type) 1)

/* Hash tables are of the following type.  The structure
   (implementation) of this type is not needed for using the hash
   tables.  All work with hash table should be executed only through
   functions mentioned below.  The size of this structure is subject to
   change.  */

struct htab {
  /* Current size (in entries) of the hash table.  */
  size_t size;

  /* Current number of elements including also deleted elements.  */
  size_t n_elements;

  /* Current number of deleted elements in the table.  */
  size_t n_deleted;

  /* Current size (in entries) of the hash table, as an index into the
     table of primes.  */
  unsigned int size_prime_index;

  /* Table itself.  */
  hash_entry_type entries[];
};

typedef struct htab *htab_t;

/* An enum saying whether we insert into the hash table or not.  */
enum insert_option {NO_INSERT, INSERT};

/* Table of primes and multiplicative inverses.

   Note that these are not minimally reduced inverses.  Unlike when generating
   code to divide by a constant, we want to be able to use the same algorithm
   all the time.  All of these inverses (are implied to) have bit 32 set.

   For the record, the function that computed the table is in
   libiberty/hashtab.c.  */

struct prime_ent
{
  hashval_t prime;
  hashval_t inv;
  hashval_t inv_m2;	/* inverse of prime-2 */
  hashval_t shift;
};

static struct prime_ent const prime_tab[] = {
  {          7, 0x24924925, 0x9999999b, 2 },
  {         13, 0x3b13b13c, 0x745d1747, 3 },
  {         31, 0x08421085, 0x1a7b9612, 4 },
  {         61, 0x0c9714fc, 0x15b1e5f8, 5 },
  {        127, 0x02040811, 0x0624dd30, 6 },
  {        251, 0x05197f7e, 0x073260a5, 7 },
  {        509, 0x01824366, 0x02864fc8, 8 },
  {       1021, 0x00c0906d, 0x014191f7, 9 },
  {       2039, 0x0121456f, 0x0161e69e, 10 },
  {       4093, 0x00300902, 0x00501908, 11 },
  {       8191, 0x00080041, 0x00180241, 12 },
  {      16381, 0x000c0091, 0x00140191, 13 },
  {      32749, 0x002605a5, 0x002a06e6, 14 },
  {      65521, 0x000f00e2, 0x00110122, 15 },
  {     131071, 0x00008001, 0x00018003, 16 },
  {     262139, 0x00014002, 0x0001c004, 17 },
  {     524287, 0x00002001, 0x00006001, 18 },
  {    1048573, 0x00003001, 0x00005001, 19 },
  {    2097143, 0x00004801, 0x00005801, 20 },
  {    4194301, 0x00000c01, 0x00001401, 21 },
  {    8388593, 0x00001e01, 0x00002201, 22 },
  {   16777213, 0x00000301, 0x00000501, 23 },
  {   33554393, 0x00001381, 0x00001481, 24 },
  {   67108859, 0x00000141, 0x000001c1, 25 },
  {  134217689, 0x000004e1, 0x00000521, 26 },
  {  268435399, 0x00000391, 0x000003b1, 27 },
  {  536870909, 0x00000019, 0x00000029, 28 },
  { 1073741789, 0x0000008d, 0x00000095, 29 },
  { 2147483647, 0x00000003, 0x00000007, 30 },
  /* Avoid "decimal constant so large it is unsigned" for 4294967291.  */
  { 0xfffffffb, 0x00000006, 0x00000008, 31 }
};

/* The following function returns an index into the above table of the
   nearest prime number which is greater than N, and near a power of two. */

static unsigned int
higher_prime_index (unsigned long n)
{
  unsigned int low = 0;
  unsigned int high = sizeof(prime_tab) / sizeof(prime_tab[0]);

  while (low != high)
    {
      unsigned int mid = low + (high - low) / 2;
      if (n > prime_tab[mid].prime)
	low = mid + 1;
      else
	high = mid;
    }

  /* If we've run out of primes, abort.  */
  if (n > prime_tab[low].prime)
    abort ();

  return low;
}

/* Return the current size of given hash table.  */

static inline size_t
htab_size (htab_t htab)
{
  return htab->size;
}

/* Return the current number of elements in given hash table. */

static inline size_t
htab_elements (htab_t htab)
{
  return htab->n_elements - htab->n_deleted;
}

/* Return X % Y.  */

static inline hashval_t
htab_mod_1 (hashval_t x, hashval_t y, hashval_t inv, int shift)
{
  /* The multiplicative inverses computed above are for 32-bit types, and
     requires that we be able to compute a highpart multiply.  */
  if (sizeof (hashval_t) * __CHAR_BIT__ <= 32)
    {
      hashval_t t1, t2, t3, t4, q, r;

      t1 = ((unsigned long long)x * inv) >> 32;
      t2 = x - t1;
      t3 = t2 >> 1;
      t4 = t1 + t3;
      q  = t4 >> shift;
      r  = x - (q * y);

      return r;
    }

  /* Otherwise just use the native division routines.  */
  return x % y;
}

/* Compute the primary hash for HASH given HTAB's current size.  */

static inline hashval_t
htab_mod (hashval_t hash, htab_t htab)
{
  const struct prime_ent *p = &prime_tab[htab->size_prime_index];
  return htab_mod_1 (hash, p->prime, p->inv, p->shift);
}

/* Compute the secondary hash for HASH given HTAB's current size.  */

static inline hashval_t
htab_mod_m2 (hashval_t hash, htab_t htab)
{
  const struct prime_ent *p = &prime_tab[htab->size_prime_index];
  return 1 + htab_mod_1 (hash, p->prime - 2, p->inv_m2, p->shift);
}

static inline htab_t
htab_clear (htab_t htab)
{
  htab->n_elements = 0;
  htab->n_deleted = 0;
  memset (htab->entries, 0, htab->size * sizeof (hash_entry_type));
  return htab;
}

/* Create hash table of size SIZE.  */

static htab_t
htab_create (size_t size)
{
  htab_t result;
  unsigned int size_prime_index;

  size_prime_index = higher_prime_index (size);
  size = prime_tab[size_prime_index].prime;

  result = (htab_t) htab_alloc (sizeof (struct htab)
				+ size * sizeof (hash_entry_type));
  result->size = size;
  result->size_prime_index = size_prime_index;
  return htab_clear (result);
}

/* Similar to htab_find_slot, but without several unwanted side effects:
    - Does not call htab_eq when it finds an existing entry.
    - Does not change the count of elements in the hash table.
   This function also assumes there are no deleted entries in the table.
   HASH is the hash value for the element to be inserted.  */

static hash_entry_type *
find_empty_slot_for_expand (htab_t htab, hashval_t hash)
{
  hashval_t index = htab_mod (hash, htab);
  size_t size = htab_size (htab);
  hash_entry_type *slot = htab->entries + index;
  hashval_t hash2;

  if (*slot == HTAB_EMPTY_ENTRY)
    return slot;
  else if (*slot == HTAB_DELETED_ENTRY)
    abort ();

  hash2 = htab_mod_m2 (hash, htab);
  for (;;)
    {
      index += hash2;
      if (index >= size)
	index -= size;

      slot = htab->entries + index;
      if (*slot == HTAB_EMPTY_ENTRY)
	return slot;
      else if (*slot == HTAB_DELETED_ENTRY)
	abort ();
    }
}

/* The following function changes size of memory allocated for the
   entries and repeatedly inserts the table elements.  The occupancy
   of the table after the call will be about 50%.  Naturally the hash
   table must already exist.  Remember also that the place of the
   table entries is changed.  */

static htab_t
htab_expand (htab_t htab)
{
  htab_t nhtab;
  hash_entry_type *olimit;
  hash_entry_type *p;
  size_t osize, elts;

  osize = htab->size;
  olimit = htab->entries + osize;
  elts = htab_elements (htab);

  /* Resize only when table after removal of unused elements is either
     too full or too empty.  */
  if (elts * 2 > osize || (elts * 8 < osize && osize > 32))
    nhtab = htab_create (elts * 2);
  else
    nhtab = htab_create (osize - 1);
  nhtab->n_elements = htab->n_elements - htab->n_deleted;

  p = htab->entries;
  do
    {
      hash_entry_type x = *p;

      if (x != HTAB_EMPTY_ENTRY && x != HTAB_DELETED_ENTRY)
	*find_empty_slot_for_expand (nhtab, htab_hash (x)) = x;

      p++;
    }
  while (p < olimit);

  htab_free (htab);
  return nhtab;
}

/* This function searches for a hash table entry equal to the given
   element.  It cannot be used to insert or delete an element.  */

static hash_entry_type
htab_find (htab_t htab, const hash_entry_type element)
{
  hashval_t index, hash2, hash = htab_hash (element);
  size_t size;
  hash_entry_type entry;

  size = htab_size (htab);
  index = htab_mod (hash, htab);

  entry = htab->entries[index];
  if (entry == HTAB_EMPTY_ENTRY
      || (entry != HTAB_DELETED_ENTRY && htab_eq (entry, element)))
    return entry;

  hash2 = htab_mod_m2 (hash, htab);
  for (;;)
    {
      index += hash2;
      if (index >= size)
	index -= size;

      entry = htab->entries[index];
      if (entry == HTAB_EMPTY_ENTRY
	  || (entry != HTAB_DELETED_ENTRY && htab_eq (entry, element)))
	return entry;
    }
}

/* This function searches for a hash table slot containing an entry
   equal to the given element.  To delete an entry, call this with
   insert=NO_INSERT, then call htab_clear_slot on the slot returned
   (possibly after doing some checks).  To insert an entry, call this
   with insert=INSERT, then write the value you want into the returned
   slot.  */

static hash_entry_type *
htab_find_slot (htab_t *htabp, const hash_entry_type element,
		enum insert_option insert)
{
  hash_entry_type *first_deleted_slot;
  hashval_t index, hash2, hash = htab_hash (element);
  size_t size;
  hash_entry_type entry;
  htab_t htab = *htabp;

  size = htab_size (htab);
  if (insert == INSERT && size * 3 <= htab->n_elements * 4)
    {
      htab = *htabp = htab_expand (htab);
      size = htab_size (htab);
    }

  index = htab_mod (hash, htab);

  first_deleted_slot = NULL;

  entry = htab->entries[index];
  if (entry == HTAB_EMPTY_ENTRY)
    goto empty_entry;
  else if (entry == HTAB_DELETED_ENTRY)
    first_deleted_slot = &htab->entries[index];
  else if (htab_eq (entry, element))
    return &htab->entries[index];

  hash2 = htab_mod_m2 (hash, htab);
  for (;;)
    {
      index += hash2;
      if (index >= size)
	index -= size;

      entry = htab->entries[index];
      if (entry == HTAB_EMPTY_ENTRY)
	goto empty_entry;
      else if (entry == HTAB_DELETED_ENTRY)
	{
	  if (!first_deleted_slot)
	    first_deleted_slot = &htab->entries[index];
	}
      else if (htab_eq (entry, element))
	return &htab->entries[index];
    }

 empty_entry:
  if (insert == NO_INSERT)
    return NULL;

  if (first_deleted_slot)
    {
      htab->n_deleted--;
      *first_deleted_slot = HTAB_EMPTY_ENTRY;
      return first_deleted_slot;
    }

  htab->n_elements++;
  return &htab->entries[index];
}

/* This function clears a specified slot in a hash table.  It is
   useful when you've already done the lookup and don't want to do it
   again.  */

static inline void
htab_clear_slot (htab_t htab, hash_entry_type *slot)
{
  if (slot < htab->entries || slot >= htab->entries + htab_size (htab)
      || *slot == HTAB_EMPTY_ENTRY || *slot == HTAB_DELETED_ENTRY)
    abort ();

  *slot = HTAB_DELETED_ENTRY;
  htab->n_deleted++;
}

/* Returns a hash code for pointer P. Simplified version of evahash */

static inline hashval_t
hash_pointer (const void *p)
{
  uintptr_t v = (uintptr_t) p;
  if (sizeof (v) > sizeof (hashval_t))
    v ^= v >> (sizeof (uintptr_t) / 2 * __CHAR_BIT__);
  return v;
}
Commit	Line	Data
acf0174b	1	/* An expandable hash tables datatype.
a945c346	2	Copyright (C) 1999-2024 Free Software Foundation, Inc.
acf0174b JJ	3	Contributed by Vladimir Makarov <vmakarov@cygnus.com>.
acf0174b JJ	4
f10e37a1 JJ	5	This file is part of the GNU Offloading and Multi Processing Library
	6	(libgomp).
	7
	8	Libgomp is free software; you can redistribute it and/or modify it
	9	under the terms of the GNU General Public License as published by
	10	the Free Software Foundation; either version 3, or (at your option)
	11	any later version.
	12
	13	Libgomp is distributed in the hope that it will be useful, but WITHOUT ANY
	14	WARRANTY; without even the implied warranty of MERCHANTABILITY or FITNESS
	15	FOR A PARTICULAR PURPOSE. See the GNU General Public License for
	16	more details.
	17
	18	Under Section 7 of GPL version 3, you are granted additional
	19	permissions described in the GCC Runtime Library Exception, version
	20	3.1, as published by the Free Software Foundation.
	21
	22	You should have received a copy of the GNU General Public License and
	23	a copy of the GCC Runtime Library Exception along with this program;
	24	see the files COPYING3 and COPYING.RUNTIME respectively. If not, see
	25	<http://www.gnu.org/licenses/>. */
acf0174b JJ	26
	27	/* The hash table code copied from include/hashtab.[hc] and adjusted,
	28	so that the hash table entries are in the flexible array at the end
	29	of the control structure, no callbacks are used and the elements in the
	30	table are of the hash_entry_type type.
	31	Before including this file, define hash_entry_type type and
	32	htab_alloc and htab_free functions. After including it, define
	33	htab_hash and htab_eq inline functions. */
	34
	35	/* This package implements basic hash table functionality. It is possible
	36	to search for an entry, create an entry and destroy an entry.
	37
	38	Elements in the table are generic pointers.
	39
	40	The size of the table is not fixed; if the occupancy of the table
	41	grows too high the hash table will be expanded.
	42
	43	The abstract data implementation is based on generalized Algorithm D
	44	from Knuth's book "The art of computer programming". Hash table is
	45	expanded by creation of new hash table and transferring elements from
	46	the old table to the new table. */
	47
	48	/* The type for a hash code. */
	49	typedef unsigned int hashval_t;
	50
	51	static inline hashval_t htab_hash (hash_entry_type);
	52	static inline bool htab_eq (hash_entry_type, hash_entry_type);
	53
	54	/* This macro defines reserved value for empty table entry. */
	55
	56	#define HTAB_EMPTY_ENTRY ((hash_entry_type) 0)
	57
	58	/* This macro defines reserved value for table entry which contained
	59	a deleted element. */
	60
	61	#define HTAB_DELETED_ENTRY ((hash_entry_type) 1)
	62
	63	/* Hash tables are of the following type. The structure
	64	(implementation) of this type is not needed for using the hash
	65	tables. All work with hash table should be executed only through
	66	functions mentioned below. The size of this structure is subject to
	67	change. */
	68
	69	struct htab {
	70	/* Current size (in entries) of the hash table. */
	71	size_t size;
	72
	73	/* Current number of elements including also deleted elements. */
	74	size_t n_elements;
	75
	76	/* Current number of deleted elements in the table. */
	77	size_t n_deleted;
	78
	79	/* Current size (in entries) of the hash table, as an index into the
	80	table of primes. */
	81	unsigned int size_prime_index;
	82
	83	/* Table itself. */
	84	hash_entry_type entries[];
	85	};
	86
	87	typedef struct htab *htab_t;
	88
	89	/* An enum saying whether we insert into the hash table or not. */
90	enum insert_option {NO_INSERT, INSERT};
91
92	/* Table of primes and multiplicative inverses.
93
94	Note that these are not minimally reduced inverses. Unlike when generating
95	code to divide by a constant, we want to be able to use the same algorithm
96	all the time. All of these inverses (are implied to) have bit 32 set.
97
98	For the record, the function that computed the table is in
99	libiberty/hashtab.c. */
100
101	struct prime_ent
102	{
103	hashval_t prime;
104	hashval_t inv;
105	hashval_t inv_m2; /* inverse of prime-2 */
106	hashval_t shift;
107	};
108
109	static struct prime_ent const prime_tab[] = {
110	{ 7, 0x24924925, 0x9999999b, 2 },
111	{ 13, 0x3b13b13c, 0x745d1747, 3 },
112	{ 31, 0x08421085, 0x1a7b9612, 4 },
113	{ 61, 0x0c9714fc, 0x15b1e5f8, 5 },
114	{ 127, 0x02040811, 0x0624dd30, 6 },
115	{ 251, 0x05197f7e, 0x073260a5, 7 },
116	{ 509, 0x01824366, 0x02864fc8, 8 },
117	{ 1021, 0x00c0906d, 0x014191f7, 9 },
118	{ 2039, 0x0121456f, 0x0161e69e, 10 },
119	{ 4093, 0x00300902, 0x00501908, 11 },
120	{ 8191, 0x00080041, 0x00180241, 12 },
121	{ 16381, 0x000c0091, 0x00140191, 13 },
122	{ 32749, 0x002605a5, 0x002a06e6, 14 },
123	{ 65521, 0x000f00e2, 0x00110122, 15 },
124	{ 131071, 0x00008001, 0x00018003, 16 },
125	{ 262139, 0x00014002, 0x0001c004, 17 },
126	{ 524287, 0x00002001, 0x00006001, 18 },
127	{ 1048573, 0x00003001, 0x00005001, 19 },
128	{ 2097143, 0x00004801, 0x00005801, 20 },
129	{ 4194301, 0x00000c01, 0x00001401, 21 },
130	{ 8388593, 0x00001e01, 0x00002201, 22 },
131	{ 16777213, 0x00000301, 0x00000501, 23 },
132	{ 33554393, 0x00001381, 0x00001481, 24 },
133	{ 67108859, 0x00000141, 0x000001c1, 25 },
134	{ 134217689, 0x000004e1, 0x00000521, 26 },
135	{ 268435399, 0x00000391, 0x000003b1, 27 },
136	{ 536870909, 0x00000019, 0x00000029, 28 },
137	{ 1073741789, 0x0000008d, 0x00000095, 29 },
138	{ 2147483647, 0x00000003, 0x00000007, 30 },
139	/* Avoid "decimal constant so large it is unsigned" for 4294967291. */
140	{ 0xfffffffb, 0x00000006, 0x00000008, 31 }
141	};
142
143	/* The following function returns an index into the above table of the
144	nearest prime number which is greater than N, and near a power of two. */
145
146	static unsigned int
147	higher_prime_index (unsigned long n)
148	{
149	unsigned int low = 0;
150	unsigned int high = sizeof(prime_tab) / sizeof(prime_tab[0]);
151
152	while (low != high)
153	{
154	unsigned int mid = low + (high - low) / 2;
155	if (n > prime_tab[mid].prime)
156	low = mid + 1;
157	else
158	high = mid;
159	}
160
161	/* If we've run out of primes, abort. */
162	if (n > prime_tab[low].prime)
163	abort ();
164
165	return low;
166	}
167
168	/* Return the current size of given hash table. */
169
170	static inline size_t
171	htab_size (htab_t htab)
172	{
173	return htab->size;
174	}
175
176	/* Return the current number of elements in given hash table. */
177
178	static inline size_t
179	htab_elements (htab_t htab)
180	{
181	return htab->n_elements - htab->n_deleted;
182	}
183
184	/* Return X % Y. */
185
186	static inline hashval_t
187	htab_mod_1 (hashval_t x, hashval_t y, hashval_t inv, int shift)
188	{
189	/* The multiplicative inverses computed above are for 32-bit types, and
190	requires that we be able to compute a highpart multiply. */
191	if (sizeof (hashval_t) * __CHAR_BIT__ <= 32)
192	{
193	hashval_t t1, t2, t3, t4, q, r;
194
195	t1 = ((unsigned long long)x * inv) >> 32;
196	t2 = x - t1;
197	t3 = t2 >> 1;
198	t4 = t1 + t3;
199	q = t4 >> shift;
200	r = x - (q * y);
201
202	return r;
203	}
204
205	/* Otherwise just use the native division routines. */
206	return x % y;
207	}
208
209	/* Compute the primary hash for HASH given HTAB's current size. */
210
211	static inline hashval_t
212	htab_mod (hashval_t hash, htab_t htab)
213	{
214	const struct prime_ent *p = &prime_tab[htab->size_prime_index];
215	return htab_mod_1 (hash, p->prime, p->inv, p->shift);
216	}
217
218	/* Compute the secondary hash for HASH given HTAB's current size. */
219
220	static inline hashval_t
221	htab_mod_m2 (hashval_t hash, htab_t htab)
222	{
223	const struct prime_ent *p = &prime_tab[htab->size_prime_index];
224	return 1 + htab_mod_1 (hash, p->prime - 2, p->inv_m2, p->shift);
225	}
226
275c736e CLT	227	static inline htab_t
	228	htab_clear (htab_t htab)
	229	{
	230	htab->n_elements = 0;
	231	htab->n_deleted = 0;
	232	memset (htab->entries, 0, htab->size * sizeof (hash_entry_type));
	233	return htab;
	234	}
	235
acf0174b JJ	236	/* Create hash table of size SIZE. */
	237
	238	static htab_t
	239	htab_create (size_t size)
	240	{
	241	htab_t result;
	242	unsigned int size_prime_index;
	243
	244	size_prime_index = higher_prime_index (size);
	245	size = prime_tab[size_prime_index].prime;
	246
	247	result = (htab_t) htab_alloc (sizeof (struct htab)
	248	+ size * sizeof (hash_entry_type));
	249	result->size = size;
acf0174b	250	result->size_prime_index = size_prime_index;
275c736e	251	return htab_clear (result);
acf0174b JJ	252	}
	253
	254	/* Similar to htab_find_slot, but without several unwanted side effects:
	255	- Does not call htab_eq when it finds an existing entry.
	256	- Does not change the count of elements in the hash table.
	257	This function also assumes there are no deleted entries in the table.
	258	HASH is the hash value for the element to be inserted. */
	259
	260	static hash_entry_type *
	261	find_empty_slot_for_expand (htab_t htab, hashval_t hash)
	262	{
	263	hashval_t index = htab_mod (hash, htab);
	264	size_t size = htab_size (htab);
	265	hash_entry_type *slot = htab->entries + index;
	266	hashval_t hash2;
	267
	268	if (*slot == HTAB_EMPTY_ENTRY)
	269	return slot;
	270	else if (*slot == HTAB_DELETED_ENTRY)
	271	abort ();
	272
	273	hash2 = htab_mod_m2 (hash, htab);
	274	for (;;)
	275	{
	276	index += hash2;
	277	if (index >= size)
	278	index -= size;
	279
	280	slot = htab->entries + index;
	281	if (*slot == HTAB_EMPTY_ENTRY)
	282	return slot;
	283	else if (*slot == HTAB_DELETED_ENTRY)
	284	abort ();
	285	}
	286	}
	287
	288	/* The following function changes size of memory allocated for the
	289	entries and repeatedly inserts the table elements. The occupancy
	290	of the table after the call will be about 50%. Naturally the hash
	291	table must already exist. Remember also that the place of the
	292	table entries is changed. */
	293
	294	static htab_t
	295	htab_expand (htab_t htab)
	296	{
	297	htab_t nhtab;
	298	hash_entry_type *olimit;
	299	hash_entry_type *p;
	300	size_t osize, elts;
	301
	302	osize = htab->size;
	303	olimit = htab->entries + osize;
	304	elts = htab_elements (htab);
	305
	306	/* Resize only when table after removal of unused elements is either
	307	too full or too empty. */
	308	if (elts * 2 > osize \|\| (elts * 8 < osize && osize > 32))
	309	nhtab = htab_create (elts * 2);
	310	else
	311	nhtab = htab_create (osize - 1);
	312	nhtab->n_elements = htab->n_elements - htab->n_deleted;
	313
	314	p = htab->entries;
	315	do
316	{
317	hash_entry_type x = *p;
318
319	if (x != HTAB_EMPTY_ENTRY && x != HTAB_DELETED_ENTRY)
320	*find_empty_slot_for_expand (nhtab, htab_hash (x)) = x;
321
322	p++;
323	}
324	while (p < olimit);
325
326	htab_free (htab);
327	return nhtab;
328	}
329
330	/* This function searches for a hash table entry equal to the given
331	element. It cannot be used to insert or delete an element. */
332
333	static hash_entry_type
334	htab_find (htab_t htab, const hash_entry_type element)
335	{
336	hashval_t index, hash2, hash = htab_hash (element);
337	size_t size;
338	hash_entry_type entry;
339
340	size = htab_size (htab);
341	index = htab_mod (hash, htab);
342
343	entry = htab->entries[index];
344	if (entry == HTAB_EMPTY_ENTRY
345	\|\| (entry != HTAB_DELETED_ENTRY && htab_eq (entry, element)))
346	return entry;
347
348	hash2 = htab_mod_m2 (hash, htab);
349	for (;;)
350	{
351	index += hash2;
352	if (index >= size)
353	index -= size;
354
355	entry = htab->entries[index];
356	if (entry == HTAB_EMPTY_ENTRY
357	\|\| (entry != HTAB_DELETED_ENTRY && htab_eq (entry, element)))
358	return entry;
359	}
360	}
361
362	/* This function searches for a hash table slot containing an entry
363	equal to the given element. To delete an entry, call this with
364	insert=NO_INSERT, then call htab_clear_slot on the slot returned
365	(possibly after doing some checks). To insert an entry, call this
366	with insert=INSERT, then write the value you want into the returned
367	slot. */
368
369	static hash_entry_type *
370	htab_find_slot (htab_t *htabp, const hash_entry_type element,
371	enum insert_option insert)
372	{
373	hash_entry_type *first_deleted_slot;
374	hashval_t index, hash2, hash = htab_hash (element);
375	size_t size;
376	hash_entry_type entry;
377	htab_t htab = *htabp;
378
379	size = htab_size (htab);
380	if (insert == INSERT && size * 3 <= htab->n_elements * 4)
381	{
382	htab = *htabp = htab_expand (htab);
383	size = htab_size (htab);
384	}
385
386	index = htab_mod (hash, htab);
387
388	first_deleted_slot = NULL;
389
390	entry = htab->entries[index];
391	if (entry == HTAB_EMPTY_ENTRY)
392	goto empty_entry;
393	else if (entry == HTAB_DELETED_ENTRY)
394	first_deleted_slot = &htab->entries[index];
395	else if (htab_eq (entry, element))
396	return &htab->entries[index];
397
398	hash2 = htab_mod_m2 (hash, htab);
399	for (;;)
400	{
401	index += hash2;
402	if (index >= size)
403	index -= size;
404
405	entry = htab->entries[index];
406	if (entry == HTAB_EMPTY_ENTRY)
407	goto empty_entry;
408	else if (entry == HTAB_DELETED_ENTRY)
409	{
410	if (!first_deleted_slot)
411	first_deleted_slot = &htab->entries[index];
412	}
413	else if (htab_eq (entry, element))
414	return &htab->entries[index];
415	}
416
417	empty_entry:
418	if (insert == NO_INSERT)
419	return NULL;
420
421	if (first_deleted_slot)
422	{
423	htab->n_deleted--;
424	*first_deleted_slot = HTAB_EMPTY_ENTRY;
425	return first_deleted_slot;
426	}
427
428	htab->n_elements++;
429	return &htab->entries[index];
430	}
431
432	/* This function clears a specified slot in a hash table. It is
433	useful when you've already done the lookup and don't want to do it
434	again. */
435
436	static inline void
437	htab_clear_slot (htab_t htab, hash_entry_type *slot)
438	{
439	if (slot < htab->entries \|\| slot >= htab->entries + htab_size (htab)
440	\|\| slot == HTAB_EMPTY_ENTRY \|\| slot == HTAB_DELETED_ENTRY)
441	abort ();
442
443	*slot = HTAB_DELETED_ENTRY;
444	htab->n_deleted++;
445	}
446
447	/* Returns a hash code for pointer P. Simplified version of evahash */
448
449	static inline hashval_t
450	hash_pointer (const void *p)
451	{
452	uintptr_t v = (uintptr_t) p;
453	if (sizeof (v) > sizeof (hashval_t))
454	v ^= v >> (sizeof (uintptr_t) / 2 * __CHAR_BIT__);
455	return v;
456	}