Use red-black-tree in zone_malloc

[devreal]

Currently, zone_malloc iterates linearly over its blocks, leading to O(N) complexity and significant overhead if all blocks are taken. We now use a red-black-tree to order lists of free blocks in a binary search tree. Lookup, insert, and delete are log(N). If all blocks are taken lookup is constant.

When allocating memory, we look for blocks or the requested size or the next larger size. In the latter case, the block is split and put back into the tree, potentially allocating a new node. When releasing a block, it is either inserted directly or merged with its predecessor/successor blocks, which are then removed and reinserted as a larger block.

In the previous scheme, freeing was of O(1) complexity, which is now O(log(N)). However, the better worst-case complexity will amortize this. Plus, using a binary search tree will help reuse of same-size fragments and avoids splitting larger segements when possible.

RB trees have lower average complexity than AVL trees and are widely used (C++ std::map, Linux kernel allocator).

[bosilca]

It would be interesting to see a comparison with the current allocator.