radix_python.c

/*
 * Copyright (c) 2004 Damien Miller <djm@mindrot.org>
 *
 * Permission to use, copy, modify, and distribute this software for any
 * purpose with or without fee is hereby granted, provided that the above
 * copyright notice and this permission notice appear in all copies.
 *
 * THE SOFTWARE IS PROVIDED "AS IS" AND THE AUTHOR DISCLAIMS ALL WARRANTIES
 * WITH REGARD TO THIS SOFTWARE INCLUDING ALL IMPLIED WARRANTIES OF
 * MERCHANTABILITY AND FITNESS. IN NO EVENT SHALL THE AUTHOR BE LIABLE FOR
 * ANY SPECIAL, DIRECT, INDIRECT, OR CONSEQUENTIAL DAMAGES OR ANY DAMAGES
 * WHATSOEVER RESULTING FROM LOSS OF USE, DATA OR PROFITS, WHETHER IN AN
 * ACTION OF CONTRACT, NEGLIGENCE OR OTHER TORTIOUS ACTION, ARISING OUT OF
 * OR IN CONNECTION WITH THE USE OR PERFORMANCE OF THIS SOFTWARE.
 */

#include "Python.h"
#include "structmember.h"
#include "radix.h"

/* $Id: radix_python.c,v 1.30 2007/12/18 02:49:01 djm Exp $ */

/* Prototypes */
struct _RadixObject;
struct _RadixIterObject;
static struct _RadixIterObject *newRadixIterObject(struct _RadixObject *);
static PyObject *radix_Radix(PyObject *, PyObject *);

/* ------------------------------------------------------------------------ */

PyObject *radix_constructor;

/* RadixNode: tree nodes */

typedef struct {
	PyObject_HEAD
	PyObject *user_attr;	/* User-specified attributes */
	PyObject *network;
	PyObject *prefix;
	PyObject *prefixlen;
	PyObject *family;
	PyObject *packed;
	radix_node_t *rn;	/* Actual radix node (pointer to parent) */
} RadixNodeObject;

static PyTypeObject RadixNode_Type;

static RadixNodeObject *
newRadixNodeObject(radix_node_t *rn)
{
	RadixNodeObject *self;
	char network[256], prefix[256];

	/* Sanity check */
	if (rn == NULL || rn->prefix == NULL || 
	    (rn->prefix->family != AF_INET && rn->prefix->family != AF_INET6))
		return NULL;

	self = PyObject_New(RadixNodeObject, &RadixNode_Type);
	if (self == NULL)
		return NULL;

	self->rn = rn;

	/* Format addresses for packing into objects */
	prefix_addr_ntop(rn->prefix, network, sizeof(network));
	prefix_ntop(rn->prefix, prefix, sizeof(prefix));

	self->user_attr = PyDict_New();
	self->network = PyString_FromString(network);
	self->prefix = PyString_FromString(prefix);
	self->prefixlen = PyInt_FromLong(rn->prefix->bitlen);
	self->family = PyInt_FromLong(rn->prefix->family);
	self->packed = PyString_FromStringAndSize((char*)&rn->prefix->add,
	    rn->prefix->family == AF_INET ? 4 : 16);

	if (self->user_attr == NULL || self->prefixlen == NULL || 
	    self->family == NULL || self->network == NULL || 
	    self->prefix == NULL) {
		/* RadixNode_dealloc will clean up for us */
		Py_XDECREF(self);
		return (NULL);		
	}

	return self;
}

/* RadixNode methods */

static void
RadixNode_dealloc(RadixNodeObject *self)
{
	Py_XDECREF(self->user_attr);
	Py_XDECREF(self->prefixlen);
	Py_XDECREF(self->family);
	Py_XDECREF(self->network);
	Py_XDECREF(self->prefix);
	PyObject_Del(self);
}

static PyMemberDef RadixNode_members[] = {
	{"data",	T_OBJECT, offsetof(RadixNodeObject, user_attr),	READONLY},
	{"network",	T_OBJECT, offsetof(RadixNodeObject, network),	READONLY},
	{"prefix",	T_OBJECT, offsetof(RadixNodeObject, prefix),	READONLY},
	{"prefixlen",	T_OBJECT, offsetof(RadixNodeObject, prefixlen),	READONLY},
	{"family",	T_OBJECT, offsetof(RadixNodeObject, family),	READONLY},
	{"packed",	T_OBJECT, offsetof(RadixNodeObject, packed),	READONLY},
	{NULL}
};

PyDoc_STRVAR(RadixNode_doc, 
"Node in a radix tree");

