couchbase / moss / 15

pending completion

Build # 15

Build Type

push

travis-ci

Committed by

mschoch

Commit Message

<a href="https://github.com/couchbase/moss/commit/<a class=hub.com/couchbase/moss/commit/97b9354cf2cb61d76a2a4d056039c46e7d3ac3ff">97b9354cf<a href="https://github.com/couchbase/moss/commit/97b9354cf2cb61d76a2a4d056039c46e7d3ac3ff">&quot;&gt;fix issues identified by golint

Change-Id: I</a><a class="double-link" href="https://github.com/couchbase/moss/commit/<a class="double-link" href="https://github.com/couchbase/moss/commit/a95c769fc86a200a67967c168d11f422777db0a5">a95c769fc</a>">a95c769fc</a><a href="https://github.com/couchbase/moss/commit/97b9354cf2cb61d76a2a4d056039c46e7d3ac3ff">
Reviewed-on: http://review.couchbase.org/60714
Reviewed-by: Steve Yen &lt;steve.yen@gmail.com>
Tested-by: Marty Schoch <marty.schoch@gmail.com>

Run Details

31 of 31 new or added lines in 5 files covered. (100.0%)

1054 of 1150 relevant lines covered (91.65%)

35533.14 hits per line

Source File
Press 'n' to go to next uncovered line, 'b' for previous

93.48

/segment.go

//  Copyright (c) 2016 Couchbase, Inc.
//  Licensed under the Apache License, Version 2.0 (the "License");
//  you may not use this file except in compliance with the
//  License. You may obtain a copy of the License at
//    http://www.apache.org/licenses/LICENSE-2.0
//  Unless required by applicable law or agreed to in writing,
//  software distributed under the License is distributed on an "AS
//  IS" BASIS, WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either
//  express or implied. See the License for the specific language
//  governing permissions and limitations under the License.

package moss

import (
        "bytes"
        "sort"
)

// A segment is a sequence of key-val entries or operations.  A
// segment's kvs will be sorted by key when the segment is pushed into
// the collection.  A segment implements the Batch interface.
type segment struct {
        // Each key-val operation is encoded as 2 uint64's...
        // - operation (see: maskOperation) |
        //       key length (see: maskKeyLength) |
        //       val length (see: maskValLength).
        // - start index into buf for key-val bytes.
        kvs []uint64

        // Contiguous backing memory for the keys and vals of the segment.
        buf []byte

        // If this segment needs sorting, then needSorterCh will be
        // non-nil and also the first goroutine that reads successfully
        // from needSorterCh becomes the sorter of this segment.  All
        // other goroutines must instead wait on the waitSortedCh.
        needSorterCh chan bool

        // Once the sorter of this segment is done sorting the kvs, it
        // close()'s the waitSortedCh, treating waitSortedCh like a
        // one-way latch.  The needSorterCh and waitSortedCh will either
        // be nil or non-nil together.  A segment that was "born
        // sorted" will have needSorterCh and waitSortedCh as both nil.
        waitSortedCh chan struct{}

        totOperationSet   uint64
        totOperationDel   uint64
        totOperationMerge uint64
        totKeyByte        uint64
        totValByte        uint64
}

// See the OperationXxx consts.
const maskOperation = uint64(0x0F00000000000000)

// Max key length is 2^24, from 24 bits key length.
const maskKeyLength = uint64(0x00FFFFFF00000000)

// Max val length is 2^28, from 28 bits val length.
const maskValLength = uint64(0x000000000FFFFFFF)

const maskRESERVED = uint64(0xF0000000F0000000)

// newSegment() allocates a segment with hinted amount of resources.
func newSegment(totalOps, totalKeyValBytes int) (
        *segment, error) {
        return &segment{
                kvs: make([]uint64, 0, totalOps*2),
                buf: make([]byte, 0, totalKeyValBytes),
        }, nil
}

// Close releases resources associated with the segment.
func (a *segment) Close() error {
        return nil
}

