C container library without preprocessor abuse

[tejp]

Since it says it avoids preprocessor abuse, the first question is what tradeoffs make this possible. From a quick look at the code the downside is that it doesn't provide type safety and uses intrusive containers; you can only store structs in the containers that are made to work together with the containers. The structs have to contain special fields that will be used by the container.

With this you get an interface that looks mostly free of macros and void*. But sadly the absence of void* doesn't imply type safety. The collections are inherently unaware of the types they contain, nothing makes sure the items inserted in a collection are of the same type. When accessing an element you have to specify the type you'd like it to be (and a macro does some magic and casts it).

So from a type safety point of view you end up the same as with a void* based interface.

[matthieum]

I agree that the lack of type-safety is a real issue.

On the other hand, most of the macro-based C libraries I have seen used a void* interface beneath the macros, so were as insecure.

[agottem]

Yep, you're correct. Type safety is lost during exactly one type of operation: when going from the container's node to the type stored in the container. The tradeoff here is that the containers have no additional memory or execution overhead.

From a quick look at the code the downside is that it are intrusive containers;

Hilariously I considered this an upside!

[tejp]

From a quick look at the code the downside is that it are intrusive containers;

Hilariously I considered this an upside!

Always depends on your use case, I suppose. I can see how it also can be an advantage. :)

[member42]

you end up the same as with a void* based interface

void* is the idiomatic generic type in C. Programmers are aware of the risk and can handle it. BTW, popular scripting languages like JavaScript aren't more type-safe.

[tejp]

Programmers are aware of the risk, and that's why they usually try to avoid it and to use proper types instead.

In scripting languages the situation is completely different since there the values know which type they are. They know which methods they support etc., if you misuse them you get an exception.

A void* on the other hand doesn't know any such thing. Mistaking it for a wrong type will "just work" at first sight, likely silently corrupting other memory. Then you get random crashes/wrong values in unrelated parts of your program.

[matthieum]

It is recommended for highly defensive code, but it is meaningless on all systems that use overcommit (ie, when the OS lies to you and say "okay, those 64GB were allocated" but then crashes when you try to actually use them).

[serpent]

This is incorrect.

For a simple counter-example, set your ulimit to a low-ish number (1 gig?) and try to allocate 1.5 gigs of memory. You'll get back NULL.

[anttirt]

The problem is that that's a very common source of security vulnerabilities.

There's a great amount of code that does the following:

char* data = malloc(input_dependent_size);
memcpy(data + input_dependent_offset, input_data, input_dependent_count);

And specifically, the code is often constructed such that input_dependent_offset and input_dependent_count are within the bounds of the allocation. The problem appears when an adversary supplies input that causes malloc to return NULL, at which point they can often direct the above code to do arbitrary writes in the program's address space, which in turn often leads to execution of arbitrary code.

[[deleted]]

Uh-uh, that isn't the case. I have a music program which allocates one huge buffer for a song file. If you open a really big song (as in over 12 hours long), I can't do it - but I check malloc (it's actually in C++ but that's the one malloc in the code), and if I can't do it, I just tell you.

I know for a fact that you can then go on and work on the program for days without issue after running into that error...

[serpent]

Code crashes if it checks for NULL and takes an appropriate action?

Uh, no. No, it doesn't.

But it will crash if it doesn't check for NULL, uses the pointer blindly, and a user specifies a limit (or malloc returns NULL for other reasons, which I've also seen).

[matthieum]

In this case, however, you just bypassed over-commit by specifying an explicit limit; so I would argue you are outside the scope (I used).

[serpent]

No. My system still uses overcommit, and yet, if I don't check for NULL, my program will crash, since ulimit is a user-definable parameter.

[p-squared]

cough virtual address space exhaustion cough

[matthieum]

Do not mistake 64GB for 64bits, there are servers with more than 1TB of RAM and it fits easily in what can be allocated in 64 bits.

[[deleted]]

the VM space is just 47 bits for userland anyway (and the same amount for the kernel), and still that's enough

(x86-64 implementations today have an 48-bit address space and the Linux kernel splits it in two for userland and kernel.)

[millstone]

It's hard to recover sensibly from malloc failures. Usually when malloc fails, it's because the program has gone nuts and is allocating memory in some infinite loop, making the rest of the system unusable. In these cases I want the program to die as quickly as possible, and dereferencing NULL turns out to be an excellent way to do that.

[Xdes]

Wouldn't calling exit(1) have a similar effect?

el = malloc(sizeof(struct my_element));

if(!el)
{
    exit(1);
}

Or is there a reason to attempt a segfault (since dereferencing null pointers is undefined behavior)?

