Logo Search packages:      
Sourcecode: ragel version File versions

resize.h

/*
 *  Copyright 2002 Adrian Thurston <adriant@ragel.ca>
 */

/*  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. */
00088 class ResizeLin
{
protected:
      /**
       * \brief Default constructor.
       *
       * Intializes resize step to 256 units of the table type T.
       */
00096       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.
       */
00104       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.
       */
00113       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.
       */
00123       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. */
00154 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.
       */
00163       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.
       */
00172       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. */
00193 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.
       */
00204       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.
 */
00214 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. */
00240 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.
       */
00254       enum ResizeType {
00255             Exponential,  /*!< Exponential resizing. */
00256             Linear,       /*!< Linear resizing. */
00257             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.
       */
00270       long step;

      /**
       * \brief Up resizing policy.
       */
00275       ResizeType upResizeType;

      /**
       * \brief Down resizing policy.
       */
00280       ResizeType downResizeType;
};

00283 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.
 */
00298 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.
 */
00319 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 */

Generated by  Doxygen 1.6.0   Back to index