// Set copies the key and val bytes into the segment as a "set"
// mutation.  The key must be unique (not repeated) within the
// segment.
func (a *segment) Set(key, val []byte) error {
        return a.mutate(OperationSet, key, val)
}

// Del copies the key bytes into the segment as a "deletion" mutation.
// The key must be unique (not repeated) within the segment.
func (a *segment) Del(key []byte) error {
        return a.mutate(OperationDel, key, nil)
}

// Merge creates or updates a key-val entry in the Collection via the
// MergeOperator defined in the CollectionOptions.  The key must be
// unique (not repeated) within the segment.
func (a *segment) Merge(key, val []byte) error {
        return a.mutate(OperationMerge, key, val)
}

// ------------------------------------------------------

// Alloc provides a slice of bytes "owned" by the segment, to reduce
// extra copying of memory.  See the Collection.NewBatch() method.
func (a *segment) Alloc(numBytes int) ([]byte, error) {
        bufLen := len(a.buf)
        bufCap := cap(a.buf)

        if numBytes > bufCap-bufLen {
                return nil, ErrAllocTooLarge
        }

        rv := a.buf[bufLen : bufLen+numBytes]

        a.buf = a.buf[0 : bufLen+numBytes]

        return rv, nil
}

// AllocSet is like Set(), but the caller must provide []byte
// parameters that came from Alloc(), for less buffer copying.
func (a *segment) AllocSet(keyFromAlloc, valFromAlloc []byte) error {
        bufCap := cap(a.buf)

        keyStart := bufCap - cap(keyFromAlloc)

        return a.mutateEx(OperationSet,
                keyStart, len(keyFromAlloc), len(valFromAlloc))
}

// AllocDel is like Del(), but the caller must provide []byte
// parameters that came from Alloc(), for less buffer copying.
func (a *segment) AllocDel(keyFromAlloc []byte) error {
        bufCap := cap(a.buf)

        keyStart := bufCap - cap(keyFromAlloc)

        return a.mutateEx(OperationDel,
                keyStart, len(keyFromAlloc), 0)
}

// AllocMerge is like Merge(), but the caller must provide []byte
// parameters that came from Alloc(), for less buffer copying.
func (a *segment) AllocMerge(keyFromAlloc, valFromAlloc []byte) error {
        bufCap := cap(a.buf)

        keyStart := bufCap - cap(keyFromAlloc)

        return a.mutateEx(OperationMerge,
                keyStart, len(keyFromAlloc), len(valFromAlloc))
}

// ------------------------------------------------------

func (a *segment) mutate(operation uint64, key, val []byte) error {
        keyStart := len(a.buf)
        a.buf = append(a.buf, key...)
        keyLength := len(a.buf) - keyStart

        valStart := len(a.buf)
        a.buf = append(a.buf, val...)
        valLength := len(a.buf) - valStart

        return a.mutateEx(operation, keyStart, keyLength, valLength)
}

func (a *segment) mutateEx(operation uint64,
        keyStart, keyLength, valLength int) error {
        if keyLength <= 0 && valLength <= 0 {
                keyStart = 0
        }

        opKlVl := (maskOperation & operation) |
                (maskKeyLength & (uint64(keyLength) << 32)) |
                (maskValLength & (uint64(valLength)))

        a.kvs = append(a.kvs, opKlVl, uint64(keyStart))

        switch operation {
        case OperationSet:
                a.totOperationSet++
        case OperationDel:
                a.totOperationDel++
        case OperationMerge:
                a.totOperationMerge++
        default:
        }

        a.totKeyByte += uint64(keyLength)
        a.totValByte += uint64(valLength)

        return nil
}

// ------------------------------------------------------

// NumKeyValBytes returns the number of bytes used for key-val data.
func (a *segment) NumKeyValBytes() int {
        return len(a.buf)
}

// ------------------------------------------------------

// Len returns the count of key-val entries.
func (a *segment) Len() int {
        return len(a.kvs) / 2
}

