Abstract Data Types

As we increase the size of our programs, we run the risk of making our programs too complex to understand. Consider a program that is broken up into eight components. Imagine if there were no restrictions on how these components interacted. In the worst case, every component could interact with every other component.

Now, imagine that a bug is found in, say, component 5. Trying to uncover the cause of the bug may require investigating how this component interacts with other components in the system. In this maximally connected case, we have to see how component 5 interacts with the other seven components of the system. Clearly such a situation is not ideal, especially if there were additional components, say hundreds of them!

But this situation can become worse. Suppose the bug is particularly tricky, and we have to investigate not just how component 5 interacts with every other component, but also how every component interacts with each component that interacts with component 5. That is a bit of a mouthful, but what we mean is that maybe the interactions of any triple of components is the issue. In other words, we have to examine how:

• Components 5, 1, and 2,
• Components 5, 1, and 3,
• Components 5, 1, and 4,
• Components 5, 1, and 6,
• Components 5, 1, and 7,
• Components 5, 2, and 3, …

… and so forth all interact to find the bug!

Maybe any combination of components that could interact together in the system can cause the bug. In the worst case, we would need to examine all of these combinations to unearth the problem, an exponential number of possibilities in all. Consequently, to build large software artifacts that we have some hope of reasoning about, we need to limit these interactions between components in our system to the bare essentials.

What is an Abstract Data Type?

One of the key tools in our arsenal to limit unnecessary interaction between software components is abstraction. By abstraction, we mean that we:

• Expose the essential parts of a software component required to interact with others and
• Hide all the inessential parts.

This approach to building software helps minimize the surface area of the component we’re writing, minimizing the ways it can interact with other components, thus reducing the complexity of our programs.

When our software components are best realized as types in our programs, this abstraction takes the form of abstract data types (ADTs). We break up our component into two parts:

• An public interface that defines the ways that our program can interact with this type, i.e., what functions are available to create, use, and delete values of this type.
• A private implementation of the interface functions, hidden from the outside world.

A Simple Example: A Counter

Let’s examine a simple abstract data type to see this concept in action. Consider a humble counter that keeps track of an ever-increasing value. First, what operations should our counter ADT expose to the outside world? Keeping in mind our mantra of “creation-use-deletion” for types, we need to consider exposing functions for each of these categories. To keep things simple, we’ll assume that our counter is only stack-allocated, so we’ll have no need to consider the “deletion” category yet.

“Using” a counter amounts to two behaviors: incrementing the counter and fetching its current value. Combining these two behaviors with the need to make a counter in the first place yields three function signatures:

// Initialize a counter with value 0
void counter_init(counter_t* c);

// Increment counter c by 1
void counter_increment(counter_t* c);

// Retrive the value of counter c
int counter_get_value(const counter_t* c);

These three functions form the interface to our counter ADT. Note that we have not defined what the counter type is or how these functions are implemented. The point of the ADT is to separate interface from implementation so that we can expose the former and hide the latter.

Nevertheless, we need to actually provide an implementation, so let’s do so. Critically, our choice of what the counter type is will guide our implementation of the interface. The simplest counter is simply an int, so let’s go with that and see how everything pans out:

typedef struct {
  int value;
} counter_t;

void counter_init(counter_t* c) {
  c->value = 0;
}

void counter_increment(counter_t* c) {
  c->value++;
}

int counter_get_value(const counter_t* c) {
  return c->value;
}

Great! We have provided an implementation of our counter ADT. Presumably, all of this code sits in a single file, so we really haven’t “hidden” anything from everyone. Next, let’s see how we can organize our C programs to effectively hide implementations and expose interfaces to other parts of our program.

Organizing C Programs around ADTs

Some programming languages provide strong support for abstractions like ADTs, e.g., classes in object-oriented languages. C does not provide such support. This is largely because C predates languages with these features, but they also sometimes come with a performance cost that would not fit well in the low-level contexts where C is used.

Instead, C programs are organized in a particular way to achieve this effect of hiding implementation and exposing interface through the compilation process. This organization is not enforced by C, per se; it is simply a convention that all C programmers follow.

