]>
Commit | Line | Data |
---|---|---|
4569a895 AT |
1 | // -*- C++ -*- |
2 | ||
7adcbafe | 3 | // Copyright (C) 2005-2022 Free Software Foundation, Inc. |
4569a895 AT |
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 | |
748086b7 | 8 | // Foundation; either version 3, or (at your option) any later |
4569a895 AT |
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 | |
748086b7 JJ |
17 | // along with this library; see the file COPYING3. If not see |
18 | // <http://www.gnu.org/licenses/>. | |
4569a895 | 19 | |
4569a895 AT |
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; | |
5e11f978 | 54 | using namespace __gnu_pbds; |
4569a895 AT |
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 | |
4569a895 AT |
63 | { |
64 | public: | |
65 | typedef size_t size_type; | |
66 | ||
67 | simple_string_ranged_hash_fn() : m_container_size(0) { } | |
68 | ||
69 | // Called to notify that the size has changed. | |
70 | void | |
71 | notify_resized(size_t size) | |
72 | { m_container_size = size; } | |
73 | ||
74 | // Called for hashing a string into a size_t in a given range. | |
75 | size_t | |
76 | operator()(const string& r_string) | |
77 | { | |
78 | /* | |
79 | * This (simplified) hash algorithm decides that if there are | |
80 | * fewer than 100 strings in the container it will hash | |
81 | * a string by summing its characters; otherwise, it will | |
82 | * perform a more complicated operation in order to produce | |
83 | * hash values with fewer collisions. | |
84 | */ | |
85 | string::const_iterator it = r_string.begin(); | |
86 | size_t hash = 0; | |
87 | if (m_container_size < 100) | |
88 | { | |
89 | // For this size, perform an accumulate type of operation. | |
90 | while (it != r_string.end()) | |
91 | hash += static_cast<size_t>(*it++); | |
92 | } | |
93 | else | |
94 | { | |
95 | // For this size, perform a different operation. | |
96 | while (it != r_string.end()) | |
97 | { | |
98 | hash += static_cast<size_t>(*it++); | |
99 | hash *= 5; | |
100 | } | |
101 | } | |
102 | ||
103 | // The function must, by whatever means, return a size in the | |
104 | // range 0 to m_container_size. | |
105 | return hash % m_container_size; | |
106 | } | |
107 | ||
108 | // Swaps content. | |
109 | void | |
110 | swap(simple_string_ranged_hash_fn& other) | |
111 | { | |
112 | std::swap(m_container_size, other.m_container_size); | |
113 | } | |
114 | ||
115 | private: | |
116 | // Records the size of the container object. | |
117 | size_t m_container_size; | |
118 | }; | |
119 | ||
120 | int | |
121 | main() | |
122 | { | |
123 | // A collision-chaining hash table storing strings. | |
124 | typedef | |
125 | cc_hash_table< | |
126 | string, | |
a345e45d BK |
127 | null_type, |
128 | null_type, | |
4569a895 AT |
129 | equal_to<string>, |
130 | simple_string_ranged_hash_fn> | |
131 | set_t; | |
132 | ||
133 | // Note that in the above, the library determines a resize policy | |
134 | // appropriate for modulo-based range hashing. | |
135 | set_t h; | |
136 | ||
137 | // Use the table normally. | |
138 | h.insert("Hello, "); | |
139 | h.insert("world"); | |
140 | ||
141 | assert(h.size() == 2); | |
142 | ||
143 | assert(h.find("Hello, ") != h.end()); | |
144 | assert(h.find("world") != h.end()); | |
145 | ||
146 | assert(h.find("Goodbye, oh cruel world!") == h.end()); | |
147 | ||
148 | return 0; | |
149 | } | |
150 |