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

Show HN: C library of generic, reference-counted data structures

theck01.github.io

Post reply on HN
Print view View original

31–40 of 42 posts

Re: Show HN: C library of generic, reference-counted data structures

#31

Post by theck01 »

pepijndevos wrote: post #11

What are "class[es] built from functions and incomplete types"? I once built classes using structs and function pointers, but this sounds different?

An incomplete type is a struct where the definition of the structure is hidden from the view of most of your source code. This makes it impossible to directly access struct elements, and is like data hiding in a object oriented language. Of course in this library you can always include the header containing the struct definition and go bananas so its a soft restriction.

Re: Show HN: C library of generic, reference-counted data structures

#32

Post by huhtenberg »

I find that the decision to adopt a C library for a project frequently boils down to whether it is using a compatible naming notation. Especially for simpler libraries.

Linked library in nice, but how many C projects do you know that use camelCase() function naming as opposed to K&R's lower_case_naming()? If it were a complex library, like OpenSSL, then - sure, to the hell with the notation, just put a wrapper around it and use it anyway. It's barely an issue. But if it is a simpler library that is meant to be weaved into the code, like data containers, the choice of naming notation is always a thing to consider.

There is obviously an indent tool, but resorting to it means using a modified version of the original with all the consequences that follow. Perhaps, it might be the next thing for GitHub to tackle - "Download in Xyz naming notation"... I know I'd use it.

Re: Show HN: C library of generic, reference-counted data structures

#33

Post by nitrogen »

ExpiredLink wrote: post #20
cmccabe wrote: post #9

It's nice that you made these available. You might also want to look at queue.h from BSD (see http://fxr.watson.org/fxr/source/sys/queue.h ) and tree.h ( http://www.freebsd.org/cgi/cvsweb.cgi/src/sys/sys/tree.h ), single-file "libraries" that can generate a few different kinds of linked list and binary tree. These don't require typecasting at all, since they generate functions for your particular type. They are also…

> You might also want to look at queue.h from BSD CPP macros, entirely. No, thanks.

Just as an anecdote, in one of my university classes we had the assignment of writing and optimizing a memory allocator. When I switched from using structs to using pointer arithmetic in macros, I gained a significant performance boost, even though the in-memory data was exactly the same.

Re: Show HN: C library of generic, reference-counted data structures

#34

Post by zht »

nitrogen wrote: post #33
ExpiredLink wrote: post #20

Earlier quoted context omitted.

> You might also want to look at queue.h from BSD CPP macros, entirely. No, thanks.

Just as an anecdote, in one of my university classes we had the assignment of writing and optimizing a memory allocator. When I switched from using structs to using pointer arithmetic in macros, I gained a significant performance boost, even though the in-memory data was exactly the same.

were you compiling with optimizations on?

Re: Show HN: C library of generic, reference-counted data structures

#36

Post by nitrogen »

zht wrote: post #34
nitrogen wrote: post #33

Earlier quoted context omitted.

Just as an anecdote, in one of my university classes we had the assignment of writing and optimizing a memory allocator. When I switched from using structs to using pointer arithmetic in macros, I gained a significant performance boost, even though the in-memory data was exactly the same.

were you compiling with optimizations on?

Yes, gcc -O2 on Opteron I believe (it was a while ago).

Re: Show HN: C library of generic, reference-counted data structures

#37

Post by mappu »

theck01 wrote: post #29
mappu wrote: post #14

Was there a rationale to choosing performActionOnStruct() names instead of the perhaps-more-idiomatic struct_perform_action() style? I strongly advise against putting identifiers like release() and getCString() in the global namespace, that's probably not the wisest idea if you plan to use libraries other than your own.

Some bad habits from Java are the only reason. I thought about having obrelease and obgetCString. Putting ob at the beginning of every function seems like overkill, and I don't like that only some functions had would have ob at the beginning if I didn't do a global name change. Any suggestions?

> Putting ob at the beginning of every function seems like overkill

That's "C-style namespaces" - really the only sane way to avoid an identifier collision, sorry.

Re: Show HN: C library of generic, reference-counted data structures

#38

Post by mtdewcmu »

ambrop7 wrote: post #23
cmccabe wrote: post #9

It's nice that you made these available. You might also want to look at queue.h from BSD (see http://fxr.watson.org/fxr/source/sys/queue.h ) and tree.h ( http://www.freebsd.org/cgi/cvsweb.cgi/src/sys/sys/tree.h ), single-file "libraries" that can generate a few different kinds of linked list and binary tree. These don't require typecasting at all, since they generate functions for your particular type. They are also…

Intrusive data structures are indeed more powerful. I made my own instrusive AVL-tree which can be found here [1] and an example here [2]. There's also the extra feature that the concept of a "link" is abstracted, so you can for example build a compressed AVL-tree inside an array using array indices instead of pointers, which don't break when the array is reallocated. It's also built in a different way than this usua…

I don't see anything inherently broken about null-terminated strings. It means that the smallest string that can be represented is a single byte, and the largest string that can be represented is unlimited. By mixing in an integer, you're expanding the smallest string and placing an arbitrary limit on the largest string. If the integer and string data are mixed in a struct, then strings pack much less tightly, not just because of the space taken up by the integer, but also because it needs to be aligned. Most of the things you'd want to do with a string are O(n) anyway, like print to the terminal. Null-terminated strings aren't perfect for every use, but no representation is, and C doesn't prevent you from using a different representation when it's more appropriate. If you're writing a parser, then that's a more demanding application than usual, and you ought not feel locked into using the default representation.

Re: Show HN: C library of generic, reference-counted data structures

#39

Post by cmccabe »

wrl wrote: post #19
cmccabe wrote: post #9

It's nice that you made these available. You might also want to look at queue.h from BSD (see http://fxr.watson.org/fxr/source/sys/queue.h ) and tree.h ( http://www.freebsd.org/cgi/cvsweb.cgi/src/sys/sys/tree.h ), single-file "libraries" that can generate a few different kinds of linked list and binary tree. These don't require typecasting at all, since they generate functions for your particular type. They are also…

Should you ever need said macros, I've written a set: https://github.com/wrl/wwrl/blob/master/vector.h

Thanks, that's interesting. I would probably add some kind of callback to free individual elements if I ended up using this. A lot of the boilerplate when managing resizable arrays in C ends up being making sure you properly dispose of elements. Or at least it was for me when I last did this.

Re: Show HN: C library of generic, reference-counted data structures

#40

Post by cmccabe »

pmjordan wrote: post #22
ExpiredLink wrote: post #20

Earlier quoted context omitted.

> You might also want to look at queue.h from BSD CPP macros, entirely. No, thanks.

I'm not a fan of macros either, which is why I've ended up implementing hybrid C data structures, with the logic in functions, and some optional type helpers in macros: https://github.com/pmj/genccont Anyway, these are largely intrusive and don't do reference counting, but that can be seen as an advantage or disadvantage, depending on the situation. (I use these heavily in kernel code) The hash tables (chaining and o…

Well, this is a good effort. I think you are quite right to leave out reference counting. Reference counting is something that you should pay for only if you need it.

I don't really understand the fear of macros. void pointers are much scarier than macros, since they open you up to the threat of bugs going undetected by the type system.

You're not by any chance maintaining one of those much-maligned "driver portability" layers, are you?

Post reply on HN