On Fri, 2005-08-12 at 16:37 +0200, Peter Zijlstra wrote: > This will keep: > > |B1_j| |B1| Sum^i(|B1_i|) > -------- ~ ------ = ------------- > |B2_j| |B2| Sum^i(|B2_i|) > > however it will violate strict FIFO order within the buckets; although I > guess it won't be too bad. > Still it bothered me. So I propose the attached code to fix it. What I've done is to keep 2 proper clocks in the bucket. Each clock is a single linked cyclic list where links are slot positions bitfield encoded in the cookie; only 24 bits of uniqueness left. The code is a bit messy and totaly untested (it should explode since I wrote it around 2 in the morning) but I think the concept is sound. The 'insert before' and 'remove current' operations are implemented by swapping slots. remove current (b from 'abc'): initial swap(2,3) 1: -> [2],a 1: -> [2],a * 2: -> [3],b 2: -> [1],c 3: -> [1],c * 3: -> [3],b 3 is now free for use. insert before (d before b in 'abc') initial set 4 swap(2,4) 1: -> [2],a 1: -> [2],a 1: -> [2],a * 2: -> [3],b 2: -> [3],b 2: -> [4],d 3: -> [1],c 3: -> [1],c 3: -> [1],c 4: nil 4: -> [4],d * 4: -> [3],b leaving us with 'adbc'. The only thing is that for this to work we have to start the algorith with filled nonresident clocks. Currently it assumes: q_i = c_i/2, |B1_i| = q_i, |B2_i| = c_i - q_i. If q=0 etc., would be preferred changing the initial clocks to |B1_j| = 0 and |B2_j| = c_j should not pose any problems either. Ok, now on to putting Rahul code on top of this ;-) -- Peter Zijlstra