/* **********************************************************
 * Copyright 2006 - 2011 VMware, Inc.  All rights reserved.
 * **********************************************************/

/*
 * @VMKAPIMOD_LICENSE@
 */

/*
 ***********************************************************************
 * Hash                                                           */ /**
 * \addtogroup Lib
 * @{
 * \defgroup Hash Hash
 *
 * The following are interfaces for a hash abstraction which enables
 * arbitrary key-value pair storage.
 *
 * @{
 ***********************************************************************
 */

#ifndef _VMKAPI_HASH_H_
#define _VMKAPI_HASH_H_

/** \cond never */
#ifndef VMK_HEADER_INCLUDED_FROM_VMKAPI_H
#error This vmkapi file should never be included directly but only via vmkapi.h
#endif
/** \endcond never */

#include "base/vmkapi_heap.h"

/**
 * \brief Invalid hash handle
 */
#define VMK_INVALID_HASH_HANDLE NULL

/**
 * \brief Handle to a hash table
 */
typedef void *vmk_HashTable;

/**
 * \brief Key used to store key-value pair. A key can really be anything ranging
 *        from a string to integer to whatever data structure one would like
 *        to use as a key.
 */
typedef void *vmk_HashKey;

/**
 * \brief Hash implementation uses these flags to process key.
 */
typedef vmk_uint64 vmk_HashKeyFlags;

/** No flags. */
#define VMK_HASH_KEY_FLAGS_NONE       0x0

/**
 * Hash implementation should do a local copy of the key on insertion
 * and do not assume the memory backing up the key will be persistent.
 */
#define VMK_HASH_KEY_FLAGS_LOCAL_COPY 0x1

/**
 * \brief Key length.
 */
typedef vmk_uint32 vmk_HashKeyLen;

/**
 * \brief Value used as part of a key-value pair. There is no restriction
 *        related to the internal value representation.
 */
typedef void *vmk_HashValue;

/**
 * \brief Key iterator commands.
 */
typedef vmk_uint64 vmk_HashKeyIteratorCmd;

/** Keep iterating through the hash table. */
#define VMK_HASH_KEY_ITER_CMD_CONTINUE 0x0

/** Stop iterating through the hash table. */
#define VMK_HASH_KEY_ITER_CMD_STOP     0x1

/** Delete the iterated key-value pair. */
#define VMK_HASH_KEY_ITER_CMD_DELETE   0x2

/*
 *******************************************************************************
 * vmk_HashGetAllocSize --                                                */ /**
 *
 * \brief Return a best estimate amount of memory necessary to operate the
 *        hash table.
 *
 * \param[in]  nbEntries A "best guess" number of expected entries for hash
 *                       buckets sizing.
 *
 * \retval Best estimate amount of memory in bytes.
 *
 *******************************************************************************
 */
vmk_ByteCount
vmk_HashGetAllocSize(vmk_uint32 nbEntries);


/*
 *******************************************************************************
 * vmk_HashAlloc --                                                       */ /**
 *
 * \brief Allocate a new hash table using integer keys.
 *
 * \note vmk_HashRelease() needs to be called once done with the hash table.
 *
 * \note The hash table returned does not come with locking, it is the
 *       caller's responsibility to provide such mechanism.
 *
 * \param[in]  moduleID  Module ID requesting the hash table.
 * \param[in]  heapID    The heap used for hash table internal allocation
 *                       related to hash structure and hash entries
 *                       structure.
 * \param[in]  nbEntries A "best guess" number of expected entries for hash
 *                       buckets sizing.
 * \param[out] hdl       Hash handle allocated for later operations.
 *
 * \retval VMK_OK        Hash table initialization was successful.
 * \retval VMK_NO_MEMORY Allocation failure.
 * \retval VMK_BAD_PARAM If hdl pointer equals to NULL.
 *                       If moduleID equals to VMK_INVALID_MODULE_ID.
 *                       If heapID equals to VMK_INVALID_HEAP_ID.
 *                       If nbEntries equals to zero.
 *
 *******************************************************************************
 */
