代码

#include "router.h"// #include <inc/netlab_internal.hpp>
#include <arpa/inet.h>
#include <assert.h>
#include <memory.h>
#include <stdint.h>
#include <stdio.h>
#include <stdlib.h>
#include <string.h>

struct TreeBitmapNode {
    // 31..25 are bitmap bits
    uint32_t internal;
    uint32_t extending;
};

class TreeBitmap
{
private:
    typedef RoutingTableEntry E;
    TreeBitmapNode *nodes;
    E *entries;
    const int NodeDivide = 24;
    int Maxsize;

public:
    int maxEntries;
    int maxNodes;
    TreeBitmap(int MaxSize);
    void insert(const RoutingTableEntry *e);
    RoutingTableEntry *query(uint32_t addr);
    ~TreeBitmap();
};

TreeBitmap *tree;

TreeBitmap::TreeBitmap(int MaxSize)
{
    MaxSize = MaxSize + 1;
    Maxsize = MaxSize;
    nodes = (TreeBitmapNode *)malloc(40 * MaxSize * sizeof(TreeBitmapNode));
    entries = (RoutingTableEntry *)malloc(40 * MaxSize * sizeof(E));
    maxNodes = 1 + 8;
    maxEntries = 7;
    nodes[0].internal = 0;
    nodes[0].extending = 1;
}

TreeBitmap::~TreeBitmap()
{
    free(nodes);
    free(entries);
}

void TreeBitmap::insert(const RoutingTableEntry *e)
{
    TreeBitmapNode *cur = &nodes[0];
    // Bits [NodeDivide..31] are bitmaps
    int i;
    int pos, child_start;
    for (i = 32 - 3; i > 0; i -= 3) {
        // 32..0; totally 33 levels
        int prefix = (e->addr >> i) & 0x7;
        if (i < 32 - e->len) {
            int sublevel = 32 - e->len - i; // [1, 3]
            assert(sublevel >= 1 && sublevel <= 3);
            pos = ((prefix + 0x8) >> sublevel) - 1; // [0, 6]
            child_start = cur->internal & ((1 << NodeDivide) - 1);
            break;
        } else {
            uint32_t bitmask = 1 << (prefix + NodeDivide);
            int child_start = cur->extending & ((1 << NodeDivide) - 1);
            assert(child_start + prefix < maxNodes);
            TreeBitmapNode *child = &nodes[child_start + prefix];
            // printf("%d\n", child_start + prefix);
            if (!(cur->extending & bitmask)) {
                cur->extending |= bitmask;
                // initialize child
                child->internal = maxEntries;
                child->extending = maxNodes;
                if (i >= 3) maxNodes += 8;
                maxEntries += 7;
            }
            cur = child;
        }
    }
    if (i <= 0) {
        // 30 <= e->len <= 32
        int prefix = e->addr & 0x3;
        int sublevel = 32 - e->len;
        pos = ((prefix + 0x4) >> sublevel) - 1;
        child_start = cur->internal & ((1 << NodeDivide) - 1);
    }
    assert(pos >= 0 && pos <= 6);
    assert(child_start + pos < maxNodes);
    cur->internal |= 1 << (pos + NodeDivide);
    RoutingTableEntry *child = &entries[child_start + pos];
    memcpy(child, e, sizeof(RoutingTableEntry));
    // if (nodes[3566].extending & (1 << 22)) {
    //     printf("@*#$&@#\n");
    // }
}

RoutingTableEntry *TreeBitmap::query(uint32_t addr)
{
    RoutingTableEntry *ret = nullptr;
    int masklen = -1;
    TreeBitmapNode *cur = &nodes[0];
    for (int i = 32 - 3; i > 0; i -= 3) {
        int prefix = (addr >> i) & 0x7;
        // pos = 1..7
        for (int pos = (prefix + 8) >> 1, k = 1; pos; pos >>= 1, k++) {
            int pos1 = pos - 1;
            if (cur->internal & (1 << (pos1 + NodeDivide))) {
                masklen = 32 - i - k;
                int child_start = cur->internal & ((1 << NodeDivide) - 1);
                ret = &entries[child_start + pos1];
                break;
            }
        }
        {
            uint32_t bitmask = 1 << (prefix + NodeDivide);
            int child_start = cur->extending & ((1 << NodeDivide) - 1);
            assert(child_start + prefix < maxNodes);
            TreeBitmapNode *child = &nodes[child_start + prefix];
            if (!(cur->extending & bitmask)) {
                return ret;
            }
            cur = child;
        }
    }
    int prefix = addr & 0x3;
    for (int pos = prefix + 4, k = 2; pos; pos >>= 1, k--) {
        int pos1 = pos - 1;
        if (cur->internal & (1 << (pos1 + NodeDivide))) {
            masklen = k;
            int child_start = cur->internal & ((1 << NodeDivide) - 1);
            ret = &entries[child_start + pos1];
            break;
        }
    }
    return ret;
}

void init(int n, int q, const RoutingTableEntry *a)
{
    tree = new TreeBitmap(n);
    for (int i = 0; i < n; i++) {
        RoutingTableEntry tmp_entry = {
            .addr = ntohl(a[i].addr),
            .len = (unsigned char)a[i].len,
            .nexthop = ntohl(a[i].nexthop),
        };
        tree->insert(&tmp_entry);
    }
}

unsigned query(unsigned addr)
{
    RoutingTableEntry *entry = tree->query(ntohl(addr));
    if (entry) {
        return ntohl(entry->nexthop);
    }
    return 0;
}

评测结果