1e6986e1e8d4a57987f47c215490cb080a65ee29aSvet Ganov// Copyright 2014 PDFium Authors. All rights reserved. 2e6986e1e8d4a57987f47c215490cb080a65ee29aSvet Ganov// Use of this source code is governed by a BSD-style license that can be 3e6986e1e8d4a57987f47c215490cb080a65ee29aSvet Ganov// found in the LICENSE file. 4e6986e1e8d4a57987f47c215490cb080a65ee29aSvet Ganov 5e6986e1e8d4a57987f47c215490cb080a65ee29aSvet Ganov// Original code by Matt McCutchen, see the LICENSE file. 6e6986e1e8d4a57987f47c215490cb080a65ee29aSvet Ganov 7e6986e1e8d4a57987f47c215490cb080a65ee29aSvet Ganov#ifndef NUMBERLIKEARRAY_H 8e6986e1e8d4a57987f47c215490cb080a65ee29aSvet Ganov#define NUMBERLIKEARRAY_H 9e6986e1e8d4a57987f47c215490cb080a65ee29aSvet Ganov 10e6986e1e8d4a57987f47c215490cb080a65ee29aSvet Ganov#include <stdlib.h> // abort() 11e6986e1e8d4a57987f47c215490cb080a65ee29aSvet Ganov// Make sure we have NULL. 12e6986e1e8d4a57987f47c215490cb080a65ee29aSvet Ganov#ifndef NULL 13e6986e1e8d4a57987f47c215490cb080a65ee29aSvet Ganov#define NULL 0 14e6986e1e8d4a57987f47c215490cb080a65ee29aSvet Ganov#endif 15e6986e1e8d4a57987f47c215490cb080a65ee29aSvet Ganov 16e6986e1e8d4a57987f47c215490cb080a65ee29aSvet Ganov/* A NumberlikeArray<Blk> object holds a heap-allocated array of Blk with a 17e6986e1e8d4a57987f47c215490cb080a65ee29aSvet Ganov * length and a capacity and provides basic memory management features. 18e6986e1e8d4a57987f47c215490cb080a65ee29aSvet Ganov * BigUnsigned and BigUnsignedInABase both subclass it. 19e6986e1e8d4a57987f47c215490cb080a65ee29aSvet Ganov * 20e6986e1e8d4a57987f47c215490cb080a65ee29aSvet Ganov * NumberlikeArray provides no information hiding. Subclasses should use 21e6986e1e8d4a57987f47c215490cb080a65ee29aSvet Ganov * nonpublic inheritance and manually expose members as desired using 22e6986e1e8d4a57987f47c215490cb080a65ee29aSvet Ganov * declarations like this: 23e6986e1e8d4a57987f47c215490cb080a65ee29aSvet Ganov * 24e6986e1e8d4a57987f47c215490cb080a65ee29aSvet Ganov * public: 25e6986e1e8d4a57987f47c215490cb080a65ee29aSvet Ganov * NumberlikeArray< the-type-argument >::getLength; 26e6986e1e8d4a57987f47c215490cb080a65ee29aSvet Ganov */ 27e6986e1e8d4a57987f47c215490cb080a65ee29aSvet Ganovtemplate <class Blk> 28e6986e1e8d4a57987f47c215490cb080a65ee29aSvet Ganovclass NumberlikeArray { 29e6986e1e8d4a57987f47c215490cb080a65ee29aSvet Ganovpublic: 30e6986e1e8d4a57987f47c215490cb080a65ee29aSvet Ganov 31e6986e1e8d4a57987f47c215490cb080a65ee29aSvet Ganov // Type for the index of a block in the array 32e6986e1e8d4a57987f47c215490cb080a65ee29aSvet Ganov typedef unsigned int Index; 33e6986e1e8d4a57987f47c215490cb080a65ee29aSvet Ganov // The number of bits in a block, defined below. 34e6986e1e8d4a57987f47c215490cb080a65ee29aSvet Ganov static const unsigned int N; 35e6986e1e8d4a57987f47c215490cb080a65ee29aSvet Ganov 36e6986e1e8d4a57987f47c215490cb080a65ee29aSvet Ganov // The current allocated capacity of this NumberlikeArray (in blocks) 37e6986e1e8d4a57987f47c215490cb080a65ee29aSvet Ganov Index cap; 38e6986e1e8d4a57987f47c215490cb080a65ee29aSvet Ganov // The actual length of the value stored in this NumberlikeArray (in blocks) 39e6986e1e8d4a57987f47c215490cb080a65ee29aSvet Ganov Index len; 40e6986e1e8d4a57987f47c215490cb080a65ee29aSvet Ganov // Heap-allocated array of the blocks (can be NULL if len == 0) 41e6986e1e8d4a57987f47c215490cb080a65ee29aSvet Ganov Blk *blk; 42e6986e1e8d4a57987f47c215490cb080a65ee29aSvet Ganov 43e6986e1e8d4a57987f47c215490cb080a65ee29aSvet Ganov // Constructs a ``zero'' NumberlikeArray with the given capacity. 44e6986e1e8d4a57987f47c215490cb080a65ee29aSvet Ganov NumberlikeArray(Index c) : cap(c), len(0) { 45e6986e1e8d4a57987f47c215490cb080a65ee29aSvet Ganov blk = (cap > 0) ? (new Blk[cap]) : NULL; 46e6986e1e8d4a57987f47c215490cb080a65ee29aSvet Ganov } 47e6986e1e8d4a57987f47c215490cb080a65ee29aSvet Ganov 48e6986e1e8d4a57987f47c215490cb080a65ee29aSvet Ganov /* Constructs a zero NumberlikeArray without allocating a backing array. 49e6986e1e8d4a57987f47c215490cb080a65ee29aSvet Ganov * A subclass that doesn't know the needed capacity at initialization 50e6986e1e8d4a57987f47c215490cb080a65ee29aSvet Ganov * time can use this constructor and then overwrite blk without first 51e6986e1e8d4a57987f47c215490cb080a65ee29aSvet Ganov * deleting it. */ 52e6986e1e8d4a57987f47c215490cb080a65ee29aSvet Ganov NumberlikeArray() : cap(0), len(0) { 53e6986e1e8d4a57987f47c215490cb080a65ee29aSvet Ganov blk = NULL; 54e6986e1e8d4a57987f47c215490cb080a65ee29aSvet Ganov } 55e6986e1e8d4a57987f47c215490cb080a65ee29aSvet Ganov 56e6986e1e8d4a57987f47c215490cb080a65ee29aSvet Ganov // Destructor. Note that `delete NULL' is a no-op. 57e6986e1e8d4a57987f47c215490cb080a65ee29aSvet Ganov ~NumberlikeArray() { 58e6986e1e8d4a57987f47c215490cb080a65ee29aSvet Ganov delete [] blk; 59e6986e1e8d4a57987f47c215490cb080a65ee29aSvet Ganov } 60e6986e1e8d4a57987f47c215490cb080a65ee29aSvet Ganov 61e6986e1e8d4a57987f47c215490cb080a65ee29aSvet Ganov /* Ensures that the array has at least the requested capacity; may 62e6986e1e8d4a57987f47c215490cb080a65ee29aSvet Ganov * destroy the contents. */ 63e6986e1e8d4a57987f47c215490cb080a65ee29aSvet Ganov void allocate(Index c); 64e6986e1e8d4a57987f47c215490cb080a65ee29aSvet Ganov 65e6986e1e8d4a57987f47c215490cb080a65ee29aSvet Ganov /* Ensures that the array has at least the requested capacity; does not 66e6986e1e8d4a57987f47c215490cb080a65ee29aSvet Ganov * destroy the contents. */ 67e6986e1e8d4a57987f47c215490cb080a65ee29aSvet Ganov void allocateAndCopy(Index c); 68e6986e1e8d4a57987f47c215490cb080a65ee29aSvet Ganov 69e6986e1e8d4a57987f47c215490cb080a65ee29aSvet Ganov // Copy constructor 70e6986e1e8d4a57987f47c215490cb080a65ee29aSvet Ganov NumberlikeArray(const NumberlikeArray<Blk> &x); 71e6986e1e8d4a57987f47c215490cb080a65ee29aSvet Ganov 72e6986e1e8d4a57987f47c215490cb080a65ee29aSvet Ganov // Assignment operator 73e6986e1e8d4a57987f47c215490cb080a65ee29aSvet Ganov void operator=(const NumberlikeArray<Blk> &x); 74e6986e1e8d4a57987f47c215490cb080a65ee29aSvet Ganov 75e6986e1e8d4a57987f47c215490cb080a65ee29aSvet Ganov // Constructor that copies from a given array of blocks 76e6986e1e8d4a57987f47c215490cb080a65ee29aSvet Ganov NumberlikeArray(const Blk *b, Index blen); 77e6986e1e8d4a57987f47c215490cb080a65ee29aSvet Ganov 78e6986e1e8d4a57987f47c215490cb080a65ee29aSvet Ganov // ACCESSORS 79e6986e1e8d4a57987f47c215490cb080a65ee29aSvet Ganov Index getCapacity() const { return cap; } 80e6986e1e8d4a57987f47c215490cb080a65ee29aSvet Ganov Index getLength() const { return len; } 81e6986e1e8d4a57987f47c215490cb080a65ee29aSvet Ganov Blk getBlock(Index i) const { return blk[i]; } 82e6986e1e8d4a57987f47c215490cb080a65ee29aSvet Ganov bool isEmpty() const { return len == 0; } 83e6986e1e8d4a57987f47c215490cb080a65ee29aSvet Ganov 84e6986e1e8d4a57987f47c215490cb080a65ee29aSvet Ganov /* Equality comparison: checks if both objects have the same length and 85e6986e1e8d4a57987f47c215490cb080a65ee29aSvet Ganov * equal (==) array elements to that length. Subclasses may wish to 86e6986e1e8d4a57987f47c215490cb080a65ee29aSvet Ganov * override. */ 87e6986e1e8d4a57987f47c215490cb080a65ee29aSvet Ganov bool operator ==(const NumberlikeArray<Blk> &x) const; 88e6986e1e8d4a57987f47c215490cb080a65ee29aSvet Ganov 89e6986e1e8d4a57987f47c215490cb080a65ee29aSvet Ganov bool operator !=(const NumberlikeArray<Blk> &x) const { 90e6986e1e8d4a57987f47c215490cb080a65ee29aSvet Ganov return !operator ==(x); 91e6986e1e8d4a57987f47c215490cb080a65ee29aSvet Ganov } 92e6986e1e8d4a57987f47c215490cb080a65ee29aSvet Ganov}; 93e6986e1e8d4a57987f47c215490cb080a65ee29aSvet Ganov 94e6986e1e8d4a57987f47c215490cb080a65ee29aSvet Ganov/* BEGIN TEMPLATE DEFINITIONS. They are present here so that source files that 95e6986e1e8d4a57987f47c215490cb080a65ee29aSvet Ganov * include this header file can generate the necessary real definitions. */ 96e6986e1e8d4a57987f47c215490cb080a65ee29aSvet Ganov 97e6986e1e8d4a57987f47c215490cb080a65ee29aSvet Ganovtemplate <class Blk> 98e6986e1e8d4a57987f47c215490cb080a65ee29aSvet Ganovconst unsigned int NumberlikeArray<Blk>::N = 8 * sizeof(Blk); 99e6986e1e8d4a57987f47c215490cb080a65ee29aSvet Ganov 100e6986e1e8d4a57987f47c215490cb080a65ee29aSvet Ganovtemplate <class Blk> 101e6986e1e8d4a57987f47c215490cb080a65ee29aSvet Ganovvoid NumberlikeArray<Blk>::allocate(Index c) { 102e6986e1e8d4a57987f47c215490cb080a65ee29aSvet Ganov // If the requested capacity is more than the current capacity... 103e6986e1e8d4a57987f47c215490cb080a65ee29aSvet Ganov if (c > cap) { 104e6986e1e8d4a57987f47c215490cb080a65ee29aSvet Ganov // Delete the old number array 105e6986e1e8d4a57987f47c215490cb080a65ee29aSvet Ganov delete [] blk; 106e6986e1e8d4a57987f47c215490cb080a65ee29aSvet Ganov // Allocate the new array 107e6986e1e8d4a57987f47c215490cb080a65ee29aSvet Ganov cap = c; 108e6986e1e8d4a57987f47c215490cb080a65ee29aSvet Ganov blk = new Blk[cap]; 109e6986e1e8d4a57987f47c215490cb080a65ee29aSvet Ganov } 110e6986e1e8d4a57987f47c215490cb080a65ee29aSvet Ganov} 111e6986e1e8d4a57987f47c215490cb080a65ee29aSvet Ganov 112e6986e1e8d4a57987f47c215490cb080a65ee29aSvet Ganovtemplate <class Blk> 113e6986e1e8d4a57987f47c215490cb080a65ee29aSvet Ganovvoid NumberlikeArray<Blk>::allocateAndCopy(Index c) { 114e6986e1e8d4a57987f47c215490cb080a65ee29aSvet Ganov // If the requested capacity is more than the current capacity... 115e6986e1e8d4a57987f47c215490cb080a65ee29aSvet Ganov if (c > cap) { 116e6986e1e8d4a57987f47c215490cb080a65ee29aSvet Ganov Blk *oldBlk = blk; 117e6986e1e8d4a57987f47c215490cb080a65ee29aSvet Ganov // Allocate the new number array 118e6986e1e8d4a57987f47c215490cb080a65ee29aSvet Ganov cap = c; 119e6986e1e8d4a57987f47c215490cb080a65ee29aSvet Ganov blk = new Blk[cap]; 120e6986e1e8d4a57987f47c215490cb080a65ee29aSvet Ganov // Copy number blocks 121e6986e1e8d4a57987f47c215490cb080a65ee29aSvet Ganov Index i; 122e6986e1e8d4a57987f47c215490cb080a65ee29aSvet Ganov for (i = 0; i < len; i++) 123e6986e1e8d4a57987f47c215490cb080a65ee29aSvet Ganov blk[i] = oldBlk[i]; 124e6986e1e8d4a57987f47c215490cb080a65ee29aSvet Ganov // Delete the old array 125e6986e1e8d4a57987f47c215490cb080a65ee29aSvet Ganov delete [] oldBlk; 126e6986e1e8d4a57987f47c215490cb080a65ee29aSvet Ganov } 127e6986e1e8d4a57987f47c215490cb080a65ee29aSvet Ganov} 128e6986e1e8d4a57987f47c215490cb080a65ee29aSvet Ganov 129e6986e1e8d4a57987f47c215490cb080a65ee29aSvet Ganovtemplate <class Blk> 130e6986e1e8d4a57987f47c215490cb080a65ee29aSvet GanovNumberlikeArray<Blk>::NumberlikeArray(const NumberlikeArray<Blk> &x) 131e6986e1e8d4a57987f47c215490cb080a65ee29aSvet Ganov : len(x.len) { 132e6986e1e8d4a57987f47c215490cb080a65ee29aSvet Ganov // Create array 133e6986e1e8d4a57987f47c215490cb080a65ee29aSvet Ganov cap = len; 134e6986e1e8d4a57987f47c215490cb080a65ee29aSvet Ganov blk = new Blk[cap]; 135e6986e1e8d4a57987f47c215490cb080a65ee29aSvet Ganov // Copy blocks 136e6986e1e8d4a57987f47c215490cb080a65ee29aSvet Ganov Index i; 137e6986e1e8d4a57987f47c215490cb080a65ee29aSvet Ganov for (i = 0; i < len; i++) 138e6986e1e8d4a57987f47c215490cb080a65ee29aSvet Ganov blk[i] = x.blk[i]; 139e6986e1e8d4a57987f47c215490cb080a65ee29aSvet Ganov} 140e6986e1e8d4a57987f47c215490cb080a65ee29aSvet Ganov 141e6986e1e8d4a57987f47c215490cb080a65ee29aSvet Ganovtemplate <class Blk> 142e6986e1e8d4a57987f47c215490cb080a65ee29aSvet Ganovvoid NumberlikeArray<Blk>::operator=(const NumberlikeArray<Blk> &x) { 143e6986e1e8d4a57987f47c215490cb080a65ee29aSvet Ganov /* Calls like a = a have no effect; catch them before the aliasing 144e6986e1e8d4a57987f47c215490cb080a65ee29aSvet Ganov * causes a problem */ 145e6986e1e8d4a57987f47c215490cb080a65ee29aSvet Ganov if (this == &x) 146e6986e1e8d4a57987f47c215490cb080a65ee29aSvet Ganov return; 147e6986e1e8d4a57987f47c215490cb080a65ee29aSvet Ganov // Copy length 148e6986e1e8d4a57987f47c215490cb080a65ee29aSvet Ganov len = x.len; 149e6986e1e8d4a57987f47c215490cb080a65ee29aSvet Ganov // Expand array if necessary 150e6986e1e8d4a57987f47c215490cb080a65ee29aSvet Ganov allocate(len); 151e6986e1e8d4a57987f47c215490cb080a65ee29aSvet Ganov // Copy number blocks 152e6986e1e8d4a57987f47c215490cb080a65ee29aSvet Ganov Index i; 153e6986e1e8d4a57987f47c215490cb080a65ee29aSvet Ganov for (i = 0; i < len; i++) 154e6986e1e8d4a57987f47c215490cb080a65ee29aSvet Ganov blk[i] = x.blk[i]; 155e6986e1e8d4a57987f47c215490cb080a65ee29aSvet Ganov} 156e6986e1e8d4a57987f47c215490cb080a65ee29aSvet Ganov 157e6986e1e8d4a57987f47c215490cb080a65ee29aSvet Ganovtemplate <class Blk> 158e6986e1e8d4a57987f47c215490cb080a65ee29aSvet GanovNumberlikeArray<Blk>::NumberlikeArray(const Blk *b, Index blen) 159e6986e1e8d4a57987f47c215490cb080a65ee29aSvet Ganov : cap(blen), len(blen) { 160e6986e1e8d4a57987f47c215490cb080a65ee29aSvet Ganov // Create array 161e6986e1e8d4a57987f47c215490cb080a65ee29aSvet Ganov blk = new Blk[cap]; 162e6986e1e8d4a57987f47c215490cb080a65ee29aSvet Ganov // Copy blocks 163e6986e1e8d4a57987f47c215490cb080a65ee29aSvet Ganov Index i; 164e6986e1e8d4a57987f47c215490cb080a65ee29aSvet Ganov for (i = 0; i < len; i++) 165e6986e1e8d4a57987f47c215490cb080a65ee29aSvet Ganov blk[i] = b[i]; 166e6986e1e8d4a57987f47c215490cb080a65ee29aSvet Ganov} 167e6986e1e8d4a57987f47c215490cb080a65ee29aSvet Ganov 168e6986e1e8d4a57987f47c215490cb080a65ee29aSvet Ganovtemplate <class Blk> 169e6986e1e8d4a57987f47c215490cb080a65ee29aSvet Ganovbool NumberlikeArray<Blk>::operator ==(const NumberlikeArray<Blk> &x) const { 170e6986e1e8d4a57987f47c215490cb080a65ee29aSvet Ganov if (len != x.len) 171e6986e1e8d4a57987f47c215490cb080a65ee29aSvet Ganov // Definitely unequal. 172e6986e1e8d4a57987f47c215490cb080a65ee29aSvet Ganov return false; 173e6986e1e8d4a57987f47c215490cb080a65ee29aSvet Ganov else { 174e6986e1e8d4a57987f47c215490cb080a65ee29aSvet Ganov // Compare corresponding blocks one by one. 175e6986e1e8d4a57987f47c215490cb080a65ee29aSvet Ganov Index i; 176e6986e1e8d4a57987f47c215490cb080a65ee29aSvet Ganov for (i = 0; i < len; i++) 177e6986e1e8d4a57987f47c215490cb080a65ee29aSvet Ganov if (blk[i] != x.blk[i]) 178e6986e1e8d4a57987f47c215490cb080a65ee29aSvet Ganov return false; 179e6986e1e8d4a57987f47c215490cb080a65ee29aSvet Ganov // No blocks differed, so the objects are equal. 180e6986e1e8d4a57987f47c215490cb080a65ee29aSvet Ganov return true; 181e6986e1e8d4a57987f47c215490cb080a65ee29aSvet Ganov } 182e6986e1e8d4a57987f47c215490cb080a65ee29aSvet Ganov} 183e6986e1e8d4a57987f47c215490cb080a65ee29aSvet Ganov 184e6986e1e8d4a57987f47c215490cb080a65ee29aSvet Ganov#endif 185