提交记录 14372


用户 题目 状态 得分 用时 内存 语言 代码长度
t4rf9 router32. 测测你的路由器 Compile Error 0 0 ns 0 KB C++ 8.31 KB
提交时间 评测时间
2020-09-25 00:30:10 2020-09-25 00:30:11
#include "router.h"


typedef struct TrieNode {
    TrieNode *children[2] = {NULL, NULL};
    int8_t depth = 0;
    int8_t size = 0;
    bool is_entry = false;
    uint32_t addr = 0;
    uint32_t if_index = 0;
    uint32_t nexthop = 0;
} TrieNode;

TrieNode root;

void initialize_TrieNode(TrieNode *node, uint32_t addr, uint32_t if_index, uint32_t nexthop,
                         int8_t depth, int8_t size, bool isItem) {
    node->addr = addr;
    node->if_index = if_index;
    node->nexthop = nexthop;
    node->depth = depth;
    node->size = size;
    node->is_entry = isItem;
}

/**
 * @brief 插入/删除一条路由表表项
 * @param insert 如果要插入则为 true ,要删除则为 false
 * @param entry 要插入/删除的表项
 *
 * 插入时如果已经存在一条 addr 和 len 都相同的表项,则替换掉原有的。
 * 删除时按照 addr 和 len **精确** 匹配。
 */
void update(bool insert, RoutingTableEntry entry) {
    uint32_t addr = ntohl(entry.addr);
    int8_t len = entry.len;
    uint32_t if_index = entry.if_index;
    uint32_t nexthop = entry.nexthop;

    TrieNode *curr_node = &root;
    TrieNode *prev_node;
    if (insert) {
        uint32_t mask = 0x80000000;
        for (int8_t i = 0; i < len; ++i) {
            int8_t entry_bit = (addr & mask) >> (31 - i);
            if (i == curr_node->depth + curr_node->size) { // reaching the end of a node
                prev_node = curr_node;
                curr_node = curr_node->children[entry_bit];
            }
            if (curr_node == NULL) {
                curr_node = (TrieNode *) malloc(sizeof(TrieNode));
                initialize_TrieNode(curr_node, addr, if_index, nexthop, i, len - i, true);
                prev_node->children[entry_bit] = curr_node;
                return;
            }

            int8_t curr_node_bit = (curr_node->addr & mask) >> (31 - i);
            if (entry_bit != curr_node_bit) { // split due to mismatching
                TrieNode *entry_node = (TrieNode *) malloc(sizeof(TrieNode));
                initialize_TrieNode(entry_node, addr, if_index, nexthop, i, len - i, true);

                uint32_t curr_size = i - curr_node->depth;

                TrieNode *next_node = (TrieNode *) malloc(sizeof(TrieNode));
                initialize_TrieNode(next_node, curr_node->addr, curr_node->if_index, curr_node->nexthop,
                                    i, curr_node->size - curr_size, curr_node->is_entry);
                next_node->children[0] = curr_node->children[0];
                next_node->children[1] = curr_node->children[1];

                curr_node->children[curr_node_bit] = next_node;
                curr_node->children[entry_bit] = entry_node;

                curr_node->size = curr_size;
                curr_node->is_entry = false;
                return;
            }
            mask >>= 1;
        }
        if (len == curr_node->depth + curr_node->size) { // reaching the end of a node, unnecessary to split, replace
            curr_node->if_index = if_index;
            curr_node->nexthop = nexthop;
            curr_node->is_entry = true;
        } else { // node splitting: split a longer chain
            int8_t next_node_bit = (curr_node->addr & mask) >> (31 - len);
            TrieNode *next_node = (TrieNode *) malloc(sizeof(TrieNode));
            uint32_t curr_size = len - curr_node->depth;
            initialize_TrieNode(next_node, curr_node->addr, curr_node->if_index, curr_node->nexthop,
                                len, curr_node->size - curr_size, curr_node->is_entry);
            next_node->children[0] = curr_node->children[0];
            next_node->children[1] = curr_node->children[1];

            curr_node->children[next_node_bit] = next_node;
            curr_node->children[1 - next_node_bit] = NULL;

            curr_node->addr = addr;
            curr_node->if_index = if_index;
            curr_node->nexthop = nexthop;
            curr_node->size = curr_size;
            curr_node->is_entry = true;
        }
    } else { // deletion
        uint32_t mask = 0x80000000;
        int8_t entry_bit;
        int8_t curr_node_bit;
        int8_t curr_node_rank;
        for (int8_t i = 0; i < len; ++i) {
            entry_bit = (addr & mask) >> (31 - i);
            if (i == curr_node->depth + curr_node->size) { // reaching the end of a node
                prev_node = curr_node;
                curr_node = curr_node->children[entry_bit];
                curr_node_rank = entry_bit;
                if (curr_node == NULL) {
                    return;
                }
            }

            curr_node_bit = (curr_node->addr & mask) >> (31 - i);
            if (entry_bit != curr_node_bit) {
                return;
            }

            mask >>= 1;
        }
        if (len == curr_node->depth + curr_node->size) { // found, delete
            if (curr_node == &root) {
                root.is_entry = false;
                return;
            }
            if (curr_node->children[0]) {
                curr_node->addr = curr_node->children[0]->addr;
                if (curr_node->children[1]) { // 2 children
                    curr_node->is_entry = false;
                } else { // 1 child
                    curr_node->size += curr_node->children[0]->size;
                    curr_node->if_index = curr_node->children[0]->if_index;
                    curr_node->nexthop = curr_node->children[0]->nexthop;
                    curr_node->is_entry = curr_node->children[0]->is_entry;
                    free(curr_node->children[0]);
                    curr_node->children[0] = NULL;
                }
            } else {
                if (curr_node->children[1]) { // 1 child
                    curr_node->addr = curr_node->children[1]->addr;
                    curr_node->size += curr_node->children[1]->size;
                    curr_node->if_index = curr_node->children[1]->if_index;
                    curr_node->nexthop = curr_node->children[1]->nexthop;
                    curr_node->is_entry = curr_node->children[1]->is_entry;
                    free(curr_node->children[1]);
                    curr_node->children[1] = NULL;
                } else { // no child
                    prev_node->children[curr_node_rank] = NULL;
                    free(curr_node);

                    if (!prev_node->is_entry && prev_node != &root) {
                        TrieNode *other = prev_node->children[1 - curr_node_rank];
                        prev_node->addr = other->addr;
                        prev_node->size += other->size;
                        prev_node->if_index = other->if_index;
                        prev_node->nexthop = other->nexthop;
                        prev_node->children[0] = other->children[0];
                        prev_node->children[1] = other->children[1];
                        free(other);
                    }
                }
            }
        }
    }
}

