hash.h

Go to the documentation of this file.

/*                         H A S H . H
 * BRL-CAD
 *
 * Copyright (c) 2004-2026 United States Government as represented by
 * the U.S. Army Research Laboratory.
 *
 * This library is free software; you can redistribute it and/or
 * modify it under the terms of the GNU Lesser General Public License
 * version 2.1 as published by the Free Software Foundation.
 *
 * This library is distributed in the hope that it will be useful, but
 * WITHOUT ANY WARRANTY; without even the implied warranty of
 * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the GNU
 * Lesser General Public License for more details.
 *
 * You should have received a copy of the GNU Lesser General Public
 * License along with this file; see the file named COPYING for more
 * information.
 */
 
#ifndef BU_HASH_H
#define BU_HASH_H
 
#include "common.h"
 
#include "bu/defines.h"
 
__BEGIN_DECLS
 
/** @addtogroup bu_hash
 * @brief
 * An implementation of hash tables. TODO - need much better discussion here. Key points:
 *
 * 1. Keys are copied to the table and do not need to be maintained by the user
 * 2. All keys, regardless of original type, are handled as byte arrays.  Need
 *    examples of using strings and pointers as has keys
 * 3. Void pointers sorted as values are *not* copies - the application must keep
 *    the data pointed to by the pointers intact and not rely on the table.
 * 4. Performance is not currently a focus of bu_hash - it is not currently suitable
 *    for applications where high performance is critical.
 */
/** @{ */
/** @file bu/hash.h */
 
/* Use typedefs to hide the details of the hash entry and table structures */
typedef struct bu_hash_entry bu_hash_entry;
typedef struct bu_hash_tbl bu_hash_tbl;
 
 
/**
 * Create and initialize a hash table.  The input is the number of desired hash
 * bins.  This number will be rounded up to the nearest power of two, or a
 * minimal size if tbl_size is smaller than the internal minimum bin count.
 */
BU_EXPORT extern bu_hash_tbl *bu_hash_create(unsigned long tbl_size);
 
 
/**
 * Free all the memory associated with the specified hash table.
 *
 * Note that the keys are freed (they are copies), but the "values"
 * are not freed.  (The values are merely pointers)
 */
BU_EXPORT extern void bu_hash_destroy(bu_hash_tbl *t);
 
 
/**
 * Get the value stored in the hash table entry corresponding to the provided key
 *
 * @param[in] t - The hash table to look in
 * @param[in] key - the key to look for
 * @param[in] key_len - the length of the key in bytes
 *
 * @return
 * the void pointer stored in the hash table entry corresponding to key, or
 * NULL if no entry corresponding to key exists.
 */
BU_EXPORT extern void *bu_hash_get(const bu_hash_tbl *t, const uint8_t *key, size_t key_len);
 
 
/**
 * Set the value stored in the hash table entry corresponding to the provided
 * key to val, or if no entry corresponding to the provided key exists create a
 * new entry associating the key and value.  The key value is stored in the
 * hash entry, but the table does not maintain its own copy of val - ensuring
 * the value pointer remains valid is the responsibility of the caller.
 *
 * Null or zero length keys are not supported.  The table will also not store
 * a key/value combination where the value is NULL, but for random access with
 * bu_hash_get get this won't matter because the return value for a key not
 * in the table is NULL - i.e. the return will be the same as if the key/value
 * pair had actually been added.  The only use case where this property is observable
 * is when a user iterates over the whole contents of a hash table - in that
 * situation a key, NULL entry might be expected, but will not be present.
 *
 * @param[in] t - The hash table to look in
 * @param[in] key - the key to look for
 * @param[in] key_len - the length of the key in bytes
 * @param[in] val - the value to be associated with key
 *
 * @return
 * 1 if a new entry is created, 0 if an existing value was updated, -1 on error.
 */
BU_EXPORT extern int bu_hash_set(bu_hash_tbl *t, const uint8_t *key, size_t key_len, void *val);
 
 
/**
 * Remove the hash table entry associated with key from the table.
 *
 * @param[in] t - The hash table to look in
 * @param[in] key - the key to look for
 * @param[in] key_len - the length of the key in bytes
 */
