Rex Jaeschke is an independent computer consultant, author, and seminar leader. He participates in both ANSI and ISO C Standards meetings and is the editor of The Journal of C Language Translation, a quarterly publication aimed at implementors of C language translation tools. Readers are encouraged to submit column topics and suggestions to Rex at 2051 Swans Neck Way, Reston, VA 22091 or via UUCP at rex@aussie.com.
Handling Multiple Stacks of the Same Type
Last month's column described how to implement a stack and to use push and pop functions on it. However, it would be a waste to have a different set of push and pop functions for each stack. This month I will discuss how to share the code.Consider Listing 1. An object of type stack contains the current context of a given stack. This context includes the stack's name (for debugging or trace-back purposes), the base address of the stack, the stack's size and its current stack pointer. The stack descriptors stack1, stack2, and stack3 therefore describe the three different int stacks. The first stack is stored in a global array, the second in a file scope static array, while the third is allocated at runtime using malloc. In short, the stack management functions don't know and don't care where the stacks reside.
Listing 2 tells push and pop which stack to use but the notation is not particularly unwieldy. Listing 3 could be made a little bit cleaner by passing the stack descriptor by value, but that could be just a little more expensive since the descriptor is a structure. The output produced is shown in Figure 1.
Handling Multiple Stacks of Different Types
Can this idea be extended to manage stacks of different types? The answer is a qualified yes. One way could be to use generic pointers, as shown in Listing 4. Here, a void pointer is used to hold the stack's base address. This also requires an extra member to indicate the type of elements in any given stack, as in
void push(stack *, void *); void *pop(stack *);The interface to push and pop gets very messy, however. Since an object of arbitrary type cannot be passed by value, it must be passed by assigning it to a named object and then passing that object by address, as shown in Listing 5. (This eliminates the ability to push a constant directly.) This is possible since all data pointer types are compatible with void *. Similarly, an arbitrary typed value can't be returned, so the address is returned instead.To use the value returned by pop you must use an explicit cast as well as a dereference since pop returns a pointer (see Listing 6) . In fact, since pop returns the address of the object just popped from the stack, if you don't dereference the pointer returned immediately, the location it points to will be overwritten by the very next push and the value popped will change.
The source for push and pop is far from pretty. Since it cannot perform arithmetic (via subscripting) on void pointers, you must explicitly provide the scaling factor.
Using Unions
Another way to look at the problem is rather than have stacks of different types, have one stack that can handle objects of different types. You can achieve this via a union, as shown in Listing 7.Each entry is a union of all the possible types along with a flag member that indicates which type this entry currently represents. We push nodes by value and return them by value using simple and obvious notation. If you try to pop from an empty stack, instead of complaining, pop returns a copy of a local node that has a special type field value of Error.
Next, consider Listing 8. Note the interesting controlling expression in the while loop — it uses the comma operator in an effective manner.
The stack management functions presented in Listing 9 are quite straightforward.
Opposing Stacks
A stack grows and shrinks from one end only so it is possible to have two stacks based at opposite ends of an array with their tops growing toward each other. This can save space if both stacks don't grow very large at the same time. However, when one is smaller, the other can grow larger and vice-versa.The dump_stack function in Listing 10 allows us to see the contents of the underlying array as the two stacks grow and shrink. Note that it pops in a different order than it pushes, so the operations are staggered.
The stack in Listing 11 can only handle four elements. This helps you monitor the progress as elements are pushed and popped. Clearly, it would be larger in a real application. Of course, the bases of the two stacks are at either end of the underlying array and in one stack the stack pointer increments as we push and in the other it decrements. Stack overflow is detected when the two stack pointers bump into each other. Note that it's OK if both of them point to the same element since that last free element is available to which ever stack can use it first.
The two versions of push and pop in Listing 12 are different enough that it is not obvious you can write a single version that is both elegant and efficient. The output produced is shown in Figure 2.
Note that even after a value is popped from a stack it still remains there — only the stack pointer is adjusted. This is exactly what happens when a C function returns; the values of it's automatic variables are still on the stack but are outside the bounds of the newly adjusted stack pointer. They remain intact until that part of the stack is overwritten for some other purpose.