BTreeMap API Reference

Self-balancing ordered map using B-tree (stores i64 key-value pairs in sorted order)

Import

U std/btreemap
U std/option

Overview

The btreemap module provides a B-tree based ordered map implementation with:

• Sorted key storage (in-order traversal)
• Self-balancing structure (min degree t=2)
• Efficient search, insert, and iteration
• Free function API (no methods)
• Optional error handling via Option<T>

Note: This implementation uses a free function API, not struct methods. The map is represented as an opaque pointer (i64).

Constants

• MIN_DEGREE: 2 (minimum degree t, so each node has at most 2*t-1 = 3 keys)
• MAX_KEYS: 3
• MAX_CHILDREN: 4

Data Structure

Internal Node Layout

Each B-tree node is 96 bytes:

• [0] = num_keys (number of keys in this node)
• [8] = is_leaf (1 = leaf, 0 = internal)
• [16] = key[0]
• [24] = value[0]
• [32] = key[1]
• [40] = value[1]
• [48] = key[2]
• [56] = value[2]
• [64] = child[0] (pointer)
• [72] = child[1]
• [80] = child[2]
• [88] = child[3]

Map Layout

• [0] = root node pointer
• [8] = size (number of entries)

Core Functions

Creation and Access

Get Operations

Insert Operations

Min/Max

Iteration

Internal Helper Functions

Node Management

Search

Insertion

Traversal

Memory Management

Examples

Basic Usage

U std/btreemap

F main() -> i64 {
    # Create new map
    map := btreemap_new()

    # Insert key-value pairs
    btreemap_put(map, 5, 50)
    btreemap_put(map, 2, 20)
    btreemap_put(map, 8, 80)
    btreemap_put(map, 1, 10)

    # Get values
    val := btreemap_get(map, 5)  # Returns 50

    # Check existence
    exists := btreemap_contains(map, 2)  # Returns 1
    not_exists := btreemap_contains(map, 99)  # Returns 0

    # Get size
    size := btreemap_size(map)  # Returns 4

    # Free memory
    btreemap_free(map)
    0
}

Using Option for Error Handling

U std/btreemap
U std/option

F main() -> i64 {
    map := btreemap_new()

    btreemap_put(map, 42, 100)

    # Use Option-based get
    opt := btreemap_get_opt(map, 42)

    M opt {
        Some(v) => {
            # Key found, v is the value
            v  # 100
        },
        None => {
            # Key not found
            0
        }
    }
}

Min/Max Keys

U std/btreemap

F main() -> i64 {
    map := btreemap_new()

    btreemap_put(map, 10, 100)
    btreemap_put(map, 5, 50)
    btreemap_put(map, 20, 200)
    btreemap_put(map, 15, 150)

    # Keys are stored in sorted order
    min := btreemap_min_key(map)  # Returns 5
    max := btreemap_max_key(map)  # Returns 20

    btreemap_free(map)
    0
}

Update Existing Keys

U std/btreemap

F main() -> i64 {
    map := btreemap_new()

    # Insert
    btreemap_put(map, 1, 10)
    val1 := btreemap_get(map, 1)  # Returns 10

    # Update (same key, new value)
    btreemap_put(map, 1, 20)
    val2 := btreemap_get(map, 1)  # Returns 20

    # Size doesn't change on update
    size := btreemap_size(map)  # Still 1

    btreemap_free(map)
    0
}

Iteration with Callback

U std/btreemap

# Callback function receives (key, value, context)
# Returns 0 to continue, 1 to stop
F print_entry(key: i64, value: i64, context: i64) -> i64 {
    # Print or process key-value pair
    # Note: actual implementation would need function pointer support
    0  # Continue
}

F main() -> i64 {
    map := btreemap_new()

    btreemap_put(map, 3, 30)
    btreemap_put(map, 1, 10)
    btreemap_put(map, 2, 20)

    # Traverse in sorted order: (1,10), (2,20), (3,30)
    btreemap_foreach(map, print_entry, 0)

    btreemap_free(map)
    0
}

Building a Sorted Map

U std/btreemap

F main() -> i64 {
    map := btreemap_new()

    # Insert in random order
    btreemap_put(map, 50, 500)
    btreemap_put(map, 10, 100)
    btreemap_put(map, 30, 300)
    btreemap_put(map, 20, 200)
    btreemap_put(map, 40, 400)

    # B-tree automatically maintains sorted order
    # In-order traversal will visit: 10, 20, 30, 40, 50

    # Access minimum and maximum
    first_key := btreemap_min_key(map)   # 10
    last_key := btreemap_max_key(map)    # 50

    btreemap_free(map)
    0
}

Checking for Keys Before Access

U std/btreemap

F safe_get(map: i64, key: i64) -> i64 {
    I btreemap_contains(map, key) == 1 {
        btreemap_get(map, key)
    } E {
        # Return default value
        -1
    }
}

F main() -> i64 {
    map := btreemap_new()
    btreemap_put(map, 5, 50)

    val1 := safe_get(map, 5)   # Returns 50
    val2 := safe_get(map, 99)  # Returns -1

    btreemap_free(map)
    0
}

Memory Management

U std/btreemap

F main() -> i64 {
    # Create map
    map := btreemap_new()

    # Insert many entries
    i := 0
    L i < 100 {
        btreemap_put(map, i, i * 10)
        i = i + 1
    }

    # Verify size
    size := btreemap_size(map)  # Should be 100

    # IMPORTANT: Always free when done to prevent memory leaks
    btreemap_free(map)

    0
}