-/*
- * 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<Blk> 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<Blk> 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 Blk>
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<Blk> &x); // Copy constructor
- void operator=(const NumberlikeArray<Blk> &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<Blk> &x);
+
+ // Assignment operator
+ void operator=(const NumberlikeArray<Blk> &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<Blk> &x) const;
- bool operator !=(const NumberlikeArray<Blk> &x) const { return !operator ==(x); }
+ bool operator !=(const NumberlikeArray<Blk> &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 <class Blk>
const unsigned int NumberlikeArray<Blk>::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 <class Blk>
void NumberlikeArray<Blk>::allocate(Index c) {
// If the requested capacity is more than the current capacity...
}
}
-// This routine is called to ensure the array is at least a
-// certain size without losing its contents.
template <class Blk>
void NumberlikeArray<Blk>::allocateAndCopy(Index c) {
// If the requested capacity is more than the current capacity...
}
}
-// Copy constructor
template <class Blk>
-NumberlikeArray<Blk>::NumberlikeArray(const NumberlikeArray<Blk> &x) : len(x.len) {
+NumberlikeArray<Blk>::NumberlikeArray(const NumberlikeArray<Blk> &x)
+ : len(x.len) {
// Create array
cap = len;
blk = new Blk[cap];
blk[i] = x.blk[i];
}
-// Assignment operator
template <class Blk>
void NumberlikeArray<Blk>::operator=(const NumberlikeArray<Blk> &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
blk[i] = x.blk[i];
}
-// Constructor from an array of blocks
template <class Blk>
-NumberlikeArray<Blk>::NumberlikeArray(const Blk *b, Index l) : cap(l), len(l) {
+NumberlikeArray<Blk>::NumberlikeArray(const Blk *b, Index blen)
+ : cap(blen), len(blen) {
// Create array
blk = new Blk[cap];
// Copy blocks
blk[i] = b[i];
}
-
-// EQUALITY TEST
-// This uses == to compare Blks for equality.
-// Therefore, Blks must have an == operator with the desired semantics.
template <class Blk>
bool NumberlikeArray<Blk>::operator ==(const NumberlikeArray<Blk> &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;
}
}
Matt McCutchen's Web Site / bigint / bigint.git / blobdiff