[thirdparty/gcc.git] / gcc / hash-map-tests.c

/* Unit tests for hash-map.h.
   Copyright (C) 2015-2020 Free Software Foundation, Inc.

This file is part of GCC.

GCC 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.

GCC 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.

You should have received a copy of the GNU General Public License
along with GCC; see the file COPYING3.  If not see
<http://www.gnu.org/licenses/>.  */

#include "config.h"
#include "system.h"
#include "coretypes.h"
#include "tm.h"
#include "opts.h"
#include "hash-set.h"
#include "fixed-value.h"
#include "alias.h"
#include "flags.h"
#include "symtab.h"
#include "tree-core.h"
#include "stor-layout.h"
#include "tree.h"
#include "stringpool.h"
#include "selftest.h"

#if CHECKING_P

namespace selftest {

/* Construct a hash_map <const char *, int> and verify that
   various operations work correctly.  */

static void
test_map_of_strings_to_int ()
{
  hash_map <const char *, int> m;

  const char *ostrich = "ostrich";
  const char *elephant = "elephant";
  const char *ant = "ant";
  const char *spider = "spider";
  const char *millipede = "Illacme plenipes";
  const char *eric = "half a bee";

  /* A fresh hash_map should be empty.  */
  ASSERT_TRUE (m.is_empty ());
  ASSERT_EQ (NULL, m.get (ostrich));

  /* Populate the hash_map.  */
  ASSERT_EQ (false, m.put (ostrich, 2));
  ASSERT_EQ (false, m.put (elephant, 4));
  ASSERT_EQ (false, m.put (ant, 6));
  ASSERT_EQ (false, m.put (spider, 8));
  ASSERT_EQ (false, m.put (millipede, 750));
  ASSERT_EQ (false, m.put (eric, 3));

  /* Verify that we can recover the stored values.  */
  ASSERT_EQ (6, m.elements ());
  ASSERT_EQ (2, *m.get (ostrich));
  ASSERT_EQ (4, *m.get (elephant));
  ASSERT_EQ (6, *m.get (ant));
  ASSERT_EQ (8, *m.get (spider));
  ASSERT_EQ (750, *m.get (millipede));
  ASSERT_EQ (3, *m.get (eric));

  /* Verify removing an item.  */
  m.remove (eric);
  ASSERT_EQ (5, m.elements ());
  ASSERT_EQ (NULL, m.get (eric));

  m.remove (eric);
  ASSERT_EQ (5, m.elements ());
  ASSERT_EQ (NULL, m.get (eric));

  /* A plain char * key is hashed based on its value (address), rather
     than the string it points to.  */
  char *another_ant = static_cast <char *> (xcalloc (4, 1));
  another_ant[0] = 'a';
  another_ant[1] = 'n';
  another_ant[2] = 't';
  another_ant[3] = 0;
  ASSERT_NE (ant, another_ant);
  unsigned prev_size = m.elements ();
  ASSERT_EQ (false, m.put (another_ant, 7));
  ASSERT_EQ (prev_size + 1, m.elements ());

  /* Need to use string_hash or nofree_string_hash key types to hash
     based on the string contents.  */
  hash_map <nofree_string_hash, int> string_map;
  ASSERT_EQ (false, string_map.put (ant, 1));
  ASSERT_EQ (1, string_map.elements ());
  ASSERT_EQ (true, string_map.put (another_ant, 5));
  ASSERT_EQ (1, string_map.elements ());

  free (another_ant);
}

/* Construct a hash_map using int_hash and verify that
   various operations work correctly.  */

static void
test_map_of_int_to_strings ()
{
  const int EMPTY = -1;
  const int DELETED = -2;
  typedef int_hash <int, EMPTY, DELETED> int_hash_t;
  hash_map <int_hash_t, const char *> m;

  const char *ostrich = "ostrich";
  const char *elephant = "elephant";
  const char *ant = "ant";
  const char *spider = "spider";
  const char *millipede = "Illacme plenipes";
  const char *eric = "half a bee";

  /* A fresh hash_map should be empty.  */
  ASSERT_EQ (0, m.elements ());
  ASSERT_EQ (NULL, m.get (2));

  /* Populate the hash_map.  */
  ASSERT_EQ (false, m.put (2, ostrich));
  ASSERT_EQ (false, m.put (4, elephant));
  ASSERT_EQ (false, m.put (6, ant));
  ASSERT_EQ (false, m.put (8, spider));
  ASSERT_EQ (false, m.put (750, millipede));
  ASSERT_EQ (false, m.put (3, eric));

  /* Verify that we can recover the stored values.  */
  ASSERT_EQ (6, m.elements ());
  ASSERT_EQ (*m.get (2), ostrich);
  ASSERT_EQ (*m.get (4), elephant);
  ASSERT_EQ (*m.get (6), ant);
  ASSERT_EQ (*m.get (8), spider);
  ASSERT_EQ (*m.get (750), millipede);
  ASSERT_EQ (*m.get (3), eric);
}

typedef class hash_map_test_val_t
{
public:
  static int ndefault;
  static int ncopy;
  static int nassign;
  static int ndtor;

  hash_map_test_val_t ()
    : ptr (&ptr)
  {
    ++ndefault;
  }

  hash_map_test_val_t (const hash_map_test_val_t &rhs)
    : ptr (&ptr)
  {
    ++ncopy;
    gcc_assert (rhs.ptr == &rhs.ptr);
  }

  hash_map_test_val_t& operator= (const hash_map_test_val_t &rhs)
  {
    ++nassign;
    gcc_assert (ptr == &ptr);
    gcc_assert (rhs.ptr == &rhs.ptr);
    return *this;
  }

  ~hash_map_test_val_t ()
  {
    gcc_assert (ptr == &ptr);
    ++ndtor;
  }

  void *ptr;
} val_t;

int val_t::ndefault;
int val_t::ncopy;
int val_t::nassign;
int val_t::ndtor;

static void
test_map_of_type_with_ctor_and_dtor ()
{
  typedef hash_map <void *, val_t> Map;

  {
    /* Test default ctor.  */
    Map m;
    (void)&m;
  }

  ASSERT_TRUE (val_t::ndefault == 0);
  ASSERT_TRUE (val_t::ncopy == 0);
  ASSERT_TRUE (val_t::nassign == 0);
  ASSERT_TRUE (val_t::ndtor == 0);

  {
    /* Test single insertion.  */
    Map m;
    void *p = &p;
    m.get_or_insert (p);
  }

  ASSERT_TRUE (val_t::ndefault + val_t::ncopy == val_t::ndtor);

  {
    /* Test copy ctor.  */
    Map m1;
    void *p = &p;
    val_t &rv1 = m1.get_or_insert (p);

    int ncopy = val_t::ncopy;
    int nassign = val_t::nassign;

    Map m2 (m1);
    val_t *pv2 = m2.get (p);

    ASSERT_TRUE (ncopy + 1 == val_t::ncopy);
    ASSERT_TRUE (nassign == val_t::nassign);

    ASSERT_TRUE (&rv1 != pv2);
  }

  ASSERT_TRUE (val_t::ndefault + val_t::ncopy == val_t::ndtor);

#if 0   /* Avoid testing until bug 90959 is fixed.  */
  {
    /* Test copy assignment into an empty map.  */
    Map m1;
    void *p = &p;
    val_t &rv1 = m1.get_or_insert (p);

    int ncopy = val_t::ncopy;
    int nassign = val_t::nassign;

    Map m2;
    m2 = m1;
    val_t *pv2 = m2.get (p);

    ASSERT_TRUE (ncopy == val_t::ncopy);
    ASSERT_TRUE (nassign + 1 == val_t::nassign);

    ASSERT_TRUE (&rv1 != pv2);
  }

  ASSERT_TRUE (val_t::ndefault + val_t::ncopy == val_t::ndtor);

#endif

  {
    Map m;
    void *p = &p, *q = &q;
    val_t &v1 = m.get_or_insert (p);
    val_t &v2 = m.get_or_insert (q);

    ASSERT_TRUE (v1.ptr == &v1.ptr && &v2.ptr == v2.ptr);
  }

  ASSERT_TRUE (val_t::ndefault + val_t::ncopy == val_t::ndtor);

  {
    Map m;
    void *p = &p, *q = &q;
    m.get_or_insert (p);
    m.remove (p);
    m.get_or_insert (q);
    m.remove (q);

    ASSERT_TRUE (val_t::ndefault + val_t::ncopy == val_t::ndtor);
  }
}

/* Test calling empty on a hash_map that has a key type with non-zero
   "empty" value.  */

static void
test_nonzero_empty_key ()
{
  typedef int_hash<int, INT_MIN, INT_MAX> IntHash;
  hash_map<int, int, simple_hashmap_traits<IntHash, int> > x;

  for (int i = 1; i != 32; ++i)
    x.put (i, i);

  ASSERT_EQ (x.get (0), NULL);
  ASSERT_EQ (*x.get (1), 1);

  x.empty ();

  ASSERT_EQ (x.get (0), NULL);
  ASSERT_EQ (x.get (1), NULL);
}

/* Run all of the selftests within this file.  */

void
hash_map_tests_c_tests ()
{
  test_map_of_strings_to_int ();
  test_map_of_int_to_strings ();
  test_map_of_type_with_ctor_and_dtor ();
  test_nonzero_empty_key ();
}

} // namespace selftest

