7. ADTs

An important aspect of abstract data types or ADTs in C is how the storage for instances is allocated. There are two main ways, plus an uncommon third:

internal allocation

The ADT allocates all its own storage, typically with malloc() and free(). This means that the ADT's public header file does not have to define the structure behind it, for better information hiding.

external allocation

Code using the ADT is responsible for allocating and freeing storage for the ADT structure itself, although not for any storage allocated indirectly through the structure. This way, instances of the ADT can be kept in automatic memory, instead of having to be stored in dynamic memory.

hybrid

Some ADTs can be allocated either way, but this is rarely seen.

An ADT with internal allocation is more "heavyweight" than an ADT with external allocation, because calls to malloc() and free() tend to be relatively expensive in time. Externally allocated ADTs are more general, because they can always be transformed into internal ADTs with wrapper functions, but the reverse is not true.

Suppose that the ADT is defined as struct adt. The standard functions to define to manipulate this ADT are listed below. Note that many of these functions should take additional arguments not shown:

void adt_init (struct adt *this); (externally allocated)

void adt_destroy (struct adt *this); (externally allocated)

Initialize or destroy an instance of an externally allocated ADT. If adt_init() can fail, then it returns a Boolean value, nonzero for success.

struct adt *adt_new (void); (internally allocated)

void adt_discard (struct adt *this); (internally allocated)

Create or destroy a new instance of an internally allocated ADT. If adt_new() fails, it returns a null pointer.

struct adt *adt_open (resource_t); (internally allocated)

int adt_open (struct adt *this, resource_t); (externally allocated)

Initializes an ADT instance from a specified external resource, such as a file, of type resource_t. Combines adt_init() with a function to access a resource.

struct adt *adt_copy (const struct adt *src); (internally allocated)

int adt_copy (struct adt *this, const struct adt *src); (externally allocated)

Makes a copy of src. The new instance of the ADT is initialized before the copy.

For ADTs where shallow and deep copies are different operations, adt_copy() performs a shallow copy. The corresponding deep copy operation is adt_clone().

item_t adt_get (struct adt *this);

void adt_put (struct adt *this, item_t);

Functions for storage and retrieval of items of type item_t within the ADT.

Additional points:

opacity

The structure for an ADT is opaque, that is, even if it is declared in a public header file, its members should not be accessed directly by user code. Rather, access them through accessor functions or well-behaved function-like macros, which should be provided wherever relevant.

this pointer

The first parameter to an ADT function should be a pointer to an instance of the ADT. Its name in the function definition should be this.

allocation

If an ADT allocates memory with malloc() and it is intended for use outside the program it is originally written for, then there should be a way to substitute another allocator.

(More specific recommendations are not given here because I have not figured out a really good way to do this yet.)