27 Nov
2013
27 Nov
'13
9:33 a.m.
yes, the handling of the stability count is a bit fragile, though 64bit integers are probably enough to prevent overflows in most applications. a simple way to prevent the overflow could also be to simply subtract the minimum value of all stability counts, which could be done in O(n) by traversing the heap twice.
That's unreliable, because there's no guarantee that any particular counter is ever removed. It's quite possible still to have 0 in the queue when you reach 2^64.
in theory, yes ... though i doubt this is an issue in the real world ... especially one can do quite a lot of work before a 64bit counter overflows and if this really turns out to be a problem ... just use a larger counter ;)