<commit_before>package brimstore

import (
	"fmt"
	"math"
	"sync"
	"sync/atomic"
	"unsafe"

	"github.com/gholt/brimtext"
)

// a is used to store at first, growth may then cause a split.
// While splitting, b will be set, c and d will still be nil.
// Once the split is complete, c and d will be set.
// Shrinking may cause an unsplit.
// During unsplit, a and e will be set, c and d will become nil.
// e is considered read-only/fallback during unsplit.
// Once unsplit is done, e will become nil.
type valuesLocMap struct {
	leftMask     uint64
	rangeStart   uint64
	rangeStop    uint64
	a            *valuesLocStore
	b            *valuesLocStore
	c            *valuesLocMap
	d            *valuesLocMap
	e            *valuesLocStore
	resizing     bool
	resizingLock sync.RWMutex
	cores        int
	splitCount   int
}

type valuesLocStore struct {
	buckets []valueLoc
	locks   []sync.RWMutex
	used    int32
}

type valueLoc struct {
	next      *valueLoc
	keyA      uint64
	keyB      uint64
	timestamp uint64
	blockID   uint16
	offset    uint32
	length    uint32
}

type valuesLocMapStats struct {
	extended     bool
	wg           sync.WaitGroup
	depth        uint64
	depthCounts  []uint64
	sections     uint64
	storages     uint64
	buckets      uint64
	bucketCounts []uint64
	splitCount   uint64
	locs         uint64
	pointerLocs  uint64
	unused       uint64
	used         uint64
	active       uint64
	length       uint64
	tombstones   uint64
}

type valuesLocMapBackground struct {
	wg                  sync.WaitGroup
	tombstoneCutoff     uint64
	tombstonesDiscarded uint64
	tombstonesRetained  uint64
}

func newValuesLocMap(opts *ValuesStoreOpts) *valuesLocMap {
	if opts == nil {
		opts = NewValuesStoreOpts("")
	}
	cores := opts.Cores
	if cores < 1 {
		cores = 1
	}
	valuesLocMapPageSize := opts.ValuesLocMapPageSize
	if valuesLocMapPageSize < 1 {
		valuesLocMapPageSize = 1
	}
	bucketCount := valuesLocMapPageSize / int(unsafe.Sizeof(valueLoc{}))
	if bucketCount < 1 {
		bucketCount = 1
	}
	lockCount := cores
	if lockCount > bucketCount {
		lockCount = bucketCount
	}
	splitMultiplier := opts.ValuesLocMapSplitMultiplier
	if splitMultiplier <= 0 {
		splitMultiplier = 0.1
	}
	vlm := &valuesLocMap{
		leftMask:   uint64(1) << 63,
		rangeStart: 0,
		rangeStop:  math.MaxUint64,
		cores:      cores,
		splitCount: int(float64(bucketCount) * splitMultiplier),
		a: &valuesLocStore{
			buckets: make([]valueLoc, bucketCount),
			locks:   make([]sync.RWMutex, lockCount),
		},
	}
	return vlm
}

func (vlm *valuesLocMap) get(keyA uint64, keyB uint64) (uint64, uint16, uint32, uint32) {
	var timestamp uint64
	var blockID uint16
	var offset uint32
	var length uint32
	for {
		vlm.resizingLock.RLock()
		if vlm.c == nil {
			break
		}
		runlock := &vlm.resizingLock
		if keyA&vlm.leftMask == 0 {
			vlm = vlm.c
		} else {
			vlm = vlm.d
		}
		runlock.RUnlock()
	}
	bix := keyB % uint64(len(vlm.a.buckets))
	lix := bix % uint64(len(vlm.a.locks))
	f := func(s *valuesLocStore, fb *valuesLocStore) {
		blockID = 0
		s.locks[lix].RLock()
		if fb != nil {
			fb.locks[lix].RLock()
		}
		for item := &s.buckets[bix]; item != nil; item = item.next {
			if item.blockID != 0 && item.keyA == keyA && item.keyB == keyB {
				timestamp, blockID, offset, length = item.timestamp, item.blockID, item.offset, item.length
				break
			}
		}
		if fb != nil && blockID == 0 {
			for item := &fb.buckets[bix]; item != nil; item = item.next {
				if item.blockID != 0 && item.keyA == keyA && item.keyB == keyB {
					timestamp, blockID, offset, length = item.timestamp, item.blockID, item.offset, item.length
					break
				}
			}
		}
		if fb != nil {
			fb.locks[lix].RUnlock()
		}
		s.locks[lix].RUnlock()
	}
	if vlm.b == nil || keyA&vlm.leftMask == 0 {
		f(vlm.a, vlm.e)
	} else {
		f(vlm.b, vlm.a)
	}
	vlm.resizingLock.RUnlock()
	return timestamp, blockID, offset, length
}

