array_slab.go

/*
 * Atree - Scalable Arrays and Ordered Maps
 *
 * Copyright Flow Foundation
 *
 * Licensed under the Apache License, Version 2.0 (the "License");
 * you may not use this file except in compliance with the License.
 * You may obtain a copy of the License at
 *
 *   http://www.apache.org/licenses/LICENSE-2.0
 *
 * Unless required by applicable law or agreed to in writing, software
 * distributed under the License is distributed on an "AS IS" BASIS,
 * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
 * See the License for the specific language governing permissions and
 * limitations under the License.
 */

package atree

type ArraySlabHeader struct {
	slabID SlabID // id is used to retrieve slab from storage
	size   uint32 // size is used to split and merge; leaf: size of all element; internal: size of all headers
	count  uint32 // count is used to lookup element; leaf: number of elements; internal: number of elements in all its headers
	// mutationCount is a per-slab counter that is bumped when this slab is detached as root.
	// It enables callers to detect that their cached view of the root is stale.
	// Element-level mutations and non-root structural changes do NOT bump the counter.
	// In-memory only (NOT encoded).
	mutationCount uint64
}

type ArraySlab interface {
	Slab

	Get(storage SlabStorage, index uint64) (Storable, error)
	Set(storage SlabStorage, address Address, index uint64, value Value) (Storable, error)
	Insert(storage SlabStorage, address Address, index uint64, value Value) error
	Remove(storage SlabStorage, index uint64) (Storable, error)

	IsData() bool

	IsFull() bool
	IsUnderflow() (uint32, bool)
	CanLendToLeft(size uint32) bool
	CanLendToRight(size uint32) bool

	SetSlabID(SlabID)

	Header() ArraySlabHeader

	// MutationCount returns a per-slab counter that is bumped when this slab is detached as root.
	// It enables callers to detect that their cached view of the root is stale.
	// Element-level mutations and non-root structural changes do NOT bump the counter.
	// In-memory only (NOT encoded).
	MutationCount() uint64
	// BumpMutationCount bumps the mutation count, which should be called when this slab is detached as root.
	// See MutationCount() for details.
	BumpMutationCount()

	ExtraData() *ArrayExtraData
	RemoveExtraData() *ArrayExtraData
	SetExtraData(*ArrayExtraData)

	PopIterate(SlabStorage, ArrayPopIterationFunc) error

	// canCopyWithoutSlabID returns true if
	// - All elements can be copied, and
	// - Slab doesn't have any references to other slabs (such as next slab ID).
	canCopyWithoutSlabID() bool
	// copyWithNewSlabID copies the ArraySlab and uses the given newID as the SlabID.
	copyWithNewSlabID(newID SlabID) (ArraySlab, error)

	Inlined() bool
	Inlinable(maxInlineSize uint32) bool
	Inline(SlabStorage) error
	Uninline(SlabStorage) error
}

func getArraySlab(storage SlabStorage, id SlabID) (ArraySlab, error) {
	slab, found, err := storage.Retrieve(id)
	if err != nil {
		// err can be an external error because storage is an interface.
		return nil, wrapErrorAsExternalErrorIfNeeded(err)
	}
	if !found {
		return nil, NewSlabNotFoundErrorf(id, "array slab not found")
	}
	arraySlab, ok := slab.(ArraySlab)
	if !ok {
		return nil, NewSlabDataErrorf("slab %s isn't ArraySlab", id)
	}
	return arraySlab, nil
}

func firstArrayDataSlab(storage SlabStorage, slab ArraySlab) (*ArrayDataSlab, error) {
	switch slab := slab.(type) {
	case *ArrayDataSlab:
		return slab, nil

	case *ArrayMetaDataSlab:
		firstChildID := slab.childrenHeaders[0].slabID
		firstChild, err := getArraySlab(storage, firstChildID)
		if err != nil {
			// Don't need to wrap error as external error because err is already categorized by getArraySlab().
			return nil, err
		}
		// Don't need to wrap error as external error because err is already categorized by firstArrayDataSlab().
		return firstArrayDataSlab(storage, firstChild)

	default:
		return nil, NewUnreachableError()
	}
}

// getArrayDataSlabWithIndex returns data slab containing element at specified index
func getArrayDataSlabWithIndex(storage SlabStorage, slab ArraySlab, index uint64) (*ArrayDataSlab, uint64, error) {
	if slab.IsData() {
		dataSlab := slab.(*ArrayDataSlab)
		if index >= uint64(len(dataSlab.elements)) {
			return nil, 0, NewIndexOutOfBoundsError(index, 0, uint64(len(dataSlab.elements)))
		}
		return dataSlab, index, nil
	}

	metaSlab := slab.(*ArrayMetaDataSlab)
	_, adjustedIndex, childID, err := metaSlab.childSlabIndexInfo(index)
	if err != nil {
		// Don't need to wrap error as external error because err is already categorized by ArrayMetadataSlab.childSlabIndexInfo().
		return nil, 0, err
	}

	child, err := getArraySlab(storage, childID)
	if err != nil {
		// Don't need to wrap error as external error because err is already categorized by getArraySlab().
		return nil, 0, err
	}

	// Don't need to wrap error as external error because err is already categorized by getArrayDataSlabWithIndex().
	return getArrayDataSlabWithIndex(storage, child, adjustedIndex)
}