Polymorphism in Plain C

Here we go through the steps required to implement polymorphic interfaces in plain C. We use function pointers for this task, hidden behind generic functions we define for the interface itself.

To demonstrate the technique, we implement a simple queue of string pointers. This entry is about the generic interface so some deficiencies and possibly bugs in the actual implementation may pass us by. Please write the author or comment on the post if you spot errors in the implementation.

First we define the interface we’re going to use. We start off by defining a struct with the function pointers we need.

struct queue {

  void *secret;

  void (* enqueue)( struct queue *, char * );
  char * (*dequeue)( struct queue * );
  bool (*empty)( struct queue * );
  struct queue * (* delete)( struct queue * );
};

The void *secret is what we use in the implementation to keep track of our secret data structure. The rest are the function pointers we need to define for each implementation.

Here we use direct function pointers for all of the functions. We could also put the pointers into a separate struct for easier sharing, or at least smaller concrete objects, but we leave that optimization as an exercise for the dedicated reader.

The Interface

We define the functions we use for the interface. This is what client code will use to manipulate our queue.

char *Dequeue_String( struct queue *queue ) {
  return queue->dequeue( queue );
}

void Enqueue_String( struct queue *queue, char *string ) {
  return queue->enqueue( queue, string );
}

bool Empty_Queue( struct queue *queue ) {
  return queue->empty( queue );
}

struct queue *Delete_Queue( struct queue *queue ) {
  return queue->delete( queue );
}

All these functions do is to pass off the work to the implementation via the function pointers in the struct.

The Dequeue_String() function pops the string from the queue, and we make a note that since we’re storing copies of the strings we enqueue, we need to delete the returned string with free().

The Enqueue_String() function stories a copy of the string in the queue, via strdup() — this is important because users need to remember to free() it.

The Empty_Queue() function just returns the boolean value true if the queue is empty, and false otherwise.

The Delete_Queue deletes the queue and it’s entire contents, and returns a NULL pointer.

Each implementation is responsible for creating the appropriate constructor, which is just a function that returns a struct queue *, appropriately named Make_Something_Or_Other.

The Implementation

The implementation we create here is just a linked list of char * pointers. We start off with the actual node, then a secret structure for the head and tail.

struct queue_node {
  char *string;
  struct queue_node *next;
};

struct queue_secret {
  struct queue_node *head, *tail;
};

We pop from the head of the list, with the following function.

char *queue_pop_head( struct queue *queue ) {
  struct queue_secret *secret = queue->secret;

We start by getting hold of the actual secret structure.

  struct queue_node *head = secret->head;

Then the head of the list, which is a dummy,

  struct queue_node *item = head->next;

and then the actual first item in our list.

  if ( item ) {
    head->next = item->next;
    char *string = item->string;
    free( item );

If the item is valid, we link to the next item, grab the string pointer, and free our old item. Notice that we do not free the string pointer itself — that’s for the client code to do.

    if ( ! head->next )
      secret->tail = head;

We also check for the special case of the empty list, and reset our tail in that case.

    return string;

And return the string.

  } else return 0;    
}

If there’s nothing in our queue, we just return a NULL pointer.

We push at the end of the list with the following function.

void queue_push_tail( struct queue *queue, char *string ) {
  struct queue_secret *secret = queue->secret;

We start by getting hold of the secret.

  struct queue_node *tail = secret->tail;

Then the actual tail of the list.

  struct queue_node *new = malloc( sizeof ( struct queue_node ) );
  new->string = strdup( string );
  new->next = 0;

We create a new item for our list, and initialize it with a duplicate of the string argument.

  tail->next = new;
  secret->tail = new;
}

And append it to the tail of the list, updating both the final pointer and the special tail pointer.

To test if the list is empty, we just check if the head->next is zero.

bool queue_empty( struct queue *queue ) {
  struct queue_secret *secret = queue->secret;

  return secret->head->next == 0;
}

To delete the queue we simply loop while it’s not empty and free the resulting pointer; making use of the functions we’ve defined earlier.

struct queue *queue_delete( struct queue *queue ) {

  while ( !queue_empty( queue ) ) {
    char *string = queue_pop_head( queue );
    free( string );
  }

  return 0;
}

For our constructor, we define a special function.

struct queue *Make_LinkListQueue( void ) {
  struct queue *queue = malloc( sizeof ( struct queue ) );

We start by allocating the queue structure.

  struct queue_secret *secret = malloc( sizeof ( struct queue_secret ) );

And then our secret;

  struct queue_node *sentinel = malloc( sizeof ( struct queue_node ) );

and finally the sentinel, or guard item we put at the head of the list.

  sentinel->string = 0;
  sentinel->next = 0;

And initialize the sentinel to zero pointers.

  secret->head = sentinel;
  secret->tail = sentinel;

Set the secret to point to the sentinel.

  queue->secret = secret;

And set the queue’s secrete to be our secret pointer.

  queue->enqueue = queue_push_tail;
  queue->dequeue = queue_pop_head;
  queue->empty = queue_empty;
  queue->delete = queue_delete;

And initialize all the function pointers.

  return queue;
}

And finally return the queue object we just constructed.

The Client

After somewhat messy code in the implementation, the client code is surprisingly simple.

We start by making our queue.

struct queue *queue = Make_LinkListQueue();

Side note: the struct queue *queue may seem like a syntax error, but it’s actually how C works.

Then we add something to the queue with

Enqueue_String( queue, "word" );

And delete from it with

char *string = Dequeue_String( queue );
free( string );

And delete the queue with

queue = Delete_Queue( queue );

Final Words

This has been a short introduction into polymorphism and object oriented programming with plain old C. For those interested in the subject, Object-oriented Programming in ANSI-C (pdf) by Axel Schreiner covers a lot more ground.

It is unfortunate that WordPress doesn’t differentiate between C and C++ tags and categories, because this post is about plain old C.

Happy C coding!

Leave a Reply

This site uses Akismet to reduce spam. Learn how your comment data is processed.

%d bloggers like this: