Linux Operating System Source Code: IBM Patches

Uses treaps, a randomized search tree for expected O(1) rotations upon insertion and deletion from accounting structures. Also uses two trees for searching on different keys, and depth-first-search exhaustive search on a restricted tree (where the restriction is enforced in logarithmic time) to implement alignment and address constrained allocation.

Note: The relevance of this patch is low, given that the machine demonstrating efficiency issues with the stock kernel's implementation of this system has not gone to market. Some strong opposition has been encountered from this subsystem's original author. It is, however, highly effective: the machines with heavy boot-time allocation activity and hostile memory maps had their boot times reduced by approximately 2 minutes with this patch.

I am still actively maintaining it in case this issue arises again, or in the event the additional expressiveness with respect to obliviousness to address ordering or intertwining of memory regions belonging to nodes is needed.