X-Git-Url: http://git.osdn.net/view?a=blobdiff_plain;ds=sidebyside;f=vendor%2Fgithub.com%2Fbtcsuite%2Fbtcd%2Fdatabase%2Finternal%2Ftreap%2Fmutable.go;fp=vendor%2Fgithub.com%2Fbtcsuite%2Fbtcd%2Fdatabase%2Finternal%2Ftreap%2Fmutable.go;h=0000000000000000000000000000000000000000;hb=d09b7a78d44dc259725902b8141cdba0d716b121;hp=84ebe6715f3252da99edcf66f81c305a8ff2db45;hpb=ee01d543fdfe1fd0a4d548965c66f7923ea7b062;p=bytom%2Fvapor.git

diff --git a/vendor/github.com/btcsuite/btcd/database/internal/treap/mutable.go b/vendor/github.com/btcsuite/btcd/database/internal/treap/mutable.go
deleted file mode 100644
index 84ebe671..00000000
--- a/vendor/github.com/btcsuite/btcd/database/internal/treap/mutable.go
+++ /dev/null
@@ -1,278 +0,0 @@
-// Copyright (c) 2015-2016 The btcsuite developers
-// Use of this source code is governed by an ISC
-// license that can be found in the LICENSE file.
-
-package treap
-
-import (
-	"bytes"
-	"math/rand"
-)
-
-// Mutable represents a treap data structure which is used to hold ordered
-// key/value pairs using a combination of binary search tree and heap semantics.
-// It is a self-organizing and randomized data structure that doesn't require
-// complex operations to maintain balance.  Search, insert, and delete
-// operations are all O(log n).
-type Mutable struct {
-	root  *treapNode
-	count int
-
-	// totalSize is the best estimate of the total size of of all data in
-	// the treap including the keys, values, and node sizes.
-	totalSize uint64
-}
-
-// Len returns the number of items stored in the treap.
-func (t *Mutable) Len() int {
-	return t.count
-}
-
-// Size returns a best estimate of the total number of bytes the treap is
-// consuming including all of the fields used to represent the nodes as well as
-// the size of the keys and values.  Shared values are not detected, so the
-// returned size assumes each value is pointing to different memory.
-func (t *Mutable) Size() uint64 {
-	return t.totalSize
-}
-
-// get returns the treap node that contains the passed key and its parent.  When
-// the found node is the root of the tree, the parent will be nil.  When the key
-// does not exist, both the node and the parent will be nil.
-func (t *Mutable) get(key []byte) (*treapNode, *treapNode) {
-	var parent *treapNode
-	for node := t.root; node != nil; {
-		// Traverse left or right depending on the result of the
-		// comparison.
-		compareResult := bytes.Compare(key, node.key)
-		if compareResult < 0 {
-			parent = node
-			node = node.left
-			continue
-		}
-		if compareResult > 0 {
-			parent = node
-			node = node.right
-			continue
-		}
-
-		// The key exists.
-		return node, parent
-	}
-
-	// A nil node was reached which means the key does not exist.
-	return nil, nil
-}
-
-// Has returns whether or not the passed key exists.
-func (t *Mutable) Has(key []byte) bool {
-	if node, _ := t.get(key); node != nil {
-		return true
-	}
-	return false
-}
-
-// Get returns the value for the passed key.  The function will return nil when
-// the key does not exist.
-func (t *Mutable) Get(key []byte) []byte {
-	if node, _ := t.get(key); node != nil {
-		return node.value
-	}
-	return nil
-}
-
-// relinkGrandparent relinks the node into the treap after it has been rotated
-// by changing the passed grandparent's left or right pointer, depending on
-// where the old parent was, to point at the passed node.  Otherwise, when there
-// is no grandparent, it means the node is now the root of the tree, so update
-// it accordingly.
-func (t *Mutable) relinkGrandparent(node, parent, grandparent *treapNode) {
-	// The node is now the root of the tree when there is no grandparent.
-	if grandparent == nil {
-		t.root = node
-		return
-	}
-
-	// Relink the grandparent's left or right pointer based on which side
-	// the old parent was.
-	if grandparent.left == parent {
-		grandparent.left = node
-	} else {
-		grandparent.right = node
-	}
-}
-
-// Put inserts the passed key/value pair.
-func (t *Mutable) Put(key, value []byte) {
-	// Use an empty byte slice for the value when none was provided.  This
-	// ultimately allows key existence to be determined from the value since
-	// an empty byte slice is distinguishable from nil.
-	if value == nil {
-		value = emptySlice
-	}
-
-	// The node is the root of the tree if there isn't already one.
-	if t.root == nil {
-		node := newTreapNode(key, value, rand.Int())
-		t.count = 1
-		t.totalSize = nodeSize(node)
-		t.root = node
-		return
-	}
-
-	// Find the binary tree insertion point and construct a list of parents
-	// while doing so.  When the key matches an entry already in the treap,
-	// just update its value and return.
-	var parents parentStack
-	var compareResult int
-	for node := t.root; node != nil; {
-		parents.Push(node)
-		compareResult = bytes.Compare(key, node.key)
-		if compareResult < 0 {
-			node = node.left
-			continue
-		}
-		if compareResult > 0 {
-			node = node.right
-			continue
-		}
-
-		// The key already exists, so update its value.
-		t.totalSize -= uint64(len(node.value))
-		t.totalSize += uint64(len(value))
-		node.value = value
-		return
-	}
-
-	// Link the new node into the binary tree in the correct position.
-	node := newTreapNode(key, value, rand.Int())
-	t.count++
-	t.totalSize += nodeSize(node)
-	parent := parents.At(0)
-	if compareResult < 0 {
-		parent.left = node
-	} else {
-		parent.right = node
-	}
-
-	// Perform any rotations needed to maintain the min-heap.
-	for parents.Len() > 0 {
-		// There is nothing left to do when the node's priority is
-		// greater than or equal to its parent's priority.
-		parent = parents.Pop()
-		if node.priority >= parent.priority {
-			break
-		}
-
-		// Perform a right rotation if the node is on the left side or
-		// a left rotation if the node is on the right side.
-		if parent.left == node {
-			node.right, parent.left = parent, node.right
-		} else {
-			node.left, parent.right = parent, node.left
-		}
-		t.relinkGrandparent(node, parent, parents.At(0))
-	}
-}
-
-// Delete removes the passed key if it exists.
-func (t *Mutable) Delete(key []byte) {
-	// Find the node for the key along with its parent.  There is nothing to
-	// do if the key does not exist.
-	node, parent := t.get(key)
-	if node == nil {
-		return
-	}
-
-	// When the only node in the tree is the root node and it is the one
-	// being deleted, there is nothing else to do besides removing it.
-	if parent == nil && node.left == nil && node.right == nil {
-		t.root = nil
-		t.count = 0
-		t.totalSize = 0
-		return
-	}
-
-	// Perform rotations to move the node to delete to a leaf position while
-	// maintaining the min-heap.
-	var isLeft bool
-	var child *treapNode
-	for node.left != nil || node.right != nil {
-		// Choose the child with the higher priority.
-		if node.left == nil {
-			child = node.right
-			isLeft = false
-		} else if node.right == nil {
-			child = node.left
-			isLeft = true
-		} else if node.left.priority >= node.right.priority {
-			child = node.left
-			isLeft = true
-		} else {
-			child = node.right
-			isLeft = false
-		}
-
-		// Rotate left or right depending on which side the child node
-		// is on.  This has the effect of moving the node to delete
-		// towards the bottom of the tree while maintaining the
-		// min-heap.
-		if isLeft {
-			child.right, node.left = node, child.right
-		} else {
-			child.left, node.right = node, child.left
-		}
-		t.relinkGrandparent(child, node, parent)
-
-		// The parent for the node to delete is now what was previously
-		// its child.
-		parent = child
-	}
-
-	// Delete the node, which is now a leaf node, by disconnecting it from
-	// its parent.
-	if parent.right == node {
-		parent.right = nil
-	} else {
-		parent.left = nil
-	}
-	t.count--
-	t.totalSize -= nodeSize(node)
-}
-
-// ForEach invokes the passed function with every key/value pair in the treap
-// in ascending order.
-func (t *Mutable) ForEach(fn func(k, v []byte) bool) {
-	// Add the root node and all children to the left of it to the list of
-	// nodes to traverse and loop until they, and all of their child nodes,
-	// have been traversed.
-	var parents parentStack
-	for node := t.root; node != nil; node = node.left {
-		parents.Push(node)
-	}
-	for parents.Len() > 0 {
-		node := parents.Pop()
-		if !fn(node.key, node.value) {
-			return
-		}
-
-		// Extend the nodes to traverse by all children to the left of
-		// the current node's right child.
-		for node := node.right; node != nil; node = node.left {
-			parents.Push(node)
-		}
-	}
-}
-
-// Reset efficiently removes all items in the treap.
-func (t *Mutable) Reset() {
-	t.count = 0
-	t.totalSize = 0
-	t.root = nil
-}
-
-// NewMutable returns a new empty mutable treap ready for use.  See the
-// documentation for the Mutable structure for more details.
-func NewMutable() *Mutable {
-	return &Mutable{}
-}