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.
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);
}
|
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 and what seems to be a cultural tendency for C programmers to avoid dealing with error conditions. C arrays are simply a block of
memory accessed by pointers. C provides no array bounds checking. Failing to specify error conditions is inexcusable, as is failing to evaluate return values of functions that do check for error conditions.
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 procedure 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.
No comments:
Post a Comment