1package unsnap 2 3// copyright (c) 2014, Jason E. Aten 4// license: MIT 5 6// Some text from the Golang standard library doc is adapted and 7// reproduced in fragments below to document the expected behaviors 8// of the interface functions Read()/Write()/ReadFrom()/WriteTo() that 9// are implemented here. Those descriptions (see 10// http://golang.org/pkg/io/#Reader for example) are 11// copyright 2010 The Go Authors. 12 13import "io" 14 15// FixedSizeRingBuf: 16// 17// a fixed-size circular ring buffer. Yes, just what is says. 18// 19// We keep a pair of ping/pong buffers so that we can linearize 20// the circular buffer into a contiguous slice if need be. 21// 22// For efficiency, a FixedSizeRingBuf may be vastly preferred to 23// a bytes.Buffer. The ReadWithoutAdvance(), Advance(), and Adopt() 24// methods are all non-standard methods written for speed. 25// 26// For an I/O heavy application, I have replaced bytes.Buffer with 27// FixedSizeRingBuf and seen memory consumption go from 8GB to 25MB. 28// Yes, that is a 300x reduction in memory footprint. Everything ran 29// faster too. 30// 31// Note that Bytes(), while inescapable at times, is expensive: avoid 32// it if possible. Instead it is better to use the FixedSizeRingBuf.Readable 33// member to get the number of bytes available. Bytes() is expensive because 34// it may copy the back and then the front of a wrapped buffer A[Use] 35// into A[1-Use] in order to get a contiguous slice. If possible use ContigLen() 36// first to get the size that can be read without copying, Read() that 37// amount, and then Read() a second time -- to avoid the copy. 38 39type FixedSizeRingBuf struct { 40 A [2][]byte // a pair of ping/pong buffers. Only one is active. 41 Use int // which A buffer is in active use, 0 or 1 42 N int // MaxViewInBytes, the size of A[0] and A[1] in bytes. 43 Beg int // start of data in A[Use] 44 Readable int // number of bytes available to read in A[Use] 45 46 OneMade bool // lazily instantiate the [1] buffer. If we never call Bytes(), 47 // we may never need it. If OneMade is false, the Use must be = 0. 48} 49 50func (b *FixedSizeRingBuf) Make2ndBuffer() { 51 if b.OneMade { 52 return 53 } 54 b.A[1] = make([]byte, b.N, b.N) 55 b.OneMade = true 56} 57 58// get the length of the largest read that we can provide to a contiguous slice 59// without an extra linearizing copy of all bytes internally. 60func (b *FixedSizeRingBuf) ContigLen() int { 61 extent := b.Beg + b.Readable 62 firstContigLen := intMin(extent, b.N) - b.Beg 63 return firstContigLen 64} 65 66func NewFixedSizeRingBuf(maxViewInBytes int) *FixedSizeRingBuf { 67 n := maxViewInBytes 68 r := &FixedSizeRingBuf{ 69 Use: 0, // 0 or 1, whichever is actually in use at the moment. 70 // If we are asked for Bytes() and we wrap, linearize into the other. 71 72 N: n, 73 Beg: 0, 74 Readable: 0, 75 OneMade: false, 76 } 77 r.A[0] = make([]byte, n, n) 78 79 // r.A[1] initialized lazily now. 80 81 return r 82} 83 84// from the standard library description of Bytes(): 85// Bytes() returns a slice of the contents of the unread portion of the buffer. 86// If the caller changes the contents of the 87// returned slice, the contents of the buffer will change provided there 88// are no intervening method calls on the Buffer. 89// 90func (b *FixedSizeRingBuf) Bytes() []byte { 91 92 extent := b.Beg + b.Readable 93 if extent <= b.N { 94 // we fit contiguously in this buffer without wrapping to the other 95 return b.A[b.Use][b.Beg:(b.Beg + b.Readable)] 96 } 97 98 // wrap into the other buffer 99 b.Make2ndBuffer() 100 101 src := b.Use 102 dest := 1 - b.Use 103 104 n := copy(b.A[dest], b.A[src][b.Beg:]) 105 n += copy(b.A[dest][n:], b.A[src][0:(extent%b.N)]) 106 107 b.Use = dest 108 b.Beg = 0 109 110 return b.A[b.Use][:n] 111} 112 113// Read(): 114// 115// from bytes.Buffer.Read(): Read reads the next len(p) bytes 116// from the buffer or until the buffer is drained. The return 117// value n is the number of bytes read. If the buffer has no data 118// to return, err is io.EOF (unless len(p) is zero); otherwise it is nil. 119// 120// from the description of the Reader interface, 121// http://golang.org/pkg/io/#Reader 122// 123/* 124Reader is the interface that wraps the basic Read method. 125 126Read reads up to len(p) bytes into p. It returns the number 127of bytes read (0 <= n <= len(p)) and any error encountered. 128Even if Read returns n < len(p), it may use all of p as scratch 129space during the call. If some data is available but not 130len(p) bytes, Read conventionally returns what is available 131instead of waiting for more. 132 133When Read encounters an error or end-of-file condition after 134successfully reading n > 0 bytes, it returns the number of bytes 135read. It may return the (non-nil) error from the same call or 136return the error (and n == 0) from a subsequent call. An instance 137of this general case is that a Reader returning a non-zero number 138of bytes at the end of the input stream may return 139either err == EOF or err == nil. The next Read should 140return 0, EOF regardless. 141 142Callers should always process the n > 0 bytes returned before 143considering the error err. Doing so correctly handles I/O errors 144that happen after reading some bytes and also both of the 145allowed EOF behaviors. 146 147Implementations of Read are discouraged from returning a zero 148byte count with a nil error, and callers should treat that 149situation as a no-op. 150*/ 151// 152 153func (b *FixedSizeRingBuf) Read(p []byte) (n int, err error) { 154 return b.ReadAndMaybeAdvance(p, true) 155} 156 157// if you want to Read the data and leave it in the buffer, so as 158// to peek ahead for example. 159func (b *FixedSizeRingBuf) ReadWithoutAdvance(p []byte) (n int, err error) { 160 return b.ReadAndMaybeAdvance(p, false) 161} 162 163func (b *FixedSizeRingBuf) ReadAndMaybeAdvance(p []byte, doAdvance bool) (n int, err error) { 164 if len(p) == 0 { 165 return 0, nil 166 } 167 if b.Readable == 0 { 168 return 0, io.EOF 169 } 170 extent := b.Beg + b.Readable 171 if extent <= b.N { 172 n += copy(p, b.A[b.Use][b.Beg:extent]) 173 } else { 174 n += copy(p, b.A[b.Use][b.Beg:b.N]) 175 if n < len(p) { 176 n += copy(p[n:], b.A[b.Use][0:(extent%b.N)]) 177 } 178 } 179 if doAdvance { 180 b.Advance(n) 181 } 182 return 183} 184 185// 186// Write writes len(p) bytes from p to the underlying data stream. 187// It returns the number of bytes written from p (0 <= n <= len(p)) 188// and any error encountered that caused the write to stop early. 189// Write must return a non-nil error if it returns n < len(p). 190// 191func (b *FixedSizeRingBuf) Write(p []byte) (n int, err error) { 192 for { 193 if len(p) == 0 { 194 // nothing (left) to copy in; notice we shorten our 195 // local copy p (below) as we read from it. 196 return 197 } 198 199 writeCapacity := b.N - b.Readable 200 if writeCapacity <= 0 { 201 // we are all full up already. 202 return n, io.ErrShortWrite 203 } 204 if len(p) > writeCapacity { 205 err = io.ErrShortWrite 206 // leave err set and 207 // keep going, write what we can. 208 } 209 210 writeStart := (b.Beg + b.Readable) % b.N 211 212 upperLim := intMin(writeStart+writeCapacity, b.N) 213 214 k := copy(b.A[b.Use][writeStart:upperLim], p) 215 216 n += k 217 b.Readable += k 218 p = p[k:] 219 220 // we can fill from b.A[b.Use][0:something] from 221 // p's remainder, so loop 222 } 223} 224 225// WriteTo and ReadFrom avoid intermediate allocation and copies. 226 227// WriteTo writes data to w until there's no more data to write 228// or when an error occurs. The return value n is the number of 229// bytes written. Any error encountered during the write is also returned. 230func (b *FixedSizeRingBuf) WriteTo(w io.Writer) (n int64, err error) { 231 232 if b.Readable == 0 { 233 return 0, io.EOF 234 } 235 236 extent := b.Beg + b.Readable 237 firstWriteLen := intMin(extent, b.N) - b.Beg 238 secondWriteLen := b.Readable - firstWriteLen 239 if firstWriteLen > 0 { 240 m, e := w.Write(b.A[b.Use][b.Beg:(b.Beg + firstWriteLen)]) 241 n += int64(m) 242 b.Advance(m) 243 244 if e != nil { 245 return n, e 246 } 247 // all bytes should have been written, by definition of 248 // Write method in io.Writer 249 if m != firstWriteLen { 250 return n, io.ErrShortWrite 251 } 252 } 253 if secondWriteLen > 0 { 254 m, e := w.Write(b.A[b.Use][0:secondWriteLen]) 255 n += int64(m) 256 b.Advance(m) 257 258 if e != nil { 259 return n, e 260 } 261 // all bytes should have been written, by definition of 262 // Write method in io.Writer 263 if m != secondWriteLen { 264 return n, io.ErrShortWrite 265 } 266 } 267 268 return n, nil 269} 270 271// ReadFrom() reads data from r until EOF or error. The return value n 272// is the number of bytes read. Any error except io.EOF encountered 273// during the read is also returned. 274func (b *FixedSizeRingBuf) ReadFrom(r io.Reader) (n int64, err error) { 275 for { 276 writeCapacity := b.N - b.Readable 277 if writeCapacity <= 0 { 278 // we are all full 279 return n, nil 280 } 281 writeStart := (b.Beg + b.Readable) % b.N 282 upperLim := intMin(writeStart+writeCapacity, b.N) 283 284 m, e := r.Read(b.A[b.Use][writeStart:upperLim]) 285 n += int64(m) 286 b.Readable += m 287 if e == io.EOF { 288 return n, nil 289 } 290 if e != nil { 291 return n, e 292 } 293 } 294} 295 296func (b *FixedSizeRingBuf) Reset() { 297 b.Beg = 0 298 b.Readable = 0 299 b.Use = 0 300} 301 302// Advance(): non-standard, but better than Next(), 303// because we don't have to unwrap our buffer and pay the cpu time 304// for the copy that unwrapping may need. 305// Useful in conjuction/after ReadWithoutAdvance() above. 306func (b *FixedSizeRingBuf) Advance(n int) { 307 if n <= 0 { 308 return 309 } 310 if n > b.Readable { 311 n = b.Readable 312 } 313 b.Readable -= n 314 b.Beg = (b.Beg + n) % b.N 315} 316 317// Adopt(): non-standard. 318// 319// For efficiency's sake, (possibly) take ownership of 320// already allocated slice offered in me. 321// 322// If me is large we will adopt it, and we will potentially then 323// write to the me buffer. 324// If we already have a bigger buffer, copy me into the existing 325// buffer instead. 326func (b *FixedSizeRingBuf) Adopt(me []byte) { 327 n := len(me) 328 if n > b.N { 329 b.A[0] = me 330 b.OneMade = false 331 b.N = n 332 b.Use = 0 333 b.Beg = 0 334 b.Readable = n 335 } else { 336 // we already have a larger buffer, reuse it. 337 copy(b.A[0], me) 338 b.Use = 0 339 b.Beg = 0 340 b.Readable = n 341 } 342} 343 344func intMax(a, b int) int { 345 if a > b { 346 return a 347 } else { 348 return b 349 } 350} 351 352func intMin(a, b int) int { 353 if a < b { 354 return a 355 } else { 356 return b 357 } 358} 359 360// Get the (beg, end] indices of the tailing empty buffer of bytes slice that from that is free for writing. 361// Note: not guaranteed to be zeroed. At all. 362func (b *FixedSizeRingBuf) GetEndmostWritable() (beg int, end int) { 363 extent := b.Beg + b.Readable 364 if extent < b.N { 365 return extent, b.N 366 } 367 368 return extent % b.N, b.Beg 369} 370 371// Note: not guaranteed to be zeroed. 372func (b *FixedSizeRingBuf) GetEndmostWritableSlice() []byte { 373 beg, e := b.GetEndmostWritable() 374 return b.A[b.Use][beg:e] 375} 376