diff options
author | 2024-05-22 09:46:24 +0000 | |
---|---|---|
committer | 2024-05-22 11:46:24 +0200 | |
commit | 3d3e99ae52ff8895b840cbced2e55b5f849fd4be (patch) | |
tree | c646d5eb99368028a2fbdafbe2c4400059d8eed5 /vendor/github.com/cornelk/hashmap | |
parent | --- (#2923) (diff) | |
download | gotosocial-3d3e99ae52ff8895b840cbced2e55b5f849fd4be.tar.xz |
[performance] update storage backend and make use of seek syscall when available (#2924)
* update to use go-storage/ instead of go-store/v2/storage/
* pull in latest version from codeberg
* remove test output :innocent:
* add code comments
* set the exclusive bit when creating new files in disk config
* bump to actual release version
* bump to v0.1.1 (tis a simple no-logic change)
* update readme
* only use a temporary read seeker when decoding video if required (should only be S3 now)
* use fastcopy library to use memory pooled buffers when calling TempFileSeeker()
* update to use seek call in serveFileRange()
Diffstat (limited to 'vendor/github.com/cornelk/hashmap')
-rw-r--r-- | vendor/github.com/cornelk/hashmap/.codecov.yml | 6 | ||||
-rw-r--r-- | vendor/github.com/cornelk/hashmap/.gitignore | 14 | ||||
-rw-r--r-- | vendor/github.com/cornelk/hashmap/.golangci.yml | 68 | ||||
-rw-r--r-- | vendor/github.com/cornelk/hashmap/LICENSE | 201 | ||||
-rw-r--r-- | vendor/github.com/cornelk/hashmap/Makefile | 25 | ||||
-rw-r--r-- | vendor/github.com/cornelk/hashmap/README.md | 88 | ||||
-rw-r--r-- | vendor/github.com/cornelk/hashmap/defines.go | 12 | ||||
-rw-r--r-- | vendor/github.com/cornelk/hashmap/hashmap.go | 348 | ||||
-rw-r--r-- | vendor/github.com/cornelk/hashmap/list.go | 127 | ||||
-rw-r--r-- | vendor/github.com/cornelk/hashmap/list_element.go | 47 | ||||
-rw-r--r-- | vendor/github.com/cornelk/hashmap/store.go | 45 | ||||
-rw-r--r-- | vendor/github.com/cornelk/hashmap/util.go | 32 | ||||
-rw-r--r-- | vendor/github.com/cornelk/hashmap/util_hash.go | 258 |
13 files changed, 0 insertions, 1271 deletions
diff --git a/vendor/github.com/cornelk/hashmap/.codecov.yml b/vendor/github.com/cornelk/hashmap/.codecov.yml deleted file mode 100644 index b9ca27e34..000000000 --- a/vendor/github.com/cornelk/hashmap/.codecov.yml +++ /dev/null @@ -1,6 +0,0 @@ -coverage: - status: - project: - default: - target: 70% - threshold: 5% diff --git a/vendor/github.com/cornelk/hashmap/.gitignore b/vendor/github.com/cornelk/hashmap/.gitignore deleted file mode 100644 index 38ecb5dc2..000000000 --- a/vendor/github.com/cornelk/hashmap/.gitignore +++ /dev/null @@ -1,14 +0,0 @@ -*.exe -.idea -.vscode -*.iml -*.local -/*.log -*.out -*.prof -*.test -.DS_Store -*.dmp -*.db - -.testCoverage diff --git a/vendor/github.com/cornelk/hashmap/.golangci.yml b/vendor/github.com/cornelk/hashmap/.golangci.yml deleted file mode 100644 index 0c29842d6..000000000 --- a/vendor/github.com/cornelk/hashmap/.golangci.yml +++ /dev/null @@ -1,68 +0,0 @@ -run: - deadline: 5m - -linters: - enable: - - asasalint # check for pass []any as any in variadic func(...any) - - asciicheck # Simple linter to check that your code does not contain non-ASCII identifiers - - bidichk # Checks for dangerous unicode character sequences - - containedctx # detects struct contained context.Context field - - contextcheck # check the function whether use a non-inherited context - - cyclop # checks function and package cyclomatic complexity - - decorder # check declaration order and count of types, constants, variables and functions - - depguard # Go linter that checks if package imports are in a list of acceptable packages - - dogsled # Checks assignments with too many blank identifiers (e.g. x, _, _, _, := f()) - - durationcheck # check for two durations multiplied together - - errcheck # checking for unchecked errors - - errname # Checks that errors are prefixed with the `Err` and error types are suffixed with the `Error` - - errorlint # finds code that will cause problems with the error wrapping scheme introduced in Go 1.13 - - exportloopref # checks for pointers to enclosing loop variables - - funlen # Tool for detection of long functions - - gci # controls golang package import order and makes it always deterministic - - gocognit # Computes and checks the cognitive complexity of functions - - gocritic # Provides diagnostics that check for bugs, performance and style issues - - gocyclo # Computes and checks the cyclomatic complexity of functions - - godot # Check if comments end in a period - - goerr113 # Golang linter to check the errors handling expressions - - gosimple # Linter for Go source code that specializes in simplifying a code - - govet # reports suspicious constructs, such as Printf calls with wrong arguments - - ineffassign # Detects when assignments to existing variables are not used - - maintidx # measures the maintainability index of each function - - makezero # Finds slice declarations with non-zero initial length - - misspell # Finds commonly misspelled English words in comments - - nakedret # Finds naked returns in functions - - nestif # Reports deeply nested if statements - - nilerr # Finds the code that returns nil even if it checks that the error is not nil - - nilnil # Checks that there is no simultaneous return of `nil` error and an invalid value - - prealloc # Finds slice declarations that could potentially be preallocated - - predeclared # find code that shadows one of Go's predeclared identifiers - - revive # drop-in replacement of golint - - staticcheck # drop-in replacement of go vet - - stylecheck # Stylecheck is a replacement for golint - - tenv # detects using os.Setenv instead of t.Setenv - - thelper # checks the consistency of test helpers - - tparallel # detects inappropriate usage of t.Parallel() - - typecheck # parses and type-checks Go code - - unconvert # Remove unnecessary type conversions - - unparam # Reports unused function parameters - - unused # Checks Go code for unused constants, variables, functions and types - - usestdlibvars # detect the possibility to use variables/constants from the Go standard library - - wastedassign # finds wasted assignment statements - - whitespace # detects leading and trailing whitespace - -linters-settings: - cyclop: - max-complexity: 15 - gocritic: - disabled-checks: - - newDeref - govet: - disable: - - unsafeptr - -issues: - exclude-use-default: false - exclude-rules: - - linters: - - goerr113 - text: "do not define dynamic errors" diff --git a/vendor/github.com/cornelk/hashmap/LICENSE b/vendor/github.com/cornelk/hashmap/LICENSE deleted file mode 100644 index e034cdf25..000000000 --- a/vendor/github.com/cornelk/hashmap/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 cornelk - - 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/cornelk/hashmap/Makefile b/vendor/github.com/cornelk/hashmap/Makefile deleted file mode 100644 index 9bab5c4dd..000000000 --- a/vendor/github.com/cornelk/hashmap/Makefile +++ /dev/null @@ -1,25 +0,0 @@ -help: ## show help, shown by default if no target is specified - @grep -E '^[0-9a-zA-Z_-]+:.*?## .*$$' $(MAKEFILE_LIST) | sort | awk 'BEGIN {FS = ":.*?## "}; {printf "\033[36m%-30s\033[0m %s\n", $$1, $$2}' - -lint: ## run code linters - golangci-lint run - -benchmark: ## run benchmarks - cd benchmarks && perflock go test -cpu 8 -run=^# -bench=. - -benchmark-perflock: ## run benchmarks using perflock - https://github.com/aclements/perflock - cd benchmarks && perflock -governor 80% go test -count 3 -cpu 8 -run=^# -bench=. - -test: ## run tests - go test -race ./... - GOARCH=386 go test ./... - -test-coverage: ## run unit tests and create test coverage - go test ./... -coverprofile .testCoverage -covermode=atomic -coverpkg=./... - -test-coverage-web: test-coverage ## run unit tests and show test coverage in browser - go tool cover -func .testCoverage | grep total | awk '{print "Total coverage: "$$3}' - go tool cover -html=.testCoverage - -install-linters: ## install all used linters - curl -sSfL https://raw.githubusercontent.com/golangci/golangci-lint/master/install.sh | sh -s -- -b $$(go env GOPATH)/bin v1.49.0 diff --git a/vendor/github.com/cornelk/hashmap/README.md b/vendor/github.com/cornelk/hashmap/README.md deleted file mode 100644 index 955eb5816..000000000 --- a/vendor/github.com/cornelk/hashmap/README.md +++ /dev/null @@ -1,88 +0,0 @@ -# hashmap - -[](https://github.com/cornelk/hashmap/actions) -[](https://pkg.go.dev/github.com/cornelk/hashmap) -[](https://goreportcard.com/report/github.com/cornelk/hashmap) -[](https://codecov.io/gh/cornelk/hashmap) - -## Overview - -A Golang lock-free thread-safe HashMap optimized for fastest read access. - -It is not a general-use HashMap and currently has slow write performance for write heavy uses. - -The minimal supported Golang version is 1.19 as it makes use of Generics and the new atomic package helpers. - -## Usage - -Example uint8 key map uses: - -``` -m := New[uint8, int]() -m.Set(1, 123) -value, ok := m.Get(1) -``` - -Example string key map uses: - -``` -m := New[string, int]() -m.Set("amount", 123) -value, ok := m.Get("amount") -``` - -Using the map to count URL requests: -``` -m := New[string, *int64]() -var i int64 -counter, _ := m.GetOrInsert("api/123", &i) -atomic.AddInt64(counter, 1) // increase counter -... -count := atomic.LoadInt64(counter) // read counter -``` - -## Benchmarks - -Reading from the hash map for numeric key types in a thread-safe way is faster than reading from a standard Golang map -in an unsafe way and four times faster than Golang's `sync.Map`: - -``` -BenchmarkReadHashMapUint-8 1774460 677.3 ns/op -BenchmarkReadHaxMapUint-8 1758708 679.0 ns/op -BenchmarkReadGoMapUintUnsafe-8 1497732 790.9 ns/op -BenchmarkReadGoMapUintMutex-8 41562 28672 ns/op -BenchmarkReadGoSyncMapUint-8 454401 2646 ns/op -``` - -Reading from the map while writes are happening: -``` -BenchmarkReadHashMapWithWritesUint-8 1388560 859.1 ns/op -BenchmarkReadHaxMapWithWritesUint-8 1306671 914.5 ns/op -BenchmarkReadGoSyncMapWithWritesUint-8 335732 3113 ns/op -``` - -Write performance without any concurrent reads: - -``` -BenchmarkWriteHashMapUint-8 54756 21977 ns/op -BenchmarkWriteGoMapMutexUint-8 83907 14827 ns/op -BenchmarkWriteGoSyncMapUint-8 16983 70305 ns/op -``` - -The benchmarks were run with Golang 1.19.0 on Linux and AMD64 using `make benchmark`. - -## Technical details - -* Technical design decisions have been made based on benchmarks that are stored in an external repository: - [go-benchmark](https://github.com/cornelk/go-benchmark) - -* The library uses a sorted linked list and a slice as an index into that list. - -* The Get() function contains helper functions that have been inlined manually until the Golang compiler will inline them automatically. - -* It optimizes the slice access by circumventing the Golang size check when reading from the slice. - Once a slice is allocated, the size of it does not change. - The library limits the index into the slice, therefore the Golang size check is obsolete. - When the slice reaches a defined fill rate, a bigger slice is allocated and all keys are recalculated and transferred into the new slice. - -* For hashing, specialized xxhash implementations are used that match the size of the key type where available diff --git a/vendor/github.com/cornelk/hashmap/defines.go b/vendor/github.com/cornelk/hashmap/defines.go deleted file mode 100644 index 75f0e9eb3..000000000 --- a/vendor/github.com/cornelk/hashmap/defines.go +++ /dev/null @@ -1,12 +0,0 @@ -package hashmap - -// defaultSize is the default size for a map. -const defaultSize = 8 - -// maxFillRate is the maximum fill rate for the slice before a resize will happen. -const maxFillRate = 50 - -// support all numeric and string types and aliases of those. -type hashable interface { - ~int | ~int8 | ~int16 | ~int32 | ~int64 | ~uint | ~uint8 | ~uint16 | ~uint32 | ~uint64 | ~uintptr | ~float32 | ~float64 | ~string -} diff --git a/vendor/github.com/cornelk/hashmap/hashmap.go b/vendor/github.com/cornelk/hashmap/hashmap.go deleted file mode 100644 index dbceb52b7..000000000 --- a/vendor/github.com/cornelk/hashmap/hashmap.go +++ /dev/null @@ -1,348 +0,0 @@ -// Package hashmap provides a lock-free and thread-safe HashMap. -package hashmap - -import ( - "bytes" - "fmt" - "reflect" - "strconv" - "sync/atomic" - "unsafe" -) - -// Map implements a read optimized hash map. -type Map[Key hashable, Value any] struct { - hasher func(Key) uintptr - store atomic.Pointer[store[Key, Value]] // pointer to a map instance that gets replaced if the map resizes - linkedList *List[Key, Value] // key sorted linked list of elements - // resizing marks a resizing operation in progress. - // this is using uintptr instead of atomic.Bool to avoid using 32 bit int on 64 bit systems - resizing atomic.Uintptr -} - -// New returns a new map instance. -func New[Key hashable, Value any]() *Map[Key, Value] { - return NewSized[Key, Value](defaultSize) -} - -// NewSized returns a new map instance with a specific initialization size. -func NewSized[Key hashable, Value any](size uintptr) *Map[Key, Value] { - m := &Map[Key, Value]{} - m.allocate(size) - m.setDefaultHasher() - return m -} - -// SetHasher sets a custom hasher. -func (m *Map[Key, Value]) SetHasher(hasher func(Key) uintptr) { - m.hasher = hasher -} - -// Len returns the number of elements within the map. -func (m *Map[Key, Value]) Len() int { - return m.linkedList.Len() -} - -// Get retrieves an element from the map under given hash key. -func (m *Map[Key, Value]) Get(key Key) (Value, bool) { - hash := m.hasher(key) - - for element := m.store.Load().item(hash); element != nil; element = element.Next() { - if element.keyHash == hash && element.key == key { - return element.Value(), true - } - - if element.keyHash > hash { - return *new(Value), false - } - } - return *new(Value), false -} - -// GetOrInsert returns the existing value for the key if present. -// Otherwise, it stores and returns the given value. -// The returned bool is true if the value was loaded, false if stored. -func (m *Map[Key, Value]) GetOrInsert(key Key, value Value) (Value, bool) { - hash := m.hasher(key) - var newElement *ListElement[Key, Value] - - for { - for element := m.store.Load().item(hash); element != nil; element = element.Next() { - if element.keyHash == hash && element.key == key { - actual := element.Value() - return actual, true - } - - if element.keyHash > hash { - break - } - } - - if newElement == nil { // allocate only once - newElement = &ListElement[Key, Value]{ - key: key, - keyHash: hash, - } - newElement.value.Store(&value) - } - - if m.insertElement(newElement, hash, key, value) { - return value, false - } - } -} - -// FillRate returns the fill rate of the map as a percentage integer. -func (m *Map[Key, Value]) FillRate() int { - store := m.store.Load() - count := int(store.count.Load()) - l := len(store.index) - return (count * 100) / l -} - -// Del deletes the key from the map and returns whether the key was deleted. -func (m *Map[Key, Value]) Del(key Key) bool { - hash := m.hasher(key) - store := m.store.Load() - element := store.item(hash) - - for ; element != nil; element = element.Next() { - if element.keyHash == hash && element.key == key { - m.deleteElement(element) - m.linkedList.Delete(element) - return true - } - - if element.keyHash > hash { - return false - } - } - return false -} - -// Insert sets the value under the specified key to the map if it does not exist yet. -// If a resizing operation is happening concurrently while calling Insert, the item might show up in the map -// after the resize operation is finished. -// Returns true if the item was inserted or false if it existed. -func (m *Map[Key, Value]) Insert(key Key, value Value) bool { - hash := m.hasher(key) - var ( - existed, inserted bool - element *ListElement[Key, Value] - ) - - for { - store := m.store.Load() - searchStart := store.item(hash) - - if !inserted { // if retrying after insert during grow, do not add to list again - element, existed, inserted = m.linkedList.Add(searchStart, hash, key, value) - if existed { - return false - } - if !inserted { - continue // a concurrent add did interfere, try again - } - } - - count := store.addItem(element) - currentStore := m.store.Load() - if store != currentStore { // retry insert in case of insert during grow - continue - } - - if m.isResizeNeeded(store, count) && m.resizing.CompareAndSwap(0, 1) { - go m.grow(0, true) - } - return true - } -} - -// Set sets the value under the specified key to the map. An existing item for this key will be overwritten. -// If a resizing operation is happening concurrently while calling Set, the item might show up in the map -// after the resize operation is finished. -func (m *Map[Key, Value]) Set(key Key, value Value) { - hash := m.hasher(key) - - for { - store := m.store.Load() - searchStart := store.item(hash) - - element, added := m.linkedList.AddOrUpdate(searchStart, hash, key, value) - if !added { - continue // a concurrent add did interfere, try again - } - - count := store.addItem(element) - currentStore := m.store.Load() - if store != currentStore { // retry insert in case of insert during grow - continue - } - - if m.isResizeNeeded(store, count) && m.resizing.CompareAndSwap(0, 1) { - go m.grow(0, true) - } - return - } -} - -// Grow resizes the map to a new size, the size gets rounded up to next power of 2. -// To double the size of the map use newSize 0. -// This function returns immediately, the resize operation is done in a goroutine. -// No resizing is done in case of another resize operation already being in progress. -func (m *Map[Key, Value]) Grow(newSize uintptr) { - if m.resizing.CompareAndSwap(0, 1) { - go m.grow(newSize, true) - } -} - -// String returns the map as a string, only hashed keys are printed. -func (m *Map[Key, Value]) String() string { - buffer := bytes.NewBufferString("") - buffer.WriteRune('[') - - first := m.linkedList.First() - item := first - - for item != nil { - if item != first { - buffer.WriteRune(',') - } - fmt.Fprint(buffer, item.keyHash) - item = item.Next() - } - buffer.WriteRune(']') - return buffer.String() -} - -// Range calls f sequentially for each key and value present in the map. -// If f returns false, range stops the iteration. -func (m *Map[Key, Value]) Range(f func(Key, Value) bool) { - item := m.linkedList.First() - - for item != nil { - value := item.Value() - if !f(item.key, value) { - return - } - item = item.Next() - } -} - -func (m *Map[Key, Value]) allocate(newSize uintptr) { - m.linkedList = NewList[Key, Value]() - if m.resizing.CompareAndSwap(0, 1) { - m.grow(newSize, false) - } -} - -func (m *Map[Key, Value]) isResizeNeeded(store *store[Key, Value], count uintptr) bool { - l := uintptr(len(store.index)) // l can't be 0 as it gets initialized in New() - fillRate := (count * 100) / l - return fillRate > maxFillRate -} - -func (m *Map[Key, Value]) insertElement(element *ListElement[Key, Value], hash uintptr, key Key, value Value) bool { - var existed, inserted bool - - for { - store := m.store.Load() - searchStart := store.item(element.keyHash) - - if !inserted { // if retrying after insert during grow, do not add to list again - _, existed, inserted = m.linkedList.Add(searchStart, hash, key, value) - if existed { - return false - } - - if !inserted { - continue // a concurrent add did interfere, try again - } - } - - count := store.addItem(element) - currentStore := m.store.Load() - if store != currentStore { // retry insert in case of insert during grow - continue - } - - if m.isResizeNeeded(store, count) && m.resizing.CompareAndSwap(0, 1) { - go m.grow(0, true) - } - return true - } -} - -// deleteElement deletes an element from index. -func (m *Map[Key, Value]) deleteElement(element *ListElement[Key, Value]) { - for { - store := m.store.Load() - index := element.keyHash >> store.keyShifts - ptr := (*unsafe.Pointer)(unsafe.Pointer(uintptr(store.array) + index*intSizeBytes)) - - next := element.Next() - if next != nil && element.keyHash>>store.keyShifts != index { - next = nil // do not set index to next item if it's not the same slice index - } - atomic.CompareAndSwapPointer(ptr, unsafe.Pointer(element), unsafe.Pointer(next)) - - currentStore := m.store.Load() - if store == currentStore { // check that no resize happened - break - } - } -} - -func (m *Map[Key, Value]) grow(newSize uintptr, loop bool) { - defer m.resizing.CompareAndSwap(1, 0) - - for { - currentStore := m.store.Load() - if newSize == 0 { - newSize = uintptr(len(currentStore.index)) << 1 - } else { - newSize = roundUpPower2(newSize) - } - - index := make([]*ListElement[Key, Value], newSize) - header := (*reflect.SliceHeader)(unsafe.Pointer(&index)) - - newStore := &store[Key, Value]{ - keyShifts: strconv.IntSize - log2(newSize), - array: unsafe.Pointer(header.Data), // use address of slice data storage - index: index, - } - - m.fillIndexItems(newStore) // initialize new index slice with longer keys - - m.store.Store(newStore) - - m.fillIndexItems(newStore) // make sure that the new index is up-to-date with the current state of the linked list - - if !loop { - return - } - - // check if a new resize needs to be done already - count := uintptr(m.Len()) - if !m.isResizeNeeded(newStore, count) { - return - } - newSize = 0 // 0 means double the current size - } -} - -func (m *Map[Key, Value]) fillIndexItems(store *store[Key, Value]) { - first := m.linkedList.First() - item := first - lastIndex := uintptr(0) - - for item != nil { - index := item.keyHash >> store.keyShifts - if item == first || index != lastIndex { // store item with smallest hash key for every index - store.addItem(item) - lastIndex = index - } - item = item.Next() - } -} diff --git a/vendor/github.com/cornelk/hashmap/list.go b/vendor/github.com/cornelk/hashmap/list.go deleted file mode 100644 index 596b2cf26..000000000 --- a/vendor/github.com/cornelk/hashmap/list.go +++ /dev/null @@ -1,127 +0,0 @@ -package hashmap - -import ( - "sync/atomic" -) - -// List is a sorted linked list. -type List[Key comparable, Value any] struct { - count atomic.Uintptr - head *ListElement[Key, Value] -} - -// NewList returns an initialized list. -func NewList[Key comparable, Value any]() *List[Key, Value] { - return &List[Key, Value]{ - head: &ListElement[Key, Value]{}, - } -} - -// Len returns the number of elements within the list. -func (l *List[Key, Value]) Len() int { - return int(l.count.Load()) -} - -// First returns the first item of the list. -func (l *List[Key, Value]) First() *ListElement[Key, Value] { - return l.head.Next() -} - -// Add adds an item to the list and returns false if an item for the hash existed. -// searchStart = nil will start to search at the head item. -func (l *List[Key, Value]) Add(searchStart *ListElement[Key, Value], hash uintptr, key Key, value Value) (element *ListElement[Key, Value], existed bool, inserted bool) { - left, found, right := l.search(searchStart, hash, key) - if found != nil { // existing item found - return found, true, false - } - - element = &ListElement[Key, Value]{ - key: key, - keyHash: hash, - } - element.value.Store(&value) - return element, false, l.insertAt(element, left, right) -} - -// AddOrUpdate adds or updates an item to the list. -func (l *List[Key, Value]) AddOrUpdate(searchStart *ListElement[Key, Value], hash uintptr, key Key, value Value) (*ListElement[Key, Value], bool) { - left, found, right := l.search(searchStart, hash, key) - if found != nil { // existing item found - found.value.Store(&value) // update the value - return found, true - } - - element := &ListElement[Key, Value]{ - key: key, - keyHash: hash, - } - element.value.Store(&value) - return element, l.insertAt(element, left, right) -} - -// Delete deletes an element from the list. -func (l *List[Key, Value]) Delete(element *ListElement[Key, Value]) { - if !element.deleted.CompareAndSwap(0, 1) { - return // concurrent delete of the item is in progress - } - - right := element.Next() - // point head to next element if element to delete was head - l.head.next.CompareAndSwap(element, right) - - // element left from the deleted element will replace its next - // pointer to the next valid element on call of Next(). - - l.count.Add(^uintptr(0)) // decrease counter -} - -func (l *List[Key, Value]) search(searchStart *ListElement[Key, Value], hash uintptr, key Key) (left, found, right *ListElement[Key, Value]) { - if searchStart != nil && hash < searchStart.keyHash { // key would remain left from item? { - searchStart = nil // start search at head - } - - if searchStart == nil { // start search at head? - left = l.head - found = left.Next() - if found == nil { // no items beside head? - return nil, nil, nil - } - } else { - found = searchStart - } - - for { - if hash == found.keyHash && key == found.key { // key hash already exists, compare keys - return nil, found, nil - } - - if hash < found.keyHash { // new item needs to be inserted before the found value - if l.head == left { - return nil, nil, found - } - return left, nil, found - } - - // go to next element in sorted linked list - left = found - found = left.Next() - if found == nil { // no more items on the right - return left, nil, nil - } - } -} - -func (l *List[Key, Value]) insertAt(element, left, right *ListElement[Key, Value]) bool { - if left == nil { - left = l.head - } - - element.next.Store(right) - - if !left.next.CompareAndSwap(right, element) { - return false // item was modified concurrently - } - - l.count.Add(1) - return true -} diff --git a/vendor/github.com/cornelk/hashmap/list_element.go b/vendor/github.com/cornelk/hashmap/list_element.go deleted file mode 100644 index 1be64b0ac..000000000 --- a/vendor/github.com/cornelk/hashmap/list_element.go +++ /dev/null @@ -1,47 +0,0 @@ -package hashmap - -import ( - "sync/atomic" -) - -// ListElement is an element of a list. -type ListElement[Key comparable, Value any] struct { - keyHash uintptr - - // deleted marks the item as deleting or deleted - // this is using uintptr instead of atomic.Bool to avoid using 32 bit int on 64 bit systems - deleted atomic.Uintptr - - // next points to the next element in the list. - // it is nil for the last item in the list. - next atomic.Pointer[ListElement[Key, Value]] - - value atomic.Pointer[Value] - - key Key -} - -// Value returns the value of the list item. -func (e *ListElement[Key, Value]) Value() Value { - return *e.value.Load() -} - -// Next returns the item on the right. -func (e *ListElement[Key, Value]) Next() *ListElement[Key, Value] { - for next := e.next.Load(); next != nil; { - // if the next item is not deleted, return it - if next.deleted.Load() == 0 { - return next - } - - // point current elements next to the following item - // after the deleted one until a non deleted or list end is found - following := next.Next() - if e.next.CompareAndSwap(next, following) { - next = following - } else { - next = next.Next() - } - } - return nil // end of the list reached -} diff --git a/vendor/github.com/cornelk/hashmap/store.go b/vendor/github.com/cornelk/hashmap/store.go deleted file mode 100644 index 8fc1d5986..000000000 --- a/vendor/github.com/cornelk/hashmap/store.go +++ /dev/null @@ -1,45 +0,0 @@ -package hashmap - -import ( - "sync/atomic" - "unsafe" -) - -type store[Key comparable, Value any] struct { - keyShifts uintptr // Pointer size - log2 of array size, to be used as index in the data array - count atomic.Uintptr // count of filled elements in the slice - array unsafe.Pointer // pointer to slice data array - index []*ListElement[Key, Value] // storage for the slice for the garbage collector to not clean it up -} - -// item returns the item for the given hashed key. -func (s *store[Key, Value]) item(hashedKey uintptr) *ListElement[Key, Value] { - index := hashedKey >> s.keyShifts - ptr := (*unsafe.Pointer)(unsafe.Pointer(uintptr(s.array) + index*intSizeBytes)) - item := (*ListElement[Key, Value])(atomic.LoadPointer(ptr)) - return item -} - -// adds an item to the index if needed and returns the new item counter if it changed, otherwise 0. -func (s *store[Key, Value]) addItem(item *ListElement[Key, Value]) uintptr { - index := item.keyHash >> s.keyShifts - ptr := (*unsafe.Pointer)(unsafe.Pointer(uintptr(s.array) + index*intSizeBytes)) - - for { // loop until the smallest key hash is in the index - element := (*ListElement[Key, Value])(atomic.LoadPointer(ptr)) // get the current item in the index - if element == nil { // no item yet at this index - if atomic.CompareAndSwapPointer(ptr, nil, unsafe.Pointer(item)) { - return s.count.Add(1) - } - continue // a new item was inserted concurrently, retry - } - - if item.keyHash < element.keyHash { - // the new item is the smallest for this index? - if !atomic.CompareAndSwapPointer(ptr, unsafe.Pointer(element), unsafe.Pointer(item)) { - continue // a new item was inserted concurrently, retry - } - } - return 0 - } -} diff --git a/vendor/github.com/cornelk/hashmap/util.go b/vendor/github.com/cornelk/hashmap/util.go deleted file mode 100644 index 4ef40e224..000000000 --- a/vendor/github.com/cornelk/hashmap/util.go +++ /dev/null @@ -1,32 +0,0 @@ -package hashmap - -import ( - "strconv" -) - -const ( - // intSizeBytes is the size in byte of an int or uint value. - intSizeBytes = strconv.IntSize >> 3 -) - -// roundUpPower2 rounds a number to the next power of 2. -func roundUpPower2(i uintptr) uintptr { - i-- - i |= i >> 1 - i |= i >> 2 - i |= i >> 4 - i |= i >> 8 - i |= i >> 16 - i |= i >> 32 - i++ - return i -} - -// log2 computes the binary logarithm of x, rounded up to the next integer. -func log2(i uintptr) uintptr { - var n, p uintptr - for p = 1; p < i; p += p { - n++ - } - return n -} diff --git a/vendor/github.com/cornelk/hashmap/util_hash.go b/vendor/github.com/cornelk/hashmap/util_hash.go deleted file mode 100644 index 5cd233ed7..000000000 --- a/vendor/github.com/cornelk/hashmap/util_hash.go +++ /dev/null @@ -1,258 +0,0 @@ -package hashmap - -import ( - "encoding/binary" - "fmt" - "math/bits" - "reflect" - "unsafe" -) - -const ( - prime1 uint64 = 11400714785074694791 - prime2 uint64 = 14029467366897019727 - prime3 uint64 = 1609587929392839161 - prime4 uint64 = 9650029242287828579 - prime5 uint64 = 2870177450012600261 -) - -var prime1v = prime1 - -/* -Copyright (c) 2016 Caleb Spare - -MIT License - -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. -*/ - -// setDefaultHasher sets the default hasher depending on the key type. -// Inlines hashing as anonymous functions for performance improvements, other options like -// returning an anonymous functions from another function turned out to not be as performant. -func (m *Map[Key, Value]) setDefaultHasher() { - var key Key - kind := reflect.ValueOf(&key).Elem().Type().Kind() - - switch kind { - case reflect.Int, reflect.Uint, reflect.Uintptr: - switch intSizeBytes { - case 2: - m.hasher = *(*func(Key) uintptr)(unsafe.Pointer(&xxHashWord)) - case 4: - m.hasher = *(*func(Key) uintptr)(unsafe.Pointer(&xxHashDword)) - case 8: - m.hasher = *(*func(Key) uintptr)(unsafe.Pointer(&xxHashQword)) - - default: - panic(fmt.Errorf("unsupported integer byte size %d", intSizeBytes)) - } - - case reflect.Int8, reflect.Uint8: - m.hasher = *(*func(Key) uintptr)(unsafe.Pointer(&xxHashByte)) - case reflect.Int16, reflect.Uint16: - m.hasher = *(*func(Key) uintptr)(unsafe.Pointer(&xxHashWord)) - case reflect.Int32, reflect.Uint32: - m.hasher = *(*func(Key) uintptr)(unsafe.Pointer(&xxHashDword)) - case reflect.Int64, reflect.Uint64: - m.hasher = *(*func(Key) uintptr)(unsafe.Pointer(&xxHashQword)) - case reflect.Float32: - m.hasher = *(*func(Key) uintptr)(unsafe.Pointer(&xxHashFloat32)) - case reflect.Float64: - m.hasher = *(*func(Key) uintptr)(unsafe.Pointer(&xxHashFloat64)) - case reflect.String: - m.hasher = *(*func(Key) uintptr)(unsafe.Pointer(&xxHashString)) - - default: - panic(fmt.Errorf("unsupported key type %T of kind %v", key, kind)) - } -} - -// Specialized xxhash hash functions, optimized for the bit size of the key where available, -// for all supported types beside string. - -var xxHashByte = func(key uint8) uintptr { - h := prime5 + 1 - h ^= uint64(key) * prime5 - h = bits.RotateLeft64(h, 11) * prime1 - - h ^= h >> 33 - h *= prime2 - h ^= h >> 29 - h *= prime3 - h ^= h >> 32 - - return uintptr(h) -} - -var xxHashWord = func(key uint16) uintptr { - h := prime5 + 2 - h ^= (uint64(key) & 0xff) * prime5 - h = bits.RotateLeft64(h, 11) * prime1 - h ^= ((uint64(key) >> 8) & 0xff) * prime5 - h = bits.RotateLeft64(h, 11) * prime1 - - h ^= h >> 33 - h *= prime2 - h ^= h >> 29 - h *= prime3 - h ^= h >> 32 - - return uintptr(h) -} - -var xxHashDword = func(key uint32) uintptr { - h := prime5 + 4 - h ^= uint64(key) * prime1 - h = bits.RotateLeft64(h, 23)*prime2 + prime3 - - h ^= h >> 33 - h *= prime2 - h ^= h >> 29 - h *= prime3 - h ^= h >> 32 - - return uintptr(h) -} - -var xxHashFloat32 = func(key float32) uintptr { - h := prime5 + 4 - h ^= uint64(key) * prime1 - h = bits.RotateLeft64(h, 23)*prime2 + prime3 - - h ^= h >> 33 - h *= prime2 - h ^= h >> 29 - h *= prime3 - h ^= h >> 32 - - return uintptr(h) -} - -var xxHashFloat64 = func(key float64) uintptr { - h := prime5 + 4 - h ^= uint64(key) * prime1 - h = bits.RotateLeft64(h, 23)*prime2 + prime3 - - h ^= h >> 33 - h *= prime2 - h ^= h >> 29 - h *= prime3 - h ^= h >> 32 - - return uintptr(h) -} - -var xxHashQword = func(key uint64) uintptr { - k1 := key * prime2 - k1 = bits.RotateLeft64(k1, 31) - k1 *= prime1 - h := (prime5 + 8) ^ k1 - h = bits.RotateLeft64(h, 27)*prime1 + prime4 - - h ^= h >> 33 - h *= prime2 - h ^= h >> 29 - h *= prime3 - h ^= h >> 32 - - return uintptr(h) -} - -var xxHashString = func(key string) uintptr { - sh := (*reflect.StringHeader)(unsafe.Pointer(&key)) - bh := reflect.SliceHeader{ - Data: sh.Data, - Len: sh.Len, - Cap: sh.Len, // cap needs to be set, otherwise xxhash fails on ARM Macs - } - - b := *(*[]byte)(unsafe.Pointer(&bh)) - var h uint64 - - if sh.Len >= 32 { - v1 := prime1v + prime2 - v2 := prime2 - v3 := uint64(0) - v4 := -prime1v - for len(b) >= 32 { - v1 = round(v1, binary.LittleEndian.Uint64(b[0:8:len(b)])) - v2 = round(v2, binary.LittleEndian.Uint64(b[8:16:len(b)])) - v3 = round(v3, binary.LittleEndian.Uint64(b[16:24:len(b)])) - v4 = round(v4, binary.LittleEndian.Uint64(b[24:32:len(b)])) - b = b[32:len(b):len(b)] - } - h = rol1(v1) + rol7(v2) + rol12(v3) + rol18(v4) - h = mergeRound(h, v1) - h = mergeRound(h, v2) - h = mergeRound(h, v3) - h = mergeRound(h, v4) - } else { - h = prime5 - } - - h += uint64(sh.Len) - - i, end := 0, len(b) - for ; i+8 <= end; i += 8 { - k1 := round(0, binary.LittleEndian.Uint64(b[i:i+8:len(b)])) - h ^= k1 - h = rol27(h)*prime1 + prime4 - } - if i+4 <= end { - h ^= uint64(binary.LittleEndian.Uint32(b[i:i+4:len(b)])) * prime1 - h = rol23(h)*prime2 + prime3 - i += 4 - } - for ; i < end; i++ { - h ^= uint64(b[i]) * prime5 - h = rol11(h) * prime1 - } - - h ^= h >> 33 - h *= prime2 - h ^= h >> 29 - h *= prime3 - h ^= h >> 32 - - return uintptr(h) -} - -func round(acc, input uint64) uint64 { - acc += input * prime2 - acc = rol31(acc) - acc *= prime1 - return acc -} - -func mergeRound(acc, val uint64) uint64 { - val = round(0, val) - acc ^= val - acc = acc*prime1 + prime4 - return acc -} - -func rol1(x uint64) uint64 { return bits.RotateLeft64(x, 1) } -func rol7(x uint64) uint64 { return bits.RotateLeft64(x, 7) } -func rol11(x uint64) uint64 { return bits.RotateLeft64(x, 11) } -func rol12(x uint64) uint64 { return bits.RotateLeft64(x, 12) } -func rol18(x uint64) uint64 { return bits.RotateLeft64(x, 18) } -func rol23(x uint64) uint64 { return bits.RotateLeft64(x, 23) } -func rol27(x uint64) uint64 { return bits.RotateLeft64(x, 27) } -func rol31(x uint64) uint64 { return bits.RotateLeft64(x, 31) } |