We break up an ADT like our counter into two files:

• A header file (named with a .h suffix) that contains information about the interface to this ADT.
• An implementation file (named with a .c suffix) that contains an appropriate implementation of this interface.

Applying this design pattern to our counter example, we create the two files below.

Header file counter.h:

#pragma once

typedef struct {
  int value;
} counter_t;

void counter_init(counter_t* c);

void counter_increment(counter_t* c);

int counter_get_value(const counter_t* c);

The only line in this file that should be surprising is #pragma once, which just tells the C compiler not to include this file’s content more than once when compiling a .c file. This is something you’ll see at the top of every .h file you write, and we’ll learn a bit more about why this is necessary when we discuss multi-file projects later in the semester.

There is an older method of accomplishing the same thing called include guards:

#ifndef COUNTER_H
#define COUNTER_H

...

# endif

This does the same thing as #pragma once, although it requires more typing and can introduce errors if you forget to rename the defined constant in each header file. You should use #pragma once rather than include guards for this course, since this feature is now part of the C standard.

Implementation file counter.c:

#include "counter.h"

void counter_init(counter_t* c) {
  c->value = 0;
}

void counter_increment(counter_t* c) {
  c->value++;
}

int counter_get_value(const counter_t* c) {
  return c->value;
}

Observe how we link the header and implementation files together. The #include pre-processor directive copies the contents of a file (more or less) verbatim into the #include’s position in the file. Thus, counter.c stays consistent with counter.h by virtue of literal copying-pasting of the latter into the former during compilation.

To use our counter type, say for example, in our main program, we would have a separate file for main, call it main.c. We would then #include the header file in main. That allows us to use the counter type we’ve written in counter.h and counter.c:

The main source file main.c:

#include "counter.h"

int main(void) {
  // Create an initialize a counter
  counter_t c;
  counter_init(&c);

  // Show the counter's initial value
  printf("Counter is initially %d\n", counter_get_value(&c));

  // Incremen tthe counter three times
  counter_increment(&c);
  counter_increment(&c);
  counter_increment(&c);

  // Show the counter's final value
  printf("Counter is now %d\n", counter_get_value(&c));

  return 0; 
}

Finally, when we go to compile our program, we need to include both compilation units in our clang invocation:

$> clang -o prog main.c counter.c
$> ./prog
Counter is initially 0
Counter is now 3

Notice that main.c and counter.c appear in the shell command above, but counter.h is not included. This is intentional; we will never list .h files in our compile commands, only .c files. The .h files are incorporated into the code through #include statements and cannot be compiled directly.

Sequences ADTs

Abstract data types can be used to capture many kinds of data. For example, the FILE* type exposed in stdio.h is an ADT over a stream of data that could be drawn from, e.g., a file on disk, the user’s keyboard, or their screen. However, ADTs are commonly used to capture classes of data structures, data that is responsible for organizing and storing other data. There are four broad classes of such data structures, defined by the relationships they encode between the data they store:

• Sequences capture sequential relationships between data.
• Trees capture hierarchical relationships between data.
• Maps capture function-like relationships between data.
• Graphs capture arbitrary relationships between data.

The study of these structures is the primary topic for CSC 207. But of these, sequences are most common and prevalent in programming, so it is worth our time to explore them in detail now.

There are many variations on sequences that come up in program design, but we’ll focus on three in this reading: stacks, queues, and lists. All three of these sequence ADTs will keep track of values in some order (that’s what makes them sequences), but each one exposes a different interface.

Recently, we learned how to allocate arrays with malloc, and to grow and shrink them with realloc. We can use dynamic arrays to implement all three of the sequence ADTs above, but a user of these ADTs would not need to know about the underlying implementation to use them safely. Soon, we will learn about linked lists, another way to store sequences that could also serve as the underlying implementation for our sequence ADTs. Implementing these ADTs will be part of our lab today, but first we will look at their interfaces.

The Stack ADT

