.fp 5 CW

.TH IV 3

.SH NAME

\fBlibiv\fR \- arbitrary size unsigned big-endian integer nested intervals and longest prefix matching

.SH SYNOPSIS

.de Tp

.fl

.ne 2

.TP

..

.de Ss

.fl

.ne 2

.SS "\\$1"

..

.de Cs

.nf

.ft 5

..

.de Ce

.ft 1

.fi

..

.ta 1.0i 2.0i 3.0i 4.0i 5.0i

.Cs

#include <iv.h>

.Ce

.Ss "LIBIV'S TYPES"

.Cs

Ivpoint_t;

Ivseg_t;

Iv_t;

Ivdisc_t;

Ivmeth_t;

.Ce

.Ss "INTERVAL MANAGEMENT"

.Cs

Iv_t* ivopen(Ivdisc_t* disc, Ivmeth_t* meth, int size, const char* options);

int ivclose(Iv_t* iv);

int ivset(Iv_t* iv, Ivpoint_t lo, Ivpoint_t hi, void* data);

int ivdel(Iv_t* iv, Ivpoint_t lo, Ivpoint_t hi);

void* ivget(Iv_t* iv, Ivpoint_t pt);

Ivseg_t* ivseg(Iv_t* iv, Ivpoint_t pt);

.Ce

.Ss "DISCIPLINE"

.Cs

typedef int (*Error_f)(void* meth, void* disc, int level, const char* format, ...);

typedef struct Ivdisc_s

{

uint32_t version;

void* unmatched;

Error_f errorf;

Ivfree_f freef;

} Ivdisc_t;

.Ce

.Ss "METHODS"

.Cs

nested

flat

.Ce

.SH DESCRIPTION

.PP

\fIlibiv\fP provides a set of functions to create and maintain

collections of nested or overlapped intervals of

arbitrary size unsigned big-endian integers.

This is a generalization of the problem of looking up IP (Internet Packet)

addresses based on Longest Prefix Matching.

IPV6 addresses are modeled as 16 byte unsigned big-endian integers.

The library provides multiple methods to maintain intervals.

.PP

.Ss "LIBINTERVAL'S TYPES"

.PP

.Ss " void*"

This type is used to pass objects with unknown type

between different apis.

.PP

.Ss " Ivpoint_t"

This is the arbitrary sized unsigned big-endian integer type as defined by \fBfv\fP(3).

It is equivalent to \f5unsigned char*\fP.

.PP

.Ss " Ivseg_t"

This type is used by the \f5ivseg()\fP function to return

a segment and associated data.

.PP

.Ss " Iv_t"

This type defines a handle to hold intervals.

.PP

.Ss " Ivdisc_t"

This type defines a discipline structure to specify

a default value for points not covered by any intervals

and a function to handle certain exceptional events.

.PP

.Ss " Ivmeth_t"

This type defines a method for dealing with intervals.

.PP

.Ss "INTERVAL MANAGEMENT"

.PP

.Ss " Iv_t* ivopen(Ivdisc_t* disc, Ivmeth_t* meth, int size, const char* options)"

This creates a new handle to manage intervals.

\f5disc\fP is a discipline structure.

\f5meth\fP defines the method used to manage intervals.

\f5size\fP is the size in bytes of the unsigned big-endian integer interval points.

\f5options\fP, if not \f50\fP, provides space-separated name=value pairs

for method-specific initializations; this is currently unused.

\f5ivopen()\fP returns the new handle or \f50\fP on failure.

.PP

.Ss " int ivclose(Iv_t* iv)"

This closes the interval handle \f5iv\fP.

It returns \f5-1\fP on failure and \f50\fP on success.

.PP

.Ss " int ivset(Iv_t* iv, Ivpoint_t lo, Ivpoint_t hi, void* data)"

This associates \f5data\fP with the closed interval \f5[lo,hi]\fP.

It returns \f5-1\fP on failure and \f50\fP on success.

.PP

.Ss " int ivdel(Iv_t* iv, Ivpoint_t lo, Ivpoint_t hi)"

This retracts the interval \f5[lo,hi]\fP.

For the methods dealing with nested intervals, only an existing

interval with the same \f5lo\fP and \f5hi\fP endpoints can be retracted.

For the method \f5Ivflat\fP, this is equivalent to calling \f5ivset()\fP with

the same endpoints and the unmatched value (defined in the discipline) as data.

\f5ivdel()\fP returns \f5-1\fP on failure and \f50\fP on success.

.PP

.Ss " void* ivget(Iv_t* iv, Ivpoint_t pt)"

This returns the value associated with the point \f5pt\fP.

If there is no set interval containing \f5pt\fP, the unmatched data value

defined in the discipline of \f5iv\fP is returned.

\f5ivget()\fP returns \f50\fP on failure.

.PP

.Ss " Ivseg_t* ivseg(Iv_t* iv, Ivpoint_t pt)"

The (nested or overlapped) intervals in \f5iv\fP define

a set of disjoint segments such that no two adjacent segments have

the same associated data. \f5ivseg()\fP returns the segment that

contains the point \f5pt\fP or \f50\fP if there is no segment.

The \f5Ivseg_t\fP structure has three elements:

.Cs

Ivpoint_t lo; /* low end of the segment */

Ivpoint_t hi; /* high end of the segment */

void* data; /* the associated data */

.Ce

.PP

.Ss "DISCIPLINE"

A discipline structure must be supplied to the \f5ivopen()\fP call.

It contains three elements:

.Cs

void* unmatched;

int (*errorf)(void* handle, void* disc, int level, const char* format, ...);

void (*freef)(Iv_t* iv, void* data);

.Ce

.PP

The \f5unmatched\fP element defines the value associated with points not

covered by any intervals.

.PP

\f5(*errorf)()\fP is called to process library diagnostic messages.

.PP

\f5(*freef)()\fP is called on for each non-null interval data item on \f5ivclose()\fP.

.PP

.Ss "METHODS"

\fIlibiv\fP provides the following methods for maintaining intervals:

.PP

.Ss " Ivnested"

This method maintains nested intervals. If an interval [u,v]

is nested in another interval [x,y], then the data associated with [u,v]

takes precedence over the data associated with [x,y] for points inside [u,v].

.PP

.Ss " Ivflat"

This method maintains intervals so that a later interval overwrites

any portion of data in earlier intervals that it overlaps with.

Adjacent segments with the same associated data are automatically merged.

For example, assume that the intervals [1,10] and [5,15] are inserted in order.

Then, the subinterval [5,10] of [1,10] will be overwritten with the value of [5,15].

.SH "IMPLEMENTATION NOTES"

.PP

\fIlibiv\fP uses the CDT library for container data types and \fIfv(3)\fP for manipulating

arbitrary size unsigned big-endian integers.

.PP

.SH SEE ALSO

\fIcdt(3)\fP, \fIfv(3)\fP.

.SH AUTHOR

.nf

Kiem-Phong Vo, kpv@research.att.com

Glenn S. Fowler, gsf@research.att.com

.fi