1 // Copyright 2009 The Go Authors. All rights reserved. 2 // Use of this source code is governed by a BSD-style 3 // license that can be found in the LICENSE file. 4 5 package util 6 7 // This a copy of Go std bytes.Buffer with some modification 8 // and some features stripped. 9 10 import ( 11 "bytes" 12 "io" 13 ) 14 15 // smallBufferSize is an initial allocation minimal capacity. 16 const smallBufferSize = 64 17 const maxInt = int(^uint(0) >> 1) 18 19 // A Buffer is a variable-sized buffer of bytes with Read and Write methods. 20 // The zero value for Buffer is an empty buffer ready to use. 21 type Buffer struct { 22 buf []byte // contents are the bytes buf[off : len(buf)] 23 off int // read at &buf[off], write at &buf[len(buf)] 24 } 25 26 // Bytes returns a slice of the contents of the unread portion of the buffer; 27 // len(b.Bytes()) == b.Len(). If the caller changes the contents of the 28 // returned slice, the contents of the buffer will change provided there 29 // are no intervening method calls on the Buffer. 30 func (b *Buffer) Bytes() []byte { return b.buf[b.off:] } 31 32 // String returns the contents of the unread portion of the buffer 33 // as a string. If the Buffer is a nil pointer, it returns "<nil>". 34 func (b *Buffer) String() string { 35 if b == nil { 36 // Special case, useful in debugging. 37 return "<nil>" 38 } 39 return string(b.buf[b.off:]) 40 } 41 42 // Len returns the number of bytes of the unread portion of the buffer; 43 // b.Len() == len(b.Bytes()). 44 func (b *Buffer) Len() int { return len(b.buf) - b.off } 45 46 // Truncate discards all but the first n unread bytes from the buffer. 47 // It panics if n is negative or greater than the length of the buffer. 48 func (b *Buffer) Truncate(n int) { 49 if n == 0 { 50 b.Reset() 51 return 52 } 53 if n < 0 || n > b.Len() { 54 panic("leveldb/util.Buffer: truncation out of range") 55 } 56 b.buf = b.buf[:b.off+n] 57 } 58 59 // Reset resets the buffer so it has no content. 60 // b.Reset() is the same as b.Truncate(0). 61 func (b *Buffer) Reset() { 62 b.buf = b.buf[:0] 63 b.off = 0 64 } 65 66 // tryGrowByReslice is a inlineable version of grow for the fast-case where the 67 // internal buffer only needs to be resliced. 68 // It returns the index where bytes should be written and whether it succeeded. 69 func (b *Buffer) tryGrowByReslice(n int) (int, bool) { 70 if l := len(b.buf); n <= cap(b.buf)-l { 71 b.buf = b.buf[:l+n] 72 return l, true 73 } 74 return 0, false 75 } 76 77 // grow grows the buffer to guarantee space for n more bytes. 78 // It returns the index where bytes should be written. 79 // If the buffer can't grow it will panic with bytes.ErrTooLarge. 80 func (b *Buffer) grow(n int) int { 81 m := b.Len() 82 // If buffer is empty, reset to recover space. 83 if m == 0 && b.off != 0 { 84 b.Reset() 85 } 86 // Try to grow by means of a reslice. 87 if i, ok := b.tryGrowByReslice(n); ok { 88 return i 89 } 90 if b.buf == nil && n <= smallBufferSize { 91 b.buf = make([]byte, n, smallBufferSize) 92 return 0 93 } 94 c := cap(b.buf) 95 if n <= c/2-m { 96 // We can slide things down instead of allocating a new 97 // slice. We only need m+n <= c to slide, but 98 // we instead let capacity get twice as large so we 99 // don't spend all our time copying. 100 copy(b.buf, b.buf[b.off:]) 101 } else if c > maxInt-c-n { 102 panic(bytes.ErrTooLarge) 103 } else { 104 // Not enough space anywhere, we need to allocate. 105 buf := makeSlice(2*c + n) 106 copy(buf, b.buf[b.off:]) 107 b.buf = buf 108 } 109 // Restore b.off and len(b.buf). 110 b.off = 0 111 b.buf = b.buf[:m+n] 112 return m 113 } 114 115 // Alloc allocs n bytes of slice from the buffer, growing the buffer as 116 // needed. If n is negative, Alloc will panic. 117 // If the buffer can't grow it will panic with bytes.ErrTooLarge. 118 func (b *Buffer) Alloc(n int) []byte { 119 if n < 0 { 120 panic("leveldb/util.Buffer.Alloc: negative count") 121 } 122 m, ok := b.tryGrowByReslice(n) 123 if !ok { 124 m = b.grow(n) 125 } 126 return b.buf[m:] 127 } 128 129 // Grow grows the buffer's capacity, if necessary, to guarantee space for 130 // another n bytes. After Grow(n), at least n bytes can be written to the 131 // buffer without another allocation. 132 // If n is negative, Grow will panic. 133 // If the buffer can't grow it will panic with bytes.ErrTooLarge. 134 func (b *Buffer) Grow(n int) { 135 if n < 0 { 136 panic("leveldb/util.Buffer.Grow: negative count") 137 } 138 m := b.grow(n) 139 b.buf = b.buf[:m] 140 } 141 142 // Write appends the contents of p to the buffer, growing the buffer as 143 // needed. The return value n is the length of p; err is always nil. If the 144 // buffer becomes too large, Write will panic with bytes.ErrTooLarge. 145 func (b *Buffer) Write(p []byte) (n int, err error) { 146 m, ok := b.tryGrowByReslice(len(p)) 147 if !ok { 148 m = b.grow(len(p)) 149 } 150 return copy(b.buf[m:], p), nil 151 } 152 153 // MinRead is the minimum slice size passed to a Read call by 154 // Buffer.ReadFrom. As long as the Buffer has at least MinRead bytes beyond 155 // what is required to hold the contents of r, ReadFrom will not grow the 156 // underlying buffer. 157 const MinRead = 512 158 159 // ReadFrom reads data from r until EOF and appends it to the buffer, growing 160 // the buffer as needed. The return value n is the number of bytes read. Any 161 // error except io.EOF encountered during the read is also returned. If the 162 // buffer becomes too large, ReadFrom will panic with bytes.ErrTooLarge. 163 func (b *Buffer) ReadFrom(r io.Reader) (n int64, err error) { 164 for { 165 i := b.grow(MinRead) 166 b.buf = b.buf[:i] 167 m, e := r.Read(b.buf[i:cap(b.buf)]) 168 if m < 0 { 169 panic("leveldb/util.Buffer.ReadFrom: reader returned negative count from Read") 170 } 171 172 b.buf = b.buf[:i+m] 173 n += int64(m) 174 if e == io.EOF { 175 return n, nil // e is EOF, so return nil explicitly 176 } 177 if e != nil { 178 return n, e 179 } 180 } 181 } 182 183 // makeSlice allocates a slice of size n. If the allocation fails, it panics 184 // with bytes.ErrTooLarge. 185 func makeSlice(n int) []byte { 186 // If the make fails, give a known error. 187 defer func() { 188 if recover() != nil { 189 panic(bytes.ErrTooLarge) 190 } 191 }() 192 return make([]byte, n) 193 } 194 195 // WriteTo writes data to w until the buffer is drained or an error occurs. 196 // The return value n is the number of bytes written; it always fits into an 197 // int, but it is int64 to match the io.WriterTo interface. Any error 198 // encountered during the write is also returned. 199 func (b *Buffer) WriteTo(w io.Writer) (n int64, err error) { 200 if b.off < len(b.buf) { 201 nBytes := b.Len() 202 m, e := w.Write(b.buf[b.off:]) 203 if m > nBytes { 204 panic("leveldb/util.Buffer.WriteTo: invalid Write count") 205 } 206 b.off += m 207 n = int64(m) 208 if e != nil { 209 return n, e 210 } 211 // all bytes should have been written, by definition of 212 // Write method in io.Writer 213 if m != nBytes { 214 return n, io.ErrShortWrite 215 } 216 } 217 // Buffer is now empty; reset. 218 b.Reset() 219 return 220 } 221 222 // WriteByte appends the byte c to the buffer, growing the buffer as needed. 223 // The returned error is always nil, but is included to match bufio.Writer's 224 // WriteByte. If the buffer becomes too large, WriteByte will panic with 225 // bytes.ErrTooLarge. 226 func (b *Buffer) WriteByte(c byte) error { 227 m, ok := b.tryGrowByReslice(1) 228 if !ok { 229 m = b.grow(1) 230 } 231 b.buf[m] = c 232 return nil 233 } 234 235 // Read reads the next len(p) bytes from the buffer or until the buffer 236 // is drained. The return value n is the number of bytes read. If the 237 // buffer has no data to return, err is io.EOF (unless len(p) is zero); 238 // otherwise it is nil. 239 func (b *Buffer) Read(p []byte) (n int, err error) { 240 if b.off >= len(b.buf) { 241 // Buffer is empty, reset to recover space. 242 b.Reset() 243 if len(p) == 0 { 244 return 245 } 246 return 0, io.EOF 247 } 248 n = copy(p, b.buf[b.off:]) 249 b.off += n 250 return 251 } 252 253 // Next returns a slice containing the next n bytes from the buffer, 254 // advancing the buffer as if the bytes had been returned by Read. 255 // If there are fewer than n bytes in the buffer, Next returns the entire buffer. 256 // The slice is only valid until the next call to a read or write method. 257 func (b *Buffer) Next(n int) []byte { 258 m := b.Len() 259 if n > m { 260 n = m 261 } 262 data := b.buf[b.off : b.off+n] 263 b.off += n 264 return data 265 } 266 267 // ReadByte reads and returns the next byte from the buffer. 268 // If no byte is available, it returns error io.EOF. 269 func (b *Buffer) ReadByte() (c byte, err error) { 270 if b.off >= len(b.buf) { 271 // Buffer is empty, reset to recover space. 272 b.Reset() 273 return 0, io.EOF 274 } 275 c = b.buf[b.off] 276 b.off++ 277 return c, nil 278 } 279 280 // ReadBytes reads until the first occurrence of delim in the input, 281 // returning a slice containing the data up to and including the delimiter. 282 // If ReadBytes encounters an error before finding a delimiter, 283 // it returns the data read before the error and the error itself (often io.EOF). 284 // ReadBytes returns err != nil if and only if the returned data does not end in 285 // delim. 286 func (b *Buffer) ReadBytes(delim byte) (line []byte, err error) { 287 slice, err := b.readSlice(delim) 288 // return a copy of slice. The buffer's backing array may 289 // be overwritten by later calls. 290 line = append(line, slice...) 291 return 292 } 293 294 // readSlice is like ReadBytes but returns a reference to internal buffer data. 295 func (b *Buffer) readSlice(delim byte) (line []byte, err error) { 296 i := bytes.IndexByte(b.buf[b.off:], delim) 297 end := b.off + i + 1 298 if i < 0 { 299 end = len(b.buf) 300 err = io.EOF 301 } 302 line = b.buf[b.off:end] 303 b.off = end 304 return line, err 305 } 306 307 // NewBuffer creates and initializes a new Buffer using buf as its initial 308 // contents. It is intended to prepare a Buffer to read existing data. It 309 // can also be used to size the internal buffer for writing. To do that, 310 // buf should have the desired capacity but a length of zero. 311 // 312 // In most cases, new(Buffer) (or just declaring a Buffer variable) is 313 // sufficient to initialize a Buffer. 314 func NewBuffer(buf []byte) *Buffer { return &Buffer{buf: buf} } 315