/*
** Copyright (C) 2004-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 _BAGTREE_H
#define _BAGTREE_H

#include <silk/silk.h>

RCSIDENTVAR(rcsID_BAGTREE_H, "$SiLK: bagtree.h 16752 2011-02-24 17:41:51Z 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 <silk/skstream.h>


/* DEFINES AND TYPEDEFS */

/* the Bag object maps a key to a counter */
typedef struct skBag_st skBag_t;

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

/* a counter */
typedef uint64_t skBagCounter_t;

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

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


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


/* 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,
    SKBAG_ERR_READ = 6
} skBagErr_t;


/* Function signature used when reading a bag from a stream */
typedef skBagErr_t (*skBagStreamFunc_t)(
    const skBagKey_t       *key,
    const skBagCounter_t   *counter,
    void                   *cb_data);


/* ranges of keys and counters */
#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))


/* The following values are not for public use; they are here for
 * macro expansion only */
extern const skBagCounter_t *skbag_counter_null;
extern const skBagCounter_t *skbag_counter_incr;



/* FUNCTION DECLARATIONS */

/*
 *  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 have their values
 *    summed.
 */
skBagErr_t skBagAddFromStream(
    skBag_t                *bag,
    skstream_t             *stream_in);


/*
 *  status = skBagAddToCounter(bag, &key, &value_add);
 *
 *    Given 'key', a pointer to a key in the bag 'bag', add to the
 *    counter associated with 'key' the value in '*value_add'.  If
 *    'key' does not exist in the bag, it will be inserted into 'bag'
 *    and its value will be set to '*value_add'.
 *
 *    Return SKBAG_OK on success.  Return SKBAG_ERR_INPUT if any input
 *    parameter is NULL.  If the addition would cause the counter to
 *    overflow, the current value in 'bag' remains unchanged and
 *    SKBAG_ERR_OP_BOUNDS is returned.  Return SKBAG_ERR_MEMORY if the
 *    attempt to add the key fails because of an allocation error.
 */
skBagErr_t skBagAddToCounter(
    skBag_t                *bag,
    const skBagKey_t       *key,
    const skBagCounter_t   *value_add);


/*
 *  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 = skBagCopy(&dest, src);
 *
 *    Make a new bag that is a deep copy of src, and set '*dest' to
 *    it.
 */
skBagErr_t skBagCopy(
    skBag_t               **dest,
    const skBag_t          *src);


/*
 *  keys = skBagCountKeys(bag);
 *
 *    Return the number of unique keys in 'bag'.
 */
uint64_t skBagCountKeys(
    const skBag_t          *bag);



/*
 *  status = skBagFree(bag);
 *
 *    Free all memory associated with the bag 'bag'.  The function
 *    returns SKBAG_ERR_INPUT if the 'bag' parameter is NULL.
 */
skBagErr_t skBagFree(
    skBag_t                *bag);


/*
 *  status = skBagGetCounter(bag, &key, &counter);
 *
 *    Find the counter associated with key stored in 'key' from the
 *    bag 'bag', and put its value into 'counter'.  Returns SKBAG_OK
 *    on success.  If 'bag' or 'key' is NULL, the 'counter' is set to
 *    0 and SKBAG_ERR_INPUT is returned.  If 'key' is not in 'bag',
 *    the 'counter' is set to 0 and SKBAG_OK is returned.
 */
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.
 */
#define skBagIncrCounter(inc_bag, inc_key)                      \
    skBagAddToCounter((inc_bag), (inc_key), skbag_counter_incr)


/*
 *  status = skBagIteratorCreate(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 skBagIteratorCreate(
    const skBag_t          *bag,
    skBagIterator_t       **iter);


/*
 *  status = skBagIteratorDestroy(iter);
 *
 *    Deallocate all memory associated with the bag iterator 'iter'.
 *    The function returns SKBAG_ERR_INPUT if the 'iter' parameter is
 *    NULL.
 */
skBagErr_t skBagIteratorDestroy(
    skBagIterator_t        *iter);


/*
 *  status = skBagIteratorNext(iter, &key, &counter);
 *
 *    Get the next key/counter pair associated with the given
 *    iterator, 'iter', store them in the memory pointed at by
 *    'key' and 'counter', respectively, and return SKBAG_OK.
 *
 *    If the iterator has visited all entries, the 'key' and 'counter'
 *    values are unchanged and the function returns
 *    SKBAG_ERR_KEY_NOT_FOUND.  Return SKBAG_ERR_INPUT if the 'iter'
 *    parameter is NULL.
 */
skBagErr_t skBagIteratorNext(
    skBagIterator_t        *iter,
    skBagKey_t             *key,
    skBagCounter_t         *counter);


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