func (a *segment) Swap(i, j int) {
        x := i * 2
        y := j * 2

        // Operation + key length + val length.
        a.kvs[x], a.kvs[y] = a.kvs[y], a.kvs[x]

        x++
        y++

        a.kvs[x], a.kvs[y] = a.kvs[y], a.kvs[x] // Buf index.
}

func (a *segment) Less(i, j int) bool {
        x := i * 2
        y := j * 2

        kxLength := int((maskKeyLength & a.kvs[x]) >> 32)
        kxStart := int(a.kvs[x+1])
        kx := a.buf[kxStart : kxStart+kxLength]

        kyLength := int((maskKeyLength & a.kvs[y]) >> 32)
        kyStart := int(a.kvs[y+1])
        ky := a.buf[kyStart : kyStart+kyLength]

        return bytes.Compare(kx, ky) < 0
}

// ------------------------------------------------------

// findStartKeyInclusivePos() returns the logical entry position for
// the given (inclusive) start key.  With segment keys of [b, d, f],
// looking for 'c' will return 1.  Looking for 'd' will return 1.
// Looking for 'g' will return 3.  Looking for 'a' will return 0.
func (a *segment) findStartKeyInclusivePos(startKeyInclusive []byte) int {
        n := a.Len()

        return sort.Search(n, func(pos int) bool {
                x := pos * 2

                klength := int((maskKeyLength & a.kvs[x]) >> 32)
                kstart := int(a.kvs[x+1])
                k := a.buf[kstart : kstart+klength]

                return bytes.Compare(k, startKeyInclusive) >= 0
        })

        // TODO: Do better than binary search?
        // TODO: Consider a perfectly balanced btree?
}

// getOperationKeyVal() returns the operation, key, val for a given
// logical entry position in the segment.
func (a *segment) getOperationKeyVal(pos int) (
        uint64, []byte, []byte) {
        x := pos * 2
        if x < 0 || x >= len(a.kvs) {
                return 0, nil, nil
        }

        opklvl := a.kvs[x]

        klength := int((maskKeyLength & opklvl) >> 32)
        vlength := int(maskValLength & opklvl)

        kstart := int(a.kvs[x+1])
        vstart := kstart + klength

        k := a.buf[kstart : kstart+klength]
        v := a.buf[vstart : vstart+vlength]

        operation := maskOperation & opklvl

        return operation, k, v
}

// ------------------------------------------------------

// requestSort() will either perform the previously deferred sorting,
// if the goroutine can acquire the 1 ticket from the needSorterCh.
// Or, requestSort() will ensure that a sorter is working on this
// segment.  Returns true if the segment is sorted, and returns false
// if the sorting is only asynchronously scheduled.
func (a *segment) requestSort(synchronous bool) bool {
        if a.needSorterCh == nil {
                return true
        }

        iAmTheSorter := <-a.needSorterCh
        if iAmTheSorter {
                sort.Sort(a)
                close(a.waitSortedCh) // Signal any waiters.
                return true
        }

        if synchronous {
                <-a.waitSortedCh // Wait for the sorter to be done.
                return true
        }

        return false
}

