1// -*- C++ -*- 2 3// Copyright (C) 2005, 2006, 2009 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// Under Section 7 of GPL version 3, you are granted additional 17// permissions described in the GCC Runtime Library Exception, version 18// 3.1, as published by the Free Software Foundation. 19 20// You should have received a copy of the GNU General Public License and 21// a copy of the GCC Runtime Library Exception along with this program; 22// see the files COPYING3 and COPYING.RUNTIME respectively. If not, see 23// <http://www.gnu.org/licenses/>. 24 25// Copyright (C) 2004 Ami Tavory and Vladimir Dreizin, IBM-HRL. 26 27// Permission to use, copy, modify, sell, and distribute this software 28// is hereby granted without fee, provided that the above copyright 29// notice appears in all copies, and that both that copyright notice 30// and this permission notice appear in supporting documentation. None 31// of the above authors, nor IBM Haifa Research Laboratories, make any 32// representation about the suitability of this software for any 33// purpose. It is provided "as is" without express or implied 34// warranty. 35 36/** 37 * @file resize_policy.hpp 38 * Contains an implementation class for a binary_heap. 39 */ 40 41#ifndef PB_DS_BINARY_HEAP_RESIZE_POLICY_HPP 42#define PB_DS_BINARY_HEAP_RESIZE_POLICY_HPP 43 44#include <debug/debug.h> 45 46namespace __gnu_pbds 47{ 48 namespace detail 49 { 50 51#define PB_DS_CLASS_T_DEC template<typename Size_Type> 52 53#define PB_DS_CLASS_C_DEC resize_policy<Size_Type> 54 55 template<typename Size_Type> 56 class resize_policy 57 { 58 public: 59 typedef Size_Type size_type; 60 61 enum 62 { 63 min_size = 16 64 }; 65 66 public: 67 inline 68 resize_policy(); 69 70 inline void 71 swap(PB_DS_CLASS_C_DEC& other); 72 73 inline bool 74 resize_needed_for_grow(size_type size) const; 75 76 inline bool 77 resize_needed_for_shrink(size_type size) const; 78 79 inline bool 80 grow_needed(size_type size) const; 81 82 inline bool 83 shrink_needed(size_type size) const; 84 85 inline size_type 86 get_new_size_for_grow() const; 87 88 inline size_type 89 get_new_size_for_shrink() const; 90 91 size_type 92 get_new_size_for_arbitrary(size_type size) const; 93 94 inline void 95 notify_grow_resize(); 96 97 inline void 98 notify_shrink_resize(); 99 100 void 101 notify_arbitrary(size_type actual_size); 102 103#ifdef _GLIBCXX_DEBUG 104 void 105 assert_valid() const; 106#endif 107 108#ifdef PB_DS_BINARY_HEAP_TRACE_ 109 void 110 trace() const; 111#endif 112 113 private: 114 enum 115 { 116 ratio = 8, 117 factor = 2 118 }; 119 120 private: 121 size_type m_next_shrink_size; 122 size_type m_next_grow_size; 123 }; 124 125 PB_DS_CLASS_T_DEC 126 inline 127 PB_DS_CLASS_C_DEC:: 128 resize_policy() : 129 m_next_shrink_size(0), 130 m_next_grow_size(min_size) 131 { _GLIBCXX_DEBUG_ONLY(assert_valid();) } 132 133 PB_DS_CLASS_T_DEC 134 inline void 135 PB_DS_CLASS_C_DEC:: 136 swap(PB_DS_CLASS_C_DEC& other) 137 { 138 std::swap(m_next_shrink_size, other.m_next_shrink_size); 139 std::swap(m_next_grow_size, other.m_next_grow_size); 140 } 141 142 PB_DS_CLASS_T_DEC 143 inline bool 144 PB_DS_CLASS_C_DEC:: 145 resize_needed_for_grow(size_type size) const 146 { 147 _GLIBCXX_DEBUG_ASSERT(size <= m_next_grow_size); 148 return size == m_next_grow_size; 149 } 150 151 PB_DS_CLASS_T_DEC 152 inline bool 153 PB_DS_CLASS_C_DEC:: 154 resize_needed_for_shrink(size_type size) const 155 { 156 _GLIBCXX_DEBUG_ASSERT(size <= m_next_grow_size); 157 return size == m_next_shrink_size; 158 } 159 160 PB_DS_CLASS_T_DEC 161 inline typename PB_DS_CLASS_C_DEC::size_type 162 PB_DS_CLASS_C_DEC:: 163 get_new_size_for_grow() const 164 { return m_next_grow_size* factor; } 165 166 PB_DS_CLASS_T_DEC 167 inline typename PB_DS_CLASS_C_DEC::size_type 168 PB_DS_CLASS_C_DEC:: 169 get_new_size_for_shrink() const 170 { 171 const size_type half_size = m_next_grow_size / factor; 172 return std::max(static_cast<size_type>(min_size), half_size); 173 } 174 175 PB_DS_CLASS_T_DEC 176 inline typename PB_DS_CLASS_C_DEC::size_type 177 PB_DS_CLASS_C_DEC:: 178 get_new_size_for_arbitrary(size_type size) const 179 { 180 size_type ret = min_size; 181 while (ret < size) 182 ret *= factor; 183 return ret; 184 } 185 186 PB_DS_CLASS_T_DEC 187 inline void 188 PB_DS_CLASS_C_DEC:: 189 notify_grow_resize() 190 { 191 _GLIBCXX_DEBUG_ONLY(assert_valid();) 192 _GLIBCXX_DEBUG_ASSERT(m_next_grow_size >= min_size); 193 m_next_grow_size *= factor; 194 m_next_shrink_size = m_next_grow_size / ratio; 195 _GLIBCXX_DEBUG_ONLY(assert_valid();) 196 } 197 198 PB_DS_CLASS_T_DEC 199 inline void 200 PB_DS_CLASS_C_DEC:: 201 notify_shrink_resize() 202 { 203 _GLIBCXX_DEBUG_ONLY(assert_valid();) 204 m_next_shrink_size /= factor; 205 if (m_next_shrink_size == 1) 206 m_next_shrink_size = 0; 207 208 m_next_grow_size = 209 std::max(m_next_grow_size / factor, static_cast<size_type>(min_size)); 210 _GLIBCXX_DEBUG_ONLY(assert_valid();) 211 } 212 213 PB_DS_CLASS_T_DEC 214 inline void 215 PB_DS_CLASS_C_DEC:: 216 notify_arbitrary(size_type actual_size) 217 { 218 m_next_grow_size = actual_size; 219 m_next_shrink_size = m_next_grow_size / ratio; 220 _GLIBCXX_DEBUG_ONLY(assert_valid();) 221 } 222 223#ifdef _GLIBCXX_DEBUG 224 PB_DS_CLASS_T_DEC 225 void 226 PB_DS_CLASS_C_DEC:: 227 assert_valid() const 228 { 229 _GLIBCXX_DEBUG_ASSERT(m_next_shrink_size == 0 || 230 m_next_shrink_size* ratio == m_next_grow_size); 231 232 _GLIBCXX_DEBUG_ASSERT(m_next_grow_size >= min_size); 233 } 234#endif 235 236#ifdef PB_DS_BINARY_HEAP_TRACE_ 237 PB_DS_CLASS_T_DEC 238 void 239 PB_DS_CLASS_C_DEC:: 240 trace() const 241 { 242 std::cerr << "shrink = " << m_next_shrink_size << 243 " grow = " << m_next_grow_size << std::endl; 244 } 245#endif 246 247#undef PB_DS_CLASS_T_DEC 248#undef PB_DS_CLASS_C_DEC 249 250} // namespace detail 251} // namespace __gnu_pbds 252 253#endif 254