* http://mysite.verizon.net/mccutchen/bigint/
*/
+/*
+* 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
#define NUMBERLIKEARRAY
+// An essential memory-management constant.
+// I wish this were built into C++ just as it is in Java.
+#ifndef NULL
+#define NULL 0
+#endif
+
/*
* A NumberlikeArray<Block> object holds a dynamically
* allocated array of Blocks. It provides certain basic
* NumberlikeArray< whatever >::getLength;
*/
+/*debug*/
+#include <iostream>
+
template <class Blk>
class NumberlikeArray {
public:
// 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
+ Blk *blk2; // Dynamically allocated array of the blocks
+
+ static Blk x; // trash that [] can return for out-of-range requests
+
+ void dump() const {
+ std::cout << "Dumping NumberlikeArray @ " << (void *)(this) << '\n';
+ std::cout << "Length " << (len) << ", capacity " << (cap) << '\n';
+ for (unsigned int i = 0; i < len; i++) {
+ std::cout << "Block " << i << ":" << blk2[i] << '\n';
+ }
+ }
+
+ struct BoundsCheckingBlk {
+ const NumberlikeArray *na;
+ BoundsCheckingBlk(NumberlikeArray *na) {
+ this->na = na;
+ }
+ Blk & operator [](Index index) const {
+ if (index >= na->len) {
+ std::cout << "== Out-of-bounds access to block " << index << ". Affected NumberlikeArray: ==\n";
+ na->dump();
+ std::cout << "== End of dump. ==" << std::endl;
+ return x;
+ } else
+ return na->blk2[index];
+ } // dangerous because it allows ``always writable'', but OK for now
+ /*const Blk & operator [](Index index) const {
+ if (index >= na->len)
+ std::cout << "OUT OF BOUNDS! Length " << (na->len) << ", accessed " << index << std::endl;
+ else
+ return na->blk[index];
+ }*/
+ /*operator Blk * () {
+ return na->blk2;
+ }*/
+ };
+
+ BoundsCheckingBlk blk;
+
+ /*
+ * 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 file.
+ */
// MANAGEMENT
- NumberlikeArray(int, Index c) : cap(c), len(0) { // Creates a NumberlikeArray with a capacity
- blk = new Blk[cap];
+ NumberlikeArray(Index c) : cap(c), len(0), blk(this) { // Creates a NumberlikeArray with a capacity
+ blk2 = (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
- NumberlikeArray() : cap(0), len(0) { // Default constructor (empty array)
- blk = new Blk[0];
+ /*
+ * 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.
+ */
+ NumberlikeArray() : cap(0), len(0), blk(this) {
+ blk2 = 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;
+ delete [] blk2; // Does nothing and causes no error if `blk' is null.
}
// PICKING APART
* so other files including NumberlikeArray will be able to generate real definitions.
*/
+template <class Blk>
+Blk NumberlikeArray<Blk>::x = 0;
+
// MANAGEMENT
// This routine is called to ensure the array is at least a
// If the requested capacity is more than the current capacity...
if (c > cap) {
// Delete the old number array
- delete [] blk;
+ delete [] blk2;
// Allocate the new array
cap = c;
- blk = new Blk[cap];
+ blk2 = new Blk[cap];
}
}
void NumberlikeArray<Blk>::allocateAndCopy(Index c) {
// If the requested capacity is more than the current capacity...
if (c > cap) {
- Blk *oldBlk = blk;
+ Blk *oldBlk = blk2;
// Allocate the new number array
cap = c;
- blk = new Blk[cap];
+ blk2 = new Blk[cap];
// Copy number blocks
Index i;
for (i = 0; i < len; i++)
// 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), blk(this) {
// Create array
cap = len;
- blk = new Blk[cap];
+ blk2 = new Blk[cap];
// Copy blocks
Index i;
for (i = 0; i < len; 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 l) : cap(l), len(l), blk(this) {
// Create array
- blk = new Blk[cap];
+ blk2 = new Blk[cap];
// Copy blocks
Index i;
for (i = 0; i < len; i++)
Matt McCutchen's Web Site / bigint / bigint.git / blobdiff