Comparison of Array Based Stacks in C and Ada

Comparison of Array Based Stacks in C and Ada

The stack is one of the simplest data structures. Array-based stacks can be implemented in all languages supporting arrays, even including early versions of Fortran which did not support pointers.

This comparison is based upon C code published at http://www-cs.ccny.cuny.edu/~peter/dstest.html

The C code published at http://www-cs.ccny.cuny.edu/~peter/dstest.html supports the book Advanced Data Structures authored by Peter Braß and published by Cambridge University Press.

The Ada code uses Ada2012, which added aspect specifications, pre and post conditions, type invariants and subtype predicates to the Ada language. Descriptions of these and other features added in the Ada 2012 version are available at The Ada 2012 Rationale

Array Stack

The C code for Array Stack is shown below.

Example 1 ArrayStack.c

#include <stdio.h> #include <stdlib.h> typedef int item_t; typedef struct {item_t *base; item_t *top; int size;} stack_t; stack_t *create_stack(int size) {   stack_t *st;     st = (stack_t *) malloc( sizeof(stack_t) );     st->base = (item_t *) malloc( size * sizeof(item_t) );     st->size = size;     st->top = st->base;     return( st ); } int stack_empty(stack_t *st) {   return( st->base == st->top ); } int push( item_t x, stack_t *st) {   if ( st->top < st->base + st->size )     {   *(st->top) = x; st->top += 1;  return( 0 );     }     else        return( -1 ); } item_t pop(stack_t *st) {   st->top -= 1;     return( *(st->top) ); } item_t top_element(stack_t *st) {   return( *(st->top -1) ); } void remove_stack(stack_t *st) {   free( st->base );     free( st ); } int main() {  stack_t *st;    char nextop;    st = create_stack(50);    printf("Made Array-Based Stack of size 50\n");    while( (nextop = getchar())!= 'q' )    { if( nextop == 'i' )      { int insitem;        scanf(" %d", &insitem);        push( insitem, st );        printf(" pushed %d. The current top item is %d\n", insitem,            top_element(st) );      }       if( nextop == 'd' )      { int de_item;        getchar();        de_item = pop(st);        printf("  popped item %d", de_item);        if( stack_empty(st) )          printf(" the stack is now empty\n");        else          printf(" the top element is now %d\n",  top_element(st) );      }      if( nextop == '?' )      { getchar();        if( stack_empty(st) )          printf("the stack is empty\n");        else          printf("the top element is %d\n", top_element(st) );      }         }    remove_stack(st);    printf(" removed stack\n");    return(0); }

The author claims that his book is not a text on Object Oriented Programming, but instead a text on advanced data structures.  None of the examples in the URL referenced above employ C header files. I assume that was done to simplify publication, placing both the data structure, including its associated functions, and a main program to demonstrate the structure, in a single file.

Issues with ArrayStack.c

While the author could have used array indexing to access the values of the array at the heart of the stack_t struct, he chose to perform pointer arithmetic directly. From a style point of view it is often preferred to use array indexing to access the elements of an array.

The push function

Example 2 push function

int push( item_t x, stack_t *st) {   if ( st->top < st->base + st->size )     {   *(st->top) = x; st->top += 1;  return( 0 );     }     else        return( -1 ); }

Note that this code only actually pushes a value onto the stack if the stack is not full. This is a correct behavior. When the array is full this function returns -1.

Example 3 Calling push

