BLI: New Edgehash and EdgeSet implementation
The new data structure uses open addressing instead of chaining to resolve collisions in the hash table. This new structure was never slower than the old implementation in my tests. Code that first inserts all edges and then iterates through all edges (e.g. to remove duplicates) benefits the most, because the `EdgeHashIterator` becomes a simple for loop over a continuous array. Reviewer: campbellbarton Differential Revision: D4050
This commit is contained in:
parent
cef2a25518
commit
aa63a87d37
|
|
@ -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); }
|
||||
EdgeSetIterator *BLI_edgesetIterator_new(EdgeSet *gs);
|
||||
void BLI_edgesetIterator_free(EdgeSetIterator *esi);
|
||||
|
||||
#ifdef DEBUG
|
||||
double BLI_edgehash_calc_quality(EdgeHash *eh);
|
||||
double BLI_edgeset_calc_quality(EdgeSet *es);
|
||||
#endif
|
||||
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__ */
|
||||
|
|
|
|||
File diff suppressed because it is too large
Load Diff
|
|
@ -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);
|
||||
}
|
||||
|
|
@ -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")
|
||||
|
|
|
|||
Loading…
Reference in New Issue