1// -*- C++ -*- 2 3// Copyright (C) 2005-2013 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 binary_heap_/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 /// Resize policy for binary heap. 51 template<typename _Tp> 52 class resize_policy 53 { 54 private: 55 enum 56 { 57 ratio = 8, 58 factor = 2 59 }; 60 61 /// Next shrink size. 62 _Tp m_shrink_size; 63 64 /// Next grow size. 65 _Tp m_grow_size; 66 67 public: 68 typedef _Tp size_type; 69 70 static const _Tp min_size = 16; 71 72 resize_policy() : m_shrink_size(0), m_grow_size(min_size) 73 { PB_DS_ASSERT_VALID((*this)) } 74 75 resize_policy(const resize_policy& other) 76 : m_shrink_size(other.m_shrink_size), m_grow_size(other.m_grow_size) 77 { PB_DS_ASSERT_VALID((*this)) } 78 79 inline void 80 swap(resize_policy<_Tp>&); 81 82 inline bool 83 resize_needed_for_grow(size_type) const; 84 85 inline bool 86 resize_needed_for_shrink(size_type) const; 87 88 inline bool 89 grow_needed(size_type) const; 90 91 inline bool 92 shrink_needed(size_type) const; 93 94 inline size_type 95 get_new_size_for_grow() const; 96 97 inline size_type 98 get_new_size_for_shrink() const; 99 100 inline size_type 101 get_new_size_for_arbitrary(size_type) const; 102 103 inline void 104 notify_grow_resize(); 105 106 inline void 107 notify_shrink_resize(); 108 109 void 110 notify_arbitrary(size_type); 111 112#ifdef _GLIBCXX_DEBUG 113 void 114 assert_valid(const char*, int) const; 115#endif 116 117#ifdef PB_DS_BINARY_HEAP_TRACE_ 118 void 119 trace() const; 120#endif 121 }; 122 123 template<typename _Tp> 124 const _Tp resize_policy<_Tp>::min_size; 125 126 template<typename _Tp> 127 inline void 128 resize_policy<_Tp>:: 129 swap(resize_policy<_Tp>& other) 130 { 131 std::swap(m_shrink_size, other.m_shrink_size); 132 std::swap(m_grow_size, other.m_grow_size); 133 } 134 135 template<typename _Tp> 136 inline bool 137 resize_policy<_Tp>:: 138 resize_needed_for_grow(size_type size) const 139 { 140 _GLIBCXX_DEBUG_ASSERT(size <= m_grow_size); 141 return size == m_grow_size; 142 } 143 144 template<typename _Tp> 145 inline bool 146 resize_policy<_Tp>:: 147 resize_needed_for_shrink(size_type size) const 148 { 149 _GLIBCXX_DEBUG_ASSERT(size <= m_grow_size); 150 return size == m_shrink_size; 151 } 152 153 template<typename _Tp> 154 inline typename resize_policy<_Tp>::size_type 155 resize_policy<_Tp>:: 156 get_new_size_for_grow() const 157 { return m_grow_size * factor; } 158 159 template<typename _Tp> 160 inline typename resize_policy<_Tp>::size_type 161 resize_policy<_Tp>:: 162 get_new_size_for_shrink() const 163 { 164 const size_type half_size = m_grow_size / factor; 165 return std::max(min_size, half_size); 166 } 167 168 template<typename _Tp> 169 inline typename resize_policy<_Tp>::size_type 170 resize_policy<_Tp>:: 171 get_new_size_for_arbitrary(size_type size) const 172 { 173 size_type ret = min_size; 174 while (ret < size) 175 ret *= factor; 176 return ret; 177 } 178 179 template<typename _Tp> 180 inline void 181 resize_policy<_Tp>:: 182 notify_grow_resize() 183 { 184 PB_DS_ASSERT_VALID((*this)) 185 _GLIBCXX_DEBUG_ASSERT(m_grow_size >= min_size); 186 m_grow_size *= factor; 187 m_shrink_size = m_grow_size / ratio; 188 PB_DS_ASSERT_VALID((*this)) 189 } 190 191 template<typename _Tp> 192 inline void 193 resize_policy<_Tp>:: 194 notify_shrink_resize() 195 { 196 PB_DS_ASSERT_VALID((*this)) 197 m_shrink_size /= factor; 198 if (m_shrink_size == 1) 199 m_shrink_size = 0; 200 m_grow_size = std::max(m_grow_size / factor, min_size); 201 PB_DS_ASSERT_VALID((*this)) 202 } 203 204 template<typename _Tp> 205 inline void 206 resize_policy<_Tp>:: 207 notify_arbitrary(size_type actual_size) 208 { 209 m_grow_size = actual_size; 210 m_shrink_size = m_grow_size / ratio; 211 PB_DS_ASSERT_VALID((*this)) 212 } 213 214#ifdef _GLIBCXX_DEBUG 215 template<typename _Tp> 216 void 217 resize_policy<_Tp>:: 218 assert_valid(const char* __file, int __line) const 219 { 220 PB_DS_DEBUG_VERIFY(m_shrink_size == 0 221 || m_shrink_size * ratio == m_grow_size); 222 PB_DS_DEBUG_VERIFY(m_grow_size >= min_size); 223 } 224#endif 225 226#ifdef PB_DS_BINARY_HEAP_TRACE_ 227 template<typename _Tp> 228 void 229 resize_policy<_Tp>:: 230 trace() const 231 { 232 std::cerr << "shrink = " << m_shrink_size 233 << " grow = " << m_grow_size << std::endl; 234 } 235#endif 236 237} // namespace detail 238} // namespace __gnu_pbds 239 240#endif 241