aapl/resize.h

   1 /*
   2  *  Copyright 2002 Adrian Thurston <thurston@cs.queensu.ca>
   3  */
   4
   5 /*  This file is part of Aapl.
   6  *
   7  *  Aapl is free software; you can redistribute it and/or modify it under the
   8  *  terms of the GNU Lesser General Public License as published by the Free
   9  *  Software Foundation; either version 2.1 of the License, or (at your option)
  10  *  any later version.
  11  *
  12  *  Aapl is distributed in the hope that it will be useful, but WITHOUT ANY
  13  *  WARRANTY; without even the implied warranty of MERCHANTABILITY or FITNESS
  14  *  FOR A PARTICULAR PURPOSE.  See the GNU Lesser General Public License for
  15  *  more details.
  16  *
  17  *  You should have received a copy of the GNU Lesser General Public License
  18  *  along with Aapl; if not, write to the Free Software Foundation, Inc., 59
  19  *  Temple Place, Suite 330, Boston, MA 02111-1307 USA
  20  */
  21
  22 #ifndef _AAPL_RESIZE_H
  23 #define _AAPL_RESIZE_H
  24
  25 #include <assert.h>
  26
  27 #ifdef AAPL_NAMESPACE
  28 namespace Aapl {
  29 #endif
  30
  31 /* This step is expressed in units of T. Changing this requires changes to
  32  * docs in ResizeLin constructor.  */
  33 #define LIN_DEFAULT_STEP 256
  34
  35 /*
  36  * Resizing macros giving different resize methods.
  37  */
  38
  39 /* If needed is greater than existing, give twice needed. */
  40 #define EXPN_UP( existing, needed ) \
  41                 needed > existing ? (needed<<1) : existing
  42
  43 /* If needed is less than 1 quarter existing, give twice needed. */
  44 #define EXPN_DOWN( existing, needed ) \
  45                 needed < (existing>>2) ? (needed<<1) : existing
  46
  47 /* If needed is greater than existing, give needed plus step. */
  48 #define LIN_UP( existing, needed ) \
  49         needed > existing ? (needed+step) : existing
  50
  51 /* If needed is less than existing - 2 * step then give needed plus step. */
  52 #define LIN_DOWN( existing, needed ) \
  53         needed < (existing-(step<<1)) ? (needed+step) : existing
  54
  55 /* Return existing. */
  56 #define CONST_UP( existing, needed ) existing
  57
  58 /* Return existing. */
  59 #define CONST_DOWN( existing, needed ) existing
  60
  61 /**
  62  * \addtogroup vector
  63  * @{
  64  */
  65
  66 /** \class ResizeLin
  67  * \brief Linear table resizer.
  68  *
  69  * When an up resize or a down resize is needed, ResizeLin allocates the space
  70  * needed plus some user defined step. The result is that when growing the
  71  * vector in a linear fashion, the number of resizes is also linear.
  72  *
  73  * If only up resizing is done, then there will never be more than step unused
  74  * spaces in the vector. If down resizing is done as well, there will never be
  75  * more than 2*step unused spaces in the vector. The up resizing and down
  76  * resizing policies are offset to improve performance when repeatedly
  77  * inserting and removing a small number of elements relative to the step.
  78  * This scheme guarantees that repetitive inserting and removing of a small
  79  * number of elements will never result in repetative reallocation.
  80  *
  81  * The vectors pass sizes to the resizer in units of T, so the step gets
  82  * interpreted as units of T.
  83  */
  84
  85 /*@}*/
  86
  87 /* Linear resizing. */
  88 class ResizeLin
  89 {
  90 protected:
  91         /**
  92          * \brief Default constructor.
  93          *
  94          * Intializes resize step to 256 units of the table type T.
  95          */
  96         ResizeLin() : step(LIN_DEFAULT_STEP) { }
  97
  98         /**
  99          * \brief Determine the new table size when up resizing.
 100          *
 101          * If the existing size is insufficient for the space needed, then allocate
 102          * the space needed plus the step. The step is in units of T.
 103          */
 104         inline long upResize( long existing, long needed )
 105                 { return LIN_UP(existing, needed); }
 106
 107         /**
 108          * \brief Determine the new table size when down resizing.
 109          *
 110          * If space needed is less than the existing - 2*step, then allocate the
 111          * space needed space plus the step. The step is in units of T.
 112          */
 113         inline long downResize( long existing, long needed )
 114                 { return LIN_DOWN(existing, needed); }
 115
 116 public:
 117         /**
 118          * \brief Step for linear resize.
 119          *
 120          * Amount of extra space in units of T added each time a resize must take
 121          * place. This may be changed at any time. The step should be >= 0.
 122          */
 123         long step;
 124 };
 125
 126 /**
 127  * \addtogroup vector
 128  * @{
 129  */
 130
 131 /** \class ResizeCtLin
 132  * \brief Linear table resizer with compile time step.
 133  *
 134  * When an up resize or a down resize is needed, ResizeCtLin allocates the
 135  * space needed plus some compile time defined step. The result is that when
 136  * growing the vector in a linear fashion, the number of resizes is also
 137  * linear.
 138  *
 139  * If only up resizing is done, then there will never be more than step unused
 140  * spaces in the vector. If down resizing is done as well, there will never be
 141  * more than 2*step unused spaces in the vector. The up resizing and down
 142  * resizing policies are offset to improve performance when repeatedly
 143  * inserting and removing a small number of elements relative to the step.
 144  * This scheme guarantees that repetitive inserting and removing of a small
 145  * number of elements will never result in repetative reallocation.
 146  *
 147  * The vectors pass sizes to the resizer in units of T, so the step gets
 148  * interpreted as units of T.
 149  */
 150
 151 /*@}*/
 152
 153 /* Linear resizing. */
 154 template <long step> class ResizeCtLin
 155 {
 156 protected:
 157         /**
 158          * \brief Determine the new table size when up resizing.
 159          *
 160          * If the existing size is insufficient for the space needed, then allocate
 161          * the space needed plus the step. The step is in units of T.
 162          */
 163         inline long upResize( long existing, long needed )
 164                 { return LIN_UP(existing, needed); }
 165
 166         /**
 167          * \brief Determine the new table size when down resizing.
 168          *
 169          * If space needed is less than the existing - 2*step, then allocate the
 170          * space needed space plus the step. The step is in units of T.
 171          */
 172         inline long downResize( long existing, long needed )
 173                 { return LIN_DOWN(existing, needed); }
 174 };
 175
 176 /**
 177  * \addtogroup vector
 178  * @{
 179  */
 180
 181 /** \class ResizeConst
 182  * \brief Constant table resizer.
 183  *
 184  * When an up resize is needed the existing size is always used. ResizeConst
 185  * does not allow dynamic resizing. To use ResizeConst, the vector needs to be
 186  * constructed with and initial allocation amount otherwise it will be
 187  * unusable.
 188  */
 189
 190 /*@}*/
 191
 192 /* Constant table resizing. */
 193 class ResizeConst
 194 {
 195 protected:
 196         /* Assert don't need more than exists. Return existing. */
 197         static inline long upResize( long existing, long needed );
 198
 199         /**
 200          * \brief Determine the new table size when down resizing.
 201          *
 202          * Always returns the existing table size.
 203          */
 204         static inline long downResize( long existing, long needed )
 205                 { return CONST_DOWN(existing, needed); }
 206 };
 207
 208 /**
 209  * \brief Determine the new table size when up resizing.
 210  *
 211  * If the existing size is insufficient for the space needed, then an assertion
 212  * will fail. Otherwise returns the existing size.
 213  */
 214 inline long ResizeConst::upResize( long existing, long needed )
 215 {
 216         assert( needed <= existing );
 217         return CONST_UP(existing, needed);
 218 }
 219
 220 /**
 221  * \addtogroup vector
 222  * @{
 223  */
 224
 225 /** \class ResizeRunTime
 226  * \brief Run time settable table resizer.
 227  *
 228  * ResizeRunTime can have it's up and down resizing policies set at run time.
 229  * Both up and down policies can be set independently to one of Exponential,
 230  * Linear, or Constant. See the documentation for ResizeExpn, ResizeLin, and
 231  * ResizeConst for the details of the resizing policies.
 232  *
 233  * The policies may be changed at any time. The default policies are
 234  * both Exponential.
 235  */
 236
 237 /*@}*/
 238
 239 /* Run time resizing. */
 240 class ResizeRunTime
 241 {
 242 protected:
 243         /**
 244          * \brief Default constuctor.
 245          *
 246          * The up and down resizing it initialized to Exponetial. The step
 247          * defaults to 256 units of T.
 248          */
 249         inline ResizeRunTime();
 250
 251         /**
 252          * \brief Resizing policies.
 253          */
 254         enum ResizeType {
 255                 Exponential,  /*!< Exponential resizing. */
 256                 Linear,       /*!< Linear resizing. */
 257                 Constant      /*!< Constant table size. */
 258         };
 259
 260         inline long upResize( long existing, long needed );
 261         inline long downResize( long existing, long needed );
 262
 263 public:
 264         /**
 265          * \brief Step for linear resize.
 266          *
 267          * Amount of extra space in units of T added each time a resize must take
 268          * place. This may be changed at any time. The step should be >= 0.
 269          */
 270         long step;
 271
 272         /**
 273          * \brief Up resizing policy.
 274          */
 275         ResizeType upResizeType;
 276
 277         /**
 278          * \brief Down resizing policy.
 279          */
 280         ResizeType downResizeType;
 281 };
 282
 283 inline ResizeRunTime::ResizeRunTime()
 284 :
 285         step( LIN_DEFAULT_STEP ),
 286         upResizeType( Exponential ),
 287         downResizeType( Exponential )
 288 {
 289 }
 290
 291 /**
 292  * \brief Determine the new table size when up resizing.
 293  *
 294  * Type of up resizing is determined by upResizeType. Exponential, Linear and
 295  * Constant resizing is the same as that of ResizeExpn, ResizeLin and
 296  * ResizeConst.
 297  */
 298 inline long ResizeRunTime::upResize( long existing, long needed )
 299 {
 300         switch ( upResizeType ) {
 301         case Exponential:
 302                 return EXPN_UP(existing, needed);
 303         case Linear:
 304                 return LIN_UP(existing, needed);
 305         case Constant:
 306                 assert( needed <= existing );
 307                 return CONST_UP(existing, needed);
 308         }
 309         return 0;
 310 };
 311
 312 /**
 313  * \brief Determine the new table size when down resizing.
 314  *
 315  * Type of down resizing is determined by downResiizeType. Exponential, Linear
 316  * and Constant resizing is the same as that of ResizeExpn, ResizeLin and
 317  * ResizeConst.
 318  */
 319 inline long ResizeRunTime::downResize( long existing, long needed )
 320 {
 321         switch ( downResizeType ) {
 322         case Exponential:
 323                 return EXPN_DOWN(existing, needed);
 324         case Linear:
 325                 return LIN_DOWN(existing, needed);
 326         case Constant:
 327                 return CONST_DOWN(existing, needed);
 328         }
 329         return 0;
 330 }
 331
 332 /* Don't need these anymore. */
 333 #undef EXPN_UP
 334 #undef EXPN_DOWN
 335 #undef LIN_UP
 336 #undef LIN_DOWN
 337 #undef CONST_UP
 338 #undef CONST_DOWN
 339
 340 #ifdef AAPL_NAMESPACE
 341 }
 342 #endif
 343
 344 #endif /* _AAPL_RESIZE_H */