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