func (vlm *valuesLocMap) set(keyA uint64, keyB uint64, timestamp uint64, blockID uint16, offset uint32, length uint32, evenIfSameTimestamp bool) uint64 {
	var oldTimestamp uint64
	var vlmPrev *valuesLocMap
	for {
		vlm.resizingLock.RLock()
		if vlm.c == nil {
			break
		}
		vlmPrev = vlm
		runlock := &vlm.resizingLock
		if keyA&vlm.leftMask == 0 {
			vlm = vlm.c
		} else {
			vlm = vlm.d
		}
		runlock.RUnlock()
	}
	bix := keyB % uint64(len(vlm.a.buckets))
	lix := bix % uint64(len(vlm.a.locks))
	f := func(s *valuesLocStore, fb *valuesLocStore) {
		oldTimestamp = 0
		var sMatch *valueLoc
		var fbMatch *valueLoc
		var unusedItem *valueLoc
		s.locks[lix].Lock()
		if fb != nil {
			fb.locks[lix].Lock()
		}
		for item := &s.buckets[bix]; item != nil; item = item.next {
			if item.blockID == 0 {
				if unusedItem == nil {
					unusedItem = item<commit_msg>Lock deeper before releasing shallower<commit_after>package brimstore

import (
	"fmt"
	"math"
	"sync"
	"sync/atomic"
	"unsafe"

	"github.com/gholt/brimtext"
)

// a is used to store at first, growth may then cause a split.
// While splitting, b will be set, c and d will still be nil.
// Once the split is complete, c and d will be set.
// Shrinking may cause an unsplit.
// During unsplit, a and e will be set, c and d will become nil.
// e is considered read-only/fallback during unsplit.
// Once unsplit is done, e will become nil.
type valuesLocMap struct {
	leftMask     uint64
	rangeStart   uint64
	rangeStop    uint64
	a            *valuesLocStore
	b            *valuesLocStore
	c            *valuesLocMap
	d            *valuesLocMap
	e            *valuesLocStore
	resizing     bool
	resizingLock sync.RWMutex
	cores        int
	splitCount   int
}

type valuesLocStore struct {
	buckets []valueLoc
	locks   []sync.RWMutex
	used    int32
}

type valueLoc struct {
	next      *valueLoc
	keyA      uint64
	keyB      uint64
	timestamp uint64
	blockID   uint16
	offset    uint32
	length    uint32
}

type valuesLocMapStats struct {
	extended     bool
	wg           sync.WaitGroup
	depth        uint64
	depthCounts  []uint64
	sections     uint64
	storages     uint64
	buckets      uint64
	bucketCounts []uint64
	splitCount   uint64
	locs         uint64
	pointerLocs  uint64
	unused       uint64
	used         uint64
	active       uint64
	length       uint64
	tombstones   uint64
}

type valuesLocMapBackground struct {
	wg                  sync.WaitGroup
	tombstoneCutoff     uint64
	tombstonesDiscarded uint64
	tombstonesRetained  uint64
}

func newValuesLocMap(opts *ValuesStoreOpts) *valuesLocMap {
	if opts == nil {
		opts = NewValuesStoreOpts("")
	}
	cores := opts.Cores
	if cores < 1 {
		cores = 1
	}
	valuesLocMapPageSize := opts.ValuesLocMapPageSize
	if valuesLocMapPageSize < 1 {
		valuesLocMapPageSize = 1
	}
	bucketCount := valuesLocMapPageSize / int(unsafe.Sizeof(valueLoc{}))
	if bucketCount < 1 {
		bucketCount = 1
	}
	lockCount := cores
	if lockCount > bucketCount {
		lockCount = bucketCount
	}
	splitMultiplier := opts.ValuesLocMapSplitMultiplier
	if splitMultiplier <= 0 {
		splitMultiplier = 0.1
	}
	vlm := &valuesLocMap{
		leftMask:   uint64(1) << 63,
		rangeStart: 0,
		rangeStop:  math.MaxUint64,
		cores:      cores,
		splitCount: int(float64(bucketCount) * splitMultiplier),
		a: &valuesLocStore{
			buckets: make([]valueLoc, bucketCount),
			locks:   make([]sync.RWMutex, lockCount),
		},
	}
	return vlm
}

func (vlm *valuesLocMap) get(keyA uint64, keyB uint64) (uint64, uint16, uint32, uint32) {
	var timestamp uint64
	var blockID uint16
	var offset uint32
	var length uint32
	vlm.resizingLock.RLock()
	for {
		if vlm.c == nil {
			break
		}
		runlock := &vlm.resizingLock
		if keyA&vlm.leftMask == 0 {
			vlm = vlm.c
		} else {
			vlm = vlm.d
		}
		vlm.resizingLock.RLock()
		runlock.RUnlock()
	}
	bix := keyB % uint64(len(vlm.a.buckets))
	lix := bix % uint64(len(vlm.a.locks))
	f := func(s *valuesLocStore, fb *valuesLocStore) {
		blockID = 0
		s.locks[lix].RLock()
		if fb != nil {
			fb.locks[lix].RLock()
		}
		for item := &s.buckets[bix]; item != nil; item = item.next {
			if item.blockID != 0 && item.keyA == keyA && item.keyB == keyB {
				timestamp, blockID, offset, length = item.timestamp, item.blockID, item.offset, item.length
				break
			}
		}
		if fb != nil && blockID == 0 {
			for item := &fb.buckets[bix]; item != nil; item = item.next {
				if item.blockID != 0 && item.keyA == keyA && item.keyB == keyB {
					timestamp, blockID, offset, length = item.timestamp, item.blockID, item.offset, item.length
					break
				}
			}
		}
		if fb != nil {
			fb.locks[lix].RUnlock()
		}
		s.locks[lix].RUnlock()
	}
	if vlm.b == nil || keyA&vlm.leftMask == 0 {
		f(vlm.a, vlm.e)
	} else {
		f(vlm.b, vlm.a)
	}
	vlm.resizingLock.RUnlock()
	return timestamp, blockID, offset, length
}

func (vlm *valuesLocMap) set(keyA uint64, keyB uint64, timestamp uint64, blockID uint16, offset uint32, length uint32, evenIfSameTimestamp bool) uint64 {
	var oldTimestamp uint64
	var vlmPrev *valuesLocMap
	vlm.resizingLock.RLock()
	for {
		if vlm.c == nil {
			break
		}
		vlmPrev = vlm
		runlock := &vlm.resizingLock
		if keyA&vlm.leftMask == 0 {
			vlm = vlm.c
		} else {
			vlm = vlm.d
		}
		vlm.resizingLock.RLock()
		runlock.RUnlock()
	}
	bix := keyB % uint64(len(vlm.a.buckets))
	lix := bix % uint64(len(vlm.a.locks))
	f := func(s *valuesLocStore, fb *valuesLocStore) {
		oldTimestamp = 0
		var sMatch *valueLoc
		var fbMatch *valueLoc
		var unusedItem *valueLoc
		s.locks[lix].Lock()
		if fb != nil {
			fb.locks[lix].Lock()
		}
		for item := &s.buckets[bix]; item != nil; item = item.next {
			if item.blockID == 0 {
				if unusedItem == nil {
					unusedItem = item
{'fraction_non_alphanumeric': 0.10885783335084585, 'fraction_numerical': 0.026478932436692235, 'mean_word_length': 2.8864842792976724, 'pattern_counts': {'":': 0, '<': 15, '<?xml version=': 0, '>': 5, 'https://': 0, 'lorem ipsum': 0, 'www.': 0, 'xml': 0}, 'pii_count': 0, 'substrings_counts': 0, 'word_list_counts': {'cursed_substrings.json': 0, 'profanity_word_list.json': 0, 'sexual_word_list.json': 0, 'zh_pornsignals.json': 0}}
{'dir': 'git-commits-cleaned', 'id': '2200583', 'n_tokens_mistral': 3960, 'n_tokens_neox': 3539, 'n_words': 929}