/*
* DO NOT ALTER OR REMOVE COPYRIGHT NOTICES OR THIS HEADER.
*
* Copyright 2021 Mike Becker, Olaf Wintermann All rights reserved.
*
* Redistribution and use in source and binary forms, with or without
* modification, are permitted provided that the following conditions are met:
*
* 1. Redistributions of source code must retain the above copyright
* notice, this list of conditions and the following disclaimer.
*
* 2. Redistributions in binary form must reproduce the above copyright
* notice, this list of conditions and the following disclaimer in the
* documentation and/or other materials provided with the distribution.
*
* THIS SOFTWARE IS PROVIDED BY THE COPYRIGHT HOLDERS AND CONTRIBUTORS "AS IS"
* AND ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE
* IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE
* ARE DISCLAIMED. IN NO EVENT SHALL THE COPYRIGHT HOLDER OR CONTRIBUTORS BE
* LIABLE FOR ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL, EXEMPLARY, OR
* CONSEQUENTIAL DAMAGES (INCLUDING, BUT NOT LIMITED TO, PROCUREMENT OF
* SUBSTITUTE GOODS OR SERVICES; LOSS OF USE, DATA, OR PROFITS; OR BUSINESS
* INTERRUPTION) HOWEVER CAUSED AND ON ANY THEORY OF LIABILITY, WHETHER IN
* CONTRACT, STRICT LIABILITY, OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE)
* ARISING IN ANY WAY OUT OF THE USE OF THIS SOFTWARE, EVEN IF ADVISED OF THE
* POSSIBILITY OF SUCH DAMAGE.
*/
/**
* @file hash_key.h
* @brief Interface for map implementations.
* @author Mike Becker
* @author Olaf Wintermann
* @copyright 2-Clause BSD License
*/
#ifndef UCX_HASH_KEY_H
#define UCX_HASH_KEY_H
#include "common.h"
#include "string.h"
#ifdef __cplusplus
extern "C" {
#endif
/** Internal structure for a key within a hash map. */
struct cx_hash_key_s {
/**
* The key data.
* May be NULL when the hash is collision-free.
*/
const void *data;
/**
* The key data length.
*/
size_t len;
/** The hash value of the key data. */
uint64_t hash;
};
/**
* Type for a hash key.
*/
typedef struct cx_hash_key_s CxHashKey;
/**
* Computes a murmur2 32-bit hash.
*
* You need to initialize @c data and @c len in the key struct.
* The hash is then directly written to that struct.
*
* Usually you should not need this function.
* Use cx_hash_key(), instead.
*
* @note If @c data is @c NULL, the hash is defined as 1574210520.
*
* @param key the key, the hash shall be computed for
* @see cx_hash_key()
*/
cx_attr_nonnull
CX_EXPORT void cx_hash_murmur(CxHashKey *key);
/**
* Mixes up a 32-bit integer to be used as a hash.
*
* This function produces no collisions and has a good statistical distribution.
*
* @param x the integer
* @return the hash
*/
CX_EXPORT uint32_t cx_hash_u32(uint32_t x);
/**
* Mixes up a 64-bit integer to be used as a hash.
*
* This function produces no collisions and has a good statistical distribution.
*
* @param x the integer
* @return the hash
*/
CX_EXPORT uint64_t cx_hash_u64(uint64_t x);
/**
* Computes a hash key from a 32-bit integer.
*
* @param x the integer
* @return the hash key
*/
cx_attr_nodiscard
CX_EXPORT CxHashKey cx_hash_key_u32(uint32_t x);
/**
* Computes a hash key from a 64-bit integer.
*
* @param x the integer
* @return the hash key
*/
cx_attr_nodiscard
CX_EXPORT CxHashKey cx_hash_key_u64(uint64_t x);
/**
* Computes a hash key from a string.
*
* The string needs to be zero-terminated.
*
* @param str the string
* @return the hash key
*/
cx_attr_nodiscard cx_attr_cstr_arg(1)
CX_EXPORT CxHashKey cx_hash_key_str(const char *str);
/**
* Computes a hash key from a string.
*
* Use this function when the string is represented
* as an unsigned char array.
*
* The string needs to be zero-terminated.
*
* @param str the string
* @return the hash key
*/
cx_attr_nodiscard cx_attr_cstr_arg(1)
CX_EXPORT CxHashKey cx_hash_key_ustr(const unsigned char *str);
/**
* Computes a hash key from a byte array.
*
* @param bytes the array
* @param len the length
* @return the hash key
*/
cx_attr_nodiscard cx_attr_access_r(1, 2)
CX_EXPORT CxHashKey cx_hash_key_bytes(const unsigned char *bytes, size_t len);
/**
* Computes a hash key for an arbitrary object.
*
* The computation uses the in-memory representation that might not be
* the same on different platforms. Therefore, this hash should not be
* used for data exchange with different machines.
*
* @param obj a pointer to an arbitrary object
* @param len the length of the object in memory
* @return the hash key
*/
cx_attr_nodiscard
cx_attr_access_r(1, 2)
CX_EXPORT CxHashKey cx_hash_key(const void *obj, size_t len);
/**
* Computes a hash key from a UCX string.
*
* @param str the string
* @return the hash key
*/
cx_attr_nodiscard
CX_EXPORT CxHashKey cx_hash_key_cxstr(cxstring str);
/**
* Computes a hash key from a UCX string.
*
* @param str the string
* @return the hash key
*/
cx_attr_nodiscard
CX_EXPORT CxHashKey cx_hash_key_mutstr(cxmutstr str);
/**
* The identity function for the CX_HASH_KEY() macro.
* You should never need to use this manually.
*
* @param key the key
* @return a copy of the key
*/
cx_attr_nodiscard
CX_INLINE CxHashKey cx_hash_key_identity(CxHashKey key) {
return key;
}
#ifndef __cplusplus
/**
* Creates a hash key from any of the supported types with implicit length.
*
* Does nothing when passing a CxHashkey.
*
* Supported types are UCX strings, zero-terminated C strings,
* and 32-bit or 64-bit unsigned integers.
*
* @param key the key data
* @returns the @c CxHashKey
*/
#define CX_HASH_KEY(key) _Generic((key), \
CxHashKey: cx_hash_key_identity, \
cxstring: cx_hash_key_cxstr, \
cxmutstr: cx_hash_key_mutstr, \
char*: cx_hash_key_str, \
const char*: cx_hash_key_str, \
unsigned char*: cx_hash_key_ustr, \
const unsigned char*: cx_hash_key_ustr, \
uint32_t: cx_hash_key_u32, \
uint64_t: cx_hash_key_u64) \
(key)
#endif // __cplusplus
/**
* Compare function for hash keys.
*
* The pointers are untyped to be compatible with the cx_compare_func signature.
*
* @param left (@c CxHashKey*) the first key
* @param right (@c CxHashKey*) the second key
* @return zero when the keys equal, non-zero when they differ
*/
cx_attr_nodiscard cx_attr_nonnull
CX_EXPORT int cx_hash_key_cmp(const void *left, const void *right);
#ifdef __cplusplus
} // extern "C"
// ----------------------------------------------------------
// Overloads of CX_HASH_KEY (the C++ version of a _Generic)
// ----------------------------------------------------------
CX_CPPDECL CxHashKey CX_HASH_KEY(CxHashKey key) {
return key;
}
CX_CPPDECL CxHashKey CX_HASH_KEY(cxstring str) {
return cx_hash_key_cxstr(str);
}
CX_CPPDECL CxHashKey CX_HASH_KEY(cxmutstr str) {
return cx_hash_key_mutstr(str);
}
CX_CPPDECL CxHashKey CX_HASH_KEY(const char *str) {
return cx_hash_key_str(str);
}
CX_CPPDECL CxHashKey CX_HASH_KEY(const unsigned char *str) {
return cx_hash_key_ustr(str);
}
CX_CPPDECL CxHashKey CX_HASH_KEY(uint32_t key) {
return cx_hash_key_u32(key);
}
CX_CPPDECL CxHashKey CX_HASH_KEY(uint64_t key) {
return cx_hash_key_u64(key);
}
#endif
#endif // UCX_HASH_KEY_H