From bbce51d11691acc561f1684c20e60613941d4e9b Mon Sep 17 00:00:00 2001 From: Campbell Barton Date: Sun, 25 Aug 2013 20:03:45 +0000 Subject: replace hashes with sets where possible. --- source/blender/blenkernel/BKE_pbvh.h | 18 +-- source/blender/blenkernel/intern/cdderivedmesh.c | 2 +- source/blender/blenkernel/intern/mesh.c | 4 +- source/blender/blenkernel/intern/pbvh.c | 12 +- source/blender/blenkernel/intern/pbvh_bmesh.c | 147 ++++++++++++--------- source/blender/blenkernel/intern/pbvh_intern.h | 4 +- source/blender/blenkernel/intern/subsurf_ccg.c | 9 +- source/blender/blenlib/intern/edgehash.c | 4 - source/blender/blenloader/intern/readblenentry.c | 8 +- source/blender/bmesh/intern/bmesh_walkers.c | 12 +- source/blender/bmesh/intern/bmesh_walkers.h | 4 +- source/blender/bmesh/intern/bmesh_walkers_impl.c | 90 ++++++------- source/blender/bmesh/operators/bmo_beautify.c | 38 +++--- source/blender/bmesh/operators/bmo_hull.c | 36 ++--- .../bmesh/operators/bmo_subdivide_edgering.c | 34 ++--- source/blender/editors/animation/anim_filter.c | 9 +- source/blender/editors/sculpt_paint/paint_hide.c | 24 ++-- source/blender/gpu/GPU_buffers.h | 9 +- source/blender/gpu/intern/gpu_buffers.c | 35 ++--- 19 files changed, 260 insertions(+), 239 deletions(-) (limited to 'source') diff --git a/source/blender/blenkernel/BKE_pbvh.h b/source/blender/blenkernel/BKE_pbvh.h index 7d3d8d7dcbd..36806c8713c 100644 --- a/source/blender/blenkernel/BKE_pbvh.h +++ b/source/blender/blenkernel/BKE_pbvh.h @@ -172,8 +172,8 @@ int BKE_pbvh_node_planes_contain_AABB(PBVHNode *node, void *data); /* test if AABB is at least partially outside the planes' volume */ int BKE_pbvh_node_planes_exclude_AABB(PBVHNode *node, void *data); -struct GHash *BKE_pbvh_bmesh_node_unique_verts(PBVHNode *node); -struct GHash *BKE_pbvh_bmesh_node_other_verts(PBVHNode *node); +struct GSet *BKE_pbvh_bmesh_node_unique_verts(PBVHNode *node); +struct GSet *BKE_pbvh_bmesh_node_other_verts(PBVHNode *node); void BKE_pbvh_bmesh_node_save_orig(PBVHNode *node); void BKE_pbvh_bmesh_after_stroke(PBVH *bvh); @@ -235,8 +235,8 @@ typedef struct PBVHVertexIter { float *vmask; /* bmesh */ - struct GHashIterator bm_unique_verts; - struct GHashIterator bm_other_verts; + struct GSetIterator bm_unique_verts; + struct GSetIterator bm_other_verts; struct CustomData *bm_vdata; /* result: these are all computed in the macro, but we assume @@ -294,13 +294,13 @@ void pbvh_vertex_iter_init(PBVH *bvh, PBVHNode *node, vi.mask = &vi.vmask[vi.vert_indices[vi.gx]]; \ } \ else { \ - if (!BLI_ghashIterator_done(&vi.bm_unique_verts)) {\ - vi.bm_vert = BLI_ghashIterator_getKey(&vi.bm_unique_verts); \ - BLI_ghashIterator_step(&vi.bm_unique_verts); \ + if (!BLI_gsetIterator_done(&vi.bm_unique_verts)) {\ + vi.bm_vert = BLI_gsetIterator_getKey(&vi.bm_unique_verts); \ + BLI_gsetIterator_step(&vi.bm_unique_verts); \ } \ else { \ - vi.bm_vert = BLI_ghashIterator_getKey(&vi.bm_other_verts); \ - BLI_ghashIterator_step(&vi.bm_other_verts); \ + vi.bm_vert = BLI_gsetIterator_getKey(&vi.bm_other_verts); \ + BLI_gsetIterator_step(&vi.bm_other_verts); \ } \ if (mode == PBVH_ITER_UNIQUE && \ BM_elem_flag_test(vi.bm_vert, BM_ELEM_HIDDEN)) \ diff --git a/source/blender/blenkernel/intern/cdderivedmesh.c b/source/blender/blenkernel/intern/cdderivedmesh.c index 7678d82ee7c..1bc12cffe7b 100644 --- a/source/blender/blenkernel/intern/cdderivedmesh.c +++ b/source/blender/blenkernel/intern/cdderivedmesh.c @@ -2642,7 +2642,7 @@ void CDDM_calc_edges_tessface(DerivedMesh *dm) for (ehi = BLI_edgehashIterator_new(eh), i = 0; BLI_edgehashIterator_isDone(ehi) == FALSE; - BLI_edgehashIterator_step(ehi), ++i, ++med, ++index) + BLI_edgehashIterator_step(ehi), i++, med++, index++) { BLI_edgehashIterator_getKey(ehi, &med->v1, &med->v2); diff --git a/source/blender/blenkernel/intern/mesh.c b/source/blender/blenkernel/intern/mesh.c index e4c0adcc24e..571772f4322 100644 --- a/source/blender/blenkernel/intern/mesh.c +++ b/source/blender/blenkernel/intern/mesh.c @@ -3852,9 +3852,7 @@ void BKE_mesh_poly_edgehash_insert(EdgeHash *ehash, const MPoly *mp, const MLoop ml = &ml_next[i - 1]; /* last loop */ while (i-- != 0) { - if (!BLI_edgehash_haskey(ehash, ml->v, ml_next->v)) { - BLI_edgehash_insert(ehash, ml->v, ml_next->v, NULL); - } + BLI_edgehash_reinsert(ehash, ml->v, ml_next->v, NULL); ml = ml_next; ml_next++; diff --git a/source/blender/blenkernel/intern/pbvh.c b/source/blender/blenkernel/intern/pbvh.c index df227b6accb..73675267b79 100644 --- a/source/blender/blenkernel/intern/pbvh.c +++ b/source/blender/blenkernel/intern/pbvh.c @@ -614,9 +614,9 @@ void BKE_pbvh_free(PBVH *bvh) if (node->bm_faces) BLI_ghash_free(node->bm_faces, NULL, NULL); if (node->bm_unique_verts) - BLI_ghash_free(node->bm_unique_verts, NULL, NULL); + BLI_gset_free(node->bm_unique_verts, NULL); if (node->bm_other_verts) - BLI_ghash_free(node->bm_other_verts, NULL, NULL); + BLI_gset_free(node->bm_other_verts, NULL); } } @@ -1314,8 +1314,8 @@ void BKE_pbvh_node_num_verts(PBVH *bvh, PBVHNode *node, int *uniquevert, int *to if (uniquevert) *uniquevert = node->uniq_verts; break; case PBVH_BMESH: - tot = BLI_ghash_size(node->bm_unique_verts); - if (totvert) *totvert = tot + BLI_ghash_size(node->bm_other_verts); + tot = BLI_gset_size(node->bm_unique_verts); + if (totvert) *totvert = tot + BLI_gset_size(node->bm_other_verts); if (uniquevert) *uniquevert = tot; break; } @@ -1866,8 +1866,8 @@ void pbvh_vertex_iter_init(PBVH *bvh, PBVHNode *node, vi->mverts = verts; if (bvh->type == PBVH_BMESH) { - BLI_ghashIterator_init(&vi->bm_unique_verts, node->bm_unique_verts); - BLI_ghashIterator_init(&vi->bm_other_verts, node->bm_other_verts); + BLI_gsetIterator_init(&vi->bm_unique_verts, node->bm_unique_verts); + BLI_gsetIterator_init(&vi->bm_other_verts, node->bm_other_verts); vi->bm_vdata = &bvh->bm->vdata; } diff --git a/source/blender/blenkernel/intern/pbvh_bmesh.c b/source/blender/blenkernel/intern/pbvh_bmesh.c index 455ffd90ada..056aadc47fa 100644 --- a/source/blender/blenkernel/intern/pbvh_bmesh.c +++ b/source/blender/blenkernel/intern/pbvh_bmesh.c @@ -48,8 +48,8 @@ static void pbvh_bmesh_node_finalize(PBVH *bvh, int node_index) PBVHNode *n = &bvh->nodes[node_index]; /* Create vert hash sets */ - n->bm_unique_verts = BLI_ghash_ptr_new("bm_unique_verts"); - n->bm_other_verts = BLI_ghash_ptr_new("bm_other_verts"); + n->bm_unique_verts = BLI_gset_ptr_new("bm_unique_verts"); + n->bm_other_verts = BLI_gset_ptr_new("bm_other_verts"); BB_reset(&n->vb); @@ -67,13 +67,12 @@ static void pbvh_bmesh_node_finalize(PBVH *bvh, int node_index) l_iter = l_first = BM_FACE_FIRST_LOOP(f); do { v = l_iter->v; - if (!BLI_ghash_haskey(n->bm_unique_verts, v)) { + if (!BLI_gset_haskey(n->bm_unique_verts, v)) { if (BLI_ghash_haskey(bvh->bm_vert_to_node, v)) { - if (!BLI_ghash_haskey(n->bm_other_verts, v)) - BLI_ghash_insert(n->bm_other_verts, v, NULL); + BLI_gset_reinsert(n->bm_other_verts, v, NULL); } else { - BLI_ghash_insert(n->bm_unique_verts, v, NULL); + BLI_gset_insert(n->bm_unique_verts, v); BLI_ghash_insert(bvh->bm_vert_to_node, v, node_val); } } @@ -101,6 +100,7 @@ static void pbvh_bmesh_node_split(PBVH *bvh, GHash *prim_bbc, int node_index) { GHash *empty, *other; GHashIterator gh_iter; + GSetIterator gs_iter; PBVHNode *n, *c1, *c2; BB cb; float mid; @@ -177,11 +177,11 @@ static void pbvh_bmesh_node_split(PBVH *bvh, GHash *prim_bbc, int node_index) /* Mark this node's unique verts as unclaimed */ if (n->bm_unique_verts) { - GHASH_ITER (gh_iter, n->bm_unique_verts) { - BMVert *v = BLI_ghashIterator_getKey(&gh_iter); + GSET_ITER (gs_iter, n->bm_unique_verts) { + BMVert *v = BLI_gsetIterator_getKey(&gs_iter); BLI_ghash_remove(bvh->bm_vert_to_node, v, NULL, NULL); } - BLI_ghash_free(n->bm_unique_verts, NULL, NULL); + BLI_gset_free(n->bm_unique_verts, NULL); } /* Unclaim faces */ @@ -192,7 +192,7 @@ static void pbvh_bmesh_node_split(PBVH *bvh, GHash *prim_bbc, int node_index) BLI_ghash_free(n->bm_faces, NULL, NULL); if (n->bm_other_verts) - BLI_ghash_free(n->bm_other_verts, NULL, NULL); + BLI_gset_free(n->bm_other_verts, NULL); if (n->layer_disp) MEM_freeN(n->layer_disp); @@ -291,7 +291,7 @@ static BMVert *pbvh_bmesh_vert_create(PBVH *bvh, int node_index, BLI_assert((bvh->totnode == 1 || node_index) && node_index <= bvh->totnode); - BLI_ghash_insert(bvh->nodes[node_index].bm_unique_verts, v, NULL); + BLI_gset_insert(bvh->nodes[node_index].bm_unique_verts, v); BLI_ghash_insert(bvh->bm_vert_to_node, v, val); /* Log the new vertex */ @@ -373,14 +373,14 @@ static void pbvh_bmesh_vert_ownership_transfer(PBVH *bvh, PBVHNode *new_owner, BLI_assert(current_owner != new_owner); /* Remove current ownership */ - BLI_ghash_remove(current_owner->bm_unique_verts, v, NULL, NULL); + BLI_gset_remove(current_owner->bm_unique_verts, v, NULL); /* Set new ownership */ BLI_ghash_reinsert(bvh->bm_vert_to_node, v, - SET_INT_IN_POINTER(new_owner - bvh->nodes), NULL, NULL); - BLI_ghash_insert(new_owner->bm_unique_verts, v, NULL); - BLI_ghash_remove(new_owner->bm_other_verts, v, NULL, NULL); - BLI_assert(!BLI_ghash_haskey(new_owner->bm_other_verts, v)); + SET_INT_IN_POINTER(new_owner - bvh->nodes), NULL, NULL); + BLI_gset_insert(new_owner->bm_unique_verts, v); + BLI_gset_remove(new_owner->bm_other_verts, v, NULL); + BLI_assert(!BLI_gset_haskey(new_owner->bm_other_verts, v)); } static void pbvh_bmesh_vert_remove(PBVH *bvh, BMVert *v) @@ -391,7 +391,7 @@ static void pbvh_bmesh_vert_remove(PBVH *bvh, BMVert *v) BLI_assert(BLI_ghash_haskey(bvh->bm_vert_to_node, v)); v_node = pbvh_bmesh_node_lookup(bvh, bvh->bm_vert_to_node, v); - BLI_ghash_remove(v_node->bm_unique_verts, v, NULL, NULL); + BLI_gset_remove(v_node->bm_unique_verts, v, NULL); BLI_ghash_remove(bvh->bm_vert_to_node, v, NULL, NULL); /* Have to check each neighboring face's node */ @@ -401,10 +401,10 @@ static void pbvh_bmesh_vert_remove(PBVH *bvh, BMVert *v) /* Remove current ownership */ /* Should be handled above by vert_to_node removal, leaving just in case - psy-fi */ //BLI_ghash_remove(f_node->bm_unique_verts, v, NULL, NULL); - BLI_ghash_remove(f_node->bm_other_verts, v, NULL, NULL); + BLI_gset_remove(f_node->bm_other_verts, v, NULL); - BLI_assert(!BLI_ghash_haskey(f_node->bm_unique_verts, v)); - BLI_assert(!BLI_ghash_haskey(f_node->bm_other_verts, v)); + BLI_assert(!BLI_gset_haskey(f_node->bm_unique_verts, v)); + BLI_assert(!BLI_gset_haskey(f_node->bm_other_verts, v)); } } @@ -424,7 +424,7 @@ static void pbvh_bmesh_face_remove(PBVH *bvh, BMFace *f) do { v = l_iter->v; if (pbvh_bmesh_node_vert_use_count(bvh, f_node, v) == 1) { - if (BLI_ghash_haskey(f_node->bm_unique_verts, v)) { + if (BLI_gset_haskey(f_node->bm_unique_verts, v)) { /* Find a different node that uses 'v' */ PBVHNode *new_node; @@ -435,13 +435,13 @@ static void pbvh_bmesh_face_remove(PBVH *bvh, BMFace *f) pbvh_bmesh_vert_ownership_transfer(bvh, new_node, v); } else { - BLI_ghash_remove(f_node->bm_unique_verts, v, NULL, NULL); + BLI_gset_remove(f_node->bm_unique_verts, v, NULL); BLI_ghash_remove(bvh->bm_vert_to_node, v, NULL, NULL); } } else { /* Remove from other verts */ - BLI_ghash_remove(f_node->bm_other_verts, v, NULL, NULL); + BLI_gset_remove(f_node->bm_other_verts, v, NULL); } } } while ((l_iter = l_iter->next) != l_first); @@ -733,10 +733,10 @@ static void pbvh_bmesh_split_edge(PBVH *bvh, EdgeQueue *q, BLI_mempool *pool, BM_face_kill(bvh->bm, f_adj); /* Ensure new vertex is in the node */ - if (!BLI_ghash_haskey(bvh->nodes[ni].bm_unique_verts, v_new) && - !BLI_ghash_haskey(bvh->nodes[ni].bm_other_verts, v_new)) + if (!BLI_gset_haskey(bvh->nodes[ni].bm_unique_verts, v_new) && + !BLI_gset_haskey(bvh->nodes[ni].bm_other_verts, v_new)) { - BLI_ghash_insert(bvh->nodes[ni].bm_other_verts, v_new, NULL); + BLI_gset_insert(bvh->nodes[ni].bm_other_verts, v_new); } if (BM_vert_edge_count(v_opp) >= 9) { @@ -857,10 +857,10 @@ static void pbvh_bmesh_collapse_edge(PBVH *bvh, BMEdge *e, BMVert *v1, pbvh_bmesh_face_create(bvh, ni, v_tri, e_tri, f); /* Ensure that v1 is in the new face's node */ - if (!BLI_ghash_haskey(n->bm_unique_verts, v1) && - !BLI_ghash_haskey(n->bm_other_verts, v1)) + if (!BLI_gset_haskey(n->bm_unique_verts, v1) && + !BLI_gset_haskey(n->bm_other_verts, v1)) { - BLI_ghash_insert(n->bm_other_verts, v1, NULL); + BLI_gset_insert(n->bm_other_verts, v1); } } @@ -1033,16 +1033,17 @@ void pbvh_bmesh_normals_update(PBVHNode **nodes, int totnode) if (node->flag & PBVH_UpdateNormals) { GHashIterator gh_iter; + GSetIterator gs_iter; GHASH_ITER (gh_iter, node->bm_faces) { BM_face_normal_update(BLI_ghashIterator_getKey(&gh_iter)); } - GHASH_ITER (gh_iter, node->bm_unique_verts) { - BM_vert_normal_update(BLI_ghashIterator_getKey(&gh_iter)); + GSET_ITER (gs_iter, node->bm_unique_verts) { + BM_vert_normal_update(BLI_gsetIterator_getKey(&gs_iter)); } /* This should be unneeded normally */ - GHASH_ITER (gh_iter, node->bm_other_verts) { - BM_vert_normal_update(BLI_ghashIterator_getKey(&gh_iter)); + GSET_ITER (gs_iter, node->bm_other_verts) { + BM_vert_normal_update(BLI_gsetIterator_getKey(&gs_iter)); } node->flag &= ~PBVH_UpdateNormals; } @@ -1156,14 +1157,15 @@ BLI_INLINE void bm_face_as_array_index_tri(BMFace *f, int r_index[3]) void BKE_pbvh_bmesh_node_save_orig(PBVHNode *node) { GHashIterator gh_iter; + GSetIterator gs_iter; int i, totvert, tottri; /* Skip if original coords/triangles are already saved */ if (node->bm_orco) return; - totvert = (BLI_ghash_size(node->bm_unique_verts) + - BLI_ghash_size(node->bm_other_verts)); + totvert = (BLI_gset_size(node->bm_unique_verts) + + BLI_gset_size(node->bm_other_verts)); tottri = BLI_ghash_size(node->bm_faces); @@ -1172,14 +1174,14 @@ void BKE_pbvh_bmesh_node_save_orig(PBVHNode *node) /* Copy out the vertices and assign a temporary index */ i = 0; - GHASH_ITER (gh_iter, node->bm_unique_verts) { - BMVert *v = BLI_ghashIterator_getKey(&gh_iter); + GSET_ITER (gs_iter, node->bm_unique_verts) { + BMVert *v = BLI_gsetIterator_getKey(&gs_iter); copy_v3_v3(node->bm_orco[i], v->co); BM_elem_index_set(v, i); /* set_dirty! */ i++; } - GHASH_ITER (gh_iter, node->bm_other_verts) { - BMVert *v = BLI_ghashIterator_getKey(&gh_iter); + GSET_ITER (gs_iter, node->bm_other_verts) { + BMVert *v = BLI_gsetIterator_getKey(&gs_iter); copy_v3_v3(node->bm_orco[i], v->co); BM_elem_index_set(v, i); /* set_dirty! */ i++; @@ -1236,12 +1238,12 @@ void BKE_pbvh_node_mark_topology_update(PBVHNode *node) node->flag |= PBVH_UpdateTopology; } -GHash *BKE_pbvh_bmesh_node_unique_verts(PBVHNode *node) +GSet *BKE_pbvh_bmesh_node_unique_verts(PBVHNode *node) { return node->bm_unique_verts; } -GHash *BKE_pbvh_bmesh_node_other_verts(PBVHNode *node) +GSet *BKE_pbvh_bmesh_node_other_verts(PBVHNode *node) { return node->bm_other_verts; } @@ -1270,6 +1272,27 @@ void bli_ghash_duplicate_key_check(GHash *gh) } } +void bli_gset_duplicate_key_check(GSet *gs) +{ + GSetIterator gs_iter1, gs_iter2; + + GSET_ITER (gs_iter1, gs) { + void *key1 = BLI_gsetIterator_getKey(&gs_iter1); + int dup = -1; + + GSET_ITER (gs_iter2, gs) { + void *key2 = BLI_gsetIterator_getKey(&gs_iter2); + + if (key1 == key2) { + dup++; + if (dup > 0) { + BLI_assert(!"duplicate in hash"); + } + } + } + } +} + void bmesh_print(BMesh *bm) { BMIter iter, siter; @@ -1331,6 +1354,7 @@ void bmesh_print(BMesh *bm) void pbvh_bmesh_print(PBVH *bvh) { GHashIterator gh_iter; + GSetIterator gs_iter; int n; fprintf(stderr, "\npbvh=%p\n", bvh); @@ -1358,13 +1382,13 @@ void pbvh_bmesh_print(PBVH *bvh) fprintf(stderr, " %d\n", BM_elem_index_get((BMFace *)BLI_ghashIterator_getKey(&gh_iter))); fprintf(stderr, " unique verts:\n"); - GHASH_ITER (gh_iter, node->bm_unique_verts) + GSET_ITER (gs_iter, node->bm_unique_verts) fprintf(stderr, " %d\n", - BM_elem_index_get((BMVert *)BLI_ghashIterator_getKey(&gh_iter))); + BM_elem_index_get((BMVert *)BLI_gsetIterator_getKey(&gs_iter))); fprintf(stderr, " other verts:\n"); - GHASH_ITER (gh_iter, node->bm_other_verts) + GSET_ITER (gs_iter, node->bm_other_verts) fprintf(stderr, " %d\n", - BM_elem_index_get((BMVert *)BLI_ghashIterator_getKey(&gh_iter))); + BM_elem_index_get((BMVert *)BLI_gsetIterator_getKey(&gs_iter))); } } @@ -1382,6 +1406,7 @@ void print_flag_factors(int flag) void pbvh_bmesh_verify(PBVH *bvh) { GHashIterator gh_iter; + GSetIterator gs_iter; int i, vert_count = 0; BMIter iter; BMVert *vi; @@ -1407,17 +1432,17 @@ void pbvh_bmesh_verify(PBVH *bvh) PBVHNode *nv; /* Check that the vertex is in the node */ - BLI_assert(BLI_ghash_haskey(n->bm_unique_verts, v) ^ - BLI_ghash_haskey(n->bm_other_verts, v)); + BLI_assert(BLI_gset_haskey(n->bm_unique_verts, v) ^ + BLI_gset_haskey(n->bm_other_verts, v)); /* Check that the vertex has a node owner */ nv = pbvh_bmesh_node_lookup(bvh, bvh->bm_vert_to_node, v); /* Check that the vertex's node knows it owns the vert */ - BLI_assert(BLI_ghash_haskey(nv->bm_unique_verts, v)); + BLI_assert(BLI_gset_haskey(nv->bm_unique_verts, v)); /* Check that the vertex isn't duplicated as an 'other' vert */ - BLI_assert(!BLI_ghash_haskey(nv->bm_other_verts, v)); + BLI_assert(!BLI_gset_haskey(nv->bm_other_verts, v)); } } @@ -1436,10 +1461,10 @@ void pbvh_bmesh_verify(PBVH *bvh) BLI_assert(n->flag & PBVH_Leaf); /* Check that the vert's node knows it owns the vert */ - BLI_assert(BLI_ghash_haskey(n->bm_unique_verts, v)); + BLI_assert(BLI_gset_haskey(n->bm_unique_verts, v)); /* Check that the vertex isn't duplicated as an 'other' vert */ - BLI_assert(!BLI_ghash_haskey(n->bm_other_verts, v)); + BLI_assert(!BLI_gset_haskey(n->bm_other_verts, v)); /* Check that the vert's node also contains one of the vert's * adjacent faces */ @@ -1451,13 +1476,13 @@ void pbvh_bmesh_verify(PBVH *bvh) } BLI_assert(found); - #if 0 + #if 1 /* total freak stuff, check if node exists somewhere else */ /* Slow */ for (i = 0; i < bvh->totnode; i++) { PBVHNode *n = &bvh->nodes[i]; if (i != ni && n->bm_unique_verts) - BLI_assert(!BLI_ghash_haskey(n->bm_unique_verts, v)); + BLI_assert(!BLI_gset_haskey(n->bm_unique_verts, v)); } #endif @@ -1470,7 +1495,7 @@ void pbvh_bmesh_verify(PBVH *bvh) bool has_unique = false; for (i = 0; i < bvh->totnode; i++) { PBVHNode *n = &bvh->nodes[i]; - if ((n->bm_unique_verts != NULL) && BLI_ghash_haskey(n->bm_unique_verts, vi)) + if ((n->bm_unique_verts != NULL) && BLI_gset_haskey(n->bm_unique_verts, vi)) has_unique = true; } BLI_assert(has_unique); @@ -1489,8 +1514,8 @@ void pbvh_bmesh_verify(PBVH *bvh) /* Slow */ #if 0 bli_ghash_duplicate_key_check(n->bm_faces); - bli_ghash_duplicate_key_check(n->bm_unique_verts); - bli_ghash_duplicate_key_check(n->bm_other_verts); + bli_gset_duplicate_key_check(n->bm_unique_verts); + bli_gset_duplicate_key_check(n->bm_other_verts); #endif GHASH_ITER (gh_iter, n->bm_faces) { @@ -1500,16 +1525,16 @@ void pbvh_bmesh_verify(PBVH *bvh) BLI_assert(GET_INT_FROM_POINTER(nip) == (n - bvh->nodes)); } - GHASH_ITER (gh_iter, n->bm_unique_verts) { - BMVert *v = BLI_ghashIterator_getKey(&gh_iter); + GSET_ITER (gs_iter, n->bm_unique_verts) { + BMVert *v = BLI_gsetIterator_getKey(&gs_iter); void *nip = BLI_ghash_lookup(bvh->bm_vert_to_node, v); BLI_assert(BLI_ghash_haskey(bvh->bm_vert_to_node, v)); - BLI_assert(!BLI_ghash_haskey(n->bm_other_verts, v)); + BLI_assert(!BLI_gset_haskey(n->bm_other_verts, v)); BLI_assert(GET_INT_FROM_POINTER(nip) == (n - bvh->nodes)); } - GHASH_ITER (gh_iter, n->bm_other_verts) { - BMVert *v = BLI_ghashIterator_getKey(&gh_iter); + GSET_ITER (gs_iter, n->bm_other_verts) { + BMVert *v = BLI_gsetIterator_getKey(&gs_iter); BLI_assert(BLI_ghash_haskey(bvh->bm_vert_to_node, v)); BLI_assert(BM_vert_face_count(v) > 0); } diff --git a/source/blender/blenkernel/intern/pbvh_intern.h b/source/blender/blenkernel/intern/pbvh_intern.h index 4154b8e4799..9af1c1decf5 100644 --- a/source/blender/blenkernel/intern/pbvh_intern.h +++ b/source/blender/blenkernel/intern/pbvh_intern.h @@ -101,8 +101,8 @@ struct PBVHNode { /* Dyntopo */ GHash *bm_faces; - GHash *bm_unique_verts; - GHash *bm_other_verts; + GSet *bm_unique_verts; + GSet *bm_other_verts; float (*bm_orco)[3]; int (*bm_ortri)[3]; int bm_tot_ortri; diff --git a/source/blender/blenkernel/intern/subsurf_ccg.c b/source/blender/blenkernel/intern/subsurf_ccg.c index 21bcf328317..9c305801ae8 100644 --- a/source/blender/blenkernel/intern/subsurf_ccg.c +++ b/source/blender/blenkernel/intern/subsurf_ccg.c @@ -298,7 +298,7 @@ static int ss_sync_from_uv(CCGSubSurf *ss, CCGSubSurf *origss, DerivedMesh *dm, CCGVertHDL *fverts = NULL; BLI_array_declare(fverts); #endif - EdgeHash *ehash; + EdgeSet *eset; float creaseFactor = (float)ccgSubSurf_getSubdivisionLevels(ss); float uv[3] = {0.0f, 0.0f, 0.0f}; /* only first 2 values are written into */ @@ -334,7 +334,7 @@ static int ss_sync_from_uv(CCGSubSurf *ss, CCGSubSurf *origss, DerivedMesh *dm, } /* create edges */ - ehash = BLI_edgehash_new_ex(__func__, BLI_EDGEHASH_SIZE_GUESS_FROM_POLYS(totface)); + eset = BLI_edgeset_new_ex(__func__, BLI_EDGEHASH_SIZE_GUESS_FROM_POLYS(totface)); for (i = 0; i < totface; i++) { MPoly *mp = &((MPoly *) mpoly)[i]; @@ -359,7 +359,7 @@ static int ss_sync_from_uv(CCGSubSurf *ss, CCGSubSurf *origss, DerivedMesh *dm, MVert *mv0 = mvert + (ml[j_next].v); MVert *mv1 = mvert + (ml[j].v); - if (!BLI_edgehash_haskey(ehash, v0, v1)) { + if (BLI_edgeset_reinsert(eset, v0, v1)) { CCGEdge *e, *orige = ccgSubSurf_getFaceEdge(origf, j_next); CCGEdgeHDL ehdl = SET_INT_IN_POINTER(mp->loopstart + j_next); float crease; @@ -370,12 +370,11 @@ static int ss_sync_from_uv(CCGSubSurf *ss, CCGSubSurf *origss, DerivedMesh *dm, crease = ccgSubSurf_getEdgeCrease(orige); ccgSubSurf_syncEdge(ss, ehdl, fverts[j_next], fverts[j], crease, &e); - BLI_edgehash_insert(ehash, v0, v1, NULL); } } } - BLI_edgehash_free(ehash, NULL); + BLI_edgeset_free(eset); /* create faces */ for (i = 0; i < totface; i++) { diff --git a/source/blender/blenlib/intern/edgehash.c b/source/blender/blenlib/intern/edgehash.c index 33577bd3f91..e90b78620c4 100644 --- a/source/blender/blenlib/intern/edgehash.c +++ b/source/blender/blenlib/intern/edgehash.c @@ -437,8 +437,6 @@ bool BLI_edgehashIterator_isDone(EdgeHashIterator *ehi) /* Use edgehash API to give 'set' functionality */ -/** \name EdgeSet Functions - * \{ */ EdgeSet *BLI_edgeset_new_ex(const char *info, const unsigned int nentries_reserve) { @@ -500,5 +498,3 @@ void BLI_edgeset_free(EdgeSet *es) { BLI_edgehash_free((EdgeHash *)es, NULL); } - -/** \} */ diff --git a/source/blender/blenloader/intern/readblenentry.c b/source/blender/blenloader/intern/readblenentry.c index aec91dedf8f..9ae2858f526 100644 --- a/source/blender/blenloader/intern/readblenentry.c +++ b/source/blender/blenloader/intern/readblenentry.c @@ -222,7 +222,7 @@ LinkNode *BLO_blendhandle_get_previews(BlendHandle *bh, int ofblocktype, int *to LinkNode *BLO_blendhandle_get_linkable_groups(BlendHandle *bh) { FileData *fd = (FileData *) bh; - GHash *gathered = BLI_ghash_ptr_new("linkable_groups gh"); + GSet *gathered = BLI_gset_ptr_new("linkable_groups gh"); LinkNode *names = NULL; BHead *bhead; @@ -234,15 +234,15 @@ LinkNode *BLO_blendhandle_get_linkable_groups(BlendHandle *bh) if (BKE_idcode_is_linkable(bhead->code)) { const char *str = BKE_idcode_to_name(bhead->code); - if (!BLI_ghash_haskey(gathered, (void *)str)) { + if (!BLI_gset_haskey(gathered, (void *)str)) { BLI_linklist_prepend(&names, strdup(str)); - BLI_ghash_insert(gathered, (void *)str, NULL); + BLI_gset_insert(gathered, (void *)str); } } } } - BLI_ghash_free(gathered, NULL, NULL); + BLI_gset_free(gathered, NULL); return names; } diff --git a/source/blender/bmesh/intern/bmesh_walkers.c b/source/blender/bmesh/intern/bmesh_walkers.c index c9e36541db7..af901b3359c 100644 --- a/source/blender/bmesh/intern/bmesh_walkers.c +++ b/source/blender/bmesh/intern/bmesh_walkers.c @@ -87,8 +87,8 @@ void BMW_init(BMWalker *walker, BMesh *bm, int type, walker->mask_edge = mask_edge; walker->mask_face = mask_face; - walker->visithash = BLI_ghash_ptr_new("bmesh walkers"); - walker->secvisithash = BLI_ghash_ptr_new("bmesh walkers sec"); + walker->visit_set = BLI_gset_ptr_new("bmesh walkers"); + walker->visit_set_alt = BLI_gset_ptr_new("bmesh walkers sec"); if (UNLIKELY(type >= BMW_MAXWALKERS || type < 0)) { fprintf(stderr, @@ -127,8 +127,8 @@ void BMW_init(BMWalker *walker, BMesh *bm, int type, void BMW_end(BMWalker *walker) { BLI_mempool_destroy(walker->worklist); - BLI_ghash_free(walker->visithash, NULL, NULL); - BLI_ghash_free(walker->secvisithash, NULL, NULL); + BLI_gset_free(walker->visit_set, NULL); + BLI_gset_free(walker->visit_set_alt, NULL); } @@ -253,6 +253,6 @@ void BMW_reset(BMWalker *walker) BMW_state_remove(walker); } walker->depth = 0; - BLI_ghash_clear(walker->visithash, NULL, NULL); - BLI_ghash_clear(walker->secvisithash, NULL, NULL); + BLI_gset_clear(walker->visit_set, NULL); + BLI_gset_clear(walker->visit_set_alt, NULL); } diff --git a/source/blender/bmesh/intern/bmesh_walkers.h b/source/blender/bmesh/intern/bmesh_walkers.h index 8be362b5afa..ea1dbc61cc6 100644 --- a/source/blender/bmesh/intern/bmesh_walkers.h +++ b/source/blender/bmesh/intern/bmesh_walkers.h @@ -67,8 +67,8 @@ typedef struct BMWalker { BMWFlag flag; - GHash *visithash; - GHash *secvisithash; + GSet *visit_set; + GSet *visit_set_alt; int depth; } BMWalker; diff --git a/source/blender/bmesh/intern/bmesh_walkers_impl.c b/source/blender/bmesh/intern/bmesh_walkers_impl.c index 2fbda777dcc..a68d9ccd2bc 100644 --- a/source/blender/bmesh/intern/bmesh_walkers_impl.c +++ b/source/blender/bmesh/intern/bmesh_walkers_impl.c @@ -85,7 +85,7 @@ static void bmw_ShellWalker_visitEdge(BMWalker *walker, BMEdge *e) { BMwShellWalker *shellWalk = NULL; - if (BLI_ghash_haskey(walker->visithash, e)) { + if (BLI_gset_haskey(walker->visit_set, e)) { return; } @@ -95,7 +95,7 @@ static void bmw_ShellWalker_visitEdge(BMWalker *walker, BMEdge *e) shellWalk = BMW_state_add(walker); shellWalk->curedge = e; - BLI_ghash_insert(walker->visithash, e, NULL); + BLI_gset_insert(walker->visit_set, e); } static void bmw_ShellWalker_begin(BMWalker *walker, void *data) @@ -167,8 +167,8 @@ static void *bmw_ShellWalker_step(BMWalker *walker) bool restrictpass = true; BMwShellWalker shellWalk = *((BMwShellWalker *)BMW_current_state(walker)); - if (!BLI_ghash_haskey(walker->visithash, shellWalk.base)) { - BLI_ghash_insert(walker->visithash, shellWalk.base, NULL); + if (!BLI_gset_haskey(walker->visit_set, shellWalk.base)) { + BLI_gset_insert(walker->visit_set, shellWalk.base); } BMW_state_remove(walker); @@ -177,7 +177,7 @@ static void *bmw_ShellWalker_step(BMWalker *walker) /* find the next edge whose other vertex has not been visite */ curedge = shellWalk.curedge; do { - if (!BLI_ghash_haskey(walker->visithash, curedge)) { + if (!BLI_gset_haskey(walker->visit_set, curedge)) { if (!walker->restrictflag || (walker->restrictflag && BMO_elem_flag_test(walker->bm, curedge, walker->restrictflag))) { @@ -187,7 +187,7 @@ static void *bmw_ShellWalker_step(BMWalker *walker) /* push a new state onto the stac */ newState = BMW_state_add(walker); - BLI_ghash_insert(walker->visithash, curedge, NULL); + BLI_gset_insert(walker->visit_set, curedge); /* populate the new stat */ @@ -211,7 +211,7 @@ static void bmw_ConnectedVertexWalker_visitVertex(BMWalker *walker, BMVert *v) { BMwConnectedVertexWalker *vwalk; - if (BLI_ghash_haskey(walker->visithash, v)) { + if (BLI_gset_haskey(walker->visit_set, v)) { /* already visited */ return; } @@ -223,7 +223,7 @@ static void bmw_ConnectedVertexWalker_visitVertex(BMWalker *walker, BMVert *v) vwalk = BMW_state_add(walker); vwalk->curvert = v; - BLI_ghash_insert(walker->visithash, v, NULL); + BLI_gset_insert(walker->visit_set, v); } static void bmw_ConnectedVertexWalker_begin(BMWalker *walker, void *data) @@ -251,7 +251,7 @@ static void *bmw_ConnectedVertexWalker_step(BMWalker *walker) BM_ITER_ELEM (e, &iter, v, BM_EDGES_OF_VERT) { v2 = BM_edge_other_vert(e, v); - if (!BLI_ghash_haskey(walker->visithash, v2)) { + if (!BLI_gset_haskey(walker->visit_set, v2)) { bmw_ConnectedVertexWalker_visitVertex(walker, v2); } } @@ -276,7 +276,7 @@ static void bmw_IslandboundWalker_begin(BMWalker *walker, void *data) iwalk->base = iwalk->curloop = l; iwalk->lastv = l->v; - BLI_ghash_insert(walker->visithash, data, NULL); + BLI_gset_insert(walker->visit_set, data); } @@ -334,11 +334,11 @@ static void *bmw_IslandboundWalker_step(BMWalker *walker) if (l == owalk.curloop) { return NULL; } - else if (BLI_ghash_haskey(walker->visithash, l)) { + else if (BLI_gset_haskey(walker->visit_set, l)) { return owalk.curloop; } - BLI_ghash_insert(walker->visithash, l, NULL); + BLI_gset_insert(walker->visit_set, l); iwalk = BMW_state_add(walker); iwalk->base = owalk.base; @@ -367,7 +367,7 @@ static void bmw_IslandWalker_begin(BMWalker *walker, void *data) } iwalk = BMW_state_add(walker); - BLI_ghash_insert(walker->visithash, data, NULL); + BLI_gset_insert(walker->visit_set, data); iwalk->cur = data; } @@ -403,18 +403,18 @@ static void *bmw_IslandWalker_step(BMWalker *walker) continue; } - /* saves checking BLI_ghash_haskey below (manifold edges theres a 50% chance) */ + /* saves checking BLI_gset_haskey below (manifold edges theres a 50% chance) */ if (f == iwalk->cur) { continue; } - if (BLI_ghash_haskey(walker->visithash, f)) { + if (BLI_gset_haskey(walker->visit_set, f)) { continue; } iwalk = BMW_state_add(walker); iwalk->cur = f; - BLI_ghash_insert(walker->visithash, f, NULL); + BLI_gset_insert(walker->visit_set, f); break; } } @@ -448,7 +448,7 @@ static void bmw_LoopWalker_begin(BMWalker *walker, void *data) v = e->v1; lwalk = BMW_state_add(walker); - BLI_ghash_insert(walker->visithash, e, NULL); + BLI_gset_insert(walker->visit_set, e); lwalk->cur = lwalk->start = e; lwalk->lastv = lwalk->startv = v; @@ -494,8 +494,8 @@ static void bmw_LoopWalker_begin(BMWalker *walker, void *data) lwalk->lastv = lwalk->startv = BM_edge_other_vert(owalk.cur, lwalk->lastv); - BLI_ghash_clear(walker->visithash, NULL, NULL); - BLI_ghash_insert(walker->visithash, owalk.cur, NULL); + BLI_gset_clear(walker->visit_set, NULL); + BLI_gset_insert(walker->visit_set, owalk.cur); } static void *bmw_LoopWalker_yield(BMWalker *walker) @@ -530,7 +530,7 @@ static void *bmw_LoopWalker_step(BMWalker *walker) nexte = BM_edge_exists(v, l->v); if (bmw_mask_check_edge(walker, nexte) && - !BLI_ghash_haskey(walker->visithash, nexte) && + !BLI_gset_haskey(walker->visit_set, nexte) && /* never step onto a boundary edge, this gives odd-results */ (BM_edge_is_boundary(nexte) == false)) { @@ -542,7 +542,7 @@ static void *bmw_LoopWalker_step(BMWalker *walker) lwalk->is_single = owalk.is_single; lwalk->f_hub = owalk.f_hub; - BLI_ghash_insert(walker->visithash, nexte, NULL); + BLI_gset_insert(walker->visit_set, nexte); } } } @@ -556,7 +556,7 @@ static void *bmw_LoopWalker_step(BMWalker *walker) BM_ITER_ELEM (nexte, &eiter, v, BM_EDGES_OF_VERT) { if ((nexte->l == NULL) && bmw_mask_check_edge(walker, nexte) && - !BLI_ghash_haskey(walker->visithash, nexte)) + !BLI_gset_haskey(walker->visit_set, nexte)) { lwalk = BMW_state_add(walker); lwalk->cur = nexte; @@ -566,7 +566,7 @@ static void *bmw_LoopWalker_step(BMWalker *walker) lwalk->is_single = owalk.is_single; lwalk->f_hub = owalk.f_hub; - BLI_ghash_insert(walker->visithash, nexte, NULL); + BLI_gset_insert(walker->visit_set, nexte); } } } @@ -601,7 +601,7 @@ static void *bmw_LoopWalker_step(BMWalker *walker) if (l != NULL) { if (l != e->l && bmw_mask_check_edge(walker, l->e) && - !BLI_ghash_haskey(walker->visithash, l->e)) + !BLI_gset_haskey(walker->visit_set, l->e)) { lwalk = BMW_state_add(walker); lwalk->cur = l->e; @@ -611,7 +611,7 @@ static void *bmw_LoopWalker_step(BMWalker *walker) lwalk->is_single = owalk.is_single; lwalk->f_hub = owalk.f_hub; - BLI_ghash_insert(walker->visithash, l->e, NULL); + BLI_gset_insert(walker->visit_set, l->e); } } } @@ -654,7 +654,7 @@ static void *bmw_LoopWalker_step(BMWalker *walker) if (l != NULL) { if (l != e->l && bmw_mask_check_edge(walker, l->e) && - !BLI_ghash_haskey(walker->visithash, l->e)) + !BLI_gset_haskey(walker->visit_set, l->e)) { lwalk = BMW_state_add(walker); lwalk->cur = l->e; @@ -664,7 +664,7 @@ static void *bmw_LoopWalker_step(BMWalker *walker) lwalk->is_single = owalk.is_single; lwalk->f_hub = owalk.f_hub; - BLI_ghash_insert(walker->visithash, l->e, NULL); + BLI_gset_insert(walker->visit_set, l->e); } } } @@ -694,7 +694,7 @@ static bool bmw_FaceLoopWalker_include_face(BMWalker *walker, BMLoop *l) } /* the face must not have been already visited */ - if (BLI_ghash_haskey(walker->visithash, l->f) && BLI_ghash_haskey(walker->secvisithash, l->e)) { + if (BLI_gset_haskey(walker->visit_set, l->f) && BLI_gset_haskey(walker->visit_set_alt, l->e)) { return false; } @@ -738,7 +738,7 @@ static void bmw_FaceLoopWalker_begin(BMWalker *walker, void *data) lwalk = BMW_state_add(walker); lwalk->l = e->l; lwalk->no_calc = false; - BLI_ghash_insert(walker->visithash, lwalk->l->f, NULL); + BLI_gset_insert(walker->visit_set, lwalk->l->f); /* rewind */ while ((owalk_pt = BMW_current_state(walker))) { @@ -750,11 +750,11 @@ static void bmw_FaceLoopWalker_begin(BMWalker *walker, void *data) *lwalk = owalk; lwalk->no_calc = false; - BLI_ghash_clear(walker->secvisithash, NULL, NULL); - BLI_ghash_insert(walker->secvisithash, lwalk->l->e, NULL); + BLI_gset_clear(walker->visit_set_alt, NULL); + BLI_gset_insert(walker->visit_set_alt, lwalk->l->e); - BLI_ghash_clear(walker->visithash, NULL, NULL); - BLI_ghash_insert(walker->visithash, lwalk->l->f, NULL); + BLI_gset_clear(walker->visit_set, NULL); + BLI_gset_insert(walker->visit_set, lwalk->l->f); } static void *bmw_FaceLoopWalker_yield(BMWalker *walker) @@ -804,8 +804,8 @@ static void *bmw_FaceLoopWalker_step(BMWalker *walker) } /* both may already exist */ - BLI_ghash_reinsert(walker->secvisithash, l->e, NULL, NULL, NULL); - BLI_ghash_reinsert(walker->visithash, l->f, NULL, NULL, NULL); + BLI_gset_reinsert(walker->visit_set_alt, l->e, NULL); + BLI_gset_reinsert(walker->visit_set, l->f, NULL); } return f; @@ -836,7 +836,7 @@ static void bmw_EdgeringWalker_begin(BMWalker *walker, void *data) lwalk->wireedge = NULL; } - BLI_ghash_insert(walker->visithash, lwalk->l->e, NULL); + BLI_gset_insert(walker->visit_set, lwalk->l->e); /* rewind */ while ((owalk_pt = BMW_current_state(walker))) { @@ -856,8 +856,8 @@ static void bmw_EdgeringWalker_begin(BMWalker *walker, void *data) lwalk->l = lwalk->l->radial_next; } - BLI_ghash_clear(walker->visithash, NULL, NULL); - BLI_ghash_insert(walker->visithash, lwalk->l->e, NULL); + BLI_gset_clear(walker->visit_set, NULL); + BLI_gset_insert(walker->visit_set, lwalk->l->e); } static void *bmw_EdgeringWalker_yield(BMWalker *walker) @@ -922,7 +922,7 @@ static void *bmw_EdgeringWalker_step(BMWalker *walker) } /* only walk to manifold edge */ if ((l->f->len % 2 == 0) && EDGE_CHECK(l->e) && - !BLI_ghash_haskey(walker->visithash, l->e)) + !BLI_gset_haskey(walker->visit_set, l->e)) #else @@ -934,14 +934,14 @@ static void *bmw_EdgeringWalker_step(BMWalker *walker) } /* only walk to manifold edge */ if ((l->f->len == 4) && EDGE_CHECK(l->e) && - !BLI_ghash_haskey(walker->visithash, l->e)) + !BLI_gset_haskey(walker->visit_set, l->e)) #endif { lwalk = BMW_state_add(walker); lwalk->l = l; lwalk->wireedge = NULL; - BLI_ghash_insert(walker->visithash, l->e, NULL); + BLI_gset_insert(walker->visit_set, l->e); } return e; @@ -954,12 +954,12 @@ static void bmw_UVEdgeWalker_begin(BMWalker *walker, void *data) BMwUVEdgeWalker *lwalk; BMLoop *l = data; - if (BLI_ghash_haskey(walker->visithash, l)) + if (BLI_gset_haskey(walker->visit_set, l)) return; lwalk = BMW_state_add(walker); lwalk->l = l; - BLI_ghash_insert(walker->visithash, l, NULL); + BLI_gset_insert(walker->visit_set, l); } static void *bmw_UVEdgeWalker_yield(BMWalker *walker) @@ -1001,7 +1001,7 @@ static void *bmw_UVEdgeWalker_step(BMWalker *walker) rlen = BM_edge_face_count(l2->e); for (j = 0; j < rlen; j++) { - if (BLI_ghash_haskey(walker->visithash, l2)) { + if (BLI_gset_haskey(walker->visit_set, l2)) { continue; } @@ -1019,7 +1019,7 @@ static void *bmw_UVEdgeWalker_step(BMWalker *walker) continue; lwalk = BMW_state_add(walker); - BLI_ghash_insert(walker->visithash, l2, NULL); + BLI_gset_insert(walker->visit_set, l2); lwalk->l = l2; diff --git a/source/blender/bmesh/operators/bmo_beautify.c b/source/blender/bmesh/operators/bmo_beautify.c index 22b686db64e..3dbdb3ddc52 100644 --- a/source/blender/bmesh/operators/bmo_beautify.c +++ b/source/blender/bmesh/operators/bmo_beautify.c @@ -28,7 +28,7 @@ * * In principle this is very simple however there is the possibility of * going into an eternal loop where edges keep rotating. - * To avoid this - each edge stores a hash of it previous + * To avoid this - each edge stores a set of it previous * states so as not to rotate back. * * TODO @@ -54,14 +54,14 @@ enum { }; /* -------------------------------------------------------------------- */ -/* GHash for edge rotation */ +/* GSet for edge rotation */ typedef struct EdRotState { int v1, v2; /* edge vert, small -> large */ int f1, f2; /* face vert, small -> large */ } EdRotState; -static unsigned int erot_ghashutil_hash(const void *ptr) +static unsigned int erot_gsetutil_hash(const void *ptr) { const EdRotState *e_state = (const EdRotState *)ptr; unsigned int @@ -71,7 +71,7 @@ static unsigned int erot_ghashutil_hash(const void *ptr) hash ^= BLI_ghashutil_inthash(SET_INT_IN_POINTER(e_state->f2)); return hash; } -static int erot_ghashutil_cmp(const void *a, const void *b) +static int erot_gsetutil_cmp(const void *a, const void *b) { const EdRotState *e_state_a = (const EdRotState *)a; const EdRotState *e_state_b = (const EdRotState *)b; @@ -86,9 +86,9 @@ static int erot_ghashutil_cmp(const void *a, const void *b) else return 0; } -static GHash *erot_ghash_new(void) +static GSet *erot_gset_new(void) { - return BLI_ghash_new(erot_ghashutil_hash, erot_ghashutil_cmp, __func__); + return BLI_gset_new(erot_gsetutil_hash, erot_gsetutil_cmp, __func__); } /* ensure v0 is smaller */ @@ -236,12 +236,12 @@ static float bm_edge_calc_rotate_beauty(const BMEdge *e, const int flag) /* Update the edge cost of rotation in the heap */ /* recalc an edge in the heap (surrounding geometry has changed) */ -static void bm_edge_update_beauty_cost_single(BMEdge *e, Heap *eheap, HeapNode **eheap_table, GHash **edge_state_arr, +static void bm_edge_update_beauty_cost_single(BMEdge *e, Heap *eheap, HeapNode **eheap_table, GSet **edge_state_arr, const int flag) { if (BM_elem_flag_test(e, BM_ELEM_TAG)) { const int i = BM_elem_index_get(e); - GHash *e_state_hash = edge_state_arr[i]; + GSet *e_state_set = edge_state_arr[i]; if (eheap_table[i]) { BLI_heap_remove(eheap, eheap_table[i]); @@ -254,10 +254,10 @@ static void bm_edge_update_beauty_cost_single(BMEdge *e, Heap *eheap, HeapNode * // BMO_elem_flag_test(bm, e->l->radial_next->f, FACE_MARK)); /* check we're not moving back into a state we have been in before */ - if (e_state_hash != NULL) { + if (e_state_set != NULL) { EdRotState e_state_alt; erot_state_alternate(e, &e_state_alt); - if (BLI_ghash_haskey(e_state_hash, (void *)&e_state_alt)) { + if (BLI_gset_haskey(e_state_set, (void *)&e_state_alt)) { // printf(" skipping, we already have this state\n"); return; } @@ -277,7 +277,7 @@ static void bm_edge_update_beauty_cost_single(BMEdge *e, Heap *eheap, HeapNode * } /* we have rotated an edge, tag other edges and clear this one */ -static void bm_edge_update_beauty_cost(BMEdge *e, Heap *eheap, HeapNode **eheap_table, GHash **edge_state_arr, +static void bm_edge_update_beauty_cost(BMEdge *e, Heap *eheap, HeapNode **eheap_table, GSet **edge_state_arr, const int flag) { BMLoop *l; @@ -308,7 +308,7 @@ static void bm_mesh_beautify_fill(BMesh *bm, BMEdge **edge_array, const int edge Heap *eheap; /* edge heap */ HeapNode **eheap_table; /* edge index aligned table pointing to the eheap */ - GHash **edge_state_arr = MEM_callocN(edge_array_len * sizeof(GHash *), __func__); + GSet **edge_state_arr = MEM_callocN(edge_array_len * sizeof(GSet *), __func__); BLI_mempool *edge_state_pool = BLI_mempool_create(sizeof(EdRotState), 512, 512, BLI_MEMPOOL_SYSMALLOC); int i; @@ -338,18 +338,18 @@ static void bm_mesh_beautify_fill(BMesh *bm, BMEdge **edge_array, const int edge e = BM_edge_rotate(bm, e, false, BM_EDGEROT_CHECK_EXISTS); if (LIKELY(e)) { - GHash *e_state_hash = edge_state_arr[i]; + GSet *e_state_set = edge_state_arr[i]; - /* add the new state into the hash so we don't move into this state again + /* add the new state into the set so we don't move into this state again * note: we could add the previous state too but this isn't essential) * for avoiding eternal loops */ EdRotState *e_state = BLI_mempool_alloc(edge_state_pool); erot_state_current(e, e_state); - if (UNLIKELY(e_state_hash == NULL)) { - edge_state_arr[i] = e_state_hash = erot_ghash_new(); /* store previous state */ + if (UNLIKELY(e_state_set == NULL)) { + edge_state_arr[i] = e_state_set = erot_gset_new(); /* store previous state */ } - BLI_assert(BLI_ghash_haskey(e_state_hash, (void *)e_state) == false); - BLI_ghash_insert(e_state_hash, e_state, NULL); + BLI_assert(BLI_gset_haskey(e_state_set, (void *)e_state) == false); + BLI_gset_insert(e_state_set, e_state); // printf(" %d -> %d, %d\n", i, BM_elem_index_get(e->v1), BM_elem_index_get(e->v2)); @@ -373,7 +373,7 @@ static void bm_mesh_beautify_fill(BMesh *bm, BMEdge **edge_array, const int edge for (i = 0; i < edge_array_len; i++) { if (edge_state_arr[i]) { - BLI_ghash_free(edge_state_arr[i], NULL, NULL); + BLI_gset_free(edge_state_arr[i], NULL); } } diff --git a/source/blender/bmesh/operators/bmo_hull.c b/source/blender/bmesh/operators/bmo_hull.c index 9ba08f0a470..f0ec45b624f 100644 --- a/source/blender/bmesh/operators/bmo_hull.c +++ b/source/blender/bmesh/operators/bmo_hull.c @@ -67,7 +67,7 @@ typedef struct HullTriangle { /*************************** Hull Triangles ***************************/ -static void hull_add_triangle(BMesh *bm, GHash *hull_triangles, BLI_mempool *pool, +static void hull_add_triangle(BMesh *bm, GSet *hull_triangles, BLI_mempool *pool, BMVert *v1, BMVert *v2, BMVert *v3) { HullTriangle *t; @@ -82,7 +82,7 @@ static void hull_add_triangle(BMesh *bm, GHash *hull_triangles, BLI_mempool *poo for (i = 0; i < 3; i++) BMO_elem_flag_disable(bm, t->v[i], HULL_FLAG_INTERIOR_ELE); - BLI_ghash_insert(hull_triangles, t, NULL); + BLI_gset_insert(hull_triangles, t); normal_tri_v3(t->no, v1->co, v2->co, v3->co); } @@ -102,12 +102,12 @@ static BMFace *hull_find_example_face(BMesh *bm, BMEdge *e) return NULL; } -static void hull_output_triangles(BMesh *bm, GHash *hull_triangles) +static void hull_output_triangles(BMesh *bm, GSet *hull_triangles) { - GHashIterator iter; + GSetIterator iter; - GHASH_ITER (iter, hull_triangles) { - HullTriangle *t = BLI_ghashIterator_getKey(&iter); + GSET_ITER (iter, hull_triangles) { + HullTriangle *t = BLI_gsetIterator_getKey(&iter); int i; if (!t->skip) { @@ -206,22 +206,22 @@ static int hull_final_edges_lookup(HullFinalEdges *final_edges, } /* Used for checking whether a pre-existing edge lies on the hull */ -static HullFinalEdges *hull_final_edges(GHash *hull_triangles) +static HullFinalEdges *hull_final_edges(GSet *hull_triangles) { HullFinalEdges *final_edges; - GHashIterator iter; + GSetIterator iter; final_edges = MEM_callocN(sizeof(HullFinalEdges), "HullFinalEdges"); final_edges->edges = BLI_ghash_ptr_new("final edges ghash"); final_edges->base_pool = BLI_mempool_create(sizeof(ListBase), 128, 128, 0); final_edges->link_pool = BLI_mempool_create(sizeof(LinkData), 128, 128, 0); - GHASH_ITER (iter, hull_triangles) { + GSET_ITER (iter, hull_triangles) { LinkData *link; int i; for (i = 0; i < 3; i++) { - HullTriangle *t = BLI_ghashIterator_getKey(&iter); + HullTriangle *t = BLI_gsetIterator_getKey(&iter); BMVert *v1 = t->v[i]; BMVert *v2 = t->v[(i + 1) % 3]; ListBase *adj; @@ -259,13 +259,13 @@ static void hull_final_edges_free(HullFinalEdges *final_edges) /**************************** Final Output ****************************/ -static void hull_remove_overlapping(BMesh *bm, GHash *hull_triangles, +static void hull_remove_overlapping(BMesh *bm, GSet *hull_triangles, HullFinalEdges *final_edges) { - GHashIterator hull_iter; + GSetIterator hull_iter; - GHASH_ITER (hull_iter, hull_triangles) { - HullTriangle *t = BLI_ghashIterator_getKey(&hull_iter); + GSET_ITER (hull_iter, hull_triangles) { + HullTriangle *t = BLI_gsetIterator_getKey(&hull_iter); BMIter bm_iter1, bm_iter2; BMFace *f; bool f_on_hull; @@ -479,7 +479,7 @@ static BMVert **hull_verts_from_bullet(plConvexHull hull, } static void hull_from_bullet(BMesh *bm, BMOperator *op, - GHash *hull_triangles, + GSet *hull_triangles, BLI_mempool *pool) { int *fvi = NULL; @@ -556,7 +556,7 @@ void bmo_convex_hull_exec(BMesh *bm, BMOperator *op) BLI_mempool *hull_pool; BMElemF *ele; BMOIter oiter; - GHash *hull_triangles; + GSet *hull_triangles; /* Verify that at least three verts in the input */ if (!hull_num_input_verts_is_ok(op)) { @@ -575,7 +575,7 @@ void bmo_convex_hull_exec(BMesh *bm, BMOperator *op) } hull_pool = BLI_mempool_create(sizeof(HullTriangle), 128, 128, 0); - hull_triangles = BLI_ghash_ptr_new("hull_triangles"); + hull_triangles = BLI_gset_ptr_new("hull_triangles"); hull_from_bullet(bm, op, hull_triangles, hull_pool); @@ -597,7 +597,7 @@ void bmo_convex_hull_exec(BMesh *bm, BMOperator *op) hull_output_triangles(bm, hull_triangles); BLI_mempool_destroy(hull_pool); - BLI_ghash_free(hull_triangles, NULL, NULL); + BLI_gset_free(hull_triangles, NULL); hull_tag_unused(bm, op); diff --git a/source/blender/bmesh/operators/bmo_subdivide_edgering.c b/source/blender/bmesh/operators/bmo_subdivide_edgering.c index fa39ae68cdf..d9d87d0db78 100644 --- a/source/blender/bmesh/operators/bmo_subdivide_edgering.c +++ b/source/blender/bmesh/operators/bmo_subdivide_edgering.c @@ -203,7 +203,7 @@ finally: /* -------------------------------------------------------------------- */ /* Edge Loop Pairs */ /* key (ordered loop pointers) */ -static GHash *bm_edgering_pair_calc(BMesh *bm, ListBase *eloops_rim) +static GSet *bm_edgering_pair_calc(BMesh *bm, ListBase *eloops_rim) { /** * Method for for finding pairs: @@ -219,7 +219,7 @@ static GHash *bm_edgering_pair_calc(BMesh *bm, ListBase *eloops_rim) * could sort and optimize this but not really so important. */ - GHash *eloop_pair_gh = BLI_ghash_pair_new(__func__); + GSet *eloop_pair_gs = BLI_gset_pair_new(__func__); GHash *vert_eloop_gh = BLI_ghash_ptr_new(__func__); struct BMEdgeLoopStore *el_store; @@ -256,9 +256,9 @@ static GHash *bm_edgering_pair_calc(BMesh *bm, ListBase *eloops_rim) if (pair_test.first > pair_test.second) SWAP(const void *, pair_test.first, pair_test.second); - if (!BLI_ghash_haskey(eloop_pair_gh, &pair_test)) { + if (!BLI_gset_haskey(eloop_pair_gs, &pair_test)) { GHashPair *pair = BLI_ghashutil_pairalloc(pair_test.first, pair_test.second); - BLI_ghash_insert(eloop_pair_gh, pair, NULL); + BLI_gset_insert(eloop_pair_gs, pair); } } @@ -268,12 +268,12 @@ static GHash *bm_edgering_pair_calc(BMesh *bm, ListBase *eloops_rim) BLI_ghash_free(vert_eloop_gh, NULL, NULL); - if (BLI_ghash_size(eloop_pair_gh) == 0) { - BLI_ghash_free(eloop_pair_gh, NULL, NULL); - eloop_pair_gh = NULL; + if (BLI_gset_size(eloop_pair_gs) == 0) { + BLI_gset_free(eloop_pair_gs, NULL); + eloop_pair_gs = NULL; } - return eloop_pair_gh; + return eloop_pair_gs; } @@ -1175,23 +1175,23 @@ void bmo_subdivide_edgering_exec(BMesh *bm, BMOperator *op) } } else { - GHashIterator gh_iter; + GSetIterator gs_iter; int i; - GHash *eloop_pairs_gh = bm_edgering_pair_calc(bm, &eloops_rim); + GSet *eloop_pairs_gs = bm_edgering_pair_calc(bm, &eloops_rim); LoopPairStore **lpair_arr; - if (eloop_pairs_gh == NULL) { + if (eloop_pairs_gs == NULL) { BMO_error_raise(bm, op, BMERR_INVALID_SELECTION, "Edge-rings are not connected"); goto cleanup; } - lpair_arr = BLI_array_alloca(lpair_arr, BLI_ghash_size(eloop_pairs_gh)); + lpair_arr = BLI_array_alloca(lpair_arr, BLI_gset_size(eloop_pairs_gs)); /* first cache pairs */ - GHASH_ITER_INDEX (gh_iter, eloop_pairs_gh, i) { - GHashPair *eloop_pair = BLI_ghashIterator_getKey(&gh_iter); + GSET_ITER_INDEX (gs_iter, eloop_pairs_gs, i) { + GHashPair *eloop_pair = BLI_gsetIterator_getKey(&gs_iter); struct BMEdgeLoopStore *el_store_a = (void *)eloop_pair->first; struct BMEdgeLoopStore *el_store_b = (void *)eloop_pair->second; LoopPairStore *lpair; @@ -1207,8 +1207,8 @@ void bmo_subdivide_edgering_exec(BMesh *bm, BMOperator *op) BLI_assert(bm_verts_tag_count(bm) == 0); } - GHASH_ITER_INDEX (gh_iter, eloop_pairs_gh, i) { - GHashPair *eloop_pair = BLI_ghashIterator_getKey(&gh_iter); + GSET_ITER_INDEX (gs_iter, eloop_pairs_gs, i) { + GHashPair *eloop_pair = BLI_gsetIterator_getKey(&gs_iter); struct BMEdgeLoopStore *el_store_a = (void *)eloop_pair->first; struct BMEdgeLoopStore *el_store_b = (void *)eloop_pair->second; LoopPairStore *lpair = lpair_arr[i]; @@ -1222,7 +1222,7 @@ void bmo_subdivide_edgering_exec(BMesh *bm, BMOperator *op) BLI_assert(bm_verts_tag_count(bm) == 0); } - BLI_ghash_free(eloop_pairs_gh, MEM_freeN, NULL); + BLI_gset_free(eloop_pairs_gs, MEM_freeN); } cleanup: diff --git a/source/blender/editors/animation/anim_filter.c b/source/blender/editors/animation/anim_filter.c index 91003674524..14974cd070f 100644 --- a/source/blender/editors/animation/anim_filter.c +++ b/source/blender/editors/animation/anim_filter.c @@ -2533,13 +2533,13 @@ static size_t animdata_filter_remove_invalid(ListBase *anim_data) static size_t animdata_filter_remove_duplis(ListBase *anim_data) { bAnimListElem *ale, *next; - GHash *gh; + GSet *gs; size_t items = 0; /* build new hashtable to efficiently store and retrieve which entries have been * encountered already while searching */ - gh = BLI_ghash_ptr_new("animdata_filter_duplis_remove gh"); + gs = BLI_gset_ptr_new(__func__); /* loop through items, removing them from the list if a similar item occurs already */ for (ale = anim_data->first; ale; ale = next) { @@ -2549,9 +2549,8 @@ static size_t animdata_filter_remove_duplis(ListBase *anim_data) * - just use ale->data for now, though it would be nicer to involve * ale->type in combination too to capture corner cases (where same data performs differently) */ - if (BLI_ghash_haskey(gh, ale->data) == 0) { + if (BLI_gset_reinsert(gs, ale->data, NULL)) { /* this entry is 'unique' and can be kept */ - BLI_ghash_insert(gh, ale->data, NULL); items++; } else { @@ -2561,7 +2560,7 @@ static size_t animdata_filter_remove_duplis(ListBase *anim_data) } /* free the hash... */ - BLI_ghash_free(gh, NULL, NULL); + BLI_gset_free(gs, NULL); /* return the number of items still in the list */ return items; diff --git a/source/blender/editors/sculpt_paint/paint_hide.c b/source/blender/editors/sculpt_paint/paint_hide.c index fc31aacffcf..345db7a0ed0 100644 --- a/source/blender/editors/sculpt_paint/paint_hide.c +++ b/source/blender/editors/sculpt_paint/paint_hide.c @@ -223,20 +223,20 @@ static void partialvis_update_grids(Object *ob, } static void partialvis_update_bmesh_verts(BMesh *bm, - GHash *verts, - PartialVisAction action, - PartialVisArea area, - float planes[4][4], - int *any_changed, - int *any_visible) + GSet *verts, + PartialVisAction action, + PartialVisArea area, + float planes[4][4], + int *any_changed, + int *any_visible) { - GHashIterator gh_iter; + GSetIterator gs_iter; - GHASH_ITER (gh_iter, verts) { - BMVert *v = BLI_ghashIterator_getKey(&gh_iter); + GSET_ITER (gs_iter, verts) { + BMVert *v = BLI_gsetIterator_getKey(&gs_iter); float *vmask = CustomData_bmesh_get(&bm->vdata, - v->head.data, - CD_PAINT_MASK); + v->head.data, + CD_PAINT_MASK); /* hide vertex if in the hide volume */ if (is_effected(area, planes, v->co, *vmask)) { @@ -260,7 +260,7 @@ static void partialvis_update_bmesh(Object *ob, float planes[4][4]) { BMesh *bm; - GHash *unique, *other; + GSet *unique, *other; int any_changed = 0, any_visible = 0; bm = BKE_pbvh_get_bmesh(pbvh); diff --git a/source/blender/gpu/GPU_buffers.h b/source/blender/gpu/GPU_buffers.h index fca8dcc3392..cc22063a83c 100644 --- a/source/blender/gpu/GPU_buffers.h +++ b/source/blender/gpu/GPU_buffers.h @@ -46,6 +46,7 @@ struct CustomData; struct DMFlagMat; struct DerivedMesh; struct GHash; +struct GSet; struct GPUVertPointLink; struct PBVH; @@ -175,10 +176,10 @@ GPU_Buffers *GPU_build_grid_buffers(int *grid_indices, int totgrid, GPU_Buffers *GPU_build_bmesh_buffers(int smooth_shading); void GPU_update_bmesh_buffers(GPU_Buffers *buffers, - struct BMesh *bm, - struct GHash *bm_faces, - struct GHash *bm_unique_verts, - struct GHash *bm_other_verts); + struct BMesh *bm, + struct GHash *bm_faces, + struct GSet *bm_unique_verts, + struct GSet *bm_other_verts); void GPU_update_grid_buffers(GPU_Buffers *buffers, struct CCGElem **grids, const struct DMFlagMat *grid_flag_mats, diff --git a/source/blender/gpu/intern/gpu_buffers.c b/source/blender/gpu/intern/gpu_buffers.c index 39b7e1c72ad..384b7cce2ff 100644 --- a/source/blender/gpu/intern/gpu_buffers.c +++ b/source/blender/gpu/intern/gpu_buffers.c @@ -1963,19 +1963,19 @@ static void gpu_bmesh_vert_to_buffer_copy(BMVert *v, } /* Return the total number of vertices that don't have BM_ELEM_HIDDEN set */ -static int gpu_bmesh_vert_visible_count(GHash *bm_unique_verts, - GHash *bm_other_verts) +static int gpu_bmesh_vert_visible_count(GSet *bm_unique_verts, + GSet *bm_other_verts) { - GHashIterator gh_iter; + GSetIterator gs_iter; int totvert = 0; - GHASH_ITER (gh_iter, bm_unique_verts) { - BMVert *v = BLI_ghashIterator_getKey(&gh_iter); + GSET_ITER (gs_iter, bm_unique_verts) { + BMVert *v = BLI_gsetIterator_getKey(&gs_iter); if (!BM_elem_flag_test(v, BM_ELEM_HIDDEN)) totvert++; } - GHASH_ITER (gh_iter, bm_other_verts) { - BMVert *v = BLI_ghashIterator_getKey(&gh_iter); + GSET_ITER (gs_iter, bm_other_verts) { + BMVert *v = BLI_gsetIterator_getKey(&gs_iter); if (!BM_elem_flag_test(v, BM_ELEM_HIDDEN)) totvert++; } @@ -2002,10 +2002,10 @@ static int gpu_bmesh_face_visible_count(GHash *bm_faces) /* Creates a vertex buffer (coordinate, normal, color) and, if smooth * shading, an element index buffer. */ void GPU_update_bmesh_buffers(GPU_Buffers *buffers, - BMesh *bm, - GHash *bm_faces, - GHash *bm_unique_verts, - GHash *bm_other_verts) + BMesh *bm, + GHash *bm_faces, + GSet *bm_unique_verts, + GSet *bm_other_verts) { VertexBufferFormat *vert_data; void *tri_data; @@ -2036,22 +2036,23 @@ void GPU_update_bmesh_buffers(GPU_Buffers *buffers, /* Fill vertex buffer */ vert_data = glMapBufferARB(GL_ARRAY_BUFFER_ARB, GL_WRITE_ONLY_ARB); if (vert_data) { - GHashIterator gh_iter; int v_index = 0; if (buffers->smooth) { + GSetIterator gs_iter; + /* Vertices get an index assigned for use in the triangle * index buffer */ bm->elem_index_dirty |= BM_VERT; - GHASH_ITER (gh_iter, bm_unique_verts) { - gpu_bmesh_vert_to_buffer_copy(BLI_ghashIterator_getKey(&gh_iter), + GSET_ITER (gs_iter, bm_unique_verts) { + gpu_bmesh_vert_to_buffer_copy(BLI_gsetIterator_getKey(&gs_iter), vert_data, &v_index, NULL, NULL, cd_vert_mask_offset); } - GHASH_ITER (gh_iter, bm_other_verts) { - gpu_bmesh_vert_to_buffer_copy(BLI_ghashIterator_getKey(&gh_iter), + GSET_ITER (gs_iter, bm_other_verts) { + gpu_bmesh_vert_to_buffer_copy(BLI_gsetIterator_getKey(&gs_iter), vert_data, &v_index, NULL, NULL, cd_vert_mask_offset); } @@ -2059,6 +2060,8 @@ void GPU_update_bmesh_buffers(GPU_Buffers *buffers, maxvert = v_index; } else { + GHashIterator gh_iter; + GHASH_ITER (gh_iter, bm_faces) { BMFace *f = BLI_ghashIterator_getKey(&gh_iter); -- cgit v1.2.3