This update provides:
1) workaround around the build failures. In
summary, it forces the download of some packages during the build
process.
2) update the set of packages that should go inside the vendor
directory
3) Update the dockerfile to use go 1.10
Change-Id: I2bfd090ce0f25b0c10aa214755ae2da7e5384d60
diff --git a/vendor/github.com/coreos/etcd/pkg/adt/interval_tree.go b/vendor/github.com/coreos/etcd/pkg/adt/interval_tree.go
new file mode 100644
index 0000000..ec302e4
--- /dev/null
+++ b/vendor/github.com/coreos/etcd/pkg/adt/interval_tree.go
@@ -0,0 +1,599 @@
+// Copyright 2016 The etcd Authors
+//
+// 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 adt
+
+import (
+ "bytes"
+ "math"
+)
+
+// Comparable is an interface for trichotomic comparisons.
+type Comparable interface {
+ // Compare gives the result of a 3-way comparison
+ // a.Compare(b) = 1 => a > b
+ // a.Compare(b) = 0 => a == b
+ // a.Compare(b) = -1 => a < b
+ Compare(c Comparable) int
+}
+
+type rbcolor int
+
+const (
+ black rbcolor = iota
+ red
+)
+
+// Interval implements a Comparable interval [begin, end)
+// TODO: support different sorts of intervals: (a,b), [a,b], (a, b]
+type Interval struct {
+ Begin Comparable
+ End Comparable
+}
+
+// Compare on an interval gives == if the interval overlaps.
+func (ivl *Interval) Compare(c Comparable) int {
+ ivl2 := c.(*Interval)
+ ivbCmpBegin := ivl.Begin.Compare(ivl2.Begin)
+ ivbCmpEnd := ivl.Begin.Compare(ivl2.End)
+ iveCmpBegin := ivl.End.Compare(ivl2.Begin)
+
+ // ivl is left of ivl2
+ if ivbCmpBegin < 0 && iveCmpBegin <= 0 {
+ return -1
+ }
+
+ // iv is right of iv2
+ if ivbCmpEnd >= 0 {
+ return 1
+ }
+
+ return 0
+}
+
+type intervalNode struct {
+ // iv is the interval-value pair entry.
+ iv IntervalValue
+ // max endpoint of all descendent nodes.
+ max Comparable
+ // left and right are sorted by low endpoint of key interval
+ left, right *intervalNode
+ // parent is the direct ancestor of the node
+ parent *intervalNode
+ c rbcolor
+}
+
+func (x *intervalNode) color() rbcolor {
+ if x == nil {
+ return black
+ }
+ return x.c
+}
+
+func (n *intervalNode) height() int {
+ if n == nil {
+ return 0
+ }
+ ld := n.left.height()
+ rd := n.right.height()
+ if ld < rd {
+ return rd + 1
+ }
+ return ld + 1
+}
+
+func (x *intervalNode) min() *intervalNode {
+ for x.left != nil {
+ x = x.left
+ }
+ return x
+}
+
+// successor is the next in-order node in the tree
+func (x *intervalNode) successor() *intervalNode {
+ if x.right != nil {
+ return x.right.min()
+ }
+ y := x.parent
+ for y != nil && x == y.right {
+ x = y
+ y = y.parent
+ }
+ return y
+}
+
+// updateMax updates the maximum values for a node and its ancestors
+func (x *intervalNode) updateMax() {
+ for x != nil {
+ oldmax := x.max
+ max := x.iv.Ivl.End
+ if x.left != nil && x.left.max.Compare(max) > 0 {
+ max = x.left.max
+ }
+ if x.right != nil && x.right.max.Compare(max) > 0 {
+ max = x.right.max
+ }
+ if oldmax.Compare(max) == 0 {
+ break
+ }
+ x.max = max
+ x = x.parent
+ }
+}
+
+type nodeVisitor func(n *intervalNode) bool
+
+// visit will call a node visitor on each node that overlaps the given interval
+func (x *intervalNode) visit(iv *Interval, nv nodeVisitor) bool {
+ if x == nil {
+ return true
+ }
+ v := iv.Compare(&x.iv.Ivl)
+ switch {
+ case v < 0:
+ if !x.left.visit(iv, nv) {
+ return false
+ }
+ case v > 0:
+ maxiv := Interval{x.iv.Ivl.Begin, x.max}
+ if maxiv.Compare(iv) == 0 {
+ if !x.left.visit(iv, nv) || !x.right.visit(iv, nv) {
+ return false
+ }
+ }
+ default:
+ if !x.left.visit(iv, nv) || !nv(x) || !x.right.visit(iv, nv) {
+ return false
+ }
+ }
+ return true
+}
+
+type IntervalValue struct {
+ Ivl Interval
+ Val interface{}
+}
+
+// IntervalTree represents a (mostly) textbook implementation of the
+// "Introduction to Algorithms" (Cormen et al, 2nd ed.) chapter 13 red-black tree
+// and chapter 14.3 interval tree with search supporting "stabbing queries".
+type IntervalTree struct {
+ root *intervalNode
+ count int
+}
+
+// Delete removes the node with the given interval from the tree, returning
+// true if a node is in fact removed.
+func (ivt *IntervalTree) Delete(ivl Interval) bool {
+ z := ivt.find(ivl)
+ if z == nil {
+ return false
+ }
+
+ y := z
+ if z.left != nil && z.right != nil {
+ y = z.successor()
+ }
+
+ x := y.left
+ if x == nil {
+ x = y.right
+ }
+ if x != nil {
+ x.parent = y.parent
+ }
+
+ if y.parent == nil {
+ ivt.root = x
+ } else {
+ if y == y.parent.left {
+ y.parent.left = x
+ } else {
+ y.parent.right = x
+ }
+ y.parent.updateMax()
+ }
+ if y != z {
+ z.iv = y.iv
+ z.updateMax()
+ }
+
+ if y.color() == black && x != nil {
+ ivt.deleteFixup(x)
+ }
+
+ ivt.count--
+ return true
+}
+
+func (ivt *IntervalTree) deleteFixup(x *intervalNode) {
+ for x != ivt.root && x.color() == black && x.parent != nil {
+ if x == x.parent.left {
+ w := x.parent.right
+ if w.color() == red {
+ w.c = black
+ x.parent.c = red
+ ivt.rotateLeft(x.parent)
+ w = x.parent.right
+ }
+ if w == nil {
+ break
+ }
+ if w.left.color() == black && w.right.color() == black {
+ w.c = red
+ x = x.parent
+ } else {
+ if w.right.color() == black {
+ w.left.c = black
+ w.c = red
+ ivt.rotateRight(w)
+ w = x.parent.right
+ }
+ w.c = x.parent.color()
+ x.parent.c = black
+ w.right.c = black
+ ivt.rotateLeft(x.parent)
+ x = ivt.root
+ }
+ } else {
+ // same as above but with left and right exchanged
+ w := x.parent.left
+ if w.color() == red {
+ w.c = black
+ x.parent.c = red
+ ivt.rotateRight(x.parent)
+ w = x.parent.left
+ }
+ if w == nil {
+ break
+ }
+ if w.left.color() == black && w.right.color() == black {
+ w.c = red
+ x = x.parent
+ } else {
+ if w.left.color() == black {
+ w.right.c = black
+ w.c = red
+ ivt.rotateLeft(w)
+ w = x.parent.left
+ }
+ w.c = x.parent.color()
+ x.parent.c = black
+ w.left.c = black
+ ivt.rotateRight(x.parent)
+ x = ivt.root
+ }
+ }
+ }
+ if x != nil {
+ x.c = black
+ }
+}
+
+// Insert adds a node with the given interval into the tree.
+func (ivt *IntervalTree) Insert(ivl Interval, val interface{}) {
+ var y *intervalNode
+ z := &intervalNode{iv: IntervalValue{ivl, val}, max: ivl.End, c: red}
+ x := ivt.root
+ for x != nil {
+ y = x
+ if z.iv.Ivl.Begin.Compare(x.iv.Ivl.Begin) < 0 {
+ x = x.left
+ } else {
+ x = x.right
+ }
+ }
+
+ z.parent = y
+ if y == nil {
+ ivt.root = z
+ } else {
+ if z.iv.Ivl.Begin.Compare(y.iv.Ivl.Begin) < 0 {
+ y.left = z
+ } else {
+ y.right = z
+ }
+ y.updateMax()
+ }
+ z.c = red
+ ivt.insertFixup(z)
+ ivt.count++
+}
+
+func (ivt *IntervalTree) insertFixup(z *intervalNode) {
+ for z.parent != nil && z.parent.parent != nil && z.parent.color() == red {
+ if z.parent == z.parent.parent.left {
+ y := z.parent.parent.right
+ if y.color() == red {
+ y.c = black
+ z.parent.c = black
+ z.parent.parent.c = red
+ z = z.parent.parent
+ } else {
+ if z == z.parent.right {
+ z = z.parent
+ ivt.rotateLeft(z)
+ }
+ z.parent.c = black
+ z.parent.parent.c = red
+ ivt.rotateRight(z.parent.parent)
+ }
+ } else {
+ // same as then with left/right exchanged
+ y := z.parent.parent.left
+ if y.color() == red {
+ y.c = black
+ z.parent.c = black
+ z.parent.parent.c = red
+ z = z.parent.parent
+ } else {
+ if z == z.parent.left {
+ z = z.parent
+ ivt.rotateRight(z)
+ }
+ z.parent.c = black
+ z.parent.parent.c = red
+ ivt.rotateLeft(z.parent.parent)
+ }
+ }
+ }
+ ivt.root.c = black
+}
+
+// rotateLeft moves x so it is left of its right child
+func (ivt *IntervalTree) rotateLeft(x *intervalNode) {
+ y := x.right
+ x.right = y.left
+ if y.left != nil {
+ y.left.parent = x
+ }
+ x.updateMax()
+ ivt.replaceParent(x, y)
+ y.left = x
+ y.updateMax()
+}
+
+// rotateLeft moves x so it is right of its left child
+func (ivt *IntervalTree) rotateRight(x *intervalNode) {
+ if x == nil {
+ return
+ }
+ y := x.left
+ x.left = y.right
+ if y.right != nil {
+ y.right.parent = x
+ }
+ x.updateMax()
+ ivt.replaceParent(x, y)
+ y.right = x
+ y.updateMax()
+}
+
+// replaceParent replaces x's parent with y
+func (ivt *IntervalTree) replaceParent(x *intervalNode, y *intervalNode) {
+ y.parent = x.parent
+ if x.parent == nil {
+ ivt.root = y
+ } else {
+ if x == x.parent.left {
+ x.parent.left = y
+ } else {
+ x.parent.right = y
+ }
+ x.parent.updateMax()
+ }
+ x.parent = y
+}
+
+// Len gives the number of elements in the tree
+func (ivt *IntervalTree) Len() int { return ivt.count }
+
+// Height is the number of levels in the tree; one node has height 1.
+func (ivt *IntervalTree) Height() int { return ivt.root.height() }
+
+// MaxHeight is the expected maximum tree height given the number of nodes
+func (ivt *IntervalTree) MaxHeight() int {
+ return int((2 * math.Log2(float64(ivt.Len()+1))) + 0.5)
+}
+
+// IntervalVisitor is used on tree searches; return false to stop searching.
+type IntervalVisitor func(n *IntervalValue) bool
+
+// Visit calls a visitor function on every tree node intersecting the given interval.
+// It will visit each interval [x, y) in ascending order sorted on x.
+func (ivt *IntervalTree) Visit(ivl Interval, ivv IntervalVisitor) {
+ ivt.root.visit(&ivl, func(n *intervalNode) bool { return ivv(&n.iv) })
+}
+
+// find the exact node for a given interval
+func (ivt *IntervalTree) find(ivl Interval) (ret *intervalNode) {
+ f := func(n *intervalNode) bool {
+ if n.iv.Ivl != ivl {
+ return true
+ }
+ ret = n
+ return false
+ }
+ ivt.root.visit(&ivl, f)
+ return ret
+}
+
+// Find gets the IntervalValue for the node matching the given interval
+func (ivt *IntervalTree) Find(ivl Interval) (ret *IntervalValue) {
+ n := ivt.find(ivl)
+ if n == nil {
+ return nil
+ }
+ return &n.iv
+}
+
+// Intersects returns true if there is some tree node intersecting the given interval.
+func (ivt *IntervalTree) Intersects(iv Interval) bool {
+ x := ivt.root
+ for x != nil && iv.Compare(&x.iv.Ivl) != 0 {
+ if x.left != nil && x.left.max.Compare(iv.Begin) > 0 {
+ x = x.left
+ } else {
+ x = x.right
+ }
+ }
+ return x != nil
+}
+
+// Contains returns true if the interval tree's keys cover the entire given interval.
+func (ivt *IntervalTree) Contains(ivl Interval) bool {
+ var maxEnd, minBegin Comparable
+
+ isContiguous := true
+ ivt.Visit(ivl, func(n *IntervalValue) bool {
+ if minBegin == nil {
+ minBegin = n.Ivl.Begin
+ maxEnd = n.Ivl.End
+ return true
+ }
+ if maxEnd.Compare(n.Ivl.Begin) < 0 {
+ isContiguous = false
+ return false
+ }
+ if n.Ivl.End.Compare(maxEnd) > 0 {
+ maxEnd = n.Ivl.End
+ }
+ return true
+ })
+
+ return isContiguous && minBegin != nil && maxEnd.Compare(ivl.End) >= 0 && minBegin.Compare(ivl.Begin) <= 0
+}
+
+// Stab returns a slice with all elements in the tree intersecting the interval.
+func (ivt *IntervalTree) Stab(iv Interval) (ivs []*IntervalValue) {
+ if ivt.count == 0 {
+ return nil
+ }
+ f := func(n *IntervalValue) bool { ivs = append(ivs, n); return true }
+ ivt.Visit(iv, f)
+ return ivs
+}
+
+// Union merges a given interval tree into the receiver.
+func (ivt *IntervalTree) Union(inIvt IntervalTree, ivl Interval) {
+ f := func(n *IntervalValue) bool {
+ ivt.Insert(n.Ivl, n.Val)
+ return true
+ }
+ inIvt.Visit(ivl, f)
+}
+
+type StringComparable string
+
+func (s StringComparable) Compare(c Comparable) int {
+ sc := c.(StringComparable)
+ if s < sc {
+ return -1
+ }
+ if s > sc {
+ return 1
+ }
+ return 0
+}
+
+func NewStringInterval(begin, end string) Interval {
+ return Interval{StringComparable(begin), StringComparable(end)}
+}
+
+func NewStringPoint(s string) Interval {
+ return Interval{StringComparable(s), StringComparable(s + "\x00")}
+}
+
+// StringAffineComparable treats "" as > all other strings
+type StringAffineComparable string
+
+func (s StringAffineComparable) Compare(c Comparable) int {
+ sc := c.(StringAffineComparable)
+
+ if len(s) == 0 {
+ if len(sc) == 0 {
+ return 0
+ }
+ return 1
+ }
+ if len(sc) == 0 {
+ return -1
+ }
+
+ if s < sc {
+ return -1
+ }
+ if s > sc {
+ return 1
+ }
+ return 0
+}
+
+func NewStringAffineInterval(begin, end string) Interval {
+ return Interval{StringAffineComparable(begin), StringAffineComparable(end)}
+}
+func NewStringAffinePoint(s string) Interval {
+ return NewStringAffineInterval(s, s+"\x00")
+}
+
+func NewInt64Interval(a int64, b int64) Interval {
+ return Interval{Int64Comparable(a), Int64Comparable(b)}
+}
+
+func NewInt64Point(a int64) Interval {
+ return Interval{Int64Comparable(a), Int64Comparable(a + 1)}
+}
+
+type Int64Comparable int64
+
+func (v Int64Comparable) Compare(c Comparable) int {
+ vc := c.(Int64Comparable)
+ cmp := v - vc
+ if cmp < 0 {
+ return -1
+ }
+ if cmp > 0 {
+ return 1
+ }
+ return 0
+}
+
+// BytesAffineComparable treats empty byte arrays as > all other byte arrays
+type BytesAffineComparable []byte
+
+func (b BytesAffineComparable) Compare(c Comparable) int {
+ bc := c.(BytesAffineComparable)
+
+ if len(b) == 0 {
+ if len(bc) == 0 {
+ return 0
+ }
+ return 1
+ }
+ if len(bc) == 0 {
+ return -1
+ }
+
+ return bytes.Compare(b, bc)
+}
+
+func NewBytesAffineInterval(begin, end []byte) Interval {
+ return Interval{BytesAffineComparable(begin), BytesAffineComparable(end)}
+}
+func NewBytesAffinePoint(b []byte) Interval {
+ be := make([]byte, len(b)+1)
+ copy(be, b)
+ be[len(b)] = 0
+ return NewBytesAffineInterval(b, be)
+}