list

Documentation

Index

• Constants
• Variables
• type Address
• type IntegerList
  • func NewIntegerList(capacity int) *IntegerList
  • func (list *IntegerList) Add(value int64) (Address, error)
  • func (list *IntegerList) Empty() bool
  • func (list *IntegerList) Get(getAddr Address) (int64, error)
  • func (list *IntegerList) PeekHead() (int64, error)
  • func (list *IntegerList) Remove(removeAddr Address) error
  • func (list *IntegerList) Size() int

Constants

const (
	// Null refers to the null list address
	Null = Address(-1)
)

Variables

var (
	// ErrEmpty indicates that the list is empty
	ErrEmpty = errors.New("list is empty")
	// ErrCapacity indicates that the list is out of capacity
	ErrCapacity = errors.New("list out of capacity")
	// ErrAddrOutOfRange indicates the provided address is out of range
	ErrAddrOutOfRange = errors.New("list address out of range")
	// ErrAddrMissingValue indicates that the requested address does not contain any value
	ErrAddrMissingValue = errors.New("list address missing value")
)

Types

type Address

type Address int

Address refers to the internal address for a list item

type IntegerList

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

IntegerList refers to a linked list of integers with fixed maximum capacity

func NewIntegerList

func NewIntegerList(capacity int) *IntegerList

NewIntegerList returns a linked list of integers with a fixed capacity this list is tailor made to keep track of out of order message offsets while processing kafka messages. Following are the allowed operations on this list:

Add(int64):

Adds the given value to the end of list. Returns an address where this
value is stored within the list. This address must be provided to remove
this item from the list later

Remove(listAddr):

Removes the item with the given address from the list. Returns address out
of range error if the address is invalid. The provided address is the address
previously received from an Add operation

PeekHead():

Returns the value at the head of the list without removing the item from the list
This operation is used to identify the same commit level during periodic checkpoints

Note: This list implementation uses math.MinInt64 as a special sentinel value

Implementation Notes: The underlying implementation uses a fixed size array where each item in the array is a linked list node. In addition to the array, there is also a free list which also refers to the same backing array i.e. the implementation uses an intrusive free list This implementation choice is chosen for the following reasons:

• No dynamic memory allocation needed
• Array based list is very cache friendly
• With this list, keeping track of out of order offsets is O(1) overhead per message

func (*IntegerList) Add

func (list *IntegerList) Add(value int64) (Address, error)

Add adds the value to the end of list. Returns the address where this value is stored on success

func (*IntegerList) Empty

func (list *IntegerList) Empty() bool

Empty returns true if the list is empty

func (*IntegerList) Get

func (list *IntegerList) Get(getAddr Address) (int64, error)

Get returns the value at the given address

func (*IntegerList) PeekHead

func (list *IntegerList) PeekHead() (int64, error)

PeekHead returns the value at the head of the list if the list is not empty. If the list empty, error is returned

func (*IntegerList) Remove

func (list *IntegerList) Remove(removeAddr Address) error

Remove removes the item stored at the specified address from the list

func (*IntegerList) Size

func (list *IntegerList) Size() int

Size returns the size of the list