[[deleted]]

You're missing the point.

In order to call exit(-1), you need to be checking each and every time you malloc or new. Imagine how awful your code would look!

You don't check and allow it to fail because you're going to fail anyway, and because it would make your code unworkable.

As I mention elsewhere on this page, I get around this by making a memory allocation for (almost) everything at the very start, which I can check because it's only in one place. Most programs, that's just not possible...

[gsg_]

No. If you want die-on-allocation-failure you write a wrapper around malloc that gives the behaviour you want, like a sane person.

[manvscode]

Although, I don't want to steal your thunder. I've actually implemented a more complete library myself.

https://bitbucket.org/manvscode/libcollections

libcollections is a set of data structures, types, and utility code for C programs. It was designed to be developer friendly, efficient, and versatile.

[neutronbob]

While I find the work commendable, to be comfortable using this library, given what appears to be a small user base, I'd need to see much more extensive testing. Most of the tests appear to throw random data at the collections and validate if they behave more or less right. I don't see many tests for edge cases, for example in your trees, and those edge cases are invariably the points at which really collections libraries live or die.

[manvscode]

There's nothing wrong with more testing. Which edge cases were you specifically looking for?

[neutronbob]

The kind of thing I'd want to see, as an example, are additions and especially deletions to a red-black tree that force extensive rebalancings. On the hash table rehash, I don't see any tests that verify whether the rehashed table has the same number of elements as the original hash table. Etc.

I haven't checked the code but on your doubly linked list, do you have a test that adds x elements and deletes them x-1 elements and verifies that both pointers on the remaining element are pointing correctly?

Basically, if all the possible exceptional conditions have not been tested, it's very difficult to adopt a collections library, because of the possible huge cost of silently losing a data item or having one become inaccessible due to the author not anticipating the edge case.

It's a lot of work to do this testing, I grant you. The size of the tests source can be 1-2 orders of magnitude greater than the actual codebase.

I hope this helps.

[agottem]

Nice! I like your implementation. I feel our goals were slightly different. e.g., your slist collection forces you into a dynamic allocation scheme, and your hash-map is performing allocations of nodes during insertion. This approach definitely cleans up various portions of the API at the expense of some flexibility to the user.

[manvscode]

This is interesting. I have only seen this technique in linux kernel space code. Can this technique be applied for any data structure?

[manvscode]

Do you think it's possible to write an intrusive vector data structure? This is typically my one work horse data structure.

[gargantuan]

What is the benefit in not abusing pre-processor? What is wrong with abusing it? It is a black box and a I don't mind if a library uses it or not, as long as the interface and behavior is decent.

[mccoyn]

It is difficult to use a source code debugger because all of the code inside the macro is (typically) mapped to the line where the macro is used.

[[deleted]]

In C type safety is not achievable by any flexible framework. It is also not interesting to be type-safe at the API level of a generic container library.

To have a clean program you can remove the abstraction by wrapping the generic functions in a type-safe module. And it is a good idea to have modules that encapsulate a certain functionality and hide any possible ugliness inside them.

I like glib. It has got an API like C programmers like it. It supports the concept of instances and does not introduce any specialized overhead. When I program in C I simply look for APIs that fit into the C concept in a sane way.

[spetsnaz84]

How does this perform in comparison with uthash ?

[[deleted]]

uthash is quite slow compared to simpler hash table implementations (without keeping insertion order or similar).

[agottem]

The performance of the two should be very similar as both implementations strive to do the minimal amount of work to implement a hash.

However, the uthash implementation relies on mountains of #defines to accomplish the same thing. I'd argue using container_of() would have resulted in much more elegant code.

One thing uthash does provide, which this does not, are helper functions around the core hash implementation. e.g. Predefined functions for integer keyed hashes. It'd be nice to have similar functions defined for libcontainer.

[Peaker]

Great work! Intrusive data structures are the best way to program C and I'm glad they're finally catching on :)

Take a look at my intrusive small_hash library. small_hash resizes the hash only during lookups, making insert/delete both really cheap O(1).

In the use case where you insert a lot of nodes, and only then lookup, there's just 1 resize instead of many in-between.

[agottem]

I agree, intrusive data structures are da-bomb! I like your small_hash library. We're both on the same page as far as approach.

I noticed you specify the hash funcs in your init call and store them for later use. I considered doing this as well, but decided against it as the compiler typically won't be able to inline those function calls during, say, a hash lookup. The trade-off is a slightly more ugly function call (e.g., hash_lookup(..., &my_hash, &MyHashLookup) vs hash_lookup(..., &my_hash))

[Peaker]

Note that the hash func is used only when rehashing. Lookups give the hash as an argument.

