Tree.h in OpenBSD: dependency-free intrusive binary tree

r/C_Programming • u/slacka123 • Apr 09 '21

Tree.h in OpenBSD: dependency-free intrusive binary tree Project

https://github.com/openbsd/src/blob/master/sys/sys/tree.h

90 Upvotes

99% Upvoted

u/slacka123 Apr 09 '21 edited Apr 09 '21

Documentation can be found under "NOTES" here: https://man.openbsd.org/tree.3

The author of this, Niels Provos, is now the head of security at Stripe. He wrote it when he was a PhD student at the University of Michigan.

Also, there is a type safe version here: https://github.com/FRRouting/frr/blob/master/lib/typerb.h

6

u/sunflsks Apr 09 '21

God bless openbsd documentation

u/attractivechaos Apr 09 '21

I was using C++ for years because I needed generic containers but I didn't know how to implement those in C without sacrificing performance. Then I found tree.h in 2008. That was an eye-opening experience. I didn't only learn the macro tricks but was also drawn to its independence and small code size. Tree.h has profoundly shaped my programming practice in the coming years and won me back to the C world. A true masterpiece.

5

u/MajorMalfunction44 Apr 09 '21

While I haven't looked at tree.h yet, the Linux kernel uses intrusive containers everywhere, almost exclusively IIRC. I also use intrusive structure in my own C code because it makes the intrusive structure type-independent, so you're not dealing with those details at implementation time.

14

u/fluffynukeit Apr 09 '21

Can you expand on this in more detail? What about it was eye opening? What misconceptions did you have before then? Were you aware of intrusive containers at the time, and if so is there something about tree.h that is especially done well?

Honestly, looking at the source code, I see a macro soup. Intrusive containers is one way to get generic containers in C, but to me it is not obviously superior to templates, so I wonder how it motivated you to come back to a language without templates. It must have been something really special but I either don't see it yet or simply have a different opinion.

10

u/attractivechaos Apr 09 '21

Can you expand on this in more detail? What about it was eye opening? What misconceptions did you have before then? Were you aware of intrusive containers at the time, and if so is there something about tree.h that is especially done well?

Looking at tree.h now, I don't see something that exciting, but back in 2008, it was my first exposure to macro tricks. Before that, I thought void* was the only sensible solution but it is awkward and inefficient. I really mastered the concept of intrusive data structures much later when I implemented my own intrusive AVL. Another thing about tree.h, as I said, is its near minimalist and independence. I used to develop large projects with interconnected components. Now I tend to break them down to fully isolated parts. At least to me, that is a much better strategy.

Honestly, looking at the source code, I see a macro soup. Intrusive containers is one way to get generic containers in C, but to me it is not obviously superior to templates

In my view, the main purpose of intrusive containers is not for generic programming, but for the flexibility of memory control. Generic program is only a side effect. A key advantage of intrusive containers is that you don't need heap allocation in the library code. This can be critical to kernel and allocator development and may help performance for certain workloads. Intrusive containers and templates are orthogonal. You can use them together. Boost has a component for that.

I wonder how it motivated you to come back to a language without templates. It must have been something really special but I either don't see it yet or simply have a different opinion.

Well, we can have such C vs C++ debates for ages. For me, template is pretty much the only thing I need from C++. Why carry the whole C++ bag when I can emulate templates in C (albeit in a less elegant way)? With C, I end up with more portable code, worry less about compatibility issues and make my libraries accessible to more developers.

4

u/fluffynukeit Apr 09 '21

Thank you for taking the time to respond. I didn’t appreciate the memory control aspect. I also feel like templates (and function overloading) are the only things I need/want from c++.

3

u/CreideikiVAX Apr 09 '21

Have you yet discovered the equally excellent and useful queue.h?

The BSD header files are just so damn useful.

I do wish that we could get OpenBSD's pledge() and unveil() facilities in such similarly easy to use forms on other systems.

1

u/jonahharris Apr 10 '21

Shaped your programming practice? I’d say - evidenced by all your awesome single-header implementations :)

u/fourier54 Apr 09 '21

Noob question, is it a good practice to use macros so heavily?

7

u/SuspiciousScript Apr 09 '21

It's necessary for (more) typesafe generics like this in C.

5

u/MDV106 Apr 09 '21

I guess heavy-use is okay if the code is not part of a user interface and performance is top priority and the person writing the code is very experienced. For the less experienced, it is probably better to use inline functions where you can.

u/sparc64_ Apr 09 '21

I love tree.h ... their splay trees were something I never knew I needed until I experimented with it. And blazingly fast. As is BSD’s queue.h, which provides linked lists and queues that are fairly robust.