static PyTypeObject RadixNode_Type = {
	/* The ob_type field must be initialized in the module init function
	 * to be portable to Windows without using C++. */
	PyObject_HEAD_INIT(NULL)
	0,			/*ob_size*/
	"radix.RadixNode",	/*tp_name*/
	sizeof(RadixNodeObject),/*tp_basicsize*/
	0,			/*tp_itemsize*/
	/* methods */
	(destructor)RadixNode_dealloc, /*tp_dealloc*/
	0,			/*tp_print*/
	0,			/*tp_getattr*/
	0,			/*tp_setattr*/
	0,			/*tp_compare*/
	0,			/*tp_repr*/
	0,			/*tp_as_number*/
	0,			/*tp_as_sequence*/
	0,			/*tp_as_mapping*/
	0,			/*tp_hash*/
	0,			/*tp_call*/
	0,			/*tp_str*/
	0,			/*tp_getattro*/
	0,			/*tp_setattro*/
	0,			/*tp_as_buffer*/
	Py_TPFLAGS_DEFAULT,	/*tp_flags*/
	RadixNode_doc,		/*tp_doc*/
	0,			/*tp_traverse*/
	0,			/*tp_clear*/
	0,			/*tp_richcompare*/
	0,			/*tp_weaklistoffset*/
	0,			/*tp_iter*/
	0,			/*tp_iternext*/
	0,			/*tp_methods*/
	RadixNode_members,	/*tp_members*/
	0,			/*tp_getset*/
	0,			/*tp_base*/
	0,			/*tp_dict*/
	0,			/*tp_descr_get*/
	0,			/*tp_descr_set*/
	0,			/*tp_dictoffset*/
	0,			/*tp_init*/
	0,			/*tp_alloc*/
	0,			/*tp_new*/
	0,			/*tp_free*/
	0,			/*tp_is_gc*/
};

/* ------------------------------------------------------------------------ */

typedef struct _RadixObject {
	PyObject_HEAD
	radix_tree_t *rt4;	/* Radix tree for IPv4 addresses */
	radix_tree_t *rt6;	/* Radix tree for IPv6 addresses */
	unsigned int gen_id;	/* Detect modification during iterations */
} RadixObject;

static PyTypeObject Radix_Type;
#define Radix_CheckExact(op) ((op)->ob_type == &Radix_Type)

static RadixObject *
newRadixObject(void)
{
	RadixObject *self;
	radix_tree_t *rt4, *rt6;

	if ((rt4 = New_Radix()) == NULL)
		return (NULL);
	if ((rt6 = New_Radix()) == NULL) {
		free(rt4);
		return (NULL);
	}
	if ((self = PyObject_New(RadixObject, &Radix_Type)) == NULL) {
		free(rt4);
		free(rt6);
		return (NULL);
	}
	self->rt4 = rt4;
	self->rt6 = rt6;
	self->gen_id = 0;
	return (self);
}

/* Radix methods */

static void
Radix_dealloc(RadixObject *self)
{
	radix_node_t *rn;
	RadixNodeObject *node;

	RADIX_WALK(self->rt4->head, rn) {
		if (rn->data != NULL) {
			node = rn->data;
			node->rn = NULL;
			Py_DECREF(node);
		}
	} RADIX_WALK_END;
	RADIX_WALK(self->rt6->head, rn) {
		if (rn->data != NULL) {
			node = rn->data;
			node->rn = NULL;
			Py_DECREF(node);
		}
	} RADIX_WALK_END;

	Destroy_Radix(self->rt4, NULL, NULL);
	Destroy_Radix(self->rt6, NULL, NULL);
	PyObject_Del(self);
}

static prefix_t
*args_to_prefix(char *addr, char *packed, int packlen, long prefixlen, char *family)
{
	prefix_t *prefix = NULL;
	const char *errmsg;

	if (addr != NULL && packed != NULL) {
		PyErr_SetString(PyExc_TypeError,
			    "Two address types specified. Please pick one.");
		return NULL;
	}

	if (addr == NULL && packed == NULL) {
		PyErr_SetString(PyExc_TypeError,
			    "No address specified (use 'address' or 'packed')");
		return NULL;
	}

	// We can save a lot of work trying to guess family if told explicitly 
	if ((addr != NULL) && (family != NULL)) {
        int ipv4 = !strncmp(family, "ipv4", 4);
        int ipv6 = !strncmp(family, "ipv6", 4);
        if(!(ipv4 || ipv6))
        {
            PyErr_SetString(PyExc_TypeError,
			    "Family must be ipv4 or ipv6");
            return NULL;
        }
        int buflen = 4;
        int domain = AF_INET;
        if(ipv6)
        {
            buflen = 16;
            domain = AF_INET6;
        }

        char *cp = NULL;
        char *tmp = strdup(addr);
        if ((cp = strchr(tmp, '/')) != NULL) {
            *cp++ = '\0';
            prefixlen = atoi(cp);
        }
        unsigned char buf[sizeof(struct in6_addr)];
        int r = inet_pton(domain, tmp, buf);
        if(r == 0) {
            PyErr_SetString(PyExc_TypeError, "Not in presentation format");
            free(tmp);
            return NULL;
        }
        else if(r < 0) {
            PyErr_SetString(PyExc_TypeError, "inet_pton failure");
            free(tmp);
            return NULL;
        }

        prefix = prefix_from_blob(buf, buflen, prefixlen);
        free(tmp);
	}
	else if (addr != NULL) {		/* Parse a string address */
		if ((prefix = prefix_pton(addr, prefixlen, &errmsg)) == NULL) {
			PyErr_SetString(PyExc_ValueError, errmsg ? errmsg :
			    "Invalid address format");
		}
	} else if (packed != NULL) {	/* "parse" a packed binary address */
		if ((prefix = prefix_from_blob((u_char*)packed, packlen, 
		    prefixlen)) == NULL) {
			PyErr_SetString(PyExc_ValueError,
			    "Invalid packed address format");
		}
	}


	if (prefix != NULL &&
	    prefix->family != AF_INET && prefix->family != AF_INET6) {
		Deref_Prefix(prefix);
		return (NULL);
	}

	return prefix;
}

