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 colblk
       6             : 
       7             : import (
       8             :         "unsafe"
       9             : 
      10             :         "github.com/cockroachdb/errors"
      11             :         "golang.org/x/exp/constraints"
      12             : )
      13             : 
      14             : // UnsafeRawSlice maintains a pointer to a slice of elements of type T.
      15             : // UnsafeRawSlice provides no bounds checking.
      16             : type UnsafeRawSlice[T constraints.Integer] struct {
      17             :         ptr unsafe.Pointer
      18             : }
      19             : 
      20           1 : func makeUnsafeRawSlice[T constraints.Integer](ptr unsafe.Pointer) UnsafeRawSlice[T] {
      21           1 :         if align(uintptr(ptr), unsafe.Sizeof(T(0))) != uintptr(ptr) {
      22           0 :                 panic(errors.AssertionFailedf("slice pointer %p not %d-byte aligned", ptr, unsafe.Sizeof(T(0))))
      23             :         }
      24           1 :         return UnsafeRawSlice[T]{ptr: ptr}
      25             : }
      26             : 
      27             : // At returns the `i`-th element of the slice.
      28           1 : func (s UnsafeRawSlice[T]) At(i int) T {
      29           1 :         return *(*T)(unsafe.Pointer(uintptr(s.ptr) + unsafe.Sizeof(T(0))*uintptr(i)))
      30           1 : }
      31             : 
      32             : // Slice returns a go []T slice containing the first `len` elements of the
      33             : // unsafe slice.
      34           1 : func (s UnsafeRawSlice[T]) Slice(len int) []T {
      35           1 :         return unsafe.Slice((*T)(s.ptr), len)
      36           1 : }
      37             : 
      38             : // set mutates the slice, setting the `i`-th value to `v`.
      39           1 : func (s UnsafeRawSlice[T]) set(i int, v T) {
      40           1 :         *(*T)(unsafe.Pointer(uintptr(s.ptr) + unsafe.Sizeof(T(0))*uintptr(i))) = v
      41           1 : }
      42             : 
      43             : // UnsafeUint8s is an UnsafeIntegerSlice of uint8s, possibly using delta
      44             : // encoding internally.
      45             : type UnsafeUint8s = UnsafeIntegerSlice[uint8]
      46             : 
      47             : // UnsafeUint16s is an UnsafeIntegerSlice of uint16s, possibly using delta
      48             : // encoding internally.
      49             : type UnsafeUint16s = UnsafeIntegerSlice[uint16]
      50             : 
      51             : // UnsafeUint32s is an UnsafeIntegerSlice of uint32s, possibly using delta
      52             : // encoding internally.
      53             : type UnsafeUint32s = UnsafeIntegerSlice[uint32]
      54             : 
      55             : // UnsafeUint64s is an UnsafeIntegerSlice of uint64s, possibly using delta
      56             : // encoding internally.
      57             : type UnsafeUint64s = UnsafeIntegerSlice[uint64]
      58             : 
      59             : // UnsafeIntegerSlice exposes a read-only slice of integers from a column. If
      60             : // the column's values are delta-encoded, UnsafeIntegerSlice transparently
      61             : // applies deltas.
      62             : //
      63             : // See DeltaEncoding and UintBuilder.
      64             : type UnsafeIntegerSlice[T constraints.Integer] struct {
      65             :         base       T
      66             :         deltaPtr   unsafe.Pointer
      67             :         deltaWidth uintptr
      68             : }
      69             : 
      70             : // Assert that UnsafeIntegerSlice implements Array.
      71             : var _ Array[uint8] = UnsafeIntegerSlice[uint8]{}
      72             : 
      73             : // DecodeUnsafeIntegerSlice decodes the structure of a slice of uints from a
      74             : // byte slice.
      75             : func DecodeUnsafeIntegerSlice[T constraints.Integer](
      76             :         b []byte, off uint32, rows int,
      77           1 : ) (slice UnsafeIntegerSlice[T], endOffset uint32) {
      78           1 :         delta := UintDeltaEncoding(b[off])
      79           1 :         off++
      80           1 :         switch delta {
      81           1 :         case UintDeltaEncodingNone:
      82           1 :                 off = align(off, uint32(unsafe.Sizeof(T(0))))
      83           1 :                 slice = makeUnsafeIntegerSlice[T](0, unsafe.Pointer(&b[off]), int(unsafe.Sizeof(T(0))))
      84           1 :                 off += uint32(unsafe.Sizeof(T(0))) * uint32(rows)
      85           1 :         case UintDeltaEncodingConstant:
      86           1 :                 base := readLittleEndianNonaligned[T](b, off)
      87           1 :                 off += uint32(unsafe.Sizeof(T(0)))
      88           1 :                 slice = makeUnsafeIntegerSlice[T](base, unsafe.Pointer(&b[off]), 0)
      89           1 :         case UintDeltaEncoding8, UintDeltaEncoding16, UintDeltaEncoding32:
      90           1 :                 w := delta.width()
      91           1 :                 base := readLittleEndianNonaligned[T](b, off)
      92           1 :                 off += uint32(unsafe.Sizeof(T(0)))
      93           1 :                 off = align(off, uint32(w))
      94           1 :                 slice = makeUnsafeIntegerSlice[T](base, unsafe.Pointer(&b[off]), w)
      95           1 :                 off += uint32(rows) * uint32(w)
      96           0 :         default:
      97           0 :                 panic("unreachable")
      98             :         }
      99           1 :         return slice, off
     100             : }
     101             : 
     102             : // Assert that DecodeUnsafeIntegerSlice implements DecodeFunc.
     103             : var _ DecodeFunc[UnsafeUint8s] = DecodeUnsafeIntegerSlice[uint8]
     104             : 
     105             : func makeUnsafeIntegerSlice[T constraints.Integer](
     106             :         base T, deltaPtr unsafe.Pointer, deltaWidth int,
     107           1 : ) UnsafeIntegerSlice[T] {
     108           1 :         return UnsafeIntegerSlice[T]{
     109           1 :                 base:       base,
     110           1 :                 deltaPtr:   deltaPtr,
     111           1 :                 deltaWidth: uintptr(deltaWidth),
     112           1 :         }
     113           1 : }
     114             : 
     115             : // At returns the `i`-th element of the slice.
     116           1 : func (s UnsafeIntegerSlice[T]) At(i int) T {
     117           1 :         // TODO(jackson): Experiment with other alternatives that might be faster
     118           1 :         // and avoid switching on the width.
     119           1 :         switch s.deltaWidth {
     120           1 :         case 0:
     121           1 :                 return s.base
     122           1 :         case 1:
     123           1 :                 return s.base + T(*(*uint8)(unsafe.Pointer(uintptr(s.deltaPtr) + uintptr(i))))
     124           1 :         case 2:
     125           1 :                 return s.base + T(*(*uint16)(unsafe.Pointer(uintptr(s.deltaPtr) + uintptr(i)<<align16Shift)))
     126           1 :         case 4:
     127           1 :                 return s.base + T(*(*uint32)(unsafe.Pointer(uintptr(s.deltaPtr) + uintptr(i)<<align32Shift)))
     128           1 :         case 8:
     129           1 :                 // NB: The slice encodes 64-bit integers, there is no base (it doesn't
     130           1 :                 // save any bits to compute a delta) and T must be a 64-bit integer. We
     131           1 :                 // cast directly into a *T pointer and don't add the base.
     132           1 :                 return (*(*T)(unsafe.Pointer(uintptr(s.deltaPtr) + uintptr(i)<<align64Shift)))
     133           0 :         default:
     134           0 :                 panic("unreachable")
     135             :         }
     136             : }