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

41–50 of 63 posts

Re: Collections-C, generic data structures for C

#41

Post by eps »

seiji wrote: post #31
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…

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/com…

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

Re: Collections-C, generic data structures for C

#42

Post by raarts »

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 take this personally, but it worries me that someone who is not well versed with things like safe memory structures is tasked with writing software like this.

Re: Collections-C, generic data structures for C

#43

Post by gibsjose »

catnaroek wrote: post #35
gibsjose wrote: post #32

Earlier quoted context omitted.

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.

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.

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

Re: Collections-C, generic data structures for C

#44

Post by catnaroek »

gibsjose wrote: post #43
catnaroek wrote: post #35

Earlier quoted context omitted.

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.

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.

Re: Collections-C, generic data structures for C

#45

Post by gibsjose »

raarts wrote: post #42
gibsjose wrote: post #25

Earlier quoted context omitted.

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

Don 't take this personally, but it worries me that someone who is not well versed with things like safe memory structures is tasked with writing software like this.

I'm not sure what aspect of asking about the level of testing performed on an open source library gives you that idea, but sure: no offense taken.

Re: Collections-C, generic data structures for C

#46

Post by gibsjose »

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.

Yeah, that's true.

Re: Collections-C, generic data structures for C

#47

Post by brongondwana »

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.

Re: Collections-C, generic data structures for C

#48

Post by mschuster91 »

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.

Re: Collections-C, generic data structures for C

#49

Post by dllthomas »

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.

Re: Collections-C, generic data structures for C

#50

Post by woodman »

akp__ wrote: post #23
jepler wrote: post #2

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.

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++?

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.
Post reply on HN