Linux kernel's RBT implementation has a nice trick of using the LSB bit of parent pointer as a node color. If I were to implement a RBT for my proprietary software and use the LSB as a node color bit as well, would it be considered a derived work (and have to licence my code under GPL v2.0) or independent implementation?


Copyright protects creative expression, not ideas. So feel free to use such bit twiddling tricks in your software. TBH, tagging pointers in the lower or upper bits is a fairly standard technique in low-level C.

You are of course most welcome to copy Linux' implementation into your software, but then the GPL would clearly apply.

It may be worth pointing out that some organizations want to steer very very clear of intellectual property infringement. In such a setting, even just reading open source code would be “dangerous”: (1) you might accidentally copy copyrightable aspects of the code into your software, or (2) some of the ideas and techniques you see could be patented. When such an organization would want to copy functionality from another software, it would attempt a clean-room design.


I'm sure the idea isn't original in Linux. If you rummage around in oldish data structure books (or books on assembly language programming, LISP implementations, or perhaps even in Knuth's "The Art of Computer Programming") you'll find rampant reuse of "spare" bits.

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.