hashmap.l0

hashmap.l0

Module: std.hashmap

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

Imports / Includes

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

Symbols

Variable HM_EMPTY

1

let HM_EMPTY: byte = 0

Variable HM_OCCUPIED

1

let HM_OCCUPIED: byte = 1

Variable HM_TOMBSTONE

1

let HM_TOMBSTONE: byte = 2

Variable HM_DEFAULT_CAP

1

let HM_DEFAULT_CAP: int = 16

Function _hm_slot

1

func _hm_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 table.

Returns: The calculated slot index.

Function spm_create

1

func spm_create() -> StringPtrMap*

Creates a new StringPtrMap with default capacity.

Returns: A pointer to the newly created StringPtrMap.

Function spm_create_with_capacity

1

func spm_create_with_capacity(min_cap: int) -> StringPtrMap*

Creates a new StringPtrMap with at least the specified capacity.

Parameters:

  • min_cap: The minimum capacity for the map.

Returns: A pointer to the newly created StringPtrMap.

Function _spm_alloc

1

func _spm_alloc(cap: int) -> StringPtrMap*

Internal allocator for StringPtrMap .

Parameters:

  • cap: The capacity to allocate.

Returns: A pointer to the newly allocated StringPtrMap.

Function _spm_get_state

1

func _spm_get_state(self: StringPtrMap*, i: int) -> byte

Returns the state of the specified slot.

Parameters:

Returns: The state byte of the slot.

Function _spm_set_state

1

func _spm_set_state(self: StringPtrMap*, i: int, s: byte)

Sets the state of the specified slot.

Parameters:

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

Function _spm_get_hash

1

func _spm_get_hash(self: StringPtrMap*, i: int) -> int

Returns the hash value of the specified slot.

Parameters:

Returns: The hash value of the slot.

Function _spm_set_hash

1

func _spm_set_hash(self: StringPtrMap*, i: int, h: int)

Sets the hash value of the specified slot.

Parameters:

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

Function _spm_get_key

1

func _spm_get_key(self: StringPtrMap*, i: int) -> string

Returns the key string of the specified slot.

Parameters:

Returns: The key string of the slot.

Function _spm_set_key_retain

1

func _spm_set_key_retain(self: StringPtrMap*, i: int, k: string)

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

Parameters:

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

Function _spm_release_key

1

func _spm_release_key(self: StringPtrMap*, i: int)

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

Parameters:

Function _spm_get_value

1

func _spm_get_value(self: StringPtrMap*, i: int) -> void*

Returns the value associated with the specified slot.

Parameters:

Returns: The value pointer of the slot.

Function _spm_set_value

1

func _spm_set_value(self: StringPtrMap*, i: int, v: void*)

Sets the value associated with the specified slot.

Parameters:

  • self: The pointer to the StringPtrMap.
  • i: The slot index.
  • v: The value pointer to set.

Function _spm_find

1

func _spm_find(self: StringPtrMap*, key: string, h: int) -> int

Find the slot index of an existing key.

Parameters:

  • self: The pointer to the StringPtrMap.
  • 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 map.

Function _spm_find_insert

1

func _spm_find_insert(self: StringPtrMap*, h: int) -> int

Find the first non-occupied slot for insertion.

Parameters:

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

Returns: The available slot index.

Function _spm_needs_grow

1

func _spm_needs_grow(self: StringPtrMap*) -> bool

Checks if the map needs to grow.

Parameters:

Returns: True if growth is needed, false otherwise.

Function _spm_rehash

1

func _spm_rehash(self: StringPtrMap*)

Rehashes the map to a larger capacity.

Parameters:

Function spm_put

1

func spm_put(self: StringPtrMap*, key: string, value: void*)

Insert or update a key-value pair.

Key is retained on first insertion. On update, only the value changes.

Parameters:

  • self: The pointer to the StringPtrMap.
  • key: The key string.
  • value: The value pointer.

Function spm_get

1

func spm_get(self: StringPtrMap*, key: string) -> void*?

Look up a key.

Returns the associated value, or null if not found.

Note: if null is a valid stored value, use spm_has() to disambiguate.

Parameters:

  • self: The pointer to the StringPtrMap.
  • key: The key string to look up.

