1// -*- C++ -*-
2
3// Copyright (C) 2005 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
7// terms of the GNU General Public License as published by the
8// Free Software Foundation; either version 2, or (at your option)
9// any later version.
10
11// This library is distributed in the hope that it will be useful,
12// but WITHOUT ANY WARRANTY; without even the implied warranty of
13// MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
14// GNU General Public License for more details.
15
16// You should have received a copy of the GNU General Public License along
17// with this library; see the file COPYING.  If not, write to the Free
18// Software Foundation, 51 Franklin Street, Fifth Floor, Boston, MA 02110-1301,
19// USA.
20
21// As a special exception, you may use this file as part of a free software
22// library without restriction.  Specifically, if other files instantiate
23// templates or use macros or inline functions from this file, or you compile
24// this file and link it with other files to produce an executable, this
25// file does not by itself cause the resulting executable to be covered by
26// the GNU General Public License.  This exception does not however
27// invalidate any other reasons why the executable file might be covered by
28// the GNU General Public License.
29
30// Copyright (C) 2004 Ami Tavory and Vladimir Dreizin, IBM-HRL.
31
32// Permission to use, copy, modify, sell, and distribute this software
33// is hereby granted without fee, provided that the above copyright
34// notice appears in all copies, and that both that copyright notice and
35// this permission notice appear in supporting documentation. None of
36// the above authors, nor IBM Haifa Research Laboratories, make any
37// representation about the suitability of this software for any
38// purpose. It is provided "as is" without express or implied warranty.
39
40/**
41 * @file ranged_hash_example.cpp
42 * A basic example showing how to write a ranged-hash functor.
43 */
44
45// For cc_hash_assoc_cntnr.
46#include <ext/pb_assoc/assoc_cntnr.hpp>
47// For hash-related policies.
48#include <ext/pb_assoc/hash_policy.hpp>
49// For unary_function and binary_function.
50#include <functional>
51// For assert.
52#include <cassert>
53// For string.
54#include <string>
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 */
62class simple_string_ranged_hash_fn : public std::unary_function<
63  std::string,
64				     size_t>
65{
66public:
67  typedef size_t size_type;
68
69  // Default constructor.
70  simple_string_ranged_hash_fn();
71
72  // Called to notify that the size has changed.
73  void
74  notify_resized(size_t size);
75
76  /*
77   * Called for hashing a string into a size_t in a
78   *	given range.
79   */
80  size_t
81  operator()(const std::string& r_string);
82
83  // Swaps content.
84  void
85  swap(simple_string_ranged_hash_fn& r_other);
86
87private:
88  // Records the size of the container object.
89  size_t m_container_size;
90};
91
92simple_string_ranged_hash_fn::
93simple_string_ranged_hash_fn() :
94  m_container_size(0)
95{
96
97}
98
99void
100simple_string_ranged_hash_fn::
101notify_resized(size_t size)
102{
103  m_container_size = size;
104}
105
106size_t
107simple_string_ranged_hash_fn::
108operator()(const std::string& r_string)
109{
110  /*
111   * This (simplified) hash algorithm decides that if there are
112   *	fewer than 100 strings in the container it will hash
113   *	a string by summing its characters; otherwise, it will
114   *	perform a more complicated operation in order to produce
115   *	hash values with fewer collisions.
116   */
117
118  std::string::const_iterator it = r_string.begin();
119
120  size_t hash = 0;
121
122  if (m_container_size < 100)
123    {
124      // For this size, perform an std::accumulate type of operation.
125
126      while (it != r_string.end())
127	hash += static_cast<size_t>(*it++);
128    }
129  else
130    {
131      // For this size, perform a different operation.
132
133      while (it != r_string.end())
134	{
135	  hash += static_cast<size_t>(*it++);
136
137	  hash *= 5;
138	}
139    }
140
141  /*
142   * The function must, by whatever means, return
143   *	a size in the range 0 to m_container_size.
144   */
145  return (hash % m_container_size);
146}
147
148void
149simple_string_ranged_hash_fn::
150swap(simple_string_ranged_hash_fn& r_other)
151{
152  std::swap(m_container_size, r_other.m_container_size);
153}
154
155int
156main()
157{
158  /*
159   * A collision-chaining hash table storing strings.
160   */
161  typedef
162    pb_assoc::cc_hash_assoc_cntnr<
163    std::string,
164    pb_assoc::null_data_type,
165    // Null hash function
166    pb_assoc::null_hash_fn,
167    // Equivalence function.
168    std::equal_to<
169    std::string>,
170    // Range hashing function.
171    simple_string_ranged_hash_fn >
172    set_t;
173
174  /*
175   * Note that in the above, the library determines a resize policy
176   *	appropriate for direct_mod_range_hashing.
177   */
178
179  set_t h;
180
181  // Use the table normally.
182
183  h.insert("Hello, ");
184  h.insert("world");
185
186  assert(h.size() == 2);
187
188  assert(h.find("Hello, ") != h.end());
189  assert(h.find("world") != h.end());
190
191  assert(h.find("Goodbye, oh cruel world!") == h.end());
192}
193
194