descriptor

Documentation

Index

• type Table
  • func (t *Table[Key, Item]) Delete(key Key)
  • func (t *Table[Key, Item]) Insert(item Item) (key Key, ok bool)
  • func (t *Table[Key, Item]) InsertAt(item Item, key Key) bool
  • func (t *Table[Key, Item]) Len() (n int)
  • func (t *Table[Key, Item]) Lookup(key Key) (item Item, found bool)
  • func (t *Table[Key, Item]) Range(f func(Key, Item) bool)
  • func (t *Table[Key, Item]) Reset()

Types

type Table

type Table[Key ~int32, Item any] struct {
	// contains filtered or unexported fields
}

Table is a data structure mapping 32 bit descriptor to items.

Negative keys are invalid.

Negative keys (e.g. -1) are invalid inputs and will return a corresponding not-found value. This matches POSIX behavior of file descriptors. See https://pubs.opengroup.org/onlinepubs/9699919799/functions/dirfd.html#tag_16_90

Data structure design

The data structure optimizes for memory density and lookup performance, trading off compute at insertion time. This is a useful compromise for the use cases we employ it with: items are usually accessed a lot more often than they are inserted, each operation requires a table lookup, so we are better off spending extra compute to insert items in the table in order to get cheaper lookups. Memory efficiency is also crucial to support scaling with programs that maintain thousands of items: having a high or non-linear memory-to-item ratio could otherwise be used as an attack vector by malicious applications attempting to damage performance of the host.

func (*Table[Key, Item]) Delete

func (t *Table[Key, Item]) Delete(key Key)

Delete deletes the item stored at the given key from the table.

func (*Table[Key, Item]) Insert

func (t *Table[Key, Item]) Insert(item Item) (key Key, ok bool)

Insert inserts the given item to the table, returning the key that it is mapped to or false if the table was full.

The method does not perform deduplication, it is possible for the same item to be inserted multiple times, each insertion will return a different key.

func (*Table[Key, Item]) InsertAt

func (t *Table[Key, Item]) InsertAt(item Item, key Key) bool

InsertAt inserts the given `item` at the item descriptor `key`. This returns false if the insert was impossible due to negative key.

func (*Table[Key, Item]) Len

func (t *Table[Key, Item]) Len() (n int)

Len returns the number of items stored in the table.

func (*Table[Key, Item]) Lookup

func (t *Table[Key, Item]) Lookup(key Key) (item Item, found bool)

Lookup returns the item associated with the given key (may be nil).

func (*Table[Key, Item]) Range

func (t *Table[Key, Item]) Range(f func(Key, Item) bool)

Range calls f for each item and its associated key in the table. The function f might return false to interupt the iteration.

func (*Table[Key, Item]) Reset

func (t *Table[Key, Item]) Reset()

Reset clears the content of the table.