#define PICKRT(prefix, rno) (prefix->family == AF_INET6 ? rno->rt6 : rno->rt4)

static PyObject *
create_add_node(RadixObject *self, prefix_t *prefix)
{
	radix_node_t *node;
	RadixNodeObject *node_obj;

	if ((node = radix_lookup(PICKRT(prefix, self), prefix)) == NULL) {
		PyErr_SetString(PyExc_MemoryError, "Couldn't add prefix");
		return NULL;
	}

	/*
	 * Create a RadixNode object in the data area of the node
	 * We duplicate most of the node's identity, because the radix.c:node 
	 * itself has a lifetime independent of the Python node object
	 * Confusing? yeah...
	 */
	if (node->data == NULL) {
		if ((node_obj = newRadixNodeObject(node)) == NULL)
			return (NULL);
		node->data = node_obj;
	} else
		node_obj = node->data;

	self->gen_id++;
	Py_XINCREF(node_obj);
	return (PyObject *)node_obj;
}

PyDoc_STRVAR(Radix_add_doc,
"Radix.add(network[, masklen][, packed]) -> new RadixNode object\n\
\n\
Adds the network specified by 'network' and 'masklen' to the radix\n\
tree. 'network' may be a string in CIDR format, a unicast host\n\
address or a network address, with the mask length specified using\n\
the optional 'masklen' parameter.\n\
\n\
Alternately, the address may be specified in a packed binary format\n\
using the 'packed' keyword argument (instead of 'network'). This is\n\
useful with binary addresses returned by socket.getpeername(),\n\
socket.inet_ntoa(), etc.\n\
\n\
Both IPv4 and IPv6 addresses/networks are supported and may be mixed in\n\
the same tree.\n\
\n\
This method returns a RadixNode object. Arbitrary data may be strored\n\
in the RadixNode.data dict.");

static PyObject *
Radix_add(RadixObject *self, PyObject *args, PyObject *kw_args)
{
	prefix_t *prefix;
	static char *keywords[] = { "network", "masklen", "packed", "family", NULL};
	PyObject *node_obj;

	char *addr = NULL, *packed = NULL, *family = NULL;
	long prefixlen = -1;
	int packlen = -1;

	if (!PyArg_ParseTupleAndKeywords(args, kw_args, "|sls#s:add", keywords,
		 &addr, &prefixlen, &packed, &packlen, &family))
		return NULL;
	if ((prefix = args_to_prefix(addr, packed, packlen, prefixlen, family)) == NULL)
		return NULL;

	node_obj = create_add_node(self, prefix);
	Deref_Prefix(prefix);

	return node_obj;
}

PyDoc_STRVAR(Radix_delete_doc,
"Radix.delete(network[, masklen][, packed] -> None\n\
\n\
Deletes the specified network from the radix tree.");

static PyObject *
Radix_delete(RadixObject *self, PyObject *args, PyObject *kw_args)
{
	radix_node_t *node;
	RadixNodeObject *node_obj;
	prefix_t *prefix;
	static char *keywords[] = { "network", "masklen", "packed", "family", NULL };

	char *addr = NULL, *packed = NULL, *family = NULL;
	long prefixlen = -1;
	int packlen = -1;

	if (!PyArg_ParseTupleAndKeywords(args, kw_args, "|sls#s:delete", keywords,
		 &addr, &prefixlen, &packed, &packlen, &family))
		return NULL;
	if ((prefix = args_to_prefix(addr, packed, packlen, prefixlen, family)) == NULL)
		return NULL;
	if ((node = radix_search_exact(PICKRT(prefix, self), prefix)) == NULL) {
		Deref_Prefix(prefix);
		PyErr_SetString(PyExc_KeyError, "no such address");
		return NULL;
	}
	if (node->data != NULL) {
		node_obj = node->data;
		node_obj->rn = NULL;
		Py_XDECREF(node_obj);
	}

	radix_remove(PICKRT(prefix, self), node);
	Deref_Prefix(prefix);

	self->gen_id++;
	Py_INCREF(Py_None);
	return Py_None;
}

