summaryrefslogtreecommitdiff
diff options
context:
space:
mode:
authorLibravatar kim <89579420+NyaaaWhatsUpDoc@users.noreply.github.com>2024-06-21 16:35:32 +0000
committerLibravatar GitHub <noreply@github.com>2024-06-21 17:35:32 +0100
commit9143ac6fb4f68f1c79e42f7adc10e68bf7f36e87 (patch)
tree73514f164dd48cfc3f902e6b3f3d2a6db8c6175c
parent[chore] update go-structr and go-mangler to no longer rely on modern-go/refle... (diff)
downloadgotosocial-9143ac6fb4f68f1c79e42f7adc10e68bf7f36e87.tar.xz
updates go-mutexes to no longer rely on unsafe linkname (#3027)
-rw-r--r--go.mod4
-rw-r--r--go.sum8
-rw-r--r--vendor/codeberg.org/gruf/go-mutexes/cond.go86
-rw-r--r--vendor/codeberg.org/gruf/go-mutexes/hash_map.go56
-rw-r--r--vendor/codeberg.org/gruf/go-mutexes/map.go92
-rw-r--r--vendor/github.com/dolthub/maphash/.gitignore2
-rw-r--r--vendor/github.com/dolthub/maphash/LICENSE201
-rw-r--r--vendor/github.com/dolthub/maphash/README.md4
-rw-r--r--vendor/github.com/dolthub/maphash/hasher.go48
-rw-r--r--vendor/github.com/dolthub/maphash/runtime.go111
-rw-r--r--vendor/github.com/dolthub/swiss/.gitignore5
-rw-r--r--vendor/github.com/dolthub/swiss/LICENSE201
-rw-r--r--vendor/github.com/dolthub/swiss/README.md54
-rw-r--r--vendor/github.com/dolthub/swiss/bits.go58
-rw-r--r--vendor/github.com/dolthub/swiss/bits_amd64.go50
-rw-r--r--vendor/github.com/dolthub/swiss/map.go359
-rw-r--r--vendor/github.com/dolthub/swiss/simd/match.s19
-rw-r--r--vendor/github.com/dolthub/swiss/simd/match_amd64.go9
-rw-r--r--vendor/modules.txt9
19 files changed, 134 insertions, 1242 deletions
diff --git a/go.mod b/go.mod
index ac2cc9f8b..558a0b90b 100644
--- a/go.mod
+++ b/go.mod
@@ -17,7 +17,7 @@ require (
codeberg.org/gruf/go-list v0.0.0-20240425093752-494db03d641f
codeberg.org/gruf/go-logger/v2 v2.2.1
codeberg.org/gruf/go-mempool v0.0.0-20240507125005-cef10d64a760
- codeberg.org/gruf/go-mutexes v1.5.0
+ codeberg.org/gruf/go-mutexes v1.5.1
codeberg.org/gruf/go-runners v1.6.2
codeberg.org/gruf/go-sched v1.2.3
codeberg.org/gruf/go-storage v0.1.1
@@ -107,8 +107,6 @@ require (
github.com/coreos/go-systemd/v22 v22.3.2 // indirect
github.com/davecgh/go-spew v1.1.2-0.20180830191138-d8f796af33cc // indirect
github.com/docker/go-units v0.5.0 // indirect
- github.com/dolthub/maphash v0.1.0 // indirect
- github.com/dolthub/swiss v0.2.1 // indirect
github.com/dsoprea/go-exif/v3 v3.0.0-20210625224831-a6301f85c82b // indirect
github.com/dsoprea/go-iptc v0.0.0-20200610044640-bc9ca208b413 // indirect
github.com/dsoprea/go-logging v0.0.0-20200710184922-b02d349568dd // indirect
diff --git a/go.sum b/go.sum
index 0870c5dc6..77ecb3099 100644
--- a/go.sum
+++ b/go.sum
@@ -68,8 +68,8 @@ codeberg.org/gruf/go-maps v1.0.3 h1:VDwhnnaVNUIy5O93CvkcE2IZXnMB1+IJjzfop9V12es=
codeberg.org/gruf/go-maps v1.0.3/go.mod h1:D5LNDxlC9rsDuVQVM6JObaVGAdHB6g2dTdOdkh1aXWA=
codeberg.org/gruf/go-mempool v0.0.0-20240507125005-cef10d64a760 h1:m2/UCRXhjDwAg4vyji6iKCpomKw6P4PmBOUi5DvAMH4=
codeberg.org/gruf/go-mempool v0.0.0-20240507125005-cef10d64a760/go.mod h1:E3RcaCFNq4zXpvaJb8lfpPqdUAmSkP5F1VmMiEUYTEk=
-codeberg.org/gruf/go-mutexes v1.5.0 h1:kDegqA/FYQhcn294zUJ3U3VBegfvhtcI7ObcAku1zkw=
-codeberg.org/gruf/go-mutexes v1.5.0/go.mod h1:rPEqQ/y6CmGITaZ3GPTMQVsoZAOzbsAHyIaLsJcOqVE=
+codeberg.org/gruf/go-mutexes v1.5.1 h1:xICU0WXhWr6wf+Iror4eE3xT+xnXNPrO6o77D/G6QuY=
+codeberg.org/gruf/go-mutexes v1.5.1/go.mod h1:rPEqQ/y6CmGITaZ3GPTMQVsoZAOzbsAHyIaLsJcOqVE=
codeberg.org/gruf/go-runners v1.6.2 h1:oQef9niahfHu/wch14xNxlRMP8i+ABXH1Cb9PzZ4oYo=
codeberg.org/gruf/go-runners v1.6.2/go.mod h1:Tq5PrZ/m/rBXbLZz0u5if+yP3nG5Sf6S8O/GnyEePeQ=
codeberg.org/gruf/go-sched v1.2.3 h1:H5ViDxxzOBR3uIyGBCf0eH8b1L8wMybOXcdtUUTXZHk=
@@ -148,10 +148,6 @@ github.com/disintegration/imaging v1.6.2 h1:w1LecBlG2Lnp8B3jk5zSuNqd7b4DXhcjwek1
github.com/disintegration/imaging v1.6.2/go.mod h1:44/5580QXChDfwIclfc/PCwrr44amcmDAg8hxG0Ewe4=
github.com/docker/go-units v0.5.0 h1:69rxXcBk27SvSaaxTtLh/8llcHD8vYHT7WSdRZ/jvr4=
github.com/docker/go-units v0.5.0/go.mod h1:fgPhTUdO+D/Jk86RDLlptpiXQzgHJF7gydDDbaIK4Dk=
-github.com/dolthub/maphash v0.1.0 h1:bsQ7JsF4FkkWyrP3oCnFJgrCUAFbFf3kOl4L/QxPDyQ=
-github.com/dolthub/maphash v0.1.0/go.mod h1:gkg4Ch4CdCDu5h6PMriVLawB7koZ+5ijb9puGMV50a4=
-github.com/dolthub/swiss v0.2.1 h1:gs2osYs5SJkAaH5/ggVJqXQxRXtWshF6uE0lgR/Y3Gw=
-github.com/dolthub/swiss v0.2.1/go.mod h1:8AhKZZ1HK7g18j7v7k6c5cYIGEZJcPn0ARsai8cUrh0=
github.com/dsoprea/go-exif/v2 v2.0.0-20200321225314-640175a69fe4/go.mod h1:Lm2lMM2zx8p4a34ZemkaUV95AnMl4ZvLbCUbwOvLC2E=
github.com/dsoprea/go-exif/v3 v3.0.0-20200717053412-08f1b6708903/go.mod h1:0nsO1ce0mh5czxGeLo4+OCZ/C6Eo6ZlMWsz7rH/Gxv8=
github.com/dsoprea/go-exif/v3 v3.0.0-20210428042052-dca55bf8ca15/go.mod h1:cg5SNYKHMmzxsr9X6ZeLh/nfBRHHp5PngtEPcujONtk=
diff --git a/vendor/codeberg.org/gruf/go-mutexes/cond.go b/vendor/codeberg.org/gruf/go-mutexes/cond.go
index d89040c02..3d7f21126 100644
--- a/vendor/codeberg.org/gruf/go-mutexes/cond.go
+++ b/vendor/codeberg.org/gruf/go-mutexes/cond.go
@@ -2,86 +2,66 @@ package mutexes
import (
"sync"
- "unsafe"
)
// Cond is similar to a sync.Cond{}, but
// it encompasses the Mutex{} within itself.
type Cond struct {
- notify notifyList
+ c sync.Cond
sync.Mutex
}
// See: sync.Cond{}.Wait().
func (c *Cond) Wait() {
- t := runtime_notifyListAdd(&c.notify)
- c.Mutex.Unlock()
- runtime_notifyListWait(&c.notify, t)
- c.Mutex.Lock()
+ if c.c.L == nil {
+ c.c.L = &c.Mutex
+ }
+ c.c.Wait()
}
// See: sync.Cond{}.Signal().
-func (c *Cond) Signal() { runtime_notifyListNotifyOne(&c.notify) }
+func (c *Cond) Signal() {
+ if c.c.L == nil {
+ c.c.L = &c.Mutex
+ }
+ c.c.Signal()
+}
// See: sync.Cond{}.Broadcast().
-func (c *Cond) Broadcast() { runtime_notifyListNotifyAll(&c.notify) }
+func (c *Cond) Broadcast() {
+ if c.c.L == nil {
+ c.c.L = &c.Mutex
+ }
+ c.c.Broadcast()
+}
// RWCond is similar to a sync.Cond{}, but
// it encompasses the RWMutex{} within itself.
type RWCond struct {
- notify notifyList
+ c sync.Cond
sync.RWMutex
}
// See: sync.Cond{}.Wait().
func (c *RWCond) Wait() {
- t := runtime_notifyListAdd(&c.notify)
- c.RWMutex.Unlock()
- runtime_notifyListWait(&c.notify, t)
- c.RWMutex.Lock()
+ if c.c.L == nil {
+ c.c.L = &c.RWMutex
+ }
+ c.c.Wait()
}
// See: sync.Cond{}.Signal().
-func (c *RWCond) Signal() { runtime_notifyListNotifyOne(&c.notify) }
-
-// See: sync.Cond{}.Broadcast().
-func (c *RWCond) Broadcast() { runtime_notifyListNotifyAll(&c.notify) }
-
-// unused fields left
-// un-named for safety.
-type notifyList struct {
- _ uint32 // wait uint32
- notify uint32 // notify uint32
- _ uintptr // lock mutex
- _ unsafe.Pointer // head *sudog
- _ unsafe.Pointer // tail *sudog
+func (c *RWCond) Signal() {
+ if c.c.L == nil {
+ c.c.L = &c.RWMutex
+ }
+ c.c.Signal()
}
-// See runtime/sema.go for documentation.
-//
-//go:linkname runtime_notifyListAdd sync.runtime_notifyListAdd
-func runtime_notifyListAdd(l *notifyList) uint32
-
-// See runtime/sema.go for documentation.
-//
-//go:linkname runtime_notifyListWait sync.runtime_notifyListWait
-func runtime_notifyListWait(l *notifyList, t uint32)
-
-// See runtime/sema.go for documentation.
-//
-//go:linkname runtime_notifyListNotifyOne sync.runtime_notifyListNotifyOne
-func runtime_notifyListNotifyOne(l *notifyList)
-
-// See runtime/sema.go for documentation.
-//
-//go:linkname runtime_notifyListNotifyAll sync.runtime_notifyListNotifyAll
-func runtime_notifyListNotifyAll(l *notifyList)
-
-// Ensure that sync and runtime agree on size of notifyList.
-//
-//go:linkname runtime_notifyListCheck sync.runtime_notifyListCheck
-func runtime_notifyListCheck(size uintptr)
-func init() {
- var n notifyList
- runtime_notifyListCheck(unsafe.Sizeof(n))
+// See: sync.Cond{}.Broadcast().
+func (c *RWCond) Broadcast() {
+ if c.c.L == nil {
+ c.c.L = &c.RWMutex
+ }
+ c.c.Broadcast()
}
diff --git a/vendor/codeberg.org/gruf/go-mutexes/hash_map.go b/vendor/codeberg.org/gruf/go-mutexes/hash_map.go
new file mode 100644
index 000000000..a177133b5
--- /dev/null
+++ b/vendor/codeberg.org/gruf/go-mutexes/hash_map.go
@@ -0,0 +1,56 @@
+package mutexes
+
+type hashmap struct {
+ m map[string]*rwmutex
+ n int
+}
+
+func (m *hashmap) init(cap int) {
+ m.m = make(map[string]*rwmutex, cap)
+ m.n = cap
+}
+
+func (m *hashmap) Get(key string) *rwmutex { return m.m[key] }
+
+func (m *hashmap) Put(key string, mu *rwmutex) {
+ m.m[key] = mu
+ if n := len(m.m); n > m.n {
+ m.n = n
+ }
+}
+
+func (m *hashmap) Delete(key string) {
+ delete(m.m, key)
+}
+
+func (m *hashmap) Compact() {
+ // Noop when hashmap size
+ // is too small to matter.
+ if m.n < 2048 {
+ return
+ }
+
+ // Difference between maximum map
+ // size and the current map size.
+ diff := m.n - len(m.m)
+
+ // Maximum load factor before
+ // runtime allocates new hmap:
+ // maxLoad = 13 / 16
+ //
+ // So we apply the inverse/2, once
+ // $maxLoad/2 % of hmap is empty we
+ // compact the map to drop buckets.
+ if 2*16*diff > m.n*13 {
+
+ // Create new map only as big as required.
+ m2 := make(map[string]*rwmutex, len(m.m))
+ for k, v := range m.m {
+ m2[k] = v
+ }
+
+ // Set new.
+ m.m = m2
+ m.n = len(m2)
+ }
+}
diff --git a/vendor/codeberg.org/gruf/go-mutexes/map.go b/vendor/codeberg.org/gruf/go-mutexes/map.go
index 0da1fc3cc..4b721cec4 100644
--- a/vendor/codeberg.org/gruf/go-mutexes/map.go
+++ b/vendor/codeberg.org/gruf/go-mutexes/map.go
@@ -6,7 +6,6 @@ import (
"unsafe"
"codeberg.org/gruf/go-mempool"
- "github.com/dolthub/swiss"
)
const (
@@ -27,14 +26,14 @@ const (
// like structures for sleeping / awaking awaiting goroutines.
type MutexMap struct {
mapmu sync.Mutex
- mumap *swiss.Map[string, *rwmutex]
+ mumap hashmap
mupool mempool.UnsafePool
}
// checkInit ensures MutexMap is initialized (UNSAFE).
func (mm *MutexMap) checkInit() {
- if mm.mumap == nil {
- mm.mumap = swiss.NewMap[string, *rwmutex](0)
+ if mm.mumap.m == nil {
+ mm.mumap.init(0)
mm.mupool.DirtyFactor = 256
}
}
@@ -58,7 +57,7 @@ func (mm *MutexMap) lock(key string, lt uint8) func() {
for {
// Check map for mutex.
- mu, _ := mm.mumap.Get(key)
+ mu := mm.mumap.Get(key)
if mu == nil {
// Allocate mutex.
@@ -69,7 +68,7 @@ func (mm *MutexMap) lock(key string, lt uint8) func() {
if !mu.Lock(lt) {
// Wait on mutex unlock, after
// immediately relocking map mu.
- mu.WaitRelock(&mm.mapmu)
+ mu.WaitRelock()
continue
}
@@ -100,27 +99,9 @@ func (mm *MutexMap) unlock(key string, mu *rwmutex) {
mm.mumap.Delete(key)
mm.release(mu)
- // Maximum load factor before
- // 'swiss' allocates new hmap:
- // maxLoad = 7 / 8
- //
- // So we apply the inverse/2, once
- // $maxLoad/2 % of hmap is empty we
- // compact the map to drop buckets.
- len := mm.mumap.Count()
- cap := mm.mumap.Capacity()
- if cap-len > (cap*7)/(8*2) {
-
- // Create a new map only as big as required.
- mumap := swiss.NewMap[string, *rwmutex](uint32(len))
- mm.mumap.Iter(func(k string, v *rwmutex) (stop bool) {
- mumap.Put(k, v)
- return false
- })
-
- // Set new map.
- mm.mumap = mumap
- }
+ // Check if compaction
+ // needed.
+ mm.mumap.Compact()
// Done with map.
mm.mapmu.Unlock()
@@ -131,7 +112,9 @@ func (mm *MutexMap) acquire() *rwmutex {
if ptr := mm.mupool.Get(); ptr != nil {
return (*rwmutex)(ptr)
}
- return new(rwmutex)
+ mu := new(rwmutex)
+ mu.c.L = &mm.mapmu
+ return mu
}
// release will release given mutex to memory pool.
@@ -152,9 +135,9 @@ func (mm *MutexMap) release(mu *rwmutex) {
// mechanism we use, otherwise all Cond{}.L would reference
// the same outer map mutex.
type rwmutex struct {
- n notifyList // 'trigger' mechanism
- l int32 // no. locks
- t uint8 // lock type
+ c sync.Cond // 'trigger' mechanism
+ l int32 // no. locks
+ t uint8 // lock type
}
// Lock will lock the mutex for given lock type, in the
@@ -202,11 +185,34 @@ func (mu *rwmutex) Unlock() bool {
// Fully unlocked.
mu.t = 0
+ // NOTE: must remain in
+ // sync with runtime.notifyList{}.
+ //
+ // goexperiment.staticlockranking
+ // does change it slightly, but
+ // this does not alter the first
+ // 2 fields which are all we need.
+ type notifyList struct {
+ _ uint32
+ notify uint32
+ // ... other fields
+ }
+
+ // NOTE: must remain in
+ // sync with sync.Cond{}.
+ type syncCond struct {
+ _ struct{}
+ L sync.Locker
+ n notifyList
+ // ... other fields
+ }
+
// Awake all blocked goroutines and check
// for change in the last notified ticket.
- before := atomic.LoadUint32(&mu.n.notify)
- runtime_notifyListNotifyAll(&mu.n)
- after := atomic.LoadUint32(&mu.n.notify)
+ cptr := (*syncCond)(unsafe.Pointer(&mu.c))
+ before := atomic.LoadUint32(&cptr.n.notify)
+ mu.c.Broadcast() // awakes all blocked!
+ after := atomic.LoadUint32(&cptr.n.notify)
// If ticket changed, this indicates
// AT LEAST one goroutine was awoken.
@@ -226,20 +232,4 @@ func (mu *rwmutex) Unlock() bool {
// locked state. It incr the notifyList waiter count before
// unlocking the outer mutex and blocking on notifyList wait.
// On awake it will decr wait count and relock outer mutex.
-func (mu *rwmutex) WaitRelock(outer *sync.Mutex) {
-
- // add ourselves to list while still
- // under protection of outer map lock.
- t := runtime_notifyListAdd(&mu.n)
-
- // Finished with
- // outer map lock.
- outer.Unlock()
-
- // Block until awoken by another
- // goroutine within mu.Unlock().
- runtime_notifyListWait(&mu.n, t)
-
- // Relock!
- outer.Lock()
-}
+func (mu *rwmutex) WaitRelock() { mu.c.Wait() }
diff --git a/vendor/github.com/dolthub/maphash/.gitignore b/vendor/github.com/dolthub/maphash/.gitignore
deleted file mode 100644
index 977a7cadf..000000000
--- a/vendor/github.com/dolthub/maphash/.gitignore
+++ /dev/null
@@ -1,2 +0,0 @@
-*.idea
-*.test \ No newline at end of file
diff --git a/vendor/github.com/dolthub/maphash/LICENSE b/vendor/github.com/dolthub/maphash/LICENSE
deleted file mode 100644
index 261eeb9e9..000000000
--- a/vendor/github.com/dolthub/maphash/LICENSE
+++ /dev/null
@@ -1,201 +0,0 @@
- Apache License
- Version 2.0, January 2004
- http://www.apache.org/licenses/
-
- TERMS AND CONDITIONS FOR USE, REPRODUCTION, AND DISTRIBUTION
-
- 1. Definitions.
-
- "License" shall mean the terms and conditions for use, reproduction,
- and distribution as defined by Sections 1 through 9 of this document.
-
- "Licensor" shall mean the copyright owner or entity authorized by
- the copyright owner that is granting the License.
-
- "Legal Entity" shall mean the union of the acting entity and all
- other entities that control, are controlled by, or are under common
- control with that entity. For the purposes of this definition,
- "control" means (i) the power, direct or indirect, to cause the
- direction or management of such entity, whether by contract or
- otherwise, or (ii) ownership of fifty percent (50%) or more of the
- outstanding shares, or (iii) beneficial ownership of such entity.
-
- "You" (or "Your") shall mean an individual or Legal Entity
- exercising permissions granted by this License.
-
- "Source" form shall mean the preferred form for making modifications,
- including but not limited to software source code, documentation
- source, and configuration files.
-
- "Object" form shall mean any form resulting from mechanical
- transformation or translation of a Source form, including but
- not limited to compiled object code, generated documentation,
- and conversions to other media types.
-
- "Work" shall mean the work of authorship, whether in Source or
- Object form, made available under the License, as indicated by a
- copyright notice that is included in or attached to the work
- (an example is provided in the Appendix below).
-
- "Derivative Works" shall mean any work, whether in Source or Object
- form, that is based on (or derived from) the Work and for which the
- editorial revisions, annotations, elaborations, or other modifications
- represent, as a whole, an original work of authorship. For the purposes
- of this License, Derivative Works shall not include works that remain
- separable from, or merely link (or bind by name) to the interfaces of,
- the Work and Derivative Works thereof.
-
- "Contribution" shall mean any work of authorship, including
- the original version of the Work and any modifications or additions
- to that Work or Derivative Works thereof, that is intentionally
- submitted to Licensor for inclusion in the Work by the copyright owner
- or by an individual or Legal Entity authorized to submit on behalf of
- the copyright owner. For the purposes of this definition, "submitted"
- means any form of electronic, verbal, or written communication sent
- to the Licensor or its representatives, including but not limited to
- communication on electronic mailing lists, source code control systems,
- and issue tracking systems that are managed by, or on behalf of, the
- Licensor for the purpose of discussing and improving the Work, but
- excluding communication that is conspicuously marked or otherwise
- designated in writing by the copyright owner as "Not a Contribution."
-
- "Contributor" shall mean Licensor and any individual or Legal Entity
- on behalf of whom a Contribution has been received by Licensor and
- subsequently incorporated within the Work.
-
- 2. Grant of Copyright License. Subject to the terms and conditions of
- this License, each Contributor hereby grants to You a perpetual,
- worldwide, non-exclusive, no-charge, royalty-free, irrevocable
- copyright license to reproduce, prepare Derivative Works of,
- publicly display, publicly perform, sublicense, and distribute the
- Work and such Derivative Works in Source or Object form.
-
- 3. Grant of Patent License. Subject to the terms and conditions of
- this License, each Contributor 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, and otherwise transfer the Work,
- where such license applies only to those patent claims licensable
- by such Contributor that are necessarily infringed by their
- Contribution(s) alone or by combination of their Contribution(s)
- with the Work to which such Contribution(s) was submitted. If You
- institute patent litigation against any entity (including a
- cross-claim or counterclaim in a lawsuit) alleging that the Work
- or a Contribution incorporated within the Work constitutes direct
- or contributory patent infringement, then any patent licenses
- granted to You under this License for that Work shall terminate
- as of the date such litigation is filed.
-
- 4. Redistribution. You may reproduce and distribute copies of the
- Work or Derivative Works thereof in any medium, with or without
- modifications, and in Source or Object form, provided that You
- meet the following conditions:
-
- (a) You must give any other recipients of the Work or
- Derivative Works a copy of this License; and
-
- (b) You must cause any modified files to carry prominent notices
- stating that You changed the files; and
-
- (c) You must retain, in the Source form of any Derivative Works
- that You distribute, all copyright, patent, trademark, and
- attribution notices from the Source form of the Work,
- excluding those notices that do not pertain to any part of
- the Derivative Works; and
-
- (d) If the Work includes a "NOTICE" text file as part of its
- distribution, then any Derivative Works that You distribute must
- include a readable copy of the attribution notices contained
- within such NOTICE file, excluding those notices that do not
- pertain to any part of the Derivative Works, in at least one
- of the following places: within a NOTICE text file distributed
- as part of the Derivative Works; within the Source form or
- documentation, if provided along with the Derivative Works; or,
- within a display generated by the Derivative Works, if and
- wherever such third-party notices normally appear. The contents
- of the NOTICE file are for informational purposes only and
- do not modify the License. You may add Your own attribution
- notices within Derivative Works that You distribute, alongside
- or as an addendum to the NOTICE text from the Work, provided
- that such additional attribution notices cannot be construed
- as modifying the License.
-
- You may add Your own copyright statement to Your modifications and
- may provide additional or different license terms and conditions
- for use, reproduction, or distribution of Your modifications, or
- for any such Derivative Works as a whole, provided Your use,
- reproduction, and distribution of the Work otherwise complies with
- the conditions stated in this License.
-
- 5. Submission of Contributions. Unless You explicitly state otherwise,
- any Contribution intentionally submitted for inclusion in the Work
- by You to the Licensor shall be under the terms and conditions of
- this License, without any additional terms or conditions.
- Notwithstanding the above, nothing herein shall supersede or modify
- the terms of any separate license agreement you may have executed
- with Licensor regarding such Contributions.
-
- 6. Trademarks. This License does not grant permission to use the trade
- names, trademarks, service marks, or product names of the Licensor,
- except as required for reasonable and customary use in describing the
- origin of the Work and reproducing the content of the NOTICE file.
-
- 7. Disclaimer of Warranty. Unless required by applicable law or
- agreed to in writing, Licensor provides the Work (and each
- Contributor provides its Contributions) on an "AS IS" BASIS,
- WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or
- implied, including, without limitation, any warranties or conditions
- of TITLE, NON-INFRINGEMENT, MERCHANTABILITY, or FITNESS FOR A
- PARTICULAR PURPOSE. You are solely responsible for determining the
- appropriateness of using or redistributing the Work and assume any
- risks associated with Your exercise of permissions under this License.
-
- 8. Limitation of Liability. In no event and under no legal theory,
- whether in tort (including negligence), contract, or otherwise,
- unless required by applicable law (such as deliberate and grossly
- negligent acts) or agreed to in writing, shall any Contributor be
- liable to You for damages, including any direct, indirect, special,
- incidental, or consequential damages of any character arising as a
- result of this License or out of the use or inability to use the
- Work (including but not limited to damages for loss of goodwill,
- work stoppage, computer failure or malfunction, or any and all
- other commercial damages or losses), even if such Contributor
- has been advised of the possibility of such damages.
-
- 9. Accepting Warranty or Additional Liability. While redistributing
- the Work or Derivative Works thereof, You may choose to offer,
- and charge a fee for, acceptance of support, warranty, indemnity,
- or other liability obligations and/or rights consistent with this
- License. However, in accepting such obligations, You may act only
- on Your own behalf and on Your sole responsibility, not on behalf
- of any other Contributor, and only if You agree to indemnify,
- defend, and hold each Contributor harmless for any liability
- incurred by, or claims asserted against, such Contributor by reason
- of your accepting any such warranty or additional liability.
-
- END OF TERMS AND CONDITIONS
-
- APPENDIX: How to apply the Apache License to your work.
-
- To apply the Apache License to your work, attach the following
- boilerplate notice, with the fields enclosed by brackets "[]"
- replaced with your own identifying information. (Don't include
- the brackets!) The text should be enclosed in the appropriate
- comment syntax for the file format. We also recommend that a
- file or class name and description of purpose be included on the
- same "printed page" as the copyright notice for easier
- identification within third-party archives.
-
- Copyright [yyyy] [name of copyright owner]
-
- Licensed under the Apache License, Version 2.0 (the "License");
- you may not use this file except in compliance with the License.
- You may obtain a copy of the License at
-
- http://www.apache.org/licenses/LICENSE-2.0
-
- Unless required by applicable law or agreed to in writing, software
- distributed under the License is distributed on an "AS IS" BASIS,
- WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
- See the License for the specific language governing permissions and
- limitations under the License.
diff --git a/vendor/github.com/dolthub/maphash/README.md b/vendor/github.com/dolthub/maphash/README.md
deleted file mode 100644
index d91530f99..000000000
--- a/vendor/github.com/dolthub/maphash/README.md
+++ /dev/null
@@ -1,4 +0,0 @@
-# maphash
-
-Hash any `comparable` type using Golang's fast runtime hash.
-Uses [AES](https://en.wikipedia.org/wiki/AES_instruction_set) instructions when available. \ No newline at end of file
diff --git a/vendor/github.com/dolthub/maphash/hasher.go b/vendor/github.com/dolthub/maphash/hasher.go
deleted file mode 100644
index ef53596a2..000000000
--- a/vendor/github.com/dolthub/maphash/hasher.go
+++ /dev/null
@@ -1,48 +0,0 @@
-// Copyright 2022 Dolthub, Inc.
-//
-// Licensed under the Apache License, Version 2.0 (the "License");
-// you may not use this file except in compliance with the License.
-// You may obtain a copy of the License at
-//
-// http://www.apache.org/licenses/LICENSE-2.0
-//
-// Unless required by applicable law or agreed to in writing, software
-// distributed under the License is distributed on an "AS IS" BASIS,
-// WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
-// See the License for the specific language governing permissions and
-// limitations under the License.
-
-package maphash
-
-import "unsafe"
-
-// Hasher hashes values of type K.
-// Uses runtime AES-based hashing.
-type Hasher[K comparable] struct {
- hash hashfn
- seed uintptr
-}
-
-// NewHasher creates a new Hasher[K] with a random seed.
-func NewHasher[K comparable]() Hasher[K] {
- return Hasher[K]{
- hash: getRuntimeHasher[K](),
- seed: newHashSeed(),
- }
-}
-
-// NewSeed returns a copy of |h| with a new hash seed.
-func NewSeed[K comparable](h Hasher[K]) Hasher[K] {
- return Hasher[K]{
- hash: h.hash,
- seed: newHashSeed(),
- }
-}
-
-// Hash hashes |key|.
-func (h Hasher[K]) Hash(key K) uint64 {
- // promise to the compiler that pointer
- // |p| does not escape the stack.
- p := noescape(unsafe.Pointer(&key))
- return uint64(h.hash(p, h.seed))
-}
diff --git a/vendor/github.com/dolthub/maphash/runtime.go b/vendor/github.com/dolthub/maphash/runtime.go
deleted file mode 100644
index 29cd6a8ed..000000000
--- a/vendor/github.com/dolthub/maphash/runtime.go
+++ /dev/null
@@ -1,111 +0,0 @@
-// Copyright 2022 Dolthub, Inc.
-//
-// Licensed under the Apache License, Version 2.0 (the "License");
-// you may not use this file except in compliance with the License.
-// You may obtain a copy of the License at
-//
-// http://www.apache.org/licenses/LICENSE-2.0
-//
-// Unless required by applicable law or agreed to in writing, software
-// distributed under the License is distributed on an "AS IS" BASIS,
-// WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
-// See the License for the specific language governing permissions and
-// limitations under the License.
-//
-// This file incorporates work covered by the following copyright and
-// permission notice:
-//
-// 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.
-
-//go:build go1.18 || go1.19
-// +build go1.18 go1.19
-
-package maphash
-
-import (
- "math/rand"
- "unsafe"
-)
-
-type hashfn func(unsafe.Pointer, uintptr) uintptr
-
-func getRuntimeHasher[K comparable]() (h hashfn) {
- a := any(make(map[K]struct{}))
- i := (*mapiface)(unsafe.Pointer(&a))
- h = i.typ.hasher
- return
-}
-
-func newHashSeed() uintptr {
- return uintptr(rand.Int())
-}
-
-// noescape hides a pointer from escape analysis. It is the identity function
-// but escape analysis doesn't think the output depends on the input.
-// noescape is inlined and currently compiles down to zero instructions.
-// USE CAREFULLY!
-// This was copied from the runtime (via pkg "strings"); see issues 23382 and 7921.
-//
-//go:nosplit
-//go:nocheckptr
-func noescape(p unsafe.Pointer) unsafe.Pointer {
- x := uintptr(p)
- return unsafe.Pointer(x ^ 0)
-}
-
-type mapiface struct {
- typ *maptype
- val *hmap
-}
-
-// go/src/runtime/type.go
-type maptype struct {
- typ _type
- key *_type
- elem *_type
- bucket *_type
- // function for hashing keys (ptr to key, seed) -> hash
- hasher func(unsafe.Pointer, uintptr) uintptr
- keysize uint8
- elemsize uint8
- bucketsize uint16
- flags uint32
-}
-
-// go/src/runtime/map.go
-type hmap struct {
- count int
- flags uint8
- B uint8
- noverflow uint16
- // hash seed
- hash0 uint32
- buckets unsafe.Pointer
- oldbuckets unsafe.Pointer
- nevacuate uintptr
- // true type is *mapextra
- // but we don't need this data
- extra unsafe.Pointer
-}
-
-// go/src/runtime/type.go
-type tflag uint8
-type nameOff int32
-type typeOff int32
-
-// go/src/runtime/type.go
-type _type struct {
- size uintptr
- ptrdata uintptr
- hash uint32
- tflag tflag
- align uint8
- fieldAlign uint8
- kind uint8
- equal func(unsafe.Pointer, unsafe.Pointer) bool
- gcdata *byte
- str nameOff
- ptrToThis typeOff
-}
diff --git a/vendor/github.com/dolthub/swiss/.gitignore b/vendor/github.com/dolthub/swiss/.gitignore
deleted file mode 100644
index 1f9adf93b..000000000
--- a/vendor/github.com/dolthub/swiss/.gitignore
+++ /dev/null
@@ -1,5 +0,0 @@
-**/.idea/
-.vscode
-.run
-venv
-.DS_Store \ No newline at end of file
diff --git a/vendor/github.com/dolthub/swiss/LICENSE b/vendor/github.com/dolthub/swiss/LICENSE
deleted file mode 100644
index 261eeb9e9..000000000
--- a/vendor/github.com/dolthub/swiss/LICENSE
+++ /dev/null
@@ -1,201 +0,0 @@
- Apache License
- Version 2.0, January 2004
- http://www.apache.org/licenses/
-
- TERMS AND CONDITIONS FOR USE, REPRODUCTION, AND DISTRIBUTION
-
- 1. Definitions.
-
- "License" shall mean the terms and conditions for use, reproduction,
- and distribution as defined by Sections 1 through 9 of this document.
-
- "Licensor" shall mean the copyright owner or entity authorized by
- the copyright owner that is granting the License.
-
- "Legal Entity" shall mean the union of the acting entity and all
- other entities that control, are controlled by, or are under common
- control with that entity. For the purposes of this definition,
- "control" means (i) the power, direct or indirect, to cause the
- direction or management of such entity, whether by contract or
- otherwise, or (ii) ownership of fifty percent (50%) or more of the
- outstanding shares, or (iii) beneficial ownership of such entity.
-
- "You" (or "Your") shall mean an individual or Legal Entity
- exercising permissions granted by this License.
-
- "Source" form shall mean the preferred form for making modifications,
- including but not limited to software source code, documentation
- source, and configuration files.
-
- "Object" form shall mean any form resulting from mechanical
- transformation or translation of a Source form, including but
- not limited to compiled object code, generated documentation,
- and conversions to other media types.
-
- "Work" shall mean the work of authorship, whether in Source or
- Object form, made available under the License, as indicated by a
- copyright notice that is included in or attached to the work
- (an example is provided in the Appendix below).
-
- "Derivative Works" shall mean any work, whether in Source or Object
- form, that is based on (or derived from) the Work and for which the
- editorial revisions, annotations, elaborations, or other modifications
- represent, as a whole, an original work of authorship. For the purposes
- of this License, Derivative Works shall not include works that remain
- separable from, or merely link (or bind by name) to the interfaces of,
- the Work and Derivative Works thereof.
-
- "Contribution" shall mean any work of authorship, including
- the original version of the Work and any modifications or additions
- to that Work or Derivative Works thereof, that is intentionally
- submitted to Licensor for inclusion in the Work by the copyright owner
- or by an individual or Legal Entity authorized to submit on behalf of
- the copyright owner. For the purposes of this definition, "submitted"
- means any form of electronic, verbal, or written communication sent
- to the Licensor or its representatives, including but not limited to
- communication on electronic mailing lists, source code control systems,
- and issue tracking systems that are managed by, or on behalf of, the
- Licensor for the purpose of discussing and improving the Work, but
- excluding communication that is conspicuously marked or otherwise
- designated in writing by the copyright owner as "Not a Contribution."
-
- "Contributor" shall mean Licensor and any individual or Legal Entity
- on behalf of whom a Contribution has been received by Licensor and
- subsequently incorporated within the Work.
-
- 2. Grant of Copyright License. Subject to the terms and conditions of
- this License, each Contributor hereby grants to You a perpetual,
- worldwide, non-exclusive, no-charge, royalty-free, irrevocable
- copyright license to reproduce, prepare Derivative Works of,
- publicly display, publicly perform, sublicense, and distribute the
- Work and such Derivative Works in Source or Object form.
-
- 3. Grant of Patent License. Subject to the terms and conditions of
- this License, each Contributor 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, and otherwise transfer the Work,
- where such license applies only to those patent claims licensable
- by such Contributor that are necessarily infringed by their
- Contribution(s) alone or by combination of their Contribution(s)
- with the Work to which such Contribution(s) was submitted. If You
- institute patent litigation against any entity (including a
- cross-claim or counterclaim in a lawsuit) alleging that the Work
- or a Contribution incorporated within the Work constitutes direct
- or contributory patent infringement, then any patent licenses
- granted to You under this License for that Work shall terminate
- as of the date such litigation is filed.
-
- 4. Redistribution. You may reproduce and distribute copies of the
- Work or Derivative Works thereof in any medium, with or without
- modifications, and in Source or Object form, provided that You
- meet the following conditions:
-
- (a) You must give any other recipients of the Work or
- Derivative Works a copy of this License; and
-
- (b) You must cause any modified files to carry prominent notices
- stating that You changed the files; and
-
- (c) You must retain, in the Source form of any Derivative Works
- that You distribute, all copyright, patent, trademark, and
- attribution notices from the Source form of the Work,
- excluding those notices that do not pertain to any part of
- the Derivative Works; and
-
- (d) If the Work includes a "NOTICE" text file as part of its
- distribution, then any Derivative Works that You distribute must
- include a readable copy of the attribution notices contained
- within such NOTICE file, excluding those notices that do not
- pertain to any part of the Derivative Works, in at least one
- of the following places: within a NOTICE text file distributed
- as part of the Derivative Works; within the Source form or
- documentation, if provided along with the Derivative Works; or,
- within a display generated by the Derivative Works, if and
- wherever such third-party notices normally appear. The contents
- of the NOTICE file are for informational purposes only and
- do not modify the License. You may add Your own attribution
- notices within Derivative Works that You distribute, alongside
- or as an addendum to the NOTICE text from the Work, provided
- that such additional attribution notices cannot be construed
- as modifying the License.
-
- You may add Your own copyright statement to Your modifications and
- may provide additional or different license terms and conditions
- for use, reproduction, or distribution of Your modifications, or
- for any such Derivative Works as a whole, provided Your use,
- reproduction, and distribution of the Work otherwise complies with
- the conditions stated in this License.
-
- 5. Submission of Contributions. Unless You explicitly state otherwise,
- any Contribution intentionally submitted for inclusion in the Work
- by You to the Licensor shall be under the terms and conditions of
- this License, without any additional terms or conditions.
- Notwithstanding the above, nothing herein shall supersede or modify
- the terms of any separate license agreement you may have executed
- with Licensor regarding such Contributions.
-
- 6. Trademarks. This License does not grant permission to use the trade
- names, trademarks, service marks, or product names of the Licensor,
- except as required for reasonable and customary use in describing the
- origin of the Work and reproducing the content of the NOTICE file.
-
- 7. Disclaimer of Warranty. Unless required by applicable law or
- agreed to in writing, Licensor provides the Work (and each
- Contributor provides its Contributions) on an "AS IS" BASIS,
- WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or
- implied, including, without limitation, any warranties or conditions
- of TITLE, NON-INFRINGEMENT, MERCHANTABILITY, or FITNESS FOR A
- PARTICULAR PURPOSE. You are solely responsible for determining the
- appropriateness of using or redistributing the Work and assume any
- risks associated with Your exercise of permissions under this License.
-
- 8. Limitation of Liability. In no event and under no legal theory,
- whether in tort (including negligence), contract, or otherwise,
- unless required by applicable law (such as deliberate and grossly
- negligent acts) or agreed to in writing, shall any Contributor be
- liable to You for damages, including any direct, indirect, special,
- incidental, or consequential damages of any character arising as a
- result of this License or out of the use or inability to use the
- Work (including but not limited to damages for loss of goodwill,
- work stoppage, computer failure or malfunction, or any and all
- other commercial damages or losses), even if such Contributor
- has been advised of the possibility of such damages.
-
- 9. Accepting Warranty or Additional Liability. While redistributing
- the Work or Derivative Works thereof, You may choose to offer,
- and charge a fee for, acceptance of support, warranty, indemnity,
- or other liability obligations and/or rights consistent with this
- License. However, in accepting such obligations, You may act only
- on Your own behalf and on Your sole responsibility, not on behalf
- of any other Contributor, and only if You agree to indemnify,
- defend, and hold each Contributor harmless for any liability
- incurred by, or claims asserted against, such Contributor by reason
- of your accepting any such warranty or additional liability.
-
- END OF TERMS AND CONDITIONS
-
- APPENDIX: How to apply the Apache License to your work.
-
- To apply the Apache License to your work, attach the following
- boilerplate notice, with the fields enclosed by brackets "[]"
- replaced with your own identifying information. (Don't include
- the brackets!) The text should be enclosed in the appropriate
- comment syntax for the file format. We also recommend that a
- file or class name and description of purpose be included on the
- same "printed page" as the copyright notice for easier
- identification within third-party archives.
-
- Copyright [yyyy] [name of copyright owner]
-
- Licensed under the Apache License, Version 2.0 (the "License");
- you may not use this file except in compliance with the License.
- You may obtain a copy of the License at
-
- http://www.apache.org/licenses/LICENSE-2.0
-
- Unless required by applicable law or agreed to in writing, software
- distributed under the License is distributed on an "AS IS" BASIS,
- WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
- See the License for the specific language governing permissions and
- limitations under the License.
diff --git a/vendor/github.com/dolthub/swiss/README.md b/vendor/github.com/dolthub/swiss/README.md
deleted file mode 100644
index 71c6f7dd0..000000000
--- a/vendor/github.com/dolthub/swiss/README.md
+++ /dev/null
@@ -1,54 +0,0 @@
-# SwissMap
-
-SwissMap is a hash table adapated from the "SwissTable" family of hash tables from [Abseil](https://abseil.io/blog/20180927-swisstables). It uses [AES](https://github.com/dolthub/maphash) instructions for fast-hashing and performs key lookups in parallel using [SSE](https://en.wikipedia.org/wiki/Streaming_SIMD_Extensions) instructions. Because of these optimizations, SwissMap is faster and more memory efficient than Golang's built-in `map`. If you'd like to learn more about its design and implementation, check out this [blog post](https://www.dolthub.com/blog/2023-03-28-swiss-map/) announcing its release.
-
-
-## Example
-
-SwissMap exposes the same interface as the built-in `map`. Give it a try using this [Go playground](https://go.dev/play/p/JPDC5WhYN7g).
-
-```go
-package main
-
-import "github.com/dolthub/swiss"
-
-func main() {
- m := swiss.NewMap[string, int](42)
-
- m.Put("foo", 1)
- m.Put("bar", 2)
-
- m.Iter(func(k string, v int) (stop bool) {
- println("iter", k, v)
- return false // continue
- })
-
- if x, ok := m.Get("foo"); ok {
- println(x)
- }
- if m.Has("bar") {
- x, _ := m.Get("bar")
- println(x)
- }
-
- m.Put("foo", -1)
- m.Delete("bar")
-
- if x, ok := m.Get("foo"); ok {
- println(x)
- }
- if m.Has("bar") {
- x, _ := m.Get("bar")
- println(x)
- }
-
- m.Clear()
-
- // Output:
- // iter foo 1
- // iter bar 2
- // 1
- // 2
- // -1
-}
-```
diff --git a/vendor/github.com/dolthub/swiss/bits.go b/vendor/github.com/dolthub/swiss/bits.go
deleted file mode 100644
index f435b6dc9..000000000
--- a/vendor/github.com/dolthub/swiss/bits.go
+++ /dev/null
@@ -1,58 +0,0 @@
-// Copyright 2023 Dolthub, Inc.
-//
-// Licensed under the Apache License, Version 2.0 (the "License");
-// you may not use this file except in compliance with the License.
-// You may obtain a copy of the License at
-//
-// http://www.apache.org/licenses/LICENSE-2.0
-//
-// Unless required by applicable law or agreed to in writing, software
-// distributed under the License is distributed on an "AS IS" BASIS,
-// WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
-// See the License for the specific language governing permissions and
-// limitations under the License.
-
-//go:build !amd64 || nosimd
-
-package swiss
-
-import (
- "math/bits"
- "unsafe"
-)
-
-const (
- groupSize = 8
- maxAvgGroupLoad = 7
-
- loBits uint64 = 0x0101010101010101
- hiBits uint64 = 0x8080808080808080
-)
-
-type bitset uint64
-
-func metaMatchH2(m *metadata, h h2) bitset {
- // https://graphics.stanford.edu/~seander/bithacks.html##ValueInWord
- return hasZeroByte(castUint64(m) ^ (loBits * uint64(h)))
-}
-
-func metaMatchEmpty(m *metadata) bitset {
- return hasZeroByte(castUint64(m) ^ hiBits)
-}
-
-func nextMatch(b *bitset) uint32 {
- s := uint32(bits.TrailingZeros64(uint64(*b)))
- *b &= ^(1 << s) // clear bit |s|
- return s >> 3 // div by 8
-}
-
-func hasZeroByte(x uint64) bitset {
- return bitset(((x - loBits) & ^(x)) & hiBits)
-}
-
-func castUint64(m *metadata) uint64 {
- return *(*uint64)((unsafe.Pointer)(m))
-}
-
-//go:linkname fastrand runtime.fastrand
-func fastrand() uint32
diff --git a/vendor/github.com/dolthub/swiss/bits_amd64.go b/vendor/github.com/dolthub/swiss/bits_amd64.go
deleted file mode 100644
index 8b91f57cf..000000000
--- a/vendor/github.com/dolthub/swiss/bits_amd64.go
+++ /dev/null
@@ -1,50 +0,0 @@
-// Copyright 2023 Dolthub, Inc.
-//
-// Licensed under the Apache License, Version 2.0 (the "License");
-// you may not use this file except in compliance with the License.
-// You may obtain a copy of the License at
-//
-// http://www.apache.org/licenses/LICENSE-2.0
-//
-// Unless required by applicable law or agreed to in writing, software
-// distributed under the License is distributed on an "AS IS" BASIS,
-// WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
-// See the License for the specific language governing permissions and
-// limitations under the License.
-
-//go:build amd64 && !nosimd
-
-package swiss
-
-import (
- "math/bits"
- _ "unsafe"
-
- "github.com/dolthub/swiss/simd"
-)
-
-const (
- groupSize = 16
- maxAvgGroupLoad = 14
-)
-
-type bitset uint16
-
-func metaMatchH2(m *metadata, h h2) bitset {
- b := simd.MatchMetadata((*[16]int8)(m), int8(h))
- return bitset(b)
-}
-
-func metaMatchEmpty(m *metadata) bitset {
- b := simd.MatchMetadata((*[16]int8)(m), empty)
- return bitset(b)
-}
-
-func nextMatch(b *bitset) (s uint32) {
- s = uint32(bits.TrailingZeros16(uint16(*b)))
- *b &= ^(1 << s) // clear bit |s|
- return
-}
-
-//go:linkname fastrand runtime.fastrand
-func fastrand() uint32
diff --git a/vendor/github.com/dolthub/swiss/map.go b/vendor/github.com/dolthub/swiss/map.go
deleted file mode 100644
index e5ad20386..000000000
--- a/vendor/github.com/dolthub/swiss/map.go
+++ /dev/null
@@ -1,359 +0,0 @@
-// Copyright 2023 Dolthub, Inc.
-//
-// Licensed under the Apache License, Version 2.0 (the "License");
-// you may not use this file except in compliance with the License.
-// You may obtain a copy of the License at
-//
-// http://www.apache.org/licenses/LICENSE-2.0
-//
-// Unless required by applicable law or agreed to in writing, software
-// distributed under the License is distributed on an "AS IS" BASIS,
-// WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
-// See the License for the specific language governing permissions and
-// limitations under the License.
-
-package swiss
-
-import (
- "github.com/dolthub/maphash"
-)
-
-const (
- maxLoadFactor = float32(maxAvgGroupLoad) / float32(groupSize)
-)
-
-// Map is an open-addressing hash map
-// based on Abseil's flat_hash_map.
-type Map[K comparable, V any] struct {
- ctrl []metadata
- groups []group[K, V]
- hash maphash.Hasher[K]
- resident uint32
- dead uint32
- limit uint32
-}
-
-// metadata is the h2 metadata array for a group.
-// find operations first probe the controls bytes
-// to filter candidates before matching keys
-type metadata [groupSize]int8
-
-// group is a group of 16 key-value pairs
-type group[K comparable, V any] struct {
- keys [groupSize]K
- values [groupSize]V
-}
-
-const (
- h1Mask uint64 = 0xffff_ffff_ffff_ff80
- h2Mask uint64 = 0x0000_0000_0000_007f
- empty int8 = -128 // 0b1000_0000
- tombstone int8 = -2 // 0b1111_1110
-)
-
-// h1 is a 57 bit hash prefix
-type h1 uint64
-
-// h2 is a 7 bit hash suffix
-type h2 int8
-
-// NewMap constructs a Map.
-func NewMap[K comparable, V any](sz uint32) (m *Map[K, V]) {
- groups := numGroups(sz)
- m = &Map[K, V]{
- ctrl: make([]metadata, groups),
- groups: make([]group[K, V], groups),
- hash: maphash.NewHasher[K](),
- limit: groups * maxAvgGroupLoad,
- }
- for i := range m.ctrl {
- m.ctrl[i] = newEmptyMetadata()
- }
- return
-}
-
-// Has returns true if |key| is present in |m|.
-func (m *Map[K, V]) Has(key K) (ok bool) {
- hi, lo := splitHash(m.hash.Hash(key))
- g := probeStart(hi, len(m.groups))
- for { // inlined find loop
- matches := metaMatchH2(&m.ctrl[g], lo)
- for matches != 0 {
- s := nextMatch(&matches)
- if key == m.groups[g].keys[s] {
- ok = true
- return
- }
- }
- // |key| is not in group |g|,
- // stop probing if we see an empty slot
- matches = metaMatchEmpty(&m.ctrl[g])
- if matches != 0 {
- ok = false
- return
- }
- g += 1 // linear probing
- if g >= uint32(len(m.groups)) {
- g = 0
- }
- }
-}
-
-// Get returns the |value| mapped by |key| if one exists.
-func (m *Map[K, V]) Get(key K) (value V, ok bool) {
- hi, lo := splitHash(m.hash.Hash(key))
- g := probeStart(hi, len(m.groups))
- for { // inlined find loop
- matches := metaMatchH2(&m.ctrl[g], lo)
- for matches != 0 {
- s := nextMatch(&matches)
- if key == m.groups[g].keys[s] {
- value, ok = m.groups[g].values[s], true
- return
- }
- }
- // |key| is not in group |g|,
- // stop probing if we see an empty slot
- matches = metaMatchEmpty(&m.ctrl[g])
- if matches != 0 {
- ok = false
- return
- }
- g += 1 // linear probing
- if g >= uint32(len(m.groups)) {
- g = 0
- }
- }
-}
-
-// Put attempts to insert |key| and |value|
-func (m *Map[K, V]) Put(key K, value V) {
- if m.resident >= m.limit {
- m.rehash(m.nextSize())
- }
- hi, lo := splitHash(m.hash.Hash(key))
- g := probeStart(hi, len(m.groups))
- for { // inlined find loop
- matches := metaMatchH2(&m.ctrl[g], lo)
- for matches != 0 {
- s := nextMatch(&matches)
- if key == m.groups[g].keys[s] { // update
- m.groups[g].keys[s] = key
- m.groups[g].values[s] = value
- return
- }
- }
- // |key| is not in group |g|,
- // stop probing if we see an empty slot
- matches = metaMatchEmpty(&m.ctrl[g])
- if matches != 0 { // insert
- s := nextMatch(&matches)
- m.groups[g].keys[s] = key
- m.groups[g].values[s] = value
- m.ctrl[g][s] = int8(lo)
- m.resident++
- return
- }
- g += 1 // linear probing
- if g >= uint32(len(m.groups)) {
- g = 0
- }
- }
-}
-
-// Delete attempts to remove |key|, returns true successful.
-func (m *Map[K, V]) Delete(key K) (ok bool) {
- hi, lo := splitHash(m.hash.Hash(key))
- g := probeStart(hi, len(m.groups))
- for {
- matches := metaMatchH2(&m.ctrl[g], lo)
- for matches != 0 {
- s := nextMatch(&matches)
- if key == m.groups[g].keys[s] {
- ok = true
- // optimization: if |m.ctrl[g]| contains any empty
- // metadata bytes, we can physically delete |key|
- // rather than placing a tombstone.
- // The observation is that any probes into group |g|
- // would already be terminated by the existing empty
- // slot, and therefore reclaiming slot |s| will not
- // cause premature termination of probes into |g|.
- if metaMatchEmpty(&m.ctrl[g]) != 0 {
- m.ctrl[g][s] = empty
- m.resident--
- } else {
- m.ctrl[g][s] = tombstone
- m.dead++
- }
- var k K
- var v V
- m.groups[g].keys[s] = k
- m.groups[g].values[s] = v
- return
- }
- }
- // |key| is not in group |g|,
- // stop probing if we see an empty slot
- matches = metaMatchEmpty(&m.ctrl[g])
- if matches != 0 { // |key| absent
- ok = false
- return
- }
- g += 1 // linear probing
- if g >= uint32(len(m.groups)) {
- g = 0
- }
- }
-}
-
-// Iter iterates the elements of the Map, passing them to the callback.
-// It guarantees that any key in the Map will be visited only once, and
-// for un-mutated Maps, every key will be visited once. If the Map is
-// Mutated during iteration, mutations will be reflected on return from
-// Iter, but the set of keys visited by Iter is non-deterministic.
-func (m *Map[K, V]) Iter(cb func(k K, v V) (stop bool)) {
- // take a consistent view of the table in case
- // we rehash during iteration
- ctrl, groups := m.ctrl, m.groups
- // pick a random starting group
- g := randIntN(len(groups))
- for n := 0; n < len(groups); n++ {
- for s, c := range ctrl[g] {
- if c == empty || c == tombstone {
- continue
- }
- k, v := groups[g].keys[s], groups[g].values[s]
- if stop := cb(k, v); stop {
- return
- }
- }
- g++
- if g >= uint32(len(groups)) {
- g = 0
- }
- }
-}
-
-// Clear removes all elements from the Map.
-func (m *Map[K, V]) Clear() {
- for i, c := range m.ctrl {
- for j := range c {
- m.ctrl[i][j] = empty
- }
- }
- var k K
- var v V
- for i := range m.groups {
- g := &m.groups[i]
- for i := range g.keys {
- g.keys[i] = k
- g.values[i] = v
- }
- }
- m.resident, m.dead = 0, 0
-}
-
-// Count returns the number of elements in the Map.
-func (m *Map[K, V]) Count() int {
- return int(m.resident - m.dead)
-}
-
-// Capacity returns the number of additional elements
-// the can be added to the Map before resizing.
-func (m *Map[K, V]) Capacity() int {
- return int(m.limit - m.resident)
-}
-
-// find returns the location of |key| if present, or its insertion location if absent.
-// for performance, find is manually inlined into public methods.
-func (m *Map[K, V]) find(key K, hi h1, lo h2) (g, s uint32, ok bool) {
- g = probeStart(hi, len(m.groups))
- for {
- matches := metaMatchH2(&m.ctrl[g], lo)
- for matches != 0 {
- s = nextMatch(&matches)
- if key == m.groups[g].keys[s] {
- return g, s, true
- }
- }
- // |key| is not in group |g|,
- // stop probing if we see an empty slot
- matches = metaMatchEmpty(&m.ctrl[g])
- if matches != 0 {
- s = nextMatch(&matches)
- return g, s, false
- }
- g += 1 // linear probing
- if g >= uint32(len(m.groups)) {
- g = 0
- }
- }
-}
-
-func (m *Map[K, V]) nextSize() (n uint32) {
- n = uint32(len(m.groups)) * 2
- if m.dead >= (m.resident / 2) {
- n = uint32(len(m.groups))
- }
- return
-}
-
-func (m *Map[K, V]) rehash(n uint32) {
- groups, ctrl := m.groups, m.ctrl
- m.groups = make([]group[K, V], n)
- m.ctrl = make([]metadata, n)
- for i := range m.ctrl {
- m.ctrl[i] = newEmptyMetadata()
- }
- m.hash = maphash.NewSeed(m.hash)
- m.limit = n * maxAvgGroupLoad
- m.resident, m.dead = 0, 0
- for g := range ctrl {
- for s := range ctrl[g] {
- c := ctrl[g][s]
- if c == empty || c == tombstone {
- continue
- }
- m.Put(groups[g].keys[s], groups[g].values[s])
- }
- }
-}
-
-func (m *Map[K, V]) loadFactor() float32 {
- slots := float32(len(m.groups) * groupSize)
- return float32(m.resident-m.dead) / slots
-}
-
-// numGroups returns the minimum number of groups needed to store |n| elems.
-func numGroups(n uint32) (groups uint32) {
- groups = (n + maxAvgGroupLoad - 1) / maxAvgGroupLoad
- if groups == 0 {
- groups = 1
- }
- return
-}
-
-func newEmptyMetadata() (meta metadata) {
- for i := range meta {
- meta[i] = empty
- }
- return
-}
-
-func splitHash(h uint64) (h1, h2) {
- return h1((h & h1Mask) >> 7), h2(h & h2Mask)
-}
-
-func probeStart(hi h1, groups int) uint32 {
- return fastModN(uint32(hi), uint32(groups))
-}
-
-// lemire.me/blog/2016/06/27/a-fast-alternative-to-the-modulo-reduction/
-func fastModN(x, n uint32) uint32 {
- return uint32((uint64(x) * uint64(n)) >> 32)
-}
-
-// randIntN returns a random number in the interval [0, n).
-func randIntN(n int) uint32 {
- return fastModN(fastrand(), uint32(n))
-}
diff --git a/vendor/github.com/dolthub/swiss/simd/match.s b/vendor/github.com/dolthub/swiss/simd/match.s
deleted file mode 100644
index 4ae29e77b..000000000
--- a/vendor/github.com/dolthub/swiss/simd/match.s
+++ /dev/null
@@ -1,19 +0,0 @@
-// Code generated by command: go run asm.go -out match.s -stubs match_amd64.go. DO NOT EDIT.
-
-//go:build amd64
-
-#include "textflag.h"
-
-// func MatchMetadata(metadata *[16]int8, hash int8) uint16
-// Requires: SSE2, SSSE3
-TEXT ·MatchMetadata(SB), NOSPLIT, $0-18
- MOVQ metadata+0(FP), AX
- MOVBLSX hash+8(FP), CX
- MOVD CX, X0
- PXOR X1, X1
- PSHUFB X1, X0
- MOVOU (AX), X1
- PCMPEQB X1, X0
- PMOVMSKB X0, AX
- MOVW AX, ret+16(FP)
- RET
diff --git a/vendor/github.com/dolthub/swiss/simd/match_amd64.go b/vendor/github.com/dolthub/swiss/simd/match_amd64.go
deleted file mode 100644
index 538c8e124..000000000
--- a/vendor/github.com/dolthub/swiss/simd/match_amd64.go
+++ /dev/null
@@ -1,9 +0,0 @@
-// Code generated by command: go run asm.go -out match.s -stubs match_amd64.go. DO NOT EDIT.
-
-//go:build amd64
-
-package simd
-
-// MatchMetadata performs a 16-way probe of |metadata| using SSE instructions
-// nb: |metadata| must be an aligned pointer
-func MatchMetadata(metadata *[16]int8, hash int8) uint16
diff --git a/vendor/modules.txt b/vendor/modules.txt
index 09850008c..d68be6db7 100644
--- a/vendor/modules.txt
+++ b/vendor/modules.txt
@@ -52,7 +52,7 @@ codeberg.org/gruf/go-maps
# codeberg.org/gruf/go-mempool v0.0.0-20240507125005-cef10d64a760
## explicit; go 1.22.2
codeberg.org/gruf/go-mempool
-# codeberg.org/gruf/go-mutexes v1.5.0
+# codeberg.org/gruf/go-mutexes v1.5.1
## explicit; go 1.22.2
codeberg.org/gruf/go-mutexes
# codeberg.org/gruf/go-runners v1.6.2
@@ -179,13 +179,6 @@ github.com/disintegration/imaging
# github.com/docker/go-units v0.5.0
## explicit
github.com/docker/go-units
-# github.com/dolthub/maphash v0.1.0
-## explicit; go 1.18
-github.com/dolthub/maphash
-# github.com/dolthub/swiss v0.2.1
-## explicit; go 1.18
-github.com/dolthub/swiss
-github.com/dolthub/swiss/simd
# github.com/dsoprea/go-exif/v3 v3.0.0-20210625224831-a6301f85c82b
## explicit; go 1.12
github.com/dsoprea/go-exif/v3