#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#include <stdarg.h>
#include <sys/socket.h>
#include <asm/types.h>
#include <linux/netlink.h>
#include <netinet/in.h>
#include <arpa/inet.h>
#include <linux/rtnetlink.h>
#include <sys/ioctl.h>
#include <net/if.h>

struct entry
{
        unsigned char addr[sizeof(struct in6_addr)];
        int dst_len;
	int type;
        char *desc;
} *entries = 0, **printstack = 0;
int n_entries = 0;
int n_printstack = 0;

int rtnl_s;

int is_subnet(unsigned char* sub, unsigned char *sup, int bits)
{
	int i;
	for (i=0;i<bits;i++)
	{
		if (((sub[i/8]>>(7-i%8))&1) != ((sup[i/8]>>(7-i%8))&1)) return 0;
	}
	return 1;
}

void catf (char *s, char *fmt, ...)
{
  va_list args;
  va_start (args, fmt);
  vsprintf (s+strlen(s), fmt, args);
  va_end (args);
}

char *get_ifname(int ifindex)
{
	static struct ifreq ifr;
	int fd;

	ifr.ifr_ifindex = ifindex;
	fd = socket(AF_INET, SOCK_DGRAM, 0);
	ioctl(fd, SIOCGIFNAME, &ifr);
	return ifr.ifr_name;
}
int cmp1(const void *a, const void *b)
{
	const struct entry *a_ = a, *b_ = b;
	int atype = a_->type, btype = b_->type;

	if (atype == RTN_UNICAST || atype == RTN_LOCAL || atype == RTN_ANYCAST) atype = 0;
	if (btype == RTN_UNICAST || btype == RTN_LOCAL || btype == RTN_ANYCAST) btype = 0;

	if (atype < btype) return -1;
	else if (atype > btype) return 1;

	return memcmp(a_->addr, b_->addr, sizeof (struct in6_addr));
}

