diff options
Diffstat (limited to 'vendor')
44 files changed, 2769 insertions, 639 deletions
diff --git a/vendor/codeberg.org/gruf/go-atomics/LICENSE b/vendor/codeberg.org/gruf/go-atomics/LICENSE new file mode 100644 index 000000000..e4163ae35 --- /dev/null +++ b/vendor/codeberg.org/gruf/go-atomics/LICENSE @@ -0,0 +1,9 @@ +MIT License + +Copyright (c) 2022 gruf + +Permission is hereby granted, free of charge, to any person obtaining a copy of this software and associated documentation files (the "Software"), to deal in the Software without restriction, including without limitation the rights to use, copy, modify, merge, publish, distribute, sublicense, and/or sell copies of the Software, and to permit persons to whom the Software is furnished to do so, subject to the following conditions: + +The above copyright notice and this permission notice shall be included in all copies or substantial portions of the Software. + +THE SOFTWARE IS PROVIDED "AS IS", WITHOUT WARRANTY OF ANY KIND, EXPRESS OR IMPLIED, INCLUDING BUT NOT LIMITED TO THE WARRANTIES OF MERCHANTABILITY, FITNESS FOR A PARTICULAR PURPOSE AND NONINFRINGEMENT. IN NO EVENT SHALL THE AUTHORS OR COPYRIGHT HOLDERS BE LIABLE FOR ANY CLAIM, DAMAGES OR OTHER LIABILITY, WHETHER IN AN ACTION OF CONTRACT, TORT OR OTHERWISE, ARISING FROM, OUT OF OR IN CONNECTION WITH THE SOFTWARE OR THE USE OR OTHER DEALINGS IN THE SOFTWARE. diff --git a/vendor/codeberg.org/gruf/go-atomics/README.md b/vendor/codeberg.org/gruf/go-atomics/README.md new file mode 100644 index 000000000..38ba53276 --- /dev/null +++ b/vendor/codeberg.org/gruf/go-atomics/README.md @@ -0,0 +1,3 @@ +# go-atomics + +This library provides a variety of types for atomic operations on common Go types.
\ No newline at end of file diff --git a/vendor/codeberg.org/gruf/go-atomics/atomic.tpl b/vendor/codeberg.org/gruf/go-atomics/atomic.tpl new file mode 100644 index 000000000..00134c1e8 --- /dev/null +++ b/vendor/codeberg.org/gruf/go-atomics/atomic.tpl @@ -0,0 +1,57 @@ +package atomics + +import ( + "sync/atomic" + "unsafe" +) + +// {{ .Name }} provides user-friendly means of performing atomic operations on {{ .Type }} types. +type {{ .Name }} struct{ ptr unsafe.Pointer } + +// New{{ .Name }} will return a new {{ .Name }} instance initialized with zero value. +func New{{ .Name }}() *{{ .Name }} { + var v {{ .Type }} + return &{{ .Name }}{ + ptr: unsafe.Pointer(&v), + } +} + +// Store will atomically store {{ .Type }} value in address contained within v. +func (v *{{ .Name }}) Store(val {{ .Type }}) { + atomic.StorePointer(&v.ptr, unsafe.Pointer(&val)) +} + +// Load will atomically load {{ .Type }} value at address contained within v. +func (v *{{ .Name }}) Load() {{ .Type }} { + return *(*{{ .Type }})(atomic.LoadPointer(&v.ptr)) +} + +// CAS performs a compare-and-swap for a(n) {{ .Type }} value at address contained within v. +func (v *{{ .Name }}) CAS(cmp, swp {{ .Type }}) bool { + for { + // Load current value at address + ptr := atomic.LoadPointer(&v.ptr) + cur := *(*{{ .Type }})(ptr) + + // Perform comparison against current + if !({{ call .Compare "cur" "cmp" }}) { + return false + } + + // Attempt to replace pointer + if atomic.CompareAndSwapPointer( + &v.ptr, + ptr, + unsafe.Pointer(&swp), + ) { + return true + } + } +} + +// Swap atomically stores new {{ .Type }} value into address contained within v, and returns previous value. +func (v *{{ .Name }}) Swap(swp {{ .Type }}) {{ .Type }} { + ptr := unsafe.Pointer(&swp) + ptr = atomic.SwapPointer(&v.ptr, ptr) + return *(*{{ .Type }})(ptr) +} diff --git a/vendor/codeberg.org/gruf/go-atomics/atomic_test.tpl b/vendor/codeberg.org/gruf/go-atomics/atomic_test.tpl new file mode 100644 index 000000000..4e659d81f --- /dev/null +++ b/vendor/codeberg.org/gruf/go-atomics/atomic_test.tpl @@ -0,0 +1,60 @@ +package atomics_test + +import ( + "atomic" + "unsafe" + "testing" + + "codeberg.org/gruf/go-atomics" +) + +func Test{{ .Name }}StoreLoad(t *testing.T) { + for _, test := range {{ .Name }}Tests { + val := atomics.New{{ .Name }}() + + val.Store(test.V1) + + if !({{ call .Compare "val.Load()" "test.V1" }}) { + t.Fatalf("failed testing .Store and .Load: expect=%v actual=%v", val.Load(), test.V1) + } + + val.Store(test.V2) + + if !({{ call .Compare "val.Load()" "test.V2" }}) { + t.Fatalf("failed testing .Store and .Load: expect=%v actual=%v", val.Load(), test.V2) + } + } +} + +func Test{{ .Name }}CAS(t *testing.T) { + for _, test := range {{ .Name }}Tests { + val := atomics.New{{ .Name }}() + + val.Store(test.V1) + + if val.CAS(test.V2, test.V1) { + t.Fatalf("failed testing negative .CAS: test=%+v state=%v", test, val.Load()) + } + + if !val.CAS(test.V1, test.V2) { + t.Fatalf("failed testing positive .CAS: test=%+v state=%v", test, val.Load()) + } + } +} + +func Test{{ .Name }}Swap(t *testing.T) { + for _, test := range {{ .Name }}Tests { + val := atomics.New{{ .Name }}() + + val.Store(test.V1) + + if !({{ call .Compare "val.Swap(test.V2)" "test.V1" }}) { + t.Fatal("failed testing .Swap") + } + + if !({{ call .Compare "val.Swap(test.V1)" "test.V2" }}) { + t.Fatal("failed testing .Swap") + } + } +} + diff --git a/vendor/codeberg.org/gruf/go-atomics/bool.go b/vendor/codeberg.org/gruf/go-atomics/bool.go new file mode 100644 index 000000000..52660d356 --- /dev/null +++ b/vendor/codeberg.org/gruf/go-atomics/bool.go @@ -0,0 +1,47 @@ +package atomics + +import "sync/atomic" + +// Bool provides user-friendly means of performing atomic operations on bool types. +type Bool uint32 + +// NewBool will return a new Bool instance initialized with zero value. +func NewBool() *Bool { + return new(Bool) +} + +// Store will atomically store bool value in address contained within i. +func (b *Bool) Store(val bool) { + atomic.StoreUint32((*uint32)(b), fromBool(val)) +} + +// Load will atomically load bool value at address contained within i. +func (b *Bool) Load() bool { + return toBool(atomic.LoadUint32((*uint32)(b))) +} + +// CAS performs a compare-and-swap for a(n) bool value at address contained within i. +func (b *Bool) CAS(cmp, swp bool) bool { + return atomic.CompareAndSwapUint32((*uint32)(b), fromBool(cmp), fromBool(swp)) +} + +// Swap atomically stores new bool value into address contained within i, and returns previous value. +func (b *Bool) Swap(swp bool) bool { + return toBool(atomic.SwapUint32((*uint32)(b), fromBool(swp))) +} + +// toBool converts uint32 value to bool. +func toBool(u uint32) bool { + if u == 0 { + return false + } + return true +} + +// fromBool converts from bool to uint32 value. +func fromBool(b bool) uint32 { + if b { + return 1 + } + return 0 +} diff --git a/vendor/codeberg.org/gruf/go-atomics/bytes.go b/vendor/codeberg.org/gruf/go-atomics/bytes.go new file mode 100644 index 000000000..3e40d186c --- /dev/null +++ b/vendor/codeberg.org/gruf/go-atomics/bytes.go @@ -0,0 +1,57 @@ +package atomics + +import ( + "sync/atomic" + "unsafe" +) + +// Bytes provides user-friendly means of performing atomic operations on []byte types. +type Bytes struct{ ptr unsafe.Pointer } + +// NewBytes will return a new Bytes instance initialized with zero value. +func NewBytes() *Bytes { + var v []byte + return &Bytes{ + ptr: unsafe.Pointer(&v), + } +} + +// Store will atomically store []byte value in address contained within v. +func (v *Bytes) Store(val []byte) { + atomic.StorePointer(&v.ptr, unsafe.Pointer(&val)) +} + +// Load will atomically load []byte value at address contained within v. +func (v *Bytes) Load() []byte { + return *(*[]byte)(atomic.LoadPointer(&v.ptr)) +} + +// CAS performs a compare-and-swap for a(n) []byte value at address contained within v. +func (v *Bytes) CAS(cmp, swp []byte) bool { + for { + // Load current value at address + ptr := atomic.LoadPointer(&v.ptr) + cur := *(*[]byte)(ptr) + + // Perform comparison against current + if !(string(cur) == string(cmp)) { + return false + } + + // Attempt to replace pointer + if atomic.CompareAndSwapPointer( + &v.ptr, + ptr, + unsafe.Pointer(&swp), + ) { + return true + } + } +} + +// Swap atomically stores new []byte value into address contained within v, and returns previous value. +func (v *Bytes) Swap(swp []byte) []byte { + ptr := unsafe.Pointer(&swp) + ptr = atomic.SwapPointer(&v.ptr, ptr) + return *(*[]byte)(ptr) +} diff --git a/vendor/codeberg.org/gruf/go-atomics/error.go b/vendor/codeberg.org/gruf/go-atomics/error.go new file mode 100644 index 000000000..0ecc4e9ad --- /dev/null +++ b/vendor/codeberg.org/gruf/go-atomics/error.go @@ -0,0 +1,57 @@ +package atomics + +import ( + "sync/atomic" + "unsafe" +) + +// Error provides user-friendly means of performing atomic operations on error types. +type Error struct{ ptr unsafe.Pointer } + +// NewError will return a new Error instance initialized with zero value. +func NewError() *Error { + var v error + return &Error{ + ptr: unsafe.Pointer(&v), + } +} + +// Store will atomically store error value in address contained within v. +func (v *Error) Store(val error) { + atomic.StorePointer(&v.ptr, unsafe.Pointer(&val)) +} + +// Load will atomically load error value at address contained within v. +func (v *Error) Load() error { + return *(*error)(atomic.LoadPointer(&v.ptr)) +} + +// CAS performs a compare-and-swap for a(n) error value at address contained within v. +func (v *Error) CAS(cmp, swp error) bool { + for { + // Load current value at address + ptr := atomic.LoadPointer(&v.ptr) + cur := *(*error)(ptr) + + // Perform comparison against current + if !(cur == cmp) { + return false + } + + // Attempt to replace pointer + if atomic.CompareAndSwapPointer( + &v.ptr, + ptr, + unsafe.Pointer(&swp), + ) { + return true + } + } +} + +// Swap atomically stores new error value into address contained within v, and returns previous value. +func (v *Error) Swap(swp error) error { + ptr := unsafe.Pointer(&swp) + ptr = atomic.SwapPointer(&v.ptr, ptr) + return *(*error)(ptr) +} diff --git a/vendor/codeberg.org/gruf/go-atomics/flags.go b/vendor/codeberg.org/gruf/go-atomics/flags.go new file mode 100644 index 000000000..42176bece --- /dev/null +++ b/vendor/codeberg.org/gruf/go-atomics/flags.go @@ -0,0 +1,97 @@ +package atomics + +import ( + "sync/atomic" + + "codeberg.org/gruf/go-bitutil" +) + +// Flags32 provides user-friendly means of performing atomic operations on bitutil.Flags32 types. +type Flags32 bitutil.Flags32 + +// NewFlags32 will return a new Flags32 instance initialized with zero value. +func NewFlags32() *Flags32 { + return new(Flags32) +} + +// Get will atomically load a(n) bitutil.Flags32 value contained within f, and check if bit value is set. +func (f *Flags32) Get(bit uint8) bool { + return f.Load().Get(bit) +} + +// Set performs a compare-and-swap for a(n) bitutil.Flags32 with bit value set, at address contained within f. +func (f *Flags32) Set(bit uint8) bool { + cur := f.Load() + return f.CAS(cur, cur.Set(bit)) +} + +// Unset performs a compare-and-swap for a(n) bitutil.Flags32 with bit value unset, at address contained within f. +func (f *Flags32) Unset(bit uint8) bool { + cur := f.Load() + return f.CAS(cur, cur.Unset(bit)) +} + +// Store will atomically store bitutil.Flags32 value in address contained within f. +func (f *Flags32) Store(val bitutil.Flags32) { + atomic.StoreUint32((*uint32)(f), uint32(val)) +} + +// Load will atomically load bitutil.Flags32 value at address contained within f. +func (f *Flags32) Load() bitutil.Flags32 { + return bitutil.Flags32(atomic.LoadUint32((*uint32)(f))) +} + +// CAS performs a compare-and-swap for a(n) bitutil.Flags32 value at address contained within f. +func (f *Flags32) CAS(cmp, swp bitutil.Flags32) bool { + return atomic.CompareAndSwapUint32((*uint32)(f), uint32(cmp), uint32(swp)) +} + +// Swap atomically stores new bitutil.Flags32 value into address contained within f, and returns previous value. +func (f *Flags32) Swap(swp bitutil.Flags32) bitutil.Flags32 { + return bitutil.Flags32(atomic.SwapUint32((*uint32)(f), uint32(swp))) +} + +// Flags64 provides user-friendly means of performing atomic operations on bitutil.Flags64 types. +type Flags64 bitutil.Flags64 + +// NewFlags64 will return a new Flags64 instance initialized with zero value. +func NewFlags64() *Flags64 { + return new(Flags64) +} + +// Get will atomically load a(n) bitutil.Flags64 value contained within f, and check if bit value is set. +func (f *Flags64) Get(bit uint8) bool { + return f.Load().Get(bit) +} + +// Set performs a compare-and-swap for a(n) bitutil.Flags64 with bit value set, at address contained within f. +func (f *Flags64) Set(bit uint8) bool { + cur := f.Load() + return f.CAS(cur, cur.Set(bit)) +} + +// Unset performs a compare-and-swap for a(n) bitutil.Flags64 with bit value unset, at address contained within f. +func (f *Flags64) Unset(bit uint8) bool { + cur := f.Load() + return f.CAS(cur, cur.Unset(bit)) +} + +// Store will atomically store bitutil.Flags64 value in address contained within f. +func (f *Flags64) Store(val bitutil.Flags64) { + atomic.StoreUint64((*uint64)(f), uint64(val)) +} + +// Load will atomically load bitutil.Flags64 value at address contained within f. +func (f *Flags64) Load() bitutil.Flags64 { + return bitutil.Flags64(atomic.LoadUint64((*uint64)(f))) +} + +// CAS performs a compare-and-swap for a(n) bitutil.Flags64 value at address contained within f. +func (f *Flags64) CAS(cmp, swp bitutil.Flags64) bool { + return atomic.CompareAndSwapUint64((*uint64)(f), uint64(cmp), uint64(swp)) +} + +// Swap atomically stores new bitutil.Flags64 value into address contained within f, and returns previous value. +func (f *Flags64) Swap(swp bitutil.Flags64) bitutil.Flags64 { + return bitutil.Flags64(atomic.SwapUint64((*uint64)(f), uint64(swp))) +} diff --git a/vendor/codeberg.org/gruf/go-atomics/int.go b/vendor/codeberg.org/gruf/go-atomics/int.go new file mode 100644 index 000000000..019ca1034 --- /dev/null +++ b/vendor/codeberg.org/gruf/go-atomics/int.go @@ -0,0 +1,69 @@ +package atomics + +import "sync/atomic" + +// Int32 provides user-friendly means of performing atomic operations on int32 types. +type Int32 int32 + +// NewInt32 will return a new Int32 instance initialized with zero value. +func NewInt32() *Int32 { + return new(Int32) +} + +// Add will atomically add int32 delta to value in address contained within i, returning new value. +func (i *Int32) Add(delta int32) int32 { + return atomic.AddInt32((*int32)(i), delta) +} + +// Store will atomically store int32 value in address contained within i. +func (i *Int32) Store(val int32) { + atomic.StoreInt32((*int32)(i), val) +} + +// Load will atomically load int32 value at address contained within i. +func (i *Int32) Load() int32 { + return atomic.LoadInt32((*int32)(i)) +} + +// CAS performs a compare-and-swap for a(n) int32 value at address contained within i. +func (i *Int32) CAS(cmp, swp int32) bool { + return atomic.CompareAndSwapInt32((*int32)(i), cmp, swp) +} + +// Swap atomically stores new int32 value into address contained within i, and returns previous value. +func (i *Int32) Swap(swp int32) int32 { + return atomic.SwapInt32((*int32)(i), swp) +} + +// Int64 provides user-friendly means of performing atomic operations on int64 types. +type Int64 int64 + +// NewInt64 will return a new Int64 instance initialized with zero value. +func NewInt64() *Int64 { + return new(Int64) +} + +// Add will atomically add int64 delta to value in address contained within i, returning new value. +func (i *Int64) Add(delta int64) int64 { + return atomic.AddInt64((*int64)(i), delta) +} + +// Store will atomically store int64 value in address contained within i. +func (i *Int64) Store(val int64) { + atomic.StoreInt64((*int64)(i), val) +} + +// Load will atomically load int64 value at address contained within i. +func (i *Int64) Load() int64 { + return atomic.LoadInt64((*int64)(i)) +} + +// CAS performs a compare-and-swap for a(n) int64 value at address contained within i. +func (i *Int64) CAS(cmp, swp int64) bool { + return atomic.CompareAndSwapInt64((*int64)(i), cmp, swp) +} + +// Swap atomically stores new int64 value into address contained within i, and returns previous value. +func (i *Int64) Swap(swp int64) int64 { + return atomic.SwapInt64((*int64)(i), swp) +} diff --git a/vendor/codeberg.org/gruf/go-atomics/interface.go b/vendor/codeberg.org/gruf/go-atomics/interface.go new file mode 100644 index 000000000..f0d1c4355 --- /dev/null +++ b/vendor/codeberg.org/gruf/go-atomics/interface.go @@ -0,0 +1,57 @@ +package atomics + +import ( + "sync/atomic" + "unsafe" +) + +// Interface provides user-friendly means of performing atomic operations on interface{} types. +type Interface struct{ ptr unsafe.Pointer } + +// NewInterface will return a new Interface instance initialized with zero value. +func NewInterface() *Interface { + var v interface{} + return &Interface{ + ptr: unsafe.Pointer(&v), + } +} + +// Store will atomically store interface{} value in address contained within v. +func (v *Interface) Store(val interface{}) { + atomic.StorePointer(&v.ptr, unsafe.Pointer(&val)) +} + +// Load will atomically load interface{} value at address contained within v. +func (v *Interface) Load() interface{} { + return *(*interface{})(atomic.LoadPointer(&v.ptr)) +} + +// CAS performs a compare-and-swap for a(n) interface{} value at address contained within v. +func (v *Interface) CAS(cmp, swp interface{}) bool { + for { + // Load current value at address + ptr := atomic.LoadPointer(&v.ptr) + cur := *(*interface{})(ptr) + + // Perform comparison against current + if !(cur == cmp) { + return false + } + + // Attempt to replace pointer + if atomic.CompareAndSwapPointer( + &v.ptr, + ptr, + unsafe.Pointer(&swp), + ) { + return true + } + } +} + +// Swap atomically stores new interface{} value into address contained within v, and returns previous value. +func (v *Interface) Swap(swp interface{}) interface{} { + ptr := unsafe.Pointer(&swp) + ptr = atomic.SwapPointer(&v.ptr, ptr) + return *(*interface{})(ptr) +} diff --git a/vendor/codeberg.org/gruf/go-atomics/state.go b/vendor/codeberg.org/gruf/go-atomics/state.go new file mode 100644 index 000000000..21892f378 --- /dev/null +++ b/vendor/codeberg.org/gruf/go-atomics/state.go @@ -0,0 +1,58 @@ +package atomics + +import "sync" + +// State provides user-friendly means of performing atomic-like +// operations on a uint32 state, and allowing callbacks on successful +// state change. This is a bit of a misnomer being where it is, as it +// actually uses a mutex under-the-hood. +type State struct { + mutex sync.Mutex + state uint32 +} + +// Store will update State value safely within mutex lock. +func (st *State) Store(val uint32) { + st.mutex.Lock() + st.state = val + st.mutex.Unlock() +} + +// Load will get value of State safely within mutex lock. +func (st *State) Load() uint32 { + st.mutex.Lock() + state := st.state + st.mutex.Unlock() + return state +} + +// WithLock performs fn within State mutex lock, useful if you want +// to just use State's mutex for locking instead of creating another. +func (st *State) WithLock(fn func()) { + st.mutex.Lock() + defer st.mutex.Unlock() + fn() +} + +// Update performs fn within State mutex lock, with the current state +// value provided as an argument, and return value used to update state. +func (st *State) Update(fn func(state uint32) uint32) { + st.mutex.Lock() + defer st.mutex.Unlock() + st.state = fn(st.state) +} + +// CAS performs a compare-and-swap on State, calling fn on success. Success value is also returned. +func (st *State) CAS(cmp, swp uint32, fn func()) (ok bool) { + // Acquire lock + st.mutex.Lock() + defer st.mutex.Unlock() + + // Perform CAS operation, fn() on success + if ok = (st.state == cmp); ok { + st.state = swp + fn() + } + + return +} diff --git a/vendor/codeberg.org/gruf/go-atomics/string.go b/vendor/codeberg.org/gruf/go-atomics/string.go new file mode 100644 index 000000000..a0a6e115f --- /dev/null +++ b/vendor/codeberg.org/gruf/go-atomics/string.go @@ -0,0 +1,57 @@ +package atomics + +import ( + "sync/atomic" + "unsafe" +) + +// String provides user-friendly means of performing atomic operations on string types. +type String struct{ ptr unsafe.Pointer } + +// NewString will return a new String instance initialized with zero value. +func NewString() *String { + var v string + return &String{ + ptr: unsafe.Pointer(&v), + } +} + +// Store will atomically store string value in address contained within v. +func (v *String) Store(val string) { + atomic.StorePointer(&v.ptr, unsafe.Pointer(&val)) +} + +// Load will atomically load string value at address contained within v. +func (v *String) Load() string { + return *(*string)(atomic.LoadPointer(&v.ptr)) +} + +// CAS performs a compare-and-swap for a(n) string value at address contained within v. +func (v *String) CAS(cmp, swp string) bool { + for { + // Load current value at address + ptr := atomic.LoadPointer(&v.ptr) + cur := *(*string)(ptr) + + // Perform comparison against current + if !(cur == cmp) { + return false + } + + // Attempt to replace pointer + if atomic.CompareAndSwapPointer( + &v.ptr, + ptr, + unsafe.Pointer(&swp), + ) { + return true + } + } +} + +// Swap atomically stores new string value into address contained within v, and returns previous value. +func (v *String) Swap(swp string) string { + ptr := unsafe.Pointer(&swp) + ptr = atomic.SwapPointer(&v.ptr, ptr) + return *(*string)(ptr) +} diff --git a/vendor/codeberg.org/gruf/go-atomics/time.go b/vendor/codeberg.org/gruf/go-atomics/time.go new file mode 100644 index 000000000..4bf20cc74 --- /dev/null +++ b/vendor/codeberg.org/gruf/go-atomics/time.go @@ -0,0 +1,58 @@ +package atomics + +import ( + "sync/atomic" + "time" + "unsafe" +) + +// Time provides user-friendly means of performing atomic operations on time.Time types. +type Time struct{ ptr unsafe.Pointer } + +// NewTime will return a new Time instance initialized with zero value. +func NewTime() *Time { + var v time.Time + return &Time{ + ptr: unsafe.Pointer(&v), + } +} + +// Store will atomically store time.Time value in address contained within v. +func (v *Time) Store(val time.Time) { + atomic.StorePointer(&v.ptr, unsafe.Pointer(&val)) +} + +// Load will atomically load time.Time value at address contained within v. +func (v *Time) Load() time.Time { + return *(*time.Time)(atomic.LoadPointer(&v.ptr)) +} + +// CAS performs a compare-and-swap for a(n) time.Time value at address contained within v. +func (v *Time) CAS(cmp, swp time.Time) bool { + for { + // Load current value at address + ptr := atomic.LoadPointer(&v.ptr) + cur := *(*time.Time)(ptr) + + // Perform comparison against current + if !(cur.Equal(cmp)) { + return false + } + + // Attempt to replace pointer + if atomic.CompareAndSwapPointer( + &v.ptr, + ptr, + unsafe.Pointer(&swp), + ) { + return true + } + } +} + +// Swap atomically stores new time.Time value into address contained within v, and returns previous value. +func (v *Time) Swap(swp time.Time) time.Time { + ptr := unsafe.Pointer(&swp) + ptr = atomic.SwapPointer(&v.ptr, ptr) + return *(*time.Time)(ptr) +} diff --git a/vendor/codeberg.org/gruf/go-atomics/uint.go b/vendor/codeberg.org/gruf/go-atomics/uint.go new file mode 100644 index 000000000..087e231d1 --- /dev/null +++ b/vendor/codeberg.org/gruf/go-atomics/uint.go @@ -0,0 +1,69 @@ +package atomics + +import "sync/atomic" + +// Uint32 provides user-friendly means of performing atomic operations on uint32 types. +type Uint32 uint32 + +// NewUint32 will return a new Uint32 instance initialized with zero value. +func NewUint32() *Uint32 { + return new(Uint32) +} + +// Add will atomically add uint32 delta to value in address contained within i, returning new value. +func (u *Uint32) Add(delta uint32) uint32 { + return atomic.AddUint32((*uint32)(u), delta) +} + +// Store will atomically store uint32 value in address contained within i. +func (u *Uint32) Store(val uint32) { + atomic.StoreUint32((*uint32)(u), val) +} + +// Load will atomically load uint32 value at address contained within i. +func (u *Uint32) Load() uint32 { + return atomic.LoadUint32((*uint32)(u)) +} + +// CAS performs a compare-and-swap for a(n) uint32 value at address contained within i. +func (u *Uint32) CAS(cmp, swp uint32) bool { + return atomic.CompareAndSwapUint32((*uint32)(u), cmp, swp) +} + +// Swap atomically stores new uint32 value into address contained within i, and returns previous value. +func (u *Uint32) Swap(swp uint32) uint32 { + return atomic.SwapUint32((*uint32)(u), swp) +} + +// Uint64 provides user-friendly means of performing atomic operations on uint64 types. +type Uint64 uint64 + +// NewUint64 will return a new Uint64 instance initialized with zero value. +func NewUint64() *Uint64 { + return new(Uint64) +} + +// Add will atomically add uint64 delta to value in address contained within i, returning new value. +func (u *Uint64) Add(delta uint64) uint64 { + return atomic.AddUint64((*uint64)(u), delta) +} + +// Store will atomically store uint64 value in address contained within i. +func (u *Uint64) Store(val uint64) { + atomic.StoreUint64((*uint64)(u), val) +} + +// Load will atomically load uint64 value at address contained within i. +func (u *Uint64) Load() uint64 { + return atomic.LoadUint64((*uint64)(u)) +} + +// CAS performs a compare-and-swap for a(n) uint64 value at address contained within i. +func (u *Uint64) CAS(cmp, swp uint64) bool { + return atomic.CompareAndSwapUint64((*uint64)(u), cmp, swp) +} + +// Swap atomically stores new uint64 value into address contained within i, and returns previous value. +func (u *Uint64) Swap(swp uint64) uint64 { + return atomic.SwapUint64((*uint64)(u), swp) +} diff --git a/vendor/codeberg.org/gruf/go-bitutil/flag.go b/vendor/codeberg.org/gruf/go-bitutil/flag.go index 6e3b36c66..d8b0f8b66 100644 --- a/vendor/codeberg.org/gruf/go-bitutil/flag.go +++ b/vendor/codeberg.org/gruf/go-bitutil/flag.go @@ -1,7 +1,7 @@ package bitutil import ( - "codeberg.org/gruf/go-bytes" + "codeberg.org/gruf/go-byteutil" ) // Flags8 is a type-casted unsigned integer with helper @@ -173,7 +173,7 @@ func (f Flags8) Unset7() Flags8 { // String returns a human readable representation of Flags8. func (f Flags8) String() string { var val bool - var buf bytes.Buffer + var buf byteutil.Buffer buf.WriteByte('{') @@ -210,7 +210,7 @@ func (f Flags8) String() string { // GoString returns a more verbose human readable representation of Flags8. func (f Flags8) GoString() string { var val bool - var buf bytes.Buffer + var buf byteutil.Buffer buf.WriteString("bitutil.Flags8{") @@ -557,7 +557,7 @@ func (f Flags16) Unset15() Flags16 { // String returns a human readable representation of Flags16. func (f Flags16) String() string { var val bool - var buf bytes.Buffer + var buf byteutil.Buffer buf.WriteByte('{') @@ -618,7 +618,7 @@ func (f Flags16) String() string { // GoString returns a more verbose human readable representation of Flags16. func (f Flags16) GoString() string { var val bool - var buf bytes.Buffer + var buf byteutil.Buffer buf.WriteString("bitutil.Flags16{") @@ -1277,7 +1277,7 @@ func (f Flags32) Unset31() Flags32 { // String returns a human readable representation of Flags32. func (f Flags32) String() string { var val bool - var buf bytes.Buffer + var buf byteutil.Buffer buf.WriteByte('{') @@ -1386,7 +1386,7 @@ func (f Flags32) String() string { // GoString returns a more verbose human readable representation of Flags32. func (f Flags32) GoString() string { var val bool - var buf bytes.Buffer + var buf byteutil.Buffer buf.WriteString("bitutil.Flags32{") @@ -2669,7 +2669,7 @@ func (f Flags64) Unset63() Flags64 { // String returns a human readable representation of Flags64. func (f Flags64) String() string { var val bool - var buf bytes.Buffer + var buf byteutil.Buffer buf.WriteByte('{') @@ -2874,7 +2874,7 @@ func (f Flags64) String() string { // GoString returns a more verbose human readable representation of Flags64. func (f Flags64) GoString() string { var val bool - var buf bytes.Buffer + var buf byteutil.Buffer buf.WriteString("bitutil.Flags64{") diff --git a/vendor/codeberg.org/gruf/go-bitutil/flag.tpl b/vendor/codeberg.org/gruf/go-bitutil/flag.tpl index 80912e24d..89f881930 100644 --- a/vendor/codeberg.org/gruf/go-bitutil/flag.tpl +++ b/vendor/codeberg.org/gruf/go-bitutil/flag.tpl @@ -3,7 +3,7 @@ package bitutil import ( "strings" - "codeberg.org/gruf/go-bytes" + "codeberg.org/gruf/go-byteutil" ) {{ range $idx, $size := . }} @@ -55,7 +55,7 @@ func (f Flags{{ $size.Size }}) Unset{{ $idx }}() Flags{{ $size.Size }} { // String returns a human readable representation of Flags{{ $size.Size }}. func (f Flags{{ $size.Size }}) String() string { var val bool - var buf bytes.Buffer + var buf byteutil.Buffer buf.WriteByte('{') {{ range $idx := .Bits }} @@ -71,7 +71,7 @@ func (f Flags{{ $size.Size }}) String() string { // GoString returns a more verbose human readable representation of Flags{{ $size.Size }}. func (f Flags{{ $size.Size }})GoString() string { var val bool - var buf bytes.Buffer + var buf byteutil.Buffer buf.WriteString("bitutil.Flags{{ $size.Size }}{") {{ range $idx := .Bits }} diff --git a/vendor/codeberg.org/gruf/go-byteutil/buffer.go b/vendor/codeberg.org/gruf/go-byteutil/buffer.go index 75b4c61c7..9e15c8ade 100644 --- a/vendor/codeberg.org/gruf/go-byteutil/buffer.go +++ b/vendor/codeberg.org/gruf/go-byteutil/buffer.go @@ -127,3 +127,8 @@ func (buf *Buffer) Reset() { func (buf *Buffer) String() string { return B2S(buf.B) } + +// Full returns the full capacity byteslice allocated for this buffer. +func (buf *Buffer) Full() []byte { + return buf.B[0:cap(buf.B)] +} diff --git a/vendor/codeberg.org/gruf/go-cache/v2/cache.go b/vendor/codeberg.org/gruf/go-cache/v2/cache.go index 89ad314ee..b0d697687 100644 --- a/vendor/codeberg.org/gruf/go-cache/v2/cache.go +++ b/vendor/codeberg.org/gruf/go-cache/v2/cache.go @@ -61,7 +61,7 @@ type Cache[Key comparable, Value any] interface { // New returns a new initialized Cache. func New[K comparable, V any]() Cache[K, V] { - c := TTLCache[K, V]{} + c := &TTLCache[K, V]{} c.Init() - return &c + return c } diff --git a/vendor/codeberg.org/gruf/go-cache/v2/lookup.go b/vendor/codeberg.org/gruf/go-cache/v2/lookup.go index cddd1317d..d353b2959 100644 --- a/vendor/codeberg.org/gruf/go-cache/v2/lookup.go +++ b/vendor/codeberg.org/gruf/go-cache/v2/lookup.go @@ -40,9 +40,9 @@ type LookupCache[OGKey, AltKey comparable, Value any] interface { } type lookupTTLCache[OK, AK comparable, V any] struct { + TTLCache[OK, V] config LookupCfg[OK, AK, V] lookup LookupMap[OK, AK] - TTLCache[OK, V] } // NewLookup returns a new initialized LookupCache. @@ -55,14 +55,13 @@ func NewLookup[OK, AK comparable, V any](cfg LookupCfg[OK, AK, V]) LookupCache[O case cfg.DeleteLookups == nil: panic("cache: nil delete lookups function") } - c := lookupTTLCache[OK, AK, V]{config: cfg} + c := &lookupTTLCache[OK, AK, V]{config: cfg} c.TTLCache.Init() c.lookup.lookup = make(map[string]map[AK]OK) c.config.RegisterLookups(&c.lookup) c.SetEvictionCallback(nil) c.SetInvalidateCallback(nil) - c.lookup.initd = true - return &c + return c } func (c *lookupTTLCache[OK, AK, V]) SetEvictionCallback(hook Hook[OK, V]) { @@ -158,16 +157,13 @@ func (c *lookupTTLCache[OK, AK, V]) InvalidateBy(lookup string, key AK) bool { // keys to primary keys under supplied lookup identifiers. // This is essentially a wrapper around map[string](map[K1]K2). type LookupMap[OK comparable, AK comparable] struct { - initd bool lookup map[string](map[AK]OK) } // RegisterLookup registers a lookup identifier in the LookupMap, // note this can only be doing during the cfg.RegisterLookups() hook. func (l *LookupMap[OK, AK]) RegisterLookup(id string) { - if l.initd { - panic("cache: cannot register lookup after initialization") - } else if _, ok := l.lookup[id]; ok { + if _, ok := l.lookup[id]; ok { panic("cache: lookup mapping already exists for identifier") } l.lookup[id] = make(map[AK]OK, 100) diff --git a/vendor/codeberg.org/gruf/go-cache/v2/scheduler.go b/vendor/codeberg.org/gruf/go-cache/v2/scheduler.go new file mode 100644 index 000000000..bc1d8074a --- /dev/null +++ b/vendor/codeberg.org/gruf/go-cache/v2/scheduler.go @@ -0,0 +1,17 @@ +package cache + +import ( + "time" + + "codeberg.org/gruf/go-sched" +) + +// scheduler is the global cache runtime scheduler +// for handling regular cache evictions. +var scheduler = sched.NewScheduler(5) + +// schedule will given sweep routine to the global scheduler, and start global scheduler. +func schedule(sweep func(time.Time), freq time.Duration) func() { + go scheduler.Start() // does nothing if already running + return scheduler.Schedule(sched.NewJob(sweep).Every(freq)) +} diff --git a/vendor/codeberg.org/gruf/go-cache/v2/ttl.go b/vendor/codeberg.org/gruf/go-cache/v2/ttl.go index 42f28b53b..a5b6637b2 100644 --- a/vendor/codeberg.org/gruf/go-cache/v2/ttl.go +++ b/vendor/codeberg.org/gruf/go-cache/v2/ttl.go @@ -1,11 +1,8 @@ package cache import ( - "context" "sync" "time" - - "codeberg.org/gruf/go-runners" ) // TTLCache is the underlying Cache implementation, providing both the base @@ -16,11 +13,11 @@ type TTLCache[Key comparable, Value any] struct { evict Hook[Key, Value] // the evict hook is called when an item is evicted from the cache, includes manual delete invalid Hook[Key, Value] // the invalidate hook is called when an item's data in the cache is invalidated ttl time.Duration // ttl is the item TTL - svc runners.Service // svc manages running of the cache eviction routine + stop func() // stop is the cancel function for the scheduled eviction routine mu sync.Mutex // mu protects TTLCache for concurrent access } -// Init performs Cache initialization, this MUST be called. +// Init performs Cache initialization. MUST be called. func (c *TTLCache[K, V]) Init() { c.cache = make(map[K](*entry[V]), 100) c.evict = emptyHook[K, V] @@ -28,68 +25,48 @@ func (c *TTLCache[K, V]) Init() { c.ttl = time.Minute * 5 } -func (c *TTLCache[K, V]) Start(freq time.Duration) bool { +func (c *TTLCache[K, V]) Start(freq time.Duration) (ok bool) { // Nothing to start if freq <= 0 { return false } - // Track state of starting - done := make(chan struct{}) - started := false - - go func() { - ran := c.svc.Run(func(ctx context.Context) { - // Successfully started - started = true - close(done) + // Safely start + c.mu.Lock() - // start routine - c.run(ctx, freq) - }) + if ok = c.stop == nil; ok { + // Not yet running, schedule us + c.stop = schedule(c.sweep, freq) + } - // failed to start - if !ran { - close(done) - } - }() + // Done with lock + c.mu.Unlock() - <-done - return started + return } -func (c *TTLCache[K, V]) Stop() bool { - return c.svc.Stop() -} +func (c *TTLCache[K, V]) Stop() (ok bool) { + // Safely stop + c.mu.Lock() -func (c *TTLCache[K, V]) run(ctx context.Context, freq time.Duration) { - t := time.NewTimer(freq) - for { - select { - // we got stopped - case <-ctx.Done(): - if !t.Stop() { - <-t.C - } - return - - // next tick - case <-t.C: - c.sweep() - t.Reset(freq) - } + if ok = c.stop != nil; ok { + // We're running, cancel evicts + c.stop() + c.stop = nil } + + // Done with lock + c.mu.Unlock() + + return } // sweep attempts to evict expired items (with callback!) from cache. -func (c *TTLCache[K, V]) sweep() { +func (c *TTLCache[K, V]) sweep(now time.Time) { // Lock and defer unlock (in case of hook panic) c.mu.Lock() defer c.mu.Unlock() - // Fetch current time for TTL check - now := time.Now() - // Sweep the cache for old items! for key, item := range c.cache { if now.After(item.expiry) { @@ -116,9 +93,9 @@ func (c *TTLCache[K, V]) SetEvictionCallback(hook Hook[K, V]) { } // Safely set evict hook - c.Lock() + c.mu.Lock() c.evict = hook - c.Unlock() + c.mu.Unlock() } func (c *TTLCache[K, V]) SetInvalidateCallback(hook Hook[K, V]) { @@ -128,14 +105,14 @@ func (c *TTLCache[K, V]) SetInvalidateCallback(hook Hook[K, V]) { } // Safely set invalidate hook - c.Lock() + c.mu.Lock() c.invalid = hook - c.Unlock() + c.mu.Unlock() } func (c *TTLCache[K, V]) SetTTL(ttl time.Duration, update bool) { // Safely update TTL - c.Lock() + c.mu.Lock() diff := ttl - c.ttl c.ttl = ttl @@ -147,13 +124,13 @@ func (c *TTLCache[K, V]) SetTTL(ttl time.Duration, update bool) { } // We're done - c.Unlock() + c.mu.Unlock() } func (c *TTLCache[K, V]) Get(key K) (V, bool) { - c.Lock() + c.mu.Lock() value, ok := c.GetUnsafe(key) - c.Unlock() + c.mu.Unlock() return value, ok } @@ -169,9 +146,9 @@ func (c *TTLCache[K, V]) GetUnsafe(key K) (V, bool) { } func (c *TTLCache[K, V]) Put(key K, value V) bool { - c.Lock() + c.mu.Lock() success := c.PutUnsafe(key, value) - c.Unlock() + c.mu.Unlock() return success } @@ -192,8 +169,8 @@ func (c *TTLCache[K, V]) PutUnsafe(key K, value V) bool { } func (c *TTLCache[K, V]) Set(key K, value V) { - c.Lock() - defer c.Unlock() // defer in case of hook panic + c.mu.Lock() + defer c.mu.Unlock() // defer in case of hook panic c.SetUnsafe(key, value) } @@ -215,9 +192,9 @@ func (c *TTLCache[K, V]) SetUnsafe(key K, value V) { } func (c *TTLCache[K, V]) CAS(key K, cmp V, swp V) bool { - c.Lock() + c.mu.Lock() ok := c.CASUnsafe(key, cmp, swp) - c.Unlock() + c.mu.Unlock() return ok } @@ -240,9 +217,9 @@ func (c *TTLCache[K, V]) CASUnsafe(key K, cmp V, swp V) bool { } func (c *TTLCache[K, V]) Swap(key K, swp V) V { - c.Lock() + c.mu.Lock() old := c.SwapUnsafe(key, swp) - c.Unlock() + c.mu.Unlock() return old } @@ -267,9 +244,9 @@ func (c *TTLCache[K, V]) SwapUnsafe(key K, swp V) V { } func (c *TTLCache[K, V]) Has(key K) bool { - c.Lock() + c.mu.Lock() ok := c.HasUnsafe(key) - c.Unlock() + c.mu.Unlock() return ok } @@ -280,8 +257,8 @@ func (c *TTLCache[K, V]) HasUnsafe(key K) bool { } func (c *TTLCache[K, V]) Invalidate(key K) bool { - c.Lock() - defer c.Unlock() + c.mu.Lock() + defer c.mu.Unlock() return c.InvalidateUnsafe(key) } @@ -300,8 +277,8 @@ func (c *TTLCache[K, V]) InvalidateUnsafe(key K) bool { } func (c *TTLCache[K, V]) Clear() { - c.Lock() - defer c.Unlock() + c.mu.Lock() + defer c.mu.Unlock() c.ClearUnsafe() } @@ -314,9 +291,9 @@ func (c *TTLCache[K, V]) ClearUnsafe() { } func (c *TTLCache[K, V]) Size() int { - c.Lock() + c.mu.Lock() sz := c.SizeUnsafe() - c.Unlock() + c.mu.Unlock() return sz } diff --git a/vendor/codeberg.org/gruf/go-debug/debug.go b/vendor/codeberg.org/gruf/go-debug/debug.go index 61e4eda41..6b5e56548 100644 --- a/vendor/codeberg.org/gruf/go-debug/debug.go +++ b/vendor/codeberg.org/gruf/go-debug/debug.go @@ -1,5 +1,9 @@ package debug +import ( + _debug "runtime/debug" +) + // DEBUG returns whether debugging is enabled. func DEBUG() bool { return debug @@ -11,3 +15,44 @@ func Run(fn func()) { fn() } } + +// BuildInfo will return a useful new-line separated build info string for current binary, setting name as given value. +func BuildInfo(name string) string { + // Read build info from current binary + build, ok := _debug.ReadBuildInfo() + if !ok { + return "name=" + name + "\n" + } + + var flags, vcs, commit, time string + + // Parse build information from BuildInfo.Settings + for i := 0; i < len(build.Settings); i++ { + switch build.Settings[i].Key { + case "-gcflags": + flags += ` -gcflags="` + build.Settings[i].Value + `"` + case "-ldflags": + flags += ` -ldflags="` + build.Settings[i].Value + `"` + case "-tags": + flags += ` -tags="` + build.Settings[i].Value + `"` + case "vcs": + vcs = build.Settings[i].Value + case "vcs.revision": + commit = build.Settings[i].Value + if len(commit) > 8 { + commit = commit[:8] + } + case "vcs.time": + time = build.Settings[i].Value + } + } + + return "" + + "name=" + name + "\n" + + "vcs=" + vcs + "\n" + + "commit=" + commit + "\n" + + "version=" + build.Main.Version + "\n" + + "path=" + build.Path + "\n" + + "build=" + build.GoVersion + flags + "\n" + + "time=" + time + "\n" +} diff --git a/vendor/codeberg.org/gruf/go-errors/v2/standard.go b/vendor/codeberg.org/gruf/go-errors/v2/standard.go index 225d9e0c1..2a4671153 100644 --- a/vendor/codeberg.org/gruf/go-errors/v2/standard.go +++ b/vendor/codeberg.org/gruf/go-errors/v2/standard.go @@ -18,14 +18,21 @@ import ( func Is(err error, targets ...error) bool { var flags bitutil.Flags64 + // Flags only has 64 bit slots if len(targets) > 64 { panic("too many targets") } - // Determine if each of targets are comparable + // Check if error is nil so we can catch + // the fast-case where a target is nil + isNil := (err == nil) + for i := 0; i < len(targets); { - // Drop nil errors + // Drop nil targets if targets[i] == nil { + if isNil /* match! */ { + return true + } targets = append(targets[:i], targets[i+1:]...) continue } diff --git a/vendor/codeberg.org/gruf/go-sched/LICENSE b/vendor/codeberg.org/gruf/go-sched/LICENSE new file mode 100644 index 000000000..e4163ae35 --- /dev/null +++ b/vendor/codeberg.org/gruf/go-sched/LICENSE @@ -0,0 +1,9 @@ +MIT License + +Copyright (c) 2022 gruf + +Permission is hereby granted, free of charge, to any person obtaining a copy of this software and associated documentation files (the "Software"), to deal in the Software without restriction, including without limitation the rights to use, copy, modify, merge, publish, distribute, sublicense, and/or sell copies of the Software, and to permit persons to whom the Software is furnished to do so, subject to the following conditions: + +The above copyright notice and this permission notice shall be included in all copies or substantial portions of the Software. + +THE SOFTWARE IS PROVIDED "AS IS", WITHOUT WARRANTY OF ANY KIND, EXPRESS OR IMPLIED, INCLUDING BUT NOT LIMITED TO THE WARRANTIES OF MERCHANTABILITY, FITNESS FOR A PARTICULAR PURPOSE AND NONINFRINGEMENT. IN NO EVENT SHALL THE AUTHORS OR COPYRIGHT HOLDERS BE LIABLE FOR ANY CLAIM, DAMAGES OR OTHER LIABILITY, WHETHER IN AN ACTION OF CONTRACT, TORT OR OTHERWISE, ARISING FROM, OUT OF OR IN CONNECTION WITH THE SOFTWARE OR THE USE OR OTHER DEALINGS IN THE SOFTWARE. diff --git a/vendor/codeberg.org/gruf/go-sched/README.md b/vendor/codeberg.org/gruf/go-sched/README.md new file mode 100644 index 000000000..d32a961ae --- /dev/null +++ b/vendor/codeberg.org/gruf/go-sched/README.md @@ -0,0 +1,5 @@ +# go-sched + +A simple job (both run-once and recurring) queueing library with down-to millisecond precision. + +Precision estimates based on test output (running on i7-11800h): 1ms precision with 80% tolerance.
\ No newline at end of file diff --git a/vendor/codeberg.org/gruf/go-sched/job.go b/vendor/codeberg.org/gruf/go-sched/job.go new file mode 100644 index 000000000..66e24fe9a --- /dev/null +++ b/vendor/codeberg.org/gruf/go-sched/job.go @@ -0,0 +1,99 @@ +package sched + +import ( + "time" + + "codeberg.org/gruf/go-atomics" +) + +// Job encapsulates logic for a scheduled job to be run according +// to a set Timing, executing the job with a set panic handler, and +// holding onto a next execution time safely in a concurrent environment. +type Job struct { + id uint64 + next atomics.Time + timing Timing + call func(time.Time) + panic func(interface{}) +} + +// NewJob returns a new Job to run given function. +func NewJob(fn func(now time.Time)) *Job { + if fn == nil { + // Ensure a function + panic("nil func") + } + + j := &Job{ // set defaults + timing: emptytiming, // i.e. fire immediately + call: fn, + panic: func(i interface{}) { panic(i) }, + } + + // Init next time ptr + j.next.Store(zerotime) + + return j +} + +// At sets this Job to execute at time, by passing (*sched.Once)(&at) to .With(). See .With() for details. +func (job *Job) At(at time.Time) *Job { + return job.With((*Once)(&at)) +} + +// Every sets this Job to execute every period, by passing sched.Period(period) to .With(). See .With() for details. +func (job *Job) Every(period time.Duration) *Job { + return job.With(Periodic(period)) +} + +// EveryAt sets this Job to execute every period starting at time, by passing &PeriodicAt{once: Once(at), period: Periodic(period)} to .With(). See .With() for details. +func (job *Job) EveryAt(at time.Time, period time.Duration) *Job { + return job.With(&PeriodicAt{Once: Once(at), Period: Periodic(period)}) +} + +// With sets this Job's timing to given implementation, or if already set will wrap existing using sched.TimingWrap{}. +func (job *Job) With(t Timing) *Job { + if t == nil { + // Ensure a timing + panic("nil Timing") + } + + if job.timing == emptytiming { + // Set new timing + job.timing = t + } else { + // Wrap old timing + old := job.timing + job.timing = &TimingWrap{ + Outer: t, + Inner: old, + } + } + + return job +} + +// Panic specifics how this job handles panics, default is an actual panic. +func (job *Job) Panic(fn func(interface{})) *Job { + if fn == nil { + // Ensure a function + panic("nil func") + } + job.panic = fn + return job +} + +// Next returns the next time this Job is expected to run. +func (job *Job) Next() time.Time { + return job.next.Load() +} + +// Run will execute this Job and pass through given now time. +func (job *Job) Run(now time.Time) { + defer func() { + if r := recover(); r != nil { + job.panic(r) + } + }() + job.call(now) +} diff --git a/vendor/codeberg.org/gruf/go-sched/scheduler.go b/vendor/codeberg.org/gruf/go-sched/scheduler.go new file mode 100644 index 000000000..d017ddcf6 --- /dev/null +++ b/vendor/codeberg.org/gruf/go-sched/scheduler.go @@ -0,0 +1,240 @@ +package sched + +import ( + "context" + "sort" + "time" + + "codeberg.org/gruf/go-atomics" + "codeberg.org/gruf/go-runners" +) + +var ( + // neverticks is a timer channel that never ticks (it's starved). + neverticks = make(chan time.Time) + + // alwaysticks is a timer channel that always ticks (it's closed). + alwaysticks = func() chan time.Time { + ch := make(chan time.Time) + close(ch) + return ch + }() +) + +// Scheduler provides a means of running jobs at specific times and +// regular intervals, all while sharing a single underlying timer. +type Scheduler struct { + jobs []*Job // jobs is a list of tracked Jobs to be executed + jch chan interface{} // jch accepts either Jobs or job IDs to notify new/removed jobs + svc runners.Service // svc manages the main scheduler routine + jid atomics.Uint64 // jid is used to iteratively generate unique IDs for jobs +} + +// New returns a new Scheduler instance with given job change queue size. +func NewScheduler(queue int) Scheduler { + if queue < 0 { + queue = 10 + } + return Scheduler{jch: make(chan interface{}, queue)} +} + +// Start will attempt to start the Scheduler. Immediately returns false if the Service is already running, and true after completed run. +func (sch *Scheduler) Start() bool { + return sch.svc.Run(sch.run) +} + +// Stop will attempt to stop the Scheduler. Immediately returns false if not running, and true only after Scheduler is fully stopped. +func (sch *Scheduler) Stop() bool { + return sch.svc.Stop() +} + +// Running will return whether Scheduler is running. +func (sch *Scheduler) Running() bool { + return sch.svc.Running() +} + +// Schedule will add provided Job to the Scheduler, returning a cancel function. +func (sch *Scheduler) Schedule(job *Job) (cancel func()) { + if job == nil { + // Ensure there's a job! + panic("nil job") + } + + // Get last known job ID + last := sch.jid.Load() + + // Give this job an ID and check overflow + if job.id = sch.jid.Add(1); job.id < last { + panic("scheduler job id overflow") + } + + // Pass job to scheduler + sch.jch <- job + + // Return cancel function for job ID + return func() { sch.jch <- job.id } +} + +// run is the main scheduler run routine, which runs for as long as ctx is valid. +func (sch *Scheduler) run(ctx context.Context) { + var ( + // timerset represents whether timer was running + // for a particular run of the loop. false means + // that tch == neverticks || tch == alwaysticks + timerset bool + + // timer tick channel (or a never-tick channel) + tch <-chan time.Time + + // timer notifies this main routine to wake when + // the job queued needs to be checked for executions + timer *time.Timer + + // stopdrain will stop and drain the timer + // if it has been running (i.e. timerset == true) + stopdrain = func() { + if timerset && !timer.Stop() { + <-timer.C + } + } + ) + + for { + select { + // Handle received job/id + case v := <-sch.jch: + sch.handle(v) + continue + + // No more + default: + } + + // Done + break + } + + // Create a stopped timer + timer = time.NewTimer(1) + <-timer.C + + for { + // Reset timer state + timerset = false + + if len(sch.jobs) > 0 { + // Sort jobs by next occurring + sort.Sort(byNext(sch.jobs)) + + // Get execution time + now := time.Now() + + // Get next job time + next := sch.jobs[0].Next() + + if until := next.Sub(now); until <= 0 { + // This job is behind schedule, + // set timer to always tick + tch = alwaysticks + } else { + // Reset timer to period + timer.Reset(until) + tch = timer.C + timerset = true + } + } else { + // Unset timer + tch = neverticks + } + + select { + // Scheduler stopped + case <-ctx.Done(): + stopdrain() + return + + // Timer ticked, run scheduled + case now := <-tch: + sch.schedule(now) + + // Received update, handle job/id + case v := <-sch.jch: + sch.handle(v) + stopdrain() + } + } +} + +// handle takes an interfaces received from Scheduler.jch and handles either: +// - Job --> new job to add. +// - uint64 --> job ID to remove. +func (sch *Scheduler) handle(v interface{}) { + switch v := v.(type) { + // New job added + case *Job: + // Get current time + now := time.Now() + + // Update the next call time + next := v.timing.Next(now) + v.next.Store(next) + + // Append this job to queued + sch.jobs = append(sch.jobs, v) + + // Job removed + case uint64: + for i := 0; i < len(sch.jobs); i++ { + if sch.jobs[i].id == v { + // This is the job we're looking for! Drop this + sch.jobs = append(sch.jobs[:i], sch.jobs[i+1:]...) + return + } + } + } +} + +// schedule will iterate through the scheduler jobs and execute those necessary, updating their next call time. +func (sch *Scheduler) schedule(now time.Time) { + for i := 0; i < len(sch.jobs); { + // Scope our own var + job := sch.jobs[i] + + // We know these jobs are ordered by .Next(), so as soon + // as we reach one with .Next() after now, we can return + if job.Next().After(now) { + return + } + + // Update the next call time + next := job.timing.Next(now) + job.next.Store(next) + + // Run this job async! + go job.Run(now) + + if job.Next().IsZero() { + // Zero time, this job is done and can be dropped + sch.jobs = append(sch.jobs[:i], sch.jobs[i+1:]...) + continue + } + + // Iter + i++ + } +} + +// byNext is an implementation of sort.Interface to sort Jobs by their .Next() time. +type byNext []*Job + +func (by byNext) Len() int { + return len(by) +} + +func (by byNext) Less(i int, j int) bool { + return by[i].Next().Before(by[j].Next()) +} + +func (by byNext) Swap(i int, j int) { + by[i], by[j] = by[j], by[i] +} diff --git a/vendor/codeberg.org/gruf/go-sched/timing.go b/vendor/codeberg.org/gruf/go-sched/timing.go new file mode 100644 index 000000000..33c230fa5 --- /dev/null +++ b/vendor/codeberg.org/gruf/go-sched/timing.go @@ -0,0 +1,92 @@ +package sched + +import ( + "time" +) + +var ( + // zerotime is zero time.Time (unix epoch). + zerotime = time.Time{} + + // emptytiming is a global timingempty to check against. + emptytiming = timingempty{} +) + +// Timing provides scheduling for a Job, determining the next time +// for given current time that execution is required. Please note that +// calls to .Next() may alter the results of the next call, and should +// only be called by the Scheduler. +type Timing interface { + Next(time.Time) time.Time +} + +// timingempty is a 'zero' Timing implementation that always returns zero time. +type timingempty struct{} + +func (timingempty) Next(time.Time) time.Time { + return zerotime +} + +// Once implements Timing to provide a run-once Job execution. +type Once time.Time + +func (o *Once) Next(time.Time) time.Time { + ret := *(*time.Time)(o) + *o = Once(zerotime) // reset + return ret +} + +// Periodic implements Timing to provide a recurring Job execution. +type Periodic time.Duration + +func (p Periodic) Next(now time.Time) time.Time { + return now.Add(time.Duration(p)) +} + +// PeriodicAt implements Timing to provide a recurring Job execution starting at 'Once' time. +type PeriodicAt struct { + Once Once + Period Periodic +} + +func (p *PeriodicAt) Next(now time.Time) time.Time { + if next := p.Once.Next(now); !next.IsZero() { + return next + } + return p.Period.Next(now) +} + +// TimingWrap allows combining two different Timing implementations. +type TimingWrap struct { + Outer Timing + Inner Timing + + // determined next times + outerNext time.Time + innerNext time.Time +} + +func (t *TimingWrap) Next(now time.Time) time.Time { + if t.outerNext.IsZero() { + // Regenerate outermost next run time + t.outerNext = t.Outer.Next(now) + } + + if t.innerNext.IsZero() { + // Regenerate innermost next run time + t.innerNext = t.Inner.Next(now) + } + + // If outer comes before inner, return outer + if t.outerNext != zerotime && + t.outerNext.Before(t.innerNext) { + next := t.outerNext + t.outerNext = zerotime + return next + } + + // Else, return inner + next := t.innerNext + t.innerNext = zerotime + return next +} diff --git a/vendor/github.com/ReneKroon/ttlcache/.travis.yml b/vendor/github.com/ReneKroon/ttlcache/.travis.yml deleted file mode 100644 index 095be4ff3..000000000 --- a/vendor/github.com/ReneKroon/ttlcache/.travis.yml +++ /dev/null @@ -1,18 +0,0 @@ -language: go - -go: - - "1.14" - - "1.13" -git: - depth: 1 - -install: - - go install -race std - - go install golang.org/x/tools/cmd/cover - - go install golang.org/x/lint/golint - - export PATH=$HOME/gopath/bin:$PATH - -script: - - golint . - - go test -cover -race -count=1 -timeout=30s -run . - - cd bench; go test -run=Bench.* -bench=. -benchmem
\ No newline at end of file diff --git a/vendor/github.com/ReneKroon/ttlcache/LICENSE b/vendor/github.com/ReneKroon/ttlcache/LICENSE deleted file mode 100644 index b3b587dce..000000000 --- a/vendor/github.com/ReneKroon/ttlcache/LICENSE +++ /dev/null @@ -1,21 +0,0 @@ -MIT License - -Copyright (c) 2018 Rene Kroon - -Permission is hereby granted, free of charge, to any person obtaining a copy -of this software and associated documentation files (the "Software"), to deal -in the Software without restriction, including without limitation the rights -to use, copy, modify, merge, publish, distribute, sublicense, and/or sell -copies of the Software, and to permit persons to whom the Software is -furnished to do so, subject to the following conditions: - -The above copyright notice and this permission notice shall be included in all -copies or substantial portions of the Software. - -THE SOFTWARE IS PROVIDED "AS IS", WITHOUT WARRANTY OF ANY KIND, EXPRESS OR -IMPLIED, INCLUDING BUT NOT LIMITED TO THE WARRANTIES OF MERCHANTABILITY, -FITNESS FOR A PARTICULAR PURPOSE AND NONINFRINGEMENT. IN NO EVENT SHALL THE -AUTHORS OR COPYRIGHT HOLDERS BE LIABLE FOR ANY CLAIM, DAMAGES OR OTHER -LIABILITY, WHETHER IN AN ACTION OF CONTRACT, TORT OR OTHERWISE, ARISING FROM, -OUT OF OR IN CONNECTION WITH THE SOFTWARE OR THE USE OR OTHER DEALINGS IN THE -SOFTWARE. diff --git a/vendor/github.com/ReneKroon/ttlcache/Readme.md b/vendor/github.com/ReneKroon/ttlcache/Readme.md deleted file mode 100644 index 9c537fbdc..000000000 --- a/vendor/github.com/ReneKroon/ttlcache/Readme.md +++ /dev/null @@ -1,71 +0,0 @@ -## TTLCache - an in-memory cache with expiration - -TTLCache is a simple key/value cache in golang with the following functions: - -1. Thread-safe -2. Individual expiring time or global expiring time, you can choose -3. Auto-Extending expiration on `Get` -or- DNS style TTL, see `SkipTtlExtensionOnHit(bool)` -4. Fast and memory efficient -5. Can trigger callback on key expiration -6. Cleanup resources by calling `Close()` at end of lifecycle. - -Note (issue #25): by default, due to historic reasons, the TTL will be reset on each cache hit and you need to explicitly configure the cache to use a TTL that will not get extended. - -[](https://travis-ci.org/ReneKroon/ttlcache) - -#### Usage -```go -import ( - "time" - "fmt" - - "github.com/ReneKroon/ttlcache" -) - -func main () { - newItemCallback := func(key string, value interface{}) { - fmt.Printf("New key(%s) added\n", key) - } - checkExpirationCallback := func(key string, value interface{}) bool { - if key == "key1" { - // if the key equals "key1", the value - // will not be allowed to expire - return false - } - // all other values are allowed to expire - return true - } - expirationCallback := func(key string, value interface{}) { - fmt.Printf("This key(%s) has expired\n", key) - } - - cache := ttlcache.NewCache() - defer cache.Close() - cache.SetTTL(time.Duration(10 * time.Second)) - cache.SetExpirationCallback(expirationCallback) - - cache.Set("key", "value") - cache.SetWithTTL("keyWithTTL", "value", 10 * time.Second) - - value, exists := cache.Get("key") - count := cache.Count() - result := cache.Remove("key") -} -``` - -#### TTLCache - Some design considerations - -1. The complexity of the current cache is already quite high. Therefore i will not add 'convenience' features like an interface to supply a function to get missing keys. -2. The locking should be done only in the functions of the Cache struct. Else data races can occur or recursive locks are needed, which are both unwanted. -3. I prefer correct functionality over fast tests. It's ok for new tests to take seconds to proof something. - -#### Original Project - -TTLCache was forked from [wunderlist/ttlcache](https://github.com/wunderlist/ttlcache) to add extra functions not avaiable in the original scope. -The main differences are: - -1. A item can store any kind of object, previously, only strings could be saved -2. Optionally, you can add callbacks too: check if a value should expire, be notified if a value expires, and be notified when new values are added to the cache -3. The expiration can be either global or per item -4. Can exist items without expiration time -5. Expirations and callbacks are realtime. Don't have a pooling time to check anymore, now it's done with a heap. diff --git a/vendor/github.com/ReneKroon/ttlcache/cache.go b/vendor/github.com/ReneKroon/ttlcache/cache.go deleted file mode 100644 index f772d0c7c..000000000 --- a/vendor/github.com/ReneKroon/ttlcache/cache.go +++ /dev/null @@ -1,307 +0,0 @@ -package ttlcache - -import ( - "sync" - "time" -) - -// CheckExpireCallback is used as a callback for an external check on item expiration -type checkExpireCallback func(key string, value interface{}) bool - -// ExpireCallback is used as a callback on item expiration or when notifying of an item new to the cache -type expireCallback func(key string, value interface{}) - -// Cache is a synchronized map of items that can auto-expire once stale -type Cache struct { - mutex sync.Mutex - ttl time.Duration - items map[string]*item - expireCallback expireCallback - checkExpireCallback checkExpireCallback - newItemCallback expireCallback - priorityQueue *priorityQueue - expirationNotification chan bool - expirationTime time.Time - skipTTLExtension bool - shutdownSignal chan (chan struct{}) - isShutDown bool -} - -func (cache *Cache) getItem(key string) (*item, bool, bool) { - item, exists := cache.items[key] - if !exists || item.expired() { - return nil, false, false - } - - if item.ttl >= 0 && (item.ttl > 0 || cache.ttl > 0) { - if cache.ttl > 0 && item.ttl == 0 { - item.ttl = cache.ttl - } - - if !cache.skipTTLExtension { - item.touch() - } - cache.priorityQueue.update(item) - } - - expirationNotification := false - if cache.expirationTime.After(time.Now().Add(item.ttl)) { - expirationNotification = true - } - return item, exists, expirationNotification -} - -func (cache *Cache) startExpirationProcessing() { - timer := time.NewTimer(time.Hour) - for { - var sleepTime time.Duration - cache.mutex.Lock() - if cache.priorityQueue.Len() > 0 { - sleepTime = time.Until(cache.priorityQueue.items[0].expireAt) - if sleepTime < 0 && cache.priorityQueue.items[0].expireAt.IsZero() { - sleepTime = time.Hour - } else if sleepTime < 0 { - sleepTime = time.Microsecond - } - if cache.ttl > 0 { - sleepTime = min(sleepTime, cache.ttl) - } - - } else if cache.ttl > 0 { - sleepTime = cache.ttl - } else { - sleepTime = time.Hour - } - - cache.expirationTime = time.Now().Add(sleepTime) - cache.mutex.Unlock() - - timer.Reset(sleepTime) - select { - case shutdownFeedback := <-cache.shutdownSignal: - timer.Stop() - cache.mutex.Lock() - if cache.priorityQueue.Len() > 0 { - cache.evictjob() - } - cache.mutex.Unlock() - shutdownFeedback <- struct{}{} - return - case <-timer.C: - timer.Stop() - cache.mutex.Lock() - if cache.priorityQueue.Len() == 0 { - cache.mutex.Unlock() - continue - } - - cache.cleanjob() - cache.mutex.Unlock() - - case <-cache.expirationNotification: - timer.Stop() - continue - } - } -} - -func (cache *Cache) evictjob() { - // index will only be advanced if the current entry will not be evicted - i := 0 - for item := cache.priorityQueue.items[i]; ; item = cache.priorityQueue.items[i] { - - cache.priorityQueue.remove(item) - delete(cache.items, item.key) - if cache.expireCallback != nil { - go cache.expireCallback(item.key, item.data) - } - if cache.priorityQueue.Len() == 0 { - return - } - } -} - -func (cache *Cache) cleanjob() { - // index will only be advanced if the current entry will not be evicted - i := 0 - for item := cache.priorityQueue.items[i]; item.expired(); item = cache.priorityQueue.items[i] { - - if cache.checkExpireCallback != nil { - if !cache.checkExpireCallback(item.key, item.data) { - item.touch() - cache.priorityQueue.update(item) - i++ - if i == cache.priorityQueue.Len() { - break - } - continue - } - } - - cache.priorityQueue.remove(item) - delete(cache.items, item.key) - if cache.expireCallback != nil { - go cache.expireCallback(item.key, item.data) - } - if cache.priorityQueue.Len() == 0 { - return - } - } -} - -// Close calls Purge, and then stops the goroutine that does ttl checking, for a clean shutdown. -// The cache is no longer cleaning up after the first call to Close, repeated calls are safe though. -func (cache *Cache) Close() { - - cache.mutex.Lock() - if !cache.isShutDown { - cache.isShutDown = true - cache.mutex.Unlock() - feedback := make(chan struct{}) - cache.shutdownSignal <- feedback - <-feedback - close(cache.shutdownSignal) - } else { - cache.mutex.Unlock() - } - cache.Purge() -} - -// Set is a thread-safe way to add new items to the map -func (cache *Cache) Set(key string, data interface{}) { - cache.SetWithTTL(key, data, ItemExpireWithGlobalTTL) -} - -// SetWithTTL is a thread-safe way to add new items to the map with individual ttl -func (cache *Cache) SetWithTTL(key string, data interface{}, ttl time.Duration) { - cache.mutex.Lock() - item, exists, _ := cache.getItem(key) - - if exists { - item.data = data - item.ttl = ttl - } else { - item = newItem(key, data, ttl) - cache.items[key] = item - } - - if item.ttl >= 0 && (item.ttl > 0 || cache.ttl > 0) { - if cache.ttl > 0 && item.ttl == 0 { - item.ttl = cache.ttl - } - item.touch() - } - - if exists { - cache.priorityQueue.update(item) - } else { - cache.priorityQueue.push(item) - } - - cache.mutex.Unlock() - if !exists && cache.newItemCallback != nil { - cache.newItemCallback(key, data) - } - cache.expirationNotification <- true -} - -// Get is a thread-safe way to lookup items -// Every lookup, also touches the item, hence extending it's life -func (cache *Cache) Get(key string) (interface{}, bool) { - cache.mutex.Lock() - item, exists, triggerExpirationNotification := cache.getItem(key) - - var dataToReturn interface{} - if exists { - dataToReturn = item.data - } - cache.mutex.Unlock() - if triggerExpirationNotification { - cache.expirationNotification <- true - } - return dataToReturn, exists -} - -func (cache *Cache) Remove(key string) bool { - cache.mutex.Lock() - object, exists := cache.items[key] - if !exists { - cache.mutex.Unlock() - return false - } - delete(cache.items, object.key) - cache.priorityQueue.remove(object) - cache.mutex.Unlock() - - return true -} - -// Count returns the number of items in the cache -func (cache *Cache) Count() int { - cache.mutex.Lock() - length := len(cache.items) - cache.mutex.Unlock() - return length -} - -func (cache *Cache) SetTTL(ttl time.Duration) { - cache.mutex.Lock() - cache.ttl = ttl - cache.mutex.Unlock() - cache.expirationNotification <- true -} - -// SetExpirationCallback sets a callback that will be called when an item expires -func (cache *Cache) SetExpirationCallback(callback expireCallback) { - cache.expireCallback = callback -} - -// SetCheckExpirationCallback sets a callback that will be called when an item is about to expire -// in order to allow external code to decide whether the item expires or remains for another TTL cycle -func (cache *Cache) SetCheckExpirationCallback(callback checkExpireCallback) { - cache.checkExpireCallback = callback -} - -// SetNewItemCallback sets a callback that will be called when a new item is added to the cache -func (cache *Cache) SetNewItemCallback(callback expireCallback) { - cache.newItemCallback = callback -} - -// SkipTtlExtensionOnHit allows the user to change the cache behaviour. When this flag is set to true it will -// no longer extend TTL of items when they are retrieved using Get, or when their expiration condition is evaluated -// using SetCheckExpirationCallback. -func (cache *Cache) SkipTtlExtensionOnHit(value bool) { - cache.skipTTLExtension = value -} - -// Purge will remove all entries -func (cache *Cache) Purge() { - cache.mutex.Lock() - cache.items = make(map[string]*item) - cache.priorityQueue = newPriorityQueue() - cache.mutex.Unlock() -} - -// NewCache is a helper to create instance of the Cache struct -func NewCache() *Cache { - - shutdownChan := make(chan chan struct{}) - - cache := &Cache{ - items: make(map[string]*item), - priorityQueue: newPriorityQueue(), - expirationNotification: make(chan bool), - expirationTime: time.Now(), - shutdownSignal: shutdownChan, - isShutDown: false, - } - go cache.startExpirationProcessing() - return cache -} - -func min(duration time.Duration, second time.Duration) time.Duration { - if duration < second { - return duration - } - return second -} diff --git a/vendor/github.com/ReneKroon/ttlcache/item.go b/vendor/github.com/ReneKroon/ttlcache/item.go deleted file mode 100644 index 2f78f49cc..000000000 --- a/vendor/github.com/ReneKroon/ttlcache/item.go +++ /dev/null @@ -1,46 +0,0 @@ -package ttlcache - -import ( - "time" -) - -const ( - // ItemNotExpire Will avoid the item being expired by TTL, but can still be exired by callback etc. - ItemNotExpire time.Duration = -1 - // ItemExpireWithGlobalTTL will use the global TTL when set. - ItemExpireWithGlobalTTL time.Duration = 0 -) - -func newItem(key string, data interface{}, ttl time.Duration) *item { - item := &item{ - data: data, - ttl: ttl, - key: key, - } - // since nobody is aware yet of this item, it's safe to touch without lock here - item.touch() - return item -} - -type item struct { - key string - data interface{} - ttl time.Duration - expireAt time.Time - queueIndex int -} - -// Reset the item expiration time -func (item *item) touch() { - if item.ttl > 0 { - item.expireAt = time.Now().Add(item.ttl) - } -} - -// Verify if the item is expired -func (item *item) expired() bool { - if item.ttl <= 0 { - return false - } - return item.expireAt.Before(time.Now()) -} diff --git a/vendor/github.com/ReneKroon/ttlcache/priority_queue.go b/vendor/github.com/ReneKroon/ttlcache/priority_queue.go deleted file mode 100644 index 11b9c3140..000000000 --- a/vendor/github.com/ReneKroon/ttlcache/priority_queue.go +++ /dev/null @@ -1,71 +0,0 @@ -package ttlcache - -import ( - "container/heap" -) - -func newPriorityQueue() *priorityQueue { - queue := &priorityQueue{} - heap.Init(queue) - return queue -} - -type priorityQueue struct { - items []*item -} - -func (pq *priorityQueue) update(item *item) { - heap.Fix(pq, item.queueIndex) -} - -func (pq *priorityQueue) push(item *item) { - heap.Push(pq, item) -} - -func (pq *priorityQueue) pop() *item { - if pq.Len() == 0 { - return nil - } - return heap.Pop(pq).(*item) -} - -func (pq *priorityQueue) remove(item *item) { - heap.Remove(pq, item.queueIndex) -} - -func (pq priorityQueue) Len() int { - length := len(pq.items) - return length -} - -// Less will consider items with time.Time default value (epoch start) as more than set items. -func (pq priorityQueue) Less(i, j int) bool { - if pq.items[i].expireAt.IsZero() { - return false - } - if pq.items[j].expireAt.IsZero() { - return true - } - return pq.items[i].expireAt.Before(pq.items[j].expireAt) -} - -func (pq priorityQueue) Swap(i, j int) { - pq.items[i], pq.items[j] = pq.items[j], pq.items[i] - pq.items[i].queueIndex = i - pq.items[j].queueIndex = j -} - -func (pq *priorityQueue) Push(x interface{}) { - item := x.(*item) - item.queueIndex = len(pq.items) - pq.items = append(pq.items, item) -} - -func (pq *priorityQueue) Pop() interface{} { - old := pq.items - n := len(old) - item := old[n-1] - item.queueIndex = -1 - pq.items = old[0 : n-1] - return item -} diff --git a/vendor/golang.org/x/exp/AUTHORS b/vendor/golang.org/x/exp/AUTHORS new file mode 100644 index 000000000..15167cd74 --- /dev/null +++ b/vendor/golang.org/x/exp/AUTHORS @@ -0,0 +1,3 @@ +# This source code refers to The Go Authors for copyright purposes. +# The master list of authors is in the main Go distribution, +# visible at http://tip.golang.org/AUTHORS. diff --git a/vendor/golang.org/x/exp/CONTRIBUTORS b/vendor/golang.org/x/exp/CONTRIBUTORS new file mode 100644 index 000000000..1c4577e96 --- /dev/null +++ b/vendor/golang.org/x/exp/CONTRIBUTORS @@ -0,0 +1,3 @@ +# This source code was written by the Go contributors. +# The master list of contributors is in the main Go distribution, +# visible at http://tip.golang.org/CONTRIBUTORS. diff --git a/vendor/golang.org/x/exp/LICENSE b/vendor/golang.org/x/exp/LICENSE new file mode 100644 index 000000000..6a66aea5e --- /dev/null +++ b/vendor/golang.org/x/exp/LICENSE @@ -0,0 +1,27 @@ +Copyright (c) 2009 The Go Authors. All rights reserved. + +Redistribution and use in source and binary forms, with or without +modification, are permitted provided that the following conditions are +met: + + * Redistributions of source code must retain the above copyright +notice, this list of conditions and the following disclaimer. + * Redistributions in binary form must reproduce the above +copyright notice, this list of conditions and the following disclaimer +in the documentation and/or other materials provided with the +distribution. + * Neither the name of Google Inc. nor the names of its +contributors may be used to endorse or promote products derived from +this software without specific prior written permission. + +THIS SOFTWARE IS PROVIDED BY THE COPYRIGHT HOLDERS AND CONTRIBUTORS +"AS IS" AND ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT +LIMITED TO, THE IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR +A PARTICULAR PURPOSE ARE DISCLAIMED. IN NO EVENT SHALL THE COPYRIGHT +OWNER OR CONTRIBUTORS BE LIABLE FOR ANY DIRECT, INDIRECT, INCIDENTAL, +SPECIAL, EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING, BUT NOT +LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES; LOSS OF USE, +DATA, OR PROFITS; OR BUSINESS INTERRUPTION) HOWEVER CAUSED AND ON ANY +THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY, OR TORT +(INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT OF THE USE +OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE. diff --git a/vendor/golang.org/x/exp/PATENTS b/vendor/golang.org/x/exp/PATENTS new file mode 100644 index 000000000..733099041 --- /dev/null +++ b/vendor/golang.org/x/exp/PATENTS @@ -0,0 +1,22 @@ +Additional IP Rights Grant (Patents) + +"This implementation" means the copyrightable works distributed by +Google as part of the Go project. + +Google hereby grants to You a perpetual, worldwide, non-exclusive, +no-charge, royalty-free, irrevocable (except as stated in this section) +patent license to make, have made, use, offer to sell, sell, import, +transfer and otherwise run, modify and propagate the contents of this +implementation of Go, where such license applies only to those patent +claims, both currently owned or controlled by Google and acquired in +the future, licensable by Google that are necessarily infringed by this +implementation of Go. This grant does not include claims that would be +infringed only as a consequence of further modification of this +implementation. If you or your agent or exclusive licensee institute or +order or agree to the institution of patent litigation against any +entity (including a cross-claim or counterclaim in a lawsuit) alleging +that this implementation of Go or any code incorporated within this +implementation of Go constitutes direct or contributory patent +infringement, or inducement of patent infringement, then any patent +rights granted to you under this License for this implementation of Go +shall terminate as of the date such litigation is filed. diff --git a/vendor/golang.org/x/exp/constraints/constraints.go b/vendor/golang.org/x/exp/constraints/constraints.go new file mode 100644 index 000000000..2c033dff4 --- /dev/null +++ b/vendor/golang.org/x/exp/constraints/constraints.go @@ -0,0 +1,50 @@ +// Copyright 2021 The Go Authors. All rights reserved. +// Use of this source code is governed by a BSD-style +// license that can be found in the LICENSE file. + +// Package constraints defines a set of useful constraints to be used +// with type parameters. +package constraints + +// Signed is a constraint that permits any signed integer type. +// If future releases of Go add new predeclared signed integer types, +// this constraint will be modified to include them. +type Signed interface { + ~int | ~int8 | ~int16 | ~int32 | ~int64 +} + +// Unsigned is a constraint that permits any unsigned integer type. +// If future releases of Go add new predeclared unsigned integer types, +// this constraint will be modified to include them. +type Unsigned interface { + ~uint | ~uint8 | ~uint16 | ~uint32 | ~uint64 | ~uintptr +} + +// Integer is a constraint that permits any integer type. +// If future releases of Go add new predeclared integer types, +// this constraint will be modified to include them. +type Integer interface { + Signed | Unsigned +} + +// Float is a constraint that permits any floating-point type. +// If future releases of Go add new predeclared floating-point types, +// this constraint will be modified to include them. +type Float interface { + ~float32 | ~float64 +} + +// Complex is a constraint that permits any complex numeric type. +// If future releases of Go add new predeclared complex numeric types, +// this constraint will be modified to include them. +type Complex interface { + ~complex64 | ~complex128 +} + +// Ordered is a constraint that permits any ordered type: any type +// that supports the operators < <= >= >. +// If future releases of Go add new ordered types, +// this constraint will be modified to include them. +type Ordered interface { + Integer | Float | ~string +} diff --git a/vendor/golang.org/x/exp/slices/slices.go b/vendor/golang.org/x/exp/slices/slices.go new file mode 100644 index 000000000..8a237c5d6 --- /dev/null +++ b/vendor/golang.org/x/exp/slices/slices.go @@ -0,0 +1,218 @@ +// Copyright 2021 The Go Authors. All rights reserved. +// Use of this source code is governed by a BSD-style +// license that can be found in the LICENSE file. + +// Package slices defines various functions useful with slices of any type. +// Unless otherwise specified, these functions all apply to the elements +// of a slice at index 0 <= i < len(s). +// +// Note that the less function in IsSortedFunc, SortFunc, SortStableFunc requires a +// strict weak ordering (https://en.wikipedia.org/wiki/Weak_ordering#Strict_weak_orderings), +// or the sorting may fail to sort correctly. A common case is when sorting slices of +// floating-point numbers containing NaN values. +package slices + +import "golang.org/x/exp/constraints" + +// Equal reports whether two slices are equal: the same length and all +// elements equal. If the lengths are different, Equal returns false. +// Otherwise, the elements are compared in increasing index order, and the +// comparison stops at the first unequal pair. +// Floating point NaNs are not considered equal. +func Equal[E comparable](s1, s2 []E) bool { + if len(s1) != len(s2) { + return false + } + for i := range s1 { + if s1[i] != s2[i] { + return false + } + } + return true +} + +// EqualFunc reports whether two slices are equal using a comparison +// function on each pair of elements. If the lengths are different, +// EqualFunc returns false. Otherwise, the elements are compared in +// increasing index order, and the comparison stops at the first index +// for which eq returns false. +func EqualFunc[E1, E2 any](s1 []E1, s2 []E2, eq func(E1, E2) bool) bool { + if len(s1) != len(s2) { + return false + } + for i, v1 := range s1 { + v2 := s2[i] + if !eq(v1, v2) { + return false + } + } + return true +} + +// Compare compares the elements of s1 and s2. +// The elements are compared sequentially, starting at index 0, +// until one element is not equal to the other. +// The result of comparing the first non-matching elements is returned. +// If both slices are equal until one of them ends, the shorter slice is +// considered less than the longer one. +// The result is 0 if s1 == s2, -1 if s1 < s2, and +1 if s1 > s2. +// Comparisons involving floating point NaNs are ignored. +func Compare[E constraints.Ordered](s1, s2 []E) int { + s2len := len(s2) + for i, v1 := range s1 { + if i >= s2len { + return +1 + } + v2 := s2[i] + switch { + case v1 < v2: + return -1 + case v1 > v2: + return +1 + } + } + if len(s1) < s2len { + return -1 + } + return 0 +} + +// CompareFunc is like Compare but uses a comparison function +// on each pair of elements. The elements are compared in increasing +// index order, and the comparisons stop after the first time cmp +// returns non-zero. +// The result is the first non-zero result of cmp; if cmp always +// returns 0 the result is 0 if len(s1) == len(s2), -1 if len(s1) < len(s2), +// and +1 if len(s1) > len(s2). +func CompareFunc[E1, E2 any](s1 []E1, s2 []E2, cmp func(E1, E2) int) int { + s2len := len(s2) + for i, v1 := range s1 { + if i >= s2len { + return +1 + } + v2 := s2[i] + if c := cmp(v1, v2); c != 0 { + return c + } + } + if len(s1) < s2len { + return -1 + } + return 0 +} + +// Index returns the index of the first occurrence of v in s, +// or -1 if not present. +func Index[E comparable](s []E, v E) int { + for i, vs := range s { + if v == vs { + return i + } + } + return -1 +} + +// IndexFunc returns the first index i satisfying f(s[i]), +// or -1 if none do. +func IndexFunc[E any](s []E, f func(E) bool) int { + for i, v := range s { + if f(v) { + return i + } + } + return -1 +} + +// Contains reports whether v is present in s. +func Contains[E comparable](s []E, v E) bool { + return Index(s, v) >= 0 +} + +// Insert inserts the values v... into s at index i, +// returning the modified slice. +// In the returned slice r, r[i] == v[0]. +// Insert panics if i is out of range. +// This function is O(len(s) + len(v)). +func Insert[S ~[]E, E any](s S, i int, v ...E) S { + tot := len(s) + len(v) + if tot <= cap(s) { + s2 := s[:tot] + copy(s2[i+len(v):], s[i:]) + copy(s2[i:], v) + return s2 + } + s2 := make(S, tot) + copy(s2, s[:i]) + copy(s2[i:], v) + copy(s2[i+len(v):], s[i:]) + return s2 +} + +// Delete removes the elements s[i:j] from s, returning the modified slice. +// Delete panics if s[i:j] is not a valid slice of s. +// Delete modifies the contents of the slice s; it does not create a new slice. +// Delete is O(len(s)-(j-i)), so if many items must be deleted, it is better to +// make a single call deleting them all together than to delete one at a time. +func Delete[S ~[]E, E any](s S, i, j int) S { + return append(s[:i], s[j:]...) +} + +// Clone returns a copy of the slice. +// The elements are copied using assignment, so this is a shallow clone. +func Clone[S ~[]E, E any](s S) S { + // Preserve nil in case it matters. + if s == nil { + return nil + } + return append(S([]E{}), s...) +} + +// Compact replaces consecutive runs of equal elements with a single copy. +// This is like the uniq command found on Unix. +// Compact modifies the contents of the slice s; it does not create a new slice. +func Compact[S ~[]E, E comparable](s S) S { + if len(s) == 0 { + return s + } + i := 1 + last := s[0] + for _, v := range s[1:] { + if v != last { + s[i] = v + i++ + last = v + } + } + return s[:i] +} + +// CompactFunc is like Compact but uses a comparison function. +func CompactFunc[S ~[]E, E any](s S, eq func(E, E) bool) S { + if len(s) == 0 { + return s + } + i := 1 + last := s[0] + for _, v := range s[1:] { + if !eq(v, last) { + s[i] = v + i++ + last = v + } + } + return s[:i] +} + +// Grow increases the slice's capacity, if necessary, to guarantee space for +// another n elements. After Grow(n), at least n elements can be appended +// to the slice without another allocation. Grow may modify elements of the +// slice between the length and the capacity. If n is negative or too large to +// allocate the memory, Grow panics. +func Grow[S ~[]E, E any](s S, n int) S { + return append(s, make(S, n)...)[:len(s)] +} + +// Clip removes unused capacity from the slice, returning s[:len(s):len(s)]. +func Clip[S ~[]E, E any](s S) S { + return s[:len(s):len(s)] +} diff --git a/vendor/golang.org/x/exp/slices/sort.go b/vendor/golang.org/x/exp/slices/sort.go new file mode 100644 index 000000000..c22e74bd1 --- /dev/null +++ b/vendor/golang.org/x/exp/slices/sort.go @@ -0,0 +1,127 @@ +// Copyright 2022 The Go Authors. All rights reserved. +// Use of this source code is governed by a BSD-style +// license that can be found in the LICENSE file. + +package slices + +import ( + "math/bits" + + "golang.org/x/exp/constraints" +) + +// Sort sorts a slice of any ordered type in ascending order. +// Sort may fail to sort correctly when sorting slices of floating-point +// numbers containing Not-a-number (NaN) values. +// Use slices.SortFunc(x, func(a, b float64) bool {return a < b || (math.IsNaN(a) && !math.IsNaN(b))}) +// instead if the input may contain NaNs. +func Sort[E constraints.Ordered](x []E) { + n := len(x) + pdqsortOrdered(x, 0, n, bits.Len(uint(n))) +} + +// SortFunc sorts the slice x in ascending order as determined by the less function. +// This sort is not guaranteed to be stable. +// +// SortFunc requires that less is a strict weak ordering. +// See https://en.wikipedia.org/wiki/Weak_ordering#Strict_weak_orderings. +func SortFunc[E any](x []E, less func(a, b E) bool) { + n := len(x) + pdqsortLessFunc(x, 0, n, bits.Len(uint(n)), less) +} + +// SortStable sorts the slice x while keeping the original order of equal +// elements, using less to compare elements. +func SortStableFunc[E any](x []E, less func(a, b E) bool) { + stableLessFunc(x, len(x), less) +} + +// IsSorted reports whether x is sorted in ascending order. +func IsSorted[E constraints.Ordered](x []E) bool { + for i := len(x) - 1; i > 0; i-- { + if x[i] < x[i-1] { + return false + } + } + return true +} + +// IsSortedFunc reports whether x is sorted in ascending order, with less as the +// comparison function. +func IsSortedFunc[E any](x []E, less func(a, b E) bool) bool { + for i := len(x) - 1; i > 0; i-- { + if less(x[i], x[i-1]) { + return false + } + } + return true +} + +// BinarySearch searches for target in a sorted slice and returns the position +// where target is found, or the position where target would appear in the +// sort order; it also returns a bool saying whether the target is really found +// in the slice. The slice must be sorted in increasing order. +func BinarySearch[E constraints.Ordered](x []E, target E) (int, bool) { + // search returns the leftmost position where f returns true, or len(x) if f + // returns false for all x. This is the insertion position for target in x, + // and could point to an element that's either == target or not. + pos := search(len(x), func(i int) bool { return x[i] >= target }) + if pos >= len(x) || x[pos] != target { + return pos, false + } else { + return pos, true + } +} + +// BinarySearchFunc works like BinarySearch, but uses a custom comparison +// function. The slice must be sorted in increasing order, where "increasing" is +// defined by cmp. cmp(a, b) is expected to return an integer comparing the two +// parameters: 0 if a == b, a negative number if a < b and a positive number if +// a > b. +func BinarySearchFunc[E any](x []E, target E, cmp func(E, E) int) (int, bool) { + pos := search(len(x), func(i int) bool { return cmp(x[i], target) >= 0 }) + if pos >= len(x) || cmp(x[pos], target) != 0 { + return pos, false + } else { + return pos, true + } +} + +func search(n int, f func(int) bool) int { + // Define f(-1) == false and f(n) == true. + // Invariant: f(i-1) == false, f(j) == true. + i, j := 0, n + for i < j { + h := int(uint(i+j) >> 1) // avoid overflow when computing h + // i ≤ h < j + if !f(h) { + i = h + 1 // preserves f(i-1) == false + } else { + j = h // preserves f(j) == true + } + } + // i == j, f(i-1) == false, and f(j) (= f(i)) == true => answer is i. + return i +} + +type sortedHint int // hint for pdqsort when choosing the pivot + +const ( + unknownHint sortedHint = iota + increasingHint + decreasingHint +) + +// xorshift paper: https://www.jstatsoft.org/article/view/v008i14/xorshift.pdf +type xorshift uint64 + +func (r *xorshift) Next() uint64 { + *r ^= *r << 13 + *r ^= *r >> 17 + *r ^= *r << 5 + return uint64(*r) +} + +func nextPowerOfTwo(length int) uint { + return 1 << bits.Len(uint(length)) +} diff --git a/vendor/golang.org/x/exp/slices/zsortfunc.go b/vendor/golang.org/x/exp/slices/zsortfunc.go new file mode 100644 index 000000000..2a632476c --- /dev/null +++ b/vendor/golang.org/x/exp/slices/zsortfunc.go @@ -0,0 +1,479 @@ +// Code generated by gen_sort_variants.go; DO NOT EDIT. + +// Copyright 2022 The Go Authors. All rights reserved. +// Use of this source code is governed by a BSD-style +// license that can be found in the LICENSE file. + +package slices + +// insertionSortLessFunc sorts data[a:b] using insertion sort. +func insertionSortLessFunc[E any](data []E, a, b int, less func(a, b E) bool) { + for i := a + 1; i < b; i++ { + for j := i; j > a && less(data[j], data[j-1]); j-- { + data[j], data[j-1] = data[j-1], data[j] + } + } +} + +// siftDownLessFunc implements the heap property on data[lo:hi]. +// first is an offset into the array where the root of the heap lies. +func siftDownLessFunc[E any](data []E, lo, hi, first int, less func(a, b E) bool) { + root := lo + for { + child := 2*root + 1 + if child >= hi { + break + } + if child+1 < hi && less(data[first+child], data[first+child+1]) { + child++ + } + if !less(data[first+root], data[first+child]) { + return + } + data[first+root], data[first+child] = data[first+child], data[first+root] + root = child + } +} + +func heapSortLessFunc[E any](data []E, a, b int, less func(a, b E) bool) { + first := a + lo := 0 + hi := b - a + + // Build heap with greatest element at top. + for i := (hi - 1) / 2; i >= 0; i-- { + siftDownLessFunc(data, i, hi, first, less) + } + + // Pop elements, largest first, into end of data. + for i := hi - 1; i >= 0; i-- { + data[first], data[first+i] = data[first+i], data[first] + siftDownLessFunc(data, lo, i, first, less) + } +} + +// pdqsortLessFunc sorts data[a:b]. +// The algorithm based on pattern-defeating quicksort(pdqsort), but without the optimizations from BlockQuicksort. +// pdqsort paper: https://arxiv.org/pdf/2106.05123.pdf +// C++ implementation: https://github.com/orlp/pdqsort +// Rust implementation: https://docs.rs/pdqsort/latest/pdqsort/ +// limit is the number of allowed bad (very unbalanced) pivots before falling back to heapsort. +func pdqsortLessFunc[E any](data []E, a, b, limit int, less func(a, b E) bool) { + const maxInsertion = 12 + + var ( + wasBalanced = true // whether the last partitioning was reasonably balanced + wasPartitioned = true // whether the slice was already partitioned + ) + + for { + length := b - a + + if length <= maxInsertion { + insertionSortLessFunc(data, a, b, less) + return + } + + // Fall back to heapsort if too many bad choices were made. + if limit == 0 { + heapSortLessFunc(data, a, b, less) + return + } + + // If the last partitioning was imbalanced, we need to breaking patterns. + if !wasBalanced { + breakPatternsLessFunc(data, a, b, less) + limit-- + } + + pivot, hint := choosePivotLessFunc(data, a, b, less) + if hint == decreasingHint { + reverseRangeLessFunc(data, a, b, less) + // The chosen pivot was pivot-a elements after the start of the array. + // After reversing it is pivot-a elements before the end of the array. + // The idea came from Rust's implementation. + pivot = (b - 1) - (pivot - a) + hint = increasingHint + } + + // The slice is likely already sorted. + if wasBalanced && wasPartitioned && hint == increasingHint { + if partialInsertionSortLessFunc(data, a, b, less) { + return + } + } + + // Probably the slice contains many duplicate elements, partition the slice into + // elements equal to and elements greater than the pivot. + if a > 0 && !less(data[a-1], data[pivot]) { + mid := partitionEqualLessFunc(data, a, b, pivot, less) + a = mid + continue + } + + mid, alreadyPartitioned := partitionLessFunc(data, a, b, pivot, less) + wasPartitioned = alreadyPartitioned + + leftLen, rightLen := mid-a, b-mid + balanceThreshold := length / 8 + if leftLen < rightLen { + wasBalanced = leftLen >= balanceThreshold + pdqsortLessFunc(data, a, mid, limit, less) + a = mid + 1 + } else { + wasBalanced = rightLen >= balanceThreshold + pdqsortLessFunc(data, mid+1, b, limit, less) + b = mid + } + } +} + +// partitionLessFunc does one quicksort partition. +// Let p = data[pivot] +// Moves elements in data[a:b] around, so that data[i]<p and data[j]>=p for i<newpivot and j>newpivot. +// On return, data[newpivot] = p +func partitionLessFunc[E any](data []E, a, b, pivot int, less func(a, b E) bool) (newpivot int, alreadyPartitioned bool) { + data[a], data[pivot] = data[pivot], data[a] + i, j := a+1, b-1 // i and j are inclusive of the elements remaining to be partitioned + + for i <= j && less(data[i], data[a]) { + i++ + } + for i <= j && !less(data[j], data[a]) { + j-- + } + if i > j { + data[j], data[a] = data[a], data[j] + return j, true + } + data[i], data[j] = data[j], data[i] + i++ + j-- + + for { + for i <= j && less(data[i], data[a]) { + i++ + } + for i <= j && !less(data[j], data[a]) { + j-- + } + if i > j { + break + } + data[i], data[j] = data[j], data[i] + i++ + j-- + } + data[j], data[a] = data[a], data[j] + return j, false +} + +// partitionEqualLessFunc partitions data[a:b] into elements equal to data[pivot] followed by elements greater than data[pivot]. +// It assumed that data[a:b] does not contain elements smaller than the data[pivot]. +func partitionEqualLessFunc[E any](data []E, a, b, pivot int, less func(a, b E) bool) (newpivot int) { + data[a], data[pivot] = data[pivot], data[a] + i, j := a+1, b-1 // i and j are inclusive of the elements remaining to be partitioned + + for { + for i <= j && !less(data[a], data[i]) { + i++ + } + for i <= j && less(data[a], data[j]) { + j-- + } + if i > j { + break + } + data[i], data[j] = data[j], data[i] + i++ + j-- + } + return i +} + +// partialInsertionSortLessFunc partially sorts a slice, returns true if the slice is sorted at the end. +func partialInsertionSortLessFunc[E any](data []E, a, b int, less func(a, b E) bool) bool { + const ( + maxSteps = 5 // maximum number of adjacent out-of-order pairs that will get shifted + shortestShifting = 50 // don't shift any elements on short arrays + ) + i := a + 1 + for j := 0; j < maxSteps; j++ { + for i < b && !less(data[i], data[i-1]) { + i++ + } + + if i == b { + return true + } + + if b-a < shortestShifting { + return false + } + + data[i], data[i-1] = data[i-1], data[i] + + // Shift the smaller one to the left. + if i-a >= 2 { + for j := i - 1; j >= 1; j-- { + if !less(data[j], data[j-1]) { + break + } + data[j], data[j-1] = data[j-1], data[j] + } + } + // Shift the greater one to the right. + if b-i >= 2 { + for j := i + 1; j < b; j++ { + if !less(data[j], data[j-1]) { + break + } + data[j], data[j-1] = data[j-1], data[j] + } + } + } + return false +} + +// breakPatternsLessFunc scatters some elements around in an attempt to break some patterns +// that might cause imbalanced partitions in quicksort. +func breakPatternsLessFunc[E any](data []E, a, b int, less func(a, b E) bool) { + length := b - a + if length >= 8 { + random := xorshift(length) + modulus := nextPowerOfTwo(length) + + for idx := a + (length/4)*2 - 1; idx <= a+(length/4)*2+1; idx++ { + other := int(uint(random.Next()) & (modulus - 1)) + if other >= length { + other -= length + } + data[idx], data[a+other] = data[a+other], data[idx] + } + } +} + +// choosePivotLessFunc chooses a pivot in data[a:b]. +// +// [0,8): chooses a static pivot. +// [8,shortestNinther): uses the simple median-of-three method. +// [shortestNinther,∞): uses the Tukey ninther method. +func choosePivotLessFunc[E any](data []E, a, b int, less func(a, b E) bool) (pivot int, hint sortedHint) { + const ( + shortestNinther = 50 + maxSwaps = 4 * 3 + ) + + l := b - a + + var ( + swaps int + i = a + l/4*1 + j = a + l/4*2 + k = a + l/4*3 + ) + + if l >= 8 { + if l >= shortestNinther { + // Tukey ninther method, the idea came from Rust's implementation. + i = medianAdjacentLessFunc(data, i, &swaps, less) + j = medianAdjacentLessFunc(data, j, &swaps, less) + k = medianAdjacentLessFunc(data, k, &swaps, less) + } + // Find the median among i, j, k and stores it into j. + j = medianLessFunc(data, i, j, k, &swaps, less) + } + + switch swaps { + case 0: + return j, increasingHint + case maxSwaps: + return j, decreasingHint + default: + return j, unknownHint + } +} + +// order2LessFunc returns x,y where data[x] <= data[y], where x,y=a,b or x,y=b,a. +func order2LessFunc[E any](data []E, a, b int, swaps *int, less func(a, b E) bool) (int, int) { + if less(data[b], data[a]) { + *swaps++ + return b, a + } + return a, b +} + +// medianLessFunc returns x where data[x] is the median of data[a],data[b],data[c], where x is a, b, or c. +func medianLessFunc[E any](data []E, a, b, c int, swaps *int, less func(a, b E) bool) int { + a, b = order2LessFunc(data, a, b, swaps, less) + b, c = order2LessFunc(data, b, c, swaps, less) + a, b = order2LessFunc(data, a, b, swaps, less) + return b +} + +// medianAdjacentLessFunc finds the median of data[a - 1], data[a], data[a + 1] and stores the index into a. +func medianAdjacentLessFunc[E any](data []E, a int, swaps *int, less func(a, b E) bool) int { + return medianLessFunc(data, a-1, a, a+1, swaps, less) +} + +func reverseRangeLessFunc[E any](data []E, a, b int, less func(a, b E) bool) { + i := a + j := b - 1 + for i < j { + data[i], data[j] = data[j], data[i] + i++ + j-- + } +} + +func swapRangeLessFunc[E any](data []E, a, b, n int, less func(a, b E) bool) { + for i := 0; i < n; i++ { + data[a+i], data[b+i] = data[b+i], data[a+i] + } +} + +func stableLessFunc[E any](data []E, n int, less func(a, b E) bool) { + blockSize := 20 // must be > 0 + a, b := 0, blockSize + for b <= n { + insertionSortLessFunc(data, a, b, less) + a = b + b += blockSize + } + insertionSortLessFunc(data, a, n, less) + + for blockSize < n { + a, b = 0, 2*blockSize + for b <= n { + symMergeLessFunc(data, a, a+blockSize, b, less) + a = b + b += 2 * blockSize + } + if m := a + blockSize; m < n { + symMergeLessFunc(data, a, m, n, less) + } + blockSize *= 2 + } +} + +// symMergeLessFunc merges the two sorted subsequences data[a:m] and data[m:b] using +// the SymMerge algorithm from Pok-Son Kim and Arne Kutzner, "Stable Minimum +// Storage Merging by Symmetric Comparisons", in Susanne Albers and Tomasz +// Radzik, editors, Algorithms - ESA 2004, volume 3221 of Lecture Notes in +// Computer Science, pages 714-723. Springer, 2004. +// +// Let M = m-a and N = b-n. Wolog M < N. +// The recursion depth is bound by ceil(log(N+M)). +// The algorithm needs O(M*log(N/M + 1)) calls to data.Less. +// The algorithm needs O((M+N)*log(M)) calls to data.Swap. +// +// The paper gives O((M+N)*log(M)) as the number of assignments assuming a +// rotation algorithm which uses O(M+N+gcd(M+N)) assignments. The argumentation +// in the paper carries through for Swap operations, especially as the block +// swapping rotate uses only O(M+N) Swaps. +// +// symMerge assumes non-degenerate arguments: a < m && m < b. +// Having the caller check this condition eliminates many leaf recursion calls, +// which improves performance. +func symMergeLessFunc[E any](data []E, a, m, b int, less func(a, b E) bool) { + // Avoid unnecessary recursions of symMerge + // by direct insertion of data[a] into data[m:b] + // if data[a:m] only contains one element. + if m-a == 1 { + // Use binary search to find the lowest index i + // such that data[i] >= data[a] for m <= i < b. + // Exit the search loop with i == b in case no such index exists. + i := m + j := b + for i < j { + h := int(uint(i+j) >> 1) + if less(data[h], data[a]) { + i = h + 1 + } else { + j = h + } + } + // Swap values until data[a] reaches the position before i. + for k := a; k < i-1; k++ { + data[k], data[k+1] = data[k+1], data[k] + } + return + } + + // Avoid unnecessary recursions of symMerge + // by direct insertion of data[m] into data[a:m] + // if data[m:b] only contains one element. + if b-m == 1 { + // Use binary search to find the lowest index i + // such that data[i] > data[m] for a <= i < m. + // Exit the search loop with i == m in case no such index exists. + i := a + j := m + for i < j { + h := int(uint(i+j) >> 1) + if !less(data[m], data[h]) { + i = h + 1 + } else { + j = h + } + } + // Swap values until data[m] reaches the position i. + for k := m; k > i; k-- { + data[k], data[k-1] = data[k-1], data[k] + } + return + } + + mid := int(uint(a+b) >> 1) + n := mid + m + var start, r int + if m > mid { + start = n - b + r = mid + } else { + start = a + r = m + } + p := n - 1 + + for start < r { + c := int(uint(start+r) >> 1) + if !less(data[p-c], data[c]) { + start = c + 1 + } else { + r = c + } + } + + end := n - start + if start < m && m < end { + rotateLessFunc(data, start, m, end, less) + } + if a < start && start < mid { + symMergeLessFunc(data, a, start, mid, less) + } + if mid < end && end < b { + symMergeLessFunc(data, mid, end, b, less) + } +} + +// rotateLessFunc rotates two consecutive blocks u = data[a:m] and v = data[m:b] in data: +// Data of the form 'x u v y' is changed to 'x v u y'. +// rotate performs at most b-a many calls to data.Swap, +// and it assumes non-degenerate arguments: a < m && m < b. +func rotateLessFunc[E any](data []E, a, m, b int, less func(a, b E) bool) { + i := m - a + j := b - m + + for i != j { + if i > j { + swapRangeLessFunc(data, m-i, m, j, less) + i -= j + } else { + swapRangeLessFunc(data, m-i, m+j-i, i, less) + j -= i + } + } + // i == j + swapRangeLessFunc(data, m-i, m, i, less) +} diff --git a/vendor/golang.org/x/exp/slices/zsortordered.go b/vendor/golang.org/x/exp/slices/zsortordered.go new file mode 100644 index 000000000..efaa1c8b7 --- /dev/null +++ b/vendor/golang.org/x/exp/slices/zsortordered.go @@ -0,0 +1,481 @@ +// Code generated by gen_sort_variants.go; DO NOT EDIT. + +// Copyright 2022 The Go Authors. All rights reserved. +// Use of this source code is governed by a BSD-style +// license that can be found in the LICENSE file. + +package slices + +import "golang.org/x/exp/constraints" + +// insertionSortOrdered sorts data[a:b] using insertion sort. +func insertionSortOrdered[E constraints.Ordered](data []E, a, b int) { + for i := a + 1; i < b; i++ { + for j := i; j > a && (data[j] < data[j-1]); j-- { + data[j], data[j-1] = data[j-1], data[j] + } + } +} + +// siftDownOrdered implements the heap property on data[lo:hi]. +// first is an offset into the array where the root of the heap lies. +func siftDownOrdered[E constraints.Ordered](data []E, lo, hi, first int) { + root := lo + for { + child := 2*root + 1 + if child >= hi { + break + } + if child+1 < hi && (data[first+child] < data[first+child+1]) { + child++ + } + if !(data[first+root] < data[first+child]) { + return + } + data[first+root], data[first+child] = data[first+child], data[first+root] + root = child + } +} + +func heapSortOrdered[E constraints.Ordered](data []E, a, b int) { + first := a + lo := 0 + hi := b - a + + // Build heap with greatest element at top. + for i := (hi - 1) / 2; i >= 0; i-- { + siftDownOrdered(data, i, hi, first) + } + + // Pop elements, largest first, into end of data. + for i := hi - 1; i >= 0; i-- { + data[first], data[first+i] = data[first+i], data[first] + siftDownOrdered(data, lo, i, first) + } +} + +// pdqsortOrdered sorts data[a:b]. +// The algorithm based on pattern-defeating quicksort(pdqsort), but without the optimizations from BlockQuicksort. +// pdqsort paper: https://arxiv.org/pdf/2106.05123.pdf +// C++ implementation: https://github.com/orlp/pdqsort +// Rust implementation: https://docs.rs/pdqsort/latest/pdqsort/ +// limit is the number of allowed bad (very unbalanced) pivots before falling back to heapsort. +func pdqsortOrdered[E constraints.Ordered](data []E, a, b, limit int) { + const maxInsertion = 12 + + var ( + wasBalanced = true // whether the last partitioning was reasonably balanced + wasPartitioned = true // whether the slice was already partitioned + ) + + for { + length := b - a + + if length <= maxInsertion { + insertionSortOrdered(data, a, b) + return + } + + // Fall back to heapsort if too many bad choices were made. + if limit == 0 { + heapSortOrdered(data, a, b) + return + } + + // If the last partitioning was imbalanced, we need to breaking patterns. + if !wasBalanced { + breakPatternsOrdered(data, a, b) + limit-- + } + + pivot, hint := choosePivotOrdered(data, a, b) + if hint == decreasingHint { + reverseRangeOrdered(data, a, b) + // The chosen pivot was pivot-a elements after the start of the array. + // After reversing it is pivot-a elements before the end of the array. + // The idea came from Rust's implementation. + pivot = (b - 1) - (pivot - a) + hint = increasingHint + } + + // The slice is likely already sorted. + if wasBalanced && wasPartitioned && hint == increasingHint { + if partialInsertionSortOrdered(data, a, b) { + return + } + } + + // Probably the slice contains many duplicate elements, partition the slice into + // elements equal to and elements greater than the pivot. + if a > 0 && !(data[a-1] < data[pivot]) { + mid := partitionEqualOrdered(data, a, b, pivot) + a = mid + continue + } + + mid, alreadyPartitioned := partitionOrdered(data, a, b, pivot) + wasPartitioned = alreadyPartitioned + + leftLen, rightLen := mid-a, b-mid + balanceThreshold := length / 8 + if leftLen < rightLen { + wasBalanced = leftLen >= balanceThreshold + pdqsortOrdered(data, a, mid, limit) + a = mid + 1 + } else { + wasBalanced = rightLen >= balanceThreshold + pdqsortOrdered(data, mid+1, b, limit) + b = mid + } + } +} + +// partitionOrdered does one quicksort partition. +// Let p = data[pivot] +// Moves elements in data[a:b] around, so that data[i]<p and data[j]>=p for i<newpivot and j>newpivot. +// On return, data[newpivot] = p +func partitionOrdered[E constraints.Ordered](data []E, a, b, pivot int) (newpivot int, alreadyPartitioned bool) { + data[a], data[pivot] = data[pivot], data[a] + i, j := a+1, b-1 // i and j are inclusive of the elements remaining to be partitioned + + for i <= j && (data[i] < data[a]) { + i++ + } + for i <= j && !(data[j] < data[a]) { + j-- + } + if i > j { + data[j], data[a] = data[a], data[j] + return j, true + } + data[i], data[j] = data[j], data[i] + i++ + j-- + + for { + for i <= j && (data[i] < data[a]) { + i++ + } + for i <= j && !(data[j] < data[a]) { + j-- + } + if i > j { + break + } + data[i], data[j] = data[j], data[i] + i++ + j-- + } + data[j], data[a] = data[a], data[j] + return j, false +} + +// partitionEqualOrdered partitions data[a:b] into elements equal to data[pivot] followed by elements greater than data[pivot]. +// It assumed that data[a:b] does not contain elements smaller than the data[pivot]. +func partitionEqualOrdered[E constraints.Ordered](data []E, a, b, pivot int) (newpivot int) { + data[a], data[pivot] = data[pivot], data[a] + i, j := a+1, b-1 // i and j are inclusive of the elements remaining to be partitioned + + for { + for i <= j && !(data[a] < data[i]) { + i++ + } + for i <= j && (data[a] < data[j]) { + j-- + } + if i > j { + break + } + data[i], data[j] = data[j], data[i] + i++ + j-- + } + return i +} + +// partialInsertionSortOrdered partially sorts a slice, returns true if the slice is sorted at the end. +func partialInsertionSortOrdered[E constraints.Ordered](data []E, a, b int) bool { + const ( + maxSteps = 5 // maximum number of adjacent out-of-order pairs that will get shifted + shortestShifting = 50 // don't shift any elements on short arrays + ) + i := a + 1 + for j := 0; j < maxSteps; j++ { + for i < b && !(data[i] < data[i-1]) { + i++ + } + + if i == b { + return true + } + + if b-a < shortestShifting { + return false + } + + data[i], data[i-1] = data[i-1], data[i] + + // Shift the smaller one to the left. + if i-a >= 2 { + for j := i - 1; j >= 1; j-- { + if !(data[j] < data[j-1]) { + break + } + data[j], data[j-1] = data[j-1], data[j] + } + } + // Shift the greater one to the right. + if b-i >= 2 { + for j := i + 1; j < b; j++ { + if !(data[j] < data[j-1]) { + break + } + data[j], data[j-1] = data[j-1], data[j] + } + } + } + return false +} + +// breakPatternsOrdered scatters some elements around in an attempt to break some patterns +// that might cause imbalanced partitions in quicksort. +func breakPatternsOrdered[E constraints.Ordered](data []E, a, b int) { + length := b - a + if length >= 8 { + random := xorshift(length) + modulus := nextPowerOfTwo(length) + + for idx := a + (length/4)*2 - 1; idx <= a+(length/4)*2+1; idx++ { + other := int(uint(random.Next()) & (modulus - 1)) + if other >= length { + other -= length + } + data[idx], data[a+other] = data[a+other], data[idx] + } + } +} + +// choosePivotOrdered chooses a pivot in data[a:b]. +// +// [0,8): chooses a static pivot. +// [8,shortestNinther): uses the simple median-of-three method. +// [shortestNinther,∞): uses the Tukey ninther method. +func choosePivotOrdered[E constraints.Ordered](data []E, a, b int) (pivot int, hint sortedHint) { + const ( + shortestNinther = 50 + maxSwaps = 4 * 3 + ) + + l := b - a + + var ( + swaps int + i = a + l/4*1 + j = a + l/4*2 + k = a + l/4*3 + ) + + if l >= 8 { + if l >= shortestNinther { + // Tukey ninther method, the idea came from Rust's implementation. + i = medianAdjacentOrdered(data, i, &swaps) + j = medianAdjacentOrdered(data, j, &swaps) + k = medianAdjacentOrdered(data, k, &swaps) + } + // Find the median among i, j, k and stores it into j. + j = medianOrdered(data, i, j, k, &swaps) + } + + switch swaps { + case 0: + return j, increasingHint + case maxSwaps: + return j, decreasingHint + default: + return j, unknownHint + } +} + +// order2Ordered returns x,y where data[x] <= data[y], where x,y=a,b or x,y=b,a. +func order2Ordered[E constraints.Ordered](data []E, a, b int, swaps *int) (int, int) { + if data[b] < data[a] { + *swaps++ + return b, a + } + return a, b +} + +// medianOrdered returns x where data[x] is the median of data[a],data[b],data[c], where x is a, b, or c. +func medianOrdered[E constraints.Ordered](data []E, a, b, c int, swaps *int) int { + a, b = order2Ordered(data, a, b, swaps) + b, c = order2Ordered(data, b, c, swaps) + a, b = order2Ordered(data, a, b, swaps) + return b +} + +// medianAdjacentOrdered finds the median of data[a - 1], data[a], data[a + 1] and stores the index into a. +func medianAdjacentOrdered[E constraints.Ordered](data []E, a int, swaps *int) int { + return medianOrdered(data, a-1, a, a+1, swaps) +} + +func reverseRangeOrdered[E constraints.Ordered](data []E, a, b int) { + i := a + j := b - 1 + for i < j { + data[i], data[j] = data[j], data[i] + i++ + j-- + } +} + +func swapRangeOrdered[E constraints.Ordered](data []E, a, b, n int) { + for i := 0; i < n; i++ { + data[a+i], data[b+i] = data[b+i], data[a+i] + } +} + +func stableOrdered[E constraints.Ordered](data []E, n int) { + blockSize := 20 // must be > 0 + a, b := 0, blockSize + for b <= n { + insertionSortOrdered(data, a, b) + a = b + b += blockSize + } + insertionSortOrdered(data, a, n) + + for blockSize < n { + a, b = 0, 2*blockSize + for b <= n { + symMergeOrdered(data, a, a+blockSize, b) + a = b + b += 2 * blockSize + } + if m := a + blockSize; m < n { + symMergeOrdered(data, a, m, n) + } + blockSize *= 2 + } +} + +// symMergeOrdered merges the two sorted subsequences data[a:m] and data[m:b] using +// the SymMerge algorithm from Pok-Son Kim and Arne Kutzner, "Stable Minimum +// Storage Merging by Symmetric Comparisons", in Susanne Albers and Tomasz +// Radzik, editors, Algorithms - ESA 2004, volume 3221 of Lecture Notes in +// Computer Science, pages 714-723. Springer, 2004. +// +// Let M = m-a and N = b-n. Wolog M < N. +// The recursion depth is bound by ceil(log(N+M)). +// The algorithm needs O(M*log(N/M + 1)) calls to data.Less. +// The algorithm needs O((M+N)*log(M)) calls to data.Swap. +// +// The paper gives O((M+N)*log(M)) as the number of assignments assuming a +// rotation algorithm which uses O(M+N+gcd(M+N)) assignments. The argumentation +// in the paper carries through for Swap operations, especially as the block +// swapping rotate uses only O(M+N) Swaps. +// +// symMerge assumes non-degenerate arguments: a < m && m < b. +// Having the caller check this condition eliminates many leaf recursion calls, +// which improves performance. +func symMergeOrdered[E constraints.Ordered](data []E, a, m, b int) { + // Avoid unnecessary recursions of symMerge + // by direct insertion of data[a] into data[m:b] + // if data[a:m] only contains one element. + if m-a == 1 { + // Use binary search to find the lowest index i + // such that data[i] >= data[a] for m <= i < b. + // Exit the search loop with i == b in case no such index exists. + i := m + j := b + for i < j { + h := int(uint(i+j) >> 1) + if data[h] < data[a] { + i = h + 1 + } else { + j = h + } + } + // Swap values until data[a] reaches the position before i. + for k := a; k < i-1; k++ { + data[k], data[k+1] = data[k+1], data[k] + } + return + } + + // Avoid unnecessary recursions of symMerge + // by direct insertion of data[m] into data[a:m] + // if data[m:b] only contains one element. + if b-m == 1 { + // Use binary search to find the lowest index i + // such that data[i] > data[m] for a <= i < m. + // Exit the search loop with i == m in case no such index exists. + i := a + j := m + for i < j { + h := int(uint(i+j) >> 1) + if !(data[m] < data[h]) { + i = h + 1 + } else { + j = h + } + } + // Swap values until data[m] reaches the position i. + for k := m; k > i; k-- { + data[k], data[k-1] = data[k-1], data[k] + } + return + } + + mid := int(uint(a+b) >> 1) + n := mid + m + var start, r int + if m > mid { + start = n - b + r = mid + } else { + start = a + r = m + } + p := n - 1 + + for start < r { + c := int(uint(start+r) >> 1) + if !(data[p-c] < data[c]) { + start = c + 1 + } else { + r = c + } + } + + end := n - start + if start < m && m < end { + rotateOrdered(data, start, m, end) + } + if a < start && start < mid { + symMergeOrdered(data, a, start, mid) + } + if mid < end && end < b { + symMergeOrdered(data, mid, end, b) + } +} + +// rotateOrdered rotates two consecutive blocks u = data[a:m] and v = data[m:b] in data: +// Data of the form 'x u v y' is changed to 'x v u y'. +// rotate performs at most b-a many calls to data.Swap, +// and it assumes non-degenerate arguments: a < m && m < b. +func rotateOrdered[E constraints.Ordered](data []E, a, m, b int) { + i := m - a + j := b - m + + for i != j { + if i > j { + swapRangeOrdered(data, m-i, m, j) + i -= j + } else { + swapRangeOrdered(data, m-i, m+j-i, i) + j -= i + } + } + // i == j + swapRangeOrdered(data, m-i, m, i) +} diff --git a/vendor/modules.txt b/vendor/modules.txt index 59438b970..99a3b0d8a 100644 --- a/vendor/modules.txt +++ b/vendor/modules.txt @@ -1,19 +1,22 @@ -# codeberg.org/gruf/go-bitutil v1.0.0 +# codeberg.org/gruf/go-atomics v1.1.0 +## explicit; go 1.16 +codeberg.org/gruf/go-atomics +# codeberg.org/gruf/go-bitutil v1.0.1 ## explicit; go 1.16 codeberg.org/gruf/go-bitutil # codeberg.org/gruf/go-bytes v1.0.2 ## explicit; go 1.14 codeberg.org/gruf/go-bytes -# codeberg.org/gruf/go-byteutil v1.0.1 +# codeberg.org/gruf/go-byteutil v1.0.2 ## explicit; go 1.16 codeberg.org/gruf/go-byteutil -# codeberg.org/gruf/go-cache/v2 v2.0.1 +# codeberg.org/gruf/go-cache/v2 v2.1.1 ## explicit; go 1.18 codeberg.org/gruf/go-cache/v2 -# codeberg.org/gruf/go-debug v1.1.2 +# codeberg.org/gruf/go-debug v1.2.0 ## explicit; go 1.16 codeberg.org/gruf/go-debug -# codeberg.org/gruf/go-errors/v2 v2.0.1 +# codeberg.org/gruf/go-errors/v2 v2.0.2 ## explicit; go 1.16 codeberg.org/gruf/go-errors/v2 # codeberg.org/gruf/go-fastcopy v1.1.1 @@ -34,14 +37,14 @@ codeberg.org/gruf/go-pools # codeberg.org/gruf/go-runners v1.2.1 ## explicit; go 1.14 codeberg.org/gruf/go-runners -# codeberg.org/gruf/go-store v1.3.7 +# codeberg.org/gruf/go-sched v1.0.1 +## explicit; go 1.18 +codeberg.org/gruf/go-sched +# codeberg.org/gruf/go-store v1.3.8 ## explicit; go 1.14 codeberg.org/gruf/go-store/kv codeberg.org/gruf/go-store/storage codeberg.org/gruf/go-store/util -# github.com/ReneKroon/ttlcache v1.7.0 -## explicit; go 1.14 -github.com/ReneKroon/ttlcache # github.com/aymerick/douceur v0.2.0 ## explicit github.com/aymerick/douceur/css @@ -601,6 +604,10 @@ golang.org/x/crypto/ripemd160 golang.org/x/crypto/sha3 golang.org/x/crypto/ssh golang.org/x/crypto/ssh/internal/bcrypt_pbkdf +# golang.org/x/exp v0.0.0-20220613132600-b0d781184e0d +## explicit; go 1.18 +golang.org/x/exp/constraints +golang.org/x/exp/slices # golang.org/x/mod v0.6.0-dev.0.20220419223038-86c51ed26bb4 ## explicit; go 1.17 golang.org/x/mod/semver |