VMK_ReturnStatus
vmk_HashAlloc(vmk_ModuleID moduleID,
              vmk_HeapID heapID,
              vmk_uint32 nbEntries,
              vmk_HashTable *hdl);


/*
 *******************************************************************************
 * vmk_HashAllocWithStrKeys --                                            */ /**
 *
 * \brief Allocate a new hash table using string keys.
 *
 * \note vmk_HashRelease() needs to be called once done with the hash table.
 *
 * \note The hash table returned does not come with locking, it is the
 *       caller's responsibility to provide such mechanism.
 *
 * \param[in]  moduleID  Module ID requesting the hash table.
 * \param[in]  heapID    The heap used for hash table internal allocation
 *                       related to hash structure and hash entries
 *                       structure.
 * \param[in]  maxStrLen Maximum string size expected.
 * \param[in]  flags     Hash key flags.
 * \param[in]  nbEntries A "best guess" number of expected entries for hash
 *                       buckets sizing.
 * \param[out] hdl       Hash handle allocated for later operations.
 *
 * \retval VMK_OK        Hash table initialization was successful.
 * \retval VMK_NO_MEMORY Allocation failure.
 * \retval VMK_BAD_PARAM If hdl pointer equals to NULL.
 *                       If moduleID equals to VMK_INVALID_MODULE_ID.
 *                       If heapID equals to VMK_INVALID_HEAP_ID.
 *                       If nbEntries equals to zero.
 *                       If flags is invalid.
 *                       If maxStrLen equals to 0.
 *
 *******************************************************************************
 */
VMK_ReturnStatus
vmk_HashAllocWithStrKeys(vmk_ModuleID moduleID,
                         vmk_HeapID heapID,
                         vmk_HashKeyLen maxStrLen,
                         vmk_HashKeyFlags flags,
                         vmk_uint32 nbEntries,
                         vmk_HashTable *hdl);


/*
 *******************************************************************************
 * vmk_HashAllocWithOpaqueKeys --                                         */ /**
 *
 * \brief Allocate a new hash table using opaque keys.
 *
 * \note The hash table returned does not come with locking, it is the
 *       caller's responsibility to provide such mechanism.
 *
 * \note vmk_HashRelease() needs to be called once done with the hash table.
 *
 * \param[in]  moduleID  Module ID requesting the hash table.
 * \param[in]  heapID    The heap used for hash table internal allocation
 *                       related to hash structure and hash entries
 *                       structure.
 * \param[in]  keyLen    Constant key size expected.
 * \param[in]  flags     Hash key flags.
 * \param[in]  nbEntries A "best guess" number of expected entries for hash
 *                       buckets sizing.
 * \param[out] hdl       Hash handle allocated for later operations.
 *
 * \retval VMK_OK        Hash table initialization was successful.
 * \retval VMK_NO_MEMORY Allocation failure.
 * \retval VMK_BAD_PARAM If hdl pointer equals to NULL.
 *                       If moduleID equals to VMK_INVALID_MODULE_ID.
 *                       If heapID equals to VMK_INVALID_HEAP_ID.
 *                       If nbEntries equals to zero.
 *                       If flags is invalid.
 *                       If keyLen equals to 0.
 *
 *******************************************************************************
 */
VMK_ReturnStatus
vmk_HashAllocWithOpaqueKeys(vmk_ModuleID moduleID,
                            vmk_HeapID heapID,
                            vmk_HashKeyLen keyLen,
                            vmk_HashKeyFlags flags,
                            vmk_uint32 nbEntries,
                            vmk_HashTable *hdl);


/*
 *******************************************************************************
 * vmk_HashRelease --                                                     */ /**
 *
 * \brief Release a hash table.
 *
 * \param[in] hdl        Hash handle.
 *
 * \retval VMK_OK        Hash table was released successful.
 * \retval VMK_BUSY      If the hash table is not empty.
 * \retval VMK_BAD_PARAM If hdl equals to VMK_INVALID_HASH_HANDLE.
 *
 *******************************************************************************
 */
VMK_ReturnStatus
vmk_HashRelease(vmk_HashTable hdl);