int main()
{
	int family_i, family, i, j, level;
	int remaining_len, rtlen;

	struct nlmsgerr *nerr;
	struct rtattr *rta;
	struct rtmsg *rtm;

	struct nlmsghdr *nlmh;
	struct ifreq ifr;

	struct {
		struct nlmsghdr  nlmh;
		struct rtmsg 	 rtm;
	} req;

	char buf[65535];
	char rta_dst[INET6_ADDRSTRLEN];
	char rta_gateway[INET6_ADDRSTRLEN];
	char rta_prefsrc[INET6_ADDRSTRLEN];
	char ifname[IFNAMSIZ];

	int rta_gateway_flag = 0, rta_prefsrc_flag = 0;

	for (family_i=0; family_i<2; family_i++)
	{
		n_entries = 0;
		family = !family_i ? AF_INET : AF_INET6;
		memset(&req, 0, sizeof(req));
		req.nlmh.nlmsg_len = NLMSG_LENGTH(sizeof(struct rtmsg));
		req.nlmh.nlmsg_flags = NLM_F_REQUEST | NLM_F_ROOT;
		req.nlmh.nlmsg_type = RTM_GETROUTE;

		memset(&(req.rtm), 0, sizeof(req.rtm));
		req.rtm.rtm_family = family;
		req.rtm.rtm_table = RT_TABLE_UNSPEC;
		req.rtm.rtm_protocol = RTPROT_UNSPEC;

		rtnl_s = socket(AF_NETLINK, SOCK_RAW, NETLINK_ROUTE);
		send(rtnl_s, &req, req.nlmh.nlmsg_len, 0);
		remaining_len = recv(rtnl_s, buf, sizeof buf, 0);
 

		for (nlmh = (struct nlmsghdr *) buf; NLMSG_OK (nlmh, remaining_len); nlmh = NLMSG_NEXT (nlmh, remaining_len)) {
			//printf("test\n");
			rtm = NLMSG_DATA(nlmh);
			rtlen = RTM_PAYLOAD(nlmh);
			entries = realloc(entries, sizeof(struct entry)*(n_entries+1));
			for (rta = RTM_RTA(rtm); RTA_OK (rta, rtlen); rta = RTA_NEXT (rta, rtlen)) {
				switch (rta->rta_type) {
					case RTA_OIF:
						strncpy(ifname, get_ifname(*(int*)RTA_DATA(rta)), IFNAMSIZ);
						break;
					case RTA_GATEWAY:
						inet_ntop(family, RTA_DATA(rta), rta_gateway, INET6_ADDRSTRLEN);
						rta_gateway_flag = 1;
						break;
					case RTA_DST:
						inet_ntop(family, RTA_DATA(rta), rta_dst, INET6_ADDRSTRLEN);
						memcpy(entries[n_entries].addr, RTA_DATA(rta), sizeof(struct in6_addr));
						break;
					case RTA_PREFSRC:
						inet_ntop(family, RTA_DATA(rta), rta_prefsrc, INET6_ADDRSTRLEN);
						rta_prefsrc_flag = 1;
						break;
					case RTA_TABLE:
					case RTA_UNSPEC:
					case RTA_PRIORITY:
					case RTA_METRICS:
					case RTA_IIF:
					case RTA_MARK:
					case RTA_MULTIPATH:
					case RTA_FLOW:
					case RTA_CACHEINFO:
					case RTA_SRC:
					case RTA_PROTOINFO:
					case RTA_SESSION:
					case RTA_MP_ALGO:
						break;
				}
			}
			char *desc = malloc(1024);
			catf(desc, "%s/%d", rta_dst, rtm->rtm_dst_len);
			switch(rtm->rtm_type) {
				case RTN_UNICAST: catf(desc, " UNICAST"); break;
				case RTN_LOCAL: catf(desc, " LOCAL"); break;
				case RTN_ANYCAST: catf(desc, " ANYCAST"); break;
				case RTN_BROADCAST: catf(desc, " BROADCAST"); break;
				case RTN_MULTICAST: catf(desc, " MULTICAST"); break;
				case RTN_BLACKHOLE: catf(desc, " BLACKHOLE"); break;
				case RTN_UNREACHABLE: catf(desc, " UNREACHABLE"); break;
				case RTN_PROHIBIT: catf(desc, " PROHIBIT"); break;
				case RTN_THROW: catf(desc, " THROW"); break;
				case RTN_NAT: catf(desc, " NAT"); break;
				case RTN_XRESOLVE: catf(desc, " XRESOLVE"); break;
			}
			switch(rtm->rtm_type) {
				case RTPROT_REDIRECT: catf(desc, " REDIRECT"); break;
				case RTPROT_KERNEL: catf(desc, " KERNEL"); break;
				case RTPROT_BOOT: catf(desc, " BOOT"); break;
				case RTPROT_STATIC: catf(desc, " STATIC"); break;
				case RTPROT_GATED: catf(desc, " GATED"); break;
				case RTPROT_RA: catf(desc, " RA"); break;
				case RTPROT_MRT: catf(desc, " MRT"); break;
				case RTPROT_ZEBRA: catf(desc, " ZEBRA"); break;
				case RTPROT_BIRD: catf(desc, " BIRD"); break;
				case RTPROT_DNROUTED: catf(desc, " DNROUTED"); break;
				case RTPROT_XORP: catf(desc, " XORP"); break;
				case RTPROT_NTK: catf(desc, " NTK"); break;
				case RTPROT_DHCP: catf(desc, " DHCP"); break;
			}
			switch(rtm->rtm_scope) {
				case RT_SCOPE_UNIVERSE: catf(desc, " UNIVERSE"); break;
				case RT_SCOPE_SITE: catf(desc, " SITE"); break;
				case RT_SCOPE_LINK: catf(desc, " LINK"); break;
				case RT_SCOPE_HOST: catf(desc, " HOST"); break;
				case RT_SCOPE_NOWHERE: catf(desc, " NOWHERE"); break;
			}
			if (rta_gateway_flag) catf(desc, " via %s", rta_gateway);
			catf(desc, " dev %s", ifname);
			if (rta_prefsrc_flag) catf(desc, " prefsrc %s", rta_prefsrc);

			switch(rtm->rtm_table) {
				case RT_TABLE_UNSPEC: catf(desc, " table UNSPEC"); break;
				case RT_TABLE_COMPAT: catf(desc, " table COMPAT"); break;
				case RT_TABLE_DEFAULT: catf(desc, " table DEFAULT"); break;
				case RT_TABLE_MAIN: catf(desc, " table MAIN"); break;
				case RT_TABLE_LOCAL: catf(desc, " table LOCAL"); break;
			}

			entries[n_entries].desc = desc;
			entries[n_entries].dst_len = rtm->rtm_dst_len;
			entries[n_entries].type = rtm->rtm_type;
			n_entries++;
			//printf("%s\n", desc);
			rta_gateway_flag = 0;
			rta_prefsrc_flag = 0;

		}

		qsort(entries, n_entries, sizeof(struct entry), cmp1);
		printstack = malloc(sizeof(struct entry*));
		printstack[0] = &entries[0];
		for (i=0, level=0; i<n_entries; i++)
		{
			if (i > 0)
			{
				if (entries[i-1].dst_len < entries[i].dst_len && is_subnet(entries[i-1].addr, entries[i].addr, entries[i-1].dst_len))
				{
					level++;
					if (level >= n_printstack)
						printstack = realloc(printstack, sizeof(struct entry*)*(level+1));
					printstack[level] = &entries[i-1];
				}
				else
				{
					for (j=level;j>=0;j--)
					{
						if (printstack[j]->dst_len < entries[i].dst_len && is_subnet(printstack[j]->addr, entries[i].addr, printstack[j]->dst_len))
						{
							level = j;
							break;
						}
					}
				}
			}
			for (j=0;j<level;j++) printf(" ");
			printf("%s\n", entries[i].desc);
		}
	}
}