bittree

package
v0.10.1-alpha.7 Latest Latest
Warning

This package is not in the latest version of its module.

 Go to latest Published: Sep 1, 2020 License: Apache-2.0 Imports: 4 Imported by: 0

Documentation

Overview

Copyright (c) Microsoft Corporation. All rights reserved. Licensed under the Apache v2.0 license.

Copyright (c) Microsoft Corporation. All rights reserved. Licensed under the Apache v2.0 license.

The BitTreeBitsetNode is a leaf node in the tree, living at the very bottom tier This structure holds a simple bitset

Copyright (c) Microsoft Corporation. All rights reserved. Licensed under the Apache v2.0 license.

Copyright (c) Microsoft Corporation. All rights reserved. Licensed under the Apache v2.0 license.

Index

Constants

View Source 
const (
	BitsPerTier = 8 // Each tear handles 8 bits of the given address
)
View Source 
const (
	BottomTierLevel = 0 // By convention, the bottom tier (the bitset tier) is always at level 0
)

Variables

This section is empty.

Functions

func ConvertBitCountToBytesCount 

func ConvertBitCountToBytesCount(bitCount uint) uint

Types

type BitMask 

type BitMask struct {
	// contains filtered or unexported fields
}

func NewBitMask 

func NewBitMask(lenInBits uint) *BitMask

func (*BitMask) GetInvertedSubMask 

func (c *BitMask) GetInvertedSubMask(bitLocationInArray uint, bitCount uint) (*big.Int, error)

func (*BitMask) GetMask 

func (c *BitMask) GetMask() *big.Int

func (*BitMask) GetMaskWithOffset 

func (c *BitMask) GetMaskWithOffset(offset int) *big.Int

func (*BitMask) GetSubMask 

func (c *BitMask) GetSubMask(bitLocationInArray uint, bitCount uint) (*big.Int, error)

type BitTree 

type BitTree struct {
	// contains filtered or unexported fields
}

func NewBitTree 

func NewBitTree(addressLengthBits uint) *BitTree

func (*BitTree) Clear 

func (c *BitTree) Clear(address *BitTreeAddress) error

func (*BitTree) ClearRange 

func (c *BitTree) ClearRange(startAddress *BitTreeAddress, endAddress *BitTreeAddress, force bool) error

func (*BitTree) Get 

func (c *BitTree) Get(address *BitTreeAddress) (bool, error)

func (*BitTree) GetNextAllocated 

func (c *BitTree) GetNextAllocated(address *BitTreeAddress) (bool, *BitTreeAddress, error)

func (*BitTree) GetNextAvailable 

func (c *BitTree) GetNextAvailable(address *BitTreeAddress) (bool, *BitTreeAddress, error)

func (*BitTree) GetPreviousAllocated 

func (c *BitTree) GetPreviousAllocated(address *BitTreeAddress) (bool, *BitTreeAddress, error)

func (*BitTree) GetPreviousAvailable 

func (c *BitTree) GetPreviousAvailable(address *BitTreeAddress) (bool, *BitTreeAddress, error)

func (*BitTree) GetRange 

func (c *BitTree) GetRange(startAddress *BitTreeAddress, endAddress *BitTreeAddress) (bool, error)

func (*BitTree) IsEmpty 

func (c *BitTree) IsEmpty() bool

func (*BitTree) IsFull 

func (c *BitTree) IsFull() bool

func (*BitTree) Set 

func (c *BitTree) Set(address *BitTreeAddress) error

func (*BitTree) SetRange 

func (c *BitTree) SetRange(startAddress *BitTreeAddress, endAddress *BitTreeAddress) error

func (*BitTree) ToJson 

func (c *BitTree) ToJson() (string, error)

type BitTreeAddress 

type BitTreeAddress struct {
	// contains filtered or unexported fields
}

func NewBitTreeAddress 

func NewBitTreeAddress(addressLengthBits uint) (c *BitTreeAddress)

func NewBitTreeAddressFromBytes 

func NewBitTreeAddressFromBytes(addressLengthBits uint, bytes []byte) (c *BitTreeAddress)

func (*BitTreeAddress) AddressAtOffset 

func (c *BitTreeAddress) AddressAtOffset(offset int) *BitTreeAddress

func (*BitTreeAddress) AsBigInt 

func (c *BitTreeAddress) AsBigInt() big.Int

func (*BitTreeAddress) Bytes 

func (c *BitTreeAddress) Bytes() []byte

func (*BitTreeAddress) Copy 

func (c *BitTreeAddress) Copy() *BitTreeAddress

func (*BitTreeAddress) EqualTo 

func (c *BitTreeAddress) EqualTo(comparand *BitTreeAddress) bool

