Rtree index method for inet/cidr
Started by John Hansenalmost 21 years ago2 messages
Hi,
Attached, an rtree implementation for inet/cidr values.
It's beyond me to implement this as a patch, but if anyone has the time and energy to do so, feel free!
Comments, positive and negative welcome - and appreciated :)
Kind Regards,
John Hansen
Attachments:
rtree_inet.capplication/octet-stream; name=rtree_inet.cDownload
/*
R-Tree support functions for inet/cidr types.
this code by john@geeknet.com.au
The hostmask,netmask,and masklen functions are code from ip4r
by andrew@supernews.net Oct 2004 - Jan 2005.
Distributed under the same terms as PostgreSQL itself.
*/
#include <netinet/in.h>
#include "postgres.h"
#include "utils/builtins.h"
#include "utils/inet.h"
/*****************************************************************************
* Typedefs
*****************************************************************************/
typedef struct {
uint32 lower, upper;
} ip4range;
/*****************************************************************************
* Prototypes
*****************************************************************************/
static inline uint32 hostmask(unsigned masklen); static inline uint32 netmask(unsigned masklen); static inline unsigned masklen(uint32 lo, uint32 hi);
static inline uint32 host_address(inet *ip); static inline uint32 network_address(inet *ip); static inline uint32 broadcast_address(inet *ip);
static inet *ip4range_inet_internal(ip4range *ip);
static inet *network_union_internal(inet *arg1, inet *arg2); static inet *network_intersect_internal(inet *arg1, inet *arg2);
PG_FUNCTION_INFO_V1(rt_network_union);
PG_FUNCTION_INFO_V1(rt_network_inter);
PG_FUNCTION_INFO_V1(rt_network_size);
PG_FUNCTION_INFO_V1(network_left);
PG_FUNCTION_INFO_V1(network_overleft);
PG_FUNCTION_INFO_V1(network_overlap);
PG_FUNCTION_INFO_V1(network_overright);
PG_FUNCTION_INFO_V1(network_right);
PG_FUNCTION_INFO_V1(network_same);
PG_FUNCTION_INFO_V1(network_contain);
PG_FUNCTION_INFO_V1(network_contained);
PG_FUNCTION_INFO_V1(network_union);
PG_FUNCTION_INFO_V1(network_inter);
/*****************************************************************************
* Access Macros
*****************************************************************************/
#define ip_family(inetptr) (((inet_struct *)VARDATA(inetptr))->family)
#define ip_bits(inetptr) (((inet_struct *)VARDATA(inetptr))->bits)
#define ip_type(inetptr) (((inet_struct *)VARDATA(inetptr))->type)
#define ip_addr(inetptr) (((inet_struct *)VARDATA(inetptr))->ipaddr)
/*****************************************************************************
* Misc local functions
*****************************************************************************/
static inline uint32 hostmask(unsigned masklen) {
return (masklen) ? ( (((uint32)(1U)) << (32-masklen)) - 1U ) : 0xFFFFFFFFU; }
static inline uint32 netmask(unsigned masklen) {
return ~hostmask(masklen);
}
static inline unsigned masklen(uint32 lo, uint32 hi) {
uint32 d = (lo ^ hi);
unsigned masklen = 31;
if(d == 0) return 32;
if(d & 0xffff0000) { masklen -= 16; d &= 0xffff0000; }
if(d & 0xff00ff00) { masklen -= 8; d &= 0xff00ff00; }
if(d & 0xf0f0f0f0) { masklen -= 4; d &= 0xf0f0f0f0; }
if(d & 0xcccccccc) { masklen -= 2; d &= 0xcccccccc; }
if(d & 0xaaaaaaaa) { masklen -= 1; d &= 0xaaaaaaaa; }
return masklen;
}
static inline uint32 host_address(inet *ip) {
return ntohl((uint32) (*((uint32*)ip_addr(ip)))); }
static inline uint32 network_address(inet *ip) {
return host_address(ip) & netmask(ip_bits(ip)); }
static inline uint32 broadcast_address(inet *ip) {
return host_address(ip) | hostmask(ip_bits(ip)); }
static inet *ip4range_inet_internal(ip4range *ip) {
inet *result = (inet *)palloc0(VARHDRSZ + sizeof(inet_struct));
uint32 *temp = (uint32 *)ip_addr(result);
VARATT_SIZEP(result) = VARHDRSZ + sizeof(inet_struct);
ip_family(result) = PGSQL_AF_INET;
ip_type(result) = 0;
ip_bits(result) = masklen(ip->lower,ip->upper);
*temp = htonl((ip->lower & ip->upper) & netmask(ip_bits(result)));
return result;
}
static inet *network_union_internal(inet *arg1, inet *arg2) {
ip4range n;
uint32 upper1 = broadcast_address(arg1);
uint32 upper2 = broadcast_address(arg2);
uint32 lower1 = network_address(arg1);
uint32 lower2 = network_address(arg2);
n.upper = (upper1 > upper2) ? upper1 : upper2;
n.lower = (lower1 < lower2) ? lower1 : lower2;
return ip4range_inet_internal(&n);
}
static inet *network_intersect_internal(inet *arg1, inet *arg2) {
ip4range n;
uint32 upper1 = broadcast_address(arg1);
uint32 upper2 = broadcast_address(arg2);
uint32 lower1 = network_address(arg1);
uint32 lower2 = network_address(arg2);
n.upper = (upper1 < upper2) ? upper1 : upper2;
n.lower = (lower1 > lower2) ? lower1 : lower2;
if (n.upper < n.lower)
{
return (inet *) NULL;
}
return ip4range_inet_internal(&n);
}
/*****************************************************************************
* R-tree support functions
*****************************************************************************/
Datum rt_network_union(PG_FUNCTION_ARGS)
{
inet *arg1 = PG_GETARG_INET_P(0);
inet *arg2 = PG_GETARG_INET_P(1);
inet *result = network_union_internal(arg1,arg2);
PG_FREE_IF_COPY(arg1,0); PG_FREE_IF_COPY(arg2,1);
PG_RETURN_INET_P(result);
}
Datum rt_network_inter(PG_FUNCTION_ARGS)
{
inet *arg1 = PG_GETARG_INET_P(0);
inet *arg2 = PG_GETARG_INET_P(1);
inet *result = network_intersect_internal(arg1,arg2);
PG_FREE_IF_COPY(arg1,0); PG_FREE_IF_COPY(arg2,1);
PG_RETURN_INET_P(result);
}
Datum rt_network_size(PG_FUNCTION_ARGS)
{
inet *arg1 = PG_GETARG_INET_P(0);
float *size = (float *) PG_GETARG_POINTER(1);
uint32 upper1,lower1;
if(arg1 == NULL) {
*size = (float) 0.0;
PG_FREE_IF_COPY(arg1,0);
PG_RETURN_VOID();
}
upper1 = broadcast_address(arg1);
lower1 = network_address(arg1);
if(upper1 < 0xffffffff) upper1++;
if(lower1 > 0) lower1--;
if (upper1 <= lower1)
*size = (float) 0.0;
else
*size = (float) (((upper1 >> 2) - (lower1 >> 2)) + 1);
PG_FREE_IF_COPY(arg1,0);
PG_RETURN_VOID();
}
Datum network_left(PG_FUNCTION_ARGS)
{
inet *arg1 = PG_GETARG_INET_P(0);
inet *arg2 = PG_GETARG_INET_P(1);
uint32 upper1 = broadcast_address(arg1);
uint32 lower2 = network_address(arg2);
PG_FREE_IF_COPY(arg1,0); PG_FREE_IF_COPY(arg2,1);
PG_RETURN_BOOL(upper1 < lower2);
}
Datum network_overleft(PG_FUNCTION_ARGS)
{
inet *arg1 = PG_GETARG_INET_P(0);
inet *arg2 = PG_GETARG_INET_P(1);
uint32 upper1 = broadcast_address(arg1);
uint32 upper2 = broadcast_address(arg2);
PG_FREE_IF_COPY(arg1,0); PG_FREE_IF_COPY(arg2,1);
PG_RETURN_BOOL(upper1 <= upper2);
}
Datum network_overlap(PG_FUNCTION_ARGS)
{
inet *arg1 = PG_GETARG_INET_P(0);
inet *arg2 = PG_GETARG_INET_P(1);
uint32 upper1 = broadcast_address(arg1);
uint32 upper2 = broadcast_address(arg2);
uint32 lower1 = network_address(arg1);
uint32 lower2 = network_address(arg2);
PG_FREE_IF_COPY(arg1,0); PG_FREE_IF_COPY(arg2,1);
PG_RETURN_BOOL(((upper1 >= upper2) && (lower1 <= upper2)) || ((upper2 >= upper1) && (lower2 <= upper1))); }
Datum network_overright(PG_FUNCTION_ARGS)
{
inet *arg1 = PG_GETARG_INET_P(0);
inet *arg2 = PG_GETARG_INET_P(1);
uint32 lower1 = network_address(arg1);
uint32 lower2 = network_address(arg2);
PG_FREE_IF_COPY(arg1,0); PG_FREE_IF_COPY(arg2,1);
PG_RETURN_BOOL(lower1 >= lower2);
}
Datum network_right(PG_FUNCTION_ARGS)
{
inet *arg1 = PG_GETARG_INET_P(0);
inet *arg2 = PG_GETARG_INET_P(1);
uint32 lower1 = network_address(arg1);
uint32 upper2 = broadcast_address(arg2);
PG_FREE_IF_COPY(arg1,0); PG_FREE_IF_COPY(arg2,1);
PG_RETURN_BOOL(lower1 > upper2);
}
Datum network_same(PG_FUNCTION_ARGS)
{
inet *arg1 = PG_GETARG_INET_P(0);
inet *arg2 = PG_GETARG_INET_P(1);
uint32 upper1 = broadcast_address(arg1);
uint32 upper2 = broadcast_address(arg2);
uint32 lower1 = network_address(arg1);
uint32 lower2 = network_address(arg2);
PG_FREE_IF_COPY(arg1,0); PG_FREE_IF_COPY(arg2,1);
PG_RETURN_BOOL((upper1 == upper2) && (lower1 == lower2)); }
Datum network_contain(PG_FUNCTION_ARGS)
{
inet *arg1 = PG_GETARG_INET_P(0);
inet *arg2 = PG_GETARG_INET_P(1);
uint32 upper1 = broadcast_address(arg1);
uint32 upper2 = broadcast_address(arg2);
uint32 lower1 = network_address(arg1);
uint32 lower2 = network_address(arg2);
PG_FREE_IF_COPY(arg1,0); PG_FREE_IF_COPY(arg2,1);
PG_RETURN_BOOL((upper1 >= upper2) && (lower1 <= lower2)); }
Datum network_contained(PG_FUNCTION_ARGS)
{
inet *arg1 = PG_GETARG_INET_P(0);
inet *arg2 = PG_GETARG_INET_P(1);
uint32 upper1 = broadcast_address(arg1);
uint32 upper2 = broadcast_address(arg2);
uint32 lower1 = network_address(arg1);
uint32 lower2 = network_address(arg2);
PG_FREE_IF_COPY(arg1,0); PG_FREE_IF_COPY(arg2,1);
PG_RETURN_BOOL((upper1 <= upper2) && (lower1 >= lower2)); }
/*****************************************************************************
* User functions
*****************************************************************************/
Datum network_union(PG_FUNCTION_ARGS)
{
inet *arg1 = PG_GETARG_INET_P(0);
inet *arg2 = PG_GETARG_INET_P(1);
inet *result = network_union_internal(arg1,arg2);
PG_FREE_IF_COPY(arg1,0); PG_FREE_IF_COPY(arg2,1);
PG_RETURN_INET_P(result);
}
Datum network_inter(PG_FUNCTION_ARGS)
{
inet *arg1 = PG_GETARG_INET_P(0);
inet *arg2 = PG_GETARG_INET_P(1);
inet *result = network_intersect_internal(arg1,arg2);
PG_FREE_IF_COPY(arg1,0); PG_FREE_IF_COPY(arg2,1);
if(result)
PG_RETURN_INET_P(result);
PG_RETURN_NULL();
}
