command_buffer: Implement IdAllocator by recording ranges in an AVL tree

command_buffer: Implement IdAllocator by recording ranges in an AVL tree

Implement IdAllocator by keeping track of used id ranges instead of
individual ids. This should make allocating big amount of ids scale a
bit better.

Store the ranges in a tree where nodes store the range as closed
interval (min, max). The tree is an AVL tree with the min entry as the
key. All represented ranges are maximal, eg. if the node is in the tree,
it represents the complete contiguous id range starting at |min| and
ending at |max|, inclusive.

BUG=344330

[Kimmo Kinnunen, 2014-10-31 13:59:21]

Alternative to https://codereview.chromium.org/692073002/ , maybe a bit more
'clean' in some sense.
Using std::map was not that concise

[Kimmo Kinnunen, 2014-10-31 14:02:08]

kkinnunen@nvidia.com changed reviewers:
+ vmiura@chromium.org

[Kimmo Kinnunen, 2014-10-31 14:02:08]

So I did this related to path rendering. This can be refactored to contain stuff
only of interest without path rendering, if it would be useful to be reviewed
before path rendering work. What would be useful is to understand which one is
preferred: the one that uses std::map, this one with custom binary tree or
nothing at all (abandon the patches)

[vmiura, 2015-01-08 19:46:44]

vmiura@chromium.org changed reviewers:
+ dyen@chromium.org

[David Yen, 2015-03-13 23:48:49]

On 2014/10/31 14:02:08, Kimmo Kinnunen wrote:
> So I did this related to path rendering. This can be refactored to contain
stuff
> only of interest without path rendering, if it would be useful to be reviewed
> before path rendering work. What would be useful is to understand which one is
> preferred: the one that uses std::map, this one with custom binary tree or
> nothing at all (abandon the patches)

Since the other CL has landed, should we close this one?

[Kimmo Kinnunen, 2015-03-15 10:58:28]

kkinnunen@nvidia.com changed reviewers:
- dyen@chromium.org, vmiura@chromium.org