[Bf-blender-cvs] [2e782109fca] sculpt-dev: Sculpt-dev: Replace usage of smallhash with ghash
Joseph Eagar
noreply at git.blender.org
Sun Nov 14 04:00:24 CET 2021
Commit: 2e782109fca5a2f4739d887c8acd86bdeb9feda2
Author: Joseph Eagar
Date: Sat Nov 13 18:57:39 2021 -0800
Branches: sculpt-dev
https://developer.blender.org/rB2e782109fca5a2f4739d887c8acd86bdeb9feda2
Sculpt-dev: Replace usage of smallhash with ghash
SmallHash doesn't deal with repeated removals
and insertions very well.
===================================================================
M source/blender/blenkernel/intern/pbvh_bmesh.c
M source/blender/blenlib/intern/smallhash.c
M source/blender/bmesh/bmesh_class.h
M source/blender/bmesh/intern/bmesh_construct.c
M source/blender/bmesh/intern/bmesh_mesh.c
===================================================================
diff --git a/source/blender/blenkernel/intern/pbvh_bmesh.c b/source/blender/blenkernel/intern/pbvh_bmesh.c
index 9137c5fb03d..ad633b8d780 100644
--- a/source/blender/blenkernel/intern/pbvh_bmesh.c
+++ b/source/blender/blenkernel/intern/pbvh_bmesh.c
@@ -342,9 +342,11 @@ static void pbvh_print_mem_size(PBVH *pbvh)
#ifdef WITH_BM_ID_FREELIST
if (bm->idmap.free_idx_map) {
- printf("free_idx_map: nentries %d, size %d\n",
+ printf("freelist length: %d\n", bm->idmap.freelist_len);
+ /* printf("free_idx_map: nentries %d, size %d: nfreecells: %d\n",
bm->idmap.free_idx_map->nentries,
- bm->idmap.free_idx_map->nbuckets);
+ bm->idmap.free_idx_map->nbuckets,
+ bm->idmap.free_idx_map->nfreecells);*/
}
#endif
}
diff --git a/source/blender/blenlib/intern/smallhash.c b/source/blender/blenlib/intern/smallhash.c
index 85c599d5bdb..7558ab686b7 100644
--- a/source/blender/blenlib/intern/smallhash.c
+++ b/source/blender/blenlib/intern/smallhash.c
@@ -192,8 +192,8 @@ BLI_INLINE SmallHashEntry *smallhash_lookup(SmallHash *sh, const uintptr_t key)
/* NOTE: there are always more buckets than entries,
* so we know there will always be a free bucket if the key isn't found. */
- for (e = &sh->buckets[h % sh->nbuckets]; e->val != SMHASH_CELL_FREE;
- h = SMHASH_NEXT(h, hoff), e = &sh->buckets[h % sh->nbuckets]) {
+ for (e = &sh->buckets[h % (uintptr_t)sh->nbuckets]; e->val != SMHASH_CELL_FREE;
+ h = SMHASH_NEXT(h, hoff), e = &sh->buckets[h % (uintptr_t)sh->nbuckets]) {
if (e->key == key) {
/* should never happen because unused keys are zero'd */
BLI_assert(e->val != SMHASH_CELL_UNUSED);
@@ -212,8 +212,8 @@ BLI_INLINE SmallHashEntry *smallhash_lookup_first_free(SmallHash *sh, const uint
uintptr_t h = smallhash_key(key);
uintptr_t hoff = 1;
- for (e = &sh->buckets[h % sh->nbuckets]; smallhash_val_is_used(e->val);
- h = SMHASH_NEXT(h, hoff), e = &sh->buckets[h % sh->nbuckets]) {
+ for (e = &sh->buckets[h % (uintptr_t)sh->nbuckets]; smallhash_val_is_used(e->val);
+ h = SMHASH_NEXT(h, hoff), e = &sh->buckets[h % (uintptr_t)sh->nbuckets]) {
/* pass */
}
@@ -321,8 +321,8 @@ bool BLI_smallhash_ensure_p(SmallHash *sh, uintptr_t key, void ***item)
/* NOTE: there are always more buckets than entries,
* so we know there will always be a free bucket if the key isn't found. */
- for (e = &sh->buckets[h % sh->nbuckets]; e->val != SMHASH_CELL_FREE;
- h = SMHASH_NEXT(h, hoff), e = &sh->buckets[h % sh->nbuckets]) {
+ for (e = &sh->buckets[h % (uintptr_t)sh->nbuckets]; e->val != SMHASH_CELL_FREE;
+ h = SMHASH_NEXT(h, hoff), e = &sh->buckets[h % (uintptr_t)sh->nbuckets]) {
if (e->key == key) {
/* should never happen because unused keys are zero'd */
BLI_assert(e->val != SMHASH_CELL_UNUSED);
@@ -334,7 +334,10 @@ bool BLI_smallhash_ensure_p(SmallHash *sh, uintptr_t key, void ***item)
if (e->val == SMHASH_CELL_FREE || e->val == SMHASH_CELL_UNUSED) {
sh->nentries++;
- sh->nfreecells--;
+
+ if (e->val == SMHASH_CELL_FREE) {
+ sh->nfreecells--;
+ }
ret = false;
e->val = NULL;
@@ -408,8 +411,8 @@ bool BLI_smallhash_remove(SmallHash *sh, uintptr_t key)
uintptr_t h = smallhash_key(key);
uintptr_t hoff = 1;
- for (e = &sh->buckets[h % sh->nbuckets]; e->val != SMHASH_CELL_FREE;
- h = SMHASH_NEXT(h, hoff), e = &sh->buckets[h % sh->nbuckets]) {
+ for (e = &sh->buckets[h % (uintptr_t)sh->nbuckets]; e->val != SMHASH_CELL_FREE;
+ h = SMHASH_NEXT(h, hoff), e = &sh->buckets[h % (uintptr_t)sh->nbuckets]) {
if (e->key == key) {
/* should never happen because unused keys are zero'd */
BLI_assert(e->val != SMHASH_CELL_UNUSED);
@@ -605,8 +608,8 @@ double BLI_smallhash_calc_quality(SmallHash *sh)
uintptr_t h = smallhash_key(e_final->key);
uintptr_t hoff = 1;
- for (e = &sh->buckets[h % sh->nbuckets]; e != e_final;
- h = SMHASH_NEXT(h, hoff), e = &sh->buckets[h % sh->nbuckets]) {
+ for (e = &sh->buckets[h % (uintptr_t)sh->nbuckets]; e != e_final;
+ h = SMHASH_NEXT(h, hoff), e = &sh->buckets[h % (uintptr_t)sh->nbuckets]) {
count += 1;
}
diff --git a/source/blender/bmesh/bmesh_class.h b/source/blender/bmesh/bmesh_class.h
index 5ae3f5716ce..fae428a6787 100644
--- a/source/blender/bmesh/bmesh_class.h
+++ b/source/blender/bmesh/bmesh_class.h
@@ -391,7 +391,7 @@ typedef struct BMesh {
/* maps ids to their position within the freelist
only used if freelist is bigger then a certain size,
see FREELIST_HASHMAP_THRESHOLD_HIGH in bmesh_construct.c.*/
- struct SmallHash *free_idx_map;
+ struct GHash *free_idx_map;
#else
struct RangeTreeUInt *idtree;
#endif
diff --git a/source/blender/bmesh/intern/bmesh_construct.c b/source/blender/bmesh/intern/bmesh_construct.c
index 1d974e267f2..4c303da39d2 100644
--- a/source/blender/bmesh/intern/bmesh_construct.c
+++ b/source/blender/bmesh/intern/bmesh_construct.c
@@ -55,17 +55,15 @@ static void bm_id_freelist_check_hashmap(BMesh *bm)
{
if (!bm->idmap.free_idx_map && bm->idmap.freelist_len >= FREELIST_HASHMAP_THRESHOLD_HIGH) {
printf("switching on freelist idx map\n");
- bm->idmap.free_idx_map = MEM_callocN(sizeof(SmallHash), "free_idx_map");
- BLI_smallhash_init_ex(bm->idmap.free_idx_map, bm->idmap.freelist_len);
+ bm->idmap.free_idx_map = BLI_ghash_ptr_new("free_idx_map");
for (int i = 0; i < bm->idmap.freelist_len; i++) {
- BLI_smallhash_insert(
- bm->idmap.free_idx_map, (uintptr_t)bm->idmap.freelist[i], POINTER_FROM_INT(i));
+ BLI_ghash_insert(
+ bm->idmap.free_idx_map, POINTER_FROM_UINT(bm->idmap.freelist[i]), POINTER_FROM_INT(i));
}
}
else if (bm->idmap.free_idx_map && bm->idmap.freelist_len <= FREELIST_HASHMAP_THRESHOLD_LOW) {
- BLI_smallhash_release(bm->idmap.free_idx_map);
- MEM_freeN(bm->idmap.free_idx_map);
+ BLI_ghash_free(bm->idmap.free_idx_map, NULL, NULL);
bm->idmap.free_idx_map = NULL;
printf("switching off freelist idx map\n");
@@ -81,7 +79,7 @@ static uint bm_id_freelist_pop(BMesh *bm)
uint id = bm->idmap.freelist[i];
if (bm->idmap.free_idx_map) {
- BLI_smallhash_remove(bm->idmap.free_idx_map, (uintptr_t) id);
+ BLI_ghash_remove(bm->idmap.free_idx_map, POINTER_FROM_UINT(id), NULL, NULL);
}
return id;
@@ -118,7 +116,7 @@ void bm_id_freelist_take(BMesh *bm, uint id)
BLI_BITMAP_DISABLE(bm->idmap.free_ids, id);
if (bm->idmap.free_idx_map) {
- void **val = BLI_smallhash_lookup_p(bm->idmap.free_idx_map, (uintptr_t)id);
+ void **val = BLI_ghash_lookup_p(bm->idmap.free_idx_map, POINTER_FROM_UINT(id));
if (val) {
int i = POINTER_AS_INT(*val);
@@ -128,7 +126,7 @@ void bm_id_freelist_take(BMesh *bm, uint id)
bm->idmap.freelist_len--;
}
- BLI_smallhash_remove(bm->idmap.free_idx_map, (uintptr_t)id);
+ BLI_ghash_remove(bm->idmap.free_idx_map, POINTER_FROM_UINT(id), NULL, NULL);
}
else {
for (int i = 0; i < bm->idmap.freelist_len; i++) {
@@ -176,7 +174,7 @@ void bm_id_freelist_push(BMesh *bm, uint id)
if (bm->idmap.free_idx_map) {
void **val;
- if (!BLI_smallhash_ensure_p(bm->idmap.free_idx_map, (uintptr_t)id, &val)) {
+ if (!BLI_ghash_ensure_p(bm->idmap.free_idx_map, POINTER_FROM_UINT(id), &val)) {
*val = POINTER_FROM_INT(bm->idmap.freelist_len - 1);
}
}
diff --git a/source/blender/bmesh/intern/bmesh_mesh.c b/source/blender/bmesh/intern/bmesh_mesh.c
index df8f6e328af..c84955c1f0a 100644
--- a/source/blender/bmesh/intern/bmesh_mesh.c
+++ b/source/blender/bmesh/intern/bmesh_mesh.c
@@ -286,8 +286,7 @@ void BM_mesh_data_free(BMesh *bm)
#ifdef WITH_BM_ID_FREELIST
if (bm->idmap.free_idx_map) {
- BLI_smallhash_release(bm->idmap.free_idx_map);
- MEM_freeN(bm->idmap.free_idx_map);
+ BLI_ghash_free(bm->idmap.free_idx_map, NULL, NULL);
bm->idmap.free_idx_map = NULL;
}
#endif
More information about the Bf-blender-cvs
mailing list