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