while( (nextop = getchar())!= 'q' )    { if( nextop == 'i' )      { int insitem;        scanf(" %d", &insitem);        push( insitem, st );        printf(" pushed %d. The current top item is %d\n", insitem,            top_element(st) );      }

The example  of calling the push function ignores the return value. This means that the push operation fails silently. The user is given no indication that the push fails. In fact, the printf statement following the push function call tells the user that the push succeeds, whether it does nor not.

The pop function

Example 4 The pop function

item_t pop(stack_t *st) {   st->top -= 1;     return( *(st->top) ); }

Please note that the pop function does not check for an empty stack. Logically, it is erroneous to pop a value from an empty stack. This function simply decrements the pointer st->top and returns whatever value is at that memory location. Since no check is made for an empty stack, the result can be to return the value at some memory location before the first element of the dynamically allocated array pointed to by st->base. This is a form of buffer overflow.

The main function calls the pop function before checking if the stack is empty. Checking the state of the stack before calling pop would be the correct behavior. Nothing in the main function prevents pop from being called when the stack is empty.

if( nextop == 'd' )      { int de_item;        getchar();        de_item = pop(st);        printf("  popped item %d", de_item);        if( stack_empty(st) )          printf(" the stack is now empty\n");        else          printf(" the top element is now %d\n",  top_element(st) );      }

If the pop function is called several times when the stack is empty the st->top pointer will continue to be decremented. If, after that the push function is called, the pushed value will be assigned to a memory location before the first element of the array, corrupting memory outside of the array.

The top_element function

A somewhat milder version of the problem with the pop function is present in the top_element function. This function returns the value of in the address one less than the current st-top pointer.

Example 5 The top_element function

item_t top_element(stack_t *st) {   return( *(st->top -1) ); }

As you can see, the top_element function does not check for an empty stack.

The stack_empty function

Example 6 The stack_empty function

int stack_empty(stack_t *st) {   return( st->base == st->top ); }

Note that this function will only return True when st->top points to the first element of the allocated array. It will return False when st->top points to any memory location before the beginning of the array. Since the function pop can move the pointer st->top to memory locations before the beginning of the array this function is highly unreliable.

Conclusions concerning ArrayStack.c

While this code may convey the general approach to implementing an array-based stack data structure, the actual implementation is faulty in many ways. All of the faults are associated with the primitive implementation of arrays in the C language. C arrays are simply a block of memory accessed by pointers. C provides no array bounds checking.

The code for this implementation may execute very efficiently, but it does no good when the code is executing erroneously.

Bounded_Stack

The Ada code for a bounded stack type is shown below. The following example implements a generic stack using an array with the size of the array determined at compile time.

Ada requires a package to implement both a specification, which is analogous to a C header file, and a body, which contains the implementation of the procedures and functions declared in the specification.

The file bounded_stack.ads

The file bounded_stack.ads contains the interface specification for a generic stack based upon an array.

generic    type Element_Type is private;    Default_Value : Element_Type; package Bounded_Stack is    type Stack(Size : Positive) is tagged private;    function Is_Empty(Item : Stack) return Boolean;    function Is_Full(Item : Stack) return Boolean;    procedure Push(Item : in out Stack; Value : in Element_Type) with      Pre => not Is_Full(Item),      Post => not Is_Empty(Item);    procedure Pop(Item : in out Stack; Value : out Element_Type) with      Pre => not Is_Empty(Item),      Post => not Is_Full(Item);    function Top(Item : in Stack) return Element_Type with      Pre => not Is_Empty(Item);    procedure Clear(Item : in out Stack) with      Post => Is_Empty(Item); private    type Buffer is array(Positive range <>) of Element_Type;    type Stack(Size : Positive) is tagged record       Buf   : Buffer(1..Size) := (Others => Default_Value);       Index : Positive := 1;       Count : Natural  := 0;    end record; end Bounded_Stack;

This is a generic package, as indicated by the reserved word “generic” at the start of the file. This package has two generic parameters; Element_Type, which designates any non-limited type, and Default_Value, which is used to initialize every instance of the stack with a properly define default value.

Declaring the type Stack to be private means that the details of the type are hidden from any calling subprogram or task. The subprogram declarations following the type declaration, and preceding the reserved word “private” are the only means given to manipulate the stack.

The procedure Push

Example 7 The procedure Push

procedure Push(Item : in out Stack; Value : in Element_Type) with      Pre => not Is_Full(Item),      Post => not Is_Empty(Item);

The declaration of the procedure Push contains a lot of information.

The parameter Item must be an instance of the type Stack. The parameter Item will be modified during the execution of the procedure Push. The parameter Value is an instance of Element_Type, and it will not be modified during execution of the procedure Push.

The procedure Push has a simple pre-condition, namely that the instance of Stack passed to this procedure cannot be full before calling Push.

The procedure Push has a simple post-condition, namely that the instance of Stack passed to the procedure Push will not be empty upon completion of the procedure Push.

The pre-condition and the post-condition are enforced by the compiler.

The procedure Pop

Example 8 The procedure Pop

procedure Pop(Item : in out Stack; Value : out Element_Type) with      Pre => not Is_Empty(Item),      Post => not Is_Full(Item);

The procedure Pop also contains a lot of information.

The parameter Item is an instance of Stack which will be modified during the execution of the procedure Pop.

The parameter Value is an instance of Element_Type which will be set during the execution of the procedure Pop.

The pre-condition for procedure Pop is that the instance of Stack passed to the procedure cannot be empty.

The post-condition for procedure Pop is that the instance of Stack passed to the procedure will not be full upon completion of the procedure Pop.

The function Top

The function Top returns the value of the stack top stack element without changing the stack itself.

Example 9 The function Top

function Top(Item : in Stack) return Element_Type with      Pre => not Is_Empty(Item);

The parameter Item is an instance of the type Stack which is not modified during execution of the function Top.

The pre-condition for the function Top is that the instance of Stack passed to the function cannot be empty.

The procedure Clear

The procedure clear empties a stack.

procedure Clear(Item : in out Stack) with      Post => Is_Empty(Item);

Clear modifies the instance of Stack passed to it.

The post-condition specifies that the instance of Stack will be empty upon completion of the procedure Clear.

The file Bounded_Stack.adb

The file Bounded_Stack.adb contains the implementation of all the functions and procedures declared in the package specification.

All the code within the package body contained in the file Bounded_Stack.adb has visibility to all the code in the file Bounded_Stack.ads.

package body Bounded_Stack is    --------------    -- Is_Empty --    --------------    function Is_Empty (Item : Stack) return Boolean is    begin       return Item.Count = 0;    end Is_Empty;    -------------    -- Is_Full --    -------------    function Is_Full (Item : Stack) return Boolean is    begin       return Item.Count = Item.Size;    end Is_Full;    ----------    -- Push --    ----------    procedure Push(Item : in out Stack; Value : in Element_Type) is    begin       Item.Buf(Item.Index) := Value;       Item.Index := Item.Index + 1;       Item.Count := Item.Count + 1;    end Push;    ---------    -- Pop --    ---------    procedure Pop (Item : in out Stack; Value : out Element_Type) is    begin       Value := Item.Top;       Item.Index := Item.Index - 1;       Item.Count := Item.Count - 1;    end Pop;    ---------    -- Top --    ---------    function Top (Item : in Stack) return Element_Type is    begin       return Item.Buf(Item.Index - 1);    end Top;    -----------    -- Clear --    -----------    procedure Clear(Item : in out Stack) is    begin       Item.Count := 0;       Item.Index := 1;    end Clear; end Bounded_Stack;

You may notice that the implementations of the functions and procedures in Bounded_Stack.adb are very simple. There is no explicit check for empty or full stack conditions. The pre-conditions specified in each procedure or function specification are implicitly checked by code generated by the compiler. The post-conditions specified for each procedure or function are implicitly checked by code generated by the compiler. Failure of any specified pre-condition or post-condition results in an exception which, if unhandled,  terminates the program.

The file main.adb

with Bounded_Stack; with Ada.Text_IO; use Ada.Text_IO; with Ada.Integer_Text_IO; use Ada.Integer_Text_IO; procedure Main is    package Int_Stack is new Bounded_Stack(Element_Type  => Integer,                                           Default_Value => 0);    use Int_Stack;    My_Stack : Stack(Size => 10);    Value : Integer; begin    while not My_Stack.Is_Full loop       Put("Enter an integer: ");       Get(Value);       My_Stack.Push(Value);    end loop;    Put_Line("Printing and popping the stack:");    while not My_Stack.Is_Empty loop       My_Stack.Pop(Value);       Put_Line(Integer'Image(Value));    end loop;    My_Stack.Pop(Value);    Put_Line(Integer'Image(Value)); end Main;

The output of this program is:

Enter an integer: 1 Enter an integer: 2 Enter an integer: 3 Enter an integer: 4 Enter an integer: 5 Enter an integer: 6 Enter an integer: 7 Enter an integer: 8 Enter an integer: 9 Enter an integer: 0 Printing and popping the stack:  0  9  8  7  6  5  4  3  2  1 raised SYSTEM.ASSERTIONS.ASSERT_FAILURE : failed precondition from bounded_stack.ads:12 instantiated at main.adb:6

The main procedure pops all the values off the stack then attempts to pop one more value off the stack. Rather than corrupting the stack pointer the program raises the exception SYSTEM.ASSERTIONS.ASSERT_FAILURE. The exception message points to the pre-condition for the pop procedure requiring the stack to be not empty.