PyDoc_STRVAR(Radix_search_exact_doc,
"Radix.search_exact(network[, masklen][, packed] -> RadixNode or None\n\
\n\
Search for the specified network in the radix tree. In order to\n\
match, the 'prefix' must be specified exactly. Contrast with the\n\
Radix.search_best method.\n\
\n\
If no match is found, then this method returns None.");

static PyObject *
Radix_search_exact(RadixObject *self, PyObject *args, PyObject *kw_args)
{
	radix_node_t *node;
	RadixNodeObject *node_obj;
	prefix_t *prefix;
	static char *keywords[] = { "network", "masklen", "packed", "family", NULL };

	char *addr = NULL, *packed = NULL, *family = NULL;
	long prefixlen = -1;
	int packlen = -1;

	if (!PyArg_ParseTupleAndKeywords(args, kw_args, "|sls#s:search_exact", keywords,
		 &addr, &prefixlen, &packed, &packlen, &family))
		return NULL;
	if ((prefix = args_to_prefix(addr, packed, packlen, prefixlen, family)) == NULL)
		return NULL;

	node = radix_search_exact(PICKRT(prefix, self), prefix);
	if (node == NULL || node->data == NULL) {
		Deref_Prefix(prefix);
		Py_INCREF(Py_None);
		return Py_None;
	}
	Deref_Prefix(prefix);
	node_obj = node->data;
	Py_XINCREF(node_obj);
	return (PyObject *)node_obj;
}

PyDoc_STRVAR(Radix_search_best_doc,
"Radix.search_best(network[, masklen][, packed] -> None\n\
\n\
Search for the specified network in the radix tree.\n\
\n\
search_best will return the best (longest) entry that includes the\n\
specified 'prefix', much like a IP routing table lookup.\n\
\n\
If no match is found, then returns None.");

static PyObject *
Radix_search_best(RadixObject *self, PyObject *args, PyObject *kw_args)
{
	radix_node_t *node;
	RadixNodeObject *node_obj;
	prefix_t *prefix;
	static char *keywords[] = { "network", "masklen", "packed", "family", NULL };

	char *addr = NULL, *packed = NULL, *family = NULL;
	long prefixlen = -1;
	int packlen = -1;

	if (!PyArg_ParseTupleAndKeywords(args, kw_args, "|sls#s:search_best", keywords,
		 &addr, &prefixlen, &packed, &packlen, &family))
		return NULL;
	if ((prefix = args_to_prefix(addr, packed, packlen, prefixlen, family)) == NULL)
		return NULL;

	if ((node = radix_search_best(PICKRT(prefix, self), prefix)) == NULL || 
	    node->data == NULL) {
		Deref_Prefix(prefix);
		Py_INCREF(Py_None);
		return Py_None;
	}
	Deref_Prefix(prefix);
	node_obj = node->data;
	Py_XINCREF(node_obj);
	return (PyObject *)node_obj;
}

PyDoc_STRVAR(Radix_nodes_doc,
"Radix.nodes(prefix) -> List of RadixNode\n\
\n\
Returns a list containing all the RadixNode objects that have been\n\
entered into the tree. This list may be empty if no prefixes have\n\
been entered.");

static PyObject *
Radix_nodes(RadixObject *self, PyObject *args)
{
	radix_node_t *node;
	PyObject *ret;

	if (!PyArg_ParseTuple(args, ":nodes"))
		return NULL;

	if ((ret = PyList_New(0)) == NULL)
		return NULL;

	RADIX_WALK(self->rt4->head, node) {
		if (node->data != NULL)
			PyList_Append(ret, (PyObject *)node->data);
	} RADIX_WALK_END;
	RADIX_WALK(self->rt6->head, node) {
		if (node->data != NULL)
			PyList_Append(ret, (PyObject *)node->data);
	} RADIX_WALK_END;

	return (ret);
}


PyDoc_STRVAR(Radix_stack_doc,
"Radix.stack(prefix) -> List of prefix strings\n\
\n\
Returns a list nodes that much the prefix\n\
This list may be empty if no prefixes have been\n");

