Augmented red-black trees

Please consider subscribing to LWN

Subscriptions are the lifeblood of LWN.net. If you appreciate this content and would like to see more of it, your subscription will help to ensure that LWN continues to thrive. Please visit this page to join up and keep LWN on the net.

Venkatesh's patch (which was one of the first things merged for 2.6.35) implements the concept of "augmented rbtrees." Such a tree works very much like an ordinary rbtree, with the exception that it keeps additional information in each node. That information, almost certainly, is a function of any child nodes in the tree - the maximum key value among all children, for example. Since users of rbtrees must write their own search functions anyway, they can easily take advantage of this extra information to optimize searches.

Users of augmented rbtrees must define an augment_cb() callback with this prototype:

    void (*augment_cb)(struct rb_node *node);

When the tree is initialized, the callback should be stored in its root node:

    struct rb_root my_root = RB_AUGMENT_ROOT(my_augment_cb);

Thereafter, the augment_cb() callback will be invoked whenever the value of one (or both) of a node's children might have changed. The callback can then update the node's additional information to match the new tree topology. The callback will be invoked from insert and delete operations - anything which might change the tree - so rbtree users should ensure that nodes are in a consistent state before inserting them.

Callbacks are not called recursively up the tree. So if a change to a node's augmented value might ripple upward, the augment_cb() callback must work its way up the tree and make the requisite updates. Note that a recursive call on the parent node is probably not a good idea unless the tree is known to be extremely shallow.

As of this writing, the PAT code is the only in-tree user of this functionality, but others seem likely to appear now that this feature is globally available.