代码

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

uint32_t get_low_n(uint32_t target, int len)
{
    uint32_t result = 0;
    for (int i = 0; i < len; ++i)
    {
        result += target & (1 << i);
    }
    return result;
}

struct Node
{
    uint32_t addr;
    int len;
    uint32_t nexthop = -1; // 大端序，下一跳的 IPv4 地址
    Node *lc = nullptr;
    Node *rc = nullptr;
    Node(uint32_t addr, int len)
    {
        this->addr = addr;
        this->len = len;
    }
    Node(RoutingTableEntry entry)
    {
        addr = entry.addr;
        len = entry.len;
        nexthop = entry.nexthop;
    }
    void set(RoutingTableEntry entry)
    {
        addr = entry.addr;
        len = entry.len;
        nexthop = entry.nexthop;
    }
};

struct DictTree
{
    Node *root = nullptr;
    int match(uint32_t addr, int len, Node *node)
    {
        if (node->len == 0)
        {
            return -1;
        }
        uint32_t result = addr ^ node->addr;
        int i;
        for (i = 0; i < node->len && i < len; ++i)
        {
            if (result & (1 << i)
            {
                return i;
            }
        }
        return i;
    }

    void insert(RoutingTableEntry entry)
    {
        if (!root)
        {
            root = new Node(0, 0);
            root->lc = new Node(entry);
            root->rc = new Node(0, 0);
            return;
        }
        Node *cur = root;
        while (1)
        {
            int lmatch = match(entry.addr, entry.len, root->lc);
            int rmatch = match(entry.addr, entry.len, root->rc);
            int match_len;
            if (lmatch > rmatch)
            {
                if (lmatch == 0) // fake rc
                {
                    cur->rc->set(entry);
                    return;
                }
                else
                {
                    cur = cur->lc;
                    match_len = lmatch;
                }
            }
            else
            {
                if (rmatch == 0) //fake lc
                {
                    cur->lc->set(entry);
                    return;
                }
                else
                {
                    cur = cur->rc;
                    match_len = rmatch;
                }
            }
            entry.addr = entry.addr >> match_len;
            entry.len -= match_len;
            if (!entry.len) //match over
            {
                if (match_len == cur->len) //exactly match
                {
                    cur->nexthop = entry.nexthop;
                    return;
                }
                split(cur, match_len, entry);
                return;
            }
            if (!cur->lc) //leaf node
            {
                split(cur, match_len, entry);
                return;
            }
        }
    }
    void split(Node *cur, int match_len, RoutingTableEntry entry)
    {
        uint32_t lc_addr = cur->addr >> match_len;
        int lc_len = cur->len - match_len;
        cur->lc = new Node(lc_addr, lc_len);

        cur->len = match_len;

        cur->rc = new Node(entry);

        if (lc_len > 0)
        {
            cur->nexthop = -1;
            cur->lc->nexthop = cur->nexthop;
        }
    }
    void remove(RoutingTableEntry entry)
    {
        Node *traget = query(entry.addr, entry.len, true);
        if (traget)
        {
            traget->nexthop = -1;
        }
    }
    Node *query(uint32_t addr, int len, bool is_strict)
    {
        if (!root)
            return nullptr;
        Node *cur = root;
        Node *result = nullptr;
        int match_len;
        while (1)
        {
            int lmatch = match(addr, len, cur->lc);
            int rmatch = match(addr, len, cur->rc);
            if (lmatch <= 0 && rmatch <= 0) //fake children
                return result;
            if (lmatch > rmatch)
            {
                cur = cur->lc;
                match_len = lmatch;
            }
            else
            {
                cur = cur->rc;
                match_len = rmatch;
            }
            addr = addr >> match_len;
            len -= match_len;
            if (match_len == cur->len && cur->nexthop != -1)
            {
                if (!is_strict)
                    result = cur;
                else if (!len)
                    result = cur;
            }
            if (!len || !cur->lc) //match over || leaf node
            {
                return result;
            }
        }
    }
};

/*
  RoutingTable Entry 的定义如下：
  typedef struct {
    uint32_t addr; // 大端序，IPv4 地址
    uint32_t len; // 小端序，前缀长度
    uint32_t nexthop; // 大端序，下一跳的 IPv4 地址
  } RoutingTableEntry;

  约定 addr 和 nexthop 以 **大端序** 存储。
  这意味着 1.2.3.4 对应 0x04030201 而不是 0x01020304。
  保证 addr 仅最低 len 位可能出现非零。
  当 nexthop 为零时这是一条直连路由。
  你可以在全局变量中把路由表以一定的数据结构格式保存下来。
*/

/**
 * @brief 插入/删除一条路由表表项
 * @param insert 如果要插入则为 true ，要删除则为 false
 * @param entry 要插入/删除的表项
 *
 * 插入时如果已经存在一条 addr 和 len 都相同的表项，则替换掉原有的。
 * 删除时按照 addr 和 len **精确** 匹配。
 */
DictTree tree;

void init(int n, int q, const RoutingTableEntry *a)
{
    for (int i = 0; i < n; ++i)
    {
        RoutingTableEntry entry = a[i];
        entry.addr = get_low_n(entry.addr, entry.len);
        tree.insert(entry);
    }
}

unsigned query(unsigned addr)
{
    Node *target = tree.query(addr, 32, false);
    if (target && target->nexthop >= 0)
    {
        return target->nexthop;
    }
    return 0;
}

评测结果