arena.go

arena.go - Overview

This file defines an arena allocator for use in a skip list implementation. It provides methods for allocating nodes, keys, and values within a pre-allocated byte buffer, ensuring proper alignment and bounds checking. The arena is designed to be lock-free, using atomic operations for managing the allocation offset.

Detailed Documentation

Constants

offsetSize

const (
	offsetSize = int(unsafe.Sizeof(uint32(0)))
	// ...
)

• Purpose: Defines the size of an offset (uint32) in bytes. This is used for calculating memory offsets within the arena.

nodeAlign

const (
	// ...
	nodeAlign = int(unsafe.Sizeof(uint64(0))) - 1
)

• Purpose: Defines the alignment requirement for nodes in the arena. Ensures that nodes are aligned on 64-bit boundaries, even on 32-bit architectures, to ensure atomic operations on the value field work correctly.

Arena struct

type Arena struct {
	n   atomic.Uint32
	buf []byte
}

• Purpose: Represents the arena allocator. It contains an atomic counter n to track the current allocation offset and a byte slice buf representing the pre-allocated memory buffer.
  • n: An atomic unsigned 32-bit integer representing the current allocation offset in the arena.
  • buf: A byte slice representing the pre-allocated memory buffer managed by the arena.

newArena func

func newArena(n int64) *Arena {
	// ...
}

• Purpose: Creates a new arena with a pre-allocated buffer of size n. It initializes the allocation offset to 1 to reserve 0 as a nil pointer.
  • Parameters:
    • n: int64 - The size of the arena buffer in bytes.
  • Returns: *Arena - A pointer to the newly created arena.

size func

func (s *Arena) size() int64 {
	return int64(s.n.Load())
}

• Purpose: Returns the current size (offset) of the arena, representing the amount of memory allocated so far.
  • Returns: int64 - The current size of the arena.

putNode func

func (s *Arena) putNode(height int) uint32 {
	// ...
}

• Purpose: Allocates a node of a given height in the arena. It calculates the required size based on the height, aligns the allocation, and returns the offset of the allocated node.
  • Parameters:
    • height: int - The height of the node to be allocated.
  • Returns: uint32 - The arena offset of the allocated node.

putVal func

func (s *Arena) putVal(v y.ValueStruct) uint32 {
	// ...
}

• Purpose: Copies a y.ValueStruct into the arena. Returns the offset of the copied value.
  • Parameters:
    • v: y.ValueStruct - The value to be copied into the arena.
  • Returns: uint32 - The arena offset of the copied value.

putKey func

func (s *Arena) putKey(key []byte) uint32 {
	// ...
}

• Purpose: Copies a key (byte slice) into the arena. Returns the offset of the copied key.
  • Parameters:
    • key: []byte - The key to be copied into the arena.
  • Returns: uint32 - The arena offset of the copied key.

getNode func

func (s *Arena) getNode(offset uint32) *node {
	// ...
}

• Purpose: Returns a pointer to the node located at the given offset in the arena. If the offset is 0, it returns nil.
  • Parameters:
    • offset: uint32 - The offset of the node in the arena.
  • Returns: *node - A pointer to the node at the given offset, or nil if the offset is 0.

getKey func

func (s *Arena) getKey(offset uint32, size uint16) []byte {
	return s.buf[offset : offset+uint32(size)]
}

• Purpose: Returns a byte slice representing the key located at the given offset and size in the arena.
  • Parameters:
    • offset: uint32 - The offset of the key in the arena.
    • size: uint16 - The size of the key in bytes.
  • Returns: []byte - The byte slice representing the key.

getVal func

func (s *Arena) getVal(offset uint32, size uint32) (ret y.ValueStruct) {
	ret.Decode(s.buf[offset : offset+size])
	return
}

• Purpose: Returns a y.ValueStruct located at the given offset and size in the arena.
  • Parameters:
    • offset: uint32 - The offset of the value in the arena.
    • size: uint32 - The size of the value in bytes.
  • Returns: y.ValueStruct - The y.ValueStruct at the given offset.

getNodeOffset func

func (s *Arena) getNodeOffset(nd *node) uint32 {
	if nd == nil {
		return 0
	}

	return uint32(uintptr(unsafe.Pointer(nd)) - uintptr(unsafe.Pointer(&s.buf[0])))
}

• Purpose: Returns the offset of a given node in the arena. If the node is nil, it returns 0.
  • Parameters:
    • nd: *node - A pointer to the node.
  • Returns: uint32 - The offset of the node in the arena, or 0 if the node is nil.

Getting Started Relevance