Abstract datatypes

Motivation

Such contacts should include:

• the name of the type, so the client can refer to it
• the names of all primitive operations over elements of that type
• the conditions, under which these operations are applicable
• a precise specification of the (observable) behavior of those operations, when they are applicable

The contracts should not include:

• information about the actual representation of the type
• information about the actual implementation of the associated operations

Answer: The client of an ADT must know:

• everything he or she needs to know in order to use elements of the type
• nothing else (regarding the ADT :-)

Enforcing the rules:

• The best way of making sure the client doesn't take advantage of things he or she shouldn't take advantage of is to not tell him or her about it.
• Even better if we can avoid telling the compiler about those details, because this makes it impossible to take advantage of implementation details by accident.

ADTs in C

A familiar example

typedef struct {
	int	_cnt;
	unsigned char	*_ptr;
	unsigned char	*_base;
	int	_bufsiz;
	short	_flag;
	short	_file;

	char	*__newbase;
	void	*_lock;
	unsigned char	*_bufendp;
} FILE;

A better approach

Since C is not a type-safe language it will always be possible for the experienced hacker to get around such ``limitations''. The resulting programs frequently suffer from all the disadvantages of not playing by the rules (and then some), and the programmer deserves what he or she gets. Of course, passengers in airplanes controlled by such software might object to that...

That's a good question. But the answer is simple: Only the implementor of the ADT is permitted to dereference the pointer, because only he or she has the complete structure definition. Since the client's code cannot do anything useful with pointers to an incomplete structure except for passing them around, it is forced to use functions provided by the implementor. This way abstraction can be enforced.

Headers, clients, and implementations

The public header file istack.h contains the following definitions:

# ifndef ISTACK_H
# define ISTACK_H

typedef struct istack *istack;

/*
 * create a new empty stack of integers
 *   RETURN VALUE: NULL if allocation fails
 */
istack istack_new (void);

/*
 * push an integer onto an existing istack
 *  RETURN VALUE: 0 upon success
 *               -1 upon failure (to allocate enough memory)
 */
int istack_push (istack, int);

/*
 * Query the number of elements on a given istack.
 * This number is the total number of istack_push operations performed
 * minus the total number of istack_pop operations performed.
 */
int istack_height (istack);

/*
 * pop the topmost integer from an istack;
 *   caveat:
 *             istack_pop (s)
 *      can only be called if
 *             istack_height (s) > 0
 */
int istack_pop (istack);

/* Free all memory associated with this stack. */
void istack_delete (istack);

# endif

# include <stdio.h>
# include "istack.h"

int main (void)
{
  istack s = istack_new ();
  int i;

  if (s == NULL) {
    fputs ("Couldn't allocate stack\n", stderr);
    exit (1);
  }
  while (scanf ("%d", &i) == 1)
    if (istack_push (s, i) < 0) {
     fputs ("Out of memory\n", stderr);
     exit (1);
    }
  while (istack_height (s) > 0)
    printf ("%d\n", istack_pop (s));
  istack_delete (s);
  return 0;
}

For completeness, here is one possible realization of the istack ADT. File istack.c:

# include <stdlib.h>
# include <stdio.h>
# include "istack.h"

# define INCREMENT 64

struct istack {
  size_t total;
  size_t height;
  int *array;
};

istack istack_new (void)
{
  istack s = malloc (sizeof (struct istack));
  if (s == NULL)
    return NULL;
  s->total = 0;
  s->height = 0;
  s->array = NULL;
  return s;
}

/*
 * This is how realloc SHOULD work according to ANSI and ISO
 * standards for C.  Unfortunately, Sun's C libraries are not quite
 * up to that... :(
 */
static void *safe_realloc (void *x, size_t s)
{
  if (x == NULL)
    if (s == 0)
      return NULL;
    else
      return malloc (s);
  else if (s == 0) {
    free (x);
    return NULL;
  } else
    return realloc (x, s);
}

int istack_push (istack s, int i)
{
  if (s->height >= s->total) {
    int *a = safe_realloc (s->array, (s->total + INCREMENT) * sizeof (int));
    if (a == NULL)
      return -1;     /* couldn't allocate more space */
    s->array = a;
    s->total += INCREMENT;
  }
  s->array [s->height++] = i;
  return 0;          /* worked out ok */
}

int istack_height (istack s)
{
  return s->height;
}

int istack_pop (istack s)
{
  if (s->height > 0)
    return s->array [--s->height];
  else {
    fputs ("Fell off the end of the stack.\n", stderr);
    exit (2);
  }
}

void istack_delete (istack s)
{
  if (s->array != NULL)
    free (s->array);
  free (s);
}

CC = lcc
CFLAGS = -g

OBJECTS = reverse.o istack.o

reverse: $(OBJECTS)
	$(CC) -o reverse $(OBJECTS)