static PyObject *
Radix_stack(RadixObject *self, PyObject *args, PyObject *kw_args)
{
	radix_node_t *node;
	radix_node_t *final_stack[RADIX_MAXBITS + 1];
	prefix_t *prefix;
	static char *keywords[] = { "network", "masklen", "packed", "family", NULL };
	int i, n;
	PyObject *ret;

	char *addr = NULL, *packed = NULL, *family = NULL;
	long prefixlen = -1;
	int packlen = -1;

	if (!PyArg_ParseTupleAndKeywords(args, kw_args, "|sls#s:search_exact", keywords,
		 &addr, &prefixlen, &packed, &packlen, &family))
		return NULL;
	if ((prefix = args_to_prefix(addr, packed, packlen, prefixlen, family)) == NULL)
		return NULL;
	
	if ((ret = PyList_New(0)) == NULL)
		return NULL;

	n = radix_stack(PICKRT(prefix, self), prefix, 1, final_stack);

	for (i=0; i < n; i++) {
		if ((node = final_stack[i]) == NULL)
			break;
		
		PyList_Append(ret, (PyObject *)node->data);
	}

	return (ret);
}


PyDoc_STRVAR(Radix_prefixes_doc,
"Radix.prefixes(prefix) -> List of prefix strings\n\
\n\
Returns a list containing all the prefixes that have been entered\n\
into the tree. This list may be empty if no prefixes have been\n\
entered.");

static PyObject *
Radix_prefixes(RadixObject *self, PyObject *args)
{
	radix_node_t *node;
	PyObject *ret;

	if (!PyArg_ParseTuple(args, ":prefixes"))
		return NULL;

	if ((ret = PyList_New(0)) == NULL)
		return NULL;

	RADIX_WALK(self->rt4->head, node) {
		if (node->data != NULL) {
			PyList_Append(ret,
			    ((RadixNodeObject *)node->data)->prefix);
		}
	} RADIX_WALK_END;
	RADIX_WALK(self->rt6->head, node) {
		if (node->data != NULL) {
			PyList_Append(ret,
			    ((RadixNodeObject *)node->data)->prefix);
		}
	} RADIX_WALK_END;

	return (ret);
}

/* Used for pickling */
static PyObject *
radix_getstate(RadixObject *self)
{
	radix_node_t *node;
	PyObject *ret;
	RadixNodeObject *rnode;

	if ((ret = PyList_New(0)) == NULL)
		return NULL;

	RADIX_WALK(self->rt4->head, node) {
		if (node->data != NULL) {
			rnode = (RadixNodeObject *)node->data;
			PyList_Append(ret, Py_BuildValue("(OO)",
			    rnode->prefix, rnode->user_attr));
			Py_INCREF(rnode->prefix);
			Py_INCREF(rnode->user_attr);
		}
	} RADIX_WALK_END;
	RADIX_WALK(self->rt6->head, node) {
		if (node->data != NULL) {
			rnode = (RadixNodeObject *)node->data;
			PyList_Append(ret, Py_BuildValue("(OO)",
			    rnode->prefix, rnode->user_attr));
			Py_INCREF(rnode->prefix);
			Py_INCREF(rnode->user_attr);
		}
	} RADIX_WALK_END;

	return (ret);
}

static PyObject *
Radix_getstate(RadixObject *self, PyObject *args)
{
	if (!PyArg_ParseTuple(args, ":__getstate__"))
		return NULL;
	return radix_getstate(self);
}

static PyObject *
Radix_reduce(RadixObject *self, PyObject *args)
{
	PyObject *state, *ret;

	if (!PyArg_ParseTuple(args, ":__reduce__"))
		return NULL;
	if ((state = radix_getstate(self)) == NULL)
		return NULL;

	ret = Py_BuildValue("(O()O)", radix_constructor, state);
	Py_XINCREF(radix_constructor);
	Py_XINCREF(state);

	return ret;
}

/* Used for unpickling */
static PyObject *
Radix_setstate(RadixObject *self, PyObject *args)
{
	PyObject *state, *tpl, *addr, *data;
	int len, i;
	RadixNodeObject *node;
	prefix_t *prefix;
	char *addr_string;
	const char *errmsg;

	if (!Radix_CheckExact(self)) {
		PyErr_SetString(PyExc_ValueError, "not a Radix object");
		return NULL;
	}

	/* XXX type-checking is overstrict here */
	if (!PyArg_ParseTuple(args, "O!:__setstate__", &PyList_Type, &state))
		return NULL;

	len = PyList_Size(state);
	for (i = 0; i < len; i++) {
		if ((tpl = PyList_GetItem(state, i)) == NULL)
			return NULL;
		if ((addr = PyTuple_GetItem(tpl, 0)) == NULL)
			return NULL;
		if ((data = PyTuple_GetItem(tpl, 1)) == NULL)
			return NULL;
		if ((addr_string = PyString_AsString(addr)) == NULL)
			return NULL;
		if ((prefix = prefix_pton(addr_string, -1, &errmsg)) == NULL) {
			PyErr_SetString(PyExc_ValueError, errmsg ? errmsg :
			    "Invalid address format");
			return NULL;
		}
		if ((node = (RadixNodeObject *)create_add_node(self,
		    prefix)) == NULL) {
			Deref_Prefix(prefix);
			return NULL;
		}
		Deref_Prefix(prefix);
		Py_XDECREF(node->user_attr);
		node->user_attr = data;
		Py_INCREF(node->user_attr);
	}

	Py_INCREF(Py_None);
	return Py_None;
}

