l4/pkg/libstdc++-v3/contrib/libstdc++-v3-4.1.0/include/ext/pb_assoc/detail/resize_policy/hash_load_check_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 hash_load_check_resize_trigger_imp.hpp.hpp
  42  * Contains an implementation of hash_load_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 hash_load_check_resize_trigger(float load_min, float load_max) :
  52   m_load_min(load_min),
  53   m_load_max(load_max),
  54   m_next_shrink_size(0),
  55   m_next_grow_size(0),
  56   m_resize_needed(false)
  57 {
  58   PB_ASSOC_DBG_ONLY(assert_valid();)
  59     }
  60
  61 PB_ASSOC_CLASS_T_DEC
  62 inline void
  63 PB_ASSOC_CLASS_C_DEC::
  64 notify_find_search_start()
  65 {
  66   PB_ASSOC_DBG_ONLY(assert_valid();)
  67     }
  68
  69 PB_ASSOC_CLASS_T_DEC
  70 inline void
  71 PB_ASSOC_CLASS_C_DEC::
  72 notify_find_search_collision()
  73 {
  74   PB_ASSOC_DBG_ONLY(assert_valid();)
  75     }
  76
  77 PB_ASSOC_CLASS_T_DEC
  78 inline void
  79 PB_ASSOC_CLASS_C_DEC::
  80 notify_find_search_end()
  81 {
  82   PB_ASSOC_DBG_ONLY(assert_valid();)
  83     }
  84
  85 PB_ASSOC_CLASS_T_DEC
  86 inline void
  87 PB_ASSOC_CLASS_C_DEC::
  88 notify_insert_search_start()
  89 {
  90   PB_ASSOC_DBG_ONLY(assert_valid();)
  91     }
  92
  93 PB_ASSOC_CLASS_T_DEC
  94 inline void
  95 PB_ASSOC_CLASS_C_DEC::
  96 notify_insert_search_collision()
  97 {
  98   PB_ASSOC_DBG_ONLY(assert_valid();)
  99     }
 100
 101 PB_ASSOC_CLASS_T_DEC
 102 inline void
 103 PB_ASSOC_CLASS_C_DEC::
 104 notify_insert_search_end()
 105 {
 106   PB_ASSOC_DBG_ONLY(assert_valid();)
 107     }
 108
 109 PB_ASSOC_CLASS_T_DEC
 110 inline void
 111 PB_ASSOC_CLASS_C_DEC::
 112 notify_erase_search_start()
 113 {
 114   PB_ASSOC_DBG_ONLY(assert_valid();)
 115     }
 116
 117 PB_ASSOC_CLASS_T_DEC
 118 inline void
 119 PB_ASSOC_CLASS_C_DEC::
 120 notify_erase_search_collision()
 121 {
 122   PB_ASSOC_DBG_ONLY(assert_valid();)
 123     }
 124
 125 PB_ASSOC_CLASS_T_DEC
 126 inline void
 127 PB_ASSOC_CLASS_C_DEC::
 128 notify_erase_search_end()
 129 {
 130   PB_ASSOC_DBG_ONLY(assert_valid();)
 131     }
 132
 133 PB_ASSOC_CLASS_T_DEC
 134 inline void
 135 PB_ASSOC_CLASS_C_DEC::
 136 notify_inserted(size_type num_entries)
 137 {
 138   PB_ASSOC_DBG_ASSERT(num_entries <= m_next_grow_size);
 139
 140   my_size_base::set_size(num_entries);
 141
 142   m_resize_needed = (num_entries == m_next_grow_size);
 143
 144   PB_ASSOC_DBG_ONLY(assert_valid();)
 145     }
 146
 147 PB_ASSOC_CLASS_T_DEC
 148 inline void
 149 PB_ASSOC_CLASS_C_DEC::
 150 notify_erased(size_type num_entries)
 151 {
 152   PB_ASSOC_DBG_ASSERT(num_entries >= m_next_shrink_size);
 153
 154   my_size_base::set_size(num_entries);
 155
 156   m_resize_needed = (num_entries == m_next_shrink_size);
 157
 158   PB_ASSOC_DBG_ONLY(assert_valid();)
 159
 160     PB_ASSOC_DBG_ONLY(assert_valid();)
 161     }
 162
 163 PB_ASSOC_CLASS_T_DEC
 164 inline bool
 165 PB_ASSOC_CLASS_C_DEC::
 166 is_resize_needed() const
 167 {
 168   PB_ASSOC_DBG_ONLY(assert_valid();)
 169
 170     return (m_resize_needed);
 171 }
 172
 173 PB_ASSOC_CLASS_T_DEC
 174 inline bool
 175 PB_ASSOC_CLASS_C_DEC::
 176 is_grow_needed(size_type /*size*/, size_type num_entries) const
 177 {
 178   PB_ASSOC_DBG_ASSERT(m_resize_needed);
 179
 180   return (num_entries >= m_next_grow_size);
 181 }
 182
 183 PB_ASSOC_CLASS_T_DEC
 184 inline bool
 185 PB_ASSOC_CLASS_C_DEC::
 186 is_shrink_needed(size_type /*size*/, size_type num_entries) const
 187 {
 188   PB_ASSOC_DBG_ASSERT(m_resize_needed);
 189
 190   return (num_entries <= m_next_shrink_size);
 191 }
 192
 193 PB_ASSOC_CLASS_T_DEC
 194 PB_ASSOC_CLASS_C_DEC::
 195 ~hash_load_check_resize_trigger()
 196 { }
 197
 198 PB_ASSOC_CLASS_T_DEC
 199 void
 200 PB_ASSOC_CLASS_C_DEC::
 201 notify_resized(size_type new_size)
 202 {
 203   m_resize_needed = false;
 204
 205   m_next_grow_size =
 206     size_type(m_load_max*  new_size - 1);
 207
 208   m_next_shrink_size =
 209     size_type(m_load_min*  new_size );
 210
 211   PB_ASSOC_DBG_ONLY(assert_valid();)
 212     }
 213
 214 PB_ASSOC_CLASS_T_DEC
 215 void
 216 PB_ASSOC_CLASS_C_DEC::
 217 notify_externally_resized(size_type new_size)
 218 {
 219   m_resize_needed = false;
 220
 221   size_type new_grow_size =
 222     size_type(m_load_max*  new_size - 1);
 223
 224   size_type new_shrink_size =
 225     size_type(m_load_min*  new_size );
 226
 227   if (new_grow_size >= m_next_grow_size)
 228     {
 229       PB_ASSOC_DBG_ASSERT(new_shrink_size > m_next_shrink_size);
 230
 231       m_next_grow_size = new_grow_size;
 232
 233       PB_ASSOC_DBG_ONLY(assert_valid();)
 234
 235         return;
 236     }
 237
 238   PB_ASSOC_DBG_ASSERT(new_shrink_size <= m_next_shrink_size);
 239
 240   m_next_shrink_size = new_shrink_size;
 241
 242   PB_ASSOC_DBG_ONLY(assert_valid();)
 243     }
 244
 245 PB_ASSOC_CLASS_T_DEC
 246 void
 247 PB_ASSOC_CLASS_C_DEC::
 248 notify_cleared()
 249 {
 250   my_size_base::set_size(0);
 251
 252   m_resize_needed = (0 < m_next_shrink_size);
 253
 254   PB_ASSOC_DBG_ONLY(assert_valid();)
 255     }
 256
 257 PB_ASSOC_CLASS_T_DEC
 258 void
 259 PB_ASSOC_CLASS_C_DEC::
 260 swap(PB_ASSOC_CLASS_C_DEC& r_other)
 261 {
 262   PB_ASSOC_DBG_ONLY(assert_valid();)
 263     PB_ASSOC_DBG_ONLY(r_other.assert_valid();)
 264
 265     my_size_base::swap(r_other);
 266
 267   std::swap(m_load_min, r_other.m_load_min);
 268   std::swap(m_load_max, r_other.m_load_max);
 269
 270   std::swap(m_resize_needed, r_other.m_resize_needed);
 271
 272   std::swap(m_next_grow_size, r_other.m_next_grow_size);
 273   std::swap(m_next_shrink_size, r_other.m_next_shrink_size);
 274
 275   PB_ASSOC_DBG_ONLY(assert_valid();)
 276     PB_ASSOC_DBG_ONLY(r_other.assert_valid();)
 277     }
 278
 279 PB_ASSOC_CLASS_T_DEC
 280 inline std::pair<float, float>
 281 PB_ASSOC_CLASS_C_DEC::
 282 get_loads() const
 283 {
 284   return (get_loads_imp(s_external_load_access_ind));
 285 }
 286
 287 PB_ASSOC_CLASS_T_DEC
 288 void
 289 PB_ASSOC_CLASS_C_DEC::
 290 set_loads(std::pair<float, float> load_pair)
 291 {
 292   set_loads_imp(load_pair, s_external_load_access_ind);
 293 }
 294
 295 PB_ASSOC_CLASS_T_DEC
 296 inline std::pair<float, float>
 297 PB_ASSOC_CLASS_C_DEC::
 298 get_loads_imp(pb_assoc::detail::int_to_type<true>) const
 299 {
 300   return (std::make_pair(m_load_min, m_load_max));
 301 }
 302
 303 PB_ASSOC_CLASS_T_DEC
 304 void
 305 PB_ASSOC_CLASS_C_DEC::
 306 set_loads_imp(std::pair<float, float> load_pair, pb_assoc::detail::int_to_type<true>)
 307 {
 308   const float old_load_min = m_load_min;
 309   const float old_load_max = m_load_max;
 310   const size_type old_next_shrink_size = m_next_shrink_size;
 311   const size_type old_next_grow_size = m_next_grow_size;
 312   const bool old_resize_needed = m_resize_needed;
 313
 314   try
 315     {
 316       m_load_min = load_pair.first;
 317       m_load_max = load_pair.second;
 318
 319       do_resize(static_cast<size_type>(
 320                                        my_size_base::get_size() / ((m_load_min + m_load_max) / 2)));
 321     }
 322   catch(...)
 323     {
 324       m_load_min = old_load_min;
 325       m_load_max = old_load_max;
 326       m_next_shrink_size = old_next_shrink_size;
 327       m_next_grow_size = old_next_grow_size;
 328       m_resize_needed = old_resize_needed;
 329
 330       throw;
 331     }
 332 }
 333
 334 PB_ASSOC_CLASS_T_DEC
 335 void
 336 PB_ASSOC_CLASS_C_DEC::
 337 do_resize(size_type /*new_size*/)
 338 {
 339   abort();
 340 }
 341
 342 #ifdef PB_ASSOC_HT_LOAD_CHECK_RESIZE_TRIGGER_DEBUG
 343 PB_ASSOC_CLASS_T_DEC
 344 void
 345 PB_ASSOC_CLASS_C_DEC::
 346 assert_valid() const
 347 {
 348   PB_ASSOC_DBG_ASSERT(m_load_max > m_load_min);
 349
 350   PB_ASSOC_DBG_ASSERT(m_next_grow_size >= m_next_shrink_size);
 351 }
 352 #endif // #ifdef PB_ASSOC_HT_LOAD_CHECK_RESIZE_TRIGGER_DEBUG