Returns: The associated value pointer, or null if not found.

Function spm_has

1

func spm_has(self: StringPtrMap*, key: string) -> bool

Check whether a key exists in the map.

Parameters:

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

Returns: True if the key exists, false otherwise.

Function spm_remove

1

func spm_remove(self: StringPtrMap*, key: string) -> bool

Remove a key.

Returns true if the key was found and removed.

Parameters:

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

Returns: True if found and removed, false otherwise.

Function spm_size

1

func spm_size(self: StringPtrMap*) -> int

Returns the number of entries in the map.

Parameters:

Returns: The count of elements.

Function spm_capacity

1

func spm_capacity(self: StringPtrMap*) -> int

Returns the current capacity of the map.

Parameters:

Returns: The capacity.

Function spm_clear

1

func spm_clear(self: StringPtrMap*)

Remove all entries.

Releases all key strings.

Parameters:

Function spm_keys

1

func spm_keys(self: StringPtrMap*) -> StringVector*

Collect all keys into a new StringVector.

Caller owns the result and must sv_free() it.

Parameters:

Returns: A new StringVector containing all keys.

Function spm_free

1

func spm_free(self: StringPtrMap*)

Free the map and all backing storage.

Releases all key strings. Does NOT free values (caller-managed).

Parameters:

Function spm_slot_occupied

1

func spm_slot_occupied(self: StringPtrMap*, i: int) -> bool

Checks if a slot is occupied.

Parameters:

Returns: True if occupied, false otherwise.

Function spm_slot_key

1

func spm_slot_key(self: StringPtrMap*, i: int) -> string

Returns the key at the specified slot.

Parameters:

Returns: The key string.

Function spm_slot_value

1

func spm_slot_value(self: StringPtrMap*, i: int) -> void*

Returns the value at the specified slot.

Parameters:

Returns: The value pointer.

Function sim_create

1

func sim_create() -> StringIntMap*

Creates a new StringIntMap with default capacity.

Returns: A pointer to the newly created StringIntMap.

Function sim_create_with_capacity

1

func sim_create_with_capacity(min_cap: int) -> StringIntMap*

Creates a new StringIntMap with at least the specified capacity.

Parameters:

  • min_cap: The minimum capacity for the map.

Returns: A pointer to the newly created StringIntMap.

Function _sim_alloc

1

func _sim_alloc(cap: int) -> StringIntMap*

Internal allocator for StringIntMap .

Parameters:

  • cap: The capacity to allocate.

Returns: A pointer to the newly allocated StringIntMap.

Function _sim_get_state

1

func _sim_get_state(self: StringIntMap*, i: int) -> byte

Returns the state of the specified slot.

Parameters:

Returns: The state byte of the slot.

Function _sim_set_state

1

func _sim_set_state(self: StringIntMap*, i: int, s: byte)

Sets the state of the specified slot.

Parameters:

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

Function _sim_get_hash

1

func _sim_get_hash(self: StringIntMap*, i: int) -> int

Returns the hash value of the specified slot.

Parameters:

Returns: The hash value of the slot.

Function _sim_set_hash

1

func _sim_set_hash(self: StringIntMap*, i: int, h: int)

Sets the hash value of the specified slot.

Parameters:

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

Function _sim_get_key

1

func _sim_get_key(self: StringIntMap*, i: int) -> string

Returns the key string of the specified slot.

Parameters:

Returns: The key string of the slot.

Function _sim_set_key_retain

1

func _sim_set_key_retain(self: StringIntMap*, i: int, k: string)

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

Parameters:

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

Function _sim_release_key

1

func _sim_release_key(self: StringIntMap*, i: int)

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

Parameters:

Function _sim_get_value

1

func _sim_get_value(self: StringIntMap*, i: int) -> int

Returns the value associated with the specified slot.

Parameters:

Returns: The value of the slot.

Function _sim_set_value

1

func _sim_set_value(self: StringIntMap*, i: int, v: int)

Sets the value associated with the specified slot.

Parameters:

  • self: The pointer to the StringIntMap.
  • i: The slot index.
  • v: The value to set.

Function _sim_find

1

func _sim_find(self: StringIntMap*, key: string, h: int) -> int

Find the slot index of an existing key.

