aapl/table.h

   1 /*
   2  *  Copyright 2001, 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_TABLE_H
  23 #define _AAPL_TABLE_H
  24
  25 #ifdef AAPL_NAMESPACE
  26 namespace Aapl {
  27 #endif
  28
  29 /**
  30  * \addtogroup vector
  31  * @{
  32  */
  33
  34 /** \class Table
  35  * \brief Base class for dynamic arrays.
  36  *
  37  * Table is used as the common data storage class for vectors. It does not
  38  * provide any methods to operate on the data and as such it is not intended
  39  * to be used directly. It exists so that algorithms that operatate on dynamic
  40  * arrays can be written without knowing about the various vector classes that
  41  * my exist.
  42  */
  43
  44 /*@}*/
  45
  46 /* Table class. */
  47 template <class T> class Table
  48 {
  49 public:
  50         /* Default Constructor. */
  51         inline Table();
  52
  53         /**
  54          * \brief Get the length of the vector.
  55          *
  56          * \returns the length of the vector.
  57          */
  58         long length() const
  59                 { return tabLen; }
  60
  61         /**
  62          * \brief Table data.
  63          *
  64          * The pointer to the elements in the vector. Modifying the vector may
  65          * cause this pointer to change.
  66          */
  67         T *data;
  68
  69         /**
  70          * \brief Table length.
  71          *
  72          * The number of items of type T in the table.
  73          */
  74         long tabLen;
  75
  76         /**
  77          * \brief Allocated length.
  78          *
  79          * The number of items for which there is room in the current allocation.
  80          */
  81         long allocLen;
  82 };
  83
  84 /**
  85  * \brief Default constructor
  86  *
  87  * Initialize table data to empty.
  88  */
  89 template <class T> inline Table<T>::Table()
  90 :
  91         data(0),
  92         tabLen(0),
  93         allocLen(0)
  94 {
  95 }
  96
  97 /* Default shared table header class. */
  98 struct STabHead
  99 {
 100         /**
 101          * \brief Table length.
 102          *
 103          * The number of items of type T in the table.
 104          */
 105         long tabLen;
 106
 107         /**
 108          * \brief Allocated length.
 109          *
 110          * The number of items for which there is room in the current allocation.
 111          */
 112         long allocLen;
 113
 114         /**
 115          * \brief Ref Count.
 116          *
 117          * The number of shared vectors referencing this data.
 118          */
 119         long refCount;
 120 };
 121
 122 /**
 123  * \addtogroup vector
 124  * @{
 125  */
 126
 127 /** \class STable
 128  * \brief Base class for implicitly shared dynamic arrays.
 129  *
 130  * STable is used as the common data storage class for shared vectors. It does
 131  * not provide any methods to operate on the data and as such it is not
 132  * intended to be used directly. It exists so that algorithms that operatate
 133  * on dynamic arrays can be written without knowing about the various shared
 134  * vector classes that my exist.
 135  */
 136
 137 /*@}*/
 138
 139 /* STable class. */
 140 template <class T> class STable
 141 {
 142 public:
 143         /* Default Constructor. */
 144         inline STable();
 145
 146         /**
 147          * \brief Get the length of the shared vector.
 148          *
 149          * \returns the length of the shared vector.
 150          */
 151         long length() const
 152                 { return data == 0 ? 0 : (((STabHead*)data) - 1)->tabLen; }
 153
 154         /**
 155          * \brief Get header of the shared vector.
 156          *
 157          * \returns the header of the shared vector.
 158          */
 159         STabHead *header() const
 160                 { return data == 0 ? 0 : (((STabHead*)data) - 1); }
 161
 162         /**
 163          * \brief Table data.
 164          *
 165          * The pointer to the elements in the vector. The shared table header is
 166          * located just behind the data. Modifying the vector may cause this
 167          * pointer to change.
 168          */
 169         T *data;
 170 };
 171
 172 /**
 173  * \brief Default constructor
 174  *
 175  * Initialize shared table data to empty.
 176  */
 177 template <class T> inline STable<T>::STable()
 178 :
 179         data(0)
 180 {
 181 }
 182
 183 /* If needed is greater than existing, give twice needed. */
 184 #define EXPN_UP( existing, needed ) \
 185                 needed > existing ? (needed<<1) : existing
 186
 187 /* If needed is less than 1 quarter existing, give twice needed. */
 188 #define EXPN_DOWN( existing, needed ) \
 189                 needed < (existing>>2) ? (needed<<1) : existing
 190
 191 /**
 192  * \addtogroup vector
 193  * @{
 194  */
 195
 196 /** \class ResizeExpn
 197  * \brief Exponential table resizer.
 198  *
 199  * ResizeExpn is the default table resizer. When an up resize is needed, space
 200  * is doubled. When a down resize is needed, space is halved.  The result is
 201  * that when growing the vector in a linear fashion, the number of resizes of
 202  * the allocated space behaves logarithmically.
 203  *
 204  * If only up resizes are done, there will never be more than 2 times the
 205  * needed space allocated. If down resizes are done as well, there will never
 206  * be more than 4 times the needed space allocated.  ResizeExpn uses this 50%
 207  * usage policy on up resizing and 25% usage policy on down resizing to
 208  * improve performance when repeatedly inserting and removing a small number
 209  * of elements relative to the size of the array.  This scheme guarantees that
 210  * repetitive inserting and removing of a small number of elements will never
 211  * result in repetative reallocation.
 212  *
 213  * The sizes passed to the resizer from the vectors are in units of T.
 214  */
 215
 216 /*@}*/
 217
 218 /* Exponential resizer. */
 219 class ResizeExpn
 220 {
 221 protected:
 222         /**
 223          * \brief Determine the new table size when up resizing.
 224          *
 225          * If the existing size is insufficient for the space needed then allocate
 226          * twice the space needed. Otherwise use the existing size.
 227          *
 228          * \returns The new table size.
 229          */
 230         static inline long upResize( long existing, long needed )
 231                 { return EXPN_UP( existing, needed ); }
 232
 233         /**
 234          * \brief Determine the new table size when down resizing.
 235          *
 236          * If the space needed is less than one quarter of the existing size then
 237          * allocate twice the space needed. Otherwise use the exitsing size.
 238          *
 239          * \returns The new table size.
 240          */
 241         static inline long downResize( long existing, long needed )
 242                 { return EXPN_DOWN( existing, needed ); }
 243 };
 244
 245 #undef EXPN_UP
 246 #undef EXPN_DOWN
 247
 248 #ifdef AAPL_NAMESPACE
 249 }
 250 #endif
 251
 252 #endif /* _AAPL_TABLE_H */