plag/plageq.c

#include <stdio.h>
#include <sys/mman.h>
#include <string.h>
#include <errno.h>

#include "config.h"
#include "lib.h"

#define DEPTHB ((int)((STRICT_MAX_DEPTH)+7)/8)
#define DEPTHL ((DEPTHB)*8)

struct node {
	pos_t a[2];
	uint8_t b[DEPTHB];
};
typedef struct node *iptree;
typedef void (*bitsfun)(bits, mask_t, mask_t, mask_t);

void clearb(uint8_t *b) {
	bzero(b, DEPTHB);
}

void setb(uint8_t *b, int n, int i) {
	int p = n >> 3;
	if (p >= DEPTHB) return;
	if (i) {
		b[p] |= 1 << (n & 0x7);
	} else {
		b[p] &= ~(1 << (n & 0x7));
	}
}

int getb(uint8_t *b, int n) {
	int p = n >> 3;
	if (p >= DEPTHB) return 0;
	int i = b[p] & (1 << (n & 0x7));
	return i ? 1 : 0;
}

iptree iptree_new(pos_t size) {
	// use mmap to get pages lazily and zeroed
	iptree t = mmap(0, size * sizeof(struct node), PROT_READ|PROT_WRITE, MAP_PRIVATE|MAP_ANONYMOUS, -1, 0);
	if (t == MAP_FAILED) error(1, errno, "iptree_new: mmap failed");
	// use 2 queues of free nodes
	t[0].a[0] = 1; // start of continuous range
	t[0].a[1] = 0; // pointer to a chain of free nodes
	t[size - 1].a[0] = 1; // end of countinous range marker
	return t;
}

pos_t iptree_popfree(iptree t) {
	pos_t f;
	if (t[0].a[1]) {
		// try from chain first
		f = t[0].a[1];
		t[0].a[1] = t[f].a[0]; // shift pointer to the next node
		t[f].a[0] = 0; // clear popped element
	} else if (t[0].a[0]) {
		// then try if something is left in continuous range
		f = t[0].a[0]; // start of the range
		if (t[f].a[0]) {
			// this is the last element
			t[0].a[0] = 0;
			t[f].a[0] = 0; // celar popped element
		} else {
			// more elements are there in the range
			++(t[0].a[0]);
		}
	} else {
		if (!f) error(1, 0, "iptree_popfree: no free nodes left");
	}
	return f;
}

void iptree_fold(iptree t, pos_t h, mask_t m) {
	// check if we can fold
	for (int i = 0; i < 2; ++i) {
		pos_t j = t[h].a[i];
		if (!j || !getb(t[j].b, m - 1)) return;
	}
	setb(t[h].b, m, 1);
}

void iptree_add_new(iptree t, pos_t h, bits b, mask_t m) {
	if (m) {
		// there are bits left
		int l = b[0];  // our bit is left
		int r = 1 - l; // sibling bit is right
		// allocate next node element
		pos_t jl = iptree_popfree(t);
		// fill current node
		t[h].a[l] = jl;
		// recurse to add other bits
		iptree_add_new(t, jl, b + 1, m - 1);
		// check if we can fold
		iptree_fold(t, h, m);
	} else {
		// no bits left, this node is terminal
		setb(t[h].b, 0, 1);
	}
}

void iptree_add_rec(iptree t, pos_t h, bits b, mask_t m) {
	if (m) {
		// bits to check are left
		int l = b[0];  // our bit is left
		pos_t jl = t[h].a[l]; // left subtree head
		if (jl) {
			// tree for our bit is not empty, recurse
			iptree_add_rec(t, jl, b + 1, m - 1);
		} else {
			// tree for our bit is missing, fill new subtree
			iptree_add_new(t, h, b, m);
		}
		// check if we can fold
		iptree_fold(t, h, m);
	} else {
		// no bits left, mark this mask
		setb(t[h].b, 0, 1);
	}
}

