代码

// 这是 trie 算法！！！不是 lulea ！！！

#include "router.h"
#include <stdint.h>
#include <assert.h>
#include <string.h>
#include <arpa/inet.h>
#include <algorithm>

/*
	Lulea Algorithm
	1. maptable (10.6KB + 128KB)
	2. map nexthops
	3. expand prefix tree // TODO
	4. build level 1
	5. build level 2
	6. build level 3
*/

/*
	Maptable:
	Stores [0,678) x [0,16) -> [0,16) : 10.6KB
	Stores [0,2^16) -> [0,678) : 128KB
*/

const int MAPTABLE_MAX_SIZE = 678;

int maptable_size;
uint8_t maptable[MAPTABLE_MAX_SIZE][16];
uint16_t maptable_index_map[1 << 16];

/*
	Init maptable
	1. dfs all possible 16-bit tries
	2. calculate prefix sums
*/

inline void maptable_add(int vec) {
	maptable_index_map[vec] = maptable_size;
	int cnt = 0;
	for (int i = 0; i < 16; i++) {
		cnt += (vec >> i) & 1;
		maptable[maptable_size][i] = cnt;
	}
	++maptable_size;
}

inline bool maptable_element_check(int vec, int bits = 16) {
	if (vec == 1) return 1;
	if (bits == 1) return 0;
	bits >>= 1;
	int mask = (1 << bits) - 1;
	return maptable_element_check(vec & mask, bits)
		&& maptable_element_check(vec >> bits, bits);
}

void init_maptable() {
	maptable_size = 0;
	for (int i = 1; i < 1 << 16; i++) {
		if (maptable_element_check(i)) {
			maptable_add(i);
		}
	}
}

/*
	Map nexthops to [0,2^16)
	1. sort nexthops
	2. unique
	3. lowerbound
*/

uint32_t *unique_nexthops, n_unique_nexthops;
uint16_t *nexthop_indices;

void init_map_nexthops(int n, const RoutingTableEntry *a) {
	uint32_t *nexthops = new uint32_t[n];
	for (int i = 0; i < n; i++) {
		nexthops[i] = a[i].nexthop;
	}
	
	std::sort(nexthops, nexthops + n);
	n_unique_nexthops = std::unique(nexthops, nexthops + n) - nexthops;
	
	unique_nexthops = new uint32_t[n_unique_nexthops + 1];  // +1 for zero fallback
	memcpy(unique_nexthops + 1, nexthops, n_unique_nexthops * sizeof(uint32_t));
	
	delete []nexthops;
	
	// Build indices
	nexthop_indices = new uint16_t[n];
	for (int i = 0; i < n; i++) {
		nexthop_indices[i] = (uint16_t) (
			std::lower_bound(unique_nexthops + 1,
				unique_nexthops + n_unique_nexthops + 1,
				a[i].nexthop)
			- unique_nexthops
		);
	}
}

/*
	Expanding the prefix tree:
	1. build prefix tree (trie) // TODO
	2. dfs and expand the trie
*/

struct trie_node {
	trie_node *s[2];
	uint16_t data;  // TODO!!!!
};

trie_node *trie_nodes_head, *trie_nodes_tail;
trie_node *trie_root;

const int TRIE_NODE_ALLOC_COUNT = 10000;

inline trie_node *new_trie_node() {
	if (trie_nodes_head == trie_nodes_tail) {
		trie_nodes_head = new trie_node[TRIE_NODE_ALLOC_COUNT];
		trie_nodes_tail = trie_nodes_head + TRIE_NODE_ALLOC_COUNT;
	}
	
	return trie_nodes_head++;
}

inline trie_node *new_trie_node_blank() {
	trie_node *ret = new_trie_node();
	ret->s[0] = ret->s[1] = NULL;
	ret->data = 0;
	return ret;
}

inline void trie_insert(trie_node *root, uint32_t val, int len, uint16_t data) {
	for (int i = 0; i < len; i++) {
		int tmp = (val >> 31) & 1;
		val <<= 1;
		if (!root->s[tmp]) {
			root = root->s[tmp] = new_trie_node_blank();
		} else {
			root = root->s[tmp];
		}
	}
	
	root->data = data;
}

void init_prefix_tree(int n, const RoutingTableEntry *a) {
	trie_root = new_trie_node_blank();
	
	for (int i = 0; i < n; i++) {
		trie_insert(trie_root, htonl(a[i].addr), (uint32_t) a[i].len,
			nexthop_indices[i]);
	}
	
	// TODO pushdown !!!
}

uint32_t trie_query(trie_node *root, uint32_t val) {
	uint16_t cur_data = root->data;
	
	for (int i = 0; i < 32; i++) {
		int tmp = (val >> 31) & 1;
		val <<= 1;
		root = root->s[tmp];
		
		if (!root) {
			break;
		} else if (root->data) {
			cur_data = root->data;
		}
	}
	
	return unique_nexthops[cur_data];
}

void init(int n, int q, const RoutingTableEntry *a) {
	init_maptable();
	assert(maptable_size == 677);
	
	init_map_nexthops(n, a);
	assert(n_unique_nexthops <= 1 << 16);
	
	init_prefix_tree(n, a);
	// TODO!!!
}

unsigned query(unsigned addr) {
	return trie_query(trie_root, htonl(addr));
}

评测结果