Module: util.intset

Source: compiler/stage2_l0/src/util/intset.l0 Language: Dea/L0

Imports / Includes

• std.array
• std.assert
• sys.memory

Symbols

• ISET_EMPTY
• ISET_OCCUPIED
• ISET_TOMBSTONE
• ISET_DEFAULT_CAP
• _iset_slot
• iset_create
• iset_create_with_capacity
• _iset_alloc
• _iset_get_state
• _iset_set_state
• _iset_get_key
• _iset_set_key
• _iset_find
• _iset_find_insert
• _iset_needs_grow
• _iset_rehash
• iset_add
• iset_has
• iset_remove
• iset_size
• iset_capacity
• iset_clear
• iset_free
• IntSet

Variable ISET_EMPTY

let ISET_EMPTY: byte = 0

Variable ISET_OCCUPIED

let ISET_OCCUPIED: byte = 1

Variable ISET_TOMBSTONE

let ISET_TOMBSTONE: byte = 2

Variable ISET_DEFAULT_CAP

let ISET_DEFAULT_CAP: int = 16

Function _iset_slot

func _iset_slot(key: int, cap: int) -> int

Compute a non-negative slot index from a key and a power-of-2 capacity.

Parameters:

• key: The key value.
• cap: The capacity of the set.

Returns: The calculated slot index.

Function iset_create

func iset_create() -> IntSet*

Creates a new IntSet with default capacity.

Returns: A pointer to the newly created IntSet.

Function iset_create_with_capacity

func iset_create_with_capacity(min_cap: int) -> IntSet*

Creates a new IntSet with at least the specified capacity.

Parameters:

• min_cap: The minimum capacity for the set.

Returns: A pointer to the newly created IntSet.

Function _iset_alloc

func _iset_alloc(cap: int) -> IntSet*

Internal allocator for IntSet .

Parameters:

• cap: The capacity to allocate.

Returns: A pointer to the newly allocated IntSet.

Function _iset_get_state

func _iset_get_state(self: IntSet*, i: int) -> byte

Returns the state of the specified slot.

Parameters:

• self: The pointer to the IntSet.
• i: The slot index.

Returns: The state byte of the slot.

Function _iset_set_state

func _iset_set_state(self: IntSet*, i: int, s: byte)

Sets the state of the specified slot.

Parameters:

• self: The pointer to the IntSet.
• i: The slot index.
• s: The state byte to set.

Function _iset_get_key

func _iset_get_key(self: IntSet*, i: int) -> int

Returns the key of the specified slot.

Parameters:

• self: The pointer to the IntSet.
• i: The slot index.

Returns: The key value of the slot.

Function _iset_set_key

func _iset_set_key(self: IntSet*, i: int, key: int)

Sets the key of the specified slot.

Parameters:

• self: The pointer to the IntSet.
• i: The slot index.
• key: The key value to set.

Function _iset_find

func _iset_find(self: IntSet*, key: int) -> int

Find the slot index of an existing key.

Parameters:

• self: The pointer to the IntSet.
• key: The key to find.

Returns: The slot index if found, or -1 if not in the set.

Function _iset_find_insert

func _iset_find_insert(self: IntSet*, key: int) -> int

Find the first non-occupied slot for insertion.

Parameters:

• self: The pointer to the IntSet.
• key: The key to insert.

Returns: The available slot index.

Function _iset_needs_grow

func _iset_needs_grow(self: IntSet*) -> bool

Checks if the set needs to grow.

Parameters:

• self: The pointer to the IntSet.

Returns: True if growth is needed, false otherwise.

Function _iset_rehash

func _iset_rehash(self: IntSet*)

Rehashes the set to a larger capacity.

Parameters:

• self: The pointer to the IntSet.

Function iset_add

func iset_add(self: IntSet*, key: int) -> bool

Add an integer to the set.

Returns true if the integer was newly added, false if already present.

Parameters:

• self: The pointer to the IntSet.
• key: The key to add.

Returns: True if the integer was newly added, false otherwise.

Function iset_has

func iset_has(self: IntSet*, key: int) -> bool

Check whether an integer is in the set.

Parameters:

• self: The pointer to the IntSet.
• key: The key to check.

Returns: True if the integer is in the set, false otherwise.

Function iset_remove

func iset_remove(self: IntSet*, key: int) -> bool

Remove an integer from the set.

Returns true if it was found and removed.

Parameters:

• self: The pointer to the IntSet.
• key: The key to remove.

Returns: True if found and removed, false otherwise.

Function iset_size

func iset_size(self: IntSet*) -> int

Returns the number of entries in the set.

Parameters:

• self: The pointer to the IntSet.

Returns: The count of elements.

Function iset_capacity

func iset_capacity(self: IntSet*) -> int

Returns the current capacity of the set.

Parameters:

• self: The pointer to the IntSet.

Returns: The capacity.

Function iset_clear

func iset_clear(self: IntSet*)

Remove all entries from the set.

Parameters:

• self: The pointer to the IntSet.

Function iset_free

func iset_free(self: IntSet*)

Free the set and all backing storage.

Parameters:

• self: The pointer to the IntSet to free.

Struct IntSet

IntSet is an open-addressing hash set of integers with linear probing.

Struct-of-arrays: states, keys.

IntSet Field capacity

capacity: int

IntSet Field count

count: int

IntSet Field tomb_count

tomb_count: int

IntSet Field states

states: ArrayBase*

IntSet Field keys

keys: ArrayBase*