array

Documentation

Index

• Constants
• func BlockCap[T any](n int) int
• func BlockLen[T any]() int
• type Array
  • func (a *Array[T]) Cap() int
  • func (a *Array[T]) Empty() bool
  • func (a *Array[T]) Get(i int) T
  • func (a *Array[T]) Len() int
  • func (a *Array[T]) Next() (ptr *T, index int)
  • func (a *Array[T]) NextWithPool(pool *Pool[T]) (ptr *T, index int)
  • func (a *Array[T]) Pop() T
  • func (a *Array[T]) PopWithPool(pool *Pool[T]) T
  • func (a *Array[T]) Ptr(i int) *T
  • func (a *Array[T]) Push(v T)
  • func (a *Array[T]) PushPtr(v *T)
  • func (a *Array[T]) PushPtrWithPool(v *T, pool *Pool[T])
  • func (a *Array[T]) PushWithPool(v T, pool *Pool[T])
  • func (a *Array[T]) Reset(pool *Pool[T])
  • func (a *Array[T]) ShiftBlocks(n int) bool
  • func (a *Array[T]) ShiftBlocksWithPool(n int, pool *Pool[T]) bool
• type Pool

Constants

const BlockSize = 64 * 1024

BlockSize is the memory allocation size in bytes for each block slot. This is converted into a slice capacity using the BlockLen function.

Functions

func BlockCap

func BlockCap[T any](n int) int

BlockCap rounds n up to the nearest BlockLen.

func BlockLen

func BlockLen[T any]() int

BlockLen calculates the entry count required to fill a slice of BlockSize bytes. Because the type is generic, we can't use const. However, as of go 1.20, the compiler will turn this into a constant expression. For example, BlockLen[int]() turns into 8192. On x86_64, this can be seen in Next:

CALL    runtime.makeslice(SB)
MOVL    $8192, CX
MOVL    $8192, DI

... and fast integer division/modulus in Ptr:

MOVQ    BX, SI
SARQ    $13, BX
ANDQ    $-8192, SI

Types

type Array

type Array[T any] struct {
	// contains filtered or unexported fields
}

Array works similarly to a Go slice, however the allocation is performed in blocks rather than a single sequential allocation. This means that appends do not need to fully copy prior entries during reallocation, and entries have pointer stability throughout their lifetime.

func (*Array[T]) Cap

func (a *Array[T]) Cap() int

Cap returns the current capacity of the array without further reallocation.

func (*Array[T]) Empty

func (a *Array[T]) Empty() bool

Empty reports whether if the array contains no entries.

func (*Array[T]) Get

func (a *Array[T]) Get(i int) T

Get obtains the value of an entry at a specific offset. Like a Go slice this results in a panic if the value is outside the array bounds.

func (*Array[T]) Len

func (a *Array[T]) Len() int

Len returns the number of entries added to the array.

func (*Array[T]) Next

func (a *Array[T]) Next() (ptr *T, index int)

Next obtains a pointer to the next slot, allocating new space if needed. The returned pointer will be zero-initialized.

func (*Array[T]) NextWithPool

func (a *Array[T]) NextWithPool(pool *Pool[T]) (ptr *T, index int)

NextWithPool obtains a pointer to the next slot, allocating new space from the optionally provided pool if needed. The returned pointer will be zero-initialized.

func (*Array[T]) Pop

func (a *Array[T]) Pop() T

Pop removes the last item from the array and returns the value.

func (*Array[T]) PopWithPool

func (a *Array[T]) PopWithPool(pool *Pool[T]) T

PopWithPool removes the last item from the array. If the popped value is the last in a block, the block will be removed and returned to the pool.

func (*Array[T]) Ptr

func (a *Array[T]) Ptr(i int) *T

Ptr obtains the pointer to a value for an entry at a specific offset. The returned pointer is guaranteed not to change until the index is popped from the array. Like a Go slice this results in a panic if the value is outside the array bounds.

func (*Array[T]) Push

func (a *Array[T]) Push(v T)

Push appends a value into the array.

func (*Array[T]) PushPtr

func (a *Array[T]) PushPtr(v *T)

PushPtr appends a value into the array by copying a value from an existing memory address.

func (*Array[T]) PushPtrWithPool

func (a *Array[T]) PushPtrWithPool(v *T, pool *Pool[T])

PushPtrWithPool appends a value into the array by copying a value from an existing memory address. If a new block needs to be allocated, it will attempt to reuse an existing one provided by the pool.

func (*Array[T]) PushWithPool

func (a *Array[T]) PushWithPool(v T, pool *Pool[T])

PushWithPool appends a value into the array, pulling a block from the provided pool when needed.

func (*Array[T]) Reset

func (a *Array[T]) Reset(pool *Pool[T])

Reset removes all entries and releases all blocks into the pool if provided.

func (*Array[T]) ShiftBlocks

func (a *Array[T]) ShiftBlocks(n int) bool

ShiftBlocks removes `n` number of blocks (`n * BlockLen[T]()` entries) from the beginning of the array, shifting the remaining blocks down. If `n` exceeds the number of blocks in the array, none are removed and false is returned.

func (*Array[T]) ShiftBlocksWithPool

func (a *Array[T]) ShiftBlocksWithPool(n int, pool *Pool[T]) bool

ShiftBlocksWithPool removes whole blocks from the array like ShiftBlocks. If a pool is provided, the removed blocks will be given back to it.

When using a pool, it is important to ensure any entries that contain heap allocations are cleared. For example, the entire blocks may be cleared at once:

type Item { values []int }
func removeBlocks(items array.Pool[Item], blocks int, pool *array.Pool[Item]) {
	n := array.BlockLen[Item] * blocks
	for i := 0; i < n; i++ {
		items.Ptr(i).values = nil
	}
	items.ShiftBlocksWithPool(blocks, &pool)
}

type Pool

type Pool[T any] struct {
	// contains filtered or unexported fields
}

Pool is a memory pool for reusing block allocations. The pool can be shared across any BucketArray of the same type.