A stack is a sequence of values where all accesses occur at one end of the sequence called the top of the stack. you can think of a stack like a pile of values where only the value at the top of the pile is accessible. We add values by pushing them onto the stack. Each pushed value sits at the new top of the stack. We remove a value by popping it from the top of the stack. A stack ADT might include additional functions to peek at the top of the stack, or to check if the stack is empty.

You will sometimes see stacks referred to as “last in, first out” (LIFO) data structures. Note that we sometimes talk about “the stack” (as opposed to “a stack”). When we say “the stack” (or “the program stack”), we are referring specifically to a region of memory the program uses to store local variables and implement function calls. The program stack does in fact work like a stack ADT, but your code doesn’t interact with it directly the same way it would use a stack that you implement yourself.

A stack that holds strings would have an interface like this:

// Initialize an empty stack of strings
void string_stack_init(string_stack_t* s);

// Destroy a stack that holds strings
void string_stack_destroy(string_stack_t* s);

// Push a string to the top of the stack
void string_stack_push(string_stack_t* s, char* str);

// Pop a string from the top of the stack and return it
char* string_stack_pop(string_stack_t* s);

// Get the string on the top of the stack, but do not remove it from the stack
char* string_stack_peek(const string_stack_t* s);

Notice that we’ve also added a destroy function, which any user of the stack should use to clean up memory allocated to hold the stack. This will be a common feature across all ADTs that could allocate memory.

The Queue ADT

A queue is another sequence ADT, but unlike a stack it allows interaction at both ends of the sequence. Specifically, we add values to a queue at one end of the sequence and take them from the queue at the other end. The first value we add will be the first one we take from the queue, regardless of how many values we add after the first. Because of this, a queue is sometimes called a “first in, first out” (FIFO) data structure.

The names for operations on queues are less consistent than “push” and “pop” for stacks. For example, the operation that adds values to a queue could be called “add”, “enqueue”, or “put”. The operation that takes values out of the queue might be called “take”, “dequeue”, or “remove”.

A queue that holds strings would have an interface like this:

// Initialize an empty queue of strings
void string_queue_init(string_queue_t* q);

// Destroy a queue that holds strings
void string_queue_destroy(string_queue_t* q);

// Add a string to the back of the queue
void string_queue_add(string_queue_t* q, char* str);

// Take a string from the front of the queue and return it
char* string_queue_take(string_queue_t* q);

// Get the string at the front of the queue, but do not remove it
char* string_queue_peek(const string_queue_t* q);

The List ADT

A third sequeunce ADT you will frequently use or encounter is the list ADT. A list ADT would allow more operations than a stack or queue; we might allow a user to append to a list, access a value at a particular index, insert a value at a particular index, and more. You’ll see many variations on list ADTs, including some that might include both stack and queue operations on the list.

Let’s build up a potential interface for the list ADT. First, we’ll need a way to initialize a list before we use it, and to destroy a list when we are done with it:

// Initialize an empty list of strings
void string_list_init(string_list_t* lst);

// Destroy a list that holds strings
void string_list_destroy(string_list_t* lst);

Next, it would be helpful to know how long the list is so we’ll add a function to get the length:

// Get the current length of a list of strings
int string_list_length(const string_list_t* lst);

Notice that lst is a const parameter. This ensures that our implementation will not be able to modify the list, and signals to a user of this interface that the list is not changed when you call this function.

We’ll also need to let users interact with the strings stored in the list. For this example, we’ll allow the user to get a string at a particular index, insert a new string at an index, and remove the string at a particular index:

// Get a string from a list at a given index
char* string_list_get(const string_list_t* lst, int index);

// Insert a string to a list at a given index
char* string_list_insert(string_list_t* lst, int index, char* value);

// Remove a string from a list at a given index
void string_list_remove(string_list_t* lst, int index);

The list ADT likely has the most variations of the three sequence ADTs we’ve discussed, since there are many other possible operations that a particular list ADT could provide. But for all of these variations, the idea of a list is still familiar. That idea of familiarity is key; when we use stacks, queues, or lists in our programs we make it easier for anyone reading our code to understand what we are doing. Using these ADTs also makes it easier to implement these data structures because we generally only need to think about is the interface the ADT exposes, not all the ways the ADT could be used.