/* Optimal routing-table compression.
*
* Let f be the LPM function of the given table and S the emitted subset.
* Any valid S must realise f with its own LPM. Claim: the minimum table keeps
* exactly those entries whose nexthop differs from the value inherited from the
* nearest enclosing entry; dropping an entry whose value *equals* the inherited
* one never changes the effective value for any deeper entry, so all such drops
* are independent and mandatory, and no entry with a different value can be
* dropped (its exclusive region would then resolve to the ancestor's value).
* Hence the greedy is optimal.
*
* The input is already sorted by (addr, len) == DFS preorder of the prefix trie,
* so one stack sweep does it in O(n) without any allocation per entry. */
#include "routecomp.h"
#include <stdlib.h>
typedef unsigned u32;
typedef unsigned long long u64;
void compress(const RoutingTableEntry *tbl, int n, RoutingTableEntry **tbl_comp, int *n_comp) {
RoutingTableEntry *out;
int cap = n > 0 ? n : 1;
out = (RoutingTableEntry *)malloc((size_t)cap * sizeof(RoutingTableEntry));
if (!out) { *tbl_comp = 0; *n_comp = 0; return; }
static u64 s_end[64];
static u32 s_nh[64];
int sp = 0, cnt = 0;
for (int i = 0; i < n; i++) {
u32 addr = tbl[i].addr;
int len = (int)tbl[i].len;
u32 nh = tbl[i].nexthop;
u32 base;
u64 width;
if (len <= 0) { base = 0; width = 1ULL << 32; }
else if (len >= 32) { base = addr; width = 1; }
else {
u32 mask = (u32)((1ULL << (32 - len)) - 1);
base = addr & ~mask;
width = (u64)mask + 1;
}
u64 end = (u64)base + width;
while (sp > 0 && s_end[sp - 1] <= (u64)base) sp--;
u32 inh = (sp > 0) ? s_nh[sp - 1] : 0u;
if (nh != inh && cnt < 1000) {
RoutingTableEntry *e = &out[cnt++];
e->addr = base;
e->len = (unsigned char)len;
e->pad[0] = 0; e->pad[1] = 0; e->pad[2] = 0;
e->nexthop = nh;
}
s_end[sp] = end;
s_nh[sp] = nh;
sp++;
}
*tbl_comp = out;
*n_comp = cnt;
}