Parameters:

  • self: The pointer to the StringIntMap.
  • 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 map.

Function _sim_find_insert

1

func _sim_find_insert(self: StringIntMap*, h: int) -> int

Find the first non-occupied slot for insertion.

Parameters:

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

Returns: The available slot index.

Function _sim_needs_grow

1

func _sim_needs_grow(self: StringIntMap*) -> bool

Checks if the map needs to grow.

Parameters:

Returns: True if growth is needed, false otherwise.

Function _sim_rehash

1

func _sim_rehash(self: StringIntMap*)

Rehashes the map to a larger capacity.

Parameters:

Function sim_put

1

func sim_put(self: StringIntMap*, key: string, value: int)

Insert or update a key-value pair.

Key is retained on first insertion. On update, only the value changes.

Parameters:

  • self: The pointer to the StringIntMap.
  • key: The key string.
  • value: The value to set.

Function sim_get

1

func sim_get(self: StringIntMap*, key: string) -> int?

Look up a key.

Returns the associated value, or null if not found.

Parameters:

  • self: The pointer to the StringIntMap.
  • key: The key string to look up.

Returns: The associated value, or null if not found.

Function sim_has

1

func sim_has(self: StringIntMap*, key: string) -> bool

Check whether a key exists in the map.

Parameters:

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

Returns: True if the key exists, false otherwise.

Function sim_remove

1

func sim_remove(self: StringIntMap*, key: string) -> bool

Remove a key.

Returns true if the key was found and removed.

Parameters:

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

Returns: True if found and removed, false otherwise.

Function sim_size

1

func sim_size(self: StringIntMap*) -> int

Returns the number of entries in the map.

Parameters:

Returns: The count of elements.

Function sim_capacity

1

func sim_capacity(self: StringIntMap*) -> int

Returns the current capacity of the map.

Parameters:

Returns: The capacity.

Function sim_clear

1

func sim_clear(self: StringIntMap*)

Remove all entries.

Releases all key strings.

Parameters:

Function sim_keys

1

func sim_keys(self: StringIntMap*) -> StringVector*

Collect all keys into a new StringVector.

Caller owns the result and must sv_free() it.

Parameters:

Returns: A new StringVector containing all keys.

Function sim_free

1

func sim_free(self: StringIntMap*)

Free the map and all backing storage.

Releases all key strings.

Parameters:

Function sim_slot_occupied

1

func sim_slot_occupied(self: StringIntMap*, i: int) -> bool

Checks if a slot is occupied.

Parameters:

Returns: True if occupied, false otherwise.

Function sim_slot_key

1

func sim_slot_key(self: StringIntMap*, i: int) -> string

Returns the key at the specified slot.

Parameters:

Returns: The key string.

Function sim_slot_value

1

func sim_slot_value(self: StringIntMap*, i: int) -> int

Returns the value at the specified slot.

Parameters:

Returns: The value.

Struct StringPtrMap

StringPtrMap is an open-addressing hash table with linear probing.

Keys are ARC-managed strings (manual retain/release). Values are caller-managed void pointers.

Struct-of-arrays layout: states — byte per slot (EMPTY / OCCUPIED / TOMBSTONE) hashes — int per slot (cached hash code) keys — string per slot (ARC-managed) values — void* per slot

StringPtrMap Field capacity

1

capacity: int

StringPtrMap Field count

1

count: int

StringPtrMap Field tomb_count

1

tomb_count: int

StringPtrMap Field states

1

states: ArrayBase*

StringPtrMap Field hashes

1

hashes: ArrayBase*

StringPtrMap Field keys

1

keys: ArrayBase*

StringPtrMap Field values

1

values: ArrayBase*

Struct StringIntMap

StringIntMap stores associations between strings and integers.

Same layout and probing as StringPtrMap , but values are int instead of void*.

StringIntMap Field capacity

1

capacity: int

StringIntMap Field count

1

count: int

StringIntMap Field tomb_count

1

tomb_count: int

StringIntMap Field states

1

states: ArrayBase*

StringIntMap Field hashes

1

hashes: ArrayBase*

StringIntMap Field keys

1

keys: ArrayBase*

StringIntMap Field values

1

values: ArrayBase*