Collections API

The collections module provides data structures for storing and accessing data efficiently.

AVL Tree

The AVL Tree is a self-balancing binary search tree with O(log n) complexity for insertion, deletion, and search operations.

Types

type myrtx_avl_tree_t: Opaque structure representing an AVL tree.

type myrtx_avl_node_t: Opaque structure representing a node in the AVL tree.

type myrtx_avl_compare_function

Function pointer type for comparing keys in the AVL tree.

typedef int (*myrtx_avl_compare_function)(const void* key1, const void* key2, void* user_data);

type myrtx_avl_free_function

Function pointer type for freeing keys and values when nodes are removed.

typedef void (*myrtx_avl_free_function)(void* key, void* value, void* user_data);

type myrtx_avl_visit_function

Function pointer type for traversing the tree.

typedef bool (*myrtx_avl_visit_function)(const void* key, void* value, void* user_data);

Creation and Destruction

myrtx_avl_tree_t *myrtx_avl_tree_create(myrtx_arena_t *arena, myrtx_avl_compare_function compare_function, void *user_data)

Creates a new AVL tree.

Parameters:

arena – Optional arena allocator (NULL for malloc/free)
compare_function – Function for comparing keys
user_data – User-defined data passed to the compare function

Returns:

Pointer to the new AVL tree or NULL on error

void myrtx_avl_tree_free(myrtx_avl_tree_t *tree, myrtx_avl_free_function free_function, void *user_data)

Frees an AVL tree.

Parameters:

tree – Pointer to the AVL tree
free_function – Optional function to free keys and values (NULL if not needed)
user_data – User-defined data for the free function

Insertion and Removal

bool myrtx_avl_tree_insert(myrtx_avl_tree_t *tree, void *key, void *value, void **existing_value)

Inserts or updates a key-value pair in the AVL tree.

Parameters:

tree – Pointer to the AVL tree
key – Pointer to the key
value – Pointer to the value
existing_value – Pointer to store the previous value (NULL if not needed)

Returns:

true on success, false on error

bool myrtx_avl_tree_remove(myrtx_avl_tree_t *tree, const void *key, void **key_out, void **value_out)

Removes an entry from the AVL tree.

Parameters:

tree – Pointer to the AVL tree
key – Pointer to the key to remove
key_out – Pointer to store the removed key (NULL if not needed)
value_out – Pointer to store the removed value (NULL if not needed)

Returns:

true if the key was found and removed, false otherwise

Lookup Functions

bool myrtx_avl_tree_find(const myrtx_avl_tree_t *tree, const void *key, void **value_out)

Searches for a value in the AVL tree by key.

Parameters:

tree – Pointer to the AVL tree
key – Pointer to the key to search for
value_out – Pointer to store the found value (NULL if not needed)

Returns:

true if the key was found, false otherwise

bool myrtx_avl_tree_contains(const myrtx_avl_tree_t *tree, const void *key)

Checks if the AVL tree contains a specific key.

Parameters:

tree – Pointer to the AVL tree
key – Pointer to the key to search for

Returns:

true if the key was found, false otherwise

Traversal Functions

void myrtx_avl_tree_traverse_inorder(const myrtx_avl_tree_t *tree, myrtx_avl_visit_function visit_function, void *user_data)

Traverses the AVL tree in-order.

Parameters:

tree – Pointer to the AVL tree
visit_function – Function called for each node
user_data – User-defined data for the visit function

void myrtx_avl_tree_traverse_preorder(const myrtx_avl_tree_t *tree, myrtx_avl_visit_function visit_function, void *user_data)

Traverses the AVL tree in pre-order.

Parameters:

tree – Pointer to the AVL tree
visit_function – Function called for each node
user_data – User-defined data for the visit function

void myrtx_avl_tree_traverse_postorder(const myrtx_avl_tree_t *tree, myrtx_avl_visit_function visit_function, void *user_data)

Traverses the AVL tree in post-order.

Parameters:

tree – Pointer to the AVL tree
visit_function – Function called for each node
user_data – User-defined data for the visit function

Utility Functions

size_t myrtx_avl_tree_size(const myrtx_avl_tree_t *tree)

Returns the number of entries in the AVL tree.

Parameters:

tree – Pointer to the AVL tree

Returns:

Number of entries

bool myrtx_avl_tree_is_empty(const myrtx_avl_tree_t *tree)

Checks if the AVL tree is empty.

Parameters:

tree – Pointer to the AVL tree

Returns:

true if the tree is empty, false otherwise

size_t myrtx_avl_tree_height(const myrtx_avl_tree_t *tree)

Returns the height of the AVL tree.

Parameters:

tree – Pointer to the AVL tree

Returns:

Height of the tree (0 for empty tree)

Min/Max Functions

bool myrtx_avl_tree_min(const myrtx_avl_tree_t *tree, void **key_out, void **value_out)

Finds the smallest key in the AVL tree.

Parameters:

tree – Pointer to the AVL tree
key_out – Pointer to store the smallest key (NULL if not needed)
value_out – Pointer to store the associated value (NULL if not needed)

Returns:

true if the tree is not empty, false otherwise

bool myrtx_avl_tree_max(const myrtx_avl_tree_t *tree, void **key_out, void **value_out)

