skiplistmap

package module
v0.2.4 Latest Latest
Warning

This package is not in the latest version of its module.

 Go to latest Published: Dec 3, 2021 License: MIT Imports: 12 Imported by: 0

README

Skip List Map in Golang

Skip List Map is a concurrent map. this Map is goroutine safety for reading/updating/deleting, no-require locking and coordination.

status

Go Go Reference

features

  • buckets, elemenet(key/value item) structure is concurrent embeded-linked list. (using list_encabezado)
  • keep key order by hash function.
  • ability to store value ( value of key/vale) and elemet of ket/value item(detail is later)
  • improve performance for sync.Map/ internal map in write heavy environment.

requirement

golang >= 1.17

install

Install this package through go get.

go get "github.com/kazu/skiplistmap"

basic usage

package main 

import (
    "fmt"
)

//create skip list map
sMap := skiplistmap.New()
// create make with configure MaxPerBucket
// sMap := skiplistmap.New(skiplistmap.MaxPefBucket(12))
// sMap := skiplistmap.New(skiplistmap.MaxPefBucket(12))

// Set/Add values
sMap.Set("test1", 1)
sMap.Set("test2", 2)

// get the value for a key, return nil if not found, the ok is found.
inf, ok := sMap.Get("test1")
var value1 int
if ok {
    value1 = inf.(int)
}

ok = sMap.GetByFn(func(v interface{}) {
    value = v.(int)
})


// if directry using key/value item. use SampleItem struct
sMap2 := skiplistmap.New(skiplistmap.MaxPefBucket(12))
item := &skiplistmap.SampleItem{
    K: "test1", 
    V: 1234
}

// store item
ok = sMap2.StoreItem(item)

// get key/value item
item, ok = sMap.LoadItem("test1")
// get next key/value
nItem := sMap.Next()

// traverse all item or key/value 
sMap.RangeItem(func(item MapItem) bool {
  fmt.Printf("key=%+v\n", item.Key())  
})
sMap.Range(func(key, value interface{}) bool {
  fmt.Printf("key=%+v\n", key)  
})



// delete marking. set nil as value.
sMap.Delete("test2")

// delete key/value entry from map. traverse locked for deleting item to acceess concurrent
sMap.Purge("test2")

performance

condition
  • 100000 record. set key/value before benchmark
  • mapWithMutex map[interface{}]interface{} with sync.RWMutex
  • skiplistmap normal element search
  • skiplistmap3 with reverse element search
  • RMap rewrite drity of sync.Map as skiplistmap (sync.Map read is map[uint64]atomic.Value)
read only
Benchmark_Map/mapWithMutex__________________w/_0_bucket=__0-16         	17055374	        69.39 ns/op	      15 B/op	       1 allocs/op
Benchmark_Map/sync.Map______________________w/_0_bucket=__0-16         	25268019	        42.00 ns/op	      63 B/op	       2 allocs/op
Benchmark_Map/skiplistmap___________________w/_0_bucket=_32-16         	26189863	        47.96 ns/op	      15 B/op	       1 allocs/op
Benchmark_Map/skiplistmap___________________w/_0_bucket=_16-16         	32570624	        44.40 ns/op	      15 B/op	       1 allocs/op
Benchmark_Map/skiplistmap3__________________w/_0_bucket=_16-16         	36449119	        40.41 ns/op	      15 B/op	       1 allocs/op
Benchmark_Map/RMap__________________________w/_0_bucket=__0-16         	34806978	        33.39 ns/op	      31 B/op	       2 allocs/op
read 50%. update 50%
Benchmark_Map/mapWithMutex__________________w/50_bucket=__0-16         	 3314656	       364.6 ns/op	      16 B/op	       1 allocs/op
Benchmark_Map/sync.Map______________________w/50_bucket=__0-16         	14289441	        70.34 ns/op	     134 B/op	       4 allocs/op
Benchmark_Map/skiplistmap___________________w/50_bucket=_32-16         	21370478	        64.18 ns/op	      27 B/op	       2 allocs/op
Benchmark_Map/skiplistmap___________________w/50_bucket=_16-16         	21110790	        65.22 ns/op	      27 B/op	       2 allocs/op
Benchmark_Map/RMap__________________________w/50_bucket=__0-16         	21455697	        53.36 ns/op	      72 B/op	       4 allocs/op

Documentation

Overview

Package loncha/list_head is like a kernel's LIST_HEAD list_head is used by loncha/gen/containers_list

Package skitlistmap ... concurrent akiplist map implementatin Copyright 2201 Kazuhisa TAKEI<xtakei@rytr.jp>. All rights reserved. Use of this source code is governed by a BSD-style license that can be found in the LICENSE file.