BU_EXPORT extern void bu_hash_rm(bu_hash_tbl *t, const uint8_t *key, size_t key_len);
 
 
/**
 * Supports iteration of all the contents in a hash table.
 *
 * @param[in] t - The hash table to look in
 * @param[in] p - the previous entry in the iteration
 *
 * This example prints all values in a hash table:
 * @code
 * void print_vals(struct bu_hash_tbl *t) {
 *   struct bu_hash_entry *e = bu_hash_next(t, NULL);
 *   while (e) {
 *     bu_log("Value: %p\n", bu_hash_value(e, NULL));
 *     e = bu_hash_next(t, e);
 *   }
 * }
 * @endcode
 *
 * @return
 * Either first entry (if p is NULL) or next entry (if p is NON-null).  Returns
 * NULL when p is last entry in table.
 */
BU_EXPORT extern bu_hash_entry *bu_hash_next(bu_hash_tbl *t, bu_hash_entry *p);
 
 
/**
 * Supports iteration of all the contents in a hash table.
 *
 * @param[in] e - The hash table to look in
 *
 * @param[out] key - the entry's key
 * @param[out] key_len - the length of the entry's key
 *
 * @return
 * Returns 0 on success, 1 on failure.
 */
BU_EXPORT extern int bu_hash_key(bu_hash_entry *e, uint8_t **key, size_t *key_len);
 
 
/* returns value of bu_hash_entry if nval is NULL.
 * returns nval if nval was assigned to p's value.
 * returns NULL on error */
 
/**
 * Extracts or updates the void pointer value for a bu_hash_entry. If nval is
 * not NULL the entry will be updated.
 *
 * @param[in] e - The hash table to look in
 * @param[in] nval - The new void pointer to assign to the entry's value slot, or NULL if no assignment is to be made.
 *
 * @return Returns the hash entry's value pointer, or NULL on error.
 */
BU_EXPORT extern void *bu_hash_value(bu_hash_entry *e, void *nval);
 
/** @} */
 
 
 
/***************************************************************************
 * Given data, return an unsigned long long value based on a hashing
 * calculation.  Unlike bu_hash_tbl and its related functions, this
 * functionality does not implement key/value data storage - it's current
 * primary use case is generation of content-based UUIDs.
 *
 * We are deliberately not documenting the hashing algorithm used
 * to allow for "under the hood" improvements to its properties over time, and
 * there should be no assumption of the equality of the hashed value between
 * different versions of BRL-CAD.
 *
 * One of the uses for this function is to provide a "good enough" content-
 * based universally unique identifier, similarly to how Git uses SHA1 hashes
 * as UUIDs for commits.
 **************************************************************************/
BU_EXPORT unsigned long long
bu_data_hash(const void *data, size_t len);
 
/* bu_data_hash is the simple API, but there are situations where we need to
 * build up the data to be used for hashing from multiple inputs.  For that
 * case, the below API allows for updating a persistent hash state.
 */
struct bu_data_hash_impl;
struct bu_data_hash_state {
    struct bu_data_hash_impl *i;
};
 
BU_EXPORT struct bu_data_hash_state *
bu_data_hash_create(void);
 
BU_EXPORT void
bu_data_hash_destroy(struct bu_data_hash_state *s);
 
BU_EXPORT void
bu_data_hash_update(struct bu_data_hash_state *s, const void *data, size_t len);
 
