README
¶
IndexMap
This is a fork from github.com/yah01/indexmap. So many thanks to yah01 from Shanghai.
Although the base from yah01 is working very well, it wasn't a full thread safe version.
The base version was extended by Harald Mueller.
A map (hash table) is often created with $ID \to Object$ to search for data (structured in tables). The map-type but is limited to search for data using only an ID. In order to search data using any field without a SQL database. The IndexMap data structure can achieve it
Installation
Get the IndexMap package:
go get -u "github.com/haraldLmueller/indexmap"
Import the IndexMap package:
import "github.com/haraldLmueller/indexmap"
Get Started
First, to create a IndexMap with primary index:
type Person struct {
ID int64
Name string
Age int
City string
Like []string
}
persons := indexmap.NewIndexMap(indexmap.NewPrimaryIndex(func(value *Person) int64 {
return value.ID
}))
Now, it works just like the common map type with the possibility of adding an index to search for a person using another field:
persons.AddIndex("name", indexmap.NewSecondaryIndex(func(value *Person) []any {
return []any{value.Name}
}))
It must provide a way to extract keys for the inserted objects, all keys must be comparable.
The insertion, updates all indexes automatically:
ashe := &Person{
ID: 1,
Name: "Ashe",
Age: 39,
City: "San Francisco",
Like: []string{"Bob", "Cassidy"},
}
bob := &Person{
ID: 2,
Name: "Bob",
Age: 18,
City: "San Francisco",
}
cassidy := &Person{
ID: 3,
Name: "Cassidy",
Age: 40,
City: "Shanghai",
Like: []string{"Ashe", "Bob"},
}
persons.Insert(ashe)
persons.Insert(bob)
persons.Insert(cassidy)
Adding index after inserting data also works:
persons.AddIndex("city", indexmap.NewSecondaryIndex(func(value *Person) []any {
return []any{value.City}
}))
// Like is a "contain" index
persons.AddIndex("like", indexmap.NewSecondaryIndex(func(value *Person) []any {
like := make([]any, 0, len(value.Like))
for i := range value.Like {
like = append(like, value.Like[i])
}
return like
}))
And search for data using the primary index or an added index:
fmt.Println("Search with ID or Name:")
fmt.Printf("%+v\n", persons.Get(ashe.ID))
fmt.Printf("%+v\n", persons.GetBy("name", ashe.Name))
fmt.Println("\nSearch persons come from San Francisco:")
for _, person := range persons.GetAllBy("city", "San Francisco") {
fmt.Printf("%+v\n", person)
}
fmt.Println("\nSearch persons like Bob")
for _, person := range persons.GetAllBy("like", "Bob") {
fmt.Printf("%+v\n", person)
}
which outputs:
Search with ID or Name:
&{ID:1 Name:Ashe Age:39 City:San Francisco Like:[Bob Cassidy]}
&{ID:1 Name:Ashe Age:39 City:San Francisco Like:[Bob Cassidy]}
Search persons come from San Francisco:
&{ID:1 Name:Ashe Age:39 City:San Francisco Like:[Bob Cassidy]}
&{ID:2 Name:Bob Age:18 City:San Francisco Like:[]}
Search persons like Bob
&{ID:3 Name:Cassidy Age:40 City:Shanghai Like:[Ashe Bob]}
&{ID:1 Name:Ashe Age:39 City:San Francisco Like:[Bob Cassidy]}
Document
Update Value
Inserting different values using the same key, works like the normal map type. The last one overwrites the value, but for an inserted value modifying it from the outside may confuse the index. It must modify an internal value using Update()/UpdateBy():
// DO NOT:
person := persons.GetBy("name", "Ashe")
person.City = "Shanghai"
persons.Insert(person)
// Modify the internal value with Update()/UpdateBy()
persons.UpdateBy("name", "Ashe", func(value *Person) (*Person, bool) {
if value.City == "Shanghai" {
return value, false
}
value.City = "Shanghai"
return value, true
})
Serialize & Deserialize
An IndexMap can be serialized to JSON, the result is the same as serializing a normal map type. It doesn't contain the index information, resulting in an unrecoverable map (indexes cannot be recovered):
// Serialize
imapData, err := json.Marshal(imap)
// Deserialize
// You have to create an IndexMap with primary index,
// it's acceptable to add secondary index after deserializing
imap := NewIndexMap(NewPrimaryIndex(func(value *Person) int64 {
return value.ID
}))
err := json.Unmarshal(imapData, &imap)
Iterate
As well as sync.Map, IndexMap can iterate using the Range() method:
imap.Range(func(key int64, value *Person) bool {
fmt.Printf("key=%v, value=%+v\n", key, value)
return true
})
Additionally, a useful method to get all keys and values:
keys, values := imap.Collect()
Performance
Let $n$ be the number of elements inserted, $m$ be the number of indexes:
| Operation | Complexity |
|---|---|
| Get | $O(1)$ |
| GetBy | $O(1)$ |
| Insert | $O(m)$ |
| Update | $O(m)$ |
| Remove | $O(m)$ |
| AddIndex | $O(n)$ |
The more indexes, the slower the write operations.
Benchmarks
Version 1.2.0
goos: linux
goarch: amd64
pkg: github.com/haraldLmueller/indexmap
cpu: Intel(R) Celeron(R) N4100 CPU @ 1.10GHz
BenchmarkInsertOnlyPrimaryInt-4 813411 1755 ns/op 151 B/op 3 allocs/op
BenchmarkParallelInsertOnlyPrimaryInt-4 984680 2012 ns/op 183 B/op 3 allocs/op
BenchmarkNativeMap-4 1000000 1675 ns/op 181 B/op 3 allocs/op
BenchmarkNativeSyncMap-4 792746 2461 ns/op 225 B/op 7 allocs/op
BenchmarkParallelNativeSyncMap-4 796434 2591 ns/op 227 B/op 7 allocs/op
BenchmarkUpdateNoIndexedValue-4 507723 2270 ns/op 129 B/op 8 allocs/op
BenchmarkUpdatePrimaryIndexedValue-4 549063 2111 ns/op 129 B/op 8 allocs/op
BenchmarkUpdateOneSecondaryIndexedValue-4 438856 2356 ns/op 129 B/op 8 allocs/op
BenchmarkUpdateTwoSecondaryIndexedValue-4 500124 2311 ns/op 129 B/op 8 allocs/op
BenchmarkUpdatePrimaryAndTwoSecondaryIndexedValue-4 547125 2197 ns/op 130 B/op 8 allocs/op
Documentation
¶
Index ¶
- type IndexMap
- func (imap *IndexMap[K, V]) AddIndex(indexName string, index *SecondaryIndex[V]) bool
- func (imap *IndexMap[K, V]) Clear()
- func (imap *IndexMap[K, V]) Collect() ([]K, []*V)
- func (imap *IndexMap[K, V]) CollectBy(indexName string) ([]any, [][]*V)
- func (imap *IndexMap[K, V]) CollectKeys() []K
- func (imap *IndexMap[K, V]) CollectValues() []*V
- func (imap *IndexMap[K, V]) CollectValuesOrdered() []*V
- func (imap *IndexMap[K, V]) Contain(key K) booldeprecated
- func (imap *IndexMap[K, V]) Contains(key K) bool
- func (imap *IndexMap[K, V]) Get(key K) *V
- func (imap *IndexMap[K, V]) GetAllBy(indexName string, key any) []*V
- func (imap *IndexMap[K, V]) GetBy(indexName string, key any) *V
- func (imap *IndexMap[K, V]) Insert(values ...*V)
- func (imap *IndexMap[K, V]) Len() int
- func (imap *IndexMap[K, V]) MarshalJSON() ([]byte, error)
- func (imap *IndexMap[K, V]) PrimaryKey(v *V) K
- func (imap *IndexMap[K, V]) Range(fn func(key K, value *V) bool)
- func (imap *IndexMap[K, V]) RangeBy(indexName string, fn func(key any, values []*V) bool)
- func (imap *IndexMap[K, V]) RangeOrdered(fn func(key K, value *V) bool)
- func (imap *IndexMap[K, V]) Remove(keys ...K)
- func (imap *IndexMap[K, V]) RemoveBy(indexName string, keys ...any)
- func (imap *IndexMap[K, V]) SetCmpFn(cmp func(value1, Value2 *V) int)
- func (imap *IndexMap[K, V]) UnmarshalJSON(data []byte) error
- func (imap *IndexMap[K, V]) Update(key K, updateFn UpdateFn[V]) *V
- func (imap *IndexMap[K, V]) UpdateBy(indexName string, key any, updateFn UpdateFn[V])
- type PrimaryIndex
- type SecondaryIndex
- type Set
- type UpdateFn
Constants ¶
This section is empty.
Variables ¶
This section is empty.
Functions ¶
This section is empty.
Types ¶
type IndexMap ¶
type IndexMap[K comparable, V any] struct { // contains filtered or unexported fields }
IndexMap is a map supports seeking data with more indexes. Serializing a IndexMap as JSON results in the same as serializing a map, the result doesn't contain the index information, only data. NOTE: DO NOT insert nil value into the IndexMap
func NewIndexMap ¶
func NewIndexMap[K comparable, V any](primaryIndex *PrimaryIndex[K, V]) *IndexMap[K, V]
Create a IndexMap with a primary index, the primary index must be a one-to-one mapping.
func (*IndexMap[K, V]) AddIndex ¶
func (imap *IndexMap[K, V]) AddIndex(indexName string, index *SecondaryIndex[V]) bool
Add a secondary index, build index for the data inserted, the return value indicates whether succeed to add index, false if the indexName existed.
func (*IndexMap[K, V]) Collect ¶
func (imap *IndexMap[K, V]) Collect() ([]K, []*V)
Collect returns all the keys and values.
func (*IndexMap[K, V]) CollectBy ¶ added in v1.2.0
CollectBy returns all the keys and values as indexed by indexName.
func (*IndexMap[K, V]) CollectKeys ¶ added in v1.2.1
func (imap *IndexMap[K, V]) CollectKeys() []K
Collect returns all the keys and values.
func (*IndexMap[K, V]) CollectValues ¶ added in v1.2.1
func (imap *IndexMap[K, V]) CollectValues() []*V
Collect returns all the keys and values.
func (*IndexMap[K, V]) CollectValuesOrdered ¶ added in v1.2.1
func (imap *IndexMap[K, V]) CollectValuesOrdered() []*V
Collect returns all the keys and values.
func (*IndexMap[K, V]) Contains ¶ added in v1.2.1
Return true if the value with given key exists, false otherwise.
func (*IndexMap[K, V]) Get ¶
func (imap *IndexMap[K, V]) Get(key K) *V
Get value by the primary key, nil if key not exists.
func (*IndexMap[K, V]) GetAllBy ¶
Return all values the seeked by the key, nil if index or key not exists.
func (*IndexMap[K, V]) GetBy ¶
Return one of the values for the given secondary key, No guarantee for which one is returned if more than one elements indexed by the key.
func (*IndexMap[K, V]) Insert ¶
func (imap *IndexMap[K, V]) Insert(values ...*V)
Insert values into the map, also updates the indexes added, overwrite if a value with the same primary key existed. NOTE: insert an modified existed value with the same address may confuse the index, use Update() to do this.
func (*IndexMap[K, V]) MarshalJSON ¶
func (*IndexMap[K, V]) PrimaryKey ¶ added in v1.2.0
func (imap *IndexMap[K, V]) PrimaryKey(v *V) K
PrimaryKey calculates the primary key of given value as defined by the IndexMap's PrimaryIndex
func (*IndexMap[K, V]) Range ¶
Range iterates over all the elements, stops iteration if fn returns false, no any guarantee to the order. don't use modifying calls to this indexmap while the Range is running that may cause dead locks.
func (*IndexMap[K, V]) RangeBy ¶ added in v1.2.0
RangeBy iterates over the map by a given index fn must not attempt modifying the IndexMap, or else it will deadlock
func (*IndexMap[K, V]) RangeOrdered ¶ added in v1.2.1
Range iterates over all the elements, stops iteration if fn returns false, guarantee to the order if OrderedFn was set before. don't use modifying calls to this indexmap while the Range is running that may cause dead locks.
func (*IndexMap[K, V]) Remove ¶
func (imap *IndexMap[K, V]) Remove(keys ...K)
Remove values into the map, also updates the indexes added.
func (*IndexMap[K, V]) SetCmpFn ¶ added in v1.2.1
SetCmpFn, defines it it is not nil the compare function which is use to sort the the result of the calls to
- RangeOrdered
- CollectValuesOrdered
SortFunc sorts the slice x in ascending order as determined by the cmp function. This sort is not guaranteed to be stable. cmp(a, b) should return a negative number when a < b, a positive number when a > b and zero when a == b.
func (*IndexMap[K, V]) UnmarshalJSON ¶
func (*IndexMap[K, V]) Update ¶
Update the value for the given key, it removes the old one if exists, and inserts updateFn(old) if modified and not nil.
type PrimaryIndex ¶
type PrimaryIndex[K comparable, V any] struct { // contains filtered or unexported fields }
func NewPrimaryIndex ¶
func NewPrimaryIndex[K comparable, V any](extractField func(value *V) K) *PrimaryIndex[K, V]
Create an primary index, the extractField func must guarantee it makes the index one-to-one.
type SecondaryIndex ¶
type SecondaryIndex[V any] struct { // contains filtered or unexported fields }
func NewSecondaryIndex ¶
func NewSecondaryIndex[V any](extractField func(value *V) []any) *SecondaryIndex[V]
Create a secondary index, the extractField func returns the keys for seeking the value, It's OK that the same key seeks more than one values.
type Set ¶
type Set[T comparable] map[T]struct{}
Source Files
Directories