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

#include "silk.h"

RCSIDENTVAR(rcsID_HASHLIB_H, "$SiLK: hashlib.h 10004 2008-01-04 23:08:59Z mthomas $");

/* File: hashlib.h: defines interface to core hash library
 * functions. */

/*
 *  **************************************************************************
 *
 *  Configuration values for hashlib. These values should be modified
 *  for your platform:
 *
 *      MAX_MEMORY_BLOCK
 *      ENABLE_LOGGING
 */

/* Maximum size in bytes that may be allocated with malloc. Must be a
 * power of two. */
#define MAX_MEMORY_BLOCK (1<<28)

/* Define ENABLE_LOGGING to display ocassional diagnostic messages on
 * stderr. As a rule, enabling shouldn't significantly effect
 * performance since messages are only displayed when blocks are
 * created. */
/* #define ENABLE_LOGGING */

/*
 *  **************************************************************************
 */



/* Return codes. Note that >= 0 are success codes. */
#define OK 0
#define OK_DUPLICATE 1              /* entry already exists */
#define ERR_NOTFOUND -1             /* couldn't find entry */
#define ERR_NOMOREENTRIES -2        /* no more entries available */
#define ERR_INDEXOUTOFBOUNDS -3     /* no longer in use */
#define ERR_FILEOPENERROR -4        /* couldn't open a file */
#define ERR_BADARGUMENT -5          /* illegal argument value */
#define ERR_INTERNALERROR -6        /* corrupt internal state */
#define ERR_NOTSUPPORTED -7         /* operation not supported for this table*/
#define ERR_FILEREADERROR -8        /* read error (corrupt data file) */
#define ERR_FILEWRITEERROR -9       /* write error */
#define ERR_NOMOREBLOCKS -254       /* attempted to aloc > max. # of blocks */
#define ERR_OUTOFMEMORY -255        /* a call to malloc failed */

/* Types of hash tables */

/* Let the library manage the memory used to store values. */
#define HTT_INPLACE 0

/* Application-managed memory. Indicates the hash table will manage
 * pointer storage, _not_ data storage. */
#define HTT_BYREFERENCE 1

/* Indicates table allows deletion. Items are only removed from the table
 * after a rehash. Deleted items have the value del_value_ptr. */
#define HTT_ALLOWDELETION 1

/* Default load is 192 (75%). Generally, this is the value that should
 * be passed to hashlib_create_table for the load factor. */
#define DEFAULT_LOAD_FACTOR 192

/* Maximum number of blocks ever allocated. Once the primary block
 * reaches the maximum block size, new blocks will be allocated
 * until this maximum is reached. */
#define MAX_BLOCKS 8

/* Data types: a HashTable maintains a set of HashBlocks.  Note that
 * these data structures should generally be regarded as a read-only
 * by hash table users. Attriutes in HashTable duplicated in HashBlock
 * are copied upon block creation.*/
typedef struct HashBlock_st {
    uint8_t value_type;     /* HTT_INPLACE or HTT_BYREFERENCE */
    uint8_t options;        /* HTT_ALLOWDELETION or 0 */
    uint8_t key_width;      /* Size of a key in bytes */
    uint8_t value_width;    /* Size of a value in bytes */
    uint8_t load_factor;    /* Point at which to resize (fraction of 255) */
    uint8_t can_memset_val; /* Non-zero if we memset new memory to a value */
    uint8_t *no_value_ptr;  /* Pointer to representation of an empty value */
    uint8_t *del_value_ptr; /* Pointer to rep. of a deleted value */
    uint32_t block_size;    /* Total number of entries in the block */
    uint32_t num_entries;   /* Number of occupied entries in the block */
    uint8_t *_data_ptr;     /* Pointer to an array of variable-sized entries */
} HashBlock;

typedef struct HashTable_st {
    uint8_t value_type;     /* HTT_INPLACE or HTT_BYREFERENCE */
    uint8_t options;        /* HTT_ALLOWDELETION or 0 */
    uint8_t key_width;      /* Size of a key in bytes */
    uint8_t value_width;    /* Size of a value in bytes */
    uint8_t load_factor;    /* Point at which to resize (fraction of 255) */
    uint8_t num_blocks;     /* Number of blocks */
    uint8_t rehash_failed;  /* Non-zero if rehashing has failed in the past */
    uint8_t is_sorted;      /* Non-zero if hash entries are sorted */
    uint8_t can_memset_val; /* Non-zero if we memset new memory to a value */
    uint32_t appdata_size;  /* Size of application data block */
    void    *appdata_ptr;   /* Application data */
    uint8_t *no_value_ptr;  /* Pointer to representation of an empty value */
    uint8_t *del_value_ptr; /* Pointer to rep. of a deleted value */
    HashBlock *block_ptrs[MAX_BLOCKS]; /* The blocks */
} HashTable;

/* Iteration */
typedef struct HashIter_st {
    /* Current block. Negative value is beginning or end */
    int         block;
    /* Current index into block */
    uint32_t    index;
    /* When working with a sorted table, index into each block */
    uint32_t    block_idx[MAX_BLOCKS];
} HASH_ITER;

