/*
** Copyright (C) 2008-2011 by Carnegie Mellon University.
**
** @OPENSOURCE_HEADER_START@
**
** Use of the SILK system and related source code is subject to the terms
** of the following licenses:
**
** GNU Public License (GPL) Rights pursuant to Version 2, June 1991
** Government Purpose License Rights (GPLR) pursuant to DFARS 252.227.7013
**
** NO WARRANTY
**
** ANY INFORMATION, MATERIALS, SERVICES, INTELLECTUAL PROPERTY OR OTHER
** PROPERTY OR RIGHTS GRANTED OR PROVIDED BY CARNEGIE MELLON UNIVERSITY
** PURSUANT TO THIS LICENSE (HEREINAFTER THE "DELIVERABLES") ARE ON AN
** "AS-IS" BASIS. CARNEGIE MELLON UNIVERSITY MAKES NO WARRANTIES OF ANY
** KIND, EITHER EXPRESS OR IMPLIED AS TO ANY MATTER INCLUDING, BUT NOT
** LIMITED TO, WARRANTY OF FITNESS FOR A PARTICULAR PURPOSE,
** MERCHANTABILITY, INFORMATIONAL CONTENT, NONINFRINGEMENT, OR ERROR-FREE
** OPERATION. CARNEGIE MELLON UNIVERSITY SHALL NOT BE LIABLE FOR INDIRECT,
** SPECIAL OR CONSEQUENTIAL DAMAGES, SUCH AS LOSS OF PROFITS OR INABILITY
** TO USE SAID INTELLECTUAL PROPERTY, UNDER THIS LICENSE, REGARDLESS OF
** WHETHER SUCH PARTY WAS AWARE OF THE POSSIBILITY OF SUCH DAMAGES.
** LICENSEE AGREES THAT IT WILL NOT MAKE ANY WARRANTY ON BEHALF OF
** CARNEGIE MELLON UNIVERSITY, EXPRESS OR IMPLIED, TO ANY PERSON
** CONCERNING THE APPLICATION OF OR THE RESULTS TO BE OBTAINED WITH THE
** DELIVERABLES UNDER THIS LICENSE.
**
** Licensee hereby agrees to defend, indemnify, and hold harmless Carnegie
** Mellon University, its trustees, officers, employees, and agents from
** all claims or demands made against them (and any related losses,
** expenses, or attorney's fees) arising out of, or relating to Licensee's
** and/or its sub licensees' negligent use or willful misuse of or
** negligent conduct or willful misconduct regarding the Software,
** facilities, or other rights or assistance granted by Carnegie Mellon
** University under this License, including, but not limited to, any
** claims of product liability, personal injury, death, damage to
** property, or violation of any laws or regulations.
**
** Carnegie Mellon University Software Engineering Institute authored
** documents are sponsored by the U.S. Department of Defense under
** Contract FA8721-05-C-0003. Carnegie Mellon University retains
** copyrights in all material produced under this contract. The U.S.
** Government retains a non-exclusive, royalty-free license to publish or
** reproduce these documents, or allow others to do so, for U.S.
** Government purposes only pursuant to the copyright license under the
** contract clause at 252.227.7013.
**
** @OPENSOURCE_HEADER_END@
*/
#ifndef _SKIPSET_H
#define _SKIPSET_H

#include <silk/silk.h>

RCSIDENTVAR(rcsID_SKIPSET_H, "$SiLK: skipset.h 16752 2011-02-24 17:41:51Z mthomas $");

/*
**  skipset.c
**
**    skipset.c provides a data structure for maintaining IP
**    addresses.  The implementation uses a Radix Tree (aka Patricia
**    Trie) to keep IP addresses and their prefixes.  The
**    implementation can support IPv4 or IPv6 addresses, though each
**    instance of an IPset can only hold one type of IP address.
**
**    skipset.c is a replacement for the skIPTree_t data structure
**    defined in iptree.c.
**
**    Mark Thomas
**    September 2008
*/

#include <silk/rwrec.h>
#include <silk/skstream.h>
#include <silk/utils.h>
#include <silk/iptree.h>


