Hacker News Reader

Comment by AndyKelley | Hacker News Reader

The thing I miss most in C when I don't cheat and use a couple C++ features is templates. Specifically, a dynamically sized List implementation that is type-generic.

If you do this in pure C, you have to pick your poison:

1. preprocessor abuse

2. void *

3. multiple redundant implementations of the data structure

Dynamically sized lists are used so often, that this tends to be a problem in almost every C project. I wonder what the author's solution is to this dilemma.

View on HN

BAH!

4. The "intrusive" containers, but of course.

The one true way to do it in C.

For one, you can keep items in multiple containers, all being on equal footing. None of that typical C++ mess, when this list is a primary storage for items, and those maps are secondary indexes, all sprinkled evenly with iterators. Intrusive containers don't own items, they merely organize them, which is exactly the right way to go about it.

For two, the actual code for container operations is as abstract and on-point as it gets as it focuses solely on "weaving" items into and out of a container rather than on other things, like de/allocating supporting structures.

For three, you get no heap activity when adding/removing items to/from a container. This means that if you already have the items, you can always arrange them into a collection. This also eliminates a lot of error handling code, leading to a simpler code.

Obviously, this is not limited to just linked lists.

[1] http://www.makelinux.net/ldd3/chp-11-sect-5 (

Yes yes! Yes! It saddens me that this extremely useful idiom is not more widely taught. It's a beautiful, simple concept that works for so many things.

What is an intrusive container?

A technique commonly used in C, for example in the Linux kernel. You embed "links" to other nodes in your structs, and find the struct from the link based on offsetof. Linux kernel uses linked lists and red-black trees this way. Probably other data structures too.

Intrusive containers are cache friendly and typically require no dynamic allocations (in addition to allocating the data itself).

See the link in the post above for more about linked lists in the linux kernel.

Interesting. At first I thought you were claiming this technique made linked lists cache friendly. After looking at it, I have concluded you meant merely that the next and prev pointers are near your data. Am I understanding you correctly?

That's my understanding too. Instead of going to your data structure, and then dereferencing a pointer to your data, after going to your data structure, you're already there.

Yes, there's one pointer chase less when you don't have a pointer from the link node to the data, but you can get it with offsetof. This can save a significant number of cache misses in some algorithms.

It is a container that intrudes on your data structure. For example in a linked list the next pointer is inside your structure instead of your data structure being wrapped in a node type.

The two other responses already described what intrusive containers are. Have a look at https://troydhanson.github.io/uthash/ to see an implementation of them that I personally like and use in my C projects. It's really simple to have a struct that is indexed by multiple keys by basically just adding two UT_hash_handle values to your struct and then using the uthash functions. On top of that, it's a really nice implementation that is completely self-contained in a single C header file.

Are you aware of Boost intrusive containers?

I use this method but never heard that name before. Many uses are unfortunately not type safe, although it is possible to use a combination of macros and inline functions to get type safety with this method.

One can implement linked lists as you describe in a C++ fashion using multiple inheritance. The LLVM project has many examples of this using the ilist_node class [1], e.g. [2].

Between using preprocessor directives in C and multiple inheritance in C++ (comes with associated complexity in the resulting client code), I'd always pick the latter.

[1] https://github.com/llvm-mirror/llvm/blob/release_37/include/... [2] https://github.com/llvm-mirror/llvm/blob/release_37/include/...

How do you put an object on multiple different lists with this technique?

E.g. in FreeBSD an mbuf can be on two lists at once: http://svnweb.freebsd.org/base/head/sys/sys/mbuf.h?revision=...

My solution is to write Jinja templates of C source files: https://github.com/mcinglis/libarray

Libarray (and my other C libraries; Libvec etc) have served me very well on a 20k LOC project. With ~150 source files, the entire project builds from fresh in 20 seconds on a i7-2620M. Rebuilds are super-fast; with proper Makefile specification, there's no need to rerender/recompile the templated files.

AGPL? Never. Ever.

My reasons are made clear in the README. I don't want to contribute to nonfree software. It's pretty simple.

Businesses who want to use my work in nonfree software are welcome to get in touch to negotiate such a license.

IMHO, for anyone who has seriously considered the morality and ethics of software licensing options, the AGPL is the obvious choice. I'm surprised it isn't more popular. It was a shame large donors strongarmed the FSF into splitting it from the GPL, and that the FSF kept pushing the GPL as it's go-to license.

Just use queue.h, as do all the BSDs.

https://github.com/freebsd/freebsd/blob/master/sys/sys/queue...

There is also STB stretchy buffer, popular with game devs. https://github.com/nothings/stb/blob/master/stretchy_buffer....

The trade-off with templates is much slower compilation times. Often slow C++ compile times can be traced to enthusiastic use of templated types, particularly given that standard types like std::string are often defined as templates themselves.

Macros are a reasonable way to solve this problem. A good example is BSD's sys/queue.h:

http://cvsweb.openbsd.org/cgi-bin/cvsweb/src/sys/sys/queue.h...

I think it's GPL, so it's not for everyone, but the last time I did something in C, I came across Judy, which is totally awesome for what it does.

Apparently, the implementation is complex enough to drive an ordinary mortal like myself insane, but it is hidden behind a very simple interface, and it is blazingly fast. It only gave me problems when trying to use boehmgc, because it does not detect pointers stored in a Judy tree.

Reply on news.ycombinator.com