static PyObject *
Radix_getiter(RadixObject *self)
{
	return (PyObject *)newRadixIterObject(self);
}

PyDoc_STRVAR(Radix_doc, "Radix tree");

static PyMethodDef Radix_methods[] = {
	{"add",		(PyCFunction)Radix_add,		METH_VARARGS|METH_KEYWORDS,	Radix_add_doc		},
	{"delete",	(PyCFunction)Radix_delete,	METH_VARARGS|METH_KEYWORDS,	Radix_delete_doc	},
	{"search_exact",(PyCFunction)Radix_search_exact,METH_VARARGS|METH_KEYWORDS,	Radix_search_exact_doc	},
	{"search_best",	(PyCFunction)Radix_search_best,	METH_VARARGS|METH_KEYWORDS,	Radix_search_best_doc	},
	{"nodes",	(PyCFunction)Radix_nodes,	METH_VARARGS,			Radix_nodes_doc		},
	{"prefixes",	(PyCFunction)Radix_prefixes,	METH_VARARGS,			Radix_prefixes_doc	},
	{"stack",	(PyCFunction)Radix_stack,	METH_VARARGS|METH_KEYWORDS,	Radix_stack_doc		},
	{"__getstate__",(PyCFunction)Radix_getstate,	METH_VARARGS,			NULL			},
	{"__setstate__",(PyCFunction)Radix_setstate,	METH_VARARGS,			NULL			},
	{"__reduce__",	(PyCFunction)Radix_reduce,	METH_VARARGS,			NULL			},
	{NULL,		NULL}		/* sentinel */
};

static PyTypeObject Radix_Type = {
	/* The ob_type field must be initialized in the module init function
	 * to be portable to Windows without using C++. */
	PyObject_HEAD_INIT(NULL)
	0,			/*ob_size*/
	"radix.Radix",		/*tp_name*/
	sizeof(RadixObject),	/*tp_basicsize*/
	0,			/*tp_itemsize*/
	/* methods */
	(destructor)Radix_dealloc, /*tp_dealloc*/
	0,			/*tp_print*/
	0,			/*tp_getattr*/
	0,			/*tp_setattr*/
	0,			/*tp_compare*/
	0,			/*tp_repr*/
	0,			/*tp_as_number*/
	0,			/*tp_as_sequence*/
	0,			/*tp_as_mapping*/
	0,			/*tp_hash*/
	0,			/*tp_call*/
	0,			/*tp_str*/
	0,			/*tp_getattro*/
	0,			/*tp_setattro*/
	0,			/*tp_as_buffer*/
	Py_TPFLAGS_DEFAULT,	/*tp_flags*/
	Radix_doc,		/*tp_doc*/
	0,			/*tp_traverse*/
	0,			/*tp_clear*/
	0,			/*tp_richcompare*/
	0,			/*tp_weaklistoffset*/
	(getiterfunc)Radix_getiter, /*tp_iter*/
	0,			/*tp_iternext*/
	Radix_methods,		/*tp_methods*/
	0,			/*tp_members*/
	0,			/*tp_getset*/
	0,			/*tp_base*/
	0,			/*tp_dict*/
	0,			/*tp_descr_get*/
	0,			/*tp_descr_set*/
	0,			/*tp_dictoffset*/
	0,			/*tp_init*/
	0,			/*tp_alloc*/
	0,			/*tp_new*/
	0,			/*tp_free*/
	0,			/*tp_is_gc*/
};

/* ------------------------------------------------------------------------ */

/* RadixIter: radix tree iterator */

typedef struct _RadixIterObject {
	PyObject_HEAD
	RadixObject *parent;
	radix_node_t *iterstack[RADIX_MAXBITS+1];
	radix_node_t **sp;
	radix_node_t *rn;
	int af;
	unsigned int gen_id;	/* Detect tree modifications */
} RadixIterObject;

static PyTypeObject RadixIter_Type;

