3.1 Arrays
The simplest way to implement our collection is to use an array to hold the
items.
Thus the implementation of the collection object becomes:
/* Array implementation of a collection */
#include <assert.h> /* Needed for assertions */
#include "collection.h" /* import the specification */
struct t_collection {
int item_cnt;
int max_cnt; /* Not strictly necessary */
int item_size; /* Needed by FindInCollection */
void *items[];
};
Points to note:
- We have imported the specification of this object into the implementaton -
this enables the compiler to verify that the implementation and the
specification match. Although it's not necessary to include the specification
(cf function prototypes),
it is much safer to do so as it enables the compiler
to detect some common errors and ensures that the specification and its
implementation remain consistent when the object is changed.
- items
is typed as an array of void * in the struct.
It is an array of item's which happen to be pointers - but remember
that we are trying to hide this from users of the class. Many C programmers
would write the equivalent void ** here.
A question:
- Why is the attribute max_cnt not strictly necessary?
Hint: it's related to the pre- and post-conditions specified
for methods on this object.
The implementations of the methods are:
Select here to load collection.c
Points to note:
- ConsCollection uses
the memory allocator
calloc to
dynamically allocate memory off the program's heap for the collection.
Two calls are necessary -
one to allocate space for the "header" structure itself
and one to allocate space for the array of item pointers.
- assert calls have been added for the pre-conditions (cf full
description of
assert). Note that the pre-conditions here are
expressed as a number of conditions linked by &&. Since assert
requires a single boolean expression as its argument, one assert would
suffice. However, we have chosen to implement each individual condition as a
separate assert. This is done to assist de-bugging: if the
pre-conditions are not satisfied, it is more helpful to know which one of
multiple conditions has not been satisfied!
- memcmp is a standard function which compares blocks of memory byte
by byte [man page for memcmp].
- The use of memcp and
ItemKey severely constrain the
form of the key - it must be in a contiguous string of characters
in the item. There are ways of providing more flexible keys
(eg ones having multiple fields within item or
ones calculated from item.
These rely on C capabilities which will be discussed in a later section.
- There is no treatment of errors, e.g. if no memory is available on
the heap for calloc.
This is a serious shortcoming.
No software without a consistent strategy for detecting, reporting and
recovering from errors can be considered well engineered. It is difficult to
debug, prone to crashes from faults which are difficult to correct because
there is no indication of the source of the error.
Error handling is addressed in a
later section.