Opaque pointers

One of the most powerful concepts when writing software is abstraction - hiding the details of a system behind a simpler interface. This article shows you how to use a language feature of C (and C++) to provide a very powerful form of abstraction for use in libraries: opaque pointers.

C/C++ has an interesting language feature. If you declare a typedef of a structure pointer, you don't need to provide that structure's definition. For example:

typedef struct _hidden_struct *handle;

This has declared a new type, handle, which is a pointer to a struct _hidden_struct. What's interesting about this? Mainly the fact that you can now use this handle type without ever having a definition of the structure it's a pointer to. Why is this powerful? That's what this article will show you (some people might already see why). Please note that the typedef above (and those used throught this article) aren't strictly needed to hide the structure's internal definition - you can just keep using the struct keyword as part of the name. However, the typedefs are used to make an abstraction away from the fact that there's a structure at all, instead of turning it into a "handle."
Sample problem

To really see the power of opaque pointers, we'll need a problem to solve. Let's suppose we want to make an image library that loads and saves bitmaps. We know that as time goes on this library will need to be able to do more things (new image types, basic transforms) and we want to preserve both compile time and runtime compatibility for this library. This means that if we have an older application, it should work with a new shared library and that if that older application is rebuilt against the new library and headers, it should still build without errors.
What about C++?

Before this goes much further, I need to address the waving hands of all the C++ fans out there, who might be thinking: "C++ already lets me do all of this behind a nice class interface with inheritance and other nice C++ language features". And this is pretty much true in the case of compile-time compatibility. But, because C++ doesn't let you separate the public and private definitions of a class, the way the class is declared changes its runtime behavior (class size, vtable offsets, etc.) - you can't provide runtime compatibility without a lot of tender care (and sometimes special compilers). So, this is still useful to C++ people, even if the slant is more towards those of us using C.

Okay, back to the library. When people design libraries like this, they'll often declare a structure that will get filled in by the library and an API for manipulating this structure. For example:

typedef struct

{

void *ptr;

int sz;

int bytes_per_pixel;

} bitmap_t;

int bitmap_load_file( char *filename, bitmap_t *bitmap );

int bitmap_save_file( char *filename, bitmap_t *bitmap );

So, to use this library, you would declare a bitmap_t variable and invoke bitmap_load_file() with a filename and a pointer to the bitmap_t that was declared. For example:

bitmap_t bitmap;

int ret;

ret = bitmap_load_file( "sample.bmp", &bitmap );

Then the user of the library could simply access the pointer inside the structure and, along with the size and bytes_per_pixel members, go to work on the image. However, because the contents of bitmap_t are known publicly, if the library is updated with new entries in that structure, then the size of the structure will have been changed. And applications that use an updated shared library will probably crash or Other Bad Things when they call into the new library with a structure of a smaller (different) size.

Alternatively, the API could be defined to take a structure size:

int bitmap_load_file( char *filename, bitmap_t *bitmap, int s );

int bitmap_save_file( char *filename, bitmap_t *bitmap, int s );

and would be used like this:

ret = bitmap_load_file( "sample.bmp", &bitmap, sizeof( bitmap_t ) );

Which effectively tags the version of the library by using the size of the structure. However, this makes for a terrible support nightmare inside the library where the structure size has to be checked and different code paths are taken based on this structure size. This leads to a lot of code bloat.

We could also try to avoid the structure size issue by padding the structure with some "reserved" space:

typedef struct

{
void *ptr;
int sz;
int bytes_per_pixel;
char reserved[64];
} bitmap_t;

But this is only a temporary fix. What if we didn't choose a value that's large enough? Then we're back to the case where a new library causes problems. If we're liberal with our reserved space, then we waste memory.

Another problem common to all of these approaches is what can occur if the layout of the structure changes. Say a new version of the library is built with a structure definition that looks like this:

typedef struct

{
int version;
void *ptr;
int sz;
int bytes_per_pixel;
} bitmap_t;

Then the compiled apps will also get "confused", since what was previously the structure member ptr is now version, and so on. The position of a structure member within a structure is important. Seems pretty much impossible to meet our goals, huh? Fear not, loyal readers, the situation isn't that dire!
Hiding the structure's internals