/*
 *******************************************************************************
 * vmk_HashDeleteAll --                                                       */ /**
 *
 * \brief Delete every entry in a hash table.
 *
 * \note This won't actually release the values passed as part of the hash
 *       table insertion. Client should make sure the right clean up is done
 *       beforehand.
 *
 * \note A subsequent call to vmk_HashIsEmpty() on the given hash table should
 *       return VMK_TRUE.
 *
 * \param[in] hdl        Hash handle.
 *
 * \retval VMK_OK        Every single entry of the hash table was deleted.
 * \retval VMK_BAD_PARAM If hdl equals to VMK_INVALID_HASH_HANDLE.
 *
 *******************************************************************************
 */
VMK_ReturnStatus
vmk_HashDeleteAll(vmk_HashTable hdl);


/*
 *******************************************************************************
 * vmk_HashIsEmpty --                                                     */ /**
 *
 * \brief Check if a given hash table is empty.
 *
 * \param[in] hdl       Hash handle.
 *
 * \retval VMK_TRUE     Hash is empty.
 * \retval VMK_FALSE    Hash has at least one key-value pair.
 *
 *******************************************************************************
 */
vmk_Bool
vmk_HashIsEmpty(vmk_HashTable hdl);


/*
 *******************************************************************************
 * vmk_HashKeyIterator --                                                 */ /**
 *
 * \brief Iterator used to iterate the key-value pairs on a given hash table.
 *
 * \note The return value is a command set given back to the iterator engine to
 *       let it know what to do next. It can be a binary union of any of the
 *       vmk_HashKeyIteratorCmd defined above.
 *
 * \param[in] hdl       Hash handle.
 * \param[in] key       Key.
 * \param[in] value     Value.
 * \param[in] data      Private data passed while calling vmk_HashKeyIterate.
 *
 * \retval VMK_HASH_KEY_ITER_CMD_CONTINUE Move to the next key-value pair.
 * \retval VMK_HASH_KEY_ITER_CMD_STOP     Stop iterating.
 * \retval VMK_HASH_KEY_ITER_CMD_DELETE   Delete the current key-value pair.
 *
 *******************************************************************************
 */
typedef vmk_HashKeyIteratorCmd (*vmk_HashKeyIterator)(vmk_HashTable hdl,
                                                      vmk_HashKey key,
                                                      vmk_HashValue value,
                                                      vmk_AddrCookie data);


/*
 *******************************************************************************
 * vmk_HashKeyIterate --                                                  */ /**
 *
 * \brief Iterate through the key-value pairs from a given hash table.
 *
 * \param[in] hdl       Hash handle.
 * \param[in] iterator  Iterator callback.
 * \param[in] data      Private data passed to the iterator for each key-value
 *                      pair.
 *
 * \retval VMK_OK        Iterator went through the entire hash table or until
 *                       stop command was issued.
 * \retval VMK_BAD_PARAM If hdl equals to VMK_INVALID_HASH_HANDLE.
 *                       If iterator equals to NULL.
 *
 *******************************************************************************
 */
VMK_ReturnStatus
vmk_HashKeyIterate(vmk_HashTable hdl,
                   vmk_HashKeyIterator iterator,
                   vmk_AddrCookie data);


/*
 *******************************************************************************
 * vmk_HashKeyInsert --                                                   */ /**
 *
 * \brief Insert a key-value pair into a given hash table.
 *
 * \note The key passed will be copied locally only if the flag
 *       VMK_HASH_KEY_FLAGS_LOCAL_COPY was passed while creating the hash.
 *
 * \note The value passed won't be copied so the reference needs to be persistent
 *       till key-value pair removal.
 *
 * \param[in] hdl        Hash handle.
 * \param[in] key        Key.
 * \param[in] value      Value. A NULL value is valid.
 *
 * \retval VMK_OK        Key-value pair insertion successful.
 * \retval VMK_NO_MEMORY Allocation failure.
 * \retval VMK_BAD_PARAM If hdl pointer equals to VMK_INVALID_HASH_HANDLE.
 *                       If key equals to NULL on a string or opaque keys hash.
 *
 *******************************************************************************
 */
