/*
 * Copyright (c) 2025 Валери Владев <vdev@lavabit.com>
 *
 * Permission is hereby granted, free of charge, to any person obtaining a copy
 * of this software and associated documentation files (the "Software"), to deal
 * in the Software without restriction, including without limitation the rights
 * to use, copy, modify, merge, publish, distribute, sublicense, and/or sell
 * copies of the Software, and to permit persons to whom the Software is
 * furnished to do so, subject to the following conditions:
 *
 * The above copyright notice and this permission notice shall be included in all
 * copies or substantial portions of the Software.
 *
 * THE SOFTWARE IS PROVIDED "AS IS", WITHOUT WARRANTY OF ANY KIND, EXPRESS OR
 * IMPLIED, INCLUDING BUT NOT LIMITED TO THE WARRANTIES OF MERCHANTABILITY,
 * FITNESS FOR A PARTICULAR PURPOSE AND NONINFRINGEMENT. IN NO EVENT SHALL THE
 * AUTHORS OR COPYRIGHT HOLDERS BE LIABLE FOR ANY CLAIM, DAMAGES OR OTHER
 * LIABILITY, WHETHER IN AN ACTION OF CONTRACT, TORT OR OTHERWISE, ARISING FROM,
 * OUT OF OR IN CONNECTION WITH THE SOFTWARE OR THE USE OR OTHER DEALINGS IN THE
 * SOFTWARE.
 */

/**
 * Minimal path compression algorithm for network routes.
 * Core idea: Use bitmasks (letters_table) and bit counting (count_uper_bits)
 * to compress shared prefixes in sequences (e.g., routes [0,1,2]).
 *
 * Use case: Efficient storage of network paths in routing tables.
 * Extensions:
 * - Add search to retrieve paths and weights.
 * - Support deletion or dynamic updates.
 * - Optimize for large networks (LLA > 64).
 * - Integrate with Linux networking (e.g., iproute2).
 */

#include <stdio.h>
#include <stdlib.h>
#include <stdint.h>

#define LLA 64 // Maximum elements (limited by uint64_t)

struct node {
    uint64_t letters_table; // Bitmask for elements
    struct node* next;      // Next node
    uint32_t weight;        // Weight (e.g., latency)
};

/**
 * Counts bits set from pos+1 to LLA-1 for prefix compression.
 */
static int count_uper_bits(struct node* i, int pos) {
    int count = 0;
    for (int j = pos + 1; j < LLA; j++) {
        if (i->letters_table & (1ULL << j)) {
            count++;
        }
    }
    return count;
}

/**
 * Inserts a path with prefix compression.
 * @param root Pointer to root node.
 * @param path Array of element IDs (e.g., [0,1,2]).
 * @param path_len Length of path.
 * @param weight Weight (e.g., latency).
 */
void insert_path(struct node* root, int* path, int path_len, int weight) {
    struct node* i = root;
    for (int k = 0; k < path_len; k++) {
        int pos = path[k];
        i->letters_table |= (1ULL << pos);
        int n = count_uper_bits(i, pos);
        if (n > 0) {
            for (int j = n; j > 0; j--) {
                i = i->next;
            }
        } else {
            struct node* new_node = calloc(1, sizeof(struct node));
            if (!new_node) {
                fprintf(stderr, "Memory allocation failed\n");
                exit(1);
            }
            struct node* temp = i->next;
            i->next = new_node;
            i = i->next;
            i->next = temp;
        }
    }
    i->letters_table |= (1ULL << LLA);
    i->weight = weight;
}