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!

See this: http://stackoverflow.com/questions/4440476/static-allocation-of-opaque-data-types. Lots of very good answers. — Lundin, Sep 30 '16 at 11:26
You're providing neither an opaque type nor an abstract type. You're simply messing around with aliasing (with or without the `&`) in a way that causes undefined behaviour. — Peter, Sep 30 '16 at 11:42

score 3 · Accepted Answer · edited May 23 '17 at 12:00

3

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.

edited May 23 '17 at 12:00

Community

1
1

answered Sep 30 '16 at 11:35

Lundin

195,001
40
254
396

Well, I wrote that my "solution" is ugly ;) Thanks for your input, I'll think about my possibilities. But I don't get the undefined behavior. When parsing communication buffers, I'm casting some array (the buffer) to some struct (structured data, e.g. message headers) all the time. Is this undefined behavior? – Markus Oct 04 '16 at 07:05
@Markus Yes it is UB. You can chop up any data type in chunks of bytes, but not the other way around - with some exceptions. See this: http://stackoverflow.com/questions/98650/what-is-the-strict-aliasing-rule – Lundin Oct 04 '16 at 10:43
The approach is valid in non-crippled C. Unfortunately, the Standard only describes a crippled dialect even though decent compilers for most platforms support a non-crippled dialect not mandated by the Standard. For many purposes, the non-crippled dialect is more useful. – supercat Oct 04 '16 at 21:50
@supercat If you refer to reliance on strict aliasing ("crippled") vs ignoring the strict aliasing rules, I believe gcc is the only compiler that does the former. Almost every compiler I've worked with didn't use it, supposedly for practical reasons. Strict aliasing severely limits your options during hardware-related programming, for example, so embedded systems compilers never use it. But gcc is getting increasingly popular even for such systems, so this is becoming a real problem. Veteran embedded programmers who aren't aware of pointer aliasing, are nowadays writing severe bugs with gcc. – Lundin Oct 05 '16 at 07:53
@Lundin: The authors of the Standard never intended that it completely describe everything an implementation for any particular platform must do to be *useful*, but instead trusted the judgment of compiler writers over their own on many issues. Unfortunately, the authors of gcc and clang have decided that there is no need for them to exercise judgment except when necessary to make benchmarks work--they regard decisions by the Committee not to mandate a behavior on all platforms as indications that such a behavior is not important in quality implementations for any platform. – supercat Oct 05 '16 at 14:34
@Lundin: What's particularly sad is that people who recognized that type punning is useful on many systems and applications fields didn't see a need to add new syntax to support things that compilers for those systems and fields were *already* supporting, while those targeting high-end computing applications where performance is more important saw the lack of language constructs as an indication that support for punning isn't really needed. There's no reason the language should not have been be able to support both purposes just fine, except for compiler writers' refusal to... – supercat Oct 05 '16 at 14:39
...exercise reasonable judgment when weighing semantics versus performance. Regarding casts from T1* to T2* as a barrier to reordering operations on type T1 would have a relatively modest performance cost, but would make a lot of code usable without incurring the higher performance cost of `-fno-strict-aliasing`. – supercat Oct 05 '16 at 14:41

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

1 Answers1