diff options
| -rw-r--r-- | source/blender/blenlib/BLI_edgehash.h | 80 | ||||
| -rw-r--r-- | source/blender/blenlib/intern/edgehash.c | 860 | ||||
| -rw-r--r-- | tests/gtests/blenlib/BLI_edgehash_test.cc | 405 | ||||
| -rw-r--r-- | tests/gtests/blenlib/CMakeLists.txt | 1 |
4 files changed, 800 insertions, 546 deletions
diff --git a/source/blender/blenlib/BLI_edgehash.h b/source/blender/blenlib/BLI_edgehash.h index 83b519fc750..38f750dfe04 100644 --- a/source/blender/blenlib/BLI_edgehash.h +++ b/source/blender/blenlib/BLI_edgehash.h @@ -33,10 +33,19 @@ struct EdgeHash; typedef struct EdgeHash EdgeHash; +struct _EdgeHash_Edge { + uint v_low, v_high; +}; + +struct _EdgeHash_Entry { + struct _EdgeHash_Edge edge; + void *value; +}; + typedef struct EdgeHashIterator { - EdgeHash *eh; - struct EdgeEntry *curEntry; - unsigned int curBucket; + struct _EdgeHash_Entry *entries; + uint length; + uint index; } EdgeHashIterator; typedef void (*EdgeHashFreeFP)(void *key); @@ -49,6 +58,7 @@ EdgeHash *BLI_edgehash_new_ex(const char *info, const unsigned int nentries_reserve); EdgeHash *BLI_edgehash_new(const char *info) ATTR_MALLOC ATTR_WARN_UNUSED_RESULT; void BLI_edgehash_free(EdgeHash *eh, EdgeHashFreeFP valfreefp); +void BLI_edgehash_print(EdgeHash *eh); void BLI_edgehash_insert(EdgeHash *eh, unsigned int v0, unsigned int v1, void *val); bool BLI_edgehash_reinsert(EdgeHash *eh, unsigned int v0, unsigned int v1, void *val); void *BLI_edgehash_lookup(EdgeHash *eh, unsigned int v0, unsigned int v1) ATTR_WARN_UNUSED_RESULT; @@ -63,33 +73,24 @@ int BLI_edgehash_len(EdgeHash *eh) ATTR_WARN_UNUSED_RESULT; void BLI_edgehash_clear_ex(EdgeHash *eh, EdgeHashFreeFP valfreefp, const unsigned int nentries_reserve); void BLI_edgehash_clear(EdgeHash *eh, EdgeHashFreeFP valfreefp); -void BLI_edgehash_flag_set(EdgeHash *eh, unsigned int flag); -void BLI_edgehash_flag_clear(EdgeHash *eh, unsigned int flag); EdgeHashIterator *BLI_edgehashIterator_new(EdgeHash *eh) ATTR_MALLOC ATTR_WARN_UNUSED_RESULT; void BLI_edgehashIterator_init(EdgeHashIterator *ehi, EdgeHash *eh); void BLI_edgehashIterator_free(EdgeHashIterator *ehi); -void BLI_edgehashIterator_step(EdgeHashIterator *ehi); -BLI_INLINE bool BLI_edgehashIterator_isDone(EdgeHashIterator *ehi) ATTR_WARN_UNUSED_RESULT; -BLI_INLINE void BLI_edgehashIterator_getKey(EdgeHashIterator *ehi, unsigned int *r_v0, unsigned int *r_v1); -BLI_INLINE void *BLI_edgehashIterator_getValue(EdgeHashIterator *ehi) ATTR_WARN_UNUSED_RESULT; -BLI_INLINE void **BLI_edgehashIterator_getValue_p(EdgeHashIterator *ehi) ATTR_WARN_UNUSED_RESULT; -BLI_INLINE void BLI_edgehashIterator_setValue(EdgeHashIterator *ehi, void *val); - -struct _eh_Entry { void *next; unsigned int v0, v1; void *val; }; +BLI_INLINE void BLI_edgehashIterator_step(EdgeHashIterator *ehi) +{ ehi->index++; } +BLI_INLINE bool BLI_edgehashIterator_isDone(EdgeHashIterator *ehi) +{ return ehi->index >= ehi->length; } BLI_INLINE void BLI_edgehashIterator_getKey(EdgeHashIterator *ehi, unsigned int *r_v0, unsigned int *r_v1) -{ *r_v0 = ((struct _eh_Entry *)ehi->curEntry)->v0; *r_v1 = ((struct _eh_Entry *)ehi->curEntry)->v1; } -BLI_INLINE void *BLI_edgehashIterator_getValue(EdgeHashIterator *ehi) { return ((struct _eh_Entry *)ehi->curEntry)->val; } -BLI_INLINE void **BLI_edgehashIterator_getValue_p(EdgeHashIterator *ehi) { return &((struct _eh_Entry *)ehi->curEntry)->val; } -BLI_INLINE void BLI_edgehashIterator_setValue(EdgeHashIterator *ehi, void *val) { ((struct _eh_Entry *)ehi->curEntry)->val = val; } -BLI_INLINE bool BLI_edgehashIterator_isDone(EdgeHashIterator *ehi) { return (((struct _eh_Entry *)ehi->curEntry) == NULL); } -/* disallow further access */ -#ifdef __GNUC__ -# pragma GCC poison _eh_Entry -#else -# define _eh_Entry void -#endif +{ struct _EdgeHash_Edge edge = ehi->entries[ehi->index].edge; *r_v0 = edge.v_low; *r_v1 = edge.v_high; } +BLI_INLINE void *BLI_edgehashIterator_getValue(EdgeHashIterator *ehi) +{ return ehi->entries[ehi->index].value; } +BLI_INLINE void **BLI_edgehashIterator_getValue_p(EdgeHashIterator *ehi) +{ return &ehi->entries[ehi->index].value; } +BLI_INLINE void BLI_edgehashIterator_setValue(EdgeHashIterator *ehi, void *val) +{ ehi->entries[ehi->index].value = val; } + #define BLI_EDGEHASH_SIZE_GUESS_FROM_LOOPS(totloop) ((totloop) / 2) #define BLI_EDGEHASH_SIZE_GUESS_FROM_POLYS(totpoly) ((totpoly) * 2) @@ -97,9 +98,13 @@ BLI_INLINE bool BLI_edgehashIterator_isDone(EdgeHashIterator *ehi) { return (( /* *** EdgeSet *** */ struct EdgeSet; -struct EdgeSetIterator; typedef struct EdgeSet EdgeSet; -typedef struct EdgeSetIterator EdgeSetIterator; + +typedef struct EdgeSetIterator { + struct _EdgeHash_Edge *edges; + uint length; + uint index; +} EdgeSetIterator; EdgeSet *BLI_edgeset_new_ex(const char *info, const unsigned int nentries_reserve) ATTR_MALLOC ATTR_WARN_UNUSED_RESULT; @@ -107,21 +112,18 @@ EdgeSet *BLI_edgeset_new(const char *info) ATTR_MALLOC ATTR_WARN_UNUSED_RESULT; int BLI_edgeset_len(EdgeSet *es) ATTR_WARN_UNUSED_RESULT; bool BLI_edgeset_add(EdgeSet *es, unsigned int v0, unsigned int v1); void BLI_edgeset_insert(EdgeSet *es, unsigned int v0, unsigned int v1); -bool BLI_edgeset_haskey(EdgeSet *eh, unsigned int v0, unsigned int v1) ATTR_WARN_UNUSED_RESULT; +bool BLI_edgeset_haskey(EdgeSet *es, unsigned int v0, unsigned int v1) ATTR_WARN_UNUSED_RESULT; void BLI_edgeset_free(EdgeSet *es); -void BLI_edgeset_flag_set(EdgeSet *es, unsigned int flag); -void BLI_edgeset_flag_clear(EdgeSet *es, unsigned int flag); /* rely on inline api for now */ -BLI_INLINE EdgeSetIterator *BLI_edgesetIterator_new(EdgeSet *gs) { return (EdgeSetIterator *)BLI_edgehashIterator_new((EdgeHash *)gs); } -BLI_INLINE void BLI_edgesetIterator_free(EdgeSetIterator *esi) { BLI_edgehashIterator_free((EdgeHashIterator *)esi); } -BLI_INLINE void BLI_edgesetIterator_getKey(EdgeSetIterator *esi, unsigned int *r_v0, unsigned int *r_v1) { BLI_edgehashIterator_getKey((EdgeHashIterator *)esi, r_v0, r_v1); } -BLI_INLINE void BLI_edgesetIterator_step(EdgeSetIterator *esi) { BLI_edgehashIterator_step((EdgeHashIterator *)esi); } -BLI_INLINE bool BLI_edgesetIterator_isDone(EdgeSetIterator *esi) { return BLI_edgehashIterator_isDone((EdgeHashIterator *)esi); } - -#ifdef DEBUG -double BLI_edgehash_calc_quality(EdgeHash *eh); -double BLI_edgeset_calc_quality(EdgeSet *es); -#endif +EdgeSetIterator *BLI_edgesetIterator_new(EdgeSet *gs); +void BLI_edgesetIterator_free(EdgeSetIterator *esi); + +BLI_INLINE void BLI_edgesetIterator_getKey(EdgeSetIterator *esi, unsigned int *r_v0, unsigned int *r_v1) +{ struct _EdgeHash_Edge edge = esi->edges[esi->index]; *r_v0 = edge.v_low; *r_v1 = edge.v_high; } +BLI_INLINE void BLI_edgesetIterator_step(EdgeSetIterator *esi) +{ esi->index++; } +BLI_INLINE bool BLI_edgesetIterator_isDone(EdgeSetIterator *esi) +{ return esi->index >= esi->length; } #endif /* __BLI_EDGEHASH_H__ */ diff --git a/source/blender/blenlib/intern/edgehash.c b/source/blender/blenlib/intern/edgehash.c index 81bfb566278..996c815a062 100644 --- a/source/blender/blenlib/intern/edgehash.c +++ b/source/blender/blenlib/intern/edgehash.c @@ -15,19 +15,16 @@ * along with this program; if not, write to the Free Software Foundation, * Inc., 51 Franklin Street, Fifth Floor, Boston, MA 02110-1301, USA. * - * Contributor(s): Daniel Dunbar, Joseph Eagar - * * ***** END GPL LICENSE BLOCK ***** */ /** \file blender/blenlib/intern/edgehash.c * \ingroup bli * - * An (edge -> pointer) chaining hash table. + * An (edge -> pointer) hash table. * Using unordered int-pairs as keys. * - * \note Based on 'BLI_ghash.c', which is a more generalized hash-table - * make sure these stay in sync. + * \note The API matches BLI_ghash.c, but the implementation is different. */ #include <stdlib.h> @@ -38,384 +35,298 @@ #include "BLI_utildefines.h" #include "BLI_edgehash.h" -#include "BLI_mempool.h" #include "BLI_strict_flags.h" -/**************inlined code************/ -static const uint _ehash_hashsizes[] = { - 1, 3, 5, 11, 17, 37, 67, 131, 257, 521, 1031, 2053, 4099, 8209, - 16411, 32771, 65537, 131101, 262147, 524309, 1048583, 2097169, - 4194319, 8388617, 16777259, 33554467, 67108879, 134217757, - 268435459 -}; - -/* internal flag to ensure sets values aren't used */ -#ifndef NDEBUG -# define EDGEHASH_FLAG_IS_SET (1 << 8) -# define IS_EDGEHASH_ASSERT(eh) BLI_assert((eh->flag & EDGEHASH_FLAG_IS_SET) == 0) -// # define IS_EDGESET_ASSERT(es) BLI_assert((es->flag & EDGEHASH_FLAG_IS_SET) != 0) -#else -# define IS_EDGEHASH_ASSERT(eh) -// # define IS_EDGESET_ASSERT(es) -#endif - -/* ensure v0 is smaller */ -#define EDGE_ORD(v0, v1) \ - if (v0 > v1) { \ - SWAP(uint, v0, v1); \ - } (void)0 - -/***/ - -typedef struct EdgeEntry { - struct EdgeEntry *next; - uint v0, v1; - void *val; -} EdgeEntry; - -struct EdgeHash { - EdgeEntry **buckets; - BLI_mempool *epool; - uint nbuckets, nentries; - uint cursize, flag; -}; - +typedef struct _EdgeHash_Edge Edge; +typedef struct _EdgeHash_Entry EdgeHashEntry; + +typedef struct EdgeHash { + EdgeHashEntry *entries; + int32_t *map; + uint32_t slot_mask; + uint capacity_exp; + uint length; + uint dummy_count; +} EdgeHash; + +typedef struct EdgeSet { + Edge *entries; + int32_t *map; + uint32_t slot_mask; + uint capacity_exp; + uint length; +} EdgeSet; /* -------------------------------------------------------------------- */ -/* EdgeHash API */ - -/** \name Internal Utility API +/** \name Internal Helper Macros & Defines * \{ */ -/** - * Compute the hash and get the bucket-index. - */ -BLI_INLINE uint edgehash_bucket_index(EdgeHash *eh, uint v0, uint v1) -{ - BLI_assert(v0 < v1); - - return ((v0 * 65) ^ (v1 * 31)) % eh->nbuckets; -} +#define ENTRIES_CAPACITY(container) (uint)(1 << (container)->capacity_exp) +#define MAP_CAPACITY(container) (uint)(1 << ((container)->capacity_exp + 1)) +#define CLEAR_MAP(container) memset(container->map, 0xFF, sizeof(int32_t) * MAP_CAPACITY(container)) +#define UPDATE_SLOT_MASK(container) (container)->slot_mask = MAP_CAPACITY(container) - 1 +#define PERTURB_SHIFT 5 -/** - * Check if the number of items in the GHash is large enough to require more buckets. - */ -BLI_INLINE bool edgehash_test_expand_buckets(const uint nentries, const uint nbuckets) -{ - return (nentries > nbuckets * 3); -} +#define ITER_SLOTS(CONTAINER, EDGE, SLOT, INDEX) \ + uint32_t hash = calc_edge_hash(EDGE); \ + uint32_t mask = (CONTAINER)->slot_mask; \ + uint32_t perturb = hash; \ + int32_t *map = (CONTAINER)->map; \ + uint32_t SLOT = mask & hash; \ + int INDEX = map[SLOT]; \ + for (;;SLOT = mask & ((5 * SLOT) + 1 + perturb), perturb >>= PERTURB_SHIFT, INDEX = map[SLOT]) -/** - * Expand buckets to the next size up. - */ -BLI_INLINE void edgehash_resize_buckets(EdgeHash *eh, const uint nbuckets) -{ - EdgeEntry **buckets_old = eh->buckets; - EdgeEntry **buckets_new; - const uint nbuckets_old = eh->nbuckets; - uint i; +#define SLOT_EMPTY -1 +#define SLOT_DUMMY -2 - BLI_assert(eh->nbuckets != nbuckets); +#define CAPACITY_EXP_DEFAULT 3 - eh->nbuckets = nbuckets; - buckets_new = MEM_callocN(eh->nbuckets * sizeof(*eh->buckets), "eh buckets"); +/** \} */ - for (i = 0; i < nbuckets_old; i++) { - for (EdgeEntry *e = buckets_old[i], *e_next; e; e = e_next) { - const unsigned bucket_index = edgehash_bucket_index(eh, e->v0, e->v1); - e_next = e->next; - e->next = buckets_new[bucket_index]; - buckets_new[bucket_index] = e; - } - } +/* -------------------------------------------------------------------- */ +/** \name Internal Edge API + * \{ */ - eh->buckets = buckets_new; - MEM_freeN(buckets_old); +BLI_INLINE uint32_t calc_edge_hash(Edge edge) +{ + return (edge.v_low << 8) ^ edge.v_high; } -/** - * Increase initial bucket size to match a reserved amount. - */ -BLI_INLINE void edgehash_buckets_reserve(EdgeHash *eh, const uint nentries_reserve) +BLI_INLINE Edge init_edge(uint v0, uint v1) { - while (edgehash_test_expand_buckets(nentries_reserve, eh->nbuckets)) { - eh->nbuckets = _ehash_hashsizes[++eh->cursize]; + Edge edge; + if (v0 < v1) { + edge.v_low = v0; + edge.v_high = v1; } -} - -/** - * Internal lookup function. - * Takes a \a bucket_index argument to avoid calling #edgehash_bucket_index multiple times. - */ -BLI_INLINE EdgeEntry *edgehash_lookup_entry_ex( - EdgeHash *eh, uint v0, uint v1, - const uint bucket_index) -{ - EdgeEntry *e; - BLI_assert(v0 < v1); - for (e = eh->buckets[bucket_index]; e; e = e->next) { - if (UNLIKELY(v0 == e->v0 && v1 == e->v1)) { - return e; - } + else { + edge.v_low = v1; + edge.v_high = v0; } - return NULL; + return edge; } -/** - * Internal lookup function, returns previous entry of target one too. - * Takes bucket_index argument to avoid calling #edgehash_bucket_index multiple times. - * Useful when modifying buckets somehow (like removing an entry...). - */ -BLI_INLINE EdgeEntry *edgehash_lookup_entry_prev_ex( - EdgeHash *eh, uint v0, uint v1, - EdgeEntry **r_e_prev, const uint bucket_index) -{ - BLI_assert(v0 < v1); - for (EdgeEntry *e_prev = NULL, *e = eh->buckets[bucket_index]; e; e_prev = e, e = e->next) { - if (UNLIKELY(v0 == e->v0 && v1 == e->v1)) { - *r_e_prev = e_prev; - return e; - } - } - - *r_e_prev = NULL; - return NULL; +BLI_INLINE bool edges_equal(Edge e1, Edge e2) +{ + return memcmp(&e1, &e2, sizeof(Edge)) == 0; } -/** - * Internal lookup function. Only wraps #edgehash_lookup_entry_ex - */ -BLI_INLINE EdgeEntry *edgehash_lookup_entry(EdgeHash *eh, uint v0, uint v1) +static uint calc_capacity_exp_for_reserve(uint reserve) { - EDGE_ORD(v0, v1); - const uint bucket_index = edgehash_bucket_index(eh, v0, v1); - return edgehash_lookup_entry_ex(eh, v0, v1, bucket_index); + uint result = 1; + while (reserve >>= 1) result++; + return result; } +/** \} */ -static EdgeHash *edgehash_new(const char *info, - const uint nentries_reserve, - const uint entry_size) -{ - EdgeHash *eh = MEM_mallocN(sizeof(*eh), info); +/* -------------------------------------------------------------------- */ +/** \name Internal Utility API + * \{ */ - eh->nbuckets = _ehash_hashsizes[0]; /* eh->cursize */ - eh->nentries = 0; - eh->cursize = 0; - eh->flag = 0; +#define EH_INDEX_HAS_EDGE(eh, index, edge) (index) >= 0 && edges_equal((edge), (eh)->entries[index].edge) - /* if we have reserved the number of elements that this hash will contain */ - if (nentries_reserve) { - edgehash_buckets_reserve(eh, nentries_reserve); +static void edgehash_free_values(EdgeHash *eh, EdgeHashFreeFP free_value) +{ + if (free_value) { + for (uint i = 0; i < eh->length; i++) { + free_value(eh->entries[i].value); + } } - - eh->buckets = MEM_callocN(eh->nbuckets * sizeof(*eh->buckets), "eh buckets"); - eh->epool = BLI_mempool_create(entry_size, nentries_reserve, 512, BLI_MEMPOOL_NOP); - - return eh; } -/** - * Internal insert function. - * Takes a \a bucket_index argument to avoid calling #edgehash_bucket_index multiple times. - */ -BLI_INLINE void edgehash_insert_ex( - EdgeHash *eh, uint v0, uint v1, void *val, - const uint bucket_index) +BLI_INLINE void edgehash_insert_index(EdgeHash *eh, Edge edge, uint entry_index) { - EdgeEntry *e = BLI_mempool_alloc(eh->epool); - - BLI_assert((eh->flag & EDGEHASH_FLAG_ALLOW_DUPES) || (BLI_edgehash_haskey(eh, v0, v1) == 0)); - IS_EDGEHASH_ASSERT(eh); - - /* this helps to track down errors with bad edge data */ - BLI_assert(v0 < v1); - BLI_assert(v0 != v1); - - e->next = eh->buckets[bucket_index]; - e->v0 = v0; - e->v1 = v1; - e->val = val; - eh->buckets[bucket_index] = e; - - if (UNLIKELY(edgehash_test_expand_buckets(++eh->nentries, eh->nbuckets))) { - edgehash_resize_buckets(eh, _ehash_hashsizes[++eh->cursize]); + ITER_SLOTS(eh, edge, slot, index) { + if (index == SLOT_EMPTY) { + eh->map[slot] = (int32_t)entry_index; + break; + } } } -/** - * Insert function that doesn't set the value (use for EdgeSet) - */ -BLI_INLINE void edgehash_insert_ex_keyonly( - EdgeHash *eh, uint v0, uint v1, - const uint bucket_index) +BLI_INLINE EdgeHashEntry *edgehash_insert_at_slot(EdgeHash *eh, uint slot, Edge edge, void *value) { - EdgeEntry *e = BLI_mempool_alloc(eh->epool); - - BLI_assert((eh->flag & EDGEHASH_FLAG_ALLOW_DUPES) || (BLI_edgehash_haskey(eh, v0, v1) == 0)); - - /* this helps to track down errors with bad edge data */ - BLI_assert(v0 < v1); - BLI_assert(v0 != v1); - - e->next = eh->buckets[bucket_index]; - e->v0 = v0; - e->v1 = v1; - eh->buckets[bucket_index] = e; - - if (UNLIKELY(edgehash_test_expand_buckets(++eh->nentries, eh->nbuckets))) { - edgehash_resize_buckets(eh, _ehash_hashsizes[++eh->cursize]); - } + EdgeHashEntry *entry = &eh->entries[eh->length]; + entry->edge = edge; + entry->value = value; + eh->map[slot] = (int32_t)eh->length; + eh->length++; + return entry; } -/** - * Insert function that doesn't set the value (use for EdgeSet) - */ -BLI_INLINE void edgehash_insert_ex_keyonly_entry( - EdgeHash *eh, uint v0, uint v1, - const uint bucket_index, - EdgeEntry *e) +BLI_INLINE bool edgehash_ensure_can_insert(EdgeHash *eh) { - BLI_assert((eh->flag & EDGEHASH_FLAG_ALLOW_DUPES) || (BLI_edgehash_haskey(eh, v0, v1) == 0)); - - /* this helps to track down errors with bad edge data */ - BLI_assert(v0 < v1); - BLI_assert(v0 != v1); - - e->next = eh->buckets[bucket_index]; - e->v0 = v0; - e->v1 = v1; - /* intentionally leave value unset */ - eh->buckets[bucket_index] = e; - - if (UNLIKELY(edgehash_test_expand_buckets(++eh->nentries, eh->nbuckets))) { - edgehash_resize_buckets(eh, _ehash_hashsizes[++eh->cursize]); + if (UNLIKELY(ENTRIES_CAPACITY(eh) <= eh->length + eh->dummy_count)) { + eh->capacity_exp++; + UPDATE_SLOT_MASK(eh); + eh->dummy_count = 0; + eh->entries = MEM_reallocN(eh->entries, sizeof(EdgeHashEntry) * ENTRIES_CAPACITY(eh)); + eh->map = MEM_reallocN(eh->map, sizeof(int32_t) * MAP_CAPACITY(eh)); + CLEAR_MAP(eh); + for (uint i = 0; i < eh->length; i++) { + edgehash_insert_index(eh, eh->entries[i].edge, i); + } + return true; } + return false; } -BLI_INLINE void edgehash_insert(EdgeHash *eh, uint v0, uint v1, void *val) +BLI_INLINE EdgeHashEntry *edgehash_insert(EdgeHash *eh, Edge edge, void *value) { - EDGE_ORD(v0, v1); - const uint bucket_index = edgehash_bucket_index(eh, v0, v1); - edgehash_insert_ex(eh, v0, v1, val, bucket_index); + ITER_SLOTS(eh, edge, slot, index) { + if (index == SLOT_EMPTY) { + return edgehash_insert_at_slot(eh, slot, edge, value); + } + else if (index == SLOT_DUMMY) { + eh->dummy_count--; + return edgehash_insert_at_slot(eh, slot, edge, value); + } + } } -/** - * Remove the entry and return it, caller must free from eh->epool. - */ -BLI_INLINE EdgeEntry *edgehash_remove_ex( - EdgeHash *eh, uint v0, uint v1, - EdgeHashFreeFP valfreefp, - const uint bucket_index) +BLI_INLINE EdgeHashEntry *edgehash_lookup_entry(EdgeHash *eh, uint v0, uint v1) { - EdgeEntry *e_prev; - EdgeEntry *e = edgehash_lookup_entry_prev_ex(eh, v0, v1, &e_prev, bucket_index); - - BLI_assert(v0 < v1); - - if (e) { - EdgeEntry *e_next = e->next; - - if (valfreefp) { - valfreefp(e->val); - } + Edge edge = init_edge(v0, v1); - if (e_prev) { - e_prev->next = e_next; + ITER_SLOTS(eh, edge, slot, index) { + if (EH_INDEX_HAS_EDGE(eh, index, edge)) { + return &eh->entries[index]; } - else { - eh->buckets[bucket_index] = e_next; + else if (index == SLOT_EMPTY) { + return NULL; } - - eh->nentries--; - return e; } - - return e; } -/** - * Run free callbacks for freeing entries. - */ -static void edgehash_free_cb(EdgeHash *eh, EdgeHashFreeFP valfreefp) +BLI_INLINE void edgehash_change_index(EdgeHash *eh, Edge edge, int new_index) { - uint i; - - BLI_assert(valfreefp); - - for (i = 0; i < eh->nbuckets; i++) { - EdgeEntry *e; - - for (e = eh->buckets[i]; e; ) { - EdgeEntry *e_next = e->next; - - valfreefp(e->val); - - e = e_next; + ITER_SLOTS(eh, edge, slot, index) { + if (EH_INDEX_HAS_EDGE(eh, index, edge)) { + eh->map[slot] = new_index; + break; } } } /** \} */ - -/** \name Public API +/* -------------------------------------------------------------------- */ +/** \name Edge Hash API * \{ */ -/* Public API */ - -EdgeHash *BLI_edgehash_new_ex(const char *info, - const uint nentries_reserve) +EdgeHash *BLI_edgehash_new_ex(const char *info, const uint reserve) { - return edgehash_new(info, - nentries_reserve, - sizeof(EdgeEntry)); + EdgeHash *eh = MEM_mallocN(sizeof(EdgeHash), info); + eh->capacity_exp = calc_capacity_exp_for_reserve(reserve); + UPDATE_SLOT_MASK(eh); + eh->length = 0; + eh->dummy_count = 0; + eh->entries = MEM_calloc_arrayN(sizeof(EdgeHashEntry), ENTRIES_CAPACITY(eh), "eh entries"); + eh->map = MEM_malloc_arrayN(sizeof(int32_t), MAP_CAPACITY(eh), "eh map"); + CLEAR_MAP(eh); + return eh; } EdgeHash *BLI_edgehash_new(const char *info) { - return BLI_edgehash_new_ex(info, 0); + return BLI_edgehash_new_ex(info, 1 << CAPACITY_EXP_DEFAULT); +} + +void BLI_edgehash_free(EdgeHash *eh, EdgeHashFreeFP free_value) +{ + edgehash_free_values(eh, free_value); + MEM_freeN(eh->map); + MEM_freeN(eh->entries); + MEM_freeN(eh); +} + +void BLI_edgehash_print(EdgeHash *eh) +{ + printf("Edgehash at %p:\n", eh); + printf(" Map:\n"); + for (uint i = 0; i < MAP_CAPACITY(eh); i++) { + int index = eh->map[i]; + printf(" %u: %d", i, index); + if (index >= 0) { + EdgeHashEntry entry = eh->entries[index]; + printf(" -> (%u, %u) -> %p", entry.edge.v_low, entry.edge.v_high, entry.value); + } + printf("\n"); + } + printf(" Entries:\n"); + for (uint i = 0; i < ENTRIES_CAPACITY(eh); i++) { + if (i == eh->length) printf(" **** below is rest capacity ****\n"); + EdgeHashEntry entry = eh->entries[i]; + printf(" %u: (%u, %u) -> %p\n", i, entry.edge.v_low, entry.edge.v_high, entry.value); + + } } /** * Insert edge (\a v0, \a v1) into hash with given value, does * not check for duplicates. */ -void BLI_edgehash_insert(EdgeHash *eh, uint v0, uint v1, void *val) +void BLI_edgehash_insert(EdgeHash *eh, uint v0, uint v1, void *value) { - edgehash_insert(eh, v0, v1, val); + edgehash_ensure_can_insert(eh); + Edge edge = init_edge(v0, v1); + edgehash_insert(eh, edge, value); } /** * Assign a new value to a key that may already be in edgehash. */ -bool BLI_edgehash_reinsert(EdgeHash *eh, uint v0, uint v1, void *val) +bool BLI_edgehash_reinsert(EdgeHash *eh, uint v0, uint v1, void *value) { - IS_EDGEHASH_ASSERT(eh); - - EDGE_ORD(v0, v1); - const uint bucket_index = edgehash_bucket_index(eh, v0, v1); + Edge edge = init_edge(v0, v1); - EdgeEntry *e = edgehash_lookup_entry_ex(eh, v0, v1, bucket_index); - if (e) { - e->val = val; - return false; - } - else { - edgehash_insert_ex(eh, v0, v1, val, bucket_index); - return true; + ITER_SLOTS(eh, edge, slot, index) { + if (EH_INDEX_HAS_EDGE(eh, index, edge)) { + eh->entries[index].value = value; + return false; + } + else if (index == SLOT_EMPTY) { + if (edgehash_ensure_can_insert(eh)) { + edgehash_insert(eh, edge, value); + } + else { + edgehash_insert_at_slot(eh, slot, edge, value); + } + return true; + } } } /** + * A version of #BLI_edgehash_lookup which accepts a fallback argument. + */ +void *BLI_edgehash_lookup_default(EdgeHash *eh, uint v0, uint v1, void *default_value) +{ + EdgeHashEntry *entry = edgehash_lookup_entry(eh, v0, v1); + return entry ? entry->value : default_value; +} + +/** + * Return value for given edge (\a v0, \a v1), or NULL if + * if key does not exist in hash. (If need exists + * to differentiate between key-value being NULL and + * lack of key then see BLI_edgehash_lookup_p(). + */ +void *BLI_edgehash_lookup(EdgeHash *eh, uint v0, uint v1) +{ + EdgeHashEntry *entry = edgehash_lookup_entry(eh, v0, v1); + return entry ? entry->value : NULL; +} + +/** * Return pointer to value for given edge (\a v0, \a v1), * or NULL if key does not exist in hash. */ void **BLI_edgehash_lookup_p(EdgeHash *eh, uint v0, uint v1) { - EdgeEntry *e = edgehash_lookup_entry(eh, v0, v1); - IS_EDGEHASH_ASSERT(eh); - return e ? &e->val : NULL; + EdgeHashEntry *entry = edgehash_lookup_entry(eh, v0, v1); + return entry ? &entry->value : NULL; } /** @@ -432,43 +343,25 @@ void **BLI_edgehash_lookup_p(EdgeHash *eh, uint v0, uint v1) * \returns true when the value didn't need to be added. * (when false, the caller _must_ initialize the value). */ -bool BLI_edgehash_ensure_p(EdgeHash *eh, uint v0, uint v1, void ***r_val) +bool BLI_edgehash_ensure_p(EdgeHash *eh, uint v0, uint v1, void ***r_value) { - EDGE_ORD(v0, v1); - const uint bucket_index = edgehash_bucket_index(eh, v0, v1); - EdgeEntry *e = edgehash_lookup_entry_ex(eh, v0, v1, bucket_index); - const bool haskey = (e != NULL); + Edge edge = init_edge(v0, v1); - if (!haskey) { - e = BLI_mempool_alloc(eh->epool); - edgehash_insert_ex_keyonly_entry(eh, v0, v1, bucket_index, e); + ITER_SLOTS(eh, edge, slot, index) { + if (EH_INDEX_HAS_EDGE(eh, index, edge)) { + *r_value = &eh->entries[index].value; + return true; + } + else if (index == SLOT_EMPTY) { + if (edgehash_ensure_can_insert(eh)) { + edgehash_insert(eh, edge, NULL); + } + else { + *r_value = &edgehash_insert_at_slot(eh, slot, edge, NULL)->value; + } + return false; + } } - - *r_val = &e->val; - return haskey; -} - -/** - * Return value for given edge (\a v0, \a v1), or NULL if - * if key does not exist in hash. (If need exists - * to differentiate between key-value being NULL and - * lack of key then see BLI_edgehash_lookup_p(). - */ -void *BLI_edgehash_lookup(EdgeHash *eh, uint v0, uint v1) -{ - EdgeEntry *e = edgehash_lookup_entry(eh, v0, v1); - IS_EDGEHASH_ASSERT(eh); - return e ? e->val : NULL; -} - -/** - * A version of #BLI_edgehash_lookup which accepts a fallback argument. - */ -void *BLI_edgehash_lookup_default(EdgeHash *eh, uint v0, uint v1, void *val_default) -{ - EdgeEntry *e = edgehash_lookup_entry(eh, v0, v1); - IS_EDGEHASH_ASSERT(eh); - return e ? e->val : val_default; } /** @@ -478,18 +371,12 @@ void *BLI_edgehash_lookup_default(EdgeHash *eh, uint v0, uint v1, void *val_defa * \param valfreefp: Optional callback to free the value. * \return true if \a key was removed from \a eh. */ -bool BLI_edgehash_remove(EdgeHash *eh, uint v0, uint v1, EdgeHashFreeFP valfreefp) +bool BLI_edgehash_remove(EdgeHash *eh, uint v0, uint v1, EdgeHashFreeFP free_value) { - EDGE_ORD(v0, v1); - const uint bucket_index = edgehash_bucket_index(eh, v0, v1); - EdgeEntry *e = edgehash_remove_ex(eh, v0, v1, valfreefp, bucket_index); - if (e) { - BLI_mempool_free(eh->epool, e); - return true; - } - else { - return false; - } + uint old_length = eh->length; + void *value = BLI_edgehash_popkey(eh, v0, v1); + if (free_value && value) free_value(value); + return old_length > eh->length; } /* same as above but return the value, @@ -502,17 +389,23 @@ bool BLI_edgehash_remove(EdgeHash *eh, uint v0, uint v1, EdgeHashFreeFP valfreef */ void *BLI_edgehash_popkey(EdgeHash *eh, uint v0, uint v1) { - EDGE_ORD(v0, v1); - const uint bucket_index = edgehash_bucket_index(eh, v0, v1); - EdgeEntry *e = edgehash_remove_ex(eh, v0, v1, NULL, bucket_index); - IS_EDGEHASH_ASSERT(eh); - if (e) { - void *val = e->val; - BLI_mempool_free(eh->epool, e); - return val; - } - else { - return NULL; + Edge edge = init_edge(v0, v1); + + ITER_SLOTS(eh, edge, slot, index) { + if (EH_INDEX_HAS_EDGE(eh, index, edge)) { + void *value = eh->entries[index].value; + eh->length--; + eh->dummy_count++; + eh->map[slot] = SLOT_DUMMY; + eh->entries[index] = eh->entries[eh->length]; + if ((uint)index < eh->length) { + edgehash_change_index(eh, eh->entries[index].edge, index); + } + return value; + } + else if (index == SLOT_EMPTY) { + return NULL; + } } } @@ -521,7 +414,7 @@ void *BLI_edgehash_popkey(EdgeHash *eh, uint v0, uint v1) */ bool BLI_edgehash_haskey(EdgeHash *eh, uint v0, uint v1) { - return (edgehash_lookup_entry(eh, v0, v1) != NULL); + return edgehash_lookup_entry(eh, v0, v1) != NULL; } /** @@ -529,71 +422,34 @@ bool BLI_edgehash_haskey(EdgeHash *eh, uint v0, uint v1) */ int BLI_edgehash_len(EdgeHash *eh) { - return (int)eh->nentries; + return (int)eh->length; } /** * Remove all edges from hash. */ -void BLI_edgehash_clear_ex(EdgeHash *eh, EdgeHashFreeFP valfreefp, - const uint nentries_reserve) +void BLI_edgehash_clear_ex(EdgeHash *eh, EdgeHashFreeFP free_value, const uint UNUSED(reserve)) { - if (valfreefp) - edgehash_free_cb(eh, valfreefp); - - eh->nbuckets = _ehash_hashsizes[0]; /* eh->cursize */ - eh->nentries = 0; - eh->cursize = 0; - - if (nentries_reserve) { - edgehash_buckets_reserve(eh, nentries_reserve); - } - - MEM_freeN(eh->buckets); - eh->buckets = MEM_callocN(eh->nbuckets * sizeof(*eh->buckets), "eh buckets"); - - BLI_mempool_clear_ex(eh->epool, nentries_reserve ? (int)nentries_reserve : -1); + /* TODO: handle reserve */ + edgehash_free_values(eh, free_value); + eh->length = 0; + eh->dummy_count = 0; + eh->capacity_exp = CAPACITY_EXP_DEFAULT; + CLEAR_MAP(eh); } /** * Wraps #BLI_edgehash_clear_ex with zero entries reserved. */ -void BLI_edgehash_clear(EdgeHash *eh, EdgeHashFreeFP valfreefp) -{ - BLI_edgehash_clear_ex(eh, valfreefp, 0); -} - -void BLI_edgehash_free(EdgeHash *eh, EdgeHashFreeFP valfreefp) -{ - BLI_assert((int)eh->nentries == BLI_mempool_len(eh->epool)); - - if (valfreefp) - edgehash_free_cb(eh, valfreefp); - - BLI_mempool_destroy(eh->epool); - - MEM_freeN(eh->buckets); - MEM_freeN(eh); -} - - -void BLI_edgehash_flag_set(EdgeHash *eh, uint flag) -{ - eh->flag |= flag; -} - -void BLI_edgehash_flag_clear(EdgeHash *eh, uint flag) +void BLI_edgehash_clear(EdgeHash *eh, EdgeHashFreeFP free_value) { - eh->flag &= ~flag; + BLI_edgehash_clear_ex(eh, free_value, 0); } /** \} */ - /* -------------------------------------------------------------------- */ -/* EdgeHash Iterator API */ - -/** \name Iterator API +/** \name Edge Hash Iterator API * \{ */ /** @@ -603,7 +459,7 @@ void BLI_edgehash_flag_clear(EdgeHash *eh, uint flag) */ EdgeHashIterator *BLI_edgehashIterator_new(EdgeHash *eh) { - EdgeHashIterator *ehi = MEM_mallocN(sizeof(*ehi), "eh iter"); + EdgeHashIterator *ehi = MEM_mallocN(sizeof(EdgeHashIterator), __func__); BLI_edgehashIterator_init(ehi, eh); return ehi; } @@ -618,37 +474,9 @@ EdgeHashIterator *BLI_edgehashIterator_new(EdgeHash *eh) */ void BLI_edgehashIterator_init(EdgeHashIterator *ehi, EdgeHash *eh) { - ehi->eh = eh; - ehi->curEntry = NULL; - ehi->curBucket = UINT_MAX; /* wraps to zero */ - if (eh->nentries) { - do { - ehi->curBucket++; - if (UNLIKELY(ehi->curBucket == ehi->eh->nbuckets)) { - break; - } - - ehi->curEntry = ehi->eh->buckets[ehi->curBucket]; - } while (!ehi->curEntry); - } -} - -/** - * Steps the iterator to the next index. - */ -void BLI_edgehashIterator_step(EdgeHashIterator *ehi) -{ - if (ehi->curEntry) { - ehi->curEntry = ehi->curEntry->next; - while (!ehi->curEntry) { - ehi->curBucket++; - if (UNLIKELY(ehi->curBucket == ehi->eh->nbuckets)) { - break; - } - - ehi->curEntry = ehi->eh->buckets[ehi->curBucket]; - } - } + ehi->entries = eh->entries; + ehi->length = eh->length; + ehi->index = 0; } /** @@ -663,43 +491,71 @@ void BLI_edgehashIterator_free(EdgeHashIterator *ehi) /** \} */ /* -------------------------------------------------------------------- */ -/* EdgeSet API */ +/** \name EdgeSet API + * + * Use edgehash API to give 'set' functionality + * \{ */ -/* Use edgehash API to give 'set' functionality */ +#define ES_INDEX_HAS_EDGE(es, index, edge) (index) >= 0 && edges_equal((edge), (es)->entries[index]) -/** \name EdgeSet Functions - * \{ */ -EdgeSet *BLI_edgeset_new_ex(const char *info, - const uint nentries_reserve) -{ - EdgeSet *es = (EdgeSet *)edgehash_new(info, - nentries_reserve, - sizeof(EdgeEntry) - sizeof(void *)); -#ifndef NDEBUG - ((EdgeHash *)es)->flag |= EDGEHASH_FLAG_IS_SET; -#endif +EdgeSet *BLI_edgeset_new_ex(const char *info, const uint reserve) +{ + EdgeSet *es = MEM_mallocN(sizeof(EdgeSet), info); + es->capacity_exp = calc_capacity_exp_for_reserve(reserve); + UPDATE_SLOT_MASK(es); + es->length = 0; + es->entries = MEM_malloc_arrayN(sizeof(Edge), ENTRIES_CAPACITY(es), "es entries"); + es->map = MEM_malloc_arrayN(sizeof(int32_t), MAP_CAPACITY(es), "es map"); + CLEAR_MAP(es); return es; } EdgeSet *BLI_edgeset_new(const char *info) { - return BLI_edgeset_new_ex(info, 0); + return BLI_edgeset_new_ex(info, 1 << CAPACITY_EXP_DEFAULT); +} + +void BLI_edgeset_free(EdgeSet *es) +{ + MEM_freeN(es->entries); + MEM_freeN(es->map); + MEM_freeN(es); } int BLI_edgeset_len(EdgeSet *es) { - return (int)((EdgeHash *)es)->nentries; + return (int)es->length; } -/** - * Adds the key to the set (no checks for unique keys!). - * Matching #BLI_edgehash_insert - */ -void BLI_edgeset_insert(EdgeSet *es, uint v0, uint v1) +static void edgeset_insert_index(EdgeSet *es, Edge edge, uint entry_index) +{ + ITER_SLOTS(es, edge, slot, index) { + if (index == SLOT_EMPTY) { + es->map[slot] = (int)entry_index; + break; + } + } +} + +BLI_INLINE void edgeset_ensure_can_insert(EdgeSet *es) { - EDGE_ORD(v0, v1); - const uint bucket_index = edgehash_bucket_index((EdgeHash *)es, v0, v1); - edgehash_insert_ex_keyonly((EdgeHash *)es, v0, v1, bucket_index); + if (UNLIKELY(ENTRIES_CAPACITY(es) <= es->length)) { + es->capacity_exp++; + UPDATE_SLOT_MASK(es); + es->entries = MEM_reallocN(es->entries, sizeof(Edge) * ENTRIES_CAPACITY(es)); + es->map = MEM_reallocN(es->map, sizeof(int32_t) * MAP_CAPACITY(es)); + CLEAR_MAP(es); + for (uint i = 0; i < es->length; i++) { + edgeset_insert_index(es, es->entries[i], i); + } + } +} + +BLI_INLINE void edgeset_insert_at_slot(EdgeSet *es, uint slot, Edge edge) +{ + es->entries[es->length] = edge; + es->map[slot] = (int)es->length; + es->length++; } /** @@ -710,73 +566,63 @@ void BLI_edgeset_insert(EdgeSet *es, uint v0, uint v1) */ bool BLI_edgeset_add(EdgeSet *es, uint v0, uint v1) { - EDGE_ORD(v0, v1); - const uint bucket_index = edgehash_bucket_index((EdgeHash *)es, v0, v1); + edgeset_ensure_can_insert(es); + Edge edge = init_edge(v0, v1); - EdgeEntry *e = edgehash_lookup_entry_ex((EdgeHash *)es, v0, v1, bucket_index); - if (e) { - return false; - } - else { - edgehash_insert_ex_keyonly((EdgeHash *)es, v0, v1, bucket_index); - return true; + ITER_SLOTS(es, edge, slot, index) { + if (ES_INDEX_HAS_EDGE(es, index, edge)) { + return false; + } + else if (index == SLOT_EMPTY) { + edgeset_insert_at_slot(es, slot, edge); + return true; + } } } -bool BLI_edgeset_haskey(EdgeSet *es, uint v0, uint v1) +/** + * Adds the key to the set (no checks for unique keys!). + * Matching #BLI_edgehash_insert + */ +void BLI_edgeset_insert(EdgeSet *es, uint v0, uint v1) { - return (edgehash_lookup_entry((EdgeHash *)es, v0, v1) != NULL); -} + edgeset_ensure_can_insert(es); + Edge edge = init_edge(v0, v1); - -void BLI_edgeset_free(EdgeSet *es) -{ - BLI_edgehash_free((EdgeHash *)es, NULL); + ITER_SLOTS(es, edge, slot, index) { + if (index == SLOT_EMPTY) { + edgeset_insert_at_slot(es, slot, edge); + return; + } + } } -void BLI_edgeset_flag_set(EdgeSet *es, uint flag) +bool BLI_edgeset_haskey(EdgeSet *es, uint v0, uint v1) { - ((EdgeHash *)es)->flag |= flag; -} + Edge edge = init_edge(v0, v1); -void BLI_edgeset_flag_clear(EdgeSet *es, uint flag) -{ - ((EdgeHash *)es)->flag &= ~flag; + ITER_SLOTS(es, edge, slot, index) { + if (ES_INDEX_HAS_EDGE(es, index, edge)) { + return true; + } + else if (index == SLOT_EMPTY) { + return false; + } + } } -/** \} */ - -/** \name Debugging & Introspection - * \{ */ -#ifdef DEBUG - -/** - * Measure how well the hash function performs - * (1.0 is approx as good as random distribution). - */ -double BLI_edgehash_calc_quality(EdgeHash *eh) +EdgeSetIterator *BLI_edgesetIterator_new(EdgeSet *es) { - uint64_t sum = 0; - uint i; - - if (eh->nentries == 0) - return -1.0; - - for (i = 0; i < eh->nbuckets; i++) { - uint64_t count = 0; - EdgeEntry *e; - for (e = eh->buckets[i]; e; e = e->next) { - count += 1; - } - sum += count * (count + 1); - } - return ((double)sum * (double)eh->nbuckets / - ((double)eh->nentries * (eh->nentries + 2 * eh->nbuckets - 1))); + EdgeSetIterator *esi = MEM_mallocN(sizeof(EdgeSetIterator), __func__); + esi->edges = es->entries; + esi->length = es->length; + esi->index = 0; + return esi; } -double BLI_edgeset_calc_quality(EdgeSet *es) + +void BLI_edgesetIterator_free(EdgeSetIterator *esi) { - return BLI_edgehash_calc_quality((EdgeHash *)es); + MEM_freeN(esi); } -#endif /** \} */ diff --git a/tests/gtests/blenlib/BLI_edgehash_test.cc b/tests/gtests/blenlib/BLI_edgehash_test.cc new file mode 100644 index 00000000000..a9771d50c92 --- /dev/null +++ b/tests/gtests/blenlib/BLI_edgehash_test.cc @@ -0,0 +1,405 @@ +/* Apache License, Version 2.0 */ + +#include "testing/testing.h" +#include <vector> +#include <algorithm> + +extern "C" { +#include "BLI_utildefines.h" +#include "BLI_edgehash.h" +} + +#define VALUE_1 POINTER_FROM_INT(1) +#define VALUE_2 POINTER_FROM_INT(2) +#define VALUE_3 POINTER_FROM_INT(3) + +TEST(edgehash, InsertIncreasesLength) +{ + EdgeHash *eh = BLI_edgehash_new(__func__); + + ASSERT_EQ(BLI_edgehash_len(eh), 0); + BLI_edgehash_insert(eh, 1, 2, VALUE_1); + ASSERT_EQ(BLI_edgehash_len(eh), 1); + + BLI_edgehash_free(eh, nullptr); +} + +TEST(edgehash, ReinsertNewIncreasesLength) +{ + EdgeHash *eh = BLI_edgehash_new(__func__); + + ASSERT_EQ(BLI_edgehash_len(eh), 0); + BLI_edgehash_reinsert(eh, 1, 2, VALUE_1); + ASSERT_EQ(BLI_edgehash_len(eh), 1); + + BLI_edgehash_free(eh, nullptr); +} + +TEST(edgehash, ReinsertExistingDoesNotIncreaseLength) +{ + EdgeHash *eh = BLI_edgehash_new(__func__); + + ASSERT_EQ(BLI_edgehash_len(eh), 0); + BLI_edgehash_reinsert(eh, 1, 2, VALUE_1); + ASSERT_EQ(BLI_edgehash_len(eh), 1); + BLI_edgehash_reinsert(eh, 1, 2, VALUE_2); + ASSERT_EQ(BLI_edgehash_len(eh), 1); + BLI_edgehash_reinsert(eh, 2, 1, VALUE_2); + ASSERT_EQ(BLI_edgehash_len(eh), 1); + + BLI_edgehash_free(eh, nullptr); +} + +TEST(edgehash, ReinsertCanChangeValue) +{ + EdgeHash *eh = BLI_edgehash_new(__func__); + + BLI_edgehash_insert(eh, 1, 2, VALUE_1); + ASSERT_EQ(BLI_edgehash_lookup(eh, 1, 2), VALUE_1); + BLI_edgehash_reinsert(eh, 2, 1, VALUE_2); + ASSERT_EQ(BLI_edgehash_lookup(eh, 1, 2), VALUE_2); + BLI_edgehash_reinsert(eh, 1, 2, VALUE_3); + ASSERT_EQ(BLI_edgehash_lookup(eh, 2, 1), VALUE_3); + + BLI_edgehash_free(eh, nullptr); +} + +TEST(edgehash, LookupExisting) +{ + EdgeHash *eh = BLI_edgehash_new(__func__); + + BLI_edgehash_insert(eh, 1, 2, VALUE_1); + ASSERT_EQ(BLI_edgehash_lookup(eh, 1, 2), VALUE_1); + ASSERT_EQ(BLI_edgehash_lookup(eh, 2, 1), VALUE_1); + + BLI_edgehash_free(eh, nullptr); +} + +TEST(edgehash, LookupNonExisting) +{ + EdgeHash *eh = BLI_edgehash_new(__func__); + + ASSERT_EQ(BLI_edgehash_lookup(eh, 1, 2), nullptr); + + BLI_edgehash_free(eh, nullptr); +} + +TEST(edgehash, LookupNonExistingWithDefault) +{ + EdgeHash *eh = BLI_edgehash_new(__func__); + + ASSERT_EQ(BLI_edgehash_lookup_default(eh, 1, 2, VALUE_1), VALUE_1); + + BLI_edgehash_free(eh, nullptr); +} + +TEST(edgehash, LookupExistingWithDefault) +{ + EdgeHash *eh = BLI_edgehash_new(__func__); + + BLI_edgehash_insert(eh, 1, 2, VALUE_1); + ASSERT_EQ(BLI_edgehash_lookup_default(eh, 1, 2, VALUE_2), VALUE_1); + + BLI_edgehash_free(eh, nullptr); +} + +TEST(edgehash, LookupPExisting) +{ + EdgeHash *eh = BLI_edgehash_new(__func__); + + void *value = VALUE_1; + BLI_edgehash_insert(eh, 1, 2, value); + void **value_p = BLI_edgehash_lookup_p(eh, 1, 2); + ASSERT_EQ(*value_p, VALUE_1); + *value_p = VALUE_2; + ASSERT_EQ(BLI_edgehash_lookup(eh, 1, 2), VALUE_2); + + BLI_edgehash_free(eh, nullptr); +} + +TEST(edgehash, LookupPNonExisting) +{ + EdgeHash *eh = BLI_edgehash_new(__func__); + + ASSERT_EQ(BLI_edgehash_lookup_p(eh, 1, 2), nullptr); + + BLI_edgehash_free(eh, nullptr); +} + +TEST(edgehash, EnsurePNonExisting) +{ + EdgeHash *eh = BLI_edgehash_new(__func__); + + void **value_p; + bool existed = BLI_edgehash_ensure_p(eh, 1, 2, &value_p); + ASSERT_FALSE(existed); + *value_p = VALUE_1; + ASSERT_EQ(BLI_edgehash_lookup(eh, 1, 2), VALUE_1); + + BLI_edgehash_free(eh, nullptr); +} + +TEST(edgehash, EnsurePExisting) +{ + EdgeHash *eh = BLI_edgehash_new(__func__); + + BLI_edgehash_insert(eh, 1, 2, VALUE_1); + void **value_p; + bool existed = BLI_edgehash_ensure_p(eh, 1, 2, &value_p); + ASSERT_TRUE(existed); + ASSERT_EQ(*value_p, VALUE_1); + *value_p = VALUE_2; + ASSERT_EQ(BLI_edgehash_lookup(eh, 1, 2), VALUE_2); + + BLI_edgehash_free(eh, nullptr); +} + +TEST(edgehash, RemoveExistingDecreasesLength) +{ + EdgeHash *eh = BLI_edgehash_new(__func__); + + BLI_edgehash_insert(eh, 1, 2, VALUE_1); + ASSERT_EQ(BLI_edgehash_len(eh), 1); + bool has_been_removed = BLI_edgehash_remove(eh, 1, 2, nullptr); + ASSERT_EQ(BLI_edgehash_len(eh), 0); + ASSERT_TRUE(has_been_removed); + + BLI_edgehash_free(eh, nullptr); +} + +TEST(edgehash, RemoveNonExistingDoesNotDecreaseLength) +{ + EdgeHash *eh = BLI_edgehash_new(__func__); + + BLI_edgehash_insert(eh, 1, 2, VALUE_1); + ASSERT_EQ(BLI_edgehash_len(eh), 1); + bool has_been_removed = BLI_edgehash_remove(eh, 4, 5, nullptr); + ASSERT_EQ(BLI_edgehash_len(eh), 1); + ASSERT_FALSE(has_been_removed); + + BLI_edgehash_free(eh, nullptr); +} + +TEST(edgehash, PopKeyTwice) +{ + EdgeHash *eh = BLI_edgehash_new(__func__); + + BLI_edgehash_insert(eh, 1, 2, VALUE_1); + ASSERT_EQ(BLI_edgehash_popkey(eh, 1, 2), VALUE_1); + ASSERT_EQ(BLI_edgehash_popkey(eh, 1, 2), nullptr); + + BLI_edgehash_free(eh, nullptr); +} + +TEST(edgehash, LookupInvertedIndices) +{ + EdgeHash *eh = BLI_edgehash_new(__func__); + + BLI_edgehash_insert(eh, 1, 2, VALUE_1); + ASSERT_EQ(BLI_edgehash_lookup(eh, 2, 1), VALUE_1); + + BLI_edgehash_free(eh, nullptr); +} + +TEST(edgehash, HasKeyExisting) +{ + EdgeHash *eh = BLI_edgehash_new(__func__); + + BLI_edgehash_insert(eh, 1, 2, VALUE_1); + ASSERT_TRUE(BLI_edgehash_haskey(eh, 1, 2)); + ASSERT_TRUE(BLI_edgehash_haskey(eh, 2, 1)); + + BLI_edgehash_free(eh, nullptr); +} + +TEST(edgehash, HasKeyNonExisting) +{ + EdgeHash *eh = BLI_edgehash_new(__func__); + + ASSERT_FALSE(BLI_edgehash_haskey(eh, 1, 2)); + + BLI_edgehash_free(eh, nullptr); +} + +TEST(edgehash, ClearSetsLengthToZero) +{ + EdgeHash *eh = BLI_edgehash_new(__func__); + + BLI_edgehash_insert(eh, 1, 2, VALUE_1); + BLI_edgehash_insert(eh, 1, 2, VALUE_2); + ASSERT_EQ(BLI_edgehash_len(eh), 2); + BLI_edgehash_clear(eh, nullptr); + ASSERT_EQ(BLI_edgehash_len(eh), 0); + + BLI_edgehash_free(eh, nullptr); +} + +TEST(edgehash, IteratorFindsAllValues) +{ + EdgeHash *eh = BLI_edgehash_new(__func__); + + BLI_edgehash_insert(eh, 1, 2, VALUE_1); + BLI_edgehash_insert(eh, 1, 3, VALUE_2); + BLI_edgehash_insert(eh, 1, 4, VALUE_3); + + EdgeHashIterator *ehi = BLI_edgehashIterator_new(eh); + auto a = BLI_edgehashIterator_getValue(ehi); + BLI_edgehashIterator_step(ehi); + auto b = BLI_edgehashIterator_getValue(ehi); + BLI_edgehashIterator_step(ehi); + auto c = BLI_edgehashIterator_getValue(ehi); + BLI_edgehashIterator_step(ehi); + + ASSERT_NE(a, b); + ASSERT_NE(b, c); + ASSERT_NE(a, c); + ASSERT_TRUE(ELEM(a, VALUE_1, VALUE_2, VALUE_3)); + ASSERT_TRUE(ELEM(b, VALUE_1, VALUE_2, VALUE_3)); + ASSERT_TRUE(ELEM(c, VALUE_1, VALUE_2, VALUE_3)); + + BLI_edgehashIterator_free(ehi); + BLI_edgehash_free(eh, nullptr); +} + +TEST(edgehash, IterateIsDone) +{ + EdgeHash *eh = BLI_edgehash_new(__func__); + + BLI_edgehash_insert(eh, 1, 2, VALUE_1); + BLI_edgehash_insert(eh, 1, 3, VALUE_2); + BLI_edgehash_insert(eh, 1, 4, VALUE_3); + + EdgeHashIterator *ehi = BLI_edgehashIterator_new(eh); + ASSERT_FALSE(BLI_edgehashIterator_isDone(ehi)); + BLI_edgehashIterator_step(ehi); + ASSERT_FALSE(BLI_edgehashIterator_isDone(ehi)); + BLI_edgehashIterator_step(ehi); + ASSERT_FALSE(BLI_edgehashIterator_isDone(ehi)); + BLI_edgehashIterator_step(ehi); + ASSERT_TRUE(BLI_edgehashIterator_isDone(ehi)); + + BLI_edgehashIterator_free(ehi); + BLI_edgehash_free(eh, nullptr); +} + +TEST(edgehash, DoubleRemove) +{ + EdgeHash *eh = BLI_edgehash_new(__func__); + + BLI_edgehash_insert(eh, 1, 2, VALUE_1); + BLI_edgehash_insert(eh, 1, 3, VALUE_2); + BLI_edgehash_insert(eh, 1, 4, VALUE_3); + ASSERT_EQ(BLI_edgehash_len(eh), 3); + + BLI_edgehash_remove(eh, 1, 2, nullptr); + BLI_edgehash_remove(eh, 1, 3, nullptr); + ASSERT_EQ(BLI_edgehash_len(eh), 1); + + BLI_edgehash_free(eh, nullptr); +} + +struct Edge { + uint v1, v2; +}; + +TEST(edgehash, StressTest) +{ + std::srand(0); + int amount = 10000; + + std::vector<Edge> edges; + for (int i = 0; i < amount; i++) { + edges.push_back({(uint)i, amount + (uint)std::rand() % 12345}); + } + + EdgeHash *eh = BLI_edgehash_new(__func__); + + /* first insert all the edges */ + for (int i = 0; i < edges.size(); i++) { + BLI_edgehash_insert(eh, edges[i].v1, edges[i].v2, POINTER_FROM_INT(i)); + } + + std::vector<Edge> shuffled = edges; + std::random_shuffle(shuffled.begin(), shuffled.end()); + + /* then remove half of them */ + int remove_until = shuffled.size() / 2; + for (int i = 0; i < remove_until; i++) { + BLI_edgehash_remove(eh, shuffled[i].v2, shuffled[i].v1, nullptr); + } + + ASSERT_EQ(BLI_edgehash_len(eh), edges.size() - remove_until); + + /* check if the right ones have been removed */ + for (int i = 0; i < shuffled.size(); i++) { + bool haskey = BLI_edgehash_haskey(eh, shuffled[i].v1, shuffled[i].v2); + if (i < remove_until) ASSERT_FALSE(haskey); + else ASSERT_TRUE(haskey); + } + + /* reinsert all edges */ + for (int i = 0; i < edges.size(); i++) { + BLI_edgehash_reinsert(eh, edges[i].v1, edges[i].v2, POINTER_FROM_INT(i)); + } + + ASSERT_EQ(BLI_edgehash_len(eh), edges.size()); + + /* pop all edges */ + for (int i = 0; i < edges.size(); i++) { + int value = POINTER_AS_INT(BLI_edgehash_popkey(eh, edges[i].v1, edges[i].v2)); + ASSERT_EQ(i, value); + } + + ASSERT_EQ(BLI_edgehash_len(eh), 0); + + BLI_edgehash_free(eh, nullptr); +} + +TEST(edgeset, AddNonExistingIncreasesLength) +{ + EdgeSet *es = BLI_edgeset_new(__func__); + + ASSERT_EQ(BLI_edgeset_len(es), 0); + BLI_edgeset_add(es, 1, 2); + ASSERT_EQ(BLI_edgeset_len(es), 1); + BLI_edgeset_add(es, 1, 3); + ASSERT_EQ(BLI_edgeset_len(es), 2); + BLI_edgeset_add(es, 1, 4); + ASSERT_EQ(BLI_edgeset_len(es), 3); + + BLI_edgeset_free(es); +} + +TEST(edgeset, AddExistingDoesNotIncreaseLength) +{ + EdgeSet *es = BLI_edgeset_new(__func__); + + ASSERT_EQ(BLI_edgeset_len(es), 0); + BLI_edgeset_add(es, 1, 2); + ASSERT_EQ(BLI_edgeset_len(es), 1); + BLI_edgeset_add(es, 2, 1); + ASSERT_EQ(BLI_edgeset_len(es), 1); + BLI_edgeset_add(es, 1, 2); + ASSERT_EQ(BLI_edgeset_len(es), 1); + + BLI_edgeset_free(es); +} + +TEST(edgeset, HasKeyNonExisting) +{ + EdgeSet *es = BLI_edgeset_new(__func__); + + ASSERT_FALSE(BLI_edgeset_haskey(es, 1, 2)); + + BLI_edgeset_free(es); +} + +TEST(edgeset, HasKeyExisting) +{ + EdgeSet *es = BLI_edgeset_new(__func__); + + BLI_edgeset_insert(es, 1, 2); + ASSERT_TRUE(BLI_edgeset_haskey(es, 1, 2)); + + BLI_edgeset_free(es); +} diff --git a/tests/gtests/blenlib/CMakeLists.txt b/tests/gtests/blenlib/CMakeLists.txt index e399d4651f5..277dfd7afe1 100644 --- a/tests/gtests/blenlib/CMakeLists.txt +++ b/tests/gtests/blenlib/CMakeLists.txt @@ -44,6 +44,7 @@ endif() BLENDER_TEST(BLI_array_store "bf_blenlib") BLENDER_TEST(BLI_array_utils "bf_blenlib") BLENDER_TEST(BLI_expr_pylike_eval "bf_blenlib") +BLENDER_TEST(BLI_edgehash "bf_blenlib") BLENDER_TEST(BLI_ghash "bf_blenlib") BLENDER_TEST(BLI_hash_mm2a "bf_blenlib") BLENDER_TEST(BLI_heap "bf_blenlib") |