[Bf-blender-cvs] SVN commit: /data/svn/bf-blender [59569] branches/soc-2013-paint/source/ blender: BKI_gset and EdgeSet api, use when hash values aren't used ( reuses ghash internally without allocating space for the value).
Antony Riakiotakis
kalast at gmail.com
Tue Aug 27 21:26:16 CEST 2013
Revision: 59569
http://projects.blender.org/scm/viewvc.php?view=rev&root=bf-blender&revision=59569
Author: psy-fi
Date: 2013-08-27 19:26:16 +0000 (Tue, 27 Aug 2013)
Log Message:
-----------
BKI_gset and EdgeSet api, use when hash values aren't used (reuses ghash internally without allocating space for the value).
Modified Paths:
--------------
branches/soc-2013-paint/source/blender/blenkernel/intern/treehash.c
branches/soc-2013-paint/source/blender/blenlib/BLI_edgehash.h
branches/soc-2013-paint/source/blender/blenlib/BLI_ghash.h
branches/soc-2013-paint/source/blender/blenlib/intern/BLI_ghash.c
branches/soc-2013-paint/source/blender/blenlib/intern/edgehash.c
Modified: branches/soc-2013-paint/source/blender/blenkernel/intern/treehash.c
===================================================================
--- branches/soc-2013-paint/source/blender/blenkernel/intern/treehash.c 2013-08-27 19:26:10 UTC (rev 59568)
+++ branches/soc-2013-paint/source/blender/blenkernel/intern/treehash.c 2013-08-27 19:26:16 UTC (rev 59569)
@@ -30,9 +30,9 @@
#include "BKE_treehash.h"
+#include "BLI_utildefines.h"
#include "BLI_ghash.h"
#include "BLI_mempool.h"
-#include "BLI_utildefines.h"
#include "DNA_outliner_types.h"
Modified: branches/soc-2013-paint/source/blender/blenlib/BLI_edgehash.h
===================================================================
--- branches/soc-2013-paint/source/blender/blenlib/BLI_edgehash.h 2013-08-27 19:26:10 UTC (rev 59568)
+++ branches/soc-2013-paint/source/blender/blenlib/BLI_edgehash.h 2013-08-27 19:26:16 UTC (rev 59569)
@@ -45,7 +45,7 @@
EdgeHash *BLI_edgehash_new(const char *info);
void BLI_edgehash_free(EdgeHash *eh, EdgeHashFreeFP valfreefp);
void BLI_edgehash_insert(EdgeHash *eh, unsigned int v0, unsigned int v1, void *val);
-void BLI_edgehash_reinsert(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);
void **BLI_edgehash_lookup_p(EdgeHash *eh, unsigned int v0, unsigned int v1);
bool BLI_edgehash_haskey(EdgeHash *eh, unsigned int v0, unsigned int v1);
@@ -65,4 +65,28 @@
#define BLI_EDGEHASH_SIZE_GUESS_FROM_LOOPS(totloop) ((totloop) / 2)
#define BLI_EDGEHASH_SIZE_GUESS_FROM_POLYS(totpoly) ((totpoly) * 2)
+/* *** EdgeSet *** */
+
+struct EdgeSet;
+struct EdgeSetIterator;
+typedef struct EdgeSet EdgeSet;
+typedef struct EdgeSetIterator EdgeSetIterator;
+
+EdgeSet *BLI_edgeset_new_ex(const char *info,
+ const unsigned int nentries_reserve);
+EdgeSet *BLI_edgeset_new(const char *info);
+int BLI_edgeset_size(EdgeSet *es);
+bool BLI_edgeset_reinsert(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);
+void BLI_edgeset_free(EdgeSet *es);
+
+/* 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 *v0_r, unsigned int *v1_r) { return BLI_edgehashIterator_getKey((EdgeHashIterator *)esi, v0_r, v1_r); }
+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); }
+
+
#endif /* __BLI_EDGEHASH_H__ */
Modified: branches/soc-2013-paint/source/blender/blenlib/BLI_ghash.h
===================================================================
--- branches/soc-2013-paint/source/blender/blenlib/BLI_ghash.h 2013-08-27 19:26:10 UTC (rev 59568)
+++ branches/soc-2013-paint/source/blender/blenlib/BLI_ghash.h 2013-08-27 19:26:16 UTC (rev 59569)
@@ -63,7 +63,7 @@
GHash *BLI_ghash_new(GHashHashFP hashfp, GHashCmpFP cmpfp, const char *info);
void BLI_ghash_free(GHash *gh, GHashKeyFreeFP keyfreefp, GHashValFreeFP valfreefp);
void BLI_ghash_insert(GHash *gh, void *key, void *val);
-void BLI_ghash_reinsert(GHash *gh, void *key, void *val, GHashKeyFreeFP keyfreefp, GHashValFreeFP valfreefp);
+bool BLI_ghash_reinsert(GHash *gh, void *key, void *val, GHashKeyFreeFP keyfreefp, GHashValFreeFP valfreefp);
void *BLI_ghash_lookup(GHash *gh, const void *key);
void **BLI_ghash_lookup_p(GHash *gh, const void *key);
bool BLI_ghash_remove(GHash *gh, void *key, GHashKeyFreeFP keyfreefp, GHashValFreeFP valfreefp);
@@ -133,6 +133,62 @@
int BLI_ghashutil_paircmp(const void *a, const void *b);
void BLI_ghashutil_pairfree(void *ptr);
+
+/* *** */
+
+typedef struct GSet GSet;
+
+typedef GHashHashFP GSetHashFP;
+typedef GHashCmpFP GSetCmpFP;
+typedef GHashKeyFreeFP GSetKeyFreeFP;
+
+/* so we can cast but compiler sees as different */
+typedef struct GSetIterator {
+ GHashIterator _ghi
+#ifdef __GNUC__
+ __attribute__ ((deprecated))
+#endif
+ ;
+} GSetIterator;
+
+GSet *BLI_gset_new_ex(GSetHashFP hashfp, GSetCmpFP cmpfp, const char *info,
+ const unsigned int nentries_reserve);
+GSet *BLI_gset_new(GSetHashFP hashfp, GSetCmpFP cmpfp, const char *info);
+int BLI_gset_size(GSet *gs);
+void BLI_gset_free(GSet *gs, GSetKeyFreeFP keyfreefp);
+void BLI_gset_insert(GSet *gh, void *key);
+bool BLI_gset_reinsert(GSet *gh, void *key, GSetKeyFreeFP keyfreefp);
+bool BLI_gset_haskey(GSet *gs, const void *key);
+bool BLI_gset_remove(GSet *gs, void *key, GSetKeyFreeFP keyfreefp);
+void BLI_gset_clear_ex(GSet *gs, GSetKeyFreeFP keyfreefp,
+ const unsigned int nentries_reserve);
+void BLI_gset_clear(GSet *gs, GSetKeyFreeFP keyfreefp);
+
+GSet *BLI_gset_ptr_new_ex(const char *info,
+ const unsigned int nentries_reserve);
+GSet *BLI_gset_ptr_new(const char *info);
+GSet *BLI_gset_pair_new_ex(const char *info,
+ const unsigned int nentries_reserve);
+GSet *BLI_gset_pair_new(const char *info);
+
+/* rely on inline api for now */
+BLI_INLINE GSetIterator *BLI_gsetIterator_new(GSet *gs) { return (GSetIterator *)BLI_ghashIterator_new((GHash *)gs); }
+BLI_INLINE void BLI_gsetIterator_init(GSetIterator *gsi, GSet *gs) { BLI_ghashIterator_init((GHashIterator *)gsi, (GHash *)gs); }
+BLI_INLINE void BLI_gsetIterator_free(GSetIterator *gsi) { BLI_ghashIterator_free((GHashIterator *)gsi); }
+BLI_INLINE void *BLI_gsetIterator_getKey(GSetIterator *gsi) { return BLI_ghashIterator_getKey((GHashIterator *)gsi); }
+BLI_INLINE void BLI_gsetIterator_step(GSetIterator *gsi) { BLI_ghashIterator_step((GHashIterator *)gsi); }
+BLI_INLINE bool BLI_gsetIterator_done(GSetIterator *gsi) { return BLI_ghashIterator_done((GHashIterator *)gsi); }
+
+#define GSET_ITER(gs_iter_, gset_) \
+ for (BLI_gsetIterator_init(&gs_iter_, gset_); \
+ BLI_gsetIterator_done(&gs_iter_) == false; \
+ BLI_gsetIterator_step(&gs_iter_))
+
+#define GSET_ITER_INDEX(gs_iter_, gset_, i_) \
+ for (BLI_gsetIterator_init(&gs_iter_, gset_), i_ = 0; \
+ BLI_gsetIterator_done(&gs_iter_) == false; \
+ BLI_gsetIterator_step(&gs_iter_), i_++)
+
#ifdef __cplusplus
}
#endif
Modified: branches/soc-2013-paint/source/blender/blenlib/intern/BLI_ghash.c
===================================================================
--- branches/soc-2013-paint/source/blender/blenlib/intern/BLI_ghash.c 2013-08-27 19:26:10 UTC (rev 59568)
+++ branches/soc-2013-paint/source/blender/blenlib/intern/BLI_ghash.c 2013-08-27 19:26:16 UTC (rev 59569)
@@ -139,12 +139,37 @@
return ghash_lookup_entry_ex(gh, key, hash);
}
+static GHash *ghash_new(GHashHashFP hashfp, GHashCmpFP cmpfp, const char *info,
+ const unsigned int nentries_reserve,
+ const size_t entry_size)
+{
+ GHash *gh = MEM_mallocN(sizeof(*gh), info);
+
+ gh->hashfp = hashfp;
+ gh->cmpfp = cmpfp;
+
+ gh->nbuckets = hashsizes[0]; /* gh->cursize */
+ gh->nentries = 0;
+ gh->cursize = 0;
+ gh->flag = 0;
+
+ /* if we have reserved the number of elements that this hash will contain */
+ if (nentries_reserve) {
+ ghash_buckets_reserve(gh, nentries_reserve);
+ }
+
+ gh->buckets = MEM_callocN(gh->nbuckets * sizeof(*gh->buckets), "buckets");
+ gh->entrypool = BLI_mempool_create((int)entry_size, 64, 64, 0);
+
+ return gh;
+}
+
/**
* Internal insert function.
* Takes a hash argument to avoid calling #ghash_keyhash multiple times.
*/
-static void ghash_insert_ex(GHash *gh, void *key, void *val,
- unsigned int hash)
+static Entry *ghash_insert_ex(GHash *gh, void *key,
+ unsigned int hash)
{
Entry *e = (Entry *)BLI_mempool_alloc(gh->entrypool);
@@ -152,10 +177,11 @@
e->next = gh->buckets[hash];
e->key = key;
- e->val = val;
+ /* intentionally don't set the value */
gh->buckets[hash] = e;
if (UNLIKELY(ghash_test_expand_buckets(++gh->nentries, gh->nbuckets))) {
+ Entry *e_iter;
Entry **old = gh->buckets;
const unsigned nold = gh->nbuckets;
unsigned int i;
@@ -165,16 +191,18 @@
for (i = 0; i < nold; i++) {
Entry *e_next;
- for (e = old[i]; e; e = e_next) {
- e_next = e->next;
- hash = ghash_keyhash(gh, e->key);
- e->next = gh->buckets[hash];
- gh->buckets[hash] = e;
+ for (e_iter = old[i]; e_iter; e_iter = e_next) {
+ e_next = e_iter->next;
+ hash = ghash_keyhash(gh, e_iter->key);
+ e_iter->next = gh->buckets[hash];
+ gh->buckets[hash] = e_iter;
}
}
MEM_freeN(old);
}
+
+ return e;
}
/** \} */
@@ -195,25 +223,9 @@
GHash *BLI_ghash_new_ex(GHashHashFP hashfp, GHashCmpFP cmpfp, const char *info,
const unsigned int nentries_reserve)
{
- GHash *gh = MEM_mallocN(sizeof(*gh), info);
-
- gh->hashfp = hashfp;
- gh->cmpfp = cmpfp;
-
- gh->nbuckets = hashsizes[0]; /* gh->cursize */
- gh->nentries = 0;
- gh->cursize = 0;
- gh->flag = 0;
-
- /* if we have reserved the number of elements that this hash will contain */
- if (nentries_reserve) {
- ghash_buckets_reserve(gh, nentries_reserve);
- }
-
- gh->buckets = MEM_callocN(gh->nbuckets * sizeof(*gh->buckets), "buckets");
- gh->entrypool = BLI_mempool_create(sizeof(Entry), 64, 64, 0);
-
- return gh;
+ return ghash_new(hashfp, cmpfp, info,
+ nentries_reserve,
+ sizeof(Entry));
}
/**
@@ -242,27 +254,32 @@
void BLI_ghash_insert(GHash *gh, void *key, void *val)
{
const unsigned int hash = ghash_keyhash(gh, key);
- ghash_insert_ex(gh, key, val, hash);
+ Entry *e = ghash_insert_ex(gh, key, hash);
+ e->val = val;
}
/**
@@ Diff output truncated at 10240 characters. @@
More information about the Bf-blender-cvs
mailing list