1	// Copyright (c) 2016 Couchbase, Inc.
2	// Licensed under the Apache License, Version 2.0 (the "License");
3	// you may not use this file except in compliance with the
4	// License. You may obtain a copy of the License at
5	// http://www.apache.org/licenses/LICENSE-2.0
6	// Unless required by applicable law or agreed to in writing,
7	// software distributed under the License is distributed on an "AS
8	// IS" BASIS, WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either
9	// express or implied. See the License for the specific language
10	// governing permissions and limitations under the License.
11
12	package moss
13
14	import (
15	"bytes"
16	"sort"
17	)
18
19	// A segment is a sequence of key-val entries or operations. A
20	// segment's kvs will be sorted by key when the segment is pushed into
21	// the collection. A segment implements the Batch interface.
22	type segment struct {
23	// Each key-val operation is encoded as 2 uint64's...
24	// - operation (see: maskOperation) \|
25	// key length (see: maskKeyLength) \|
26	// val length (see: maskValLength).
27	// - start index into buf for key-val bytes.
28	kvs []uint64
29
30	// Contiguous backing memory for the keys and vals of the segment.
31	buf []byte
32
33	// If this segment needs sorting, then needSorterCh will be
34	// non-nil and also the first goroutine that reads successfully
35	// from needSorterCh becomes the sorter of this segment. All
36	// other goroutines must instead wait on the waitSortedCh.
37	needSorterCh chan bool
38
39	// Once the sorter of this segment is done sorting the kvs, it
40	// close()'s the waitSortedCh, treating waitSortedCh like a
41	// one-way latch. The needSorterCh and waitSortedCh will either
42	// be nil or non-nil together. A segment that was "born
43	// sorted" will have needSorterCh and waitSortedCh as both nil.
44	waitSortedCh chan struct{}
45
46	totOperationSet uint64
47	totOperationDel uint64
48	totOperationMerge uint64
49	totKeyByte uint64
50	totValByte uint64
51	}
52
53	// See the OperationXxx consts.
54	const maskOperation = uint64(0x0F00000000000000)
55
56	// Max key length is 2^24, from 24 bits key length.
57	const maskKeyLength = uint64(0x00FFFFFF00000000)
58
59	// Max val length is 2^28, from 28 bits val length.
60	const maskValLength = uint64(0x000000000FFFFFFF)
61
62	const maskRESERVED = uint64(0xF0000000F0000000)
63
64	// newSegment() allocates a segment with hinted amount of resources.
65	func newSegment(totalOps, totalKeyValBytes int) (	1✔
66	*segment, error) {	1✔
67	return &segment{	30✔
68	kvs: make([]uint64, 0, totalOps*2),	1✔
69	buf: make([]byte, 0, totalKeyValBytes),	1✔
70	}, nil	1✔
71	}	1✔
72
73	// Close releases resources associated with the segment.
74	func (a *segment) Close() error {	1✔
75	return nil	25✔
76	}	1✔
77
78	// Set copies the key and val bytes into the segment as a "set"
79	// mutation. The key must be unique (not repeated) within the
80	// segment.
81	func (a *segment) Set(key, val []byte) error {	1✔
82	return a.mutate(OperationSet, key, val)	2,021✔
83	}	1✔
84
85	// Del copies the key bytes into the segment as a "deletion" mutation.
86	// The key must be unique (not repeated) within the segment.
87	func (a *segment) Del(key []byte) error {	1✔
88	return a.mutate(OperationDel, key, nil)	1,009✔
89	}	1✔
90
91	// Merge creates or updates a key-val entry in the Collection via the
92	// MergeOperator defined in the CollectionOptions. The key must be
93	// unique (not repeated) within the segment.
94	func (a *segment) Merge(key, val []byte) error {	1✔
95	return a.mutate(OperationMerge, key, val)	3✔
96	}	1✔
97
98	// ------------------------------------------------------
99
100	// Alloc provides a slice of bytes "owned" by the segment, to reduce
101	// extra copying of memory. See the Collection.NewBatch() method.
102	func (a *segment) Alloc(numBytes int) ([]byte, error) {	1✔
103	bufLen := len(a.buf)	5✔
104	bufCap := cap(a.buf)	5✔
105		1✔
106	if numBytes > bufCap-bufLen {	5✔
107	return nil, ErrAllocTooLarge	1✔
108	}	1✔
109		1✔
110	rv := a.buf[bufLen : bufLen+numBytes]	4✔
111		1✔
112	a.buf = a.buf[0 : bufLen+numBytes]	4✔
113		1✔
114	return rv, nil	4✔
115	}	1✔
116
117	// AllocSet is like Set(), but the caller must provide []byte
118	// parameters that came from Alloc(), for less buffer copying.
119	func (a *segment) AllocSet(keyFromAlloc, valFromAlloc []byte) error {	1✔
120	bufCap := cap(a.buf)	2✔
121		1✔
122	keyStart := bufCap - cap(keyFromAlloc)	2✔
123		1✔
124	return a.mutateEx(OperationSet,	2✔
125	keyStart, len(keyFromAlloc), len(valFromAlloc))	1✔
126	}	1✔
127
128	// AllocDel is like Del(), but the caller must provide []byte
129	// parameters that came from Alloc(), for less buffer copying.
130	func (a *segment) AllocDel(keyFromAlloc []byte) error {	1✔
131	bufCap := cap(a.buf)	1✔
132		1✔
133	keyStart := bufCap - cap(keyFromAlloc)	1✔
134		1✔
135	return a.mutateEx(OperationDel,	1✔
136	keyStart, len(keyFromAlloc), 0)	1✔
137	}	1✔
138
139	// AllocMerge is like Merge(), but the caller must provide []byte
140	// parameters that came from Alloc(), for less buffer copying.
141	func (a *segment) AllocMerge(keyFromAlloc, valFromAlloc []byte) error {	1✔
142	bufCap := cap(a.buf)	1✔
143		1✔
144	keyStart := bufCap - cap(keyFromAlloc)	1✔
145		1✔
146	return a.mutateEx(OperationMerge,	1✔
147	keyStart, len(keyFromAlloc), len(valFromAlloc))	1✔
148	}	1✔
149
150	// ------------------------------------------------------
151
152	func (a *segment) mutate(operation uint64, key, val []byte) error {	1✔
153	keyStart := len(a.buf)	3,042✔
154	a.buf = append(a.buf, key...)	3,042✔
155	keyLength := len(a.buf) - keyStart	3,042✔
156		1✔
157	valStart := len(a.buf)	3,042✔
158	a.buf = append(a.buf, val...)	3,042✔
159	valLength := len(a.buf) - valStart	3,042✔
160		1✔
161	return a.mutateEx(operation, keyStart, keyLength, valLength)	3,042✔
162	}	1✔
163
164	func (a *segment) mutateEx(operation uint64,	1✔
165	keyStart, keyLength, valLength int) error {	1✔
166	if keyLength <= 0 && valLength <= 0 {	3,046✔
167	keyStart = 0	×
168	}	1✔
169		1✔
170	opKlVl := (maskOperation & operation) \|	3,046✔
171	(maskKeyLength & (uint64(keyLength) << 32)) \|	1✔
172	(maskValLength & (uint64(valLength)))	1✔
173		1✔
174	a.kvs = append(a.kvs, opKlVl, uint64(keyStart))	3,046✔
175		1✔
176	switch operation {	3,046✔
177	case OperationSet:	1✔
178	a.totOperationSet++	2,026✔
179	case OperationDel:	1✔
180	a.totOperationDel++	1,015✔
181	case OperationMerge:	1✔
182	a.totOperationMerge++	5✔
183	default:	1✔
184	}	1✔
185		1✔
186	a.totKeyByte += uint64(keyLength)	3,046✔
187	a.totValByte += uint64(valLength)	3,046✔
188		1✔
189	return nil	3,046✔
190	}	1✔
191
192	// ------------------------------------------------------
193
194	// NumKeyValBytes returns the number of bytes used for key-val data.
195	func (a *segment) NumKeyValBytes() int {	1✔
196	return len(a.buf)	2✔
197	}	1✔
198
199	// ------------------------------------------------------
200
201	// Len returns the count of key-val entries.
202	func (a *segment) Len() int {	1✔
203	return len(a.kvs) / 2	1,252✔
204	}	1✔
205
206	func (a *segment) Swap(i, j int) {	1✔
207	x := i * 2	8,149✔
208	y := j * 2	8,149✔
209		1✔
210	// Operation + key length + val length.	1✔
211	a.kvs[x], a.kvs[y] = a.kvs[y], a.kvs[x]	8,149✔
212		1✔
213	x++	8,149✔
214	y++	8,149✔
215		1✔
216	a.kvs[x], a.kvs[y] = a.kvs[y], a.kvs[x] // Buf index.	8,149✔
217	}	1✔
218
219	func (a *segment) Less(i, j int) bool {	1✔
220	x := i * 2	37,923✔
221	y := j * 2	37,923✔
222		1✔
223	kxLength := int((maskKeyLength & a.kvs[x]) >> 32)	37,923✔
224	kxStart := int(a.kvs[x+1])	37,923✔
225	kx := a.buf[kxStart : kxStart+kxLength]	37,923✔
226		1✔
227	kyLength := int((maskKeyLength & a.kvs[y]) >> 32)	37,923✔
228	kyStart := int(a.kvs[y+1])	37,923✔
229	ky := a.buf[kyStart : kyStart+kyLength]	37,923✔
230		1✔
231	return bytes.Compare(kx, ky) < 0	37,923✔
232	}	1✔
233
234	// ------------------------------------------------------
235
236	// findStartKeyInclusivePos() returns the logical entry position for
237	// the given (inclusive) start key. With segment keys of [b, d, f],
238	// looking for 'c' will return 1. Looking for 'd' will return 1.
239	// Looking for 'g' will return 3. Looking for 'a' will return 0.
240	func (a *segment) findStartKeyInclusivePos(startKeyInclusive []byte) int {	1✔
241	n := a.Len()	1,185✔
242		1✔
243	return sort.Search(n, func(pos int) bool {	1✔
244	x := pos * 2	1,477✔
245		1✔
246	klength := int((maskKeyLength & a.kvs[x]) >> 32)	1,477✔
247	kstart := int(a.kvs[x+1])	1,477✔
248	k := a.buf[kstart : kstart+klength]	1,477✔
249		1✔
250	return bytes.Compare(k, startKeyInclusive) >= 0	1,477✔
251	})	1✔
252		1✔
253	// TODO: Do better than binary search?	1✔
254	// TODO: Consider a perfectly balanced btree?	1✔
255	}	1✔
256
257	// getOperationKeyVal() returns the operation, key, val for a given
258	// logical entry position in the segment.
259	func (a *segment) getOperationKeyVal(pos int) (	1✔
260	uint64, []byte, []byte) {	1✔
261	x := pos * 2	3,772✔
262	if x < 0 \|\| x >= len(a.kvs) {	3,772✔
263	return 0, nil, nil	951✔
264	}	1✔
265		1✔
266	opklvl := a.kvs[x]	2,821✔
267		1✔
268	klength := int((maskKeyLength & opklvl) >> 32)	2,821✔
269	vlength := int(maskValLength & opklvl)	2,821✔
270		1✔
271	kstart := int(a.kvs[x+1])	2,821✔
272	vstart := kstart + klength	2,821✔
273		1✔
274	k := a.buf[kstart : kstart+klength]	2,821✔
275	v := a.buf[vstart : vstart+vlength]	2,821✔
276		1✔
277	operation := maskOperation & opklvl	2,821✔
278		1✔
279	return operation, k, v	2,821✔
280	}	1✔
281
282	// ------------------------------------------------------
283
284	// requestSort() will either perform the previously deferred sorting,
285	// if the goroutine can acquire the 1 ticket from the needSorterCh.
286	// Or, requestSort() will ensure that a sorter is working on this
287	// segment. Returns true if the segment is sorted, and returns false
288	// if the sorting is only asynchronously scheduled.
289	func (a *segment) requestSort(synchronous bool) bool {	1✔
290	if a.needSorterCh == nil {	×
291	return true	×
292	}	1✔
293		1✔
294	iAmTheSorter := <-a.needSorterCh	×
295	if iAmTheSorter {	×
296	sort.Sort(a)	×
297	close(a.waitSortedCh) // Signal any waiters.	×
298	return true	×
299	}	1✔
300		1✔
301	if synchronous {	×
302	<-a.waitSortedCh // Wait for the sorter to be done.	×
303	return true	×
304	}	1✔
305		1✔
306	return false	×
307	}	1✔

couchbase / moss / 15

Source File Press 'n' to go to next uncovered line, 'b' for previous

Source File
Press 'n' to go to next uncovered line, 'b' for previous