aboutsummaryrefslogtreecommitdiffstats
path: root/common/prque/sstack.go
diff options
context:
space:
mode:
Diffstat (limited to 'common/prque/sstack.go')
-rwxr-xr-xcommon/prque/sstack.go106
1 files changed, 106 insertions, 0 deletions
diff --git a/common/prque/sstack.go b/common/prque/sstack.go
new file mode 100755
index 000000000..4875dae99
--- /dev/null
+++ b/common/prque/sstack.go
@@ -0,0 +1,106 @@
+// This is a duplicated and slightly modified version of "gopkg.in/karalabe/cookiejar.v2/collections/prque".
+
+package prque
+
+// The size of a block of data
+const blockSize = 4096
+
+// A prioritized item in the sorted stack.
+//
+// Note: priorities can "wrap around" the int64 range, a comes before b if (a.priority - b.priority) > 0.
+// The difference between the lowest and highest priorities in the queue at any point should be less than 2^63.
+type item struct {
+ value interface{}
+ priority int64
+}
+
+// setIndexCallback is called when the element is moved to a new index.
+// Providing setIndexCallback is optional, it is needed only if the application needs
+// to delete elements other than the top one.
+type setIndexCallback func(a interface{}, i int)
+
+// Internal sortable stack data structure. Implements the Push and Pop ops for
+// the stack (heap) functionality and the Len, Less and Swap methods for the
+// sortability requirements of the heaps.
+type sstack struct {
+ setIndex setIndexCallback
+ size int
+ capacity int
+ offset int
+
+ blocks [][]*item
+ active []*item
+}
+
+// Creates a new, empty stack.
+func newSstack(setIndex setIndexCallback) *sstack {
+ result := new(sstack)
+ result.setIndex = setIndex
+ result.active = make([]*item, blockSize)
+ result.blocks = [][]*item{result.active}
+ result.capacity = blockSize
+ return result
+}
+
+// Pushes a value onto the stack, expanding it if necessary. Required by
+// heap.Interface.
+func (s *sstack) Push(data interface{}) {
+ if s.size == s.capacity {
+ s.active = make([]*item, blockSize)
+ s.blocks = append(s.blocks, s.active)
+ s.capacity += blockSize
+ s.offset = 0
+ } else if s.offset == blockSize {
+ s.active = s.blocks[s.size/blockSize]
+ s.offset = 0
+ }
+ if s.setIndex != nil {
+ s.setIndex(data.(*item).value, s.size)
+ }
+ s.active[s.offset] = data.(*item)
+ s.offset++
+ s.size++
+}
+
+// Pops a value off the stack and returns it. Currently no shrinking is done.
+// Required by heap.Interface.
+func (s *sstack) Pop() (res interface{}) {
+ s.size--
+ s.offset--
+ if s.offset < 0 {
+ s.offset = blockSize - 1
+ s.active = s.blocks[s.size/blockSize]
+ }
+ res, s.active[s.offset] = s.active[s.offset], nil
+ if s.setIndex != nil {
+ s.setIndex(res.(*item).value, -1)
+ }
+ return
+}
+
+// Returns the length of the stack. Required by sort.Interface.
+func (s *sstack) Len() int {
+ return s.size
+}
+
+// Compares the priority of two elements of the stack (higher is first).
+// Required by sort.Interface.
+func (s *sstack) Less(i, j int) bool {
+ return (s.blocks[i/blockSize][i%blockSize].priority - s.blocks[j/blockSize][j%blockSize].priority) > 0
+}
+
+// Swaps two elements in the stack. Required by sort.Interface.
+func (s *sstack) Swap(i, j int) {
+ ib, io, jb, jo := i/blockSize, i%blockSize, j/blockSize, j%blockSize
+ a, b := s.blocks[jb][jo], s.blocks[ib][io]
+ if s.setIndex != nil {
+ s.setIndex(a.value, i)
+ s.setIndex(b.value, j)
+ }
+ s.blocks[ib][io], s.blocks[jb][jo] = a, b
+}
+
+// Resets the stack, effectively clearing its contents.
+func (s *sstack) Reset() {
+ *s = *newSstack(s.setIndex)
+}