[alsa-devel] [PATCH 1/2 v2] ASoC: soc-cache: block based rbtree compression

[Mark Brown]

On Tue, May 03, 2011 at 12:46:18PM +0100, Dimitris Papastamos wrote:

> We can do this yes.  One possible problem is that if we start merging
> blocks like that, in the long run we might end-up having one node with a
> very large block.  This will happen for example if we write to the
> entire register map.  In that case looking up a register will require
> O(n) time in the worst case where n is the number of registers.  If we
> however have a constant limit k on the block size, we can cut this down to
> O(klogn) in the worst case.

Summarising offline discussion for the list: if we use an array for the
data and realloc it if we need to change the node size then we keep the
O(klogn) for these cases