libstdc++-v3/testsuite/ext/pb_ds/example/hash_shift_mask.cc

   1 // -*- C++ -*-
   2
   3 // Copyright (C) 2005-2024 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 hash_shift_mask_example.cpp
  34  * An example showing how to write a range-hasing functor.
  35  */
  36
  37 /**
  38  * In some rare cases, advance knowledge of the distribution of keys allows
  39  * writing more efficient hash-related policies.
  40  * In the rather simplistic case of the example, it is known in advance that
  41  * all keys have 0 two lowest bits. The example shows how to write
  42  * a range-hashing function disregarding the two lowest bits of the hash value.
  43  */
  44
  45 #include <functional>
  46 #include <ext/pb_ds/assoc_container.hpp>
  47 #include <ext/pb_ds/hash_policy.hpp>
  48
  49 using namespace std;
  50 using namespace __gnu_pbds;
  51
  52 // A simple hash functor. hash could serve instead of this functor,
  53 // but it is not yet standard everywhere.
  54 struct simple_int_hash
  55 {
  56   size_t
  57   operator()(int i) const
  58   { return i; }
  59 };
  60
  61 // A range-hashing function which shifts 2 bits right and then masks.
  62 class shift_two_mask_range_hashing : private direct_mask_range_hashing<>
  63 {
  64 public:
  65   typedef size_t size_type;
  66
  67   // Swaps with a different instant.
  68   void
  69   swap(shift_two_mask_range_hashing& other)
  70   { direct_mask_range_hashing<>::swap(other); }
  71
  72   // Called by the container when internally resized.
  73   void
  74   notify_resized(size_type size)
  75   { direct_mask_range_hashing<>::notify_resized(size); }
  76
  77   // Given a hash value, returns a number in the range of the internal
  78   // size of the container.
  79   inline size_type
  80   operator()(size_type hash) const
  81   { return direct_mask_range_hashing<>::operator()(hash >> 2); }
  82 };
  83
  84 int
  85 main()
  86 {
  87   // A collision-chaining hash table mapping ints to chars.
  88   typedef
  89     cc_hash_table<
  90     int,
  91     char,
  92     // Hash function.
  93     simple_int_hash,
  94     equal_to<int>,
  95     // Range hashing function.
  96     shift_two_mask_range_hashing>
  97     map_t;
  98
  99   map_t h;
 100
 101   // Use normally.
 102   h[16] = 'a';
 103   h[256] = 'e';
 104   h[4] = 'z';
 105
 106   return 0;
 107 }
 108