The common thread to all the situations above was that the compiled application was aware of the size of the structure and the location in the structure of the structure members. So we need to hide the internals of the structure and provide access functions to get the important data out of the structure.

Let's try out a new public interface:

typedef struct _internal_bitmap * bitmap_t;
int bitmap_alloc( bitmap_t *bitmap );
int bitmap_free( bitmap_t *bitmap );
int bitmap_load_file( bitmap_t bitmap, char *filename );
int bitmap_save_file( bitmap_t bitmap, char *filename );
int bitmap_get_ptr( bitmap_t bitmap, void **ptr );
int bitmap_get_size( bitmap_t bitmap, int *size );
int bitmap_get_bpp( bitmap_t bitmap, int *bpp );

And now we can maintain a private interface that applications never get to see or use, only the library:

struct _internal_bitmap
{
void *ptr;
int sz;
int bytes_per_pixel;
}

Did you notice the opaque pointer? Also, notice we've added "access functions" to get the interesting data from the new bitmap "handle"? It's pretty obvious now that we're passing in a bitmap_t (a structure pointer) as a handle to the library, but the alloc and free functions are a little confusing for people.

When we declare a bitmap_t, we're really just declaring a pointer to a structure, so we need to provide some memory for that pointer to point at. Here are the guts of the bitmap_alloc() function:

int bitmap_alloc( bitmap_t *bitmap )
{
struct _internal_bitmap *handle;
handle = ( struct _internal_bitmap * )malloc( sizeof( *handle ) );
if( handle == NULL )
{
return -1;
}

memset( handle, 0, sizeof( *handle ) );
*bitmap = handle;
return 0;
}

Since a bitmap_t is just a struct pointer, we allocate the proper sized struct (which we can do - this code is part of the library and it knows how big the structure is). Once we've verified that the malloc() didn't fail, we assign the newly allocated structure to the bitmap_t pointer. So when the application calls this function, it will get back the proper sized structure to pass into the rest of the library functions.

Here's an example of an "access function" that uses the allocated bitmap handle:

int bitmap_get_ptr( bitmap_t bitmap, void **ptr )
{
if( ptr == NULL )
{
return -1;
}
*ptr = bitmap->ptr;
return 0;
}

Since the library knows the definition of the _internal_bitmap structure, it can directly access its members. If you tried to access the internals of the bitmap_t handle in application code, the compiler would return an error, because it has no idea how the structure is organized or what any of its members are named.

For the last bit of code, I'll write a function that loads a bitmap, sets all the pixels to 255, and writes the bitmap back:

int turn_bitmap_white( char *filename )
{
int ret, i;
bitmap_t bitmap;
unsigned char *ptr;
int sz;
ret = bitmap_alloc( &bitmap );
if( ret )
return ret;
ret = bitmap_load_file( bitmap, filename );
if( ret )
return ret;
ret = bitmap_get_ptr( bitmap, (void **)&ptr );
ret |= bitmap_get_size( bitmap, &sz );
if( ret )
return ret;
for (i = 0; i < sz; ++i)
{
 bitmap_save_file(bitmap,filename );
}

Problem solved

So, we've solved our problem. If we change the structure layout, we'll be okay, since the application code can't access the internals of the structure directly and must use "access functions" to get at the internal data.

If we change the size of the structure, we'll be okay, since the library itself allocates the memory for the structure and knows the proper size of the structure to allocate for the given version of the library. You can now replace the library (in shared library form) without having to rebuild any applications. And you can rebuild applications against the library without change. Now, this does assume that you haven't changed the API to your library - opaque pointers are a powerful tool, but they can't perform magic.

Lastly, the use of opaque pointers enforces good programming practice by providing a defined interface (abstraction) between the application and the library. This is usually a good method even when doing your own projects, since it lets you easily separate functionality for future projects!

Just to splay a tree.

I was looking for something different from a RBTree for implementing a queue request indexed by an integer, with a lot of accesses. It's valueable to consider a simple O(n) queue, because the items are scarsely popped out.
A Splay Tree fits well in this case. Not so much code.

#ifndef SPLAY_TREE_H
#define SPLAY_TREE_H 1

#include <stdlib.h>

typedef struct tree_node Tree;

struct tree_node {
    Tree * left, * right;
    int item;
    void* data;
};

struct tree_node* searchSplay(int value, struct tree_node* n)
{
 if (n == NULL)
  return NULL;

 if (value > n->item)
  return search(value, n->left);
 else if (value < n->item)
  return search(value, n->right);
 else
  return n;

 return NULL;
}
Tree * splay (int i, Tree * t) {
/* Simple top down splay, not requiring i to be in the tree t.  */
/* What it does is described above.                             */
    Tree N, *l, *r, *y;
    if (t == NULL) return t;
    N.left = N.right = NULL;
    l = r = &N;

    for (;;) {
 if (i < t->item) {
     if (t->left == NULL) break;
     if (i < t->left->item) {
  y = t->left;                           /* rotate right */
  t->left = y->right;
  y->right = t;
  t = y;
  if (t->left == NULL) break;
     }
     r->left = t;                               /* link right */
     r = t;
     t = t->left;
 } else if (i > t->item) {
     if (t->right == NULL) break;
     if (i > t->right->item) {
  y = t->right;                          /* rotate left */
  t->right = y->left;
  y->left = t;
  t = y;
  if (t->right == NULL) break;
     }
     l->right = t;                              /* link left */
     l = t;
     t = t->right;
 } else {
     break;
 }
    }
    l->right = t->left;                                /* assemble */
    r->left = t->right;
    t->left = N.right;
    t->right = N.left;
    return t;
}

Tree * insertSplay(int i, void* data, Tree * t) {
/* Insert i into the tree t, unless it's already there.    */
/* Return a pointer to the resulting tree.                 */
    Tree * new;

    new = (Tree *) malloc (sizeof (Tree));
    if (new == NULL) {
     printf("Ran out of space\n");
     exit(1);
    }
    new->item = i;
    new->data = data;
    if (t == NULL) {
     new->left = new->right = NULL;
     size = 1;
     return new;
    }
    t = splay(i,t);
    if (i < t->item) {
 new->left = t->left;
 new->right = t;
 t->left = NULL;
 size ++;
 return new;
    } else if (i > t->item) {
 new->right = t->right;
 new->left = t;
 t->right = NULL;
 return new;
    } else { /* We get here if it's already in the tree */
             /* Don't add it again                      */
 free(new);
 return t;
    }
}

Tree * deleteSplay(int i, Tree * t) {
/* Deletes i from the tree if it's there.               */
/* Return a pointer to the resulting tree.              */
    Tree * x;
    if (t==NULL) return NULL;
    t = splay(i,t);
    if (i == t->item) {               /* found it */
 if (t->left == NULL) {
     x = t->right;
 } else {
     x = splay(i, t->left);
     x->right = t->right;
 }
 free(t);
 return x;
    }
    return t;                         /* It wasn't there */
}
#endif

Just a simple Red Black Tree in C

This is our current RB implementation. It's C but it likes more C++.
Enjoy :)

 --- file treemap.h ---  
 #ifndef TREE_MAP  
 #define TREE_MAP  
 #include <ctype.h>  
 #include <stdlib.h>  
 #include <pthread.h>  
 typedef struct t_node  
 {  
  enum  
  { RED = 0, BLACK } colour;  
  void *key;  
  void *value;  
  struct t_node *left;  
  struct t_node *right;  
  struct t_node *parent;  
 } Node;  
 typedef struct  
 {  
  Node *rootNode;  
  Node *nil;  
  pthread_mutex_t big_lock;  
  int (*cmp) (void *item1, void *item2);  
  Node *(*clone) (void *key, void *item);  
  void (*delete) (Node ** item);  
 } TreeMap;  
 #define RED_COLOR 0  
 #define BLACK_COLOR 1  
 #define IS_EMPTY_ROOT(root)((root)->rootNode == NULL)  
 #define color(r)  ((r)->colour &amp; 1)  
 #define is_red(r)  (!color(r))  
 #define is_black(r) color(r)  
 #define set_black(r) r->colour = 1;  
 #define set_red(r) r->colour = 0;  
 TreeMap *new_tree_map (Node * (*clone) (void *key, void *data),  
        int (*cmp) (void *k1, void *k2),  
        void (*delete) (Node ** item));  
 Node *searchKey (TreeMap * t, void *key);  
 void insertKey (TreeMap * t, void *key, void *value);  
 Node *updateKey (TreeMap * t, void *key, void *value);  
 Node *eraseKey (TreeMap * t, void *key);  
 void destroyKey (TreeMap * t, void *key);  
 int eraseNode (TreeMap * t, Node * n);  
 void destroy_tree_map (TreeMap * t);  
 void replaceKey (TreeMap * t, void *key, void *newKey);  
 #endif  
 ----- file treemap.c -----  
 #include <treemap.h>  
 #include <stdlib.h>  
 #include <ctype.h>  
 #include <string.h>  
 #include <stdio.h>  
 #include <assert.h>  
 TreeMap *  
 new_tree_map (Node * (*clone) (void *key, void *data),  
      int (*cmp) (void *key1, void *key2),  
      void (*delete) (Node ** item))  
 {  
  TreeMap *t = calloc (1, sizeof (TreeMap));  
  t->nil = calloc (1, sizeof (Node));  
  t->nil->left = t->nil->right = t->nil->parent = t->nil;  
  t->nil->colour = BLACK;  
  t->nil->key = NULL;  
  t->nil->value = NULL;  
  t->rootNode = calloc (1, sizeof (Node));  /*allocate sentinel */  
  t->rootNode->left = t->rootNode->right = t->rootNode->parent = t->nil;  
  t->rootNode->key = NULL;  
  t->rootNode->value = NULL;  
  t->rootNode->colour = BLACK;  /*sentinel is black */  
  t->clone = clone;  
  t->cmp = cmp;  
  t->delete = delete;  
  pthread_mutex_init (&amp;t->big_lock, NULL);  
  return t;  
 }  
 static void  
 insertNode (TreeMap * t, Node * n)  
 {  
  Node *x, *y;  
  n->left = n->right = t->nil;  
  y = t->rootNode;  
  x = t->rootNode->left;  
  while (x != t->nil)  
   {  
    y = x;  
    if ((t->cmp (x->key, n->key) == 1))  
   x = x->left;  
    else  
   x = x->right;  
   }  
  n->parent = y;  
  if ((y == t->rootNode) || (t->cmp (y->key, n->key) == 1))  
   {  
    y->left = n;  
   }  
  else  
   {  
    y->right = n;  
   }  
 }  
 static void  
 freeTree (TreeMap * t, Node * current)  
 {  
  if ((current != t->nil))  
   {  
    freeTree (t, current->left);  
    freeTree (t, current->right);  
    t->delete (&amp;current);  
    free (current);  
   }  
 }  
 static Node *  
 search (TreeMap * t, Node * current, void *keyval)  
 {  
  if (current != t->nil)  
   {  
    if (t->cmp (current->key, keyval) > 0)  
   return search (t, current->left, keyval);  
    else if (t->cmp (current->key, keyval) <>right, keyval);  
    else if ((t->cmp (current->key, keyval) == 0))  
   return current;  
   }  
  return current;  
 }  
 static void  
 LeftRotate (TreeMap * t, Node * x)  
 {  
  Node *y;  
  y = x->right;  
  x->right = y->left;  
  if (y->left != t->nil)  
   y->left->parent = x;  
  y->parent = x->parent;  
  if (x == x->parent->left)  
   {  
    x->parent->left = y;  
   }  
  else  
   {  
    x->parent->right = y;  
   }  
  y->left = x;  
  x->parent = y;  
 }  
 static void  
 RightRotate (TreeMap * t, Node * y)  
 {  
  Node *x;  
  x = y->left;  
  y->left = x->right;  
  if (x->right != t->nil)  
   x->right->parent = y;  
  x->parent = y->parent;  
  if (y == y->parent->left)  
   {  
    y->parent->left = x;  
   }  
  else  
   {  
    y->parent->right = x;  
   }  
  x->right = y;  
  y->parent = x;  
 }  
 static void  
 balanceAfterDeletion (TreeMap * tree, Node * x)  
 {  
  Node *root = tree->rootNode->left;  
  Node *w;  
  while ((x->colour == BLACK) &amp;&amp; (root != x))  
   {  
    if (x == x->parent->left)  
   {  
    w = x->parent->right;  
    if (w->colour == RED)  
     {  
      w->colour = BLACK;  
      x->parent->colour = RED;  
      LeftRotate (tree, x->parent);  
      w = x->parent->right;  
     }  
    if ((w->right->colour == BLACK) &amp;&amp; (w->left->colour == BLACK))  
     {  
      w->colour = RED;  
      x = x->parent;  
     }  
    else  
     {  
      if (w->right->colour == BLACK)  
     {  
      w->left->colour = BLACK;  
      w->colour = RED;  
      RightRotate (tree, w);  
      w = x->parent->right;  
     }  
      w->colour = x->parent->colour;  
      x->parent->colour = BLACK;  
      w->right->colour = BLACK;  
      LeftRotate (tree, x->parent);  
      x = root;    /* this is to exit while loop */  
     }  
   }  
    else  
   {  
    w = x->parent->left;  
    if (w->colour == RED)  
     {  
      w->colour = BLACK;  
      x->parent->colour = RED;  
      RightRotate (tree, x->parent);  
      w = x->parent->left;  
     }  
    if ((w->right->colour == BLACK) &amp;&amp; (w->left->colour == BLACK))  
     {  
      w->colour = RED;  
      x = x->parent;  
     }  
    else  
     {  
      if (w->left->colour == BLACK)  
     {  
      w->right->colour = BLACK;  
      w->colour = RED;  
      LeftRotate (tree, w);  
      w = x->parent->left;  
     }  
      w->colour = x->parent->colour;  
      x->parent->colour = BLACK;  
      w->left->colour = BLACK;  
      RightRotate (tree, x->parent);  
      x = root;    /* this is to exit while loop */  
     }  
   }  
   }  
  x->colour = BLACK;  
 }  
 static void  
 balance (Node * n, TreeMap * t)  
 {  
  Node *y;  
  Node *x = n;  
  while (x->parent->colour == RED)  
   {        /* use sentinel colour as exit loop */  
    if (x->parent == x->parent->parent->left)  
   {  
    y = x->parent->parent->right;  /* y 'uncle' of x */  
    if (y->colour == RED)  
     {  
      x->parent->colour = BLACK;  
      y->colour = BLACK;  
      x->parent->parent->colour = RED;  
      x = x->parent->parent;  
     }  
    else  
     {  
      if (x == x->parent->right)  
     {  
      x = x->parent;  
      LeftRotate (t, x);  
     }  
      x->parent->colour = BLACK;  
      x->parent->parent->colour = RED;  
      RightRotate (t, x->parent->parent);  
     }  
   }  
    else  
   {      /* case for x->parent == x->parent->parent->right */  
    y = x->parent->parent->left;  
    if (y->colour == RED)  
     {  
      x->parent->colour = BLACK;  
      y->colour = BLACK;  
      x->parent->parent->colour = RED;  
      x = x->parent->parent;  
     }  
    else  
     {  
      if (x == x->parent->left)  
     {  
      x = x->parent;  
      RightRotate (t, x);  
     }  
      x->parent->colour = BLACK;  
      x->parent->parent->colour = RED;  
      LeftRotate (t, x->parent->parent);  
     }  
   }  
   }  
  t->rootNode->left->colour = BLACK;  
 }  
 static Node *  
 TreeSuccessor (TreeMap * t, Node * x)  
 {  
  Node *y;  
  Node *root = t->rootNode;  
  if ((y = x->right) != t->nil)  
   {  
    while (y->left != t->nil)  
   {  
    y = y->left;  
   }  
    return (y);  
   }  
  else  
   {  
    y = x->parent;  
    while (x == y->right)  
   {  
    x = y;  
    y = y->parent;  
   }  
    if (y == root)  
   return (t->nil);  
    return (y);  
   }  
 }  
 static void  
 removeNode (TreeMap * t, Node * p)  
 {  
  Node *y;  
  Node *x;  
  Node *root = t->rootNode;  
  y = ((p->left == t->nil)  
    || (p->right == t->nil)) ? p : TreeSuccessor (t, p);  
  x = ((y->left == t->nil)) ? y->right : y->left;  
  x->parent = y->parent;  
  if (root == x->parent)  
   {  
    root->left = x;  
   }  
  else  
   {  
    if (y == y->parent->left)  
   {  
    y->parent->left = x;  
   }  
    else  
   {  
    y->parent->right = x;  
   }  
   }  
  if (y != p)  
   {  
    if (!(y->colour == RED))  
   balanceAfterDeletion (t, x);  
    t->delete (&amp;p);  
    y->left = p->left;  
    y->right = p->right;  
    y->parent = p->parent;  
    y->colour = p->colour;  
    p->left->parent = p->right->parent = y;  
    if (p == p->parent->left)  
   {  
    p->parent->left = y;  
   }  
    else  
   {  
    p->parent->right = y;  
   }  
    free (p);  
   }  
  else  
   {  
    t->delete (&amp;p);  
    if (!(p->colour == RED))  
   balanceAfterDeletion (t, x);  
    free (p);  
   }  
 }  
 /* public stuff...*/  
 Node *  
 searchKey (TreeMap * t, void *key)  
 {  
  Node *current;  
  Node *found;  
  assert (t != NULL);  
  current = t->rootNode->left;  
  pthread_mutex_lock (&amp;t->big_lock);  
  if (t->rootNode->left == t->nil)  
   {  
    pthread_mutex_unlock (&amp;t->big_lock);  
    return t->nil;  
   }  
  found = search (t, current, key);  
  pthread_mutex_unlock (&amp;t->big_lock);  
  if (found == t->nil)  
   return t->nil;  
  else  
   return found;  
 }  
 void  
 destroyKey (TreeMap * t, void *key)  
 {  
  Node *k = searchKey (t, key);  
  pthread_mutex_lock (&amp;t->big_lock);  
  removeNode (t, k);  
  pthread_mutex_unlock (&amp;t->big_lock);  
 }  
 void  
 insertKey (TreeMap * t, void *key, void *value)  
 {  
  Node *n;  
  pthread_mutex_lock (&amp;t->big_lock);  
  n = t->clone (key, value);  
  n->colour = RED;  
  insertNode (t, n);  
  balance (n, t);  
  pthread_mutex_unlock (&amp;t->big_lock);  
 }  
 void  
 replaceKey (TreeMap * t, void *key, void *newKey)  
 {  
  Node *current;  
  Node *cloned;  
  current = searchKey (t, key);  
  if (current == t->nil)  
   {  
    printf ("node not found for replacekey\n");  
    return;  
   }  
  pthread_mutex_lock (&amp;t->big_lock);  
  cloned = t->clone (newKey, current->value);  
  cloned->colour = RED;  
  removeNode (t, current);  
  insertNode (t, cloned);  
  balance (cloned, t);  
  pthread_mutex_unlock (&amp;t->big_lock);  
 }  
 Node *  
 updateKey (TreeMap * t, void *key, void *value)  
 {  
  Node *current;  
  Node *n;  
  current = searchKey (t, key);  
  if (current == t->nil)  
   return t->nil;  
  pthread_mutex_lock (&amp;t->big_lock);  
  n = t->clone (key, value);  
  n->colour = current->colour;  
  n->left = current->left;  
  n->right = current->right;  
  if (n->left != t->nil)  
   n->left->parent = n;  
  if (n->right != t->nil)  
   n->right->parent = n;  
  n->parent = current->parent;  
  if (current->parent->left == current)  
   current->parent->left = n;  
  else  
   current->parent->right = n;  
  t->delete (&amp;current);  
  free (current);  
  pthread_mutex_unlock (&amp;t->big_lock);  
  return n;  
 }  
 Node *  
 eraseKey (TreeMap * t, void *key)  
 {  
  Node *ret;  
  Node *k = searchKey (t, key);  
  if (k == t->nil)  
   return t->nil;  
  pthread_mutex_lock (&amp;t->big_lock);  
  ret = t->clone (k->key, k->value);  
  removeNode (t, k);  
  pthread_mutex_unlock (&amp;t->big_lock);  
  return ret;  
 }  
 int  
 eraseNode (TreeMap * t, Node * n)  
 {  
  if (n == t->nil)  
   return 0;  
  t->delete (&amp;n);  
  return 1;  
 }  
 void  
 destroy_tree_map (TreeMap * t)  
 {  
  if (t == NULL)  
   return;  
  pthread_mutex_destroy (&amp;t->big_lock);  
  freeTree (t, t->rootNode->left);  
  free (t->rootNode);  
  free (t->nil);  
  free (t);  
 }