reverse.o: reverse.c istack.h
istack.o:  istack.c istack.h

Watch it!

# include "istack.h"

struct istack {
  size_t total;
  size_t height;
  int *array;
};

int main (void) {
  char buf [37];
  istack s = istack_new ();
  s->total = -23;
  s->height = 31415;
  s->array = buf;
  ...
}

# include "istack.h"

struct istack {
  float let;
  double us;
  struct istack *_break;
  int this;
  char code;
};

...

Specifications

Specifications can be divided into two parts: signatures and axioms.

Signatures

• the name of the type(s)
• names of operations over those type(s)
• the operation's argument and result types

Axioms

Axioms specify:

• conditions under which it is legal to invoke operations
• restrictions on the behavior of those operations

(A bad) Example

For those who are interested: The ANSI standard for C requires realloc to subsume the functionality of both malloc and free. In particular, when it is called as

        realloc (NULL, n)

then it must behave like

        malloc (n)

If you look at our code for istack_new and istack_push, then you will discover that we are taking advantage of this feature. However, since Sun's default realloc doesn't behave as it should, we had to ``roll our own''.

Testing

A more practical (but less convincing) way of ``proving'' one's implementation correct is to thoroughly test it. But beware! Testing itself is a non-trivial task. A good approach: Write a test program, the purpose of which is to exercise the ADT's implementation! Stress-test it!

Most people's code, if it breaks at all, breaks at boundary cases. For example, try the program with empty input and with very large input, with empty lines, and with very long lines. If it works for those cases (and for at least a few ``normal'' cases as well), then the odds are it was implemented correctly. Good test programs will work very hard not to miss any of the boundary cases.

Interactive testing

In the case of istack we could use something like this:

# include <stdio.h>
# include "istack.h"

static istack s = NULL;

static void no_stack (void) {
  fputs ("no stack\n", stdout);
}

static void delete (void)
{
  if (s) {
    istack_delete (s);
    s = NULL;
    fputs ("deleted\n", stdout);
  } else
    no_stack ();
}

static void new (void)
{
  if (s) {
    istack_delete (s);
    fputs ("old stack deleted\n", stdout);
  }
  s = istack_new ();
  if (s == NULL)
    fputs ("allocation failed\n", stdout);
  else
    fputs ("new stack\n", stdout);
}

static void height (void)
{
  if (s == NULL)
    no_stack ();
  else
    printf ("height: %d\n", istack_height (s));
}

static void huh (void)
{
  fputs ("huh?!\n", stdout);
}

static void add (char *num)
{
  int i;
  if (s == NULL)
    no_stack ();
  else if (sscanf (num, "%d", &i) != 1)
    huh ();
  else if (istack_push (s, i) < 0)
    fputs ("Couldn't push -- out of memory\n", stdout);
  else
    printf ("pushed %d\n", i);
  }
}

static void pop (void)
{
  if (s == NULL)
    no_stack ();
  else if (istack_height (s) <= 0)
    fputs ("empty stack\n", stdout);
  else
    printf ("popped: %d\n", istack_pop (s));
}

static void Pop (void)
{
  if (s == NULL)
    no_stack ();
  else
    printf ("popped: %d\n", istack_pop (s));
}

static void test (char *command)
{
  switch (*command) {
  case 'n': new (); break;            /* new stack */
  case 'd': delete (); break;         /* get rid of it */
  case 'h': height (); break;         /* print height */
  case 'a': add (command + 1); break; /* add (push) element */
  case 'p': pop (); break;            /* (safely) pop element */
  case 'P': Pop (); break;            /* (forcedly) pop element */
  default: huh (); break;             /* huh?! */
  }
}

# define LEN 32

int main (int argc, char **argv)
{
  char buf [LEN];
  int c;
  if (argc == 1) {
    while (fgets (buf, LEN, stdin) != NULL) {
      test (buf);
      if (buf [strlen (buf) - 1] != '\n')
        while ((c = getchar ()) != EOF && c != '\n')
          ;
    }
  } else {
    while (--argc)
      test (*++argv);
  }
  return 0;
}

CC = lcc
CFLAGS = -g

OBJECTS = reverse.o istack.o
TESTOBJ = istack-test.o istack.o

all: reverse istack-test

reverse: $(OBJECTS)
	$(CC) -o reverse $(OBJECTS)

istack-test: $(TESTOBJ)
	$(CC) -o istack-test $(TESTOBJ)

reverse.o: reverse.c istack.h
istack.o:  istack.c istack.h
istack-test.o: istack-test.c istack.h

n

new - make a brand new stack

d

delete - delete the current stack

h

height - show the height of the current stack

anum

add - push num onto the current stack

p

pop - check for empty stack and pop an element from the stack

P

Pop - don't check for empty stack and pop an element

Considering the simplicity of the ADT all this is probably overkill. But it gives you a flavor of what can be done, and what should be done in more interesting cases.