#endif /* CHECKING_P */
Commit	Line	Data
d9b950dd	1	/* Unit tests for hash-map.h.
8d9254fc	2	Copyright (C) 2015-2020 Free Software Foundation, Inc.
d9b950dd DM	3
	4	This file is part of GCC.
	5
	6	GCC is free software; you can redistribute it and/or modify it under
	7	the terms of the GNU General Public License as published by the Free
	8	Software Foundation; either version 3, or (at your option) any later
	9	version.
	10
	11	GCC is distributed in the hope that it will be useful, but WITHOUT ANY
	12	WARRANTY; without even the implied warranty of MERCHANTABILITY or
	13	FITNESS FOR A PARTICULAR PURPOSE. See the GNU General Public License
	14	for more details.
	15
	16	You should have received a copy of the GNU General Public License
	17	along with GCC; see the file COPYING3. If not see
	18	<http://www.gnu.org/licenses/>. */
	19
	20	#include "config.h"
	21	#include "system.h"
	22	#include "coretypes.h"
	23	#include "tm.h"
	24	#include "opts.h"
d9b950dd DM	25	#include "hash-set.h"
	26	#include "fixed-value.h"
	27	#include "alias.h"
	28	#include "flags.h"
	29	#include "symtab.h"
	30	#include "tree-core.h"
	31	#include "stor-layout.h"
	32	#include "tree.h"
	33	#include "stringpool.h"
	34	#include "selftest.h"
	35
	36	#if CHECKING_P
	37
	38	namespace selftest {
	39
	40	/* Construct a hash_map <const char *, int> and verify that
	41	various operations work correctly. */
	42
	43	static void
	44	test_map_of_strings_to_int ()
	45	{
	46	hash_map <const char *, int> m;
	47
	48	const char *ostrich = "ostrich";
	49	const char *elephant = "elephant";
	50	const char *ant = "ant";
	51	const char *spider = "spider";
	52	const char *millipede = "Illacme plenipes";
	53	const char *eric = "half a bee";
	54
	55	/* A fresh hash_map should be empty. */
b119c055	56	ASSERT_TRUE (m.is_empty ());
d9b950dd DM	57	ASSERT_EQ (NULL, m.get (ostrich));
	58
	59	/* Populate the hash_map. */
	60	ASSERT_EQ (false, m.put (ostrich, 2));
	61	ASSERT_EQ (false, m.put (elephant, 4));
	62	ASSERT_EQ (false, m.put (ant, 6));
	63	ASSERT_EQ (false, m.put (spider, 8));
	64	ASSERT_EQ (false, m.put (millipede, 750));
	65	ASSERT_EQ (false, m.put (eric, 3));
	66
	67	/* Verify that we can recover the stored values. */
	68	ASSERT_EQ (6, m.elements ());
	69	ASSERT_EQ (2, *m.get (ostrich));
	70	ASSERT_EQ (4, *m.get (elephant));
	71	ASSERT_EQ (6, *m.get (ant));
	72	ASSERT_EQ (8, *m.get (spider));
	73	ASSERT_EQ (750, *m.get (millipede));
	74	ASSERT_EQ (3, *m.get (eric));
	75
	76	/* Verify removing an item. */
	77	m.remove (eric);
	78	ASSERT_EQ (5, m.elements ());
	79	ASSERT_EQ (NULL, m.get (eric));
3b1f091c	80
62de703f JM	81	m.remove (eric);
	82	ASSERT_EQ (5, m.elements ());
	83	ASSERT_EQ (NULL, m.get (eric));
	84
3b1f091c MP	85	/* A plain char * key is hashed based on its value (address), rather
	86	than the string it points to. */
	87	char another_ant = static_cast <char > (xcalloc (4, 1));
	88	another_ant[0] = 'a';
	89	another_ant[1] = 'n';
	90	another_ant[2] = 't';
	91	another_ant[3] = 0;
	92	ASSERT_NE (ant, another_ant);
	93	unsigned prev_size = m.elements ();
	94	ASSERT_EQ (false, m.put (another_ant, 7));
	95	ASSERT_EQ (prev_size + 1, m.elements ());
	96
	97	/* Need to use string_hash or nofree_string_hash key types to hash
	98	based on the string contents. */
	99	hash_map <nofree_string_hash, int> string_map;
	100	ASSERT_EQ (false, string_map.put (ant, 1));
	101	ASSERT_EQ (1, string_map.elements ());
	102	ASSERT_EQ (true, string_map.put (another_ant, 5));
	103	ASSERT_EQ (1, string_map.elements ());
51f90235 DM	104
51f90235 DM	105	free (another_ant);
d9b950dd DM	106	}
d9b950dd DM	107
aa0e90e7 DM	108	/* Construct a hash_map using int_hash and verify that
	109	various operations work correctly. */
	110
	111	static void
	112	test_map_of_int_to_strings ()
	113	{
	114	const int EMPTY = -1;
	115	const int DELETED = -2;
	116	typedef int_hash <int, EMPTY, DELETED> int_hash_t;
	117	hash_map <int_hash_t, const char *> m;
	118
	119	const char *ostrich = "ostrich";
	120	const char *elephant = "elephant";
	121	const char *ant = "ant";
	122	const char *spider = "spider";
	123	const char *millipede = "Illacme plenipes";
	124	const char *eric = "half a bee";
	125
	126	/* A fresh hash_map should be empty. */
	127	ASSERT_EQ (0, m.elements ());
	128	ASSERT_EQ (NULL, m.get (2));
	129
	130	/* Populate the hash_map. */
	131	ASSERT_EQ (false, m.put (2, ostrich));
	132	ASSERT_EQ (false, m.put (4, elephant));
	133	ASSERT_EQ (false, m.put (6, ant));
	134	ASSERT_EQ (false, m.put (8, spider));
	135	ASSERT_EQ (false, m.put (750, millipede));
	136	ASSERT_EQ (false, m.put (3, eric));
	137
	138	/* Verify that we can recover the stored values. */
	139	ASSERT_EQ (6, m.elements ());
	140	ASSERT_EQ (*m.get (2), ostrich);
	141	ASSERT_EQ (*m.get (4), elephant);
	142	ASSERT_EQ (*m.get (6), ant);
	143	ASSERT_EQ (*m.get (8), spider);
	144	ASSERT_EQ (*m.get (750), millipede);
	145	ASSERT_EQ (*m.get (3), eric);
	146	}
	147
6c1dae73	148	typedef class hash_map_test_val_t
7b8795a1	149	{
6c1dae73	150	public:
7b8795a1 MS	151	static int ndefault;
	152	static int ncopy;
	153	static int nassign;
	154	static int ndtor;
	155
	156	hash_map_test_val_t ()
	157	: ptr (&ptr)
	158	{
	159	++ndefault;
	160	}
	161
49070d06	162	hash_map_test_val_t (const hash_map_test_val_t &rhs)
7b8795a1 MS	163	: ptr (&ptr)
	164	{
	165	++ncopy;
49070d06	166	gcc_assert (rhs.ptr == &rhs.ptr);
7b8795a1 MS	167	}
7b8795a1 MS	168
49070d06 MS	169	hash_map_test_val_t& operator= (const hash_map_test_val_t &rhs)
	170	{
	171	++nassign;
	172	gcc_assert (ptr == &ptr);
	173	gcc_assert (rhs.ptr == &rhs.ptr);
	174	return *this;
	175	}
7b8795a1 MS	176
7b8795a1 MS	177	~hash_map_test_val_t ()
49070d06 MS	178	{
	179	gcc_assert (ptr == &ptr);
	180	++ndtor;
	181	}
7b8795a1 MS	182
	183	void *ptr;
	184	} val_t;
	185
	186	int val_t::ndefault;
	187	int val_t::ncopy;
	188	int val_t::nassign;
	189	int val_t::ndtor;
	190
	191	static void
	192	test_map_of_type_with_ctor_and_dtor ()
	193	{
	194	typedef hash_map <void *, val_t> Map;
	195
	196	{
	197	/* Test default ctor. */
	198	Map m;
	199	(void)&m;
	200	}
	201
	202	ASSERT_TRUE (val_t::ndefault == 0);
	203	ASSERT_TRUE (val_t::ncopy == 0);
	204	ASSERT_TRUE (val_t::nassign == 0);
	205	ASSERT_TRUE (val_t::ndtor == 0);
	206
	207	{
	208	/* Test single insertion. */
	209	Map m;
	210	void *p = &p;
	211	m.get_or_insert (p);
	212	}
	213
	214	ASSERT_TRUE (val_t::ndefault + val_t::ncopy == val_t::ndtor);
	215
	216	{
	217	/* Test copy ctor. */
	218	Map m1;
	219	void *p = &p;
	220	val_t &rv1 = m1.get_or_insert (p);
	221
	222	int ncopy = val_t::ncopy;
	223	int nassign = val_t::nassign;
	224
	225	Map m2 (m1);
	226	val_t *pv2 = m2.get (p);
	227
	228	ASSERT_TRUE (ncopy + 1 == val_t::ncopy);
	229	ASSERT_TRUE (nassign == val_t::nassign);
	230
	231	ASSERT_TRUE (&rv1 != pv2);
7b8795a1 MS	232	}
	233
	234	ASSERT_TRUE (val_t::ndefault + val_t::ncopy == val_t::ndtor);
	235
	236	#if 0 /* Avoid testing until bug 90959 is fixed. */
	237	{
	238	/* Test copy assignment into an empty map. */
	239	Map m1;
	240	void *p = &p;
	241	val_t &rv1 = m1.get_or_insert (p);
	242
	243	int ncopy = val_t::ncopy;
	244	int nassign = val_t::nassign;
	245
	246	Map m2;
	247	m2 = m1;
	248	val_t *pv2 = m2.get (p);
	249
	250	ASSERT_TRUE (ncopy == val_t::ncopy);
	251	ASSERT_TRUE (nassign + 1 == val_t::nassign);
	252
	253	ASSERT_TRUE (&rv1 != pv2);
7b8795a1 MS	254	}
	255
	256	ASSERT_TRUE (val_t::ndefault + val_t::ncopy == val_t::ndtor);
	257
	258	#endif
	259
	260	{
	261	Map m;
	262	void p = &p, q = &q;
	263	val_t &v1 = m.get_or_insert (p);
	264	val_t &v2 = m.get_or_insert (q);
	265
	266	ASSERT_TRUE (v1.ptr == &v1.ptr && &v2.ptr == v2.ptr);
	267	}
	268
	269	ASSERT_TRUE (val_t::ndefault + val_t::ncopy == val_t::ndtor);
	270
	271	{
	272	Map m;
	273	void p = &p, q = &q;
	274	m.get_or_insert (p);
	275	m.remove (p);
	276	m.get_or_insert (q);
	277	m.remove (q);
	278
	279	ASSERT_TRUE (val_t::ndefault + val_t::ncopy == val_t::ndtor);
	280	}
	281	}
	282
7ca50de0 DM	283	/* Test calling empty on a hash_map that has a key type with non-zero
	284	"empty" value. */
	285
	286	static void
	287	test_nonzero_empty_key ()
	288	{
	289	typedef int_hash<int, INT_MIN, INT_MAX> IntHash;
	290	hash_map<int, int, simple_hashmap_traits<IntHash, int> > x;
	291
	292	for (int i = 1; i != 32; ++i)
	293	x.put (i, i);
	294
	295	ASSERT_EQ (x.get (0), NULL);
	296	ASSERT_EQ (*x.get (1), 1);
	297
	298	x.empty ();
	299
	300	ASSERT_EQ (x.get (0), NULL);
	301	ASSERT_EQ (x.get (1), NULL);
	302	}
	303
d9b950dd DM	304	/* Run all of the selftests within this file. */
	305
	306	void
	307	hash_map_tests_c_tests ()
	308	{
	309	test_map_of_strings_to_int ();
aa0e90e7	310	test_map_of_int_to_strings ();
7b8795a1	311	test_map_of_type_with_ctor_and_dtor ();
7ca50de0	312	test_nonzero_empty_key ();
d9b950dd DM	313	}
	314
	315	} // namespace selftest
	316
	317	#endif /* CHECKING_P */