diff options
author | Campbell Barton <ideasman42@gmail.com> | 2013-08-26 00:00:19 +0400 |
---|---|---|
committer | Campbell Barton <ideasman42@gmail.com> | 2013-08-26 00:00:19 +0400 |
commit | 1d5eff36f5bd7fc7986e59d4dbe7b885ccb50e61 (patch) | |
tree | 69d5934bf61b55b098b6e59406cb9da897bdfba5 /source/blender/blenlib/intern | |
parent | 74b770bc898d745f3d377c451fe263529acbc46c (diff) |
BKI_gset and EdgeSet api, use when hash values aren't used (reuses ghash internally without allocating space for the value).
Diffstat (limited to 'source/blender/blenlib/intern')
-rw-r--r-- | source/blender/blenlib/intern/BLI_ghash.c | 198 | ||||
-rw-r--r-- | source/blender/blenlib/intern/edgehash.c | 141 |
2 files changed, 280 insertions, 59 deletions
diff --git a/source/blender/blenlib/intern/BLI_ghash.c b/source/blender/blenlib/intern/BLI_ghash.c index 51526fd2b99..27ab65fd92f 100644 --- a/source/blender/blenlib/intern/BLI_ghash.c +++ b/source/blender/blenlib/intern/BLI_ghash.c @@ -139,12 +139,37 @@ BLI_INLINE Entry *ghash_lookup_entry(GHash *gh, const void *key) 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 @@ static void ghash_insert_ex(GHash *gh, void *key, void *val, 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 @@ static void ghash_insert_ex(GHash *gh, void *key, void *val, 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 @@ static void ghash_insert_ex(GHash *gh, void *key, void *val, 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 @@ int BLI_ghash_size(GHash *gh) 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; } /** * Inserts a new value to a key that may already be in ghash. * * Avoids #BLI_ghash_remove, #BLI_ghash_insert calls (double lookups) + * + * \returns true if a new key has been added. */ -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) { const unsigned int hash = ghash_keyhash(gh, key); Entry *e = ghash_lookup_entry_ex(gh, key, hash); if (e) { if (keyfreefp) keyfreefp(e->key); if (valfreefp) valfreefp(e->val); - e->key = key; e->val = val; + return false; } else { - ghash_insert_ex(gh, key, val, hash); + e = ghash_insert_ex(gh, key, hash); + e->val = val; + return true; } } @@ -700,7 +717,7 @@ void BLI_ghashutil_pairfree(void *ptr) /** \} */ -/** \name Convenience Creation Functions +/** \name Convenience GHash Creation Functions * \{ */ GHash *BLI_ghash_ptr_new_ex(const char *info, @@ -748,3 +765,120 @@ GHash *BLI_ghash_pair_new(const char *info) } /** \} */ + + +/* -------------------------------------------------------------------- */ +/* GSet API */ + +/* Use ghash API to give 'set' functionality */ + +/* TODO: typical set functions + * isdisjoint/issubset/issuperset/union/intersection/difference etc */ + +/** \name GSet Functions + * \{ */ +GSet *BLI_gset_new_ex(GSetHashFP hashfp, GSetCmpFP cmpfp, const char *info, + const unsigned int nentries_reserve) +{ + return (GSet *)ghash_new(hashfp, cmpfp, info, + nentries_reserve, + sizeof(Entry) - sizeof(void *)); +} + +GSet *BLI_gset_new(GSetHashFP hashfp, GSetCmpFP cmpfp, const char *info) +{ + return BLI_gset_new_ex(hashfp, cmpfp, info, 0); +} + +int BLI_gset_size(GSet *gs) +{ + return (int)((GHash *)gs)->nentries; +} + +/** + * Adds the key to the set (no checks for unique keys!). + * Matching #BLI_ghash_insert + */ +void BLI_gset_insert(GSet *gs, void *key) +{ + const unsigned int hash = ghash_keyhash((GHash *)gs, key); + ghash_insert_ex((GHash *)gs, key, hash); +} + +/** + * Adds the key to the set (duplicates are managed). + * Matching #BLI_ghash_reinsert + * + * \returns true if a new key has been added. + */ +bool BLI_gset_reinsert(GSet *gs, void *key, GSetKeyFreeFP keyfreefp) +{ + const unsigned int hash = ghash_keyhash((GHash *)gs, key); + Entry *e = ghash_lookup_entry_ex((GHash *)gs, key, hash); + if (e) { + if (keyfreefp) keyfreefp(e->key); + e->key = key; + return false; + } + else { + ghash_insert_ex((GHash *)gs, key, hash); + return true; + } +} + +bool BLI_gset_remove(GSet *gs, void *key, GSetKeyFreeFP keyfreefp) +{ + return BLI_ghash_remove((GHash *)gs, key, keyfreefp, NULL); +} + + +bool BLI_gset_haskey(GSet *gs, const void *key) +{ + return (ghash_lookup_entry((GHash *)gs, key) != NULL); +} + +void BLI_gset_clear_ex(GSet *gs, GSetKeyFreeFP keyfreefp, + const unsigned int nentries_reserve) +{ + BLI_ghash_clear_ex((GHash *)gs, keyfreefp, NULL, + nentries_reserve); +} + +void BLI_gset_clear(GSet *gs, GSetKeyFreeFP keyfreefp) +{ + BLI_ghash_clear((GHash *)gs, keyfreefp, NULL); +} + +void BLI_gset_free(GSet *gs, GSetKeyFreeFP keyfreefp) +{ + BLI_ghash_free((GHash *)gs, keyfreefp, NULL); +} +/** \} */ + + +/** \name Convenience GSet Creation Functions + * \{ */ + +GSet *BLI_gset_ptr_new_ex(const char *info, + const unsigned int nentries_reserve) +{ + return BLI_gset_new_ex(BLI_ghashutil_ptrhash, BLI_ghashutil_ptrcmp, info, + nentries_reserve); +} +GSet *BLI_gset_ptr_new(const char *info) +{ + return BLI_gset_ptr_new_ex(info, 0); +} + +GSet *BLI_gset_pair_new_ex(const char *info, + const unsigned int nentries_reserve) +{ + return BLI_gset_new_ex(BLI_ghashutil_pairhash, BLI_ghashutil_paircmp, info, + nentries_reserve); +} +GSet *BLI_gset_pair_new(const char *info) +{ + return BLI_gset_pair_new_ex(info, 0); +} + +/** \} */ diff --git a/source/blender/blenlib/intern/edgehash.c b/source/blender/blenlib/intern/edgehash.c index cf1405e8f01..33577bd3f91 100644 --- a/source/blender/blenlib/intern/edgehash.c +++ b/source/blender/blenlib/intern/edgehash.c @@ -128,8 +128,30 @@ BLI_INLINE EdgeEntry *edgehash_lookup_entry(EdgeHash *eh, unsigned int v0, unsig return edgehash_lookup_entry_ex(eh, v0, v1, hash); } -static void edgehash_insert_ex(EdgeHash *eh, unsigned int v0, unsigned int v1, void *val, - unsigned int hash) +static EdgeHash *edgehash_new(const char *info, + const unsigned int nentries_reserve, + const size_t entry_size) +{ + EdgeHash *eh = MEM_mallocN(sizeof(*eh), info); + + eh->nbuckets = _ehash_hashsizes[0]; /* eh->cursize */ + eh->nentries = 0; + eh->cursize = 0; + eh->flag = 0; + + /* if we have reserved the number of elements that this hash will contain */ + if (nentries_reserve) { + edgehash_buckets_reserve(eh, nentries_reserve); + } + + eh->buckets = MEM_callocN(eh->nbuckets * sizeof(*eh->buckets), "eh buckets 2"); + eh->epool = BLI_mempool_create((int)entry_size, 512, 512, BLI_MEMPOOL_SYSMALLOC); + + return eh; +} + +static EdgeEntry *edgehash_insert_ex(EdgeHash *eh, unsigned int v0, unsigned int v1, + unsigned int hash) { EdgeEntry *e = BLI_mempool_alloc(eh->epool); @@ -142,10 +164,11 @@ static void edgehash_insert_ex(EdgeHash *eh, unsigned int v0, unsigned int v1, v e->next = eh->buckets[hash]; e->v0 = v0; e->v1 = v1; - e->val = val; + /* intentionally don't set the value */ eh->buckets[hash] = e; if (UNLIKELY(edgehash_test_expand_buckets(++eh->nentries, eh->nbuckets))) { + EdgeEntry *e_iter; EdgeEntry **old = eh->buckets; const unsigned int nold = eh->nbuckets; unsigned int i; @@ -155,16 +178,17 @@ static void edgehash_insert_ex(EdgeHash *eh, unsigned int v0, unsigned int v1, v for (i = 0; i < nold; i++) { EdgeEntry *e_next; - for (e = old[i]; e; e = e_next) { - e_next = e->next; - hash = edgehash_keyhash(eh, e->v0, e->v1); - e->next = eh->buckets[hash]; - eh->buckets[hash] = e; + for (e_iter = old[i]; e_iter; e_iter = e_next) { + e_next = e_iter->next; + hash = edgehash_keyhash(eh, e_iter->v0, e_iter->v1); + e_iter->next = eh->buckets[hash]; + eh->buckets[hash] = e_iter; } } MEM_freeN(old); } + return e; } /** \} */ @@ -177,22 +201,9 @@ static void edgehash_insert_ex(EdgeHash *eh, unsigned int v0, unsigned int v1, v EdgeHash *BLI_edgehash_new_ex(const char *info, const unsigned int nentries_reserve) { - EdgeHash *eh = MEM_mallocN(sizeof(*eh), info); - - eh->nbuckets = _ehash_hashsizes[0]; /* eh->cursize */ - eh->nentries = 0; - eh->cursize = 0; - eh->flag = 0; - - /* if we have reserved the number of elements that this hash will contain */ - if (nentries_reserve) { - edgehash_buckets_reserve(eh, nentries_reserve); - } - - eh->buckets = MEM_callocN(eh->nbuckets * sizeof(*eh->buckets), "eh buckets 2"); - eh->epool = BLI_mempool_create(sizeof(EdgeEntry), 512, 512, BLI_MEMPOOL_SYSMALLOC); - - return eh; + return edgehash_new(info, + nentries_reserve, + sizeof(EdgeEntry)); } EdgeHash *BLI_edgehash_new(const char *info) @@ -207,15 +218,17 @@ EdgeHash *BLI_edgehash_new(const char *info) void BLI_edgehash_insert(EdgeHash *eh, unsigned int v0, unsigned int v1, void *val) { unsigned int hash; + EdgeEntry *e; EDGE_ORD(v0, v1); /* ensure v0 is smaller */ hash = edgehash_keyhash(eh, v0, v1); - edgehash_insert_ex(eh, v0, v1, val, hash); + e = edgehash_insert_ex(eh, v0, v1, hash); + e->val = val; } /** * Assign a new value to a key that may already be in edgehash. */ -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) { unsigned int hash; EdgeEntry *e; @@ -226,9 +239,12 @@ void BLI_edgehash_reinsert(EdgeHash *eh, unsigned int v0, unsigned int v1, void e = edgehash_lookup_entry_ex(eh, v0, v1, hash); if (e) { e->val = val; + return false; } else { - edgehash_insert_ex(eh, v0, v1, val, hash); + e = edgehash_insert_ex(eh, v0, v1, hash); + e->val = val; + return true; } } @@ -415,3 +431,74 @@ bool BLI_edgehashIterator_isDone(EdgeHashIterator *ehi) } /** \} */ + +/* -------------------------------------------------------------------- */ +/* EdgeSet API */ + +/* Use edgehash API to give 'set' functionality */ + +/** \name EdgeSet Functions + * \{ */ +EdgeSet *BLI_edgeset_new_ex(const char *info, + const unsigned int nentries_reserve) +{ + return (EdgeSet *)edgehash_new(info, + nentries_reserve, + sizeof(EdgeEntry) - sizeof(void *)); +} + +EdgeSet *BLI_edgeset_new(const char *info) +{ + return BLI_edgeset_new_ex(info, 0); +} + +int BLI_edgeset_size(EdgeSet *es) +{ + return (int)((EdgeHash *)es)->nentries; +} + +/** + * Adds the key to the set (no checks for unique keys!). + * Matching #BLI_edgehash_insert + */ +void BLI_edgeset_insert(EdgeSet *es, unsigned int v0, unsigned int v1) +{ + unsigned int hash; + EDGE_ORD(v0, v1); /* ensure v0 is smaller */ + hash = edgehash_keyhash((EdgeHash *)es, v0, v1); + edgehash_insert_ex((EdgeHash *)es, v0, v1, hash); +} + +/** + * Assign a new value to a key that may already be in edgehash. + */ +bool BLI_edgeset_reinsert(EdgeSet *es, unsigned int v0, unsigned int v1) +{ + unsigned int hash; + EdgeEntry *e; + + EDGE_ORD(v0, v1); /* ensure v0 is smaller */ + hash = edgehash_keyhash((EdgeHash *)es, v0, v1); + + e = edgehash_lookup_entry_ex((EdgeHash *)es, v0, v1, hash); + if (e) { + return false; + } + else { + edgehash_insert_ex((EdgeHash *)es, v0, v1, hash); + return true; + } +} + +bool BLI_edgeset_haskey(EdgeSet *es, unsigned int v0, unsigned int v1) +{ + return (edgehash_lookup_entry((EdgeHash *)es, v0, v1) != NULL); +} + + +void BLI_edgeset_free(EdgeSet *es) +{ + BLI_edgehash_free((EdgeHash *)es, NULL); +} + +/** \} */ |