X-Git-Url: https://mattmccutchen.net/bigint/bigint.git/blobdiff_plain/2301f99c6175d543626d61c0bda90e80f85e7eac..3e1327901d299a537a8d932c49dd330f87ac3bda:/NumberlikeArray.hh diff --git a/NumberlikeArray.hh b/NumberlikeArray.hh index 8fa52d7..53c8e5b 100644 --- a/NumberlikeArray.hh +++ b/NumberlikeArray.hh @@ -1,137 +1,95 @@ -/* - * This mechanism prevents files from being included twice. - * Each file gets its own `id' (here `NUMBERLIKEARRAY'). - * When `#include'd, this file checks whether its `id' has - * already been flagged. If not, it flags the `id' and - * loads the declarations. - */ #ifndef NUMBERLIKEARRAY_H #define NUMBERLIKEARRAY_H -// An essential memory-management constant. -// I wish this were built into C++ just as it is in Java. +// Make sure we have NULL. #ifndef NULL #define NULL 0 #endif -/* - * A NumberlikeArray object holds a dynamically - * allocated array of Blk. It provides certain basic - * memory management features needed by both BigUnsigned - * and BigUnsignedInABase, which are both derived from it. +/* A NumberlikeArray object holds a heap-allocated array of Blk with a + * length and a capacity and provides basic memory management features. + * BigUnsigned and BigUnsignedInABase both subclass it. * - * NumberlikeArray provides no information hiding, so make - * sure you know what you are doing if you use it directly. - * Classes derived from it will probably wish to pass on - * some members of NumberlikeArray to their clients while - * keeping some safe for themselves. These classes should - * use protected inheritance and manually make some members - * public with declarations like this: + * NumberlikeArray provides no information hiding. Subclasses should use + * nonpublic inheritance and manually expose members as desired using + * declarations like this: * * public: - * NumberlikeArray< whatever >::getLength; + * NumberlikeArray< the-type-argument >::getLength; */ - template class NumberlikeArray { public: - typedef unsigned int Index; // Type for the index of a block in the array - static const unsigned int N; // The number of bits in a block, defined below. - - // FIELDS - Index cap; // The current allocated capacity of this NumberlikeArray (in blocks) - Index len; // The actual length of the value stored in this NumberlikeArray (in blocks) - Blk *blk; // Dynamically allocated array of the blocks - - /* - * Change made on 2005.01.06: - * - * If a zero-length NumberlikeArray is desired, no array is actually allocated. - * Instead, `blk' is set to `NULL', and `cap' and `len' are zero as usual. - * - * `blk' is never dereferenced if the array has zero length. Furthermore, - * `delete NULL;' does nothing and causes no error. Therefore, we can use - * `NULL' as if it were a zero-length array from `new'. - * - * This is a great convenience because the only code that need be changed - * is the array allocation code. All other code will still work fine. - */ - - // MANAGEMENT - NumberlikeArray(Index c) : cap(c), len(0) { // Creates a NumberlikeArray with a capacity + // Type for the index of a block in the array + typedef unsigned int Index; + // The number of bits in a block, defined below. + static const unsigned int N; + + // The current allocated capacity of this NumberlikeArray (in blocks) + Index cap; + // The actual length of the value stored in this NumberlikeArray (in blocks) + Index len; + // Heap-allocated array of the blocks (can be NULL if len == 0) + Blk *blk; + + // Constructs a ``zero'' NumberlikeArray with the given capacity. + NumberlikeArray(Index c) : cap(c), len(0) { blk = (cap > 0) ? (new Blk[cap]) : NULL; } - void allocate(Index c); // Ensures the array has at least the indicated capacity, maybe discarding contents - void allocateAndCopy(Index c); // Ensures the array has at least the indicated capacity, preserving its contents - - /* - * Default constructor. - * - * If a class derived from NumberlikeArray knows at initializer time what size array - * it wants, it can call the first constructor listed above in an initializer. - * - * Otherwise, this default constructor will be implicitly invoked, pointing `blk' to - * `NULL', a fake zero-length block array. The derived class can allocate the desired - * array itself and overwrite `blk'; it need not `delete [] blk' first. - * - * This change fixes a memory leak reported by Milan Tomic on 2005.01.06. - * Integer-type-to-BigUnsigned (and BigInteger) conversion constructors have always - * allocated their own array of length 0 or 1 after seeing whether the input is zero. - * But when the NumberlikeArray transition occurred, these constructors contained an - * implicit initializer call to the old NumberlikeArray default constructor, which - * created a real `new'-allocated zero-length array. This array would then be lost, - * causing a small but annoying memory leak. - */ + + /* Constructs a zero NumberlikeArray without allocating a backing array. + * A subclass that doesn't know the needed capacity at initialization + * time can use this constructor and then overwrite blk without first + * deleting it. */ NumberlikeArray() : cap(0), len(0) { blk = NULL; } - NumberlikeArray(const NumberlikeArray &x); // Copy constructor - void operator=(const NumberlikeArray &x); // Assignment operator - NumberlikeArray(const Blk *b, Index l); // Constructor from an array of blocks - ~NumberlikeArray() { // Destructor - delete [] blk; // Does nothing and causes no error if `blk' is null. + + // Destructor. Note that `delete NULL' is a no-op. + ~NumberlikeArray() { + delete [] blk; } - // PICKING APART - // These accessors can be used to get the pieces of the value - Index getCapacity() const { return cap; } - Index getLength() const { return len; } - Blk getBlock(Index i) const { return blk[i]; }; - bool isEmpty() const { return len == 0; } + /* Ensures that the array has at least the requested capacity; may + * destroy the contents. */ + void allocate(Index c); + + /* Ensures that the array has at least the requested capacity; does not + * destroy the contents. */ + void allocateAndCopy(Index c); + + // Copy constructor + NumberlikeArray(const NumberlikeArray &x); + + // Assignment operator + void operator=(const NumberlikeArray &x); - // Equality comparison: checks if arrays have same length and matching values - // Derived classes may wish to override these if differing arrays can - // sometimes be considered equivalent. + // Constructor that copies from a given array of blocks + NumberlikeArray(const Blk *b, Index blen); + + // ACCESSORS + Index getCapacity() const { return cap; } + Index getLength() const { return len; } + Blk getBlock(Index i) const { return blk[i]; } + bool isEmpty() const { return len == 0; } + + /* Equality comparison: checks if both objects have the same length and + * equal (==) array elements to that length. Subclasses may wish to + * override. */ bool operator ==(const NumberlikeArray &x) const; - bool operator !=(const NumberlikeArray &x) const { return !operator ==(x); } + bool operator !=(const NumberlikeArray &x) const { + return !operator ==(x); + } }; -/* - * ================================= - * BELOW THIS POINT are template definitions; above are declarations. - * - * Definitions would ordinarily belong in a file NumberlikeArray.cc so that they would - * be compiled once into NumberlikeArray.o and then linked. - * - * However, because of the way templates are usually implemented, - * template ``definitions'' are treated as declarations by the compiler. - * When someone uses an instance of the template, definitions are generated, - * and the linker is smart enough to toss duplicate definitions for the same - * instance generated by different files. - * - * Thus, the template ``definitions'' for NumberlikeArray must appear in this header file - * so other files including NumberlikeArray will be able to generate real definitions. - */ +/* BEGIN TEMPLATE DEFINITIONS. They are present here so that source files that + * include this header file can generate the necessary real definitions. */ template const unsigned int NumberlikeArray::N = 8 * sizeof(Blk); -// MANAGEMENT - -// This routine is called to ensure the array is at least a -// certain size before another value is written into it. template void NumberlikeArray::allocate(Index c) { // If the requested capacity is more than the current capacity... @@ -144,8 +102,6 @@ void NumberlikeArray::allocate(Index c) { } } -// This routine is called to ensure the array is at least a -// certain size without losing its contents. template void NumberlikeArray::allocateAndCopy(Index c) { // If the requested capacity is more than the current capacity... @@ -163,9 +119,9 @@ void NumberlikeArray::allocateAndCopy(Index c) { } } -// Copy constructor template -NumberlikeArray::NumberlikeArray(const NumberlikeArray &x) : len(x.len) { +NumberlikeArray::NumberlikeArray(const NumberlikeArray &x) + : len(x.len) { // Create array cap = len; blk = new Blk[cap]; @@ -175,10 +131,10 @@ NumberlikeArray::NumberlikeArray(const NumberlikeArray &x) : len(x.len blk[i] = x.blk[i]; } -// Assignment operator template void NumberlikeArray::operator=(const NumberlikeArray &x) { - // Calls like a = a have no effect + /* Calls like a = a have no effect; catch them before the aliasing + * causes a problem */ if (this == &x) return; // Copy length @@ -191,9 +147,9 @@ void NumberlikeArray::operator=(const NumberlikeArray &x) { blk[i] = x.blk[i]; } -// Constructor from an array of blocks template -NumberlikeArray::NumberlikeArray(const Blk *b, Index l) : cap(l), len(l) { +NumberlikeArray::NumberlikeArray(const Blk *b, Index blen) + : cap(blen), len(blen) { // Create array blk = new Blk[cap]; // Copy blocks @@ -202,22 +158,18 @@ NumberlikeArray::NumberlikeArray(const Blk *b, Index l) : cap(l), len(l) { blk[i] = b[i]; } - -// EQUALITY TEST -// This uses == to compare Blks for equality. -// Therefore, Blks must have an == operator with the desired semantics. template bool NumberlikeArray::operator ==(const NumberlikeArray &x) const { - // Different lengths imply different objects. if (len != x.len) + // Definitely unequal. return false; else { - // Compare matching blocks one by one. + // Compare corresponding blocks one by one. Index i; for (i = 0; i < len; i++) if (blk[i] != x.blk[i]) return false; - // If no blocks differed, the objects are equal. + // No blocks differed, so the objects are equal. return true; } }