VMK_ReturnStatus
vmk_HashKeyInsert(vmk_HashTable hdl,
                  vmk_HashKey key,
                  vmk_HashValue value);


/*
 *******************************************************************************
 * vmk_HashKeyUpdate --                                                   */ /**
 *
 * \brief Update a key-value pair on a given hash table and return the previous
 *        associated value.
 *
 * \note The value passed won't be copied so the reference needs to be persistent
 *       till key-value pair removal.
 *
 * \param[in]  hdl       Hash handle.
 * \param[in]  key       Key.
 * \param[in]  newValue  Updated value. A NULL value is valid.
 * \param[out] oldValue  Value before update. A NULL value would mean that the
 *                       caller is not interested in getting the previous
 *                       associated value.
 *
 * \retval VMK_OK        Key-value pair update successful.
 * \retval VMK_NOT_FOUND If there is no key-value pair matching the key
 *                       parameter.
 * \retval VMK_BAD_PARAM If hdl pointer equals to VMK_INVALID_HASH_HANDLE.
 *                       If key equals to NULL on a string or opaque keys hash.
 *
 *******************************************************************************
 */
VMK_ReturnStatus
vmk_HashKeyUpdate(vmk_HashTable hdl,
                  vmk_HashKey key,
                  vmk_HashValue newValue,
                  vmk_HashValue *oldValue);


/*
 *******************************************************************************
 * vmk_HashKeyDelete --                                                   */ /**
 *
 * \brief Delete a key-value pair from a given hash table and return the current
 *        value.
 *
 * \param[in]  hdl       Hash handle.
 * \param[in]  key       Key.
 * \param[out] value     Value before remove. A NULL value would mean that the
 *                       caller is not interested in getting the current
 *                       associated value.
 *
 * \retval VMK_OK        Key-value pair removal successful.
 * \retval VMK_NOT_FOUND If there is no key-value pair matching the key
 *                       parameter.
 * \retval VMK_BAD_PARAM If hdl pointer equals to VMK_INVALID_HASH_HANDLE.
 *                       If key equals to NULL on a string or opaque keys hash.
 *
 *******************************************************************************
 */
VMK_ReturnStatus
vmk_HashKeyDelete(vmk_HashTable hdl,
                  vmk_HashKey key,
                  vmk_HashValue *value);


/*
 *******************************************************************************
 * vmk_HashKeyFind --                                                     */ /**
 *
 * \brief Find a key-value pair and return the current associated value.
 *
 * \param[in]  hdl       Hash handle.
 * \param[in]  key       Key.
 * \param[out] value     Value associated to the key. A NULL value would mean
 *                       that the caller is not interested in getting the current
 *                       associated value.
 *
 * \retval VMK_OK        Key-value pair found successfully.
 * \retval VMK_NOT_FOUND If there is no key-value pair matching the key
 *                       parameter.
 * \retval VMK_BAD_PARAM If hdl pointer equals to VMK_INVALID_HASH_HANDLE.
 *                       If key equals to NULL on a string or opaque keys hash.
 *
 *******************************************************************************
 */
VMK_ReturnStatus
vmk_HashKeyFind(vmk_HashTable hdl,
                vmk_HashKey key,
                vmk_HashValue *value);

/*
 *******************************************************************************
 * vmk_HashBytes --                                                       */ /**
 *
 * \brief Calculate 64 bit hash for an array of bytes.
 *
 * \note This API is not used as part of a hash table allocated with the
 *       vmk_HashAlloc() function. It is provided as a helper routine for
 *       callers that need to calculate hashes for their own purpose.
 *
 * \param[in]  key       Byte array pointer.
 * \param[in]  keySize   Array Size in byte.
 * \param[out] hash      The calculated hash value.
 *
 * \retval VMK_OK        Hash calculated successfully.
 * \retval VMK_BAD_PARAM If key or hash is NULL, or keySize equal zero.
 *
 *******************************************************************************
 */

VMK_ReturnStatus
vmk_HashBytes(const vmk_uint8 *key,
              vmk_uint32 keySize,
              vmk_uint64 *hash);

#endif /* _VMKAPI_HASH_H_ */
/** @} */
/** @} */