diff options
| author | 6543 <6543@obermui.de> | 2020-11-06 19:41:42 +0100 |
|---|---|---|
| committer | GitHub <noreply@github.com> | 2020-11-06 13:41:42 -0500 |
| commit | 30ce3731a17913155436cee323b1e7016ad8eb49 (patch) | |
| tree | d03230684af7dfcfff7705ac547a35b3089f02fb /vendor/github.com/RoaringBitmap | |
| parent | eebaa81f43a6fd982dcd96571a020242f0ea3276 (diff) | |
| download | gitea-30ce3731a17913155436cee323b1e7016ad8eb49.tar.gz gitea-30ce3731a17913155436cee323b1e7016ad8eb49.zip | |
Vendor Update Go Libs (#13444)
* denisenkom/go-mssqldb untagged -> v0.9.0
* github.com/editorconfig/editorconfig-core-go v2.3.7 -> v2.3.8
* github.com/go-testfixtures/testfixtures v3.4.0 -> v3.4.1
* github.com/mholt/archiver v3.3.2 -> v3.5.0
* github.com/olivere/elastic v7.0.20 -> v7.0.21
* github.com/urfave/cli v1.22.4 -> v1.22.5
* github.com/xanzy/go-gitlab v0.38.1 -> v0.39.0
* github.com/yuin/goldmark-meta untagged -> v1.0.0
* github.com/ethantkoenig/rupture 0a76f03a811a -> c3b3b810dc77
* github.com/jaytaylor/html2text 8fb95d837f7d -> 3577fbdbcff7
* github.com/kballard/go-shellquote cd60e84ee657 -> 95032a82bc51
* github.com/msteinert/pam 02ccfbfaf0cc -> 913b8f8cdf8b
* github.com/unknwon/paginater 7748a72e0141 -> 042474bd0eae
* CI.restart()
Co-authored-by: techknowlogick <techknowlogick@gitea.io>
Diffstat (limited to 'vendor/github.com/RoaringBitmap')
14 files changed, 352 insertions, 94 deletions
diff --git a/vendor/github.com/RoaringBitmap/roaring/.travis.yml b/vendor/github.com/RoaringBitmap/roaring/.travis.yml index 9ce8cadcf6..12266d7250 100644 --- a/vendor/github.com/RoaringBitmap/roaring/.travis.yml +++ b/vendor/github.com/RoaringBitmap/roaring/.travis.yml @@ -8,7 +8,6 @@ install: notifications: email: false go: -- "1.12.x" - "1.13.x" - "1.14.x" - tip diff --git a/vendor/github.com/RoaringBitmap/roaring/CONTRIBUTORS b/vendor/github.com/RoaringBitmap/roaring/CONTRIBUTORS index b1e3a379f0..1a8da9cc0f 100644 --- a/vendor/github.com/RoaringBitmap/roaring/CONTRIBUTORS +++ b/vendor/github.com/RoaringBitmap/roaring/CONTRIBUTORS @@ -13,4 +13,6 @@ Forud Ghafouri (@fzerorubigd), Joe Nall (@joenall), (@fredim), Edd Robinson (@e-dard), -Alexander Petrov (@alldroll) +Alexander Petrov (@alldroll), +Guy Molinari (@guymolinari), +Ling Jin (@JinLingChristopher) diff --git a/vendor/github.com/RoaringBitmap/roaring/README.md b/vendor/github.com/RoaringBitmap/roaring/README.md index 39b48420f4..00d2351c05 100644 --- a/vendor/github.com/RoaringBitmap/roaring/README.md +++ b/vendor/github.com/RoaringBitmap/roaring/README.md @@ -3,7 +3,6 @@ roaring [](https    - ============= This is a go version of the Roaring bitmap data structure. @@ -56,6 +55,93 @@ This code is licensed under Apache License, Version 2.0 (ASL2.0). Copyright 2016-... by the authors. +When should you use a bitmap? +=================================== + + +Sets are a fundamental abstraction in +software. They can be implemented in various +ways, as hash sets, as trees, and so forth. +In databases and search engines, sets are often an integral +part of indexes. For example, we may need to maintain a set +of all documents or rows (represented by numerical identifier) +that satisfy some property. Besides adding or removing +elements from the set, we need fast functions +to compute the intersection, the union, the difference between sets, and so on. + + +To implement a set +of integers, a particularly appealing strategy is the +bitmap (also called bitset or bit vector). Using n bits, +we can represent any set made of the integers from the range +[0,n): the ith bit is set to one if integer i is present in the set. +Commodity processors use words of W=32 or W=64 bits. By combining many such words, we can +support large values of n. Intersections, unions and differences can then be implemented + as bitwise AND, OR and ANDNOT operations. +More complicated set functions can also be implemented as bitwise operations. + +When the bitset approach is applicable, it can be orders of +magnitude faster than other possible implementation of a set (e.g., as a hash set) +while using several times less memory. + +However, a bitset, even a compressed one is not always applicable. For example, if the +you have 1000 random-looking integers, then a simple array might be the best representation. +We refer to this case as the "sparse" scenario. + +When should you use compressed bitmaps? +=================================== + +An uncompressed BitSet can use a lot of memory. For example, if you take a BitSet +and set the bit at position 1,000,000 to true and you have just over 100kB. That is over 100kB +to store the position of one bit. This is wasteful even if you do not care about memory: +suppose that you need to compute the intersection between this BitSet and another one +that has a bit at position 1,000,001 to true, then you need to go through all these zeroes, +whether you like it or not. That can become very wasteful. + +This being said, there are definitively cases where attempting to use compressed bitmaps is wasteful. +For example, if you have a small universe size. E.g., your bitmaps represent sets of integers +from [0,n) where n is small (e.g., n=64 or n=128). If you are able to uncompressed BitSet and +it does not blow up your memory usage, then compressed bitmaps are probably not useful +to you. In fact, if you do not need compression, then a BitSet offers remarkable speed. + +The sparse scenario is another use case where compressed bitmaps should not be used. +Keep in mind that random-looking data is usually not compressible. E.g., if you have a small set of +32-bit random integers, it is not mathematically possible to use far less than 32 bits per integer, +and attempts at compression can be counterproductive. + +How does Roaring compares with the alternatives? +================================================== + + +Most alternatives to Roaring are part of a larger family of compressed bitmaps that are run-length-encoded +bitmaps. They identify long runs of 1s or 0s and they represent them with a marker word. +If you have a local mix of 1s and 0, you use an uncompressed word. + +There are many formats in this family: + +* Oracle's BBC is an obsolete format at this point: though it may provide good compression, +it is likely much slower than more recent alternatives due to excessive branching. +* WAH is a patented variation on BBC that provides better performance. +* Concise is a variation on the patented WAH. It some specific instances, it can compress +much better than WAH (up to 2x better), but it is generally slower. +* EWAH is both free of patent, and it is faster than all the above. On the downside, it +does not compress quite as well. It is faster because it allows some form of "skipping" +over uncompressed words. So though none of these formats are great at random access, EWAH +is better than the alternatives. + + + +There is a big problem with these formats however that can hurt you badly in some cases: there is no random access. If you want to check whether a given value is present in the set, you have to start from the beginning and "uncompress" the whole thing. This means that if you want to intersect a big set with a large set, you still have to uncompress the whole big set in the worst case... + +Roaring solves this problem. It works in the following manner. It divides the data into chunks of 2<sup>16</sup> integers +(e.g., [0, 2<sup>16</sup>), [2<sup>16</sup>, 2 x 2<sup>16</sup>), ...). Within a chunk, it can use an uncompressed bitmap, a simple list of integers, +or a list of runs. Whatever format it uses, they all allow you to check for the present of any one value quickly +(e.g., with a binary search). The net result is that Roaring can compute many operations much faster than run-length-encoded +formats like WAH, EWAH, Concise... Maybe surprisingly, Roaring also generally offers better compression ratios. + + + + ### References diff --git a/vendor/github.com/RoaringBitmap/roaring/arraycontainer.go b/vendor/github.com/RoaringBitmap/roaring/arraycontainer.go index 12fe6cf530..f8bb29b96f 100644 --- a/vendor/github.com/RoaringBitmap/roaring/arraycontainer.go +++ b/vendor/github.com/RoaringBitmap/roaring/arraycontainer.go @@ -359,28 +359,17 @@ func (ac *arrayContainer) iorArray(value2 *arrayContainer) container { len1 := value1.getCardinality() len2 := value2.getCardinality() maxPossibleCardinality := len1 + len2 - if maxPossibleCardinality > arrayDefaultMaxSize { // it could be a bitmap! - bc := newBitmapContainer() - for k := 0; k < len(value2.content); k++ { - v := value2.content[k] - i := uint(v) >> 6 - mask := uint64(1) << (v % 64) - bc.bitmap[i] |= mask - } - for k := 0; k < len(ac.content); k++ { - v := ac.content[k] - i := uint(v) >> 6 - mask := uint64(1) << (v % 64) - bc.bitmap[i] |= mask - } - bc.cardinality = int(popcntSlice(bc.bitmap)) - if bc.cardinality <= arrayDefaultMaxSize { - return bc.toArrayContainer() - } - return bc - } if maxPossibleCardinality > cap(value1.content) { - newcontent := make([]uint16, 0, maxPossibleCardinality) + // doubling the capacity reduces new slice allocations in the case of + // repeated calls to iorArray(). + newSize := 2 * maxPossibleCardinality + // the second check is to handle overly large array containers + // and should not occur in normal usage, + // as all array containers should be at most arrayDefaultMaxSize + if newSize > 2*arrayDefaultMaxSize && maxPossibleCardinality <= 2*arrayDefaultMaxSize { + newSize = 2 * arrayDefaultMaxSize + } + newcontent := make([]uint16, 0, newSize) copy(newcontent[len2:maxPossibleCardinality], ac.content[0:len1]) ac.content = newcontent } else { @@ -388,6 +377,13 @@ func (ac *arrayContainer) iorArray(value2 *arrayContainer) container { } nl := union2by2(value1.content[len2:maxPossibleCardinality], value2.content, ac.content) ac.content = ac.content[:nl] // reslice to match actual used capacity + + if nl > arrayDefaultMaxSize { + // Only converting to a bitmap when arrayDefaultMaxSize + // is actually exceeded minimizes conversions in the case of repeated + // calls to iorArray(). + return ac.toBitmapContainer() + } return ac } diff --git a/vendor/github.com/RoaringBitmap/roaring/go.mod b/vendor/github.com/RoaringBitmap/roaring/go.mod index f5aebf3967..5e9db36bac 100644 --- a/vendor/github.com/RoaringBitmap/roaring/go.mod +++ b/vendor/github.com/RoaringBitmap/roaring/go.mod @@ -1,6 +1,6 @@ module github.com/RoaringBitmap/roaring -go 1.12 +go 1.14 require ( github.com/glycerine/go-unsnap-stream v0.0.0-20181221182339-f9677308dec2 @@ -13,4 +13,6 @@ require ( github.com/stretchr/testify v1.4.0 github.com/tinylib/msgp v1.1.0 github.com/willf/bitset v1.1.10 + golang.org/x/lint v0.0.0-20200302205851-738671d3881b // indirect + golang.org/x/tools v0.0.0-20200928182047-19e03678916f // indirect ) diff --git a/vendor/github.com/RoaringBitmap/roaring/go.sum b/vendor/github.com/RoaringBitmap/roaring/go.sum index 2e27dbb6e6..c01900e6d7 100644 --- a/vendor/github.com/RoaringBitmap/roaring/go.sum +++ b/vendor/github.com/RoaringBitmap/roaring/go.sum @@ -24,6 +24,31 @@ github.com/tinylib/msgp v1.1.0 h1:9fQd+ICuRIu/ue4vxJZu6/LzxN0HwMds2nq/0cFvxHU= github.com/tinylib/msgp v1.1.0/go.mod h1:+d+yLhGm8mzTaHzB+wgMYrodPfmZrzkirds8fDWklFE= github.com/willf/bitset v1.1.10 h1:NotGKqX0KwQ72NUzqrjZq5ipPNDQex9lo3WpaS8L2sc= github.com/willf/bitset v1.1.10/go.mod h1:RjeCKbqT1RxIR/KWY6phxZiaY1IyutSBfGjNPySAYV4= +github.com/yuin/goldmark v1.2.1/go.mod h1:3hX8gzYuyVAZsxl0MRgGTJEmQBFcNTphYh9decYSb74= +golang.org/x/crypto v0.0.0-20190308221718-c2843e01d9a2/go.mod h1:djNgcEr1/C05ACkg1iLfiJU5Ep61QUkGW8qpdssI0+w= +golang.org/x/crypto v0.0.0-20191011191535-87dc89f01550/go.mod h1:yigFU9vqHzYiE8UmvKecakEJjdnWj3jj499lnFckfCI= +golang.org/x/crypto v0.0.0-20200622213623-75b288015ac9/go.mod h1:LzIPMQfyMNhhGPhUkYOs5KpL4U8rLKemX1yGLhDgUto= +golang.org/x/lint v0.0.0-20200302205851-738671d3881b h1:Wh+f8QHJXR411sJR8/vRBTZ7YapZaRvUcLFFJhusH0k= +golang.org/x/lint v0.0.0-20200302205851-738671d3881b/go.mod h1:3xt1FjdF8hUf6vQPIChWIBhFzV8gjjsPE/fR3IyQdNY= +golang.org/x/mod v0.1.1-0.20191105210325-c90efee705ee/go.mod h1:QqPTAvyqsEbceGzBzNggFXnrqF1CaUcvgkdR5Ot7KZg= +golang.org/x/mod v0.3.0/go.mod h1:s0Qsj1ACt9ePp/hMypM3fl4fZqREWJwdYDEqhRiZZUA= +golang.org/x/net v0.0.0-20190404232315-eb5bcb51f2a3/go.mod h1:t9HGtf8HONx5eT2rtn7q6eTqICYqUVnKs3thJo3Qplg= +golang.org/x/net v0.0.0-20190620200207-3b0461eec859/go.mod h1:z5CRVTTTmAJ677TzLLGU+0bjPO0LkuOLi4/5GtJWs/s= +golang.org/x/net v0.0.0-20200822124328-c89045814202/go.mod h1:/O7V0waA8r7cgGh81Ro3o1hOxt32SMVPicZroKQ2sZA= +golang.org/x/sync v0.0.0-20190423024810-112230192c58/go.mod h1:RxMgew5VJxzue5/jJTE5uejpjVlOe/izrB70Jof72aM= +golang.org/x/sync v0.0.0-20200625203802-6e8e738ad208/go.mod h1:RxMgew5VJxzue5/jJTE5uejpjVlOe/izrB70Jof72aM= +golang.org/x/sys v0.0.0-20190215142949-d0b11bdaac8a/go.mod h1:STP8DvDyc/dI5b8T5hshtkjS+E42TnysNCUPdjciGhY= +golang.org/x/sys v0.0.0-20190412213103-97732733099d/go.mod h1:h1NjWce9XRLGQEsW7wpKNCjG9DtNlClVuFLEZdDNbEs= +golang.org/x/sys v0.0.0-20200323222414-85ca7c5b95cd/go.mod h1:h1NjWce9XRLGQEsW7wpKNCjG9DtNlClVuFLEZdDNbEs= +golang.org/x/text v0.3.0/go.mod h1:NqM8EUOU14njkJ3fqMW+pc6Ldnwhi/IjpwHt7yyuwOQ= +golang.org/x/tools v0.0.0-20191119224855-298f0cb1881e/go.mod h1:b+2E5dAYhXwXZwtnZ6UAqBI28+e2cm9otk0dWdXHAEo= +golang.org/x/tools v0.0.0-20200130002326-2f3ba24bd6e7 h1:EBZoQjiKKPaLbPrbpssUfuHtwM6KV/vb4U85g/cigFY= +golang.org/x/tools v0.0.0-20200130002326-2f3ba24bd6e7/go.mod h1:TB2adYChydJhpapKDTa4BR/hXlZSLoq2Wpct/0txZ28= +golang.org/x/tools v0.0.0-20200928182047-19e03678916f h1:VwGa2Wf+rHGIxvsssCkUNIyFv8jQY0VCBCNWtikoWq0= +golang.org/x/tools v0.0.0-20200928182047-19e03678916f/go.mod h1:z6u4i615ZeAfBE4XtMziQW1fSVJXACjjbWkB/mvPzlU= +golang.org/x/xerrors v0.0.0-20190717185122-a985d3407aa7/go.mod h1:I/5z698sn9Ka8TeJc9MKroUUfqBBauWjQqLJ2OPfmY0= +golang.org/x/xerrors v0.0.0-20191011141410-1b5146add898/go.mod h1:I/5z698sn9Ka8TeJc9MKroUUfqBBauWjQqLJ2OPfmY0= +golang.org/x/xerrors v0.0.0-20200804184101-5ec99f83aff1/go.mod h1:I/5z698sn9Ka8TeJc9MKroUUfqBBauWjQqLJ2OPfmY0= gopkg.in/check.v1 v0.0.0-20161208181325-20d25e280405 h1:yhCVgyC4o1eVCa2tZl7eS0r+SDo693bJlVdllGtEeKM= gopkg.in/check.v1 v0.0.0-20161208181325-20d25e280405/go.mod h1:Co6ibVJAznAaIkqp8huTwlJQCZ016jof/cbN4VW5Yz0= gopkg.in/yaml.v2 v2.2.2 h1:ZCJp+EgiOT7lHqUV2J862kp8Qj64Jo6az82+3Td9dZw= diff --git a/vendor/github.com/RoaringBitmap/roaring/roaring.go b/vendor/github.com/RoaringBitmap/roaring/roaring.go index 477bad1826..2afb39570a 100644 --- a/vendor/github.com/RoaringBitmap/roaring/roaring.go +++ b/vendor/github.com/RoaringBitmap/roaring/roaring.go @@ -345,9 +345,9 @@ func newIntReverseIterator(a *Bitmap) *intReverseIterator { // ManyIntIterable allows you to iterate over the values in a Bitmap type ManyIntIterable interface { - // pass in a buffer to fill up with values, returns how many values were returned + // NextMany fills buf up with values, returns how many values were returned NextMany(buf []uint32) int - // pass in a buffer to fill up with 64 bit values, returns how many values were returned + // NextMany64 fills up buf with 64 bit values, uses hs as a mask (OR), returns how many values were returned NextMany64(hs uint64, buf []uint64) int } @@ -1006,7 +1006,7 @@ main: } s2 = x2.highlowcontainer.getKeyAtIndex(pos2) } else { - rb.highlowcontainer.replaceKeyAndContainerAtIndex(pos1, s1, rb.highlowcontainer.getWritableContainerAtIndex(pos1).ior(x2.highlowcontainer.getContainerAtIndex(pos2)), false) + rb.highlowcontainer.replaceKeyAndContainerAtIndex(pos1, s1, rb.highlowcontainer.getUnionedWritableContainer(pos1, x2.highlowcontainer.getContainerAtIndex(pos2)), false) pos1++ pos2++ if (pos1 == length1) || (pos2 == length2) { @@ -1581,7 +1581,3 @@ func (rb *Bitmap) Stats() Statistics { } return stats } - -func (rb *Bitmap) FillLeastSignificant32bits(x []uint64, i uint64, mask uint64) { - rb.ManyIterator().NextMany64(mask, x[i:]) -} diff --git a/vendor/github.com/RoaringBitmap/roaring/roaringarray.go b/vendor/github.com/RoaringBitmap/roaring/roaringarray.go index 892755779f..d0c832b1b5 100644 --- a/vendor/github.com/RoaringBitmap/roaring/roaringarray.go +++ b/vendor/github.com/RoaringBitmap/roaring/roaringarray.go @@ -328,6 +328,17 @@ func (ra *roaringArray) getFastContainerAtIndex(i int, needsWriteable bool) cont return c } +// getUnionedWritableContainer switches behavior for in-place Or +// depending on whether the container requires a copy on write. +// If it does using the non-inplace or() method leads to fewer allocations. +func (ra *roaringArray) getUnionedWritableContainer(pos int, other container) container { + if ra.needCopyOnWrite[pos] { + return ra.getContainerAtIndex(pos).or(other) + } + return ra.getContainerAtIndex(pos).ior(other) + +} + func (ra *roaringArray) getWritableContainerAtIndex(i int) container { if ra.needCopyOnWrite[i] { ra.containers[i] = ra.containers[i].clone() diff --git a/vendor/github.com/RoaringBitmap/roaring/serialization_generic.go b/vendor/github.com/RoaringBitmap/roaring/serialization_generic.go index 4b9d9e3d48..90a336cdae 100644 --- a/vendor/github.com/RoaringBitmap/roaring/serialization_generic.go +++ b/vendor/github.com/RoaringBitmap/roaring/serialization_generic.go @@ -1,4 +1,4 @@ -// +build !amd64,!386 appengine +// +build !amd64,!386,!arm,!arm64,!ppc64le,!mipsle,!mips64le,!mips64p32le,!wasm appengine package roaring diff --git a/vendor/github.com/RoaringBitmap/roaring/serialization_littleendian.go b/vendor/github.com/RoaringBitmap/roaring/serialization_littleendian.go index 818a06c80b..82edeb8982 100644 --- a/vendor/github.com/RoaringBitmap/roaring/serialization_littleendian.go +++ b/vendor/github.com/RoaringBitmap/roaring/serialization_littleendian.go @@ -1,4 +1,4 @@ -// +build 386 amd64,!appengine +// +build 386,!appengine amd64,!appengine arm,!appengine arm64,!appengine ppc64le,!appengine mipsle,!appengine mips64le,!appengine mips64p32le,!appengine wasm,!appengine package roaring diff --git a/vendor/github.com/RoaringBitmap/roaring/setutil.go b/vendor/github.com/RoaringBitmap/roaring/setutil.go index 2fe8151411..663c4fa37e 100644 --- a/vendor/github.com/RoaringBitmap/roaring/setutil.go +++ b/vendor/github.com/RoaringBitmap/roaring/setutil.go @@ -135,66 +135,6 @@ func exclusiveUnion2by2(set1 []uint16, set2 []uint16, buffer []uint16) int { return pos } -func union2by2(set1 []uint16, set2 []uint16, buffer []uint16) int { - pos := 0 - k1 := 0 - k2 := 0 - if 0 == len(set2) { - buffer = buffer[:len(set1)] - copy(buffer, set1[:]) - return len(set1) - } - if 0 == len(set1) { - buffer = buffer[:len(set2)] - copy(buffer, set2[:]) - return len(set2) - } - s1 := set1[k1] - s2 := set2[k2] - buffer = buffer[:cap(buffer)] - for { - if s1 < s2 { - buffer[pos] = s1 - pos++ - k1++ - if k1 >= len(set1) { - copy(buffer[pos:], set2[k2:]) - pos += len(set2) - k2 - break - } - s1 = set1[k1] - } else if s1 == s2 { - buffer[pos] = s1 - pos++ - k1++ - k2++ - if k1 >= len(set1) { - copy(buffer[pos:], set2[k2:]) - pos += len(set2) - k2 - break - } - if k2 >= len(set2) { - copy(buffer[pos:], set1[k1:]) - pos += len(set1) - k1 - break - } - s1 = set1[k1] - s2 = set2[k2] - } else { // if (set1[k1]>set2[k2]) - buffer[pos] = s2 - pos++ - k2++ - if k2 >= len(set2) { - copy(buffer[pos:], set1[k1:]) - pos += len(set1) - k1 - break - } - s2 = set2[k2] - } - } - return pos -} - func union2by2Cardinality(set1 []uint16, set2 []uint16) int { pos := 0 k1 := 0 diff --git a/vendor/github.com/RoaringBitmap/roaring/setutil_arm64.go b/vendor/github.com/RoaringBitmap/roaring/setutil_arm64.go new file mode 100644 index 0000000000..debca813c4 --- /dev/null +++ b/vendor/github.com/RoaringBitmap/roaring/setutil_arm64.go @@ -0,0 +1,6 @@ +// +build arm64,!gccgo,!appengine + +package roaring + +//go:noescape +func union2by2(set1 []uint16, set2 []uint16, buffer []uint16) (size int) diff --git a/vendor/github.com/RoaringBitmap/roaring/setutil_arm64.s b/vendor/github.com/RoaringBitmap/roaring/setutil_arm64.s new file mode 100644 index 0000000000..e4f0f20473 --- /dev/null +++ b/vendor/github.com/RoaringBitmap/roaring/setutil_arm64.s @@ -0,0 +1,132 @@ +// +build arm64,!gccgo,!appengine + +#include "textflag.h" + + +// This implements union2by2 using golang's version of arm64 assembly +// The algorithm is very similar to the generic one, +// but makes better use of arm64 features so is notably faster. +// The basic algorithm structure is as follows: +// 1. If either set is empty, copy the other set into the buffer and return the length +// 2. Otherwise, load the first element of each set into a variable (s1 and s2). +// 3. a. Compare the values of s1 and s2. + // b. add the smaller one to the buffer. + // c. perform a bounds check before incrementing. + // If one set is finished, copy the rest of the other set over. + // d. update s1 and or s2 to the next value, continue loop. + // + // Past the fact of the algorithm, this code makes use of several arm64 features + // Condition Codes: + // arm64's CMP operation sets 4 bits that can be used for branching, + // rather than just true or false. + // As a consequence, a single comparison gives enough information to distinguish the three cases + // + // Post-increment pointers after load/store: + // Instructions like `MOVHU.P 2(R0), R6` + // increment the register by a specified amount, in this example 2. + // Because uint16's are exactly 2 bytes and the length of the slices + // is part of the slice header, + // there is no need to separately track the index into the slice. + // Instead, the code can calculate the final read value and compare against that, + // using the post-increment reads to move the pointers along. + // + // TODO: CALL out to memmove once the list is exhausted. + // Right now it moves the necessary shorts so that the remaining count + // is a multiple of 4 and then copies 64 bits at a time. + +TEXT ·union2by2(SB), NOSPLIT, $0-80 + // R0, R1, and R2 for the pointers to the three slices + MOVD set1+0(FP), R0 + MOVD set2+24(FP), R1 + MOVD buffer+48(FP), R2 + + //R3 and R4 will be the values at which we will have finished reading set1 and set2. + // R3 should be R0 + 2 * set1_len+8(FP) + MOVD set1_len+8(FP), R3 + MOVD set2_len+32(FP), R4 + + ADD R3<<1, R0, R3 + ADD R4<<1, R1, R4 + + + //Rather than counting the number of elements added separately + //Save the starting register of buffer. + MOVD buffer+48(FP), R5 + + // set1 is empty, just flush set2 + CMP R0, R3 + BEQ flush_right + + // set2 is empty, just flush set1 + CMP R1, R4 + BEQ flush_left + + // R6, R7 are the working space for s1 and s2 + MOVD ZR, R6 + MOVD ZR, R7 + + MOVHU.P 2(R0), R6 + MOVHU.P 2(R1), R7 +loop: + + CMP R6, R7 + BEQ pop_both // R6 == R7 + BLS pop_right // R6 > R7 +//pop_left: // R6 < R7 + MOVHU.P R6, 2(R2) + CMP R0, R3 + BEQ pop_then_flush_right + MOVHU.P 2(R0), R6 + JMP loop +pop_both: + MOVHU.P R6, 2(R2) //could also use R7, since they are equal + CMP R0, R3 + BEQ flush_right + CMP R1, R4 + BEQ flush_left + MOVHU.P 2(R0), R6 + MOVHU.P 2(R1), R7 + JMP loop +pop_right: + MOVHU.P R7, 2(R2) + CMP R1, R4 + BEQ pop_then_flush_left + MOVHU.P 2(R1), R7 + JMP loop + +pop_then_flush_right: + MOVHU.P R7, 2(R2) +flush_right: + MOVD R1, R0 + MOVD R4, R3 + JMP flush_left +pop_then_flush_left: + MOVHU.P R6, 2(R2) +flush_left: + CMP R0, R3 + BEQ return + //figure out how many bytes to slough off. Must be a multiple of two + SUB R0, R3, R4 + ANDS $6, R4 + BEQ long_flush //handles the 0 mod 8 case + SUBS $4, R4, R4 // since possible values are 2, 4, 6, this splits evenly + BLT pop_single // exactly the 2 case + MOVW.P 4(R0), R6 + MOVW.P R6, 4(R2) + BEQ long_flush // we're now aligned by 64 bits, as R4==4, otherwise 2 more +pop_single: + MOVHU.P 2(R0), R6 + MOVHU.P R6, 2(R2) +long_flush: + // at this point we know R3 - R0 is a multiple of 8. + CMP R0, R3 + BEQ return + MOVD.P 8(R0), R6 + MOVD.P R6, 8(R2) + JMP long_flush +return: + // number of shorts written is (R5 - R2) >> 1 + SUB R5, R2 + LSR $1, R2, R2 + MOVD R2, size+72(FP) + RET diff --git a/vendor/github.com/RoaringBitmap/roaring/setutil_generic.go b/vendor/github.com/RoaringBitmap/roaring/setutil_generic.go new file mode 100644 index 0000000000..9edcc9025e --- /dev/null +++ b/vendor/github.com/RoaringBitmap/roaring/setutil_generic.go @@ -0,0 +1,63 @@ +// +build !arm64 gccgo appengine + +package roaring + +func union2by2(set1 []uint16, set2 []uint16, buffer []uint16) int { + pos := 0 + k1 := 0 + k2 := 0 + if 0 == len(set2) { + buffer = buffer[:len(set1)] + copy(buffer, set1[:]) + return len(set1) + } + if 0 == len(set1) { + buffer = buffer[:len(set2)] + copy(buffer, set2[:]) + return len(set2) + } + s1 := set1[k1] + s2 := set2[k2] + buffer = buffer[:cap(buffer)] + for { + if s1 < s2 { + buffer[pos] = s1 + pos++ + k1++ + if k1 >= len(set1) { + copy(buffer[pos:], set2[k2:]) + pos += len(set2) - k2 + break + } + s1 = set1[k1] + } else if s1 == s2 { + buffer[pos] = s1 + pos++ + k1++ + k2++ + if k1 >= len(set1) { + copy(buffer[pos:], set2[k2:]) + pos += len(set2) - k2 + break + } + if k2 >= len(set2) { + copy(buffer[pos:], set1[k1:]) + pos += len(set1) - k1 + break + } + s1 = set1[k1] + s2 = set2[k2] + } else { // if (set1[k1]>set2[k2]) + buffer[pos] = s2 + pos++ + k2++ + if k2 >= len(set2) { + copy(buffer[pos:], set1[k1:]) + pos += len(set1) - k1 + break + } + s2 = set2[k2] + } + } + return pos +} |