/* Distinguished values for block */
#define HASH_ITER_BEGIN -1
#define HASH_ITER_END -2


HashTable *hashlib_create_table(
    uint8_t         key_width,
    uint8_t         value_width,
    uint8_t         data_type,
    uint8_t        *no_value_ptr,
    uint8_t        *app_data_ptr,
    uint32_t        app_data_size,
    uint32_t        estimated_size,
    uint8_t         load_factor);

HashTable *hashlib_create_table_ex(
    uint8_t         key_width,
    uint8_t         value_width,
    uint8_t         value_type,
    uint8_t        *no_value_ptr,
    uint8_t        *appdata_ptr,
    uint32_t        appdata_size,
    uint32_t        estimated_count,
    uint8_t         load_factor,
    uint8_t         options,
    uint8_t        *del_value_ptr);

int hashlib_sort_entries(
    HashTable      *table_ptr);

int hashlib_mark_deleted(
    HashTable      *table_ptr,
    uint8_t        *key_ptr);

int hashlib_insert(
    HashTable      *table_ptr,
    uint8_t        *key_ptr,
    uint8_t       **value_pptr);

int hashlib_lookup(
    HashTable      *table_ptr,
    uint8_t        *key_ptr,
    uint8_t       **value_pptr);

HASH_ITER hashlib_create_iterator(HashTable *table_ptr);

int hashlib_iterate(
    HashTable      *table_ptr,
    HASH_ITER      *iter_ptr,
    uint8_t       **key_pptr,
    uint8_t       **val_pptr);

void hashlib_free_table(HashTable *table_ptr);
int hashlib_rehash(HashTable *table_ptr);
uint32_t hashlib_count_nonempties(HashTable *table_ptr);
uint32_t hashlib_count_entries(HashTable *table_ptr);
uint32_t hashlib_count_nondeleted(HashTable *table_ptr);
int32_t hashlib_count_buckets(HashTable *table_ptr);
void hashlib_dump_table_header(FILE *fp, HashTable *table_ptr);
void hashlib_dump_table(FILE *fp, HashTable *table_ptr);
void hashlib_dump_bytes(FILE *fp, uint8_t *data_ptr, uint32_t data_size);

/* Serialization */
int hashlib_save_table(
    HashTable      *table_ptr,
    const char     *filename_str,
    uint8_t        *header_ptr,
    uint8_t         header_length);
int hashlib_restore_table(
    HashTable     **table_pptr,
    const char     *filename_str,
    uint8_t        *header_ptr,
    uint8_t         header_length);

int hashlib_serialize_table(
    HashTable      *table_ptr,
    FILE           *output_fp,
    uint8_t        *header_ptr,
    uint8_t         header_length);

int hashlib_deserialize_table(
    HashTable     **table_pptr,
    FILE           *input_fp,
    uint8_t        *header_ptr,
    int             header_length);

/* #define HASHLIB_RECORD_STATS */

/* Statistics */
#ifdef HASHLIB_RECORD_STATS
extern void hashlib_clear_stats(void);
extern void hashlib_dump_stats(FILE *fp);
extern uint64_t stats_total_rehashes;
extern uint64_t stats_total_rehash_inserts;
extern uint64_t stats_total_inserts;
extern uint64_t stats_total_lookups;
extern uint32_t stats_total_blocks_allocated;
#endif /* HASHLIB_RECORD_STATS */

#ifndef ENABLE_LOGGING
#ifdef TEST_PRINTF_FORMATS
#define ENABLE_LOGGING 1
#endif
#endif

#ifdef ENABLE_LOGGING
#define HASHLOG_FP stderr
#define OPEN_HASHLOG(fp, fn_str, flags_str) fp = fopen(fn_str, flags_str)
#define CLOSE_HASHLOG(fp) fclose(fp)
#define HASHLOG0(fs) fprintf(HASHLOG_FP, fs)
#define HASHLOG1(fs, arg1) fprintf(HASHLOG_FP, fs, arg1)
#define HASHLOG2(fs, arg1, arg2) fprintf(HASHLOG_FP, fs, arg1,arg2)
#define HASHLOG3(fs, arg1, arg2, arg3) fprintf(HASHLOG_FP, fs, arg1,arg2,arg3)
#define HASHLOG_BYTES(dp, n)          \
    {                                 \
        int j;                        \
        for (j=0; j<n; j++) {         \
            HASHLOG1("%02x ", dp[j]); \
        }                             \
    }
#else
#define OPEN_HASHLOG(fp,file_name_str, flags_str)
#define CLOSE_HASHLOG(fp)
#define HASHLOG0(fs)
#define HASHLOG1(fs, a1)
#define HASHLOG2(fs, a1, a2)
#define HASHLOG3(fs, a1, a2, a3)
#define HASHLOG_BYTES(fp, data_ptr, num_bytes)
#endif


#endif /* _HASHLIB_H */


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