typedef enum skipset_return_en {
    SKIPSET_OK = 0,
    SKIPSET_ERR_ALLOC,
    SKIPSET_ERR_BADINPUT,
    SKIPSET_ERR_FILEIO,
    SKIPSET_ERR_FILETYPE,
    SKIPSET_ERR_EMPTY,
    SKIPSET_ERR_OPEN,
    SKIPSET_ERR_IPV6,
    SKIPSET_ERR_FILEVERSION,
    SKIPSET_ERR_PREFIX,
    SKIPSET_ERR_NOTFOUND
} skipset_return_t;


typedef struct skipset_st skipset_t;

typedef int (*skipset_walk_fn_t)(skipaddr_t *ip, uint32_t prefix, void *data);

typedef struct skipset_iterator_st {
    union iter_un {
        skIPTreeCIDRBlockIterator_t     cidr;
        skIPTreeIterator_t              ip;
    }                               iter;
    const skipset_t                *ipset;
    /* 0 for individual IPs, 1 for CIDR blocks */
    uint8_t                         cidr_blocks;
    /* how to return the addresses */
    sk_ipv6policy_t                 ipv6_policy;
} skipset_iterator_t;


int skIPSetCheckAddress(
    const skipset_t    *ipset,
    const skipaddr_t   *ip);
/*
 *    Return 1 if 'ip' is present in 'ipset'; return 0 otherwise.
 *
 *    If 'ip' and 'ipset' have different IP versions (IPv4 vs IPv6),
 *    this function will attempt to convert 'ip' to the form used in
 *    'ipset'.  If the conversion cannot be performed, 0 is returned.
 */


int skIPSetCheckIPSet(
    const skipset_t    *ipset1,
    const skipset_t    *ipset2);
/*
 *    Return 1 if the IPsets 'ipset1' and 'ipset2' have any IPs in
 *    common; otherwise, return 0.
 */


int skIPSetCheckIPWildcard(
    const skipset_t        *ipset,
    const skIPWildcard_t   *ipwild);
/*
 *    Return 1 if the IPset 'ipset' and IPWildcard 'ipwild' have any
 *    IPs in common; otherwise, return 0.
 */


int skIPSetCheckRecord(
    const skipset_t        *ipset,
    const rwRec            *rwrec,
    int                     src_dst_nh);


#define skIPSetCheckRecordSIP(ipset, rwrec)     \
    skIPSetCheckRecord((ipset), (rwrec), 1)
/*
 *    Return 1 if the IPset 'ipset' contains the source IP address of
 *    the SiLK Flow record 'rwrec'; otherwise, return 0.
 */


#define skIPSetCheckRecordDIP(ipset, rwrec)     \
    skIPSetCheckRecord((ipset), (rwrec), 2)
/*
 *    Return 1 if the IPset 'ipset' contains the destination IP
 *    address of the SiLK Flow record 'rwrec'; otherwise, return 0.
 */


#define skIPSetCheckRecordNhIP(ipset, rwrec)     \
    skIPSetCheckRecord((ipset), (rwrec), 4)
/*
 *    Return 1 if the IPset 'ipset' contains the next hop IP address
 *    of the SiLK Flow record 'rwrec'; otherwise, return 0.
 */


int skIPSetClean(
    skipset_t          *ipset);
/*
 *    Combines adjacent CIDR blocks into a larger blocks and makes
 *    certain the IPs in 'ipset' use a contiguous region of memory.
 */


int skIPSetContainsV6(
    const skipset_t    *ipset);
/*
 *    Return 1 if the IPset 'ipset' contains IPv6 addresses (other
 *    than IPv6-encoded-IPv4 addresses); return 0 otherwise.
 *
 *    See also skIPSetIsV6().
 */


int skIPSetConvert(
    skipset_t          *ipset,
    int                 target_ip_version);
