Resizable Data Structures

The use of memory blocks and arrays (which are basically typed memory blocks) for data storage has several great advantages, such as quick and direct access and ease of implementation. Implementing arrays is a task which is fairly straightforward and far less error-prone and time-consuming than, say, using linked lists. The reason arrays are often put aside as valid programming solutions, though, is that their size seems to be too static in nature. Often array size is specified at compile time or it is determined at array-creation time, after which it does not change until the array is destroyed. Arrays are often declared as follows:

void MakeArrays(int size)
{
   char name[200];                 // size determined at compile time.
   char *pName = new char[size];   // size determined at creation time.
   ~~

The following sections show how you can use arrays and memory blocks with dynamic sizes. This means you can keep the advantages of normal arrays and memory blocks and still be able to influence their size by enlarging or shrinking them when necessary.

Enlarging Arrays

This section shows how to increase the size of memory blocks. The BigChunkStack class from an earlier section of this chapter is taken as an example. You will remember that the BigChunkStack allocated a large block of memory during initialization. This block of memory was called a pool and objects that should be placed on the stack were copied into this pool. When the pool could not fit any more objects, an error was returned. This section shows you how you can expand the BigChunkStack with the ability to have its pool grow when it is in danger of filling up. The dynamic version of the BigChunkStack can be found in the companion file 09Source02.cpp on the Web site. In the rest of this section you will see what changes need to be made to the original BigChunkStack.

The first thing you have to do to make the BigChunkStack resizable is to change the implementation of the pool. In the original BigChunkStack the pool was declared as an array with a fixed size: char pool[MAXSIZE]. For a dynamic pool, you should declare the pool variable as a pointer and the MAXSIZE constant as a member variable. You can set initial values for both in the constructor:

class BigChunkStack
{
public:
    BigChunkStack()
    {  totalSize = 0; MAXSIZE = 0;
      emptyElemSize = sizeof(elem); lastElemSize = 0;}
private:
   char   *pool;         // pointer instead of constant array.
   int     MAXSIZE;      // variable that will keep track of pool size.

Listing 9.5 shows the implementation of a new BigChunkStack::push() function that detects when the pool should grow.

Code Listing 9.5. Resizing push Function for the BigChunkStack

inline void BigChunkStack::push(const char *s, const int nr)
{  // add new item to the top of the stack

    int newStringSize   = strlen(s) + 1;
    int totalElemSize   = newStringSize + emptyElemSize;

    while (totalSize + totalElemSize > MAXSIZE)
    {
        if (!grow())
        {
            cout << "Error, Stack Overflow!!" << endl;
            return;
        }
    }

    elem *newElem       = (elem*) (pool + totalSize);

    newElem->id         = nr;
    newElem->nameSize   = newStringSize;
    newElem->previousElemSize = lastElemSize;
    strcpy(&newElem->name, s);

    lastElemSize = totalElemSize;
    totalSize  += totalElemSize;
}

The check that originally determined whether another object could be pushed onto the stack now makes sure the pool is always sufficiently large. It does this by repeatedly calling a grow() function to enlarge the pool while it is too small to contain the new data. The grow() function is where all the interesting work is done. Listing 9.6 shows the implementation of a BigChunkStack::grow() function that detects when the pool should grow.

Code Listing 9.6. grow Function for the BigChunkStack

#define INITSIZE 1000

inline int BigChunkStack::grow()
// Create or Enlarge the pool size.
{
    if (MAXSIZE == 0)
    {
        // create.
        pool = (char*) malloc(INITSIZE);
        if (pool == NULL) return 0;

        MAXSIZE = INITSIZE;
        return 1;
    }
    else
    {
        // enlarge.
        MAXSIZE *= 2;

        char* tempPool = (char*) realloc(pool, MAXSIZE);
        if (tempPool == NULL) return 0;

        pool = tempPool;
        return 1;
    }
}

Basically, there are two situations in which the pool can grow. First, the pool can grow when there is no pool at all. This is the initialization of the pool in the if body of the grow function. The constant INITSIZE is used for the initial size. Any value could be chosen here; your choice of value will depend on the requirements of the stack.

Second, the pool can grow when the existing pool is too small to fit an object that is being pushed onto the stack. This is done by the reallocation in the else body of the grow function. Each time the pool needs to grow it doubles in size. Because reallocating memory blocks takes time, you do not want to do this too often.

The C++ function that is used to resize the pool is called realloc , which takes as arguments a pointer to the first byte of the block to be resized and an integer denoting the new desired size. When realloc is successful, it returns a pointer to the reallocated block. When there is not enough memory to perform the reallocation, a NULL pointer is returned and the block of data is left unchanged. This is why you will want to capture and test the returned pointer before initializing the pool variable with it. When the realloc is unsuccessful, you will not want to overwrite the existing pool pointer with it. Simply return an error and your program will still be able to pop elements from the stack later. For more information on the realloc call, consult your C++ documentation.

The changes made in this section to the BigChunkStack result in a stack that will grow when necessary. The following section shows additional changes that allow the stack to decrease in size when it becomes empty.

Shrinking Arrays

This section shows how to decrease the size of memory blocks. The BigChunkStack class is again taken as an example. The dynamic version of the BigChunkStack can be found in the companion file 09Source02.cpp on the Web site. In the rest of this section you will see what changes were made to the original BigChunkStack to allow it to shrink. The changes in this section and in the section Enlarging Arrays constitute all the changes to be made to the BigChunkStack to make it completely dynamic.

Listing 9.7 shows the implementation of a new BigChunkStack::pop() function that detects when the pool should shrink.

Code Listing 9.7. Resizing Pop() Function for the BigChunkStack

inline void BigChunkStack::pop(char *s, int &nr)
{  // return item from the top of the stack and free it

    if (totalSize * 4 <= MAXSIZE)

        shrink();

    if (totalSize != 0)
    {
        totalSize       -= lastElemSize;
        elem *popped    = (elem*) (pool + totalSize);
        lastElemSize    = popped->previousElemSize;

        strcpy(s, &popped->name);
        nr      = popped->id;

    }
    else
    {
        cout << "Error, Stack Underflow!!"  << endl;
    }
}

The check at the beginning of Listing 9.7 is the addition that allows the stack to shrink by calling the shrink() member function. The following rule is chosen for when the stack should shrink: The stack's pool will shrink when it is only 25% full. The shrink() function is where all the interesting work is done. Listing 9.8 shows a shrink function for the BigChunkStack.

Code Listing 9.8. shrink Function for the BigChunkStack

inline void BigChunkStack::shrink()
// Shrink the pool size.
{
    if ((MAXSIZE/2) >= INITSIZE)
    {
        // shrink.
        char* tempPool = (char*) realloc(pool, MAXSIZE/2);
        if (tempPool == NULL) return ;

        MAXSIZE /= 2;
        pool = tempPool;
        return;
    }
}

The shrink function will decrease the pool by 50% as long as the resulting size is greater than or equal to the chosen INITSIZE. You will note that the realloc function is used again. realloc can be used to increase as well as decrease memory block sizes.