Abstract Data Type using opaque pointers in C

README.md

Compile and run

gcc adt.c array.c -o adt
./adt

adt.c

#include <stdio.h>
#include <stdlib.h>

#include "array_api.h"

// Opaque pointer:
//        An ADT implementation hidden behind the interface that is abstract to
//        the client, making it easier to maintain, apply changes and improve
//        in this example the array_t data type provides a bunch of functins
//        for manipulating the array, these are accessed through the array_api.h
//        interface but the implementation stays hidded in array.c

int main(int argc, char const *argv[])
{
  // A static structure can not be defined because the compiler doesn't know
  // how big the data type is since we didn't add any elements to it
  // array_t new_array;
  // error: storage size of ‘new_array’ isn’t known

  // We can however define a pointer to such structure because a pointer is
  // always of a known size
  array_t *arr;

  // Create a new abstract array with size 3
  arr = array_alloc(3);

  // Set some values
  array_set(arr, 0, 1);
  array_set(arr, 1, 2);
  array_set(arr, 2, 4);

  // Display the array
  array_print(array_begin(arr), array_end(arr));

  // Cause the array to grow by setting new indices
  array_set(arr, 3, 8);
  array_set(arr, 6, 42);

  // Display the array, note the empty indices 4 and 5 are set to zero
  array_print(array_begin(arr), array_end(arr));

  // Free up the array
  array_free(arr);

  return EXIT_SUCCESS;
}

array.c

#include <stdio.h>
#include <stdlib.h>

#include "array_api.h"

// this is the abstract implementation of the array api
// including the header here helps us stay consistent with the public api we provide
// this file can, of course, also have it's own private header file

// abstract data type
struct array_s
{
  int m_size;
  int m_capacity;
  int * m_data; // actual array data
};

// memory management
array_t *array_alloc(int size)
{
  // memory for the return structure
  array_t* ret = malloc(sizeof(array_t));

  // size and capacity
  ret->m_size = ret->m_capacity = size;

  // array data allocation
  ret->m_data = malloc(ret->m_capacity * sizeof(int));

  return ret;
}

void array_free(array_t *arr)
{
  // free array data and struct itself
  free(arr->m_data);
  free(arr);
}

// manipulations
void array_set(array_t *arr, int index, int value)
{
  // set the size if requested index is bigger than we have
  if (index >= arr->m_size)
  {
    arr->m_size = index + 1;
  }

  // check the capacity
  if (arr->m_size >= arr->m_capacity)
  {
    // grow the array by doubling it's current capacity
    int new_capacity = arr->m_capacity * 2;

    if (new_capacity <= arr->m_size)
    {
      new_capacity = arr->m_size + 1;
    }

    // realloc more memory
    arr->m_data = realloc(arr->m_data, new_capacity * sizeof(int));
    arr->m_capacity = new_capacity;
  }

  // set the value
  arr->m_data[index] = value;
}

void array_print(int *begin, int *end)
{
  while (begin != end)
  {
    printf("%d ", *begin);
    begin++;
  }
  printf("\n");
}

// array status info
int *array_begin(array_t *arr)
{
  return arr->m_data;
}

int *array_end(array_t *arr)
{
  return arr->m_data + arr->m_size;
}

array_api.h

#ifndef ARRAY_H
#define ARRAY_H

// Abstract Data Type
//
// This demonstrates information hiding (encapsulation) using C
// If the declaration of array_t or the internal structure were to change
// it would be unnecessary to recompile other modules, unless the API was also
// changed

// object of an incomplete type
typedef struct array_s array_t;

// interface for the ADT
array_t *array_alloc(int size);
void array_free(array_t *arr);

void array_set(array_t *arr, int index, int value);

int *array_begin(array_t *arr);
int *array_end(array_t *arr);

void array_print(int *begin, int *end);

#endif

// and other junk, but the array_api.h can stays separate

The purpose of opaque pointers is to keep the implementation separate, that allows you to do "separate compilation", but the api is something that is NOT separate and this is an error to not include it here.

It would be better to include array_api.h inside array.c that way the compiler could guarantee that the definition used by the callers match the function declarations inside array.c

If at some point you decide to evolve the api, and you make the following mistake: the function declarations and the header prototypes are not matching anymore because you copy pasted wrong, or forgot something, then It is likely that everything will compile just fine and you will have ABI errors at runtime. If you are not lucky they could even NOT trigger segmentation fault and go undetected while you're code is not working.

---

you would have to remove that typedef to prevent a name conflict probably (did not test it)

typedef struct array_s
{
  int m_size;
  int m_capacity;
  int * m_data; // actual array data
} array_t;

would become

#include "array_api.h"


struct array_s
{
  int m_size;
  int m_capacity;
  int * m_data; // actual array data
};

@tmijieux Didn't think 5 years after someone would even look at this :D
Thanks for the comment, you're totally correct! Public header should be included in the implementation as well :)