Hacker News Reader

Comment by munin | Hacker News Reader

> like passing around a reference to a struct's member, then to retrieve the struct decrementing a value from the pointer + casting.

that's not weird, that's a pretty standard way to enqueue structures on singly/doubly linked lists... it's made somewhat prettier by offsetof/CONTAINING_RECORD though

View on HN

Yeah, but why?

I mean, can't you pass a reference to the whole structure instead? I prefer pointers to void* to the whole thing, with a normal cast later, instead of seeing pointer arithmetic.

I'm not a C developer, I just play around -- I've seen for example this practice used in libev, passing around extra-context along with the file-handler in events callbacks.

That seems really ugly to me, as they could have added an extra parameter for whatever context you wanted to be passed around.

It's a relatively common pattern to have a "collection" data structure (like a list or hash table) use link structs embedded inside other structs to simplify memory management. When you append to a linked list in Java, you always allocate a new Link object and then update the various pointers. Using this pattern in C, the object you want to put in a list contains a list_link_t structure, and the list library takes as arguments pointers to these structures. This may sound like an argument about convenience, but the implications of this are very significant: if you have to allocate memory, the operation can fail. So in the C version (unlike the Java one) you can control exactly in which contexts something can fail.

For example, if you want to trigger some operation after some number of second elapses, you can preallocate some structure and then just populate it and fill it in when the timeout fires. Timeouts are usually just signals or other contexts where you have no way to return failure, so it's important that it be possible to always handle that case correctly without the possibility of failing.

This pattern is sometimes called an intrusive data structure. For example, see boost::intrusive in the C++ world. It saves allocation, gives better locality, and allows various optimizations such as the ability to remove an object from a doubly-linked list in constant time.

Another way to think about all the offsetof() stuff is that it's emulating multiple inheritance in C. You can think of structures as inheriting the "trait" of being a participant in a container; the "pointer-arithmetic-and-cast" idiom to move from a container entry to the corresponding object is isomorphic to downcasting from the trait to the object that contains it.

Interestingly it is not possible to express this pattern in a generic way within Java's type system.

True - and the important point here is that this is a pattern. Like any language, to be truly fluent in C you have to understand the common idioms as well as the syntax, grammar and vocabulary.

the purpose of offsetof/CONTAINING_RECORD is so that you don't "see" the pointer arithmetic, it's safely ensconced in a macro ;)

one advantage is it produces a generic linked list API. you can write routines to traverse, add, and remove elements from the list without caring about the structure of data stored in the list. if you use offsetof, you can also have the list data for a structure at any position inside of the structure instead of the beginning. some systems do that so they can store header information at the beginning.

you can also have elements enqueued on multiple lists. you might say that if you're doing that, you have bigger problems, but sometimes shakespere got to get paid.

Check out the Linux kernel's linked list implementation for an example of it being done right. The actual workings of it are hidden behind macros that you can look at (quite simple, easy to grasp) so it's very clean to used.

Reply on news.ycombinator.com