/*
 *  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().
 *
 *    Return SKBAG_OK on success.  Return SKBAG_ERR_INPUT if
 *    'filename' is NULL.  Return SKBAG_ERR_READ (and print an error)
 *    if 'filename' cannot be opened.  May also return the error codes
 *    specified by skBagRead().
 */
skBagErr_t skBagLoad(
    skBag_t               **bag,
    const char             *filename);


/*
 *  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 = skBagProcessStream(stream, cb_data, cb_func);
 *
 *    Read a Bag from the 'stream'.  For each key/counter pair in the
 *    Bag, the function invokes the callback function 'cb_func' with
 *    the key, the counter, and the 'cb_data'.  Processing continues
 *    until the stream is exhausted or until 'cb_func' returns a value
 *    other than 'SKBAG_OK'.
 *
 *    Return SKBAG_ERR_INPUT if the 'stream' or 'cb_func' input
 *    parameters are NULL.  Return SKBAG_ERR_READ (and print an error)
 *    if 'stream' does not contain a Bag file, or the Bag file version
 *    is unsupported.  Return SKBAG_ERR_READ if there is an error
 *    reading 'bag' from 'stream'.  Otherwise, the return status of
 *    this function will be the return status of 'cb_func'.
 */
skBagErr_t skBagProcessStream(
    skstream_t             *stream_in,
    void                   *cb_data,
    skBagStreamFunc_t       cb_func);


/*
 *  status = skBagRead(&bag, stream);
 *
 *    Create a new Bag at '*bag' and read a serialized Bag from the
 *    input stream 'stream' into the it.
 *
 *    Return SKBAG_OK on success.  Return SKBAG_ERR_INPUT if any input
 *    parameter is NULL.  Return SKBAG_ERR_READ (and print an error)
 *    if 'stream' does not contain a Bag file, or the Bag file version
 *    is unsupported.  Return SKBAG_ERR_READ if there is an error
 *    reading 'bag' from 'stream'.  Return SKBAG_ERR_MEMORY if there
 *    is an error creating the bag or adding entries to it.
 */
skBagErr_t skBagRead(
    skBag_t               **bag,
    skstream_t             *stream_in);


/*
 *  status = skBagRemoveKey(bag, key);
 *
 *    Given 'key', a pointer to a key, remove that key from the bag
 *    'bag'.  Return SKBAG_OK on success.  Return SKBAG_OK if 'key' is
 *    not in 'bag'.
 */
#define skBagRemoveKey(rm_bag, rm_key)                          \
    skBagSetCounter((rm_bag), (rm_key), skbag_counter_null)


/*
 *  status = skBagSave(bag, filename);
 *
 *    Serialize the Bag 'bag' to the file specified by 'filename'.
 *    This function is a wrapper around skBagWrite().
 *
 *    Return SKBAG_OK on success.  Return SKBAG_ERR_INPUT if
 *    'filename' is NULL.  Return SKBAG_ERR_OUTPUT (and print an
 *    error) if 'filename' cannot be opened for writing.  May also
 *    return the error codes specified by skBagWrite().
 */
skBagErr_t skBagSave(
    const skBag_t          *bag,
    const char             *filename);


/*
 *  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.
 *
 *    Return SKBAG_OK on success.  Return SKBAG_ERR_INPUT if any input
 *    parameter is NULL.  Return SKBAG_ERR_MEMORY if there is an
 *    allocation error when inserting the 'key'.
 */
skBagErr_t skBagSetCounter(
    skBag_t                *bag,
    const skBagKey_t       *key,
    const skBagCounter_t   *value);


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


/*
 *  status = skBagSubtractFromCounter(bag, &key, &value_sub);
 *
 *    Given 'key', a pointer to a key in the bag 'bag', subtract from
 *    the counter associated with 'key' the value in '*value_sub'.
 *    The 'key' must exist in the bag
 *
 *    Return SKBAG_OK on success.  Return SKBAG_ERR_INPUT if any input
 *    parameter is NULL.  If the subtraction would cause the counter
 *    to become negative or if 'key' does not exist in 'bag', the
 *    counter in 'bag' is unchanged and SKBAG_ERR_OP_BOUNDS is
 *    returned.
 */
skBagErr_t skBagSubtractFromCounter(
    skBag_t                *bag,
    const skBagKey_t       *key,
    const skBagCounter_t   *value_sub);


/*
 *  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.
 *
 *    Return SKBAG_OK on success.  Return SKBAG_ERR_INPUT if any input
 *    parameter is NULL.  Return SKBAG_ERR_OUTPUT if there is an error
 *    writing 'bag' to 'stream'.
 */
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);


/* Legacy function support */

#define skBagAllocIterator  skBagIteratorCreate
#define skBagFreeIterator   skBagIteratorDestroy
#define skBagResetIterator  skBagIteratorReset
#define skBagGetNext        skBagIteratorNext


#endif /* _BAGTREE_H */

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