/*
** Copyright (C) 2004-2007 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.225-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 F19628-00-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 _BAGTREE_H
#define _BAGTREE_H

#include "silk.h"

RCSIDENTVAR(rcsID_BAGTREE_H, "$SiLK: bagtree.h 7514 2007-06-14 12:20:54Z mthomas $");


/*
**  bagtree.h
**
**  Christopher Lee
**  2004-11-04
**
**  A Bag is a static (but variable) depth tree, where a key is
**  encoded into the tree structure, and blocks of counters are stored
**  in the leaf nodes.
**
**  It would be nice to have more-variable size keys and values, but
**  that has not been worked out.
*/

#include "utils.h"
#include "skstream.h"


/* DEFINES AND TYPEDEFS */

/* Return codes */
typedef enum skBag_err_e {
    SKBAG_OK = 0,
    SKBAG_ERR_MEMORY = 1,
    SKBAG_ERR_KEY_NOT_FOUND = 2,
    SKBAG_ERR_INPUT = 3,
    SKBAG_ERR_OP_BOUNDS = 4,
    SKBAG_ERR_OUTPUT = 5
} skBag_err_t;

/* the number of a level */
typedef uint8_t skBag_level_t;

/* the number of bits encoded on a level */
typedef uint8_t skBag_levelsize_t;

/* the number of entries in a node/leaf */
typedef uint32_t skBag_blocksize_t;

/* a key encoded in the tree */
typedef uint32_t skBag_key_t;

/* a counter */
typedef uint64_t skBag_counter_t;

/* A node either points to another node or to a counter */
union _skBag_node;
typedef union _skBag_node skBag_node_t;
union _skBag_node {
    skBag_node_t       *child;
    skBag_counter_t    *leaf;
};

/* Forward declaration of statistics about the bag data structure */
struct _skBag_stats;
typedef struct _skBag_stats skBag_stats_t;

/* The SiLK Bag */
typedef struct _skBag_header {
    /* the root of the bag */
    skBag_node_t        root;
    /* number of levels in the tree */
    skBag_level_t       levels;
    /* array of length "levels", each entry is the number of bits
     * encoded in a level. */
    skBag_levelsize_t  *level_size;
    /* the offset at every level: the sum of the offsets at every
     * level below this one. */
    skBag_levelsize_t  *level_offset;
    /* statistics about the bag */
    skBag_stats_t      *stats;
} skBag_header_t;


/* Structure used to iterate over bags */
struct _skBag_iterator;
typedef struct _skBag_iterator skBag_iterator_t;


#define SKBAG_KEY_MIN       ((skBag_key_t)0)
#define SKBAG_KEY_MAX       (~((skBag_key_t)0))
#define SKBAG_COUNTER_MIN   ((skBag_counter_t)0)
#define SKBAG_COUNTER_MAX   (~((skBag_counter_t)0))



/* FUNCTION DECLARATIONS */

/*
 *  status = skBag_alloc(&bag, num_levels, level_sizes);
 *
 *    Allocate memory for a new bag, and set '*bag' to point to it.
 *    The new bag should be 'num_levels' levels deep (counting leaf
 *    nodes), and each level 'i' should encode 'level_sizes[i]' bits
 *    of data.
 *
 *    For example, to create a 9/9/9/5 IP space tree:
 *
 *        skBag_header_t *bag;
 *        skBag_levelsize_t level_sizes[4] = { 9, 9, 9, 5 };
 *        skBag_alloc(&bag, 4, level_sizes);
 */
skBag_err_t skBag_alloc(
    skBag_header_t            **bag,
    skBag_level_t               levels,
    const skBag_levelsize_t    *level_sizes);


/*
 *  status = skBag_create(&bag);
 *
 *    Allocate memory for a new Bag and set '*bag' to point to it.
 *    The bag is created with 4 levels, with 9/9/9/5 IPs each.
 */
skBag_err_t skBag_create(
    skBag_header_t            **bag);


/*
 *  status = skBag_free(bag);
 *
 *   Free all memory associated with the bag 'bag'.  It is an error if
 *   bag is NULL.
 */
skBag_err_t skBag_free(
    skBag_header_t         *bag);


/*
 *  status = skBag_addToCounter(bag, &key, &value_add);
 *
 *    Given 'key', a pointer to a key, increment the counter
 *    associated with that key in the bag 'bag' by the value in
 *    '*value_add'.  Creates the key if it does not exist in the bag.
 *
 *    Will return SKBAG_ERR_OP_BOUNDS if the addition would exceed the
 *    counter size and cause it to overflow.
 */
skBag_err_t skBag_addToCounter(
    skBag_header_t         *bag,
    const skBag_key_t      *key,
    const skBag_counter_t  *value_add);


/*
 *  status = skBag_getCounter(bag, &key, &counter);
 *
 *   Get the counter associated with key stored in 'key' from the bag
 *   'bag', and put its value into 'counter'.
 */
