tri_insert_indicator_parse.c

#define MAX_INDICATOR_LEN 512 // Define a sane limit

void ti_insert_indicator_sparse(TrieNode *root, const char *indicator) {
    TrieNode *current = root;
    int length = strlen(indicator);

    for (int i = 0; i < length; i++) {
        char key_char = indicator[i];
        
        // 1. Search for Existing Child using Binary Search (Faster than linear)
        ChildPair *found_pair = (ChildPair *)bsearch(
            &key_char, 
            current->children, 
            current->num_children, 
            sizeof(ChildPair), 
            compare_child_pairs
        );
        
        if (found_pair != NULL) {
            // Path exists: Move to the next node and continue loop
            current = found_pair->node;
            continue;
        }
        
        // 2. Path DOES NOT exist: Prepare to insert a NEW ChildPair

        // Find the index where the new char should go to maintain sorted order
        int insert_idx = find_insertion_index(current, key_char);

        // Check for and handle array capacity limit
        if (!grow_children_array(current)) {
            fprintf(stderr, "Fatal error: Could not grow array during insertion.\n");
            return;
        }

        // 3. Shift elements using memmove (OPTIMIZATION)
        // Move all elements from insert_idx to the end, one position right
        // This creates a "hole" at insert_idx.
        if (insert_idx < current->num_children) {
            size_t bytes_to_shift = (current->num_children - insert_idx) * sizeof(ChildPair);
            
            // memmove handles overlapping memory regions safely
            memmove(
                &current->children[insert_idx + 1],  // Destination (shifted one right)
                &current->children[insert_idx],      // Source
                bytes_to_shift
            );
        }

        // 4. Create and Insert the New ChildPair
        current->children[insert_idx].key_char = key_char;
        current->children[insert_idx].node = create_sparse_trie_node(); // Create a new node!
        current->num_children++; // Increment the count

        // Move to the newly created node
        current = current->children[insert_idx].node;
    }

    // Mark the final node as the end of a complete malicious indicator
    current->is_malicious_indicator = 1;
}