NumberlikeArray.hh

   1 /*
   2  * This mechanism prevents files from being included twice.
   3  * Each file gets its own `id' (here `NUMBERLIKEARRAY').
   4  * When `#include'd, this file checks whether its `id' has
   5  * already been flagged.  If not, it flags the `id' and
   6  * loads the declarations.
   7  */
   8 #ifndef NUMBERLIKEARRAY_H
   9 #define NUMBERLIKEARRAY_H
  10
  11 // An essential memory-management constant.
  12 // I wish this were built into C++ just as it is in Java.
  13 #ifndef NULL
  14 #define NULL 0
  15 #endif
  16
  17 /*
  18  * A NumberlikeArray<Blk> object holds a dynamically
  19  * allocated array of Blk.  It provides certain basic
  20  * memory management features needed by both BigUnsigned
  21  * and BigUnsignedInABase, which are both derived from it.
  22  *
  23  * NumberlikeArray provides no information hiding, so make
  24  * sure you know what you are doing if you use it directly.
  25  * Classes derived from it will probably wish to pass on
  26  * some members of NumberlikeArray to their clients while
  27  * keeping some safe for themselves.  These classes should
  28  * use protected inheritance and manually make some members
  29  * public with declarations like this:
  30  *
  31  * public:
  32  *     NumberlikeArray< whatever >::getLength;
  33  */
  34
  35 template <class Blk>
  36 class NumberlikeArray {
  37 public:
  38
  39         typedef unsigned int Index; // Type for the index of a block in the array
  40         static const unsigned int N; // The number of bits in a block, defined below.
  41
  42         // FIELDS
  43         Index cap; // The current allocated capacity of this NumberlikeArray (in blocks)
  44         Index len; // The actual length of the value stored in this NumberlikeArray (in blocks)
  45         Blk *blk; // Dynamically allocated array of the blocks
  46
  47         /*
  48          * Change made on 2005.01.06:
  49          *
  50          * If a zero-length NumberlikeArray is desired, no array is actually allocated.
  51          * Instead, `blk' is set to `NULL', and `cap' and `len' are zero as usual.
  52          *
  53          * `blk' is never dereferenced if the array has zero length.  Furthermore,
  54          * `delete NULL;' does nothing and causes no error. Therefore, we can use
  55          * `NULL' as if it were a zero-length array from `new'.
  56          *
  57          * This is a great convenience because the only code that need be changed
  58          * is the array allocation code.  All other code will still work fine.
  59          */
  60
  61         // MANAGEMENT
  62         NumberlikeArray(Index c) : cap(c), len(0) { // Creates a NumberlikeArray with a capacity
  63                 blk = (cap > 0) ? (new Blk[cap]) : NULL;
  64         }
  65         void allocate(Index c); // Ensures the array has at least the indicated capacity, maybe discarding contents
  66         void allocateAndCopy(Index c); // Ensures the array has at least the indicated capacity, preserving its contents
  67
  68         /*
  69          * Default constructor.
  70          *
  71          * If a class derived from NumberlikeArray knows at initializer time what size array
  72          * it wants, it can call the first constructor listed above in an initializer.
  73          *
  74          * Otherwise, this default constructor will be implicitly invoked, pointing `blk' to
  75          * `NULL', a fake zero-length block array.  The derived class can allocate the desired
  76          * array itself and overwrite `blk'; it need not `delete [] blk' first.
  77          *
  78          * This change fixes a memory leak reported by Milan Tomic on 2005.01.06.
  79          * Integer-type-to-BigUnsigned (and BigInteger) conversion constructors have always
  80          * allocated their own array of length 0 or 1 after seeing whether the input is zero.
  81          * But when the NumberlikeArray transition occurred, these constructors contained an
  82          * implicit initializer call to the old NumberlikeArray default constructor, which
  83          * created a real `new'-allocated zero-length array.  This array would then be lost,
  84          * causing a small but annoying memory leak.
  85          */
  86         NumberlikeArray() : cap(0), len(0) {
  87                 blk = NULL;
  88         }
  89         NumberlikeArray(const NumberlikeArray<Blk> &x); // Copy constructor
  90         void operator=(const NumberlikeArray<Blk> &x); // Assignment operator
  91         NumberlikeArray(const Blk *b, Index l); // Constructor from an array of blocks
  92         ~NumberlikeArray() { // Destructor
  93                 delete [] blk; // Does nothing and causes no error if `blk' is null.
  94         }
  95
  96         // PICKING APART
  97         // These accessors can be used to get the pieces of the value
  98         Index getCapacity() const { return cap; }
  99         Index getLength() const { return len; }
 100         Blk getBlock(Index i) const { return blk[i]; };
 101         bool isEmpty() const { return len == 0; }
 102
 103         // Equality comparison: checks if arrays have same length and matching values
 104         // Derived classes may wish to override these if differing arrays can
 105         // sometimes be considered equivalent.
 106         bool operator ==(const NumberlikeArray<Blk> &x) const;
 107         bool operator !=(const NumberlikeArray<Blk> &x) const { return !operator ==(x); }
 108
 109 };
 110
 111 /*
 112  * =================================
 113  * BELOW THIS POINT are template definitions; above are declarations.
 114  *
 115  * Definitions would ordinarily belong in a file NumberlikeArray.cc so that they would
 116  * be compiled once into NumberlikeArray.o and then linked.
 117  *
 118  * However, because of the way templates are usually implemented,
 119  * template ``definitions'' are treated as declarations by the compiler.
 120  * When someone uses an instance of the template, definitions are generated,
 121  * and the linker is smart enough to toss duplicate definitions for the same
 122  * instance generated by different files.
 123  *
 124  * Thus, the template ``definitions'' for NumberlikeArray must appear in this header file
 125  * so other files including NumberlikeArray will be able to generate real definitions.
 126  */
 127
 128 template <class Blk>
 129 const unsigned int NumberlikeArray<Blk>::N = 8 * sizeof(Blk);
 130
 131 // MANAGEMENT
 132
 133 // This routine is called to ensure the array is at least a
 134 // certain size before another value is written into it.
 135 template <class Blk>
 136 void NumberlikeArray<Blk>::allocate(Index c) {
 137         // If the requested capacity is more than the current capacity...
 138         if (c > cap) {
 139                 // Delete the old number array
 140                 delete [] blk;
 141                 // Allocate the new array
 142                 cap = c;
 143                 blk = new Blk[cap];
 144         }
 145 }
 146
 147 // This routine is called to ensure the array is at least a
 148 // certain size without losing its contents.
 149 template <class Blk>
 150 void NumberlikeArray<Blk>::allocateAndCopy(Index c) {
 151         // If the requested capacity is more than the current capacity...
 152         if (c > cap) {
 153                 Blk *oldBlk = blk;
 154                 // Allocate the new number array
 155                 cap = c;
 156                 blk = new Blk[cap];
 157                 // Copy number blocks
 158                 Index i;
 159                 for (i = 0; i < len; i++)
 160                         blk[i] = oldBlk[i];
 161                 // Delete the old array
 162                 delete [] oldBlk;
 163         }
 164 }
 165
 166 // Copy constructor
 167 template <class Blk>
 168 NumberlikeArray<Blk>::NumberlikeArray(const NumberlikeArray<Blk> &x) : len(x.len) {
 169         // Create array
 170         cap = len;
 171         blk = new Blk[cap];
 172         // Copy blocks
 173         Index i;
 174         for (i = 0; i < len; i++)
 175                 blk[i] = x.blk[i];
 176 }
 177
 178 // Assignment operator
 179 template <class Blk>
 180 void NumberlikeArray<Blk>::operator=(const NumberlikeArray<Blk> &x) {
 181         // Calls like a = a have no effect
 182         if (this == &x)
 183                 return;
 184         // Copy length
 185         len = x.len;
 186         // Expand array if necessary
 187         allocate(len);
 188         // Copy number blocks
 189         Index i;
 190         for (i = 0; i < len; i++)
 191                 blk[i] = x.blk[i];
 192 }
 193
 194 // Constructor from an array of blocks
 195 template <class Blk>
 196 NumberlikeArray<Blk>::NumberlikeArray(const Blk *b, Index l) : cap(l), len(l) {
 197         // Create array
 198         blk = new Blk[cap];
 199         // Copy blocks
 200         Index i;
 201         for (i = 0; i < len; i++)
 202                 blk[i] = b[i];
 203 }
 204
 205
 206 // EQUALITY TEST
 207 // This uses == to compare Blks for equality.
 208 // Therefore, Blks must have an == operator with the desired semantics.
 209 template <class Blk>
 210 bool NumberlikeArray<Blk>::operator ==(const NumberlikeArray<Blk> &x) const {
 211         // Different lengths imply different objects.
 212         if (len != x.len)
 213                 return false;
 214         else {
 215                 // Compare matching blocks one by one.
 216                 Index i;
 217                 for (i = 0; i < len; i++)
 218                         if (blk[i] != x.blk[i])
 219                                 return false;
 220                 // If no blocks differed, the objects are equal.
 221                 return true;
 222         }
 223 }
 224
 225 #endif