Collections-C, generic data structures for C

by marxo • 10 years ago

115 60 10 years ago

jepler• 10 years ago

It looks like all collections store void pointers. I don't see any abstractions to help with pointer lifetimes, which remains the main problem I encounter when trying to write large programs in C that dynamically allocate memory.

yoklov• 10 years ago

Start using arenas wherever you can. Makes memory management in C programs substantially simpler.

eatonphil• 10 years ago

Any good readings on getting started with arenas?

stinos• 10 years ago

It looks like all collections store void pointers

Does that mean that if you're running as 32bit and want to store a number larger than that (a double or int64_t or so) or a POD that all of these have to be allocated seperately?

akp__• 10 years ago

I'm no expert here, just curious. I've seen this brought up a couple times now: what's wrong with void pointers? How else would you do this in C? If you wanted abstractions to help with pointer lifetimes wouldn't you just be better off using C++?

lucozade• 10 years ago

The limitation with void pointers is that it can only inline values <= the size of a pointer. If you have something larger then you need to allocate it separately which may have cache efficiency issues.

The main alternative, other than hardcoding an element type, is to use macros and pass the element type in the definition.

Sometimes you just don't have the option of a C++ compiler. Also, and this was a situation I was in recently, I needed a collection in a small area of my C code so it really didn't warrant a toolset change.

woodman• 10 years ago

Void pointers mean no type safety, preventing a lot of potential compiler optimizations and static analysis checks. 99% of the time the right thing to do is just create a new type:

  typedef struct Strref_t {
    char* str;
    size_t ref;
  } Strref;

There, just pass a pointer of that type around.

wangchow• 10 years ago

Would be nice to have parallel structures like "Intel threading building blocks" provides.

https://en.m.wikipedia.org/wiki/Threading_Building_Blocks

I recommend this book to understand such structures:

https://www.goodreads.com/book/show/14788830-structured-para...

srdja2• 10 years ago

I'll definitely look into it.

gibsjose8• 10 years ago

Has this library been stress tested? I am interested in using this library for a spaceflight application, but reliability is paramount in our situation.

asveikau• 10 years ago

I stopped looking when I saw it doesn't check for malloc failure. I am going to say space flight is a no-go.

ryandrake• 10 years ago

Some of the functions do check for malloc failure and others don't. It's on github--Have you submitted a pull request? Wow--guess the idea of sending a patch to an open source project is now controversial.

david-given3• 10 years ago

But for this kind of application, wouldn't you just panic and do a soft restart on malloc failure anyway? Actually recovering from an out-of-memory situation is incredibly fraught and unreliable; most of the realtime operating systems I've used don't even bother to try.

gibsjose8• 10 years ago

Ouch. I'll keep looking then.

Any recommendations for reliable C data structures?

rewqfdsa2• 10 years ago

Thank you. There is somebody else on this fucking planet who understands that memory is not limitless manna from heaven.

TickleSteve3• 10 years ago

This is quite common because the alloc() call itself would panic if out-of-memory.

Remember, a large proportion of C code is for embedded/real-time systems where the only sensible recovery option is to reset.

Attempting to 'handle' an error manually in every case is simply not possible. Better to reset and come up in a clean state than propagate errors.

Having said that, dynamic memory allocation is itself frowned upon in embedded systems.

junke2• 10 years ago

Give Ada a try

gibsjose8• 10 years ago

[Un]fortunately, we are tied to C/C++ due to mission requirements and our hardware platform.

kev009• 10 years ago

I try and plug http://concurrencykit.org/ whenever I see someone looking for something like this. It's built around providing portable atomic intrinsics for parallel code, but the data structures are also very well done and work just as nicely for single threaded code.

CyberDildonics• 10 years ago

Does it include any sort of a concurrent heap into shared memory?

rurban• 10 years ago

Yes, ck and preshing https://github.com/preshing/junction are state of the art. This one really not.

naasking• 10 years ago

klib [1] is another good one I recently came across. In fact, I'll just leave this great curated list of free software libraries right here:

https://notabug.org/koz.ross/awesome-c

[1] https://github.com/attractivechaos/klib

Mellowcandle• 10 years ago

nice. I actually built something very similar a while ago. although I only supported lists, queue and stacks... https://github.com/mellowcandle/liblist

kazinator• 10 years ago

Kazlib: since 1996.

http://git.savannah.gnu.org/cgit/kazlib.git/tree/

http://www.kylheku.com/~kaz/kazlib.html

Used in e2fsck since 2002: http://git.kernel.org/cgit/fs/ext2/e2fsprogs.git/commit/e2fs...

vc98mvco2• 10 years ago

A quick look shows this is storing void* pointers only. My excitement was quickly over as I was expecting something with _Generic macros or ability to manage memory for any type.

https://github.com/srdja/Collections-C/blob/master/src/hasht... shows the container is manually configurable. Look at the defines at the bottom. This would mean the container file source-header pair, would have to be duplicated for every type, which is somewhat manageable.

Why isn't this written in the readme?

deadgrey193• 10 years ago

<shameless self promotion> Take a look at this instead. Work started on this before C-generics came about, so there is pretty heavy macro usage, but all data structures are type safe: https://github.com/mgrosvenor/libchaste

vc98mvco2• 10 years ago

