alexgartrell on How to Make a Computer Operating System in C/C++

Comment on How to Make a Computer Operating System in C/C++parent

Intrusive datastructures were the thing I missed most from C, but boost::intrusive satisfies my desires when it's absolutely necessary.

In general, I'm anti-boost, but I think it's a personal bias and we use the hell out of it at work to great effect. The one thing I'll give boost::intrusive over sys/queue.h is that the type system helps you a lot more to catch issues and the common case is a bit simpler (a struct that exists in a single linked list and a single hash table, for example).

I've been burned many times by something like the following

  struct foo {
    TAILQ_ENTRY(foo) lru_entry;
    TAILQ_ENTRY(foo) hash_entry;
  };
  ...
  void some_magic_func(struct foo *f) {
    TAILQ_REMOVE(static_tailq, f, hash_entry); // oops, should be lru_entry!
  }

Boost intrusive templatizes on the member as well (IIRC) and eliminates this whole class of problem.

Peaker 12y

In C, you can use a bit of macro trickery to get the same safety, e.g: by defining a 0-sized array of the some type alongside the intrusive node. Then, macros that do the "cast down" from the intrusive node to the container element can also do a type-comparison (using some trickery) between the anchor's array and the container type.

I've seen it implemented, but everyone uses the typical non-type-safe one anyway :)

I don't think I've ever had such bugs in a lot of code though, since I tend to wrap the "containerof" call with a little function like: foo_of_lru_entry and foo_of_hash_entry. A bit of boilerplate for each data structure, but worth it.

gsg 12y

You might find http://www.locklessinc.com/articles/dlist/ interesting: it describes a (perhaps excessively) clever way to do intrusive lists that gives type checking.

(Unfortunately it does rely on `typeof`, an extension.)

Comments