3 May
2011
3 May
'11
3:44 p.m.
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