TWO HANDED INSERTION AND DELETION ALGORITHM FOR CIRCULAR BUFFER

摘要

Exemplary embodiments of the present invention disclose a method, program product, and system for selecting an item to evict and an insertion location for a new item in a circular buffer. A computer moves, in a circular buffer, in the same direction both of i) an insertion pointer to a first buffer entry, and ii) an eviction pointer to a second buffer entry that includes an item. A constant number of buffer entries is maintained between the eviction pointer and the insertion pointer. The computer responds to an eviction of the item from the second buffer entry by inserting a new item into a third buffer entry. The third buffer entry is located such that the third buffer entry is pointed to by the eviction pointer before being pointed to by the insertion pointer, as the eviction pointer and the insertion pointer continue to move around the circular buffer.

主权项

1. A method for selecting an eviction location of an item to evict and an insertion location for a new item in a circular buffer, the method comprising the steps of:in a circular buffer:
moving, by one or more processors, in the same direction both of i) an insertion pointer to a first buffer entry, and ii) an eviction pointer to a second buffer entry that includes a first item, such that a constant number of buffer entries is maintained between the eviction pointer and the insertion pointer; and responsive to an eviction of the first item from the second buffer entry, inserting, by the one or more processors, a new item into a third buffer entry that is located such that the third buffer entry is pointed to by the eviction pointer before being pointed to by the insertion pointer as the eviction pointer and the insertion pointer continue to move around the circular buffer.