Module: std.hashset

Source: compiler/shared/l0/stdlib/std/hashset.l0 Language: Dea/L0

Imports / Includes

• std.vector
• std.array
• std.string
• std.assert
• sys.hash
• sys.memory
• sys.rt

Symbols

• HS_EMPTY
• HS_OCCUPIED
• HS_TOMBSTONE
• HS_DEFAULT_CAP
• _hs_slot
• ss_create
• ss_create_with_capacity
• _ss_alloc
• _ss_get_state
• _ss_set_state
• _ss_get_hash
• _ss_set_hash
• _ss_get_key
• _ss_set_key_retain
• _ss_release_key
• _ss_find
• _ss_find_insert
• _ss_needs_grow
• _ss_rehash
• ss_add
• ss_has
• ss_remove
• ss_size
• ss_capacity
• ss_clear
• ss_to_vector
• ss_free
• ss_slot_occupied
• ss_slot_key
• StringSet

Variable HS_EMPTY

let HS_EMPTY: byte = 0

Variable HS_OCCUPIED

let HS_OCCUPIED: byte = 1

Variable HS_TOMBSTONE

let HS_TOMBSTONE: byte = 2

Variable HS_DEFAULT_CAP

let HS_DEFAULT_CAP: int = 16

Function _hs_slot

func _hs_slot(h: int, cap: int) -> int

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

Parameters:

• h: The hash value.
• cap: The capacity of the hash set.

Returns: The calculated slot index.

Function ss_create

func ss_create() -> StringSet*

Creates a new StringSet with default capacity.

Returns: A pointer to the newly created StringSet.

Function ss_create_with_capacity

func ss_create_with_capacity(min_cap: int) -> StringSet*

Creates a new StringSet with at least the specified capacity.

Parameters:

• min_cap: The minimum capacity for the set.

Returns: A pointer to the newly created StringSet.

Function _ss_alloc

func _ss_alloc(cap: int) -> StringSet*

Internal allocator for StringSet .

Parameters:

• cap: The capacity to allocate.

Returns: A pointer to the newly allocated StringSet.

Function _ss_get_state

func _ss_get_state(self: StringSet*, i: int) -> byte

Returns the state of the specified slot.

Parameters:

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

Returns: The state byte of the slot.

Function _ss_set_state

func _ss_set_state(self: StringSet*, i: int, s: byte)

Sets the state of the specified slot.

Parameters:

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

Function _ss_get_hash

func _ss_get_hash(self: StringSet*, i: int) -> int

Returns the hash value of the specified slot.

Parameters:

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

Returns: The hash value of the slot.

Function _ss_set_hash

func _ss_set_hash(self: StringSet*, i: int, h: int)

Sets the hash value of the specified slot.

Parameters:

• self: The pointer to the StringSet.
• i: The slot index.
• h: The hash value to set.

Function _ss_get_key

func _ss_get_key(self: StringSet*, i: int) -> string

Returns the key string of the specified slot.

Parameters:

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

Returns: The key string of the slot.

Function _ss_set_key_retain

func _ss_set_key_retain(self: StringSet*, i: int, k: string)

Sets the key string of the specified slot and retains it.

Parameters:

• self: The pointer to the StringSet.
• i: The slot index.
• k: The key string to set.

Function _ss_release_key

func _ss_release_key(self: StringSet*, i: int)

Releases the key string of the specified slot and zaps it.

Parameters:

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

Function _ss_find

func _ss_find(self: StringSet*, key: string, h: int) -> int

Find the slot index of an existing key.

Parameters:

• self: The pointer to the StringSet.
• key: The key string to find.
• h: The hash value of the key.

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

Function _ss_find_insert

func _ss_find_insert(self: StringSet*, h: int) -> int

Find the first non-occupied slot for insertion.

Parameters:

• self: The pointer to the StringSet.
• h: The hash value of the key.

Returns: The available slot index.

Function _ss_needs_grow

func _ss_needs_grow(self: StringSet*) -> bool

Checks if the set needs to grow.

Parameters:

• self: The pointer to the StringSet.

Returns: True if growth is needed, false otherwise.

Function _ss_rehash

func _ss_rehash(self: StringSet*)

Rehashes the set to a larger capacity.

Parameters:

• self: The pointer to the StringSet.

Function ss_add

func ss_add(self: StringSet*, key: string) -> bool

Add a string to the set.

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

Parameters:

• self: The pointer to the StringSet.
• key: The key string to add.

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

Function ss_has

func ss_has(self: StringSet*, key: string) -> bool

Check whether a string is in the set.

Parameters:

• self: The pointer to the StringSet.
• key: The key string to check.

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

Function ss_remove

func ss_remove(self: StringSet*, key: string) -> bool

Remove a string from the set.

Returns true if it was found and removed.

Parameters:

• self: The pointer to the StringSet.
• key: The key string to remove.

Returns: True if found and removed, false otherwise.

Function ss_size

func ss_size(self: StringSet*) -> int

Returns the number of entries in the set.

Parameters:

• self: The pointer to the StringSet.

Returns: The count of elements.

Function ss_capacity

func ss_capacity(self: StringSet*) -> int

Returns the current capacity of the set.

Parameters:

• self: The pointer to the StringSet.

Returns: The capacity.

Function ss_clear

func ss_clear(self: StringSet*)

Remove all entries from the set.

Releases all key strings.

Parameters:

• self: The pointer to the StringSet.

Function ss_to_vector

func ss_to_vector(self: StringSet*) -> StringVector*

Collect all elements into a new StringVector.

Caller owns the result and must sv_free() it.

Parameters:

• self: The pointer to the StringSet.

Returns: A new StringVector containing all elements.

Function ss_free

func ss_free(self: StringSet*)

Free the set and all backing storage.

Releases all key strings.

Parameters:

• self: The pointer to the StringSet to free.

Function ss_slot_occupied

func ss_slot_occupied(self: StringSet*, i: int) -> bool

Checks if a slot is occupied.

Parameters:

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

Returns: True if occupied, false otherwise.

Function ss_slot_key

func ss_slot_key(self: StringSet*, i: int) -> string

Returns the key at the specified slot.

Parameters:

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

Returns: The key string.

Struct StringSet

StringSet is an open-addressing hash set with linear probing.

Struct-of-arrays: states, hashes, keys.

StringSet Field capacity

capacity: int

StringSet Field count

count: int

StringSet Field tomb_count

tomb_count: int

StringSet Field states

states: ArrayBase*

StringSet Field hashes

hashes: ArrayBase*

StringSet Field keys

keys: ArrayBase*