static RadixIterObject *
newRadixIterObject(RadixObject *parent)
{
	RadixIterObject *self;

	self = PyObject_New(RadixIterObject, &RadixIter_Type);
	if (self == NULL)
		return NULL;

	self->parent = parent;
	Py_XINCREF(self->parent);

	self->sp = self->iterstack;
	self->rn = self->parent->rt4->head;
	self->gen_id = self->parent->gen_id;
	self->af = AF_INET;
	return self;
}

/* RadixIter methods */

static void
RadixIter_dealloc(RadixIterObject *self)
{
	Py_XDECREF(self->parent);
	PyObject_Del(self);
}

static PyObject *
RadixIter_iternext(RadixIterObject *self)
{
	radix_node_t *node;
	PyObject *ret;

	if (self->gen_id != self->parent->gen_id) {
		PyErr_SetString(PyExc_RuntimeWarning,
		    "Radix tree modified during iteration");
		return (NULL);
	}

 again:
	if ((node = self->rn) == NULL) {
		/* We have walked both trees */
		if (self->af == AF_INET6)
			return NULL;
		/* Otherwise reset and start walk of IPv6 tree */
		self->sp = self->iterstack;
		self->rn = self->parent->rt6->head;
		self->af = AF_INET6;
		goto again;
	}

	/* Get next node */
	if (self->rn->l) {
		if (self->rn->r)
			*self->sp++ = self->rn->r;
		self->rn = self->rn->l;
	} else if (self->rn->r)
		self->rn = self->rn->r;
	else if (self->sp != self->iterstack)
		self->rn = *(--self->sp);
	else
		self->rn = NULL;

	if (node->prefix == NULL || node->data == NULL)
		goto again;

	ret = node->data;
	Py_INCREF(ret);
	return (ret);
}

PyDoc_STRVAR(RadixIter_doc, 
"Radix tree iterator");

static PyTypeObject RadixIter_Type = {
	/* The ob_type field must be initialized in the module init function
	 * to be portable to Windows without using C++. */
	PyObject_HEAD_INIT(NULL)
	0,			/*ob_size*/
	"radix.RadixIter",	/*tp_name*/
	sizeof(RadixIterObject),/*tp_basicsize*/
	0,			/*tp_itemsize*/
	/* methods */
	(destructor)RadixIter_dealloc, /*tp_dealloc*/
	0,			/*tp_print*/
	0,			/*tp_getattr*/
	0,			/*tp_setattr*/
	0,			/*tp_compare*/
	0,			/*tp_repr*/
	0,			/*tp_as_number*/
	0,			/*tp_as_sequence*/
	0,			/*tp_as_mapping*/
	0,			/*tp_hash*/
	0,			/*tp_call*/
	0,			/*tp_str*/
	0,			/*tp_getattro*/
	0,			/*tp_setattro*/
	0,			/*tp_as_buffer*/
	Py_TPFLAGS_DEFAULT,	/*tp_flags*/
	RadixIter_doc,		/*tp_doc*/
	0,			/*tp_traverse*/
	0,			/*tp_clear*/
	0,			/*tp_richcompare*/
	0,			/*tp_weaklistoffset*/
	0,			/*tp_iter*/
	(iternextfunc)RadixIter_iternext, /*tp_iternext*/
	0,			/*tp_methods*/
	0,			/*tp_members*/
	0,			/*tp_getset*/
	0,			/*tp_base*/
	0,			/*tp_dict*/
	0,			/*tp_descr_get*/
	0,			/*tp_descr_set*/
	0,			/*tp_dictoffset*/
	0,			/*tp_init*/
	0,			/*tp_alloc*/
	0,			/*tp_new*/
	0,			/*tp_free*/
	0,			/*tp_is_gc*/
};

/* ------------------------------------------------------------------------ */

/* Radix object creator */

PyDoc_STRVAR(radix_Radix_doc,
"Radix() -> new Radix tree object\n\
\n\
Instantiate a new radix tree object.");

static PyObject *
radix_Radix(PyObject *self, PyObject *args)
{
	RadixObject *rv;

	if (!PyArg_ParseTuple(args, ":Radix"))
		return NULL;
	rv = newRadixObject();
	if (rv == NULL)
		return NULL;
	return (PyObject *)rv;
}

static PyMethodDef radix_methods[] = {
	{"Radix",	radix_Radix,	METH_VARARGS,	radix_Radix_doc	},
	{NULL,		NULL}		/* sentinel */
};