func (*BitTreeAddress) GetAddressChunkForTier 

func (c *BitTreeAddress) GetAddressChunkForTier(tierLevel uint, bitsInTier uint) (uint, error)

Returns the address chunk that matches the given tier

func (*BitTreeAddress) GetFirstElementInTier 

func (c *BitTreeAddress) GetFirstElementInTier(tierLevel uint, bitsInTier uint) *BitTreeAddress

func (*BitTreeAddress) GetLastElementInTier 

func (c *BitTreeAddress) GetLastElementInTier(tierLevel uint, bitsInTier uint) *BitTreeAddress

func (*BitTreeAddress) GreaterOrEqualTo 

func (c *BitTreeAddress) GreaterOrEqualTo(comparand *BitTreeAddress) bool

func (*BitTreeAddress) GreaterThan 

func (c *BitTreeAddress) GreaterThan(comparand *BitTreeAddress) bool

func (*BitTreeAddress) LowerOrEqualTo 

func (c *BitTreeAddress) LowerOrEqualTo(comparand *BitTreeAddress) bool

func (*BitTreeAddress) LowerThan 

func (c *BitTreeAddress) LowerThan(comparand *BitTreeAddress) bool

func (*BitTreeAddress) MeasureOffset 

func (c *BitTreeAddress) MeasureOffset(compAddress *BitTreeAddress) int

func (*BitTreeAddress) SetAddressChunkForTier 

func (c *BitTreeAddress) SetAddressChunkForTier(tierLevel uint, chunk uint, bitsInTier uint) error

Sets a chunk of the address that matches the given tier, hence modifying the address

func (*BitTreeAddress) String 

func (c *BitTreeAddress) String() string

type BitTreeBitsetNode 

type BitTreeBitsetNode struct {
	// contains filtered or unexported fields
}

func NewTreeBitsetNode 

func NewTreeBitsetNode(tierLenBits uint) *BitTreeBitsetNode

func (*BitTreeBitsetNode) Clear 

func (c *BitTreeBitsetNode) Clear(address *BitTreeAddress) error

func (*BitTreeBitsetNode) ClearAllBits 

func (c *BitTreeBitsetNode) ClearAllBits() error

func (*BitTreeBitsetNode) ClearAllBitsAfter 

func (c *BitTreeBitsetNode) ClearAllBitsAfter(address *BitTreeAddress, force bool) error

func (*BitTreeBitsetNode) ClearAllBitsBefore 

func (c *BitTreeBitsetNode) ClearAllBitsBefore(address *BitTreeAddress, force bool) error

func (*BitTreeBitsetNode) ClearRange 

func (c *BitTreeBitsetNode) ClearRange(startAddress *BitTreeAddress, endAddress *BitTreeAddress, force bool) error

func (*BitTreeBitsetNode) CountLeadingZeroBits 

func (c *BitTreeBitsetNode) CountLeadingZeroBits() uint

func (*BitTreeBitsetNode) CountTrailingZeroBits 

func (c *BitTreeBitsetNode) CountTrailingZeroBits() uint

func (*BitTreeBitsetNode) Get 

func (c *BitTreeBitsetNode) Get(address *BitTreeAddress) (bool, error)

func (*BitTreeBitsetNode) GetAllBitsAfter 

func (c *BitTreeBitsetNode) GetAllBitsAfter(address *BitTreeAddress) (bool, error)

func (*BitTreeBitsetNode) GetAllBitsBefore 

func (c *BitTreeBitsetNode) GetAllBitsBefore(address *BitTreeAddress) (bool, error)

func (*BitTreeBitsetNode) GetNextAllocated 

func (c *BitTreeBitsetNode) GetNextAllocated(address *BitTreeAddress) (bool, *BitTreeAddress, error)

func (*BitTreeBitsetNode) GetNextAvailable 

func (c *BitTreeBitsetNode) GetNextAvailable(address *BitTreeAddress) (bool, *BitTreeAddress, error)

func (*BitTreeBitsetNode) GetPreviousAllocated 

func (c *BitTreeBitsetNode) GetPreviousAllocated(address *BitTreeAddress) (bool, *BitTreeAddress, error)

func (*BitTreeBitsetNode) GetPreviousAvailable 

func (c *BitTreeBitsetNode) GetPreviousAvailable(address *BitTreeAddress) (bool, *BitTreeAddress, error)

func (*BitTreeBitsetNode) GetRange 

func (c *BitTreeBitsetNode) GetRange(startAddress *BitTreeAddress, endAddress *BitTreeAddress) (bool, error)

func (*BitTreeBitsetNode) IsEmpty 

func (c *BitTreeBitsetNode) IsEmpty() bool

func (*BitTreeBitsetNode) IsFull 

