aboutsummaryrefslogtreecommitdiff
path: root/vendor/github.com/jackc/puddle/v2/internal/genstack
diff options
context:
space:
mode:
authorGibheer <gibheer+git@zero-knowledge.org>2024-09-05 19:38:25 +0200
committerGibheer <gibheer+git@zero-knowledge.org>2024-09-05 19:38:25 +0200
commit6ea4d2c82de80efc87708e5e182034b7c6c2019e (patch)
tree35c0856a929040216c82153ca62d43b27530a887 /vendor/github.com/jackc/puddle/v2/internal/genstack
parent6f64eeace1b66639b9380b44e88a8d54850a4306 (diff)
switch from github.com/lib/pq to github.com/jackc/pgx/v5HEAD20240905master
lib/pq is out of maintenance for some time now, so switch to the newer more active library. Looks like it finally stabilized after a long time.
Diffstat (limited to 'vendor/github.com/jackc/puddle/v2/internal/genstack')
-rw-r--r--vendor/github.com/jackc/puddle/v2/internal/genstack/gen_stack.go85
-rw-r--r--vendor/github.com/jackc/puddle/v2/internal/genstack/stack.go39
2 files changed, 124 insertions, 0 deletions
diff --git a/vendor/github.com/jackc/puddle/v2/internal/genstack/gen_stack.go b/vendor/github.com/jackc/puddle/v2/internal/genstack/gen_stack.go
new file mode 100644
index 0000000..7e4660c
--- /dev/null
+++ b/vendor/github.com/jackc/puddle/v2/internal/genstack/gen_stack.go
@@ -0,0 +1,85 @@
+package genstack
+
+// GenStack implements a generational stack.
+//
+// GenStack works as common stack except for the fact that all elements in the
+// older generation are guaranteed to be popped before any element in the newer
+// generation. New elements are always pushed to the current (newest)
+// generation.
+//
+// We could also say that GenStack behaves as a stack in case of a single
+// generation, but it behaves as a queue of individual generation stacks.
+type GenStack[T any] struct {
+ // We can represent arbitrary number of generations using 2 stacks. The
+ // new stack stores all new pushes and the old stack serves all reads.
+ // Old stack can represent multiple generations. If old == new, then all
+ // elements pushed in previous (not current) generations have already
+ // been popped.
+
+ old *stack[T]
+ new *stack[T]
+}
+
+// NewGenStack creates a new empty GenStack.
+func NewGenStack[T any]() *GenStack[T] {
+ s := &stack[T]{}
+ return &GenStack[T]{
+ old: s,
+ new: s,
+ }
+}
+
+func (s *GenStack[T]) Pop() (T, bool) {
+ // Pushes always append to the new stack, so if the old once becomes
+ // empty, it will remail empty forever.
+ if s.old.len() == 0 && s.old != s.new {
+ s.old = s.new
+ }
+
+ if s.old.len() == 0 {
+ var zero T
+ return zero, false
+ }
+
+ return s.old.pop(), true
+}
+
+// Push pushes a new element at the top of the stack.
+func (s *GenStack[T]) Push(v T) { s.new.push(v) }
+
+// NextGen starts a new stack generation.
+func (s *GenStack[T]) NextGen() {
+ if s.old == s.new {
+ s.new = &stack[T]{}
+ return
+ }
+
+ // We need to pop from the old stack to the top of the new stack. Let's
+ // have an example:
+ //
+ // Old: <bottom> 4 3 2 1
+ // New: <bottom> 8 7 6 5
+ // PopOrder: 1 2 3 4 5 6 7 8
+ //
+ //
+ // To preserve pop order, we have to take all elements from the old
+ // stack and push them to the top of new stack:
+ //
+ // New: 8 7 6 5 4 3 2 1
+ //
+ s.new.push(s.old.takeAll()...)
+
+ // We have the old stack allocated and empty, so why not to reuse it as
+ // new new stack.
+ s.old, s.new = s.new, s.old
+}
+
+// Len returns number of elements in the stack.
+func (s *GenStack[T]) Len() int {
+ l := s.old.len()
+ if s.old != s.new {
+ l += s.new.len()
+ }
+
+ return l
+}
diff --git a/vendor/github.com/jackc/puddle/v2/internal/genstack/stack.go b/vendor/github.com/jackc/puddle/v2/internal/genstack/stack.go
new file mode 100644
index 0000000..dbced0c
--- /dev/null
+++ b/vendor/github.com/jackc/puddle/v2/internal/genstack/stack.go
@@ -0,0 +1,39 @@
+package genstack
+
+// stack is a wrapper around an array implementing a stack.
+//
+// We cannot use slice to represent the stack because append might change the
+// pointer value of the slice. That would be an issue in GenStack
+// implementation.
+type stack[T any] struct {
+ arr []T
+}
+
+// push pushes a new element at the top of a stack.
+func (s *stack[T]) push(vs ...T) { s.arr = append(s.arr, vs...) }
+
+// pop pops the stack top-most element.
+//
+// If stack length is zero, this method panics.
+func (s *stack[T]) pop() T {
+ idx := s.len() - 1
+ val := s.arr[idx]
+
+ // Avoid memory leak
+ var zero T
+ s.arr[idx] = zero
+
+ s.arr = s.arr[:idx]
+ return val
+}
+
+// takeAll returns all elements in the stack in order as they are stored - i.e.
+// the top-most stack element is the last one.
+func (s *stack[T]) takeAll() []T {
+ arr := s.arr
+ s.arr = nil
+ return arr
+}
+
+// len returns number of elements in the stack.
+func (s *stack[T]) len() int { return len(s.arr) }