/*
 *    Changes the form of IP addresses that are stored in the IPset
 *    'ipset'.
 *
 *    When 'target_ip_version' is 6, 'ipset' will be modified to hold
 *    IPv6 addresses.  An IPset that already holds IPv6 addresses will
 *    not be modified.
 *
 *    When 'target_ip_version' is 4 and 'ipset' holds only
 *    IPv6-encoded-IPv4 addresses, 'ipset' will be modified to hold
 *    IPv4 addresses.  If 'ipset' holds addresses that cannot be
 *    converted to IPv4 (i.e., if skIPSetContainsV6() returns true),
 *    the function returns SKIPSET_ERR_IPV6.  An IPset that already
 *    holds IPv4 addresses will not be modified.
 *
 *    Any other value for 'target_ip_version' results in a return
 *    value of SKIPSET_ERR_BADINPUT, and no changes will be made to
 *    'ipset'.
 */


uint64_t skIPSetCountIPs(
    const skipset_t    *ipset,
    double             *count);
/*
 *    Counts the number of IPs in the IPset 'ipset'.  Returns the
 *    count and, when 'count' is specified, stores the count in that
 *    memory location.  If 'ipset' contains more than MAX_UINT64 IPv6
 *    addresses, the return value is MAX_UINT64.
 */


int skIPSetCreate(
    skipset_t         **ipset,
    int                 support_ipv6);
/*
 *    Allocates and initializes a new IPset at the space specified by
 *    '*ipset'.  The set is initially empty.  When 'support_ipv6' is
 *    non-zero, the IPset will be initialized to store IPv6 addresses;
 *    otherwise it will hold IPv4 addresses.
 *
 *    Returns SKIPSET_OK if everything went well, else
 *    SKIPSET_ERR_ALLOC on a malloc failure, or SKIPSET_ERR_BADINPUT
 *    if the 'ipset' parameter was NULL.
 *
 *    skIPTreeDestroy() is the corresponding free function.
 */


void skIPSetDestroy(
    skipset_t         **ipset);
/*
 *    Deallocates all memory associated with IPset stored in '*ipset'.
 *    On completion, sets *ipset to NULL.  If 'ipset' or '*ipset' are
 *    NULL, no action is taken.
 */


int skIPSetInsertAddress(
    skipset_t          *ipset,
    const skipaddr_t   *ip,
    uint32_t            prefix);
/*
 *    Adds the CIDR block represented by 'ip'/'prefix' to the binary
 *    IPSet 'ipset'.
 *
 *    If 'prefix' is 0, the function inserts the single IP address
 *    'ip'.  If 'prefix' is too large, SKIPSET_ERR_PREFIX is returned.
 *
 *    The 'ip' will be converted to the appropriate form (IPv4 or
 *    IPv6) to match the 'ipset'.  If 'ip' contains an address that
 *    cannot be converted or if 'prefix' is nonsensical,
 *    SKIPSET_ERR_IPV6 is returned.
 *
 *    Returns SKIPSET_OK for success, or SKIPSET_ERR_ALLOC if there is
 *    not enough memory to allocate space for the new IP address
 *    block.
 *
 *    Note that little effort is made to combine CIDR blocks into
 *    larger CIDR blocks as the blocks are inserted.  To ensure that
 *    the data structure is as compact as possible, you may wish to
 *    call skIPSetClean() after inserting a series of IP addresses.
 */



int skIPSetInsertIPWildcard(
    skipset_t              *ipset,
    const skIPWildcard_t   *ipwild);
/*
 *    Add all the addresses in the IPWildcard 'ipwild' to the IPset
 *    'ipset'.  Returns SKIP_OK for success, SKIP_ERR_ALLOC if there
 *    is a memory allocation error.
 */


int skIPSetInsertRange(
    skipset_t          *ipset,
    const skipaddr_t   *ipaddr_start,
    const skipaddr_t   *ipaddr_end);
/*
 *    Insert all IPs from 'ipaddr_start' to 'ipaddr_end' inclusive to
 *    the IPset 'ipset'.  In addition to the return values specified
 *    in 'skIPSetInsertAddress()', this function will return
 *    SKIPSET_ERR_BADINPUT if 'ipaddr_start' is greater than
 *    'ipaddr_end'.
 */


int skIPSetIntersect(
    skipset_t          *result_ipset,
    const skipset_t    *ipset);
