plag/plagmax.c

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

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

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

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 {
		error(1, 0, "iptree_popfree: no free nodes left");
	}
	return f;
}

void iptree_pushfree(iptree t, pos_t f) {
	// elements are pushed only to the pointer chain
	t[f].a[0] = t[0].a[1]; // pointer to current head
	t[f].a[1] = 0; // clear remaining fields
	t[0].a[1] = f; // redirect the pointer to new head
}

int iptree_is_term(iptree t, pos_t h) {
	return (h && !t[h].a[0] && !t[h].a[1]);
}

void iptree_sub_del(iptree t, pos_t h) {
	for (int i = 0; i < 2; ++i) {
		int j = t[h].a[i];
		if (j) iptree_sub_del(t, j);
	}
	iptree_pushfree(t, h);
}

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);
	} else {
		// no bits left, this node is terminal
		t[h].a[0] = 0;
		t[h].a[1] = 0;
	}
}

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
		int r = 1 - l; // sibling bit is right
		pos_t jl = t[h].a[l]; // left subtree head
		pos_t jr = t[h].a[r]; // right 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
			// check if this element is terminal (less specific here)
			if (!jr) return;
			// otherwise fill new subtree
			iptree_add_new(t, h, b, m);
		}
		// check if we can fold
		if (iptree_is_term(t, t[h].a[0]) && iptree_is_term(t, t[h].a[1])) {
			for (int i = 0; i < 2; ++i) {
				iptree_pushfree(t, t[h].a[i]);
				t[h].a[i] = 0;
			}
		}
	} else {
		// no bits left, this node must be terminal
		for (int i = 0; i < 2; ++i) {
			pos_t j = t[h].a[i]; // subtree head
			// delete subtree if exist
			if (j) {
				iptree_sub_del(t, j);
				t[h].a[i] = 0;
			}
		}
	}
}

void iptree_add(iptree t, pos_t h, bits b, mask_t m) {
	if (t[h].a[0]) {
		// tree is not empty already
		iptree_add_rec(t, t[h].a[0], b, m);
	} else {
		// tree is empty, initialize it
		t[h].a[0] = iptree_popfree(t);
		iptree_add_new(t, t[h].a[0], b, m);
	}
}

void iptree_traverse_rec(iptree t, bitsfun f, pos_t h, bits b, mask_t m) {
	int flag = 1;
	for (int i = 0; i < 2; ++i) {
		pos_t j = t[h].a[i];
		// if subtree exists
		if (j) {
			flag = 0; // node is not terminal
			b[m] = i; // set bit
			// recurse
			iptree_traverse_rec(t, f, j, b, m + 1);
		}
	}
	if (flag) {
		// terminal node
		f(b, m);
	}
}

void iptree_traverse(iptree t, pos_t h, bitsfun f) {
	bit_t b[IPMAXLEN];
	if (t[h].a[0]) {
		// tree is not empty
		iptree_traverse_rec(t, f, t[h].a[0], b, 0);
	}
}

void print4(bits b, mask_t m) {
	char s_ip[BUFLEN];
	bits2ip4(b, m, s_ip, BUFLEN);
	puts(s_ip);
}

void print6(bits b, mask_t m) {
	char s_ip[BUFLEN];
	bits2ip6(b, m, s_ip, BUFLEN);
	puts(s_ip);
}

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(t, ip4, b, m);
		} else {
			// ipv6
			ip62bits(s, b, &m);
			iptree_add(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;
}