On 11.06.2012 20:43, Roman D. Boiko wrote: [snip]
Actually, in my case, deletions could be deferred and performed in bulk. OTOH, I will need to count how many times a string is inserted minus number of times it has been deleted. Alternatively, I could just check from time to time which strings are not needed any more (micro-GC :) ). There are many possible data structures, but the one you mentioned seems to be the most reasonable.
I meant an operation pseudo-XOR x P^ y where x is part of snapshot and y is part of diff page.
x P^ y == x when y == T.init x P^ y == y when y != T.init -- Dmitry Olshansky
