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

[Dimitris Papastamos]

On Tue, May 03, 2011 at 12:26:51PM +0100, Mark Brown wrote:
> On Tue, May 03, 2011 at 12:24:24PM +0100, Dimitris Papastamos wrote:
> 
> > Yes, I will look into that.  The block size will still need to be to set
> > to determine the maximum size of the variable length block.  Otherwise
> > there is no way to determine if we need to allocate a new node for the
> > rbtree or not.
> 
> I don't think that's required - if we just allocate blocks containing
> only contiguous registers we don't need to worry about it, the decision
> is just based on if there's an adjacent register we know about it.

So at init time, we populate the tree based on the defaults register
map.  Each block contains only contiguous registers.  If there exist
two nodes A and B, containing adjacent blocks meaning that the last
register in A's block is one before the first register in B's block, we can
eliminate one node and merge the two blocks into the other node.

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.

Of course we can also avoid merging blocks altogether, and just consider
blocks as full.

Thanks,
Dimitris