It's not, because it does not need to support all the operations a Rope does. It's O(1) for head and tail inserts, and log(N) (N number of blocks) for seek. So it is at least as performing, likely best, because head and tail inserts in a Rope will have to rebalance the three at some point. And it's probably 1/8 the size a rope (with all the tree operations will be needed).
On Mon, Dec 7, 2015 at 9:00 AM, Dan Cross <[email protected]> wrote: > On Mon, Dec 7, 2015 at 11:59 AM, 'Davide Libenzi' via Akaros < > [email protected]> wrote: > >> On Mon, Dec 7, 2015 at 7:40 AM, Barret Rhoden <[email protected]> >> wrote: >> >>> On 2015-12-07 at 07:32 "'Davide Libenzi' via Akaros" >>> <[email protected]> wrote: >>> > No, qpread() does not discard. Like pread(), simply reads at offset. >>> >>> In that case, let's not use the queue stuff for this. All we need is a >>> buffer and length, and hang it off the aux. >>> >> >> OK, dropped all the queue qpread() code 😐 >> But, it is not just a simple buffer. >> In general, you need to be able to build it progressively, without using >> huge-alloc-and-hope semantics. >> This is why the queue stuff was coming handy. You could just append stuff. >> I created a new growable buffer data structure, which allows O(1) writes >> at both head and tail, as well as log(N) seeks. >> As well as doing-less-allocs-than-writes thing. >> Supporting seek+read+read as well as pread, with the ability to pass in >> custom memcpy() functions, to allow it to read directly into user buffers. >> > > I hope it's a Rope. I suggested a while ago that we should have an > implementation of Ropes in our system. > https://en.wikipedia.org/wiki/Rope_(data_structure) > > -- > You received this message because you are subscribed to the Google Groups > "Akaros" group. > To unsubscribe from this group and stop receiving emails from it, send an > email to [email protected]. > To post to this group, send email to [email protected]. > For more options, visit https://groups.google.com/d/optout. > -- You received this message because you are subscribed to the Google Groups "Akaros" group. To unsubscribe from this group and stop receiving emails from it, send an email to [email protected]. To post to this group, send email to [email protected]. For more options, visit https://groups.google.com/d/optout.