/*
 *    Perform an intersection of 'result_ipset' and 'ipset', with the
 *    result in the 'result_ipset'; i.e., turn off all addresses in
 *    'result_ipset' that are off in 'ipset'.
 */


int skIPSetIsV6(
    const skipset_t    *ipset);
/*
 *    Return 1 if the IPset 'ipset' can hold IPv6 addresses; return 0
 *    otherwise.
 *
 *    See also skIPSetContainsV6().
 */


int skIPSetIteratorBind(
    skipset_iterator_t *iter,
    const skipset_t    *ipset,
    uint32_t            cidr_blocks,
    sk_ipv6policy_t     policy);
/*
 *    Bind the IPset iterator 'iter' to iterate over the contents of
 *    the IPSet 'ipset'.  If 'cidr_blocks' is 0, the
 *    skIPSetIteratorNext() function will visit each individual IP.
 *    If 'cidr_blocks' is 1, skIPSetIteratorNext() will visit CIDR
 *    blocks.  Any other value for 'cidr_blocks' is illegal.  The
 *    'policy' parameter can be used to force skIPSetIteratorNext() to
 *    return an IPv4 or an IPv6 skipaddr_t.  This function returns 0
 *    on success, non-zero otherwise.
 */


int skIPSetIteratorNext(
    skipset_iterator_t *iter,
    skipaddr_t         *ipaddr,
    uint32_t           *prefix);
/*
 *    If there are more entries in the IPSet, this function puts the
 *    next IP Address into the location referenced by 'out_addr' and
 *    returns SK_ITERATOR_OK.  Otherwise, 'out_addr' is not touched
 *    and SK_ITERATOR_NO_MORE_ENTRIES is returned.
 */


void skIPSetIteratorReset(
    skipset_iterator_t *iter);
/*
 *    Resets the iterator 'iter' to begin looping through the entries
 *    in the IPSet again.
 */


int skIPSetLoad(
    skipset_t         **ipset,
    const char         *filename);
/*
 *    Creates a new IPset at the location pointed at by 'ipset' and
 *    fills it with the data that the function reads from 'filename'.
 *
 *    This function is similar to skIPTreeRead(), except that this
 *    function will create the stream from the specified filename.
 */


int skIPSetMask(
    skipset_t          *ipset,
    uint32_t            prefix);
/*
 *    Modify in place the specified 'ipset' so it contains at most 1
 *    IP address for every block of bitmask length 'prefix', a value
 *    from 1 to the maximum prefix size for the 'ipset'.  If the
 *    'ipset' has any IP active within each block, all IPs in that
 *    block are turned off except for the IP at the start of the
 *    block.
 *
 *    Specify mask==16 with an IPset containing these IPs:
 *        10.0.0.23
 *        10.0.1.0/24
 *        10.7.1.0/24
 *        20.20.0.243
 *        32.32.0.0/15
 *    produces an IPset with these three IPs:
 *        10.0.0.0
 *        10.7.0.0
 *        20.20.0.0
 *        32.32.0.0
 *        32.33.0.0
 *
 *    Returns SKIPSET_OK on success.  Returns SKIPSET_ERR_PREFIX if
 *    the 'prefix' value is 0 or too large for the 'ipset'.  Returns
 *    SKIPSET_ERR_ALLOC if memory cannot be allocated.
 */


void skIPSetPrint(
    const skipset_t    *ipset,
    skstream_t         *stream,
    skipaddr_flags_t    ip_format,
    int                 as_cidr);
/*
 *    Prints, to the stream 'stream', a textual representation of the
 *    IPset given by 'ipset'.  The parameter 'ip_format' decribes how
 *    to print the ipset (see utils.h).  If 'as_cidr' is non-zero, the
 *    output will be in CIDR notation.
 */



int skIPSetRead(
    skipset_t         **ipset,
    skstream_t         *stream);
/*
 *    Allocates a new IPset at the location pointed at by 'ipset' and
 *    fills it with the data that the function reads from the stream
 *    'stream'.  'stream' should be bound to a file and open.
 *
 *    The skIPSetLoad() function is a wrapper around this function.
 *
 *    On failure, 'ipset' is set to NULL.
 */