I see you use C macro templates. I have been experimenting with containers that use those. The advantages are speed and full type safety, and disadvantages are long compilations times (which have to be done only once though), the need to define a new template for every type in (only one) separate file, code bloat, and somewhat long function names (I don't use member function pointers).

I'm not sure if all that is worth it.

YesThatTom2• 10 years ago

Take that, Golang!!!!

J/K

eps2• 10 years ago

Nice, but it's rather naive and through that - needlessly wasteful.

It's C.

Why on Earth you'd want to allocate a separate list node for each piece of data when you can embed this node directly into the data and then use container_of or similar offsetof() derivative to get a pointer to the data by a pointer to a list item? Saves you at least sizeof(void*) per item and eliminates a chance of list_add ever failing among other things.

The same goes for custom allocators - why would you drag around pointers to malloc, calloc and free, when all you need is just a pointer to realloc?

This sort of thing. The code is nice, but it's not how one would write a container library after few years of hands-on C experience.

seiji• 10 years ago

allocate a separate list node for each piece of data

So many programmers don't even consider "overhead" of data when writing things. But, most of the time it doesn't matter. Do you need a list of ten things? Great. Do whatever. Do you need a list of a billion things? Then you need to rethink everything from the bottom up.

when all you need is just a pointer to realloc

Wrong! https://github.com/Tarsnap/libcperciva/commit/cabe5fca76f6c3...

catnaroek4• 10 years ago

So many programmers don't even consider "overhead" of data when writing things.

Because they're using managed languages where the amount of overhead per object can't be reduced to zero. And also because, in exchange for that overhead, they get other benefits, like compacting garbage collection. But you don't get this in C.

eps2• 10 years ago

Wrong! https://github.com/Tarsnap/libcperciva/commit/cabe5fca76f6c3....

No, of course not "Wrong!"

If a user of a library wants to supply their own allocator, they must provide a version of realloc that acts as free() for the (p,0) case. That's the semantics the library expects, observe them. Internally the lib may look at whether a custom realloc is set, and fallback to malloc/free if it's not.

dllthomas2• 10 years ago

"Why on Earth you'd want to allocate a separate list node for each piece of data when you can embed this node directly into the data"

It's a good approach when the items may need to be in several lists at once.

junke2• 10 years ago

You can certainly put the payload into multiple lists. From http://www.crashcourse.ca/introduction-linux-kernel-programm...:

More to the point, a payload is welcome to participate on several lists, but only after defining an internal list_head object for each list. In other words, unlike the payloads you're used to that contain only pure data and could (theoretically) be on an infinite number of lists at once, objects on kernel lists can be only on those lists for which they have an internal set of links. It's an interesting way to lock down what lists you're willing to be a member of.

rewqfdsa2• 10 years ago

Honestly, why? Most of the time, you want to write C++, with exceptions, and the STL. You can make this kind of programming as robust as you want against memory allocation failure.

If you don't want to use this style of programming, for whatever reason, check out sys/queue.h. It's already on your system, if you're using some kind of Unix.

gibsjose8• 10 years ago

If you are using an RTOS (which many timing-critical applications run on), you should be worried about memory allocations happening under the hood.

If you don't have full control over when memory is being allocated/reallocated, your system is now non-deterministic.

With pure C, you can know exactly when those few extra instructions for resizing your dynamic array are going to happen.

catnaroek4• 10 years ago

Same in C++. There's `std::vector::reserve`, which grows the vector's underlying physical buffer, without logically adding any new elements. If you `reserve` enough capacity before inserting anything, it's even a `O(1)` operation.

deadgrey193• 10 years ago

<shameless self promotion> If you're interested in this sort of thing, take a look at https://github.com/mgrosvenor/libchaste. Work started on this before C-generics came about, so there is pretty heavy macro usage, but all data structures are type safe rather than the "cast to void*" approach which is common in this space. It's a bit less mature, but reasonably well covered by unit tests where it matters.

srdja2• 10 years ago

Hello everyone, I'm the author of this library. I was quite surprised to find it on the front page of HN! I must thank you for all the great feedback, it's been very helpful. I agree that it has rough edges and that it also lacks some useful features but I guess this is mostly because I was the only user of it.

I very much welcome your suggestions on how to make better and more useful. :)

brongondwana• 10 years ago

I tried reading the documentation, which is awfully sparse, to see how to use the hash table and if it would be a good replacement for the current one in cyrus-imapd.

The destroy function in cyrus-imapd has both a destroy that takes a cleanup function for values, and an interator:

https://github.com/brong/cyrus-imapd/blob/master/lib/hash.c

I couldn't see how to do either with this library until reading the source code I see you can set a mem_free at creation instead.

The documentation didn't really describe that, and the example is actively wrong.

I see from the code that there's a way to get the keys, from which you can do an external iterator. It's less efficient, but it works. You wouldn't know that from the documentation though, you have to read the source code.

fit2rule• 10 years ago

Any chance you're going to submit a pull request to fix the documentation? I'd like to check this library out for use in a project, but I'm not sure I'd get so far as you have with regards to matching the documentation to the sources ..

mschuster91• 10 years ago

From hashtable (https://github.com/srdja/Collections-C/blob/master/src/hasht...)

HashTableConf htc;

Hold short, that structure is allocated from the stack and not via malloc? I'd expect that one to blow up after the second call to hashtable_new.

edit: seems like htc is immutable and the values copied over in hashtable_new_conf, but that's downright scary in case one forgets this semantic and accidentally uses htc for something.

ape4• 10 years ago

Something like this should be in standard C.

Collections-C, generic data structures for C

Related Stories