diff options
author | Bastien Montagne <montagne29@wanadoo.fr> | 2016-02-20 17:17:40 +0300 |
---|---|---|
committer | Bastien Montagne <montagne29@wanadoo.fr> | 2016-02-20 17:28:25 +0300 |
commit | fe9b21a44ad25f068da88f6e12b60c1486be3605 (patch) | |
tree | f2ff785c3a59efa3f756ba0042262b332a0930d9 /source/blender/blenlib/BLI_ghash.h | |
parent | 90e77c871b771ad9df23c3e3c9b255d75c409b60 (diff) |
Add GHash/GSet pop() feature.
Behavior is similar to python's set.pop(), it removes and returns a 'random' entry from the hash.
Notes:
* Popping will return items in same order as ghash/gset iterators (i.e. increasing
order in internal buckets-based storage), unless ghash/gset is modified in between.
* We are keeping a track of the latest bucket we popped out (through a 'state' parameter),
this allows for similar performances to iterators when iteratively popping a whole hash
(without it, we are roughly O(n!), with it we are roughly O(n)...).
Reviewers: campbellbarton
Differential Revision: https://developer.blender.org/D1808
Diffstat (limited to 'source/blender/blenlib/BLI_ghash.h')
-rw-r--r-- | source/blender/blenlib/BLI_ghash.h | 18 |
1 files changed, 18 insertions, 0 deletions
diff --git a/source/blender/blenlib/BLI_ghash.h b/source/blender/blenlib/BLI_ghash.h index 9503da6e53e..f13e8cb2ae8 100644 --- a/source/blender/blenlib/BLI_ghash.h +++ b/source/blender/blenlib/BLI_ghash.h @@ -39,6 +39,14 @@ extern "C" { #endif +#define _GHASH_INTERNAL_ATTR +#ifndef GHASH_INTERNAL_API +# ifdef __GNUC__ +# undef _GHASH_INTERNAL_ATTR +# define _GHASH_INTERNAL_ATTR __attribute__ ((deprecated)) +# endif +#endif + typedef unsigned int (*GHashHashFP) (const void *key); /** returns false when equal */ typedef bool (*GHashCmpFP) (const void *a, const void *b); @@ -55,6 +63,12 @@ typedef struct GHashIterator { unsigned int curBucket; } GHashIterator; +typedef struct GHashIterState { + unsigned int curr_bucket _GHASH_INTERNAL_ATTR; +} GHashIterState; + + + enum { GHASH_FLAG_ALLOW_DUPES = (1 << 0), /* Only checked for in debug mode */ GHASH_FLAG_ALLOW_SHRINK = (1 << 1), /* Allow to shrink buckets' size. */ @@ -87,6 +101,7 @@ void BLI_ghash_clear_ex(GHash *gh, GHashKeyFreeFP keyfreefp, GHashValFreeFP va const unsigned int nentries_reserve); void *BLI_ghash_popkey(GHash *gh, const void *key, GHashKeyFreeFP keyfreefp) ATTR_WARN_UNUSED_RESULT; bool BLI_ghash_haskey(GHash *gh, const void *key) ATTR_WARN_UNUSED_RESULT; +bool BLI_ghash_pop(GHash *gh, GHashIterState *state, void **r_key, void **r_val) ATTR_WARN_UNUSED_RESULT ATTR_NONNULL(); unsigned int BLI_ghash_size(GHash *gh) ATTR_WARN_UNUSED_RESULT; void BLI_ghash_flag_set(GHash *gh, unsigned int flag); void BLI_ghash_flag_clear(GHash *gh, unsigned int flag); @@ -208,6 +223,8 @@ typedef GHashCmpFP GSetCmpFP; typedef GHashKeyFreeFP GSetKeyFreeFP; typedef GHashKeyCopyFP GSetKeyCopyFP; +typedef GHashIterState GSetIterState; + /* so we can cast but compiler sees as different */ typedef struct GSetIterator { GHashIterator _ghi @@ -229,6 +246,7 @@ void BLI_gset_insert(GSet *gh, void *key); bool BLI_gset_add(GSet *gs, void *key); bool BLI_gset_reinsert(GSet *gh, void *key, GSetKeyFreeFP keyfreefp); bool BLI_gset_haskey(GSet *gs, const void *key) ATTR_WARN_UNUSED_RESULT; +bool BLI_gset_pop(GSet *gs, GSetIterState *state, void **r_key) ATTR_WARN_UNUSED_RESULT ATTR_NONNULL(); bool BLI_gset_remove(GSet *gs, const void *key, GSetKeyFreeFP keyfreefp); void BLI_gset_clear_ex(GSet *gs, GSetKeyFreeFP keyfreefp, const unsigned int nentries_reserve); |