int skIPSetRemoveAddress(
    skipset_t          *ipset,
    const skipaddr_t   *ip,
    uint32_t            prefix);
/*
 *    Removes the CIDR block represented by 'ip'/'prefix' from the
 *    binary IPSet 'ipset'.
 *
 *    If 'prefix' is 0, the function removes the single IP address
 *    'ip'.  If 'prefix' is too large, SKIPSET_ERR_PREFIX is returned.
 *
 *    The 'ip' will be converted to the appropriate form (IPv4 or
 *    IPv6) to match the 'ipset'.  If 'ip' contains an address that
 *    cannot be converted or if 'prefix' is nonsensical,
 *    SKIPSET_ERR_IPV6 is returned.
 *
 *    Returns SKIPSET_OK for success.  This function may require
 *    memory allocation: Since the IPset stores CIDR blocks
 *    interanlly, the removal of a single IP from a CIDR block
 *    requires more entries.  If memory allocatoin fails,
 *    SKIPSET_ERR_ALLOC is returned.
 */


int skIPSetRemoveAll(
    skipset_t          *ipset);
/*
 *    Remove all IPs from the IPset.
 */


int skIPSetSave(
    const skipset_t    *ipset,
    const char         *filename);
/*
 *    Writes the IPset at 'ipset' to 'filename'.
 *
 *    This function is similar to skIPTreeWrite(), except this
 *    function writes directly to a file using the default compression
 *    method.
 *
 */


const char *skIPSetStrerror(int error_code);
/*
 *    Return a text string describing 'err_code'.
 */


int skIPSetSubtract(
    skipset_t          *result_ipset,
    const skipset_t    *ipset);
/*
 *    Subtract 'ipset' from 'result_ipset'.  That is, remove all
 *    addresses from 'result_ipset' that are specified in 'ipset'.
 */


int skIPSetUnion(
    skipset_t          *result_ipset,
    const skipset_t    *ipset);
/*
 *    Add the addresses in 'ipset' to 'result_ipset'.  Returns 0 on
 *    success, or 1 on memory allocation error.
 */


int skIPSetWalk(
    const skipset_t    *ipset,
    uint32_t            cidr_blocks,
    sk_ipv6policy_t     policy,
    skipset_walk_fn_t   callback,
    void               *cb_data);
/*
 *    Calls the specified 'callback' function on the contents of the
 *    specified 'ipset'.  If 'cidr_blocks' is 0, the 'callback' is
 *    called on each individual IP in the 'ipset'.  If 'cidr_blocks'
 *    is 1, blocks of IP addresses are passed to the 'callback'.  The
 *    'policy' parameter can be used to force the IP addresses to be
 *    passed to callback as IPv4 or IPv6 addresses.  The 'cb_data'
 *    parameter is passed unchanged to 'callback' function.
 *
 *    If the 'callback' function returns a non-zero value, the
 *    function stops walking through the IPset, and the return value
 *    from 'callback' becomes the return value of this function.
 *
 *    It is not safe to modify the 'ipset' while visiting the CIDR
 *    blocks.
 */


int skIPSetWrite(
    const skipset_t    *ipset,
    skstream_t         *stream);
/*
 *   Write the IPset at 'ipset' the output stream 'stream'.  'stream'
 *   should be bound to a file and open.  The caller may add headers
 *   to the file and set the compression method of the stream before
 *   calling this function.  If not set, the default compression
 *   method is used.
 *
 *   The skIPSetSave() function is a wrapper around this function.
 */


int skIPSetWriteIPTree(
    const skipset_t    *ipset,
    skstream_t         *stream);
/*
 *    Like skIPSetWrite(), except writes the IPset in the legacy
 *    IPTree format.
 */


void skIPSetDebugPrint(
    const skipset_t    *ipset,
    uint32_t            node_idx);
/*
 *    This is meant as a debugging function only.  It prints all
 *    entries in the radix tree starting at 'node_idx'.
 */

#endif /* _SKIPSET_H */

/*
** Local Variables:
** mode:c
** indent-tabs-mode:nil
** c-basic-offset:4
** End:
*/
