mirror of
https://codeberg.org/noisytoot/notnotdnethack.git
synced 2025-05-22 23:37:09 +01:00
bbdba1f428
Use a hashmap linking strings to colors and attributes so that we can spend less time evaluating regexs. Also record the last turn on which a coloring was used, and every 1000 turns free all entries that haven't been used for more than 1000 turns. This uses https://github.com/sheredom/hashmap.h and includes it in dnhethack's sources. As it is released into the public domain under unlicense, I believe this causes no problems.
737 lines
24 KiB
C
737 lines
24 KiB
C
/*
|
|
The latest version of this library is available on GitHub;
|
|
https://github.com/sheredom/hashmap.h
|
|
*/
|
|
|
|
/*
|
|
This is free and unencumbered software released into the public domain.
|
|
|
|
Anyone is free to copy, modify, publish, use, compile, sell, or
|
|
distribute this software, either in source code form or as a compiled
|
|
binary, for any purpose, commercial or non-commercial, and by any
|
|
means.
|
|
|
|
In jurisdictions that recognize copyright laws, the author or authors
|
|
of this software dedicate any and all copyright interest in the
|
|
software to the public domain. We make this dedication for the benefit
|
|
of the public at large and to the detriment of our heirs and
|
|
successors. We intend this dedication to be an overt act of
|
|
relinquishment in perpetuity of all present and future rights to this
|
|
software under copyright law.
|
|
|
|
THE SOFTWARE IS PROVIDED "AS IS", WITHOUT WARRANTY OF ANY KIND,
|
|
EXPRESS OR IMPLIED, INCLUDING BUT NOT LIMITED TO THE WARRANTIES OF
|
|
MERCHANTABILITY, FITNESS FOR A PARTICULAR PURPOSE AND NONINFRINGEMENT.
|
|
IN NO EVENT SHALL THE AUTHORS BE LIABLE FOR ANY CLAIM, DAMAGES OR
|
|
OTHER LIABILITY, WHETHER IN AN ACTION OF CONTRACT, TORT OR OTHERWISE,
|
|
ARISING FROM, OUT OF OR IN CONNECTION WITH THE SOFTWARE OR THE USE OR
|
|
OTHER DEALINGS IN THE SOFTWARE.
|
|
|
|
For more information, please refer to <http://unlicense.org/>
|
|
*/
|
|
#ifndef SHEREDOM_HASHMAP_H_INCLUDED
|
|
#define SHEREDOM_HASHMAP_H_INCLUDED
|
|
|
|
#if defined(_MSC_VER)
|
|
// Workaround a bug in the MSVC runtime where it uses __cplusplus when not
|
|
// defined.
|
|
#pragma warning(push, 0)
|
|
#pragma warning(disable : 4668)
|
|
#endif
|
|
|
|
#include <stdlib.h>
|
|
#include <string.h>
|
|
|
|
#if (defined(_MSC_VER) && defined(__AVX__)) || \
|
|
(!defined(_MSC_VER) && defined(__SSE4_2__))
|
|
#define HASHMAP_X86_SSE42
|
|
#endif
|
|
|
|
#if defined(HASHMAP_X86_SSE42)
|
|
#include <nmmintrin.h>
|
|
#endif
|
|
|
|
#if defined(__aarch64__) && defined(__ARM_FEATURE_CRC32)
|
|
#define HASHMAP_ARM_CRC32
|
|
#endif
|
|
|
|
#if defined(HASHMAP_ARM_CRC32)
|
|
#include <arm_acle.h>
|
|
#endif
|
|
|
|
#if defined(_MSC_VER)
|
|
#include <intrin.h>
|
|
#endif
|
|
|
|
#if defined(_MSC_VER)
|
|
#pragma warning(pop)
|
|
#endif
|
|
|
|
#if defined(_MSC_VER)
|
|
#pragma warning(push)
|
|
/* Stop MSVC complaining about unreferenced functions */
|
|
#pragma warning(disable : 4505)
|
|
/* Stop MSVC complaining about not inlining functions */
|
|
#pragma warning(disable : 4710)
|
|
/* Stop MSVC complaining about inlining functions! */
|
|
#pragma warning(disable : 4711)
|
|
#endif
|
|
|
|
#if defined(__clang__)
|
|
#pragma clang diagnostic push
|
|
#pragma clang diagnostic ignored "-Wunused-function"
|
|
#pragma clang diagnostic ignored "-Wstatic-in-inline"
|
|
|
|
#if __has_warning("-Wunsafe-buffer-usage")
|
|
#pragma clang diagnostic ignored "-Wunsafe-buffer-usage"
|
|
#endif
|
|
#endif
|
|
|
|
#if defined(__TINYC__)
|
|
#define HASHMAP_ATTRIBUTE(a) __attribute((a))
|
|
#else
|
|
#define HASHMAP_ATTRIBUTE(a) __attribute__((a))
|
|
#endif
|
|
|
|
#if defined(_MSC_VER)
|
|
#define HASHMAP_WEAK __inline
|
|
#elif defined(__MINGW32__) || defined(__MINGW64__)
|
|
#define HASHMAP_WEAK static HASHMAP_ATTRIBUTE(used)
|
|
#elif defined(__clang__) || defined(__GNUC__) || defined(__TINYC__)
|
|
#define HASHMAP_WEAK HASHMAP_ATTRIBUTE(weak)
|
|
#else
|
|
#error Non clang, non gcc, non MSVC, non tcc compiler found!
|
|
#endif
|
|
|
|
#if defined(_MSC_VER)
|
|
#define HASHMAP_ALWAYS_INLINE __forceinline
|
|
#elif (defined(__STDC_VERSION__) && (__STDC_VERSION__ >= 199901L)) || \
|
|
defined(__cplusplus)
|
|
#define HASHMAP_ALWAYS_INLINE __attribute__((always_inline)) inline
|
|
#else
|
|
/* If we cannot use inline, its not safe to use always_inline, so we mark the
|
|
* function weak. */
|
|
#define HASHMAP_ALWAYS_INLINE HASHMAP_WEAK
|
|
#endif
|
|
|
|
#if defined(_MSC_VER) && (_MSC_VER < 1920)
|
|
typedef unsigned __int8 hashmap_uint8_t;
|
|
typedef unsigned __int32 hashmap_uint32_t;
|
|
typedef unsigned __int64 hashmap_uint64_t;
|
|
#else
|
|
#include <stdint.h>
|
|
typedef uint8_t hashmap_uint8_t;
|
|
typedef uint32_t hashmap_uint32_t;
|
|
typedef uint64_t hashmap_uint64_t;
|
|
#endif
|
|
|
|
typedef struct hashmap_element_s {
|
|
const void *key;
|
|
hashmap_uint32_t key_len;
|
|
int in_use;
|
|
void *data;
|
|
} hashmap_element_t;
|
|
|
|
typedef hashmap_uint32_t (*hashmap_hasher_t)(hashmap_uint32_t seed,
|
|
const void *key,
|
|
hashmap_uint32_t key_len);
|
|
typedef int (*hashmap_comparer_t)(const void *a, hashmap_uint32_t a_len,
|
|
const void *b, hashmap_uint32_t b_len);
|
|
|
|
typedef struct hashmap_s {
|
|
hashmap_uint32_t log2_capacity;
|
|
hashmap_uint32_t size;
|
|
hashmap_hasher_t hasher;
|
|
hashmap_comparer_t comparer;
|
|
struct hashmap_element_s *data;
|
|
} hashmap_t;
|
|
|
|
#define HASHMAP_LINEAR_PROBE_LENGTH (8)
|
|
|
|
typedef struct hashmap_create_options_s {
|
|
hashmap_hasher_t hasher;
|
|
hashmap_comparer_t comparer;
|
|
hashmap_uint32_t initial_capacity;
|
|
hashmap_uint32_t _;
|
|
} hashmap_create_options_t;
|
|
|
|
#if defined(__cplusplus)
|
|
extern "C" {
|
|
#endif
|
|
|
|
/// @brief Create a hashmap.
|
|
/// @param initial_capacity The initial capacity of the hashmap.
|
|
/// @param out_hashmap The storage for the created hashmap.
|
|
/// @return On success 0 is returned.
|
|
HASHMAP_WEAK int hashmap_create(const hashmap_uint32_t initial_capacity,
|
|
struct hashmap_s *const out_hashmap);
|
|
|
|
/// @brief Create a hashmap.
|
|
/// @param options The options to create the hashmap with.
|
|
/// @param out_hashmap The storage for the created hashmap.
|
|
/// @return On success 0 is returned.
|
|
///
|
|
/// The options members work as follows:
|
|
/// - initial_capacity The initial capacity of the hashmap.
|
|
/// - hasher Which hashing function to use with the hashmap (by default the
|
|
// crc32 with Robert Jenkins' mix is used).
|
|
HASHMAP_WEAK int hashmap_create_ex(struct hashmap_create_options_s options,
|
|
struct hashmap_s *const out_hashmap);
|
|
|
|
/// @brief Put an element into the hashmap.
|
|
/// @param hashmap The hashmap to insert into.
|
|
/// @param key The string key to use.
|
|
/// @param len The length of the string key.
|
|
/// @param value The value to insert.
|
|
/// @return On success 0 is returned.
|
|
///
|
|
/// The key string slice is not copied when creating the hashmap entry, and thus
|
|
/// must remain a valid pointer until the hashmap entry is removed or the
|
|
/// hashmap is destroyed.
|
|
HASHMAP_WEAK int hashmap_put(struct hashmap_s *const hashmap,
|
|
const void *const key, const hashmap_uint32_t len,
|
|
void *const value);
|
|
|
|
/// @brief Get an element from the hashmap.
|
|
/// @param hashmap The hashmap to get from.
|
|
/// @param key The string key to use.
|
|
/// @param len The length of the string key.
|
|
/// @return The previously set element, or NULL if none exists.
|
|
HASHMAP_WEAK void *hashmap_get(const struct hashmap_s *const hashmap,
|
|
const void *const key,
|
|
const hashmap_uint32_t len);
|
|
|
|
/// @brief Remove an element from the hashmap.
|
|
/// @param hashmap The hashmap to remove from.
|
|
/// @param key The string key to use.
|
|
/// @param len The length of the string key.
|
|
/// @return On success 0 is returned.
|
|
HASHMAP_WEAK int hashmap_remove(struct hashmap_s *const hashmap,
|
|
const void *const key,
|
|
const hashmap_uint32_t len);
|
|
|
|
/// @brief Remove an element from the hashmap.
|
|
/// @param hashmap The hashmap to remove from.
|
|
/// @param key The string key to use.
|
|
/// @param len The length of the string key.
|
|
/// @return On success the original stored key pointer is returned, on failure
|
|
/// NULL is returned.
|
|
HASHMAP_WEAK const void *
|
|
hashmap_remove_and_return_key(struct hashmap_s *const hashmap,
|
|
const void *const key,
|
|
const hashmap_uint32_t len);
|
|
|
|
/// @brief Iterate over all the elements in a hashmap.
|
|
/// @param hashmap The hashmap to iterate over.
|
|
/// @param iterator The function pointer to call on each element.
|
|
/// @param context The context to pass as the first argument to f.
|
|
/// @return If the entire hashmap was iterated then 0 is returned. Otherwise if
|
|
/// the callback function f returned non-zero then non-zero is returned.
|
|
HASHMAP_WEAK int hashmap_iterate(const struct hashmap_s *const hashmap,
|
|
int (*iterator)(void *const context,
|
|
void *const value),
|
|
void *const context);
|
|
|
|
/// @brief Iterate over all the elements in a hashmap.
|
|
/// @param hashmap The hashmap to iterate over.
|
|
/// @param iterator The function pointer to call on each element.
|
|
/// @param context The context to pass as the first argument to f.
|
|
/// @return If the entire hashmap was iterated then 0 is returned.
|
|
/// Otherwise if the callback function f returned positive then the positive
|
|
/// value is returned. If the callback function returns -1, the current item
|
|
/// is removed and iteration continues.
|
|
HASHMAP_WEAK int hashmap_iterate_pairs(
|
|
struct hashmap_s *const hashmap,
|
|
int (*iterator)(void *const, struct hashmap_element_s *const),
|
|
void *const context);
|
|
|
|
/// @brief Get the size of the hashmap.
|
|
/// @param hashmap The hashmap to get the size of.
|
|
/// @return The size of the hashmap.
|
|
HASHMAP_ALWAYS_INLINE hashmap_uint32_t
|
|
hashmap_num_entries(const struct hashmap_s *const hashmap);
|
|
|
|
/// @brief Get the capacity of the hashmap.
|
|
/// @param hashmap The hashmap to get the size of.
|
|
/// @return The capacity of the hashmap.
|
|
HASHMAP_ALWAYS_INLINE hashmap_uint32_t
|
|
hashmap_capacity(const struct hashmap_s *const hashmap);
|
|
|
|
/// @brief Destroy the hashmap.
|
|
/// @param hashmap The hashmap to destroy.
|
|
HASHMAP_WEAK void hashmap_destroy(struct hashmap_s *const hashmap);
|
|
|
|
static hashmap_uint32_t hashmap_crc32_hasher(const hashmap_uint32_t seed,
|
|
const void *const s,
|
|
const hashmap_uint32_t len);
|
|
static int hashmap_memcmp_comparer(const void *const a,
|
|
const hashmap_uint32_t a_len,
|
|
const void *const b,
|
|
const hashmap_uint32_t b_len);
|
|
HASHMAP_ALWAYS_INLINE hashmap_uint32_t hashmap_hash_helper_int_helper(
|
|
const struct hashmap_s *const m, const void *const key,
|
|
const hashmap_uint32_t len);
|
|
HASHMAP_ALWAYS_INLINE int
|
|
hashmap_hash_helper(const struct hashmap_s *const m, const void *const key,
|
|
const hashmap_uint32_t len,
|
|
hashmap_uint32_t *const out_index);
|
|
HASHMAP_WEAK int hashmap_rehash_iterator(void *const new_hash,
|
|
struct hashmap_element_s *const e);
|
|
HASHMAP_ALWAYS_INLINE int hashmap_rehash_helper(struct hashmap_s *const m);
|
|
HASHMAP_ALWAYS_INLINE hashmap_uint32_t hashmap_clz(const hashmap_uint32_t x);
|
|
|
|
#if defined(__cplusplus)
|
|
}
|
|
#endif
|
|
|
|
#if defined(__cplusplus)
|
|
#define HASHMAP_CAST(type, x) static_cast<type>(x)
|
|
#define HASHMAP_PTR_CAST(type, x) reinterpret_cast<type>(x)
|
|
#define HASHMAP_NULL NULL
|
|
#else
|
|
#define HASHMAP_CAST(type, x) ((type)(x))
|
|
#define HASHMAP_PTR_CAST(type, x) ((type)(x))
|
|
#define HASHMAP_NULL 0
|
|
#endif
|
|
|
|
int hashmap_create(const hashmap_uint32_t initial_capacity,
|
|
struct hashmap_s *const out_hashmap) {
|
|
struct hashmap_create_options_s options;
|
|
memset(&options, 0, sizeof(options));
|
|
options.initial_capacity = initial_capacity;
|
|
|
|
return hashmap_create_ex(options, out_hashmap);
|
|
}
|
|
|
|
int hashmap_create_ex(struct hashmap_create_options_s options,
|
|
struct hashmap_s *const out_hashmap) {
|
|
if (2 > options.initial_capacity) {
|
|
options.initial_capacity = 2;
|
|
} else if (0 != (options.initial_capacity & (options.initial_capacity - 1))) {
|
|
options.initial_capacity = 1u
|
|
<< (32 - hashmap_clz(options.initial_capacity));
|
|
}
|
|
|
|
if (HASHMAP_NULL == options.hasher) {
|
|
options.hasher = &hashmap_crc32_hasher;
|
|
}
|
|
|
|
if (HASHMAP_NULL == options.comparer) {
|
|
options.comparer = &hashmap_memcmp_comparer;
|
|
}
|
|
|
|
out_hashmap->data = HASHMAP_CAST(
|
|
struct hashmap_element_s *,
|
|
calloc(options.initial_capacity + HASHMAP_LINEAR_PROBE_LENGTH,
|
|
sizeof(struct hashmap_element_s)));
|
|
|
|
out_hashmap->log2_capacity = 31 - hashmap_clz(options.initial_capacity);
|
|
out_hashmap->size = 0;
|
|
out_hashmap->hasher = options.hasher;
|
|
out_hashmap->comparer = options.comparer;
|
|
|
|
return 0;
|
|
}
|
|
|
|
int hashmap_put(struct hashmap_s *const m, const void *const key,
|
|
const hashmap_uint32_t len, void *const value) {
|
|
hashmap_uint32_t index;
|
|
|
|
if ((HASHMAP_NULL == key) || (0 == len)) {
|
|
return 1;
|
|
}
|
|
|
|
/* Find a place to put our value. */
|
|
while (!hashmap_hash_helper(m, key, len, &index)) {
|
|
if (hashmap_rehash_helper(m)) {
|
|
return 1;
|
|
}
|
|
}
|
|
|
|
/* Set the data. */
|
|
m->data[index].data = value;
|
|
m->data[index].key = key;
|
|
m->data[index].key_len = len;
|
|
|
|
/* If the hashmap element was not already in use, set that it is being used
|
|
* and bump our size. */
|
|
if (0 == m->data[index].in_use) {
|
|
m->data[index].in_use = 1;
|
|
m->size++;
|
|
}
|
|
|
|
return 0;
|
|
}
|
|
|
|
void *hashmap_get(const struct hashmap_s *const m, const void *const key,
|
|
const hashmap_uint32_t len) {
|
|
hashmap_uint32_t i, curr;
|
|
|
|
if ((HASHMAP_NULL == key) || (0 == len)) {
|
|
return HASHMAP_NULL;
|
|
}
|
|
|
|
curr = hashmap_hash_helper_int_helper(m, key, len);
|
|
|
|
/* Linear probing, if necessary */
|
|
for (i = 0; i < HASHMAP_LINEAR_PROBE_LENGTH; i++) {
|
|
const hashmap_uint32_t index = curr + i;
|
|
|
|
if (m->data[index].in_use) {
|
|
if (m->comparer(m->data[index].key, m->data[index].key_len, key, len)) {
|
|
return m->data[index].data;
|
|
}
|
|
}
|
|
}
|
|
|
|
/* Not found */
|
|
return HASHMAP_NULL;
|
|
}
|
|
|
|
int hashmap_remove(struct hashmap_s *const m, const void *const key,
|
|
const hashmap_uint32_t len) {
|
|
hashmap_uint32_t i, curr;
|
|
|
|
if ((HASHMAP_NULL == key) || (0 == len)) {
|
|
return 1;
|
|
}
|
|
|
|
curr = hashmap_hash_helper_int_helper(m, key, len);
|
|
|
|
/* Linear probing, if necessary */
|
|
for (i = 0; i < HASHMAP_LINEAR_PROBE_LENGTH; i++) {
|
|
const hashmap_uint32_t index = curr + i;
|
|
|
|
if (m->data[index].in_use) {
|
|
if (m->comparer(m->data[index].key, m->data[index].key_len, key, len)) {
|
|
/* Blank out the fields including in_use */
|
|
memset(&m->data[index], 0, sizeof(struct hashmap_element_s));
|
|
|
|
/* Reduce the size */
|
|
m->size--;
|
|
|
|
return 0;
|
|
}
|
|
}
|
|
}
|
|
|
|
return 1;
|
|
}
|
|
|
|
const void *hashmap_remove_and_return_key(struct hashmap_s *const m,
|
|
const void *const key,
|
|
const hashmap_uint32_t len) {
|
|
hashmap_uint32_t i, curr;
|
|
|
|
if ((HASHMAP_NULL == key) || (0 == len)) {
|
|
return HASHMAP_NULL;
|
|
}
|
|
|
|
curr = hashmap_hash_helper_int_helper(m, key, len);
|
|
|
|
/* Linear probing, if necessary */
|
|
for (i = 0; i < HASHMAP_LINEAR_PROBE_LENGTH; i++) {
|
|
const hashmap_uint32_t index = curr + i;
|
|
|
|
if (m->data[index].in_use) {
|
|
if (m->comparer(m->data[index].key, m->data[index].key_len, key, len)) {
|
|
const void *const stored_key = m->data[index].key;
|
|
|
|
/* Blank out the fields */
|
|
memset(&m->data[index], 0, sizeof(struct hashmap_element_s));
|
|
|
|
/* Reduce the size */
|
|
m->size--;
|
|
|
|
return stored_key;
|
|
}
|
|
}
|
|
}
|
|
|
|
return HASHMAP_NULL;
|
|
}
|
|
|
|
int hashmap_iterate(const struct hashmap_s *const m,
|
|
int (*f)(void *const, void *const), void *const context) {
|
|
hashmap_uint32_t i;
|
|
|
|
for (i = 0; i < (hashmap_capacity(m) + HASHMAP_LINEAR_PROBE_LENGTH); i++) {
|
|
if (m->data[i].in_use) {
|
|
if (!f(context, m->data[i].data)) {
|
|
return 1;
|
|
}
|
|
}
|
|
}
|
|
|
|
return 0;
|
|
}
|
|
|
|
int hashmap_iterate_pairs(struct hashmap_s *const m,
|
|
int (*f)(void *const,
|
|
struct hashmap_element_s *const),
|
|
void *const context) {
|
|
hashmap_uint32_t i;
|
|
struct hashmap_element_s *p;
|
|
int r;
|
|
|
|
for (i = 0; i < (hashmap_capacity(m) + HASHMAP_LINEAR_PROBE_LENGTH); i++) {
|
|
p = &m->data[i];
|
|
if (p->in_use) {
|
|
r = f(context, p);
|
|
switch (r) {
|
|
case -1: /* remove item */
|
|
memset(p, 0, sizeof(struct hashmap_element_s));
|
|
m->size--;
|
|
break;
|
|
case 0: /* continue iterating */
|
|
break;
|
|
default: /* early exit */
|
|
return 1;
|
|
}
|
|
}
|
|
}
|
|
return 0;
|
|
}
|
|
|
|
void hashmap_destroy(struct hashmap_s *const m) {
|
|
free(m->data);
|
|
memset(m, 0, sizeof(struct hashmap_s));
|
|
}
|
|
|
|
HASHMAP_ALWAYS_INLINE hashmap_uint32_t
|
|
hashmap_num_entries(const struct hashmap_s *const m) {
|
|
return m->size;
|
|
}
|
|
|
|
HASHMAP_ALWAYS_INLINE hashmap_uint32_t
|
|
hashmap_capacity(const struct hashmap_s *const m) {
|
|
return 1u << m->log2_capacity;
|
|
}
|
|
|
|
hashmap_uint32_t hashmap_crc32_hasher(const hashmap_uint32_t seed,
|
|
const void *const k,
|
|
const hashmap_uint32_t len) {
|
|
hashmap_uint32_t i = 0;
|
|
hashmap_uint32_t crc32val = seed;
|
|
const hashmap_uint8_t *const s = HASHMAP_PTR_CAST(const hashmap_uint8_t *, k);
|
|
|
|
#if defined(HASHMAP_X86_SSE42)
|
|
for (; (i + sizeof(hashmap_uint32_t)) < len; i += sizeof(hashmap_uint32_t)) {
|
|
hashmap_uint32_t next;
|
|
memcpy(&next, &s[i], sizeof(next));
|
|
crc32val = _mm_crc32_u32(crc32val, next);
|
|
}
|
|
|
|
for (; i < len; i++) {
|
|
crc32val = _mm_crc32_u8(crc32val, s[i]);
|
|
}
|
|
#elif defined(HASHMAP_ARM_CRC32)
|
|
for (; (i + sizeof(hashmap_uint64_t)) < len; i += sizeof(hashmap_uint64_t)) {
|
|
hashmap_uint64_t next;
|
|
memcpy(&next, &s[i], sizeof(next));
|
|
crc32val = __crc32d(crc32val, next);
|
|
}
|
|
|
|
for (; i < len; i++) {
|
|
crc32val = __crc32b(crc32val, s[i]);
|
|
}
|
|
#else
|
|
// Using polynomial 0x11EDC6F41 to match SSE 4.2's crc function.
|
|
static const hashmap_uint32_t crc32_tab[] = {
|
|
0x00000000U, 0xF26B8303U, 0xE13B70F7U, 0x1350F3F4U, 0xC79A971FU,
|
|
0x35F1141CU, 0x26A1E7E8U, 0xD4CA64EBU, 0x8AD958CFU, 0x78B2DBCCU,
|
|
0x6BE22838U, 0x9989AB3BU, 0x4D43CFD0U, 0xBF284CD3U, 0xAC78BF27U,
|
|
0x5E133C24U, 0x105EC76FU, 0xE235446CU, 0xF165B798U, 0x030E349BU,
|
|
0xD7C45070U, 0x25AFD373U, 0x36FF2087U, 0xC494A384U, 0x9A879FA0U,
|
|
0x68EC1CA3U, 0x7BBCEF57U, 0x89D76C54U, 0x5D1D08BFU, 0xAF768BBCU,
|
|
0xBC267848U, 0x4E4DFB4BU, 0x20BD8EDEU, 0xD2D60DDDU, 0xC186FE29U,
|
|
0x33ED7D2AU, 0xE72719C1U, 0x154C9AC2U, 0x061C6936U, 0xF477EA35U,
|
|
0xAA64D611U, 0x580F5512U, 0x4B5FA6E6U, 0xB93425E5U, 0x6DFE410EU,
|
|
0x9F95C20DU, 0x8CC531F9U, 0x7EAEB2FAU, 0x30E349B1U, 0xC288CAB2U,
|
|
0xD1D83946U, 0x23B3BA45U, 0xF779DEAEU, 0x05125DADU, 0x1642AE59U,
|
|
0xE4292D5AU, 0xBA3A117EU, 0x4851927DU, 0x5B016189U, 0xA96AE28AU,
|
|
0x7DA08661U, 0x8FCB0562U, 0x9C9BF696U, 0x6EF07595U, 0x417B1DBCU,
|
|
0xB3109EBFU, 0xA0406D4BU, 0x522BEE48U, 0x86E18AA3U, 0x748A09A0U,
|
|
0x67DAFA54U, 0x95B17957U, 0xCBA24573U, 0x39C9C670U, 0x2A993584U,
|
|
0xD8F2B687U, 0x0C38D26CU, 0xFE53516FU, 0xED03A29BU, 0x1F682198U,
|
|
0x5125DAD3U, 0xA34E59D0U, 0xB01EAA24U, 0x42752927U, 0x96BF4DCCU,
|
|
0x64D4CECFU, 0x77843D3BU, 0x85EFBE38U, 0xDBFC821CU, 0x2997011FU,
|
|
0x3AC7F2EBU, 0xC8AC71E8U, 0x1C661503U, 0xEE0D9600U, 0xFD5D65F4U,
|
|
0x0F36E6F7U, 0x61C69362U, 0x93AD1061U, 0x80FDE395U, 0x72966096U,
|
|
0xA65C047DU, 0x5437877EU, 0x4767748AU, 0xB50CF789U, 0xEB1FCBADU,
|
|
0x197448AEU, 0x0A24BB5AU, 0xF84F3859U, 0x2C855CB2U, 0xDEEEDFB1U,
|
|
0xCDBE2C45U, 0x3FD5AF46U, 0x7198540DU, 0x83F3D70EU, 0x90A324FAU,
|
|
0x62C8A7F9U, 0xB602C312U, 0x44694011U, 0x5739B3E5U, 0xA55230E6U,
|
|
0xFB410CC2U, 0x092A8FC1U, 0x1A7A7C35U, 0xE811FF36U, 0x3CDB9BDDU,
|
|
0xCEB018DEU, 0xDDE0EB2AU, 0x2F8B6829U, 0x82F63B78U, 0x709DB87BU,
|
|
0x63CD4B8FU, 0x91A6C88CU, 0x456CAC67U, 0xB7072F64U, 0xA457DC90U,
|
|
0x563C5F93U, 0x082F63B7U, 0xFA44E0B4U, 0xE9141340U, 0x1B7F9043U,
|
|
0xCFB5F4A8U, 0x3DDE77ABU, 0x2E8E845FU, 0xDCE5075CU, 0x92A8FC17U,
|
|
0x60C37F14U, 0x73938CE0U, 0x81F80FE3U, 0x55326B08U, 0xA759E80BU,
|
|
0xB4091BFFU, 0x466298FCU, 0x1871A4D8U, 0xEA1A27DBU, 0xF94AD42FU,
|
|
0x0B21572CU, 0xDFEB33C7U, 0x2D80B0C4U, 0x3ED04330U, 0xCCBBC033U,
|
|
0xA24BB5A6U, 0x502036A5U, 0x4370C551U, 0xB11B4652U, 0x65D122B9U,
|
|
0x97BAA1BAU, 0x84EA524EU, 0x7681D14DU, 0x2892ED69U, 0xDAF96E6AU,
|
|
0xC9A99D9EU, 0x3BC21E9DU, 0xEF087A76U, 0x1D63F975U, 0x0E330A81U,
|
|
0xFC588982U, 0xB21572C9U, 0x407EF1CAU, 0x532E023EU, 0xA145813DU,
|
|
0x758FE5D6U, 0x87E466D5U, 0x94B49521U, 0x66DF1622U, 0x38CC2A06U,
|
|
0xCAA7A905U, 0xD9F75AF1U, 0x2B9CD9F2U, 0xFF56BD19U, 0x0D3D3E1AU,
|
|
0x1E6DCDEEU, 0xEC064EEDU, 0xC38D26C4U, 0x31E6A5C7U, 0x22B65633U,
|
|
0xD0DDD530U, 0x0417B1DBU, 0xF67C32D8U, 0xE52CC12CU, 0x1747422FU,
|
|
0x49547E0BU, 0xBB3FFD08U, 0xA86F0EFCU, 0x5A048DFFU, 0x8ECEE914U,
|
|
0x7CA56A17U, 0x6FF599E3U, 0x9D9E1AE0U, 0xD3D3E1ABU, 0x21B862A8U,
|
|
0x32E8915CU, 0xC083125FU, 0x144976B4U, 0xE622F5B7U, 0xF5720643U,
|
|
0x07198540U, 0x590AB964U, 0xAB613A67U, 0xB831C993U, 0x4A5A4A90U,
|
|
0x9E902E7BU, 0x6CFBAD78U, 0x7FAB5E8CU, 0x8DC0DD8FU, 0xE330A81AU,
|
|
0x115B2B19U, 0x020BD8EDU, 0xF0605BEEU, 0x24AA3F05U, 0xD6C1BC06U,
|
|
0xC5914FF2U, 0x37FACCF1U, 0x69E9F0D5U, 0x9B8273D6U, 0x88D28022U,
|
|
0x7AB90321U, 0xAE7367CAU, 0x5C18E4C9U, 0x4F48173DU, 0xBD23943EU,
|
|
0xF36E6F75U, 0x0105EC76U, 0x12551F82U, 0xE03E9C81U, 0x34F4F86AU,
|
|
0xC69F7B69U, 0xD5CF889DU, 0x27A40B9EU, 0x79B737BAU, 0x8BDCB4B9U,
|
|
0x988C474DU, 0x6AE7C44EU, 0xBE2DA0A5U, 0x4C4623A6U, 0x5F16D052U,
|
|
0xAD7D5351U};
|
|
|
|
for (; i < len; i++) {
|
|
crc32val = crc32_tab[(HASHMAP_CAST(hashmap_uint8_t, crc32val) ^ s[i])] ^
|
|
(crc32val >> 8);
|
|
}
|
|
#endif
|
|
|
|
// Use the mix function from murmur3.
|
|
crc32val ^= len;
|
|
|
|
crc32val ^= crc32val >> 16;
|
|
crc32val *= 0x85ebca6b;
|
|
crc32val ^= crc32val >> 13;
|
|
crc32val *= 0xc2b2ae35;
|
|
crc32val ^= crc32val >> 16;
|
|
|
|
return crc32val;
|
|
}
|
|
|
|
int hashmap_memcmp_comparer(const void *const a, const hashmap_uint32_t a_len,
|
|
const void *const b, const hashmap_uint32_t b_len) {
|
|
return (a_len == b_len) && (0 == memcmp(a, b, a_len));
|
|
}
|
|
|
|
HASHMAP_ALWAYS_INLINE hashmap_uint32_t
|
|
hashmap_hash_helper_int_helper(const struct hashmap_s *const m,
|
|
const void *const k, const hashmap_uint32_t l) {
|
|
return (m->hasher(~0u, k, l) * 2654435769u) >> (32u - m->log2_capacity);
|
|
}
|
|
|
|
HASHMAP_ALWAYS_INLINE int
|
|
hashmap_hash_helper(const struct hashmap_s *const m, const void *const key,
|
|
const hashmap_uint32_t len,
|
|
hashmap_uint32_t *const out_index) {
|
|
hashmap_uint32_t curr;
|
|
hashmap_uint32_t i;
|
|
hashmap_uint32_t first_free;
|
|
|
|
/* If full, return immediately */
|
|
if (hashmap_num_entries(m) == hashmap_capacity(m)) {
|
|
return 0;
|
|
}
|
|
|
|
/* Find the best index */
|
|
curr = hashmap_hash_helper_int_helper(m, key, len);
|
|
first_free = ~0u;
|
|
|
|
for (i = 0; i < HASHMAP_LINEAR_PROBE_LENGTH; i++) {
|
|
const hashmap_uint32_t index = curr + i;
|
|
|
|
if (!m->data[index].in_use) {
|
|
first_free = (first_free < index) ? first_free : index;
|
|
} else if (m->comparer(m->data[index].key, m->data[index].key_len, key,
|
|
len)) {
|
|
*out_index = index;
|
|
return 1;
|
|
}
|
|
}
|
|
|
|
// Couldn't find a free element in the linear probe.
|
|
if (~0u == first_free) {
|
|
return 0;
|
|
}
|
|
|
|
*out_index = first_free;
|
|
return 1;
|
|
}
|
|
|
|
int hashmap_rehash_iterator(void *const new_hash,
|
|
struct hashmap_element_s *const e) {
|
|
int temp = hashmap_put(HASHMAP_PTR_CAST(struct hashmap_s *, new_hash), e->key,
|
|
e->key_len, e->data);
|
|
|
|
if (0 < temp) {
|
|
return 1;
|
|
}
|
|
|
|
/* clear old value to avoid stale pointers */
|
|
return -1;
|
|
}
|
|
|
|
/*
|
|
* Doubles the size of the hashmap, and rehashes all the elements
|
|
*/
|
|
HASHMAP_ALWAYS_INLINE int hashmap_rehash_helper(struct hashmap_s *const m) {
|
|
struct hashmap_create_options_s options;
|
|
struct hashmap_s new_m;
|
|
int flag;
|
|
|
|
memset(&options, 0, sizeof(options));
|
|
options.initial_capacity = hashmap_capacity(m) * 2;
|
|
options.hasher = m->hasher;
|
|
|
|
if (0 == options.initial_capacity) {
|
|
return 1;
|
|
}
|
|
|
|
flag = hashmap_create_ex(options, &new_m);
|
|
|
|
if (0 != flag) {
|
|
return flag;
|
|
}
|
|
|
|
/* copy the old elements to the new table */
|
|
flag = hashmap_iterate_pairs(m, hashmap_rehash_iterator,
|
|
HASHMAP_PTR_CAST(void *, &new_m));
|
|
|
|
if (0 != flag) {
|
|
return flag;
|
|
}
|
|
|
|
hashmap_destroy(m);
|
|
|
|
/* put new hash into old hash structure by copying */
|
|
memcpy(m, &new_m, sizeof(struct hashmap_s));
|
|
|
|
return 0;
|
|
}
|
|
|
|
HASHMAP_ALWAYS_INLINE hashmap_uint32_t hashmap_clz(const hashmap_uint32_t x) {
|
|
#if defined(_MSC_VER)
|
|
unsigned long result;
|
|
_BitScanReverse(&result, x);
|
|
return 31u - HASHMAP_CAST(hashmap_uint32_t, result);
|
|
#elif defined(__TINYC__)
|
|
union {
|
|
double d;
|
|
hashmap_uint64_t u;
|
|
} u;
|
|
u.d = HASHMAP_CAST(double, x) + 0.5;
|
|
return 1054u - HASHMAP_CAST(hashmap_uint32_t, u.u >> 52);
|
|
#else
|
|
return HASHMAP_CAST(hashmap_uint32_t, __builtin_clz(x));
|
|
#endif
|
|
}
|
|
|
|
#if defined(_MSC_VER)
|
|
#pragma warning(pop)
|
|
#endif
|
|
|
|
#if defined(__clang__)
|
|
#pragma clang diagnostic pop
|
|
#endif
|
|
|
|
#endif
|