代码

// 24-8 bitmap

#pragma GCC target("popcnt")

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

const uint32_t TABLE_SIZE = 16384;

uint32_t table_cnt = 0;
uint32_t table_32[TABLE_SIZE][1 << 8] __attribute__((aligned(4096)));
uint32_t table_24[1 << 24] __attribute__((aligned(4096)));
uint64_t table_24_bitmap[1 << 24 >> 6] __attribute__((aligned(4096)));  // 4 MiB
int table_24_bitsum[1 << 24 >> 6] __attribute__((aligned(4096)));  // 2 MiB
uint32_t table_24_content[1 << 24] __attribute__((aligned(4096)));  // (2N + 1)

inline void fill(uint32_t *a, int n, uint32_t val) {
	while (n >= 4) {
		a[0] = val;
		a[1] = val;
		a[2] = val;
		a[3] = val;
		n -= 4;
		a += 4;
	}
	while (n) {
		a[0] = val;
		n--;
		a++;
	}
}

inline void ins(uint32_t addr, int len, uint32_t nexthop) {
	if (len <= 24) {
		fill(table_24 + (addr >> 8), 1u << (24 - len), nexthop);
	} else {
		uint32_t &tmp = table_24[addr >> 8];
		addr &= 255u;
		
		if (tmp < -TABLE_SIZE) {
			uint32_t *tmp2 = table_32[--table_cnt + TABLE_SIZE];
			fill(tmp2, addr, tmp);
			fill(tmp2 + addr, 1u << (32 - len), nexthop);
			fill(tmp2 + addr + (1u << (32 - len)), 256 - addr - (1u << (32 - len)), tmp);
			tmp = table_cnt;
		} else {
			uint32_t *tmp2 = table_32[tmp + TABLE_SIZE];
			fill(tmp2 + addr, 1u << (32 - len), nexthop);
		}
	}
}

inline void build_bitmap(uint32_t *table, int size, uint64_t *bits, int *bitsum, uint32_t *content) {
	uint32_t last_val = table[0] + 1;
	int cur_sum = 0;
	
	for (int i = 0; i < size; i++) {
		if (!(i & 63)) {
			bitsum[i >> 6] = cur_sum;
		}
		if (table[i] != last_val) {
			bits[i >> 6] |= 1ull << (i & 63);
			++cur_sum;
			content[cur_sum] = last_val = table[i];
		}
	}
}

void init(int n, int q, const RoutingTableEntry *tbl) {
	for (int i = 0; i < n; i++) {
		ins(htonl(tbl[i].addr), tbl[i].len, tbl[i].nexthop);
	}
	
	build_bitmap(table_24, 1 << 24, table_24_bitmap, table_24_bitsum, table_24_content);
}

unsigned query(unsigned addr) {
	addr = htonl(addr);
	
	uint32_t addr_24 = addr >> 8;
	uint32_t addr_24_idx = addr_24 >> 6;
	uint32_t addr_24_bits = addr_24 & 63;
	int s1 = table_24_bitsum[addr_24_idx];
	int s2 = __builtin_popcountll(table_24_bitmap[addr_24_idx] & ((2ull << addr_24_bits) - 1ull));
	uint32_t tmp = table_24_content[s1 + s2];
	
	if (tmp >= -TABLE_SIZE) {
		return table_32[tmp + TABLE_SIZE][addr & 255u];
	} else {
		return tmp;
	}
}

评测结果