Hacker News Board Hacker News, browsed like a classic message board
Live data from Hacker News

Collections-C, generic data structures for C

github.com

Post reply on HN
Print view View original

51–60 of 63 posts

Re: Collections-C, generic data structures for C

#51

Post by TickleSteve »

gibsjose wrote: post #30
david-given wrote: post #13

Earlier quoted context omitted.

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.

That depends on when a failure were to occur. If we have a failure while the spacecraft is en route to its destination, perhaps we can recover because we may have enough time. If we have a failure during rendezvous with our target, it could be a very bad day.

Dynamic memory allocation is extremely frowned-upon in embedded/real-time systems such as flight systems for exactly that reason. You simply cannot handle out-of-memory and fragmentation issues in a safe manner.

Re: Collections-C, generic data structures for C

#52

Post by TickleSteve »

asveikau wrote: post #6
gibsjose wrote: post #4

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

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

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.

Re: Collections-C, generic data structures for C

#53

Post by TickleSteve »

gibsjose wrote: post #25
asveikau wrote: post #6

Earlier quoted context omitted.

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

Ouch. I'll keep looking then. Any recommendations for reliable C data structures?

Don't dismiss it because of that, handling OOM errors is best handled by the alloc call by panicing.

If that situation is not allowed, I would suggest you shouldn't be performing memory allocation (or any other resource allocation) dynamically.

Re: Collections-C, generic data structures for C

#54

Post by optforfon »

catnaroek wrote: post #44
gibsjose wrote: post #43

Earlier quoted context omitted.

Vector and possibly string have that. The vast majority of STL structures do not.

All containers from the C++ standard library (please don't call it STL, that's Stepanov's original library) can be parameterized by an allocator. You can use whatever allocation policy you like best. However, most people use the default allocator because it's good enough. In any case, while C++ has lots of defects, “loss of control relative to what C gives you” isn't one of them.

(a bit of topic - but I'm humbly trying to learn more...) I've got zero experience writing allocators. Is there some common ones you use provided somewhere? Do you write your own? (in which case can you point me to where to learn to do that properly)

Re: Collections-C, generic data structures for C

#55

Post by junke »

dllthomas wrote: post #49
eps wrote: post #24

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 amon…

"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.

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.

Re: Collections-C, generic data structures for C

#56

Post by deadgrey19 »

vc98mvco wrote: post #40
deadgrey19 wrote: post #36

Earlier quoted context omitted.

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

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 wor…

I've not noticed the compile time increase to be honest. But I have noticed the type safety. A few times it has saved me from bugs that would have taken days to find if I was using void* casts. In my world (mostly high perf networking) I'm happy to pay a (small ~= unnoticeable) compile time cost if I get both safety and performance.

To make it more user friendly, I've provided (yet more) macros to make defining new types super easy. Using the macros does not necessarily involve adding a separate file, although the code is much cleaner if you do. And I don't have anything against adding extra files. There's almost no cost to me. I often group a couple of vectors or linked lists into a single .c/.h file pair to keep things manageable.

The code bloat you get is on par with using C++ templates. In fact, I'd say that it is probably better because the type safe macro's all devolve to a void* underlying implementation rather than generating separate instances. So it's pretty thin. You can always throw away the standard types list that I provide so that you don't have to pay for anything you don't use. And if you really want to, you can interface to the void* underlying implementation directly, loose the indirection costs, the function pointers and the macro costs. Basically, you can choose which world you want to live in, or live in both at the same time.

The long function names are handled by macros again. And since i used function pointer indirection you almost never see them. The costs with this sort of thing are minimal. A typical invocation looks something like

  CH_VECTOR(MYVECCLASS)* myvec =  NEW_CH_VECTOR(MYVECCLASS);
  myvec->append(myvec,object);
There are certainly tradeoffs, the implementation is not nearly as mature as I'd like and debugging problems inside the containers is a HUGE PITA. But in my experience it lets me kee the benefits of working in C (can pull inside the kernel, can port to different machines, easy control over memory and performance) and gives me the flexibility of doing higher level things when I want.

Re: Collections-C, generic data structures for C

#57

Post by catnaroek »

optforfon wrote: post #54
catnaroek wrote: post #44

Earlier quoted context omitted.

All containers from the C++ standard library (please don't call it STL, that's Stepanov's original library) can be parameterized by an allocator. You can use whatever allocation policy you like best. However, most people use the default allocator because it's good enough. In any case, while C++ has lots of defects, “loss of control relative to what C gives you” isn't one of them.

(a bit of topic - but I'm humbly trying to learn more...) I've got zero experience writing allocators. Is there some common ones you use provided somewhere? Do you write your own? (in which case can you point me to where to learn to do that properly)

I don't write allocators myself, but Boost has a pool allocator library [http://www.boost.org/doc/libs/1_60_0/libs/pool/doc/html/inde...], which conforms to the Allocator concept defined in the standard library [http://en.cppreference.com/w/cpp/concept/Allocator].

Re: Collections-C, generic data structures for C

#59

Post by fit2rule »

brongondwana wrote: post #47

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 cod…

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 ..

Re: Collections-C, generic data structures for C

#60

Post by dllthomas »

junke wrote: post #55
dllthomas wrote: post #49

Earlier quoted context omitted.

"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.

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, obj…

Sorry, yes, rather the problem comes from a sufficiently dynamic set of list memberships.
Post reply on HN