Add `chunk` segmented data library.

common/chunkstream/buffer.go

+// Copyright 2015 The Chromium Authors. All rights reserved.
+// Use of this source code is governed by a BSD-style license that can be
+// found in the LICENSE file.
+
+package chunkstream
+
+// Buffer is a collection of ordered Chunks that can cheaply read and shifted
+// as if it were a continuous byte stream.
+//
+// A Buffer is not goroutine-safe. However, data can be Append()ed to a Buffer
+// without affecting Readers that were previously generated from it so long as
+// no data is Consume()d from the Buffer. The act of consuming data invalidates
+// any Reader state, and using a Reader constructed prior to a Consume() call
+// after the Consume() call is completed is an error and may result in a panic.

[iannucci, 2015/11/05 01:10:07]

So I think the following operations are mutually exclusive:
  * Append and Append
  * Append and Consume
  * Consume and Readers (Consume invalidates all Readers)

However, the following can happen concurrently:
  * Append and Multiple Readers
  * Multiple Readers

Right?

[dnj, 2015/11/13 23:22:03]

Yep. I'll update the documentation to be more clear on this.

+type Buffer struct {
+        // First is a pointer to the first Chunk node in the buffer.
+        first *chunkNode
+        // Last is a pointer to the last Chunk node in the buffer.
+        last *chunkNode
+
+        // size is the total number of bytes in the Buffer.
+        size int64
+
+        // fidx is the current byte offset in first.
+        fidx int
+
+        // gen is a monotonically-increasing generation number. It increases every
+        // time data is consumed from the Buffer via Consume.
+        gen int64
+}
+
+// Append adds another Chunk to the buffer.

[iannucci, 2015/11/05 01:10:07]

another Chunk -> one or more Chunks

[dnj, 2015/11/13 23:22:03]

Done.

+//
+// After completion, the Chunk is now owned by the Buffer and should not be used
+// anymore externally.
+func (b *Buffer) Append(c ...Chunk) {
+        for _, chunk := range c {
+                b.appendChunk(chunk)
+        }
+}
+
+func (b *Buffer) appendChunk(c Chunk) {
+        // Ignore/discard zero-length data.
+        if c.Len() == 0 {
+                c.Release()
+                return
+        }
+
+        cn := newChunkNode(c)
+        cn.next = nil
+        if b.last == nil {
+                // First node.
+                b.first = cn
+        } else {
+                b.last.next = cn
+        }
+        b.last = cn
+        b.size += int64(c.Len())
+}
+
+// Bytes constructs a byte slice containing the contents of the Buffer.
+//
+// This is a potentially expensive operation, and should generally be used only
+// for debugging and tests, as it defeats most of the purpose of this package.
+func (b *Buffer) Bytes() []byte {
+        if b.Len() == 0 {
+                return nil
+        }
+
+        m := make([]byte, 0, b.Len())
+        idx := b.fidx
+        for cur := b.first; cur != nil; cur = cur.next {
+                m = append(m, cur.Bytes()[idx:]...)
+                idx = 0
+        }
+        return m
+}
+
+// Len returns the total amount of data in the buffer.
+func (b *Buffer) Len() int64 {
+        return b.size
+}
+
+// FirstChunk returns the first Chunk in the Buffer, or nil if the Buffer has
+// no Chunks.
+func (b *Buffer) FirstChunk() Chunk {
+        if b.first == nil {
+                return nil
+        }
+        return b.first.Chunk
+}
+
+// Reader returns a Reader instance bound to this Buffer.
+//
+// If the limit is greater than zero, the Reader's limit will be set.

[iannucci, 2015/11/05 01:10:07]

I think this docstring is stale.

[dnj, 2015/11/13 23:22:03]

Done.

+//
+// The Reader is no longer valid after Consume is called.
+func (b *Buffer) Reader() *Reader {
+        return b.ReaderLimit(b.size)
+}
+
+// ReaderLimit constructs a Reader instance, but artifically constrains it to
+// read at most the specified number of bytes.
+//
+// This is useful when reading a subset of the data into a Buffer, as ReadFrom
+// does not allow a size to be specified.
+func (b *Buffer) ReaderLimit(limit int64) *Reader {
+        if limit > b.size {
+                limit = b.size

[iannucci, 2015/11/05 01:10:07]

hm.. why? what if you plan to Append stuff, since Append and Readers can
coexist?

[dnj, 2015/11/13 23:22:03]

Clearer with "View", but it's basically a snapshot.

+        }
+
+        return &Reader{
+                cur:  b.first,
+                cidx: b.fidx,
+                size: limit,
+
+                gen: b.gen,
+                b:   b,
+        }
+}
+
+// Consume removes the specified number of bytes from the beginning of the
+// Buffer. If Consume skips past all of the data in a Chunk is no longer needed,
+// it is Release()d.
+//
+// Consume invalidates any current Reader instances. Using a Reader generated
+// from before a Consume call is an error and will result in a panic.

[iannucci, 2015/11/05 01:10:07]

nice! glad to see this is enforced with gen :)

[dnj, 2015/11/13 23:22:03]

Removed gen. :(

+func (b *Buffer) Consume(c int64) {
+        if c == 0 {
+                return
+        }
+
+        if c > b.size {
+                panic("consuming more data than available")
+        }
+        b.size -= c
+
+        for c > 0 {
+                // Do we consume the entire chunk?
+                if int64(b.first.Len()-b.fidx) > c {
+                        // No. Advance our chunk index and terminate.
+                        b.fidx += int(c)
+                        break
+                }
+
+                n := b.first
+                c -= int64(n.Len() - b.fidx)
+                b.first = n.next
+                b.fidx = 0
+                if b.first == nil {
+                        b.last = nil
+                }
+
+                // Release our node. We must not reference it after this.
+                n.release()
+        }
+        b.gen++
+}