void iptree_traverse_rec(iptree t, bitsfun f, pos_t h, bits ip, bits mask_b, mask_t m) {
	if (!h) return;

	int l = MIN(IPMAXLEN + 1 - m, DEPTHL);
	bit_t b[l];
	if (l < DEPTHL) {
		if (l > 0) memcpy(b, mask_b, sizeof(b));
	} else {
		memcpy(b, mask_b, sizeof(b) - sizeof(bit_t));
		b[l - 1] = 0;
	}

	// find sequences of folded masks folded from lower levels
	for (int c1 = 0; c1 < l; ++c1) {
		// skip if mask was processed or is missing in tree
		if (b[c1] || !getb(t[h].b, c1)) continue;
		// we found first mask to process
		b[c1] = 1; // mark it as processed
		// look for the end of the masks interval
		int c2 = c1 + 1;
		for (c2 = c1 + 1; c2 < l; ++c2) {
			// this time check masks in tree only
			if (!getb(t[h].b, c2)) break;
			b[c2] = 1; // mark it as processed
		}
		// print prefix with found masks interval
		f(ip, m, m + c1, m + c2 - 1);
		// jump to the end of the interval
		// b[c2] is zero anyway, so ++c1 in "for" will not hurt
		c1 = c2;
	}

	// traverse subtrees
	for (int i = 0; i < 2; ++i) {
		pos_t j = t[h].a[i];
		// if subtree exists
		if (j) {
			ip[m] = i; // set ip bit
			// recurse
			iptree_traverse_rec(t, f, j, ip, b + 1, m + 1);
		}
	}
}

void iptree_traverse(iptree t, pos_t h, bitsfun f) {
	bit_t ip[IPMAXLEN]; // ip bits
	bit_t b[DEPTHL]; // processed masks bits
	bzero(b, sizeof(b));
	// call recursive traversal
	iptree_traverse_rec(t, f, h, ip, b, 0);
}

void print4(bits b, mask_t m, mask_t m1, mask_t m2) {
	char s_ip[BUFLEN];
	bits2ip4(b, m, s_ip, BUFLEN);
	if (m == m1 && m1 == m2) puts(s_ip);
	else printf("%s{%d,%d}\n", s_ip, m1, m2);
}

void print6(bits b, mask_t m, mask_t m1, mask_t m2) {
	char s_ip[BUFLEN];
	bits2ip6(b, m, s_ip, BUFLEN);
	if (m == m1 && m1 == m2) puts(s_ip);
	else printf("%s{%d,%d}\n", s_ip, m1, m2);
}

double nodes2mb(pos_t n) {
	return sizeof(struct node) * (double)n / (double)(1 << 20);
}

int main(int argc, const char *argv[]) {
	init_err();

	bit_t b[IPMAXLEN];
	mask_t m;
	char s[BUFLEN];

	iptree t = iptree_new(SIZE);
	pos_t ip4 = iptree_popfree(t);
	pos_t ip6 = iptree_popfree(t);

	while (1) {
		if (!fgets(s, BUFLEN, stdin)) {
			if (!feof(stdin)) error(1, errno, "input");
			break;
		}
		int l = strlen(s);
		if (l && s[l - 1] == '\n') s[--l] = 0;
		if (!l) continue;
		if (!strchr(s, ':')) {
			// ipv4
			ip42bits(s, b, &m);
			iptree_add_rec(t, ip4, b, m);
		} else {
			// ipv6
			ip62bits(s, b, &m);
			iptree_add_rec(t, ip6, b, m);
		}
	}

	iptree_traverse(t, ip4, print4);
	iptree_traverse(t, ip6, print6);

	pos_t maxpos = t[0].a[0] ? t[0].a[0] : SIZE;
	double mb_used = nodes2mb(maxpos);
	double mb_all = nodes2mb(SIZE);
	fprintf(stderr, "max nodes: %.2f%%, %d / %d, %.2fMB / %.2fMB\n", maxpos / (double)SIZE * 100.0, maxpos, SIZE, mb_used, mb_all);

	return 0;
}