Package skitlistmap ... concurrent akiplist map implementatin Copyright 2201 Kazuhisa TAKEI<xtakei@rytr.jp>. All rights reserved. Use of this source code is governed by a BSD-style license that can be found in the LICENSE file.

Index

Constants

View Source 
const (
	CntSearchBucket  statKey = 1
	CntLevelBucket   statKey = 2
	CntSearchEntry   statKey = 3
	CntReverseSearch statKey = 4
	CntOfGet         statKey = 5
)

Variables

View Source 
var (
	ErrInvalidAdd      error = NewError(EInvalidAdd, "dd: item is added. but not found", nil)
	ErrNotFoundBUcket  error = NewError(ENotFoundBucket, "bucket is not found", nil)
	ErrFailBucketAlloc error = NewError(EFailBucketAlloc, "cannot allocated level bucket buffer", nil)
)
View Source 
var DebugStats map[statKey]int = map[statKey]int{}
View Source 
var (
	EmptyEntryHMap *entryHMap = emptyEntryHMap
)
View Source 
var EnableStats bool = false
View Source 
var Failreverse uint64 = 0

Functions

func IsDebug added in v0.2.4 

func IsDebug() bool

func KeyToHash 

func KeyToHash(key interface{}) (uint64, uint64)

func Log added in v0.1.4 

func Log(l LogLevel, s string, args ...interface{})

func MemHash 

func MemHash(data []byte) uint64

func MemHashString 

func MemHashString(str string) uint64

func NewEntryMap 

func NewEntryMap(key, value interface{}) *entryHMap

func ResetStats added in v0.1.3 

func ResetStats()

func SetLogIO added in v0.1.4 

func SetLogIO(w io.Writer)

func WithBucket 

func WithBucket(b *bucket) func(*hmapMethod)

Types

type CondOfFinder 

type CondOfFinder func(ehead *entryHMap) bool

func CondOfFind 

func CondOfFind(reverse uint64, l sync.Locker) CondOfFinder

type ErrType added in v0.2.4 

type ErrType uint16
const (
	EInvalidAdd ErrType = 1 << iota
	ENotFoundBucket
	EFailBucketAlloc
	EInvalidBucket
)

type Error added in v0.2.4 

type Error struct {
	Type ErrType
	// contains filtered or unexported fields
}

func NewError added in v0.2.4 

func NewError(t ErrType, m string, e error) *Error

func (*Error) Error added in v0.2.4 

func (e *Error) Error() string

func (*Error) ErrorNum added in v0.2.4 

func (e *Error) ErrorNum() uint16

type HMapEntry 

type HMapEntry interface {
	Offset() uintptr
	PtrMapHead() *MapHead
	PtrListHead() *list_head.ListHead
	HmapEntryFromListHead(*list_head.ListHead) HMapEntry
	Next() HMapEntry
	Prev() HMapEntry
}

type HMethodOpt 

type HMethodOpt func(*hmapMethod)

type LevelHead 

type LevelHead list_head.ListHead

type LogLevel added in v0.1.4 

type LogLevel byte
const (
	LogDebug LogLevel = iota
	LogInfo
	LogWarn
	LogError
	LogFatal
)
const CurrentLogLevel LogLevel = LogWarn

type Map 

type Map struct {
	ItemFn func() MapItem
	// contains filtered or unexported fields
}

Map ... Skip List Map is an ordered and concurrent map. this Map is gourtine safety for reading/updating/deleting, require locking and coordination. This

func New 

func New(opts ...OptHMap) *Map

func NewHMap 

func NewHMap(opts ...OptHMap) *Map

func (*Map) AddLen added in v0.2.1 

func (h *Map) AddLen(inc int64) int64

func (*Map) BackBucket added in v0.2.4 

func (h *Map) BackBucket() (bCur *bucket)

func (*Map) Delete 

func (h *Map) Delete(key interface{})

Delete ... set nil to the key of MapItem. cannot Get entry

func (*Map) DumpBucket 

func (h *Map) DumpBucket(w io.Writer)

func (*Map) DumpBucketPerLevel 

func (h *Map) DumpBucketPerLevel(w io.Writer)

func (*Map) DumpEntry 

func (h *Map) DumpEntry(w io.Writer)

func (*Map) Get 

func (h *Map) Get(key interface{}) (value interface{}, ok bool)

Get ... return the value for a key, if not found, ok is false

func (*Map) GetWithFn 

func (h *Map) GetWithFn(key interface{}, onSuccess func(interface{})) bool

GetWithFn ... Get with succes function.

func (*Map) Len added in v0.2.1 

