StackOverflow2013

Note that there are some explanatory texts on larger screens.

plurals

POLooking for a data structure with persistent sequential indexes
text
Body
copied!<p>I am looking for a data structure that works essentially like this:</p> <ul> <li>The structure is an ordered sequence of values.</li> <li>Each inserted value claims an index that is larger than the previous index, will not be reused and will not shift (it is <em>persistent</em>).</li> <li>All items before a particular index can be removed from the structure in one operation.</li> <li>All items that are still alive are reachable by their index.</li> <li>All items between two indexes can be retrieved in a batch. (If they could be retrieved while a new item is being added, that would also be great.)</li> </ul> <p>The above is my best implementation guess. The properties I actually want are to be able to have a consumer which keeps a sort of bookmark value and can read the new items without missing out, and to be able to clear out items before a certain timestamp. However, the data structure need not know about the timestamp; being able to delete everything before a particular index is fine.</p> <p>The way I would implement this structure is by keeping an int of where the item count starts and then keep either a list of items directly or a list of list segments. The index being some sort of primitive integer will wrap, but not within several multiples of the realistic timespan of the program's life.</p> <p>The structure that I know of that gets closest is the particular ring buffer from <a href="http://lmax-exchange.github.com/disruptor/" rel="nofollow">the LMAX Disruptor</a>. However, that structure also blocks if the consumer gets too far behind which will not suit my purposes. The consumer is batch-oriented and may not get frequent CPU time; the Disruptor works best with dedicated logical tasks continuously working against the ring buffer.</p> <p>So the questions I'm asking are:</p> <ul> <li>Is there a name for this?</li> <li>Is there an implementation of it for C# or another language?</li> <li>Is there a better alternative for my use case?</li> </ul>

Querying!

Guidance

An individual column

Larger individual text columns get their own page to allow for proper reading.

SQuiL has stopped working due to an internal error.

If you are curious you may find further information in the browser console, which is accessible through the devtools (F12).

Reload