contrib/gcc-4.1/libstdc++-v3/include/ext/pb_assoc/detail/resize_policy/cc_hash_max_collision_resize_trigger_imp.hpp

   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 cc_hash_max_collision_check_resize_trigger_imp.hpp
  42  * Contains an implementation of cc_hash_max_collision_check_resize_trigger.
  43  */
  44
  45 PB_ASSOC_CLASS_T_DEC
  46 pb_assoc::detail::int_to_type<External_Load_Access>
  47 PB_ASSOC_CLASS_C_DEC::s_external_load_access_ind;
  48
  49 PB_ASSOC_CLASS_T_DEC
  50 PB_ASSOC_CLASS_C_DEC::
  51 cc_hash_max_collision_check_resize_trigger(float load) :
  52   m_load(load),
  53   m_size(0),
  54   m_num_col(0),
  55   m_max_col(0),
  56   m_resize_needed(false)
  57 { }
  58
  59 PB_ASSOC_CLASS_T_DEC
  60 inline void
  61 PB_ASSOC_CLASS_C_DEC::
  62 notify_find_search_start()
  63 { }
  64
  65 PB_ASSOC_CLASS_T_DEC
  66 inline void
  67 PB_ASSOC_CLASS_C_DEC::
  68 notify_find_search_collision()
  69 { }
  70
  71 PB_ASSOC_CLASS_T_DEC
  72 inline void
  73 PB_ASSOC_CLASS_C_DEC::
  74 notify_find_search_end()
  75 { }
  76
  77 PB_ASSOC_CLASS_T_DEC
  78 inline void
  79 PB_ASSOC_CLASS_C_DEC::
  80 notify_insert_search_start()
  81 {
  82   m_num_col = 0;
  83 }
  84
  85 PB_ASSOC_CLASS_T_DEC
  86 inline void
  87 PB_ASSOC_CLASS_C_DEC::
  88 notify_insert_search_collision()
  89 {
  90   ++m_num_col;
  91 }
  92
  93 PB_ASSOC_CLASS_T_DEC
  94 inline void
  95 PB_ASSOC_CLASS_C_DEC::
  96 notify_insert_search_end()
  97 {
  98   PB_ASSOC_DBG_ASSERT(NOTHING_HT_RESIZE_ACTION == 0);
  99
 100   m_resize_needed =
 101     m_resize_needed || (m_num_col >= m_max_col);
 102 }
 103
 104 PB_ASSOC_CLASS_T_DEC
 105 inline void
 106 PB_ASSOC_CLASS_C_DEC::
 107 notify_erase_search_start()
 108 { }
 109
 110 PB_ASSOC_CLASS_T_DEC
 111 inline void
 112 PB_ASSOC_CLASS_C_DEC::
 113 notify_erase_search_collision()
 114 { }
 115
 116 PB_ASSOC_CLASS_T_DEC
 117 inline void
 118 PB_ASSOC_CLASS_C_DEC::
 119 notify_erase_search_end()
 120 { }
 121
 122 PB_ASSOC_CLASS_T_DEC
 123 inline void
 124 PB_ASSOC_CLASS_C_DEC::
 125 notify_inserted(size_type num_e)
 126 {
 127   PB_ASSOC_DBG_ASSERT(num_e <= m_size);
 128
 129   if (num_e == m_size)
 130     m_resize_needed = true;
 131 }
 132
 133 PB_ASSOC_CLASS_T_DEC
 134 inline void
 135 PB_ASSOC_CLASS_C_DEC::
 136 notify_erased(size_type num_e)
 137 {
 138   PB_ASSOC_DBG_ASSERT(num_e <= m_size);
 139
 140   m_resize_needed = false;
 141 }
 142
 143 PB_ASSOC_CLASS_T_DEC
 144 void
 145 PB_ASSOC_CLASS_C_DEC::
 146 notify_cleared()
 147 {
 148   m_resize_needed = false;
 149 }
 150
 151 PB_ASSOC_CLASS_T_DEC
 152 inline bool
 153 PB_ASSOC_CLASS_C_DEC::
 154 is_resize_needed() const
 155 {
 156   return (m_resize_needed);
 157 }
 158
 159 PB_ASSOC_CLASS_T_DEC
 160 inline bool
 161 PB_ASSOC_CLASS_C_DEC::
 162 is_grow_needed(size_type /*size*/, size_type /*num_used_e*/) const
 163 {
 164   PB_ASSOC_DBG_ASSERT(m_resize_needed);
 165
 166   return (true);
 167 }
 168
 169 PB_ASSOC_CLASS_T_DEC
 170 inline bool
 171 PB_ASSOC_CLASS_C_DEC::
 172 is_shrink_needed(size_type size, size_type num_used_e) const
 173 {
 174   PB_ASSOC_DBG_ASSERT(m_resize_needed);
 175
 176   return (false);
 177 }
 178
 179 PB_ASSOC_CLASS_T_DEC
 180 void
 181 PB_ASSOC_CLASS_C_DEC::
 182 notify_resized(size_type new_size)
 183 {
 184   m_size = new_size;
 185
 186   // max_col <-- \sqrt{2 load \ln( 2 m \ln( m ) ) }
 187
 188   const double ln_arg = 2*  m_size*  ::log( (double)m_size);
 189
 190   m_max_col = (size_type)::ceil(  ::sqrt(2*   m_load*  ::log(ln_arg) ) );
 191
 192   m_num_col = 0;
 193
 194   m_resize_needed = false;
 195 }
 196
 197 PB_ASSOC_CLASS_T_DEC
 198 void
 199 PB_ASSOC_CLASS_C_DEC::
 200 notify_externally_resized(size_type new_size)
 201 {
 202   notify_resized(new_size);
 203 }
 204
 205 PB_ASSOC_CLASS_T_DEC
 206 void
 207 PB_ASSOC_CLASS_C_DEC::
 208 swap(PB_ASSOC_CLASS_C_DEC& r_other)
 209 {
 210   std::swap(m_load, r_other.m_load);
 211
 212   std::swap(m_size, r_other.m_size);
 213
 214   std::swap(m_num_col, r_other.m_num_col);
 215
 216   std::swap(m_max_col, r_other.m_max_col);
 217
 218   std::swap(m_resize_needed, r_other.m_resize_needed);
 219 }
 220
 221 PB_ASSOC_CLASS_T_DEC
 222 inline float
 223 PB_ASSOC_CLASS_C_DEC::
 224 get_load_imp(pb_assoc::detail::int_to_type<true>) const
 225 {
 226   return (m_load);
 227 }