Lock-Free Queue Index Math

Problem

Map a lock-free queue's sequence number to a slot index.

Producers and consumers share a monotonically increasing sequence number while the ring has a fixed capacity. Compute the physical slot and how many times the number has wrapped.

Return [slot, wrap_count].

Hint

Modulo gives the slot and integer division gives the lap count.

Test cases

case 1

in: [0,4]

expected: [0,0]

case 2

in: [5,4]

expected: [1,1]

case 3

in: [8,4]

expected: [0,2]

case 4

in: [3,1]

expected: [0,3]

Starter codePython

def queue_slot(sequence, capacity):
    # Your code here
    pass

4 test cases · run your code against them in the editor