Line data    Source code

       1             : // Copyright 2024 The LevelDB-Go and Pebble Authors. All rights reserved. Use
       2             : // of this source code is governed by a BSD-style license that can be found in
       3             : // the LICENSE file.
       4             : 
       5             : package cache
       6             : 
       7             : import (
       8             :         "fmt"
       9             :         "os"
      10             :         "unsafe"
      11             : 
      12             :         "github.com/cockroachdb/pebble/internal/invariants"
      13             :         "github.com/cockroachdb/pebble/internal/manual"
      14             :         "github.com/cockroachdb/swiss"
      15             : )
      16             : 
      17           1 : func fibonacciHash(k *key, seed uintptr) uintptr {
      18           1 :         const m = 11400714819323198485
      19           1 :         h := uint64(seed)
      20           1 :         h ^= k.id * m
      21           1 :         h ^= uint64(k.fileNum) * m
      22           1 :         h ^= k.offset * m
      23           1 :         return uintptr(h)
      24           1 : }
      25             : 
      26             : type blockMapAllocator struct{}
      27             : 
      28           1 : func (blockMapAllocator) Alloc(n int) []swiss.Group[key, *entry] {
      29           1 :         size := uintptr(n) * unsafe.Sizeof(swiss.Group[key, *entry]{})
      30           1 :         buf := manual.New(int(size))
      31           1 :         return unsafe.Slice((*swiss.Group[key, *entry])(unsafe.Pointer(unsafe.SliceData(buf))), n)
      32           1 : }
      33             : 
      34           1 : func (blockMapAllocator) Free(v []swiss.Group[key, *entry]) {
      35           1 :         size := uintptr(len(v)) * unsafe.Sizeof(swiss.Group[key, *entry]{})
      36           1 :         buf := unsafe.Slice((*byte)(unsafe.Pointer(unsafe.SliceData(v))), size)
      37           1 :         manual.Free(buf)
      38           1 : }
      39             : 
      40             : var blockMapOptions = []swiss.Option[key, *entry]{
      41             :         swiss.WithHash[key, *entry](fibonacciHash),
      42             :         swiss.WithMaxBucketCapacity[key, *entry](1 << 16),
      43             :         swiss.WithAllocator[key, *entry](blockMapAllocator{}),
      44             : }
      45             : 
      46             : type blockMap struct {
      47             :         swiss.Map[key, *entry]
      48             :         closed bool
      49             : }
      50             : 
      51           0 : func newBlockMap(initialCapacity int) *blockMap {
      52           0 :         m := &blockMap{}
      53           0 :         m.Init(initialCapacity)
      54           0 : 
      55           0 :         // Note: this is a no-op if invariants are disabled or race is enabled.
      56           0 :         invariants.SetFinalizer(m, func(obj interface{}) {
      57           0 :                 m := obj.(*blockMap)
      58           0 :                 if !m.closed {
      59           0 :                         fmt.Fprintf(os.Stderr, "%p: block-map not closed\n", m)
      60           0 :                         os.Exit(1)
      61           0 :                 }
      62             :         })
      63           0 :         return m
      64             : }
      65             : 
      66           1 : func (m *blockMap) Init(initialCapacity int) {
      67           1 :         m.Map.Init(initialCapacity, blockMapOptions...)
      68           1 : }
      69             : 
      70           1 : func (m *blockMap) Close() {
      71           1 :         m.Map.Close()
      72           1 :         m.closed = true
      73           1 : }
      74             : 
      75           1 : func (m *blockMap) findByValue(v *entry) bool {
      76           1 :         var found bool
      77           1 :         m.Map.All(func(_ key, e *entry) bool {
      78           1 :                 if v == e {
      79           0 :                         found = true
      80           0 :                         return false
      81           0 :                 }
      82           1 :                 return true
      83             :         })
      84           1 :         return found
      85             : }