Store
 

Store

Forward declarations.

Our calculator can deal with symbolic variables. The user creates a variable by inventing a name for it and then using it in arithmetic operations. Every variable has to be initialized—assigned a value in an assignment expression—before it can be used in evaluating other expressions. To store the values of user defined variables our calculator will need some kind of "memory." We will create a class Store that contains a fixed number, size, of memory cells. Each cell can store a value of the type double. The cells are numbered from zero to size-1. Each cell can be in either of two states—uninitialized or initialized. 
enum { stNotInit, stInit };

The association between a symbolic name—a string—and the cell number is handled by the symbol table. For instance, when the user first introduces a given variable, say x, the string "x" is added to the symbol table and assigned an integer, say 3. From that point on, the value of the variable x will be stored in cell number 3 in the Store object.

We would also like to pre-initialize the symbol table and the store with some useful constants like e (the base of natural logarithms) and pi (the ratio of the circumference of a circle to its diameter). We would like to do it in the constructor of Store, therefore we need to pass it a reference to the symbol table. Now here’s a little snag: We want to put the definition of the class Store in a separate header file, store.h. The definition of the class SymbolTable is in a different file, symtab.h. When the compiler is looking at the declaration of the constructor of Store 
    Store (int size, SymbolTable & symTab);

it has no idea what SymbolTable is. The simple-minded solution is to include the file symtab.h in store.h. There is nothing wrong with doing that, except for burdening the compiler with the processing of one more file whenever it is processing symtab.h or any file that includes it. In a really big project, with a lot of header files including one another, it might become a real headache. If you are using any type of dependency checker, it will assume that a change in symtab.h requires the recompilation of all the files that include it directly or indirectly. In particular, any file that includes store.h will have to be recompiled too. And all this unnecessary processing just because we wanted to let the compiler know that SymbolTable is a name of a class? Why don’t we just say that? Indeed, the syntax of such a forward declaration is: 
class SymbolTable;

As long as we are only using pointers or references to SymbolTable, this will do. We don’t need to include symtab.h. On the other hand, a forward declaration would not be sufficient if we wanted to call any of the methods of SymbolTable (including the constructor or the destructor) or if we tried to embed or inherit from SymbolTable. 
class SymbolTable; // forward declaration

class Store
{
public:
    Store (int size, SymbolTable & symTab);
    ~Store ()
    {
        delete []_cell;
        delete []_status;
    }
    bool IsInit (int id) const
    {
        return (id < _size && _status [id] != stNotInit);
    }
    double Value (int id) const
    {
        assert (IsInit (id));
        return _cell [id];
    }
    void SetValue (int id, double val)
    {
        if (id < _size)
        {
            _cell [id] = val;
            _status [id] = stInit;
        }
    }
private:
    int             _size;
    double        * _cell;
    unsigned char * _status;
};

Store contains two arrays. The array of cells and the array of statuses (initialized/uninitialized). They are initialized in the constructor and deleted in the destructor. We also store the size of these arrays (it's used for error checking). The client of Store can check whether a given cell has been initialized, get the value stored there, as well as set (and initialize) this value.

Why am I using two arrays instead of a single array of two-field objects? I could have defined a class Cell 
class Cell
{
    // …
private:
    double            _value;
    unsigned char     _status;
};

I could have had a single array of Cell 's in Store instead of two separate arrays for values and statuses.

Both solutions have their merits. Using Cell improves code understandability and maintenance. On the other hand, using two separate arrays may be more space efficient. How come? Because of the alignment of data.

On most computer architectures it is cheaper to retrieve data from memory if it's aligned on 32-bit or 64-bit boundary. So, unless you specify otherwise, the compiler will force the alignment of user-defined data structures on such boundaries. In particular, it might add padding to your data structures. It's very likely that the compiler will add three (or even seven) bytes of padding to every Cell. This way, the size of a Cell in memory will be guaranteed to be a multiple of 32 (or 64) bits, and accessing an array of Cells will be very fast.

As long as you're dealing with reasonably small arrays, you shouldn't care. But if your program uses lots of memory, you might want to be more careful. In our implementation we tried to reduce the memory overhead by declaring the array _status as an array of bytes (unsigned chars). In fact, we could get away with an array of bits. After all, status is a two-valued variable and it can be encoded using a single bit. Implementing a bit array is nontrivial and involves explicit bit-wise operations on every access, but in some cases it might save you oodles of memory.

So here's a rule of thumb: If you anticipate that you might have to shrink your data structures because of memory constraints, implementing the shrinkable part separately will give you more flexibility. In our case, we could, in the future, re-implement the _status array as a bit array without changing much code around it. On the other hand, if you anticipate that you might have to add more under-sized variables to each element of the array, you'd be better off combining them into a single class. In our case, if we expected that we might, say, need some kind of type enumeration for every variable, we could easily add it to the Cell class.

Making choices like this is what makes programming interesting.

The constructor of Store is defined in the source file store.cpp. Since the constructor calls actual methods of the SymbolTable, the forward declaration of this class is no longer sufficient and we need to explicitly include the header symtab.h in store.cpp. 
Store::Store (int size, SymbolTable & symTab): _size (size)
{
    _cell = new double [size];
    _status = new unsigned char [size];
    for (int i = 0; i < size; ++i)
        _status [i] = stNotInit;

    // add predefined constants
    // Note: if more needed, do a more general job
    cout << "e = " << exp(1) << endl;
    int id = symTab.ForceAdd ("e", 1);
    SetValue (id, exp (1));
    cout << "pi = " << 2 * acos (0.0) << endl;
    id = symTab.ForceAdd ("pi", 2);
    SetValue (id, 2.0 * acos (0.0));
}

We add the mapping of the string "e" of size 1 to the symbol table and then use the returned integer as a cell number in the call to SetValue. The same procedure is used to initialize the value of "pi."
Next.