OpenCores
URL https://opencores.org/ocsvn/scarts/scarts/trunk

Subversion Repositories scarts

[/] [scarts/] [trunk/] [toolchain/] [scarts-gcc/] [gcc-4.1.1/] [libstdc++-v3/] [testsuite/] [ext/] [pb_assoc/] [example/] [ranged_hash.cc] - Blame information for rev 19

Details | Compare with Previous | View Log

Line No. Rev Author Line
1 19 jlechner
// -*- 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
 */
62
class simple_string_ranged_hash_fn : public std::unary_function<
63
  std::string,
64
                                     size_t>
65
{
66
public:
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
 
87
private:
88
  // Records the size of the container object.
89
  size_t m_container_size;
90
};
91
 
92
simple_string_ranged_hash_fn::
93
simple_string_ranged_hash_fn() :
94
  m_container_size(0)
95
{
96
 
97
}
98
 
99
void
100
simple_string_ranged_hash_fn::
101
notify_resized(size_t size)
102
{
103
  m_container_size = size;
104
}
105
 
106
size_t
107
simple_string_ranged_hash_fn::
108
operator()(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
 
148
void
149
simple_string_ranged_hash_fn::
150
swap(simple_string_ranged_hash_fn& r_other)
151
{
152
  std::swap(m_container_size, r_other.m_container_size);
153
}
154
 
155
int
156
main()
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
 

powered by: WebSVN 2.1.0

© copyright 1999-2024 OpenCores.org, equivalent to Oliscience, all rights reserved. OpenCores®, registered trademark.