1 // -*- C++ -*-
2
3 // Copyright (C) 2005-2016 Free Software Foundation, Inc.
4 //
5 // This file is part of the GNU ISO C++ Library. This library is free
6 // software; you can redistribute it and/or modify it under the terms
7 // of the GNU General Public License as published by the Free Software
8 // Foundation; either version 3, or (at your option) any later
9 // version.
10
11 // This library is distributed in the hope that it will be useful, but
12 // WITHOUT ANY WARRANTY; without even the implied warranty of
13 // MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the GNU
14 // General Public License for more details.
15
16 // You should have received a copy of the GNU General Public License
17 // along with this library; see the file COPYING3. If not see
18 // <http://www.gnu.org/licenses/>.
19
20
21 // Copyright (C) 2004 Ami Tavory and Vladimir Dreizin, IBM-HRL.
22
23 // Permission to use, copy, modify, sell, and distribute this software
24 // is hereby granted without fee, provided that the above copyright
25 // notice appears in all copies, and that both that copyright notice
26 // and this permission notice appear in supporting documentation. None
27 // of the above authors, nor IBM Haifa Research Laboratories, make any
28 // representation about the suitability of this software for any
29 // purpose. It is provided "as is" without express or implied
30 // warranty.
31
32 /**
33 * @file ranged_hash_example.cpp
34 * A basic example showing how to write a ranged-hash functor.
35 */
36
37 /**
38 * In some cases it is beneficial to write a hash function which determines
39 * hash values based on the size of the container object.
40 * The example shows an example of a string-hashing function which
41 * uses a fast method for hashing strings when the number of strings
42 * in the container object is small, and a slower but more careful method
43 * for hashing strings when the number of strings in the container object
44 * is large.
45 */
46
47 #include <functional>
48 #include <cassert>
49 #include <string>
50 #include <ext/pb_ds/assoc_container.hpp>
51 #include <ext/pb_ds/hash_policy.hpp>
52
53 using namespace std;
54 using namespace __gnu_pbds;
55
56 /**
57 * A (somewhat simplistic) ranged-hash function for strings.
58 * It uses the size of the container object to determine
59 * the hashing method. For smaller sizes it uses a simple hash function;
60 * for larger sizes it uses a more complicated hash function.
61 */
62 class simple_string_ranged_hash_fn
63 : public unary_function<string, size_t>
64 {
65 public:
66 typedef size_t size_type;
67
simple_string_ranged_hash_fn()68 simple_string_ranged_hash_fn() : m_container_size(0) { }
69
70 // Called to notify that the size has changed.
71 void
notify_resized(size_t size)72 notify_resized(size_t size)
73 { m_container_size = size; }
74
75 // Called for hashing a string into a size_t in a given range.
76 size_t
operator ()(const string & r_string)77 operator()(const string& r_string)
78 {
79 /*
80 * This (simplified) hash algorithm decides that if there are
81 * fewer than 100 strings in the container it will hash
82 * a string by summing its characters; otherwise, it will
83 * perform a more complicated operation in order to produce
84 * hash values with fewer collisions.
85 */
86 string::const_iterator it = r_string.begin();
87 size_t hash = 0;
88 if (m_container_size < 100)
89 {
90 // For this size, perform an accumulate type of operation.
91 while (it != r_string.end())
92 hash += static_cast<size_t>(*it++);
93 }
94 else
95 {
96 // For this size, perform a different operation.
97 while (it != r_string.end())
98 {
99 hash += static_cast<size_t>(*it++);
100 hash *= 5;
101 }
102 }
103
104 // The function must, by whatever means, return a size in the
105 // range 0 to m_container_size.
106 return hash % m_container_size;
107 }
108
109 // Swaps content.
110 void
swap(simple_string_ranged_hash_fn & other)111 swap(simple_string_ranged_hash_fn& other)
112 {
113 std::swap(m_container_size, other.m_container_size);
114 }
115
116 private:
117 // Records the size of the container object.
118 size_t m_container_size;
119 };
120
121 int
main()122 main()
123 {
124 // A collision-chaining hash table storing strings.
125 typedef
126 cc_hash_table<
127 string,
128 null_type,
129 null_type,
130 equal_to<string>,
131 simple_string_ranged_hash_fn>
132 set_t;
133
134 // Note that in the above, the library determines a resize policy
135 // appropriate for modulo-based range hashing.
136 set_t h;
137
138 // Use the table normally.
139 h.insert("Hello, ");
140 h.insert("world");
141
142 assert(h.size() == 2);
143
144 assert(h.find("Hello, ") != h.end());
145 assert(h.find("world") != h.end());
146
147 assert(h.find("Goodbye, oh cruel world!") == h.end());
148
149 return 0;
150 }
151
152