PyDoc_STRVAR(module_doc,
"Implementation of a radix tree data structure for network prefixes.\n"
"\n"
"The radix tree is the data structure most commonly used for routing\n"
"table lookups. It efficiently stores network prefixes of varying\n"
"lengths and allows fast lookups of containing networks.\n"
"\n"
"Simple example:\n"
"\n"
"	import radix\n"
"\n"
"	# Create a new tree\n"
"	rtree = radix.Radix()\n"
"\n"
"	# Adding a node returns a RadixNode object. You can create\n"
"	# arbitrary members in its 'data' dict to store your data\n"
"	rnode = rtree.add(\"10.0.0.0/8\")\n"
"	rnode.data[\"blah\"] = \"whatever you want\"\n"
"\n"
"	# You can specify nodes as CIDR addresses, or networks with\n"
"	# separate mask lengths. The following three invocations are\n"
"	# identical:\n"
"	rnode = rtree.add(\"10.0.0.0/16\")\n"
"	rnode = rtree.add(\"10.0.0.0\", 16)\n"
"	rnode = rtree.add(network = \"10.0.0.0\", masklen = 16)\n"
"\n"
"	# It is also possible to specify nodes using binary packed\n"
"	# addresses, such as those returned by the socket module\n"
"	# functions. In this case, the radix module will assume that\n"
"	# a four-byte address is an IPv4 address and a sixteen-byte\n"
"	# address is an IPv6 address. For example:\n"
"	binary_addr = inet_ntoa(\"172.18.22.0\")\n"
"	rnode = rtree.add(packed = binary_addr, masklen = 23)\n"
"\n"
"	# Exact search will only return prefixes you have entered\n"
"	# You can use all of the above ways to specify the address\n"
"	rnode = rtree.search_exact(\"10.0.0.0/8\")\n"
"	# Get your data back out\n"
"	print rnode.data[\"blah\"]\n"
"	# Use a packed address\n"
"	addr = socket.inet_ntoa(\"10.0.0.0\")\n"
"	rnode = rtree.search_exact(packed = addr, masklen = 8)\n"
"\n"
"	# Best-match search will return the longest matching prefix\n"
"	# that contains the search term (routing-style lookup)\n"
"	rnode = rtree.search_best(\"10.123.45.6\")\n"
"\n"
"	# There are a couple of implicit members of a RadixNode:\n"
"	print rnode.network	# -> \"10.0.0.0\"\n"
"	print rnode.prefix	# -> \"10.0.0.0/8\"\n"
"	print rnode.prefixlen	# -> 8\n"
"	print rnode.family	# -> socket.AF_INET\n"
"	print rnode.packed	# -> '\\n\\x00\\x00\\x00'\n"
"\n"
"	# IPv6 prefixes are fully supported in the same tree\n"
"	rnode = rtree.add(\"2001:DB8::/32\")\n"
"	rnode = rtree.add(\"::/0\")\n"
"\n"
"	# Use the nodes() method to return all RadixNodes created\n"
"	nodes = rtree.nodes()\n"
"	for rnode in nodes:\n"
"  		print rnode.prefix\n"
"\n"
"	# The prefixes() method will return all the prefixes (as a\n"
"	# list of strings) that have been entered\n"
"	prefixes = rtree.prefixes()\n"
"\n"
"	# You can also directly iterate over the tree itself\n"
"	# this would save some memory if the tree is big\n"
"	# NB. Don't modify the tree (add or delete nodes) while\n"
"	# iterating otherwise you will abort the iteration and\n"
"	# receive a RuntimeWarning. Changing a node's data dict\n"
"	# is permitted.\n"
"	for rnode in rtree:\n"
"  		print rnode.prefix\n"
);

#if defined(_MSC_VER)
static void cleanupradix(void)
{
	WSACleanup();
}
#endif

PyMODINIT_FUNC
initradix(void)
{
	PyObject *m, *d;
#if defined(_MSC_VER)
	WSADATA winsock_data;
	int r;
	char errbuf[256];

	r = WSAStartup(0x0202, &winsock_data);
	switch (r) {
	case 0:
		Py_AtExit(cleanupradix);
		break;
	case WSASYSNOTREADY:
		PyErr_SetString(PyExc_ImportError, "Winsock error: "
		    "network subsystem not ready");
		return;
	case WSAEINVAL:
	case WSAVERNOTSUPPORTED:
		PyErr_SetString(PyExc_ImportError, "Winsock error: "
		    "required winsock version 2.2 not supported");
		return;
	default:
		snprintf(errbuf, sizeof(errbuf), "Winsock error: code %d", r);
		PyErr_SetString(PyExc_ImportError, errbuf);
		return;
	}
#endif

	if (PyType_Ready(&Radix_Type) < 0)
		return;
	if (PyType_Ready(&RadixNode_Type) < 0)
		return;
	m = Py_InitModule3("radix", radix_methods, module_doc);

	/* Stash the callable constructor for use in Radix.__reduce__ */
	d = PyModule_GetDict(m);
	radix_constructor = PyDict_GetItemString(d, "Radix");

	PyModule_AddStringConstant(m, "__version__", "0.4");
}