diff --git a/cart.bin b/cart.bin new file mode 100755 index 0000000..a7e9658 --- /dev/null +++ b/cart.bin Binary files differ diff --git a/cart.bin b/cart.bin new file mode 100755 index 0000000..a7e9658 --- /dev/null +++ b/cart.bin Binary files differ diff --git a/cart/test/game.bin b/cart/test/game.bin new file mode 100755 index 0000000..7b91a31 --- /dev/null +++ b/cart/test/game.bin Binary files differ diff --git a/cart.bin b/cart.bin new file mode 100755 index 0000000..a7e9658 --- /dev/null +++ b/cart.bin Binary files differ diff --git a/cart/test/game.bin b/cart/test/game.bin new file mode 100755 index 0000000..7b91a31 --- /dev/null +++ b/cart/test/game.bin Binary files differ diff --git a/cart/test/game.dll b/cart/test/game.dll index 1d6d40a..9b1ea05 100644 --- a/cart/test/game.dll +++ b/cart/test/game.dll Binary files differ diff --git a/cart.bin b/cart.bin new file mode 100755 index 0000000..a7e9658 --- /dev/null +++ b/cart.bin Binary files differ diff --git a/cart/test/game.bin b/cart/test/game.bin new file mode 100755 index 0000000..7b91a31 --- /dev/null +++ b/cart/test/game.bin Binary files differ diff --git a/cart/test/game.dll b/cart/test/game.dll index 1d6d40a..9b1ea05 100644 --- a/cart/test/game.dll +++ b/cart/test/game.dll Binary files differ diff --git a/cart/test/game.pdb b/cart/test/game.pdb new file mode 100755 index 0000000..21226ee --- /dev/null +++ b/cart/test/game.pdb Binary files differ diff --git a/cart.bin b/cart.bin new file mode 100755 index 0000000..a7e9658 --- /dev/null +++ b/cart.bin Binary files differ diff --git a/cart/test/game.bin b/cart/test/game.bin new file mode 100755 index 0000000..7b91a31 --- /dev/null +++ b/cart/test/game.bin Binary files differ diff --git a/cart/test/game.dll b/cart/test/game.dll index 1d6d40a..9b1ea05 100644 --- a/cart/test/game.dll +++ b/cart/test/game.dll Binary files differ diff --git a/cart/test/game.pdb b/cart/test/game.pdb new file mode 100755 index 0000000..21226ee --- /dev/null +++ b/cart/test/game.pdb Binary files differ diff --git a/cart/test/game.txt b/cart/test/game.txt new file mode 100644 index 0000000..676792b --- /dev/null +++ b/cart/test/game.txt @@ -0,0 +1 @@ +RPG \ No newline at end of file diff --git a/cart.bin b/cart.bin new file mode 100755 index 0000000..a7e9658 --- /dev/null +++ b/cart.bin Binary files differ diff --git a/cart/test/game.bin b/cart/test/game.bin new file mode 100755 index 0000000..7b91a31 --- /dev/null +++ b/cart/test/game.bin Binary files differ diff --git a/cart/test/game.dll b/cart/test/game.dll index 1d6d40a..9b1ea05 100644 --- a/cart/test/game.dll +++ b/cart/test/game.dll Binary files differ diff --git a/cart/test/game.pdb b/cart/test/game.pdb new file mode 100755 index 0000000..21226ee --- /dev/null +++ b/cart/test/game.pdb Binary files differ diff --git a/cart/test/game.txt b/cart/test/game.txt new file mode 100644 index 0000000..676792b --- /dev/null +++ b/cart/test/game.txt @@ -0,0 +1 @@ +RPG \ No newline at end of file diff --git a/cart/test/level14.txt b/cart/test/level14.txt index b285061..4a6a3d9 100644 --- a/cart/test/level14.txt +++ b/cart/test/level14.txt @@ -2,15 +2,15 @@ r roof st r3f roof3f st w wall s -d door s +d door -c1, c2 , c2 , c2 , c2 , c2 , c2 , c2 , c2 , c2 , c2 , c3 -c4, c5.1, c5.1, c5.1, c5.1, c5.1, c5.1, c5.1, c5.1, c5.1, c5.1, c6 -c4, c5.1, c5.1, c5.1, c5.1, c5.1, c5.1, c5.1, c5.1, c5.1, c5.1, c6 -c4, r1 , r2 , r3f , c5.1, r1 , r2 , r3f , c5.1, c5.1, c5.1, c6 -c4, r7 , r8 , r9 , c5.1, r4 , r5 , r6 , c5.1, c5.1, c5.1, c6 -c4, w1 , -d1 , w1 , c5.1, r7 , r8 , r9 , c5.1, c5.1, c5.1, c6 -c4, c5.1, c5.1, c5.1, c5.1, w1 , d1 , w1 , c5.1, c5.1, c5.1, c6 -c4, c5.1, c5.1, c5.1, c5.1, c5.1, c5.1, c5.1, c5.1, c5.1, c5.1, c6 -c4, c5.1, c5.1, c5.1, c5.1, c5.1, c5.1, c5.1, c5.1, c5.1, c5.1, c6 -c7, c8 , c8 , c8 , c8 , c8 , c8 , c8 , c8 , c8 , c8 , c9 +c1, c2 , c2 , c2 , c2 , c2 , c2 , c2 , c2 , c2 , c2 , c3 +c4, c5.1, c5.1 , c5.1, c5.1, c5.1, c5.1 , c5.1, c5.1, c5.1, c5.1, c6 +c4, c5.1, c5.1 , c5.1, c5.1, c5.1, c5.1 , c5.1, c5.1, c5.1, c5.1, c6 +c4, r1 , r2 , r3f , c5.1, r1 , r2 , r3f , c5.1, c5.1, c5.1, c6 +c4, r7 , r8 , r9 , c5.1, r4 , r5 , r6 , c5.1, c5.1, c5.1, c6 +c4, w1 , -d1:d1 , w1 , c5.1, r7 , r8 , r9 , c5.1, c5.1, c5.1, c6 +c4, c5.1, c5.1 , c5.1, c5.1, w1 , d1:d2, w1 , c5.1, c5.1, c5.1, c6 +c4, c5.1, c5.1 , c5.1, c5.1, c5.1, c5.1 , c5.1, c5.1, c5.1, c5.1, c6 +c4, c5.1, c5.1 , c5.1, c5.1, c5.1, c5.1 , c5.1, c5.1, c5.1, c5.1, c6 +c7, c8 , c8 , c8 , c8 , c8 , c8 , c8 , c8 , c8 , c8 , c9 diff --git a/cart.bin b/cart.bin new file mode 100755 index 0000000..a7e9658 --- /dev/null +++ b/cart.bin Binary files differ diff --git a/cart/test/game.bin b/cart/test/game.bin new file mode 100755 index 0000000..7b91a31 --- /dev/null +++ b/cart/test/game.bin Binary files differ diff --git a/cart/test/game.dll b/cart/test/game.dll index 1d6d40a..9b1ea05 100644 --- a/cart/test/game.dll +++ b/cart/test/game.dll Binary files differ diff --git a/cart/test/game.pdb b/cart/test/game.pdb new file mode 100755 index 0000000..21226ee --- /dev/null +++ b/cart/test/game.pdb Binary files differ diff --git a/cart/test/game.txt b/cart/test/game.txt new file mode 100644 index 0000000..676792b --- /dev/null +++ b/cart/test/game.txt @@ -0,0 +1 @@ +RPG \ No newline at end of file diff --git a/cart/test/level14.txt b/cart/test/level14.txt index b285061..4a6a3d9 100644 --- a/cart/test/level14.txt +++ b/cart/test/level14.txt @@ -2,15 +2,15 @@ r roof st r3f roof3f st w wall s -d door s +d door -c1, c2 , c2 , c2 , c2 , c2 , c2 , c2 , c2 , c2 , c2 , c3 -c4, c5.1, c5.1, c5.1, c5.1, c5.1, c5.1, c5.1, c5.1, c5.1, c5.1, c6 -c4, c5.1, c5.1, c5.1, c5.1, c5.1, c5.1, c5.1, c5.1, c5.1, c5.1, c6 -c4, r1 , r2 , r3f , c5.1, r1 , r2 , r3f , c5.1, c5.1, c5.1, c6 -c4, r7 , r8 , r9 , c5.1, r4 , r5 , r6 , c5.1, c5.1, c5.1, c6 -c4, w1 , -d1 , w1 , c5.1, r7 , r8 , r9 , c5.1, c5.1, c5.1, c6 -c4, c5.1, c5.1, c5.1, c5.1, w1 , d1 , w1 , c5.1, c5.1, c5.1, c6 -c4, c5.1, c5.1, c5.1, c5.1, c5.1, c5.1, c5.1, c5.1, c5.1, c5.1, c6 -c4, c5.1, c5.1, c5.1, c5.1, c5.1, c5.1, c5.1, c5.1, c5.1, c5.1, c6 -c7, c8 , c8 , c8 , c8 , c8 , c8 , c8 , c8 , c8 , c8 , c9 +c1, c2 , c2 , c2 , c2 , c2 , c2 , c2 , c2 , c2 , c2 , c3 +c4, c5.1, c5.1 , c5.1, c5.1, c5.1, c5.1 , c5.1, c5.1, c5.1, c5.1, c6 +c4, c5.1, c5.1 , c5.1, c5.1, c5.1, c5.1 , c5.1, c5.1, c5.1, c5.1, c6 +c4, r1 , r2 , r3f , c5.1, r1 , r2 , r3f , c5.1, c5.1, c5.1, c6 +c4, r7 , r8 , r9 , c5.1, r4 , r5 , r6 , c5.1, c5.1, c5.1, c6 +c4, w1 , -d1:d1 , w1 , c5.1, r7 , r8 , r9 , c5.1, c5.1, c5.1, c6 +c4, c5.1, c5.1 , c5.1, c5.1, w1 , d1:d2, w1 , c5.1, c5.1, c5.1, c6 +c4, c5.1, c5.1 , c5.1, c5.1, c5.1, c5.1 , c5.1, c5.1, c5.1, c5.1, c6 +c4, c5.1, c5.1 , c5.1, c5.1, c5.1, c5.1 , c5.1, c5.1, c5.1, c5.1, c6 +c7, c8 , c8 , c8 , c8 , c8 , c8 , c8 , c8 , c8 , c8 , c9 diff --git a/test/hashmap.h b/test/hashmap.h new file mode 100644 index 0000000..da88e81 --- /dev/null +++ b/test/hashmap.h @@ -0,0 +1,594 @@ +/* + 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 +*/ +#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 "client_api.h" + +//#include +//#include + +//#if (defined(_MSC_VER) && defined(__AVX__)) || \ +// (!defined(_MSC_VER) && defined(__SSE4_2__)) +//#define HASHMAP_SSE42 +//#endif + +//#if defined(HASHMAP_SSE42) +//#include +//#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) +#elif defined(__clang__) +#pragma clang diagnostic push +#pragma clang diagnostic ignored "-Wunused-function" +#endif + +#if defined(_MSC_VER) +#define HASHMAP_USED +#elif defined(__GNUC__) +#define HASHMAP_USED __attribute__((used)) +#else +#define HASHMAP_USED +#endif + +/* We need to keep keys and values. */ +struct hashmap_element_s { + const char *key; + unsigned key_len; + int in_use; + void *data; +}; + +/* A hashmap has some maximum size and current size, as well as the data to + * hold. */ +struct hashmap_s { + unsigned table_size; + unsigned size; + struct hashmap_element_s *data; +}; + +#define HASHMAP_MAX_CHAIN_LENGTH (8) + +#if defined(__cplusplus) +extern "C" { +#endif + +/// @brief Create a hashmap. +/// @param initial_size The initial size of the hashmap. Must be a power of two. +/// @param out_hashmap The storage for the created hashmap. +/// @return On success 0 is returned. +/// +/// Note that the initial size of the hashmap must be a power of two, and +/// creation of the hashmap will fail if this is not the case. +static int hashmap_create(const unsigned initial_size, + struct hashmap_s *const out_hashmap) HASHMAP_USED; + +/// @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. +static int hashmap_put(struct hashmap_s *const hashmap, const char *const key, + const unsigned len, void *const value) HASHMAP_USED; + +/// @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. +static void *hashmap_get(const struct hashmap_s *const hashmap, + const char *const key, + const unsigned len) HASHMAP_USED; + +/// @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. +static int hashmap_remove(struct hashmap_s *const hashmap, + const char *const key, + const unsigned len) HASHMAP_USED; + +/// @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. +static const char * +hashmap_remove_and_return_key(struct hashmap_s *const hashmap, + const char *const key, + const unsigned len) HASHMAP_USED; + +/// @brief Iterate over all the elements in a hashmap. +/// @param hashmap The hashmap to iterate over. +/// @param f 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. +static int hashmap_iterate(const struct hashmap_s *const hashmap, + int (*f)(void *const context, void *const value), + void *const context) HASHMAP_USED; + +/// @brief Iterate over all the elements in a hashmap. +/// @param hashmap The hashmap to iterate over. +/// @param f 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. +static int hashmap_iterate_pairs(struct hashmap_s *const hashmap, + int (*f)(void *const, + struct hashmap_element_s *const), + void *const context) HASHMAP_USED; + +/// @brief Get the size of the hashmap. +/// @param hashmap The hashmap to get the size of. +/// @return The size of the hashmap. +static unsigned +hashmap_num_entries(const struct hashmap_s *const hashmap) HASHMAP_USED; + +/// @brief Destroy the hashmap. +/// @param hashmap The hashmap to destroy. +static void hashmap_destroy(struct hashmap_s *const hashmap) HASHMAP_USED; + +static unsigned hashmap_crc32_helper(const char *const s, + const unsigned len) HASHMAP_USED; +static unsigned hashmap_hash_helper_int_helper(const struct hashmap_s *const m, + const char *const keystring, + const unsigned len) HASHMAP_USED; +static int hashmap_match_helper(const struct hashmap_element_s *const element, + const char *const key, + const unsigned len) HASHMAP_USED; +static int hashmap_hash_helper(const struct hashmap_s *const m, + const char *const key, const unsigned len, + unsigned *const out_index) HASHMAP_USED; +static int +hashmap_rehash_iterator(void *const new_hash, + struct hashmap_element_s *const e) HASHMAP_USED; +static int hashmap_rehash_helper(struct hashmap_s *const m) HASHMAP_USED; + +#if defined(__cplusplus) +} +#endif + +#if defined(__cplusplus) +#define HASHMAP_CAST(type, x) static_cast(x) +#define HASHMAP_PTR_CAST(type, x) reinterpret_cast(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 unsigned initial_size, + struct hashmap_s *const out_hashmap) { + out_hashmap->table_size = initial_size; + out_hashmap->size = 0; + + if (0 == initial_size || 0 != (initial_size & (initial_size - 1))) { + return 1; + } + + out_hashmap->data = + HASHMAP_CAST(struct hashmap_element_s *, + malloc(initial_size * sizeof(struct hashmap_element_s))); + if (!out_hashmap->data) { + return 1; + } + memset(out_hashmap->data, 0, initial_size * sizeof(struct hashmap_element_s)); + + return 0; +} + +int hashmap_put(struct hashmap_s *const m, const char *const key, + const unsigned len, void *const value) { + unsigned int index; + + /* 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 char *const key, + const unsigned len) { + unsigned int curr; + unsigned int i; + + /* Find data location */ + curr = hashmap_hash_helper_int_helper(m, key, len); + + /* Linear probing, if necessary */ + for (i = 0; i < HASHMAP_MAX_CHAIN_LENGTH; i++) { + if (m->data[curr].in_use) { + if (hashmap_match_helper(&m->data[curr], key, len)) { + return m->data[curr].data; + } + } + + curr = (curr + 1) % m->table_size; + } + + /* Not found */ + return HASHMAP_NULL; +} + +int hashmap_remove(struct hashmap_s *const m, const char *const key, + const unsigned len) { + unsigned int i; + unsigned int curr; + + /* Find key */ + curr = hashmap_hash_helper_int_helper(m, key, len); + + /* Linear probing, if necessary */ + for (i = 0; i < HASHMAP_MAX_CHAIN_LENGTH; i++) { + if (m->data[curr].in_use) { + if (hashmap_match_helper(&m->data[curr], key, len)) { + /* Blank out the fields including in_use */ + memset(&m->data[curr], 0, sizeof(struct hashmap_element_s)); + + /* Reduce the size */ + m->size--; + + return 0; + } + } + + curr = (curr + 1) % m->table_size; + } + + return 1; +} + +const char *hashmap_remove_and_return_key(struct hashmap_s *const m, + const char *const key, + const unsigned len) { + unsigned int i; + unsigned int curr; + + /* Find key */ + curr = hashmap_hash_helper_int_helper(m, key, len); + + /* Linear probing, if necessary */ + for (i = 0; i < HASHMAP_MAX_CHAIN_LENGTH; i++) { + if (m->data[curr].in_use) { + if (hashmap_match_helper(&m->data[curr], key, len)) { + const char *const stored_key = m->data[curr].key; + + /* Blank out the fields */ + m->data[curr].in_use = 0; + m->data[curr].data = HASHMAP_NULL; + m->data[curr].key = HASHMAP_NULL; + + /* Reduce the size */ + m->size--; + + return stored_key; + } + } + curr = (curr + 1) % m->table_size; + } + + return HASHMAP_NULL; +} + +int hashmap_iterate(const struct hashmap_s *const m, + int (*f)(void *const, void *const), void *const context) { + unsigned int i; + + /* Linear probing */ + for (i = 0; i < m->table_size; 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 hashmap, + int (*f)(void *const, + struct hashmap_element_s *const), + void *const context) { + unsigned int i; + struct hashmap_element_s *p; + int r; + + /* Linear probing */ + for (i = 0; i < hashmap->table_size; i++) { + p = &hashmap->data[i]; + if (p->in_use) { + r = f(context, p); + switch (r) { + case -1: /* remove item */ + memset(p, 0, sizeof(struct hashmap_element_s)); + hashmap->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)); +} + +unsigned hashmap_num_entries(const struct hashmap_s *const m) { + return m->size; +} + +unsigned hashmap_crc32_helper(const char *const s, const unsigned len) { + unsigned i; + unsigned crc32val = 0; + +#if defined(HASHMAP_SSE42) + for (i = 0; i < len; i++) { + crc32val = _mm_crc32_u8(crc32val, HASHMAP_CAST(unsigned char, s[i])); + } + + return crc32val; +#else + // Using polynomial 0x11EDC6F41 to match SSE 4.2's crc function. + static const unsigned 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 = 0; i < len; i++) { + crc32val = crc32_tab[(HASHMAP_CAST(unsigned char, crc32val) ^ + HASHMAP_CAST(unsigned char, s[i]))] ^ + (crc32val >> 8); + } + return crc32val; +#endif +} + +unsigned hashmap_hash_helper_int_helper(const struct hashmap_s *const m, + const char *const keystring, + const unsigned len) { + unsigned key = hashmap_crc32_helper(keystring, len); + + /* Robert Jenkins' 32 bit Mix Function */ + key += (key << 12); + key ^= (key >> 22); + key += (key << 4); + key ^= (key >> 9); + key += (key << 10); + key ^= (key >> 2); + key += (key << 7); + key ^= (key >> 12); + + /* Knuth's Multiplicative Method */ + key = (key >> 3) * 2654435761; + + return key % m->table_size; +} + +int hashmap_match_helper(const struct hashmap_element_s *const element, + const char *const key, const unsigned len) { + return (element->key_len == len) && (0 == memcmp(element->key, key, len)); +} + +int hashmap_hash_helper(const struct hashmap_s *const m, const char *const key, + const unsigned len, unsigned *const out_index) { + unsigned int start, curr; + unsigned int i; + int total_in_use; + + /* If full, return immediately */ + if (m->size >= m->table_size) { + return 0; + } + + /* Find the best index */ + curr = start = hashmap_hash_helper_int_helper(m, key, len); + + /* First linear probe to check if we've already insert the element */ + total_in_use = 0; + + for (i = 0; i < HASHMAP_MAX_CHAIN_LENGTH; i++) { + const int in_use = m->data[curr].in_use; + + total_in_use += in_use; + + if (in_use && hashmap_match_helper(&m->data[curr], key, len)) { + *out_index = curr; + return 1; + } + + curr = (curr + 1) % m->table_size; + } + + curr = start; + + /* Second linear probe to actually insert our element (only if there was at + * least one empty entry) */ + if (HASHMAP_MAX_CHAIN_LENGTH > total_in_use) { + for (i = 0; i < HASHMAP_MAX_CHAIN_LENGTH; i++) { + if (!m->data[curr].in_use) { + *out_index = curr; + return 1; + } + + curr = (curr + 1) % m->table_size; + } + } + + return 0; +} + +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 + */ +int hashmap_rehash_helper(struct hashmap_s *const m) { + /* If this multiplication overflows hashmap_create will fail. */ + unsigned new_size = 2 * m->table_size; + + struct hashmap_s new_hash; + + int flag = hashmap_create(new_size, &new_hash); + + 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_hash)); + + if (0 != flag) { + return flag; + } + + hashmap_destroy(m); + /* put new hash into old hash structure by copying */ + memcpy(m, &new_hash, sizeof(struct hashmap_s)); + + return 0; +} + +#if defined(_MSC_VER) +#pragma warning(pop) +#elif defined(__clang__) +#pragma clang diagnostic pop +#endif + +#endif diff --git a/cart.bin b/cart.bin new file mode 100755 index 0000000..a7e9658 --- /dev/null +++ b/cart.bin Binary files differ diff --git a/cart/test/game.bin b/cart/test/game.bin new file mode 100755 index 0000000..7b91a31 --- /dev/null +++ b/cart/test/game.bin Binary files differ diff --git a/cart/test/game.dll b/cart/test/game.dll index 1d6d40a..9b1ea05 100644 --- a/cart/test/game.dll +++ b/cart/test/game.dll Binary files differ diff --git a/cart/test/game.pdb b/cart/test/game.pdb new file mode 100755 index 0000000..21226ee --- /dev/null +++ b/cart/test/game.pdb Binary files differ diff --git a/cart/test/game.txt b/cart/test/game.txt new file mode 100644 index 0000000..676792b --- /dev/null +++ b/cart/test/game.txt @@ -0,0 +1 @@ +RPG \ No newline at end of file diff --git a/cart/test/level14.txt b/cart/test/level14.txt index b285061..4a6a3d9 100644 --- a/cart/test/level14.txt +++ b/cart/test/level14.txt @@ -2,15 +2,15 @@ r roof st r3f roof3f st w wall s -d door s +d door -c1, c2 , c2 , c2 , c2 , c2 , c2 , c2 , c2 , c2 , c2 , c3 -c4, c5.1, c5.1, c5.1, c5.1, c5.1, c5.1, c5.1, c5.1, c5.1, c5.1, c6 -c4, c5.1, c5.1, c5.1, c5.1, c5.1, c5.1, c5.1, c5.1, c5.1, c5.1, c6 -c4, r1 , r2 , r3f , c5.1, r1 , r2 , r3f , c5.1, c5.1, c5.1, c6 -c4, r7 , r8 , r9 , c5.1, r4 , r5 , r6 , c5.1, c5.1, c5.1, c6 -c4, w1 , -d1 , w1 , c5.1, r7 , r8 , r9 , c5.1, c5.1, c5.1, c6 -c4, c5.1, c5.1, c5.1, c5.1, w1 , d1 , w1 , c5.1, c5.1, c5.1, c6 -c4, c5.1, c5.1, c5.1, c5.1, c5.1, c5.1, c5.1, c5.1, c5.1, c5.1, c6 -c4, c5.1, c5.1, c5.1, c5.1, c5.1, c5.1, c5.1, c5.1, c5.1, c5.1, c6 -c7, c8 , c8 , c8 , c8 , c8 , c8 , c8 , c8 , c8 , c8 , c9 +c1, c2 , c2 , c2 , c2 , c2 , c2 , c2 , c2 , c2 , c2 , c3 +c4, c5.1, c5.1 , c5.1, c5.1, c5.1, c5.1 , c5.1, c5.1, c5.1, c5.1, c6 +c4, c5.1, c5.1 , c5.1, c5.1, c5.1, c5.1 , c5.1, c5.1, c5.1, c5.1, c6 +c4, r1 , r2 , r3f , c5.1, r1 , r2 , r3f , c5.1, c5.1, c5.1, c6 +c4, r7 , r8 , r9 , c5.1, r4 , r5 , r6 , c5.1, c5.1, c5.1, c6 +c4, w1 , -d1:d1 , w1 , c5.1, r7 , r8 , r9 , c5.1, c5.1, c5.1, c6 +c4, c5.1, c5.1 , c5.1, c5.1, w1 , d1:d2, w1 , c5.1, c5.1, c5.1, c6 +c4, c5.1, c5.1 , c5.1, c5.1, c5.1, c5.1 , c5.1, c5.1, c5.1, c5.1, c6 +c4, c5.1, c5.1 , c5.1, c5.1, c5.1, c5.1 , c5.1, c5.1, c5.1, c5.1, c6 +c7, c8 , c8 , c8 , c8 , c8 , c8 , c8 , c8 , c8 , c8 , c9 diff --git a/test/hashmap.h b/test/hashmap.h new file mode 100644 index 0000000..da88e81 --- /dev/null +++ b/test/hashmap.h @@ -0,0 +1,594 @@ +/* + 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 +*/ +#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 "client_api.h" + +//#include +//#include + +//#if (defined(_MSC_VER) && defined(__AVX__)) || \ +// (!defined(_MSC_VER) && defined(__SSE4_2__)) +//#define HASHMAP_SSE42 +//#endif + +//#if defined(HASHMAP_SSE42) +//#include +//#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) +#elif defined(__clang__) +#pragma clang diagnostic push +#pragma clang diagnostic ignored "-Wunused-function" +#endif + +#if defined(_MSC_VER) +#define HASHMAP_USED +#elif defined(__GNUC__) +#define HASHMAP_USED __attribute__((used)) +#else +#define HASHMAP_USED +#endif + +/* We need to keep keys and values. */ +struct hashmap_element_s { + const char *key; + unsigned key_len; + int in_use; + void *data; +}; + +/* A hashmap has some maximum size and current size, as well as the data to + * hold. */ +struct hashmap_s { + unsigned table_size; + unsigned size; + struct hashmap_element_s *data; +}; + +#define HASHMAP_MAX_CHAIN_LENGTH (8) + +#if defined(__cplusplus) +extern "C" { +#endif + +/// @brief Create a hashmap. +/// @param initial_size The initial size of the hashmap. Must be a power of two. +/// @param out_hashmap The storage for the created hashmap. +/// @return On success 0 is returned. +/// +/// Note that the initial size of the hashmap must be a power of two, and +/// creation of the hashmap will fail if this is not the case. +static int hashmap_create(const unsigned initial_size, + struct hashmap_s *const out_hashmap) HASHMAP_USED; + +/// @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. +static int hashmap_put(struct hashmap_s *const hashmap, const char *const key, + const unsigned len, void *const value) HASHMAP_USED; + +/// @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. +static void *hashmap_get(const struct hashmap_s *const hashmap, + const char *const key, + const unsigned len) HASHMAP_USED; + +/// @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. +static int hashmap_remove(struct hashmap_s *const hashmap, + const char *const key, + const unsigned len) HASHMAP_USED; + +/// @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. +static const char * +hashmap_remove_and_return_key(struct hashmap_s *const hashmap, + const char *const key, + const unsigned len) HASHMAP_USED; + +/// @brief Iterate over all the elements in a hashmap. +/// @param hashmap The hashmap to iterate over. +/// @param f 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. +static int hashmap_iterate(const struct hashmap_s *const hashmap, + int (*f)(void *const context, void *const value), + void *const context) HASHMAP_USED; + +/// @brief Iterate over all the elements in a hashmap. +/// @param hashmap The hashmap to iterate over. +/// @param f 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. +static int hashmap_iterate_pairs(struct hashmap_s *const hashmap, + int (*f)(void *const, + struct hashmap_element_s *const), + void *const context) HASHMAP_USED; + +/// @brief Get the size of the hashmap. +/// @param hashmap The hashmap to get the size of. +/// @return The size of the hashmap. +static unsigned +hashmap_num_entries(const struct hashmap_s *const hashmap) HASHMAP_USED; + +/// @brief Destroy the hashmap. +/// @param hashmap The hashmap to destroy. +static void hashmap_destroy(struct hashmap_s *const hashmap) HASHMAP_USED; + +static unsigned hashmap_crc32_helper(const char *const s, + const unsigned len) HASHMAP_USED; +static unsigned hashmap_hash_helper_int_helper(const struct hashmap_s *const m, + const char *const keystring, + const unsigned len) HASHMAP_USED; +static int hashmap_match_helper(const struct hashmap_element_s *const element, + const char *const key, + const unsigned len) HASHMAP_USED; +static int hashmap_hash_helper(const struct hashmap_s *const m, + const char *const key, const unsigned len, + unsigned *const out_index) HASHMAP_USED; +static int +hashmap_rehash_iterator(void *const new_hash, + struct hashmap_element_s *const e) HASHMAP_USED; +static int hashmap_rehash_helper(struct hashmap_s *const m) HASHMAP_USED; + +#if defined(__cplusplus) +} +#endif + +#if defined(__cplusplus) +#define HASHMAP_CAST(type, x) static_cast(x) +#define HASHMAP_PTR_CAST(type, x) reinterpret_cast(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 unsigned initial_size, + struct hashmap_s *const out_hashmap) { + out_hashmap->table_size = initial_size; + out_hashmap->size = 0; + + if (0 == initial_size || 0 != (initial_size & (initial_size - 1))) { + return 1; + } + + out_hashmap->data = + HASHMAP_CAST(struct hashmap_element_s *, + malloc(initial_size * sizeof(struct hashmap_element_s))); + if (!out_hashmap->data) { + return 1; + } + memset(out_hashmap->data, 0, initial_size * sizeof(struct hashmap_element_s)); + + return 0; +} + +int hashmap_put(struct hashmap_s *const m, const char *const key, + const unsigned len, void *const value) { + unsigned int index; + + /* 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 char *const key, + const unsigned len) { + unsigned int curr; + unsigned int i; + + /* Find data location */ + curr = hashmap_hash_helper_int_helper(m, key, len); + + /* Linear probing, if necessary */ + for (i = 0; i < HASHMAP_MAX_CHAIN_LENGTH; i++) { + if (m->data[curr].in_use) { + if (hashmap_match_helper(&m->data[curr], key, len)) { + return m->data[curr].data; + } + } + + curr = (curr + 1) % m->table_size; + } + + /* Not found */ + return HASHMAP_NULL; +} + +int hashmap_remove(struct hashmap_s *const m, const char *const key, + const unsigned len) { + unsigned int i; + unsigned int curr; + + /* Find key */ + curr = hashmap_hash_helper_int_helper(m, key, len); + + /* Linear probing, if necessary */ + for (i = 0; i < HASHMAP_MAX_CHAIN_LENGTH; i++) { + if (m->data[curr].in_use) { + if (hashmap_match_helper(&m->data[curr], key, len)) { + /* Blank out the fields including in_use */ + memset(&m->data[curr], 0, sizeof(struct hashmap_element_s)); + + /* Reduce the size */ + m->size--; + + return 0; + } + } + + curr = (curr + 1) % m->table_size; + } + + return 1; +} + +const char *hashmap_remove_and_return_key(struct hashmap_s *const m, + const char *const key, + const unsigned len) { + unsigned int i; + unsigned int curr; + + /* Find key */ + curr = hashmap_hash_helper_int_helper(m, key, len); + + /* Linear probing, if necessary */ + for (i = 0; i < HASHMAP_MAX_CHAIN_LENGTH; i++) { + if (m->data[curr].in_use) { + if (hashmap_match_helper(&m->data[curr], key, len)) { + const char *const stored_key = m->data[curr].key; + + /* Blank out the fields */ + m->data[curr].in_use = 0; + m->data[curr].data = HASHMAP_NULL; + m->data[curr].key = HASHMAP_NULL; + + /* Reduce the size */ + m->size--; + + return stored_key; + } + } + curr = (curr + 1) % m->table_size; + } + + return HASHMAP_NULL; +} + +int hashmap_iterate(const struct hashmap_s *const m, + int (*f)(void *const, void *const), void *const context) { + unsigned int i; + + /* Linear probing */ + for (i = 0; i < m->table_size; 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 hashmap, + int (*f)(void *const, + struct hashmap_element_s *const), + void *const context) { + unsigned int i; + struct hashmap_element_s *p; + int r; + + /* Linear probing */ + for (i = 0; i < hashmap->table_size; i++) { + p = &hashmap->data[i]; + if (p->in_use) { + r = f(context, p); + switch (r) { + case -1: /* remove item */ + memset(p, 0, sizeof(struct hashmap_element_s)); + hashmap->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)); +} + +unsigned hashmap_num_entries(const struct hashmap_s *const m) { + return m->size; +} + +unsigned hashmap_crc32_helper(const char *const s, const unsigned len) { + unsigned i; + unsigned crc32val = 0; + +#if defined(HASHMAP_SSE42) + for (i = 0; i < len; i++) { + crc32val = _mm_crc32_u8(crc32val, HASHMAP_CAST(unsigned char, s[i])); + } + + return crc32val; +#else + // Using polynomial 0x11EDC6F41 to match SSE 4.2's crc function. + static const unsigned 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 = 0; i < len; i++) { + crc32val = crc32_tab[(HASHMAP_CAST(unsigned char, crc32val) ^ + HASHMAP_CAST(unsigned char, s[i]))] ^ + (crc32val >> 8); + } + return crc32val; +#endif +} + +unsigned hashmap_hash_helper_int_helper(const struct hashmap_s *const m, + const char *const keystring, + const unsigned len) { + unsigned key = hashmap_crc32_helper(keystring, len); + + /* Robert Jenkins' 32 bit Mix Function */ + key += (key << 12); + key ^= (key >> 22); + key += (key << 4); + key ^= (key >> 9); + key += (key << 10); + key ^= (key >> 2); + key += (key << 7); + key ^= (key >> 12); + + /* Knuth's Multiplicative Method */ + key = (key >> 3) * 2654435761; + + return key % m->table_size; +} + +int hashmap_match_helper(const struct hashmap_element_s *const element, + const char *const key, const unsigned len) { + return (element->key_len == len) && (0 == memcmp(element->key, key, len)); +} + +int hashmap_hash_helper(const struct hashmap_s *const m, const char *const key, + const unsigned len, unsigned *const out_index) { + unsigned int start, curr; + unsigned int i; + int total_in_use; + + /* If full, return immediately */ + if (m->size >= m->table_size) { + return 0; + } + + /* Find the best index */ + curr = start = hashmap_hash_helper_int_helper(m, key, len); + + /* First linear probe to check if we've already insert the element */ + total_in_use = 0; + + for (i = 0; i < HASHMAP_MAX_CHAIN_LENGTH; i++) { + const int in_use = m->data[curr].in_use; + + total_in_use += in_use; + + if (in_use && hashmap_match_helper(&m->data[curr], key, len)) { + *out_index = curr; + return 1; + } + + curr = (curr + 1) % m->table_size; + } + + curr = start; + + /* Second linear probe to actually insert our element (only if there was at + * least one empty entry) */ + if (HASHMAP_MAX_CHAIN_LENGTH > total_in_use) { + for (i = 0; i < HASHMAP_MAX_CHAIN_LENGTH; i++) { + if (!m->data[curr].in_use) { + *out_index = curr; + return 1; + } + + curr = (curr + 1) % m->table_size; + } + } + + return 0; +} + +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 + */ +int hashmap_rehash_helper(struct hashmap_s *const m) { + /* If this multiplication overflows hashmap_create will fail. */ + unsigned new_size = 2 * m->table_size; + + struct hashmap_s new_hash; + + int flag = hashmap_create(new_size, &new_hash); + + 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_hash)); + + if (0 != flag) { + return flag; + } + + hashmap_destroy(m); + /* put new hash into old hash structure by copying */ + memcpy(m, &new_hash, sizeof(struct hashmap_s)); + + return 0; +} + +#if defined(_MSC_VER) +#pragma warning(pop) +#elif defined(__clang__) +#pragma clang diagnostic pop +#endif + +#endif diff --git a/test/test.c b/test/test.c index e9aa1bb..4b982c9 100644 --- a/test/test.c +++ b/test/test.c @@ -1,5 +1,6 @@ #include #include "parse.h" +#include "hashmap.h" #define GRID 14 #define COLS 12 @@ -37,10 +38,20 @@ { uint8_t tile; grid_flags flags; + char* tag; } grid_t; grid_t grid[COLS][ROWS]; +void grid_pos(grid_t* g, int* x, int* y) +{ + int index = (int)(g - &grid[0][0]); + *x = index / ROWS; + *y = index - (*x * ROWS); +} + +struct hashmap_s tile_tags; + #define OUTLINE 2 bool load_level(char* fname); @@ -48,6 +59,8 @@ int setup(int a) { + hashmap_create(32, &tile_tags); + player = f_bitmap("/player.pbm"); player_out = d_expand_bitmap(player, OUTLINE, true, false); @@ -59,6 +72,8 @@ return 0; } +int remove_all_hashmap(void* const ctx, struct hashmap_element_s* const value) { return -1; } + char* last_level = NULL; void unload_bg() { @@ -73,6 +88,8 @@ free(last_level); last_level = NULL; } + + hashmap_iterate_pairs(&tile_tags, remove_all_hashmap, NULL); } #define SOLID 1 @@ -125,6 +142,8 @@ return false; } + if (!tile_def[2]) tile_def[2] = "NULL"; + printf("Parsed tile %d %s %s %s\n", not_null, tile_def[0], tile_def[1], tile_def[2]); bg_flags flags = 0; @@ -229,6 +248,7 @@ return false; } char* prob = NULL; + char* tag = NULL; grid_flags flags = 0; for (int i = 0; i < 2; i++) { @@ -244,13 +264,29 @@ } } - size_t l = strlen(parse_word); + char* last_word = parse_word; + + size_t l = strlen(last_word); for (int i = 0; i < l; i++) { - if (parse_word[i] == '.') + if (last_word[i] == '.') { - parse_word[i] = 0; - prob = parse_word + (i + 1); + last_word[i] = 0; + prob = last_word + (i + 1); + last_word = prob; + l = strlen(prob); + break; + } + } + + for (int i = 0; i < l; i++) + { + if (last_word[i] == ':') + { + last_word[i] = 0; + tag = last_word + (i + 1); + last_word = tag; + l = strlen(tag); break; } } @@ -267,7 +303,8 @@ if (random(1, 10) > p) continue; } //printf("Tile %d on %d,%d\n", i, x, y); - grid_t g = { i + 1, flags }; + grid_t g = { i + 1, flags, tag }; + if (tag) hashmap_put(&tile_tags, tag, strlen(tag), &grid[x][y]); grid[x][y] = g; } } @@ -337,6 +374,31 @@ return true; } +#define ENTER_GRID_PCT 0.2f + +void entered_tile(int tx, int ty) +{ + grid_t g = grid[tx][ty]; + if (g.tag) + { + void* find = NULL; + if (strcmp(g.tag, "d1") == 0) + { + if ((find = hashmap_get(&tile_tags, "d2", 2)) != NULL) + { + int gx, gy; + grid_pos((grid_t*)find, &gx, &gy); + x = gx * GRID; + y = gy * GRID; + } + } + } +} +void exited_tile(int x, int y) +{ + grid_t g = grid[x][y]; +} + int loop(int ms) { @@ -422,6 +484,18 @@ int ox_i = (int)roundf(ox); int oy_i = (int)roundf(oy); + float o_grid_x; + float o_grid_y; + + float o_ingrid_x = modff((x + GRID * 0.5f) / GRID, &o_grid_x) - 0.5f; + float o_ingrid_y = modff((y + GRID * 0.5f) / GRID, &o_grid_y) - 0.5f; + if (fabsf(o_ingrid_x) > ENTER_GRID_PCT || fabsf(o_ingrid_y) > ENTER_GRID_PCT) + { + o_grid_x = -1; + o_grid_y = -1; + } + + float t = ms / 1000.0f; if (button_down(DPAD_RIGHT)) x += t * speed; if (button_down(DPAD_LEFT)) x -= t * speed; @@ -489,6 +563,31 @@ if (move_debug) printf("reached (%d,%d) on target of (%d,%d), x,y=(%f,%f)\n", ox_i, oy_i, x_i, y_i, x, y); if (move_debug) printf("\n====================\n\n"); + + float grid_x; + float grid_y; + + float ingrid_x = modff((x + GRID * 0.5f) / GRID, &grid_x) - 0.5f; + float ingrid_y = modff((y + GRID * 0.5f) / GRID, &grid_y) - 0.5f; + if (fabsf(ingrid_x) > ENTER_GRID_PCT || fabsf(ingrid_y) > ENTER_GRID_PCT) + { + grid_x = -1; + grid_y = -1; + } + + if (grid_x != o_grid_x || grid_y != o_grid_y) + { + if (o_grid_x != -1) + { + exited_tile((int)o_grid_x, (int)o_grid_y); + //printf("Exited: %f %f\n", o_grid_x, o_grid_y); + } + if (grid_x != -1) + { + entered_tile((int)grid_x, (int)grid_y); + //printf("Entered: %f %f\n", grid_x, grid_y); + } + } } return 0;