Finds the largest key in the AVL tree.

Parameters:

tree – Pointer to the AVL tree
key_out – Pointer to store the largest key (NULL if not needed)
value_out – Pointer to store the associated value (NULL if not needed)

Returns:

true if the tree is not empty, false otherwise

Predefined Comparison Functions

int myrtx_avl_compare_strings(const void *key1, const void *key2, void *user_data)

Standard comparison function for string keys.

Parameters:

key1 – Pointer to the first string
key2 – Pointer to the second string
user_data – Not used

Returns:

Comparison result as from strcmp

int myrtx_avl_compare_integers(const void *key1, const void *key2, void *user_data)

Standard comparison function for integer keys.

Parameters:

key1 – Pointer to the first integer
key2 – Pointer to the second integer
user_data – Not used

Returns:

Comparison result (<0, 0, >0)

Hash Table

The Hash Table is a high-performance implementation for key-value storage with constant time complexity for most operations.

Types

type myrtx_hashtable_t: Opaque structure representing a hash table.

type myrtx_hashtable_entry_t: Opaque structure representing an entry in the hash table.

type myrtx_hashtable_hash_function

Function pointer type for computing hash values.

typedef uint64_t (*myrtx_hashtable_hash_function)(const void* key, size_t key_size, void* user_data);

type myrtx_hashtable_compare_function

Function pointer type for comparing keys in the hash table.

typedef bool (*myrtx_hashtable_compare_function)(const void* key1, const void* key2, size_t key_size, void* user_data);

type myrtx_hashtable_free_function

Function pointer type for freeing keys and values when entries are removed.

typedef void (*myrtx_hashtable_free_function)(void* key, void* value, void* user_data);

Creation and Destruction

myrtx_hashtable_t *myrtx_hashtable_create(myrtx_allocator_t *allocator, myrtx_hashtable_hash_function hash_function, myrtx_hashtable_compare_function compare_function, void *user_data)

Creates a new hash table.

Parameters:

allocator – The allocator to use for memory management
hash_function – Function for computing hash values
compare_function – Function for comparing keys
user_data – User-defined data passed to the hash and compare functions

Returns:

Pointer to the new hash table or NULL on error

void myrtx_hashtable_destroy(myrtx_hashtable_t *table, myrtx_hashtable_free_function free_function, void *user_data)

Frees a hash table.

Parameters:

table – Pointer to the hash table
free_function – Optional function to free keys and values (NULL if not needed)
user_data – User-defined data for the free function

Insertion and Removal

bool myrtx_hashtable_insert(myrtx_hashtable_t *table, const void *key, size_t key_size, void *value, void **existing_value)

Inserts or updates a key-value pair in the hash table.

Parameters:

table – Pointer to the hash table
key – Pointer to the key
key_size – Size of the key in bytes
value – Pointer to the value
existing_value – Pointer to store the previous value (NULL if not needed)

Returns:

true on success, false on error

bool myrtx_hashtable_remove(myrtx_hashtable_t *table, const void *key, size_t key_size, void **key_out, void **value_out)

Removes an entry from the hash table.

Parameters:

table – Pointer to the hash table
key – Pointer to the key to remove
key_size – Size of the key in bytes
key_out – Pointer to store the removed key (NULL if not needed)
value_out – Pointer to store the removed value (NULL if not needed)

Returns:

true if the key was found and removed, false otherwise

Lookup Functions

bool myrtx_hashtable_get(myrtx_hashtable_t *table, const void *key, size_t key_size, void **value_out)

Searches for a value in the hash table by key.

Parameters:

table – Pointer to the hash table
key – Pointer to the key to search for
key_size – Size of the key in bytes
value_out – Pointer to store the found value (NULL if not needed)

Returns:

true if the key was found, false otherwise

bool myrtx_hashtable_contains(myrtx_hashtable_t *table, const void *key, size_t key_size)

Checks if the hash table contains a specific key.

Parameters:

table – Pointer to the hash table
key – Pointer to the key to search for
key_size – Size of the key in bytes

Returns:

true if the key was found, false otherwise

Utility Functions

size_t myrtx_hashtable_size(const myrtx_hashtable_t *table)

Returns the number of entries in the hash table.

Parameters:

table – Pointer to the hash table

Returns:

Number of entries

bool myrtx_hashtable_is_empty(const myrtx_hashtable_t *table)

Checks if the hash table is empty.

Parameters:

table – Pointer to the hash table

Returns:

true if the table is empty, false otherwise

size_t myrtx_hashtable_capacity(const myrtx_hashtable_t *table)

Returns the current capacity of the hash table.

Parameters:

table – Pointer to the hash table

Returns:

Current capacity

Predefined Hash Functions

uint64_t myrtx_hashtable_hash_string(const void *key, size_t key_size, void *user_data)

Standard hash function for string keys.

Parameters:

key – Pointer to the string
key_size – Size of the string including null terminator
user_data – Not used

Returns:

Hash value for the string

uint64_t myrtx_hashtable_hash_integer(const void *key, size_t key_size, void *user_data)

Standard hash function for integer keys.

Parameters:

key – Pointer to the integer
key_size – Size of the integer (must be sizeof(int))
user_data – Not used

Returns:

Hash value for the integer