Re: Free Space Map data structure

On Tue, 2008-04-08 at 13:38 +0300, Hannu Krosing wrote:
> On Tue, 2008-04-08 at 12:26 +0300, Hannu Krosing wrote:
>
> > Probably we could do without sparse files, if we find an efficient way
> > to compute the "add order" of leaf and parent pages for above algorithm.
>
> if we always add only the minimal needed set of parents then the order
> will look something like
>
> 1: 0
> 2: 1
> 3: (0-1)
> 4: 2
> 5: (0-3)
> 6: 3
> 7: (2-3)
> 8: 4
> 9: (0-7)
> 10: 5
> 11: (4-5)
> 12. 6
> 13: (4-7)
> 13: 7
> 14: (6-7)
>
> seems pretty regular :)
>
> and is probably easy to expand into pages
>
> ------------
> Will work on this a little more

index tree node binary mask mask bits
0 0 00000
1 0-1 0000? 1
2 1 00001
3 0-3 000?? 2
4 2 00010
5 2-3 0001? 1
6 3 00011
7 0-7 00??? 3
8 4 00100
9 4-5 0010? 1
10 5 00101
11 4-7 001?? 2
12 6 00110
13 6-7 0011? 1
14 7 00111
15 0-15 0???? 4
16 8 01000
17 8-9 0100? 1
18 9 01001
19 8-11 010?? 2
20 10 01010
21 10-11 0101? 1
22 11 01011
23 8-15 01??? 3
24 12 01100
25 12-13 0110? 1
26 13 01101
27 12-15 011?? 2
28 14 01110
29 14-15 0111? 1
30 15 01111
31 0-31 ????? 5
...32........16.........10000.........

seems to be a simple pattern

for each node row (each second row) take binary representation of
next row, start from end and replace all zeros up to and including
rightmost one with mask bits.

mask 011?? means (data and 11100) == 01100

I will try to work out some experimental/sample code in python for find
and update in the evening.

---------------
Hannu