/*
** Copyright (C) 2004-2008 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 10619 2008-02-25 15:19:21Z 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 "skstream.h"


/* DEFINES AND TYPEDEFS */

/* Return codes */
typedef enum skBagErr_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
} skBagErr_t;

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

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

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

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

/* a counter */
typedef uint64_t skBagCounter_t;

/* A node either points to another node or to a counter */
union skBagNode_un;
typedef union skBagNode_un skBagNode_t;
union skBagNode_un {
    skBagNode_t            *child;
    skBagCounter_t         *leaf;
};

/* Forward declaration of statistics about the bag data structure */
struct skBagStats_st;
typedef struct skBagStats_st skBagStats_t;

/* The SiLK Bag */
typedef struct skBag_st {
    /* the root of the bag */
    skBagNode_t             root;
    /* number of levels in the tree */
    skBagLevel_t            levels;
    /* array of length "levels", each entry is the number of bits
     * encoded in a level. */
    skBagLevelsize_t       *level_size;
    /* the offset at every level: the sum of the offsets at every
     * level below this one. */
    skBagLevelsize_t       *level_offset;
    /* statistics about the bag */
    skBagStats_t           *stats;
} skBag_t;


/* Structure used to iterate over bags */
struct skBagIterator_st;
typedef struct skBagIterator_st skBagIterator_t;


#define SKBAG_KEY_MIN       ((skBagKey_t)0)
#define SKBAG_KEY_MAX       (~((skBagKey_t)0))
#define SKBAG_COUNTER_MIN   ((skBagCounter_t)0)
#define SKBAG_COUNTER_MAX   (~((skBagCounter_t)0))



/* FUNCTION DECLARATIONS */

/*
 *  status = skBagAlloc(&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_t *bag;
 *        skBagLevelsize_t level_sizes[4] = { 9, 9, 9, 5 };
 *        skBagAlloc(&bag, 4, level_sizes);
 */
skBagErr_t skBagAlloc(
    skBag_t               **bag,
    skBagLevel_t            levels,
    const skBagLevelsize_t *level_sizes);


/*
 *  status = skBagCreate(&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.
 */
skBagErr_t skBagCreate(
    skBag_t               **bag);


/*
 *  status = skBagFree(bag);
 *
 *   Free all memory associated with the bag 'bag'.  It is an error if
 *   bag is NULL.
 */
skBagErr_t skBagFree(
    skBag_t                *bag);


/*
 *  status = skBagAddToCounter(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.
 */
skBagErr_t skBagAddToCounter(
    skBag_t                *bag,
    const skBagKey_t       *key,
    const skBagCounter_t   *value_add);


/*
 *  status = skBagGetCounter(bag, &key, &counter);
 *
 *   Get the counter associated with key stored in 'key' from the bag
 *   'bag', and put its value into 'counter'.
 */
skBagErr_t skBagGetCounter(
    const skBag_t          *bag,
    const skBagKey_t       *key,
    skBagCounter_t         *counter);


/*
 *  status = skBagIncrCounter(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.
 */
skBagErr_t skBagIncrCounter(
    skBag_t                *bag,
    const skBagKey_t       *key);


/*
 *  status = skBagSetCounter(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.
 */
skBagErr_t skBagSetCounter(
    skBag_t                *bag,
    const skBagKey_t       *key,
    const skBagCounter_t   *value);


/*
 *  status = skBagSubtractFromCounter(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
 */
skBagErr_t skBagSubtractFromCounter(
    skBag_t                *bag,
    const skBagKey_t       *key,
    const skBagCounter_t   *value_sub);


/*
 *
 *   BAG ITERATOR API FUNCTIONS
 *
 */


/*
 *  status = skBagAllocIterator(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 skBagGetNext will return the counter
 *    associated with the first key
 */
skBagErr_t skBagAllocIterator(
    const skBag_t          *bag,
    skBagIterator_t       **iter);


/*
 *  status = skBagFreeIterator(iter);
 *
 *    Deallocate all memory associated with the bag iterator 'iter'.
 */
skBagErr_t skBagFreeIterator(
    skBagIterator_t        *iter);


/*
 *  status = skBagResetIterator(iter);
 *
 *    Reset the iterator at 'iter' so the next call to skBagGetNext
 *    will return the counter associated with the first key.
 */
skBagErr_t skBagResetIterator(
    skBagIterator_t        *iter);


/*
 *  status = skBagGetNext(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.
 */
skBagErr_t skBagGetNext(
    skBagIterator_t        *iter,
    skBagKey_t             *key,
    skBagCounter_t         *counter);


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


/*
 *  status = skBagPrintTreeStats(bag, stream);
 *
 *    Print to the stream 'stream' metadata on how the bag 'bag' is
 *    performing.
 */
skBagErr_t skBagPrintTreeStats(
    const skBag_t          *bag,
    skstream_t             *stream_out);


/*
 *  status = skBagLoad(bag, filename);
 *
 *    Create a new Bag at '*bag' and read a serialized Bag from the
 *    file specified by 'filename'.  This function is a wrapper around
 *    skBagRead().
 */
skBagErr_t skBagLoad(
    skBag_t               **bag,
    const char             *filename);


/*
 *  status = skBagRead(&bag, stream);
 *
 *    Create a new Bag at '*bag' and read a serialized Bag from the
 *    input stream 'stream' into the it.
 */
skBagErr_t skBagRead(
    skBag_t               **bag,
    skstream_t             *stream_in);


/*
 *  status = skBagSave(bag, filename);
 *
 *    Serialize the Bag 'bag' to the file specified by 'filename'.
 *    This function is a wrapper around skBagWrite().
 */
skBagErr_t skBagSave(
    const skBag_t          *bag,
    const char             *filename);


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


/*
 *  status = skBagWriteArray(counter_array, num_keys, stream);
 *
 *    Create a Bag file from an array by writing 'counter_array', an
 *    array of skBagCounter_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.
 */
skBagErr_t skBagWriteArray(
    const skBagCounter_t   *counter_data,
    skBagKey_t              num_keys,
    skstream_t             *stream);


/*
 *  status = skBagAddFromStream(&bag, stream);
 *
 *    Read a serialized Bag from the input stream 'stream' and add
 *    its key/counter pairs to the existing Bag 'bag'.  New keys will
 *    be created if required; existing keys will value their values
 *    summed.
 */
skBagErr_t skBagAddFromStream(
    skBag_t                *bag,
    skstream_t             *stream_in);


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


#endif /* _BAGTREE_H */

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