/**
 * @brief 进行一次路由表的查询,按照最长前缀匹配原则
 * @param addr 需要查询的目标地址,网络字节序
 * @param nexthop 如果查询到目标,把表项的 nexthop 写入
 * @param if_index 如果查询到目标,把表项的 if_index 写入
 * @return 查到则返回 true ,没查到则返回 false
 */
bool prefix_query(uint32_t addr, uint32_t *nexthop, uint32_t *if_index) {
    uint32_t nexthop_tmp, if_index_tmp, is_entry_tmp = false;
    addr = ntohl(addr);
    uint32_t mask = 0x80000000;
    TrieNode *prev_node;
    TrieNode *curr_node = &root;
    for (int8_t i = 0; i < 32; ++i, mask >>= 1) {
        uint8_t entry_bit = (addr & mask) >> (31 - i);
        if (i == curr_node->depth + curr_node->size) { // reaching the end of a node
            if (curr_node->is_entry) {
                nexthop_tmp = curr_node->nexthop;
                if_index_tmp = curr_node->if_index;
                is_entry_tmp = true;
            }

            curr_node = curr_node->children[entry_bit];
            if (curr_node == NULL) {
                *nexthop = nexthop_tmp;
                *if_index = if_index_tmp;
                return is_entry_tmp;
            }
        }

        uint8_t curr_node_bit = (curr_node->addr & mask) >> (31 - i);
        if (entry_bit != curr_node_bit) {
            *nexthop = nexthop_tmp;
            *if_index = if_index_tmp;
            return is_entry_tmp;
        }
    }
    *nexthop = curr_node->nexthop;
    *if_index = curr_node->if_index;
    return curr_node->is_entry;
}


void init(int n, int q, const RoutingTableEntry *a) {
	for (int i = 0; i < n; ++i) {
            update(true, a[i]);
        }
}

unsigned query(unsigned addr) {
        unsigned nexthop, if_index;
        bool res = prefix_query(addr, &nexthop, &if_index);
	return res && nexthop;
}

CompilationN/AN/ACompile ErrorScore: N/A


Judge Duck Online | 评测鸭在线
Server Time: 2020-10-31 11:52:12 | Loaded in 1 ms | Server Status
个人娱乐项目,仅供学习交流使用