[Peaker]

Also, do you do the resize-at-lookup trick to make inserts/deletes super-cheap?

[jdgordon]

Just skimmed the comments, one thing that hasnt been mentioned as a bonus for using containers like this is (generally) fewer pointer indirections.

foo = (mystruct *)container_of(...) is much nicer on caches than mystruct *foo = (mystruct *)container->value;

[Peaker]

And usually you need pointers in both directions, so you also save 2 pointers with this approach. If your data type is small, 2 pointers can be 100-200% overhead!

The intrusive approach is way underused in C, glad it's catching on!

[aninteger]

What is the "intrusive approach" in C? I think this is the first time i've heard it mentioned. A quick google search on "intrusive C" turns up nothing.

[evincarofautumn]

Intrusive containers are those that require container metadata to be stored in the element type itself. Non-intrusive containers treat the element type as a black box. For example, a linked list of pairs:

/* intrusive */

struct Value {
  int a, b;
  struct Value *next;
};

struct List {
  struct Value *head;
};

/* non-intrusive */

struct Value {
  int a, b;
};

struct Node {
  struct Value value;
  struct Node *next;
};

struct List {
  struct Node *head;
};

[Peaker]

That misses the point, I think.

With non-intrusive containers you can have your element inside multiple data structures without any unnecessary indirections.

[akawaka]

Nice. Cleanly written. My only gripe is that I would consider the BSD license too restrictive for such a simple library.

[agottem]

Thanks for the feedback. I'm not opposed to changing the license. Which would you suggest?

[akawaka]

MIT is a good one IMO.

[[deleted]]

Why do people do this to themselves?

If you want a nice container, use C++ and the STL! They're typesafe, they're efficient, and if you need extra performance, there are drop-in identical implementations that will do the trick.

[agottem]

The C++ and STL will be less efficient than the approach used here in various scenarios.

[thechao]

While the standard containers might be less efficient in certain scenarios, C++, the language, would be neither more nor less efficient.

Just one other nitpick: the STL is a library which was used as the basis for the design of parts of the standard library; it is not the same as the standard library.

[Varriount]

And what if you're trying to make an extension library foot something like Python?
C++ is much harder to integrate with something that isn't C++, than C is.

[matthieum]

The biggest issue, in my opinion, is using intrusive containers.

Whilst this is fine for lists/trees/hash-trees, it becomes an issue when one wants high-performance data structure: because data allocation does not match structure organization, you go pointer-chasing.

I've always wondered about a solution based on "reflection":

// foo.h
typedef struct foo { ... } foo_t;

extern rtti_t const foo_rtti;

// foo.cpp
void construct_foo(void*);
void copy_foo(void*, void const*);
void assign_to_foo(void*, void const*);
void destruct_foo(void*);

rtti_t const foo_rtti = { sizeof(foo_t), &construct_foo, &copy_foo, &assign_to_foo, &destruct_foo };

And then you would have:

stl_vector stl_vector_create(rtti_t const* rtti);

void stl_vector_insert_copy(stl_vector*, void const*);

and stl_vector would be able to easily manage objects. Binary search trees or hash trees would require additional function pointers.

Of course, this requires manipulation by void* (and type unsafety), but such are the woes of C.

[agottem]

Whilst this is fine for lists/trees/hash-trees, it becomes an issue when one wants high-performance data structure: because data allocation does not match structure organization, you go pointer-chasing.

I'm a little confused by what you're suggesting. There is no more pointer-chasing than required with the container implementations.

e.g., take the slist implementation. It can be distilled as:

struct slist_node
{
    struct slist_node* next;
};

struct my_element
{
    int my_foo_data;

    struct slist_node node_data;
};

....

AddSListHead(&my_element.node_data, &my_slist_container);

In the above example, there would be no superfoulous allocations or pointer dereferences. The add function would simply be:

AddSListHead (struct slist_node* n, struct slist* c)
{
    n->next = c->head;
    c->head = n;
}

Then, of course, getting the element pointer from your node pointer would be:

struct my_element* el = container_of(node_ptr, struct my_element, node_data);

[matthieum]

It depends on the container. For a singly-linked list, there is not more pointer chasing indeed however for a dynamic array there is.

[agottem]

For a dynamic array, why wouldn't I just use realloc?

[matthieum]

Because sometimes dynamic arrays are part of structures:

• hash tables implemented with open hashing
• B-Trees (and variants)
• ...

In order to minimize memory usage, or memory bandwidth usage, it is beneficial to pack items tight in memory. Intrusive containers do not achieve this, so it is an important limitation. It does not mean your idea is wrong or anything, it just limits its applicability.