C99: is it possible to design an abstract datatype without dynamic allocation?

Question

I have to design an abstract datatype, but I'm not allowed to use dynamic allocation. Seems a bit tricky...

What I currently have:

In adt.c:

struct adt
{
  bool b;
};

const size_t adtSize = sizeof( struct adt );

// Initialisation of the adt
void Adt_New( struct adt* anAdt, bool b )
{
  // No calloc allowed...
  anAdt->b = b;
}

In adt.h, the ugly part comes:

struct adt; // adt structure

extern const size_t adtSize;

// Bear with me...    
#define ADT_DATA( NAME ) uint8_t NAME ## _storage[ adtSize ]; \
    memset( &NAME ## _storage , 0 , adtSize ); \
    struct adt* NAME = (adt*) & NAME ## _storage;

Now I can use it like this:

void TestAdt()
{
  ADT_DATA( a );

  Adt_New( a, true );
}

On the pro side, I have an opaque data type and I don't have to use dynamic allocation.

Con the con side, this is just ugly. And when I try to call ADT_DATA( ... ) not from within a function (globally, e.g.), I get an error message.

Is it possible to improve this? Currently, my only alternative is to make the data type public...

TIA for your Ideas!

Answer 1

Your approach won't work at all, because as soon as you start using that uint8_t buffer for unrelated purposes, you violate strict aliasing. In fact that's what you are doing right here: struct adt* NAME = (adt*) & NAME ## _storage;. That's undefined behavior.

Typically, having no access to malloc (as in, your average embedded system) is solved by creating your own memory pool inside the ADT. The memory pool is an array of X objects of the opaque struct type. Here is an example with opaque pointers:

Header file:

typedef struct adt adt;

C file:

struct adt
{
  // stuff
};


static adt mempool [X];
static size_t mempool_size;    

adt* adt_alloc (/* stuff */)
{
  adt* new_obj;

  new_obj = &mempool[mempool_size];

  mempool_size++;
  if(mempool_size == MAX)
  { /* handle error */ }

  new_obj->this = 123;
  new_obj->that = 456;
  ...

  return new_obj;
}

This method makes most sense for more complex ADTs. For simpler ones, the overhead needed might not be worth it, and you should consider making the whole struct public in such cases.

Other ways exist too, I would strongly recommend to read all of Static allocation of opaque data types. Lots of nice tips & tricks.