diff options
Diffstat (limited to 'aapl/resize.h')
| -rw-r--r-- | aapl/resize.h | 344 |
1 files changed, 344 insertions, 0 deletions
diff --git a/aapl/resize.h b/aapl/resize.h new file mode 100644 index 0000000..9e8491a --- /dev/null +++ b/aapl/resize.h @@ -0,0 +1,344 @@ +/* + * Copyright 2002 Adrian Thurston <thurston@complang.org> + */ + +/* This file is part of Aapl. + * + * Aapl is free software; you can redistribute it and/or modify it under the + * terms of the GNU Lesser General Public License as published by the Free + * Software Foundation; either version 2.1 of the License, or (at your option) + * any later version. + * + * Aapl is distributed in the hope that it will be useful, but WITHOUT ANY + * WARRANTY; without even the implied warranty of MERCHANTABILITY or FITNESS + * FOR A PARTICULAR PURPOSE. See the GNU Lesser General Public License for + * more details. + * + * You should have received a copy of the GNU Lesser General Public License + * along with Aapl; if not, write to the Free Software Foundation, Inc., 59 + * Temple Place, Suite 330, Boston, MA 02111-1307 USA + */ + +#ifndef _AAPL_RESIZE_H +#define _AAPL_RESIZE_H + +#include <assert.h> + +#ifdef AAPL_NAMESPACE +namespace Aapl { +#endif + +/* This step is expressed in units of T. Changing this requires changes to + * docs in ResizeLin constructor. */ +#define LIN_DEFAULT_STEP 256 + +/* + * Resizing macros giving different resize methods. + */ + +/* If needed is greater than existing, give twice needed. */ +#define EXPN_UP( existing, needed ) \ + needed > existing ? (needed<<1) : existing + +/* If needed is less than 1 quarter existing, give twice needed. */ +#define EXPN_DOWN( existing, needed ) \ + needed < (existing>>2) ? (needed<<1) : existing + +/* If needed is greater than existing, give needed plus step. */ +#define LIN_UP( existing, needed ) \ + needed > existing ? (needed+step) : existing + +/* If needed is less than existing - 2 * step then give needed plus step. */ +#define LIN_DOWN( existing, needed ) \ + needed < (existing-(step<<1)) ? (needed+step) : existing + +/* Return existing. */ +#define CONST_UP( existing, needed ) existing + +/* Return existing. */ +#define CONST_DOWN( existing, needed ) existing + +/** + * \addtogroup vector + * @{ + */ + +/** \class ResizeLin + * \brief Linear table resizer. + * + * When an up resize or a down resize is needed, ResizeLin allocates the space + * needed plus some user defined step. The result is that when growing the + * vector in a linear fashion, the number of resizes is also linear. + * + * If only up resizing is done, then there will never be more than step unused + * spaces in the vector. If down resizing is done as well, there will never be + * more than 2*step unused spaces in the vector. The up resizing and down + * resizing policies are offset to improve performance when repeatedly + * inserting and removing a small number of elements relative to the step. + * This scheme guarantees that repetitive inserting and removing of a small + * number of elements will never result in repetative reallocation. + * + * The vectors pass sizes to the resizer in units of T, so the step gets + * interpreted as units of T. + */ + +/*@}*/ + +/* Linear resizing. */ +class ResizeLin +{ +protected: + /** + * \brief Default constructor. + * + * Intializes resize step to 256 units of the table type T. + */ + ResizeLin() : step(LIN_DEFAULT_STEP) { } + + /** + * \brief Determine the new table size when up resizing. + * + * If the existing size is insufficient for the space needed, then allocate + * the space needed plus the step. The step is in units of T. + */ + inline long upResize( long existing, long needed ) + { return LIN_UP(existing, needed); } + + /** + * \brief Determine the new table size when down resizing. + * + * If space needed is less than the existing - 2*step, then allocate the + * space needed space plus the step. The step is in units of T. + */ + inline long downResize( long existing, long needed ) + { return LIN_DOWN(existing, needed); } + +public: + /** + * \brief Step for linear resize. + * + * Amount of extra space in units of T added each time a resize must take + * place. This may be changed at any time. The step should be >= 0. + */ + long step; +}; + +/** + * \addtogroup vector + * @{ + */ + +/** \class ResizeCtLin + * \brief Linear table resizer with compile time step. + * + * When an up resize or a down resize is needed, ResizeCtLin allocates the + * space needed plus some compile time defined step. The result is that when + * growing the vector in a linear fashion, the number of resizes is also + * linear. + * + * If only up resizing is done, then there will never be more than step unused + * spaces in the vector. If down resizing is done as well, there will never be + * more than 2*step unused spaces in the vector. The up resizing and down + * resizing policies are offset to improve performance when repeatedly + * inserting and removing a small number of elements relative to the step. + * This scheme guarantees that repetitive inserting and removing of a small + * number of elements will never result in repetative reallocation. + * + * The vectors pass sizes to the resizer in units of T, so the step gets + * interpreted as units of T. + */ + +/*@}*/ + +/* Linear resizing. */ +template <long step> class ResizeCtLin +{ +protected: + /** + * \brief Determine the new table size when up resizing. + * + * If the existing size is insufficient for the space needed, then allocate + * the space needed plus the step. The step is in units of T. + */ + inline long upResize( long existing, long needed ) + { return LIN_UP(existing, needed); } + + /** + * \brief Determine the new table size when down resizing. + * + * If space needed is less than the existing - 2*step, then allocate the + * space needed space plus the step. The step is in units of T. + */ + inline long downResize( long existing, long needed ) + { return LIN_DOWN(existing, needed); } +}; + +/** + * \addtogroup vector + * @{ + */ + +/** \class ResizeConst + * \brief Constant table resizer. + * + * When an up resize is needed the existing size is always used. ResizeConst + * does not allow dynamic resizing. To use ResizeConst, the vector needs to be + * constructed with and initial allocation amount otherwise it will be + * unusable. + */ + +/*@}*/ + +/* Constant table resizing. */ +class ResizeConst +{ +protected: + /* Assert don't need more than exists. Return existing. */ + static inline long upResize( long existing, long needed ); + + /** + * \brief Determine the new table size when down resizing. + * + * Always returns the existing table size. + */ + static inline long downResize( long existing, long needed ) + { return CONST_DOWN(existing, needed); } +}; + +/** + * \brief Determine the new table size when up resizing. + * + * If the existing size is insufficient for the space needed, then an assertion + * will fail. Otherwise returns the existing size. + */ +inline long ResizeConst::upResize( long existing, long needed ) +{ + assert( needed <= existing ); + return CONST_UP(existing, needed); +} + +/** + * \addtogroup vector + * @{ + */ + +/** \class ResizeRunTime + * \brief Run time settable table resizer. + * + * ResizeRunTime can have it's up and down resizing policies set at run time. + * Both up and down policies can be set independently to one of Exponential, + * Linear, or Constant. See the documentation for ResizeExpn, ResizeLin, and + * ResizeConst for the details of the resizing policies. + * + * The policies may be changed at any time. The default policies are + * both Exponential. + */ + +/*@}*/ + +/* Run time resizing. */ +class ResizeRunTime +{ +protected: + /** + * \brief Default constuctor. + * + * The up and down resizing it initialized to Exponetial. The step + * defaults to 256 units of T. + */ + inline ResizeRunTime(); + + /** + * \brief Resizing policies. + */ + enum ResizeType { + Exponential, /*!< Exponential resizing. */ + Linear, /*!< Linear resizing. */ + Constant /*!< Constant table size. */ + }; + + inline long upResize( long existing, long needed ); + inline long downResize( long existing, long needed ); + +public: + /** + * \brief Step for linear resize. + * + * Amount of extra space in units of T added each time a resize must take + * place. This may be changed at any time. The step should be >= 0. + */ + long step; + + /** + * \brief Up resizing policy. + */ + ResizeType upResizeType; + + /** + * \brief Down resizing policy. + */ + ResizeType downResizeType; +}; + +inline ResizeRunTime::ResizeRunTime() +: + step( LIN_DEFAULT_STEP ), + upResizeType( Exponential ), + downResizeType( Exponential ) +{ +} + +/** + * \brief Determine the new table size when up resizing. + * + * Type of up resizing is determined by upResizeType. Exponential, Linear and + * Constant resizing is the same as that of ResizeExpn, ResizeLin and + * ResizeConst. + */ +inline long ResizeRunTime::upResize( long existing, long needed ) +{ + switch ( upResizeType ) { + case Exponential: + return EXPN_UP(existing, needed); + case Linear: + return LIN_UP(existing, needed); + case Constant: + assert( needed <= existing ); + return CONST_UP(existing, needed); + } + return 0; +}; + +/** + * \brief Determine the new table size when down resizing. + * + * Type of down resizing is determined by downResiizeType. Exponential, Linear + * and Constant resizing is the same as that of ResizeExpn, ResizeLin and + * ResizeConst. + */ +inline long ResizeRunTime::downResize( long existing, long needed ) +{ + switch ( downResizeType ) { + case Exponential: + return EXPN_DOWN(existing, needed); + case Linear: + return LIN_DOWN(existing, needed); + case Constant: + return CONST_DOWN(existing, needed); + } + return 0; +} + +/* Don't need these anymore. */ +#undef EXPN_UP +#undef EXPN_DOWN +#undef LIN_UP +#undef LIN_DOWN +#undef CONST_UP +#undef CONST_DOWN + +#ifdef AAPL_NAMESPACE +} +#endif + +#endif /* _AAPL_RESIZE_H */ |