func (c *BitTreeBitsetNode) IsFull() bool

func (*BitTreeBitsetNode) Set 

func (c *BitTreeBitsetNode) Set(address *BitTreeAddress) error

func (*BitTreeBitsetNode) SetAllBits 

func (c *BitTreeBitsetNode) SetAllBits() error

func (*BitTreeBitsetNode) SetAllBitsAfter 

func (c *BitTreeBitsetNode) SetAllBitsAfter(address *BitTreeAddress) error

func (*BitTreeBitsetNode) SetAllBitsBefore 

func (c *BitTreeBitsetNode) SetAllBitsBefore(address *BitTreeAddress) error

func (*BitTreeBitsetNode) SetRange 

func (c *BitTreeBitsetNode) SetRange(startAddress *BitTreeAddress, endAddress *BitTreeAddress) error

func (*BitTreeBitsetNode) ToJson 

func (c *BitTreeBitsetNode) ToJson() (string, error)

type BitTreeNode 

type BitTreeNode struct {
	// contains filtered or unexported fields
}

func NewTreeNode 

func NewTreeNode(remainingBits uint) *BitTreeNode

func (*BitTreeNode) Clear 

func (c *BitTreeNode) Clear(address *BitTreeAddress) error

func (*BitTreeNode) ClearAllBits 

func (c *BitTreeNode) ClearAllBits() error

func (*BitTreeNode) ClearRange 

func (c *BitTreeNode) ClearRange(startAddress *BitTreeAddress, endAddress *BitTreeAddress, force bool) error

func (*BitTreeNode) Get 

func (c *BitTreeNode) Get(address *BitTreeAddress) (bool, error)

func (*BitTreeNode) GetNextAllocated 

func (c *BitTreeNode) GetNextAllocated(startAddress *BitTreeAddress) (bool, *BitTreeAddress, error)

func (*BitTreeNode) GetNextAvailable 

func (c *BitTreeNode) GetNextAvailable(startAddress *BitTreeAddress) (bool, *BitTreeAddress, error)

func (*BitTreeNode) GetPreviousAllocated 

func (c *BitTreeNode) GetPreviousAllocated(startAddress *BitTreeAddress) (bool, *BitTreeAddress, error)

func (*BitTreeNode) GetPreviousAvailable 

func (c *BitTreeNode) GetPreviousAvailable(startAddress *BitTreeAddress) (bool, *BitTreeAddress, error)

func (*BitTreeNode) GetRange 

func (c *BitTreeNode) GetRange(startAddress *BitTreeAddress, endAddress *BitTreeAddress) (bool, error)

func (*BitTreeNode) IsEmpty 

func (c *BitTreeNode) IsEmpty() bool

func (*BitTreeNode) IsFull 

func (c *BitTreeNode) IsFull() bool

func (*BitTreeNode) Set 

func (c *BitTreeNode) Set(address *BitTreeAddress) error

func (*BitTreeNode) SetAllBits 

func (c *BitTreeNode) SetAllBits() error

func (*BitTreeNode) SetRange 

func (c *BitTreeNode) SetRange(startAddress *BitTreeAddress, endAddress *BitTreeAddress) error

func (*BitTreeNode) ToJson 

func (c *BitTreeNode) ToJson() (string, error)

type BitTreeNodeInterface 

type BitTreeNodeInterface interface {
	Set(*BitTreeAddress) error
	Clear(*BitTreeAddress) error
	Get(*BitTreeAddress) (bool, error)
	SetRange(*BitTreeAddress, *BitTreeAddress) error
	ClearRange(*BitTreeAddress, *BitTreeAddress, bool) error
	GetRange(*BitTreeAddress, *BitTreeAddress) (bool, error)
	GetNextAvailable(*BitTreeAddress) (bool, *BitTreeAddress, error)
	GetPreviousAvailable(*BitTreeAddress) (bool, *BitTreeAddress, error)
	GetNextAllocated(*BitTreeAddress) (bool, *BitTreeAddress, error)
	GetPreviousAllocated(*BitTreeAddress) (bool, *BitTreeAddress, error)
	SetAllBits() error
	ClearAllBits() error
	IsFull() bool
	IsEmpty() bool
	ToJson() (string, error)
}

type ChildNodesCallback 

type ChildNodesCallback func(childNode BitTreeNodeInterface, beginningOfSegment *BitTreeAddress, endOfSegment *BitTreeAddress) (interface{}, error, bool)

Source Files

View all Source files

Jump to

Keyboard shortcuts

? : This menu
/ : Search site
f or F : Jump to
y or Y : Canonical URL
go.dev uses cookies from Google to deliver and enhance the quality of its services and to analyze traffic. Learn more.