BU_EXPORT unsigned long long
bu_data_hash_val(struct bu_data_hash_state *s);
 
 
/***************************************************************************
 * 128-bit fingerprint API - provides an extremely low probability for birthday
 * collisions (effectively zero for any realistic number of distinct inputs),
 * at the expense of API convenience.
 *
 * The result type bu_h128_t is a plain C struct (two uint64_t words) that is
 * ABI-stable and can be stored, compared, and copied with ordinary C code.
 *
 * C++ callers that need to use bu_h128_t as a key in std::unordered_map or
 * std::unordered_set will need to provide operator== (all 128 bits) and
 * std::hash<bu_h128_t> (folds to size_t for bucket placement only).  Those two
 * roles are intentionally separate: operator== provides strong uniqueness, while
 * std::hash's fold gives us a value suitable for the initial bucket key.  Below
 * is an example implementation.
 *
 * @code
 * inline bool operator==(const bu_h128_t &a, const bu_h128_t &b)
 * {
 *     return a.w[0] == b.w[0] && a.w[1] == b.w[1];
 * }
 *
 * // Bucket-placement hasher for bu_h128_t (performance only, not identity).
 * //
 * // This function maps a 128-bit fingerprint to a single std::size_t bucket
 * // index.  It is used exclusively for bucket selection; the container
 * // resolves actual equality with operator== (above), which inspects all
 * // 128 bits.
 * //
 * // Folding to std::size_t increases *bucket* collision probability back to
 * // roughly N^2 / 2^65 on 64-bit platforms – that is intentional and
 * // harmless: a bucket collision only lengthens one chain by one node, it
 * // never causes a false identity match.  See the file-level comment for
 * // a full explanation of the two-level collision model.
 * //
 * // Implementation: XOR the two 64-bit halves (both have XXH3's excellent
 * // avalanche properties), then fold to size_t width for 32-bit platforms.
 * namespace std {
 *   template<>
 *   struct hash<bu_h128_t> {
 *       std::size_t operator()(const bu_h128_t &h) const noexcept {
 *           // XOR the two 64-bit halves, then fold to size_t width.
 *           // On 64-bit platforms this is a no-op truncation.
 *           // On 32-bit platforms the extra shift folds the upper 32
 *           // bits of the XOR result into the lower 32 before the cast.
 *           uint64_t v = h.w[0] ^ h.w[1];
 *           if (sizeof(std::size_t) < sizeof(uint64_t))
 *              v ^= (v >> 32);
 *           return (std::size_t)v;
 *       }
 *   };
 * } // namespace std
 * @endcode
 *
 * Note:  the implementation hash as of 2026/03/09 is XXH3-128, whose
 * birthday-bound identity-collision probability is N^2 / 2^129. HOWEVER, while
 * we are documenting this to illustrate why callers might want to use a 128
 * bit hash instead of the 64 bit version, the specific underlying hash
 * algorithm is deliberately and explicitly NOT part of the public contract.
 * We may change the under-the-hood algorithm and implementation at any time,
 * so no numerical stability of the hash values between releases can be
 * assumed.
 **************************************************************************/
 
/**
 * A C-compatible 128-bit fingerprint.
 * w[0] holds bits 0-63 (the low half); w[1] holds bits 64-127 (the high half).
 */
struct bu_h128_t {
    uint64_t w[2];
};
typedef struct bu_h128_t bu_h128_t;
 
/** One-shot 128-bit hash of @p len bytes starting at @p data. */
BU_EXPORT bu_h128_t
bu_data_hash128(const void *data, size_t len);
 
/** Streaming 128-bit hash: opaque state object. */
struct bu_data_hash128_impl;
struct bu_data_hash128_state {
    struct bu_data_hash128_impl *i;
};
 
BU_EXPORT struct bu_data_hash128_state *
bu_data_hash128_create(void);
 
BU_EXPORT void
bu_data_hash128_destroy(struct bu_data_hash128_state *s);
 
BU_EXPORT void
bu_data_hash128_update(struct bu_data_hash128_state *s, const void *data, size_t len);
 
/** Finalise the stream and return the 128-bit digest. */
BU_EXPORT bu_h128_t
bu_data_hash128_val(struct bu_data_hash128_state *s);
 
 
__END_DECLS
 
#endif  /* BU_HASH_H */
 
 
/*
 * Local Variables:
 * mode: C
 * tab-width: 8
 * indent-tabs-mode: t
 * c-file-style: "stroustrup"
 * End:
 * ex: shiftwidth=4 tabstop=8
 */