func (h *Map) Len() int

func (*Map) LoadItem 

func (h *Map) LoadItem(key interface{}) (MapItem, bool)

LoadItem ... return key/value item with embedded-linked-list. if not found, ok is false

func (*Map) LoadItemByHash added in v0.2.1 

func (h *Map) LoadItemByHash(k uint64, conflict uint64) (MapItem, bool)

func (*Map) MakeBucket 

func (h *Map) MakeBucket(ocur *list_head.ListHead, back int) (err error)

func (*Map) Options 

func (h *Map) Options(opts ...OptHMap) (previouses []OptHMap)

func (*Map) Range added in v0.1.2 

func (h *Map) Range(f func(key, value interface{}) bool)

Range ... calls f sequentially for each key and value present in the map. order is reverse key order

func (*Map) RangeItem added in v0.1.2 

func (h *Map) RangeItem(f func(MapItem) bool)

RangeItem ... calls f sequentially for each key and value present in the map. called ordre is reverse key order

func (*Map) SearchKey 

func (h *Map) SearchKey(k uint64, opts ...searchArg) HMapEntry

func (*Map) Set 

func (h *Map) Set(key, value interface{}) bool

Set ... set the value for a key

func (*Map) StoreItem 

func (h *Map) StoreItem(item MapItem) bool

StoreItem ... set key/value item with embedded-linked-list

type MapHead 

type MapHead struct {
	list_head.ListHead
	// contains filtered or unexported fields
}
var EmptyMapHead MapHead = MapHead{}

func (*MapHead) ConflictInHamp 

func (mh *MapHead) ConflictInHamp() uint64

func (*MapHead) FromListHead 

func (c *MapHead) FromListHead(l *list_head.ListHead) list_head.List

func (*MapHead) KeyInHmap 

func (mh *MapHead) KeyInHmap() uint64

func (*MapHead) NextWithNil added in v0.1.3 

func (c *MapHead) NextWithNil() *MapHead

func (*MapHead) Offset 

func (mh *MapHead) Offset() uintptr

func (*MapHead) PrevtWithNil added in v0.1.3 

func (c *MapHead) PrevtWithNil() *MapHead

func (*MapHead) PtrListHead 

func (mh *MapHead) PtrListHead() *list_head.ListHead

type MapItem 

type MapItem interface {
	Key() interface{}   // require order for HMap
	Value() interface{} // require order for HMap
	SetValue(interface{}) bool
	Delete()

	HMapEntry
}

type OptHMap 

type OptHMap func(*Map) OptHMap

func BucketMode 

func BucketMode(mode SearchMode) OptHMap

func ItemFn 

func ItemFn(fn func() MapItem) OptHMap

func MaxPefBucket 

func MaxPefBucket(max int) OptHMap

type SampleItem 

type SampleItem struct {
	K interface{}
	V interface{}
	MapHead
}
var EmptySampleHMapEntry SampleItem = SampleItem{}

func SampleItemFromListHead 

func SampleItemFromListHead(head *list_head.ListHead) *SampleItem

func (*SampleItem) Delete 

func (s *SampleItem) Delete()

func (*SampleItem) HmapEntryFromListHead 

func (s *SampleItem) HmapEntryFromListHead(lhead *list_head.ListHead) HMapEntry

func (*SampleItem) Key 

func (s *SampleItem) Key() interface{}

func (*SampleItem) Next 

func (s *SampleItem) Next() HMapEntry

func (*SampleItem) Offset 

func (s *SampleItem) Offset() uintptr

func (*SampleItem) Prev 

func (s *SampleItem) Prev() HMapEntry

func (*SampleItem) PtrMapHead 

func (s *SampleItem) PtrMapHead() *MapHead

func (*SampleItem) PtrMapeHead 

func (s *SampleItem) PtrMapeHead() *MapHead

func (*SampleItem) SetValue 

func (s *SampleItem) SetValue(v interface{}) bool

func (*SampleItem) Setup added in v0.2.1 

func (s *SampleItem) Setup()

func (*SampleItem) Value 

func (s *SampleItem) Value() interface{}

type SearchMode 

type SearchMode byte
const (
	LenearSearchForBucket SearchMode = iota
	NestedSearchForBucket
	CombineSearch
	CombineSearch2
	CombineSearch3

	NoItemSearchForBucket = 9 // test mode
	FalsesSearchForBucket = 10
)

Source Files

View all Source files

Directories

Path Synopsis

Jump to

Keyboard shortcuts

? : This menu
/ : Search site
f or F : Jump to
y or Y : Canonical URL
go.dev uses cookies from Google to deliver and enhance the quality of its services and to analyze traffic. Learn more.