Initial check in of big integer library, v2010.04.30

R=tsepez@chromium.org

Review URL: https://codereview.chromium.org/773443004

1 files changed, 177 insertions, 0 deletions

diff --git a/third_party/bigint/NumberlikeArray.hh b/third_party/bigint/NumberlikeArray.hh
new file mode 100644
index 0000000000..53c8e5be8f
--- /dev/null
+++ b/third_party/bigint/NumberlikeArray.hh
@@ -0,0 +1,177 @@
+#ifndef NUMBERLIKEARRAY_H
+#define NUMBERLIKEARRAY_H
+
+// Make sure we have NULL.
+#ifndef NULL
+#define NULL 0
+#endif
+
+/* 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.  Subclasses should use
+ * nonpublic inheritance and manually expose members as desired using
+ * declarations like this:
+ *
+ * public:
+ *     NumberlikeArray< the-type-argument >::getLength;
+ */
+template <class Blk>
+class NumberlikeArray {
+public:
+
+	// 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;
+	}
+
+	/* 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;
+	}
+
+	// Destructor.  Note that `delete NULL' is a no-op.
+	~NumberlikeArray() {
+		delete [] blk;
+	}
+
+	/* 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);
+
+	// 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);
+	}
+};
+
+/* 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);
+
+template <class Blk>
+void NumberlikeArray<Blk>::allocate(Index c) {
+	// If the requested capacity is more than the current capacity...
+	if (c > cap) {
+		// Delete the old number array
+		delete [] blk;
+		// Allocate the new array
+		cap = c;
+		blk = new Blk[cap];
+	}
+}
+
+template <class Blk>
+void NumberlikeArray<Blk>::allocateAndCopy(Index c) {
+	// If the requested capacity is more than the current capacity...
+	if (c > cap) {
+		Blk *oldBlk = blk;
+		// Allocate the new number array
+		cap = c;
+		blk = new Blk[cap];
+		// Copy number blocks
+		Index i;
+		for (i = 0; i < len; i++)
+			blk[i] = oldBlk[i];
+		// Delete the old array
+		delete [] oldBlk;
+	}
+}
+
+template <class Blk>
+NumberlikeArray<Blk>::NumberlikeArray(const NumberlikeArray<Blk> &x)
+		: len(x.len) {
+	// Create array
+	cap = len;
+	blk = new Blk[cap];
+	// Copy blocks
+	Index i;
+	for (i = 0; i < len; i++)
+		blk[i] = x.blk[i];
+}
+
+template <class Blk>
+void NumberlikeArray<Blk>::operator=(const NumberlikeArray<Blk> &x) {
+	/* Calls like a = a have no effect; catch them before the aliasing
+	 * causes a problem */
+	if (this == &x)
+		return;
+	// Copy length
+	len = x.len;
+	// Expand array if necessary
+	allocate(len);
+	// Copy number blocks
+	Index i;
+	for (i = 0; i < len; i++)
+		blk[i] = x.blk[i];
+}
+
+template <class Blk>
+NumberlikeArray<Blk>::NumberlikeArray(const Blk *b, Index blen)
+		: cap(blen), len(blen) {
+	// Create array
+	blk = new Blk[cap];
+	// Copy blocks
+	Index i;
+	for (i = 0; i < len; i++)
+		blk[i] = b[i];
+}
+
+template <class Blk>
+bool NumberlikeArray<Blk>::operator ==(const NumberlikeArray<Blk> &x) const {
+	if (len != x.len)
+		// Definitely unequal.
+		return false;
+	else {
+		// Compare corresponding blocks one by one.
+		Index i;
+		for (i = 0; i < len; i++)
+			if (blk[i] != x.blk[i])
+				return false;
+		// No blocks differed, so the objects are equal.
+		return true;
+	}
+}
+
+#endif