skBag_err_t skBag_getCounter(
    const skBag_header_t   *bag,
    const skBag_key_t      *key,
    skBag_counter_t        *counter);


/*
 *  status = skBag_incrCounter(bag, &key);
 *
 *    Given 'key', a pointer to a key, increment the counter
 *    associated with that key in the bag 'bag' by one.  Creates the
 *    key if it does not exist in the bag.
 */
skBag_err_t skBag_incrCounter(
    skBag_header_t         *bag,
    const skBag_key_t      *key);


/*
 *  status = skBag_setCounter(bag, &key, &value);
 *
 *    Given 'key', a pointer to a key, set the counter associated with
 *    that key in the bag 'bag' to the value specified in '*value'.
 *    Creates the key if it does not exist in the bag.
 */
skBag_err_t skBag_setCounter(
    skBag_header_t         *bag,
    const skBag_key_t      *key,
    const skBag_counter_t  *value);


/*
 *  status = skBag_subtractFromCounter(bag, &key, &value_sub);
 *
 *    Given 'key', a pointer to a key, decrement the counter
 *    associated with that key in the bag 'bag' by the value in
 *    '*value_sub'.  The key must exist in the bag.
 *
 *    Will return SKBAG_ERR_OP_BOUNDS if the subtraction would cause
 *    the counter to become negative
 */
skBag_err_t skBag_subtractFromCounter(
    skBag_header_t         *bag,
    const skBag_key_t      *key,
    const skBag_counter_t  *value_sub);


/*
 *
 *   BAG ITERATOR API FUNCTIONS
 *
 */


/*
 *  status = skBag_allocIterator(bag, &iter);
 *
 *    Create a new iterator to iterate over the bag 'bag' and store
 *    the iterator in '*iter'.  The iterator is initialized so that
 *    the first call to skBag_getNext will return the counter
 *    associated with the first key
 */
skBag_err_t skBag_allocIterator(
    const skBag_header_t   *bag,
    skBag_iterator_t      **iter);


/*
 *  status = skBag_freeIterator(iter);
 *
 *    Deallocate all memory associated with the bag iterator 'iter'.
 */
skBag_err_t skBag_freeIterator(
    skBag_iterator_t       *iter);


/*
 *  status = skBag_resetIterator(iter);
 *
 *    Reset the iterator at 'iter' so the next call to skBag_getNext
 *    will return the counter associated with the first key.
 */
skBag_err_t skBag_resetIterator(
    skBag_iterator_t       *iter);


/*
 *  status = skBag_getNext(iter, &key, &counter);
 *
 *    Get the next key/counter pair associated with the given
 *    iterator, 'iter', and store them in the memory pointed at by
 *    'key' and 'counter', respectively.
 */
skBag_err_t skBag_getNext(
    skBag_iterator_t       *iter,
    skBag_key_t            *key,
    skBag_counter_t        *counter);


/*
 *
 *    EXPORTED BAG I/O API FUNCTIONS
 *
 */


/*
 *  status = skBag_printTreeStats(bag, stream);
 *
 *    Print to the stream 'stream' metadata on how the bag 'bag' is
 *    performing.
 */
skBag_err_t skBag_printTreeStats(
    const skBag_header_t   *bag,
    skstream_t             *stream_out);


/*
 *  status = skBag_writeArray(counter_array, num_keys, stream);
 *
 *    Create a Bag file from an array by writing 'counter_array', an
 *    array of skBag_counter_t values indexed from 0 to 'num_keys'-1,
 *    to the output stream 'stream'.  The caller may set the
 *    compression method of 'stream' before calling this function.
 */
skBag_err_t skBag_writeArray(
    const skBag_counter_t  *counter_data,
    skBag_key_t             num_keys,
    skstream_t             *stream);


/*
 *  status = skBag_writeBinary(bag, stream);
 *
 *    Serialize the bag 'bag' to the output stream 'stream'.  The
 *    caller may set the compression method of 'stream' before calling
 *    this function.
 */
skBag_err_t skBag_writeBinary(
    const skBag_header_t   *bag,
    skstream_t             *stream_out);


/*
 *  status = skBag_readBinary(&bag, stream);
 *
 *    Create a new bag at '*bag' and read a serialized bag from the
 *    input stream 'stream' into the new bag.
 */
skBag_err_t skBag_readBinary(
    skBag_header_t        **bag,
    skstream_t             *stream_in);


/*
 *  status = skBag_addBinary(&bag, stream);
 *
 *    Read a serialized bag from the input stream 'stream' and add
 *    it's key/counter pairs to the existing bag 'bag'.  New keys will
 *    be created if required; existing keys will value their values
 *    summed.
 */
skBag_err_t skBag_addBinary(
    skBag_header_t         *bag,
    skstream_t             *stream_in);


/*
 *  error_string = skBag_strerror(code);
 *
 *    Return a static string describing the skBag_err_t value 'code'.
 */
const char *skBag_strerror(
    skBag_err_t             err_code);
 

#endif /* _BAGTREE_H */


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