1// { dg-timeout-factor 2.0 }
2
3// -*- C++ -*-
4
5// Copyright (C) 2005-2015 Free Software Foundation, Inc.
6//
7// This file is part of the GNU ISO C++ Library.  This library is free
8// software; you can redistribute it and/or modify it under the terms
9// of the GNU General Public License as published by the Free Software
10// Foundation; either version 3, or (at your option) any later
11// version.
12
13// This library is distributed in the hope that it will be useful, but
14// WITHOUT ANY WARRANTY; without even the implied warranty of
15// MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the GNU
16// General Public License for more details.
17
18// You should have received a copy of the GNU General Public License
19// along with this library; see the file COPYING3.  If not see
20// <http://www.gnu.org/licenses/>.
21
22
23// Copyright (C) 2004 Ami Tavory and Vladimir Dreizin, IBM-HRL.
24
25// Permission to use, copy, modify, sell, and distribute this software
26// is hereby granted without fee, provided that the above copyright
27// notice appears in all copies, and that both that copyright notice
28// and this permission notice appear in supporting documentation. None
29// of the above authors, nor IBM Haifa Research Laboratories, make any
30// representation about the suitability of this software for any
31// purpose. It is provided "as is" without express or implied
32// warranty.
33
34/**
35 * @file hash_illegal_resize_example.cpp
36 * An example of illegally externally resizing a hash-based container object.
37 */
38
39/**
40 * This example shows the case where a hash-based container object is
41 * resized to a value which it cannot accommodate at runtime. Illegal
42 * runtime resizes cause an exception.
43 */
44
45#include <ext/pb_ds/assoc_container.hpp>
46#include <ext/pb_ds/hash_policy.hpp>
47#include <ext/pb_ds/exception.hpp>
48#include <cassert>
49
50// size of test containers
51#ifdef _GLIBCXX_DEBUG
52# define SIZE 100
53# define RESIZE 20
54#else
55# define SIZE 1000
56# define RESIZE 200
57#endif
58
59using namespace std;
60using namespace __gnu_pbds;
61
62// A simple hash functor.
63// hash could serve instead of this functor, but it is not yet
64// standard everywhere.
65struct int_hash : public unary_function<int, size_t>
66{
67  inline size_t
68  operator()(const int& r_i) const
69  { return r_i; }
70};
71
72
73int main()
74{
75  // A probing hash table mapping ints to chars.
76  typedef
77    gp_hash_table<
78    int,
79    int,
80    int_hash,
81    equal_to<int>,
82    // Combining function.
83    direct_mod_range_hashing<>,
84    // Probe function.
85    quadratic_probe_fn<>,
86    // Resize policy.
87    hash_standard_resize_policy<
88    hash_prime_size_policy,
89    hash_load_check_resize_trigger<>,
90    /* Allow external access to size.
91     *     Without setting this to true, external resizing
92     *     is not possible.
93     */
94    true> >
95    map_t;
96
97  map_t g;
98
99  // Insert some elements.
100  int i;
101
102  for (i = 0; i < SIZE; ++i)
103    g[i] = 2*  i;
104
105  // Check all ok.
106  assert(g.size() == SIZE);
107  for (i = 0; i < SIZE; ++i)
108    assert(g.find(i) != g.end() && g.find(i)->second == 2 * i);
109
110  // Now attempt to resize the table to 200 (impossible).
111  bool ex_thrown = false;
112
113  try
114    {
115      g.resize(RESIZE);
116    }
117  catch(__gnu_pbds::resize_error& )
118    {
119      ex_thrown = true;
120    }
121
122  // Assert an exception was thrown. A probing table cannot contain
123  // 1000 entries in less than 1000 places.
124  assert(ex_thrown);
125
126  // Irrespective of the fact that the resize was not successful, the
127  // container object should still be in a valid state; the following
128  // checks this.
129  // Check all ok.
130  assert(g.size() == SIZE);
131  for (i = 0; i < SIZE; ++i)
132    assert(g.find(i) != g.end() && g.find(i)->second == 2 * i);
133
134  return 0;
135}
136