13 #ifndef __UT_ArraySet__
14 #define __UT_ArraySet__
23 #include <hboost/functional/hash.hpp>
32 struct DefaultClearer;
41 static const bool clearNeedsDestruction =
false;
49 if (std::numeric_limits<T>::has_quiet_NaN) {
53 v = std::numeric_limits<T>::quiet_NaN();
66 if (std::numeric_limits<T>::has_quiet_NaN) {
107 static const bool clearNeedsDestruction =
false;
110 template<
typename S0,
typename S1>
161 std::size_t MAX_LOAD_FACTOR_256=128,
163 class Hash=hboost::hash<Key>,
164 class KeyEqual=std::equal_to<Key>
192 if (init_bucket_count != 0)
201 that.myBuckets =
nullptr;
202 that.myNumBuckets = 0;
215 template<
typename INPUT_ITERATOR>
223 if (ninput_items == 0)
228 for (; start_input != end_input; ++start_input)
233 *pdest = *start_input;
247 if (init_bucket_count == 0 || init_bucket_count < init.size()) {
251 bucket_count = init_bucket_count;
254 for (
auto &&p = init.begin(); p != init.end(); ++p) {
289 insert(init.begin(), init.end());
298 that.myBuckets =
nullptr;
299 that.myNumBuckets = 0;
315 if (Clearer::isClear(*p))
318 const_iterator it = that.
find(*p);
328 return !(*
this == that);
397 if (Clearer::clearNeedsDestruction || !Clearer::isClear(*p))
440 return float(MAX_LOAD_FACTOR_256)/256;
455 if (new_num_buckets < min_buckets) {
456 new_num_buckets = min_buckets;
480 if (new_num_buckets == 0)
488 if (new_num_buckets < old_size)
490 UT_ASSERT_MSG(0,
"What does the caller expect to happen when setting the number of buckets lower than the size, but not to zero?\nThis class doesn't support multiple items per bucket.");
491 new_num_buckets = old_size;
499 pointer new_end = new_buckets + new_num_buckets;
500 for (
pointer p = new_buckets; p < new_end; ++p)
502 Clearer::clearConstruct(p);
511 if (!Clearer::isClear(*srcp))
520 insertHelper<false,false>(new_buckets, new_num_buckets,
v, destp);
521 *destp = std::move(v);
552 template<
bool constant_type>
567 UT_ASSERT_MSG_P(scan || current == end || !Clearer::isClear(*current),
"An iterator can't point to a clear item!");
570 while (myCurrent != myEnd && Clearer::isClear(*myCurrent))
582 UT_ASSERT_MSG_P(myEnd == that.myEnd,
"Probably unintentional: Comparing against iterator from different set or iterator invalidated by reallocation!");
583 return (myCurrent == that.myCurrent);
587 UT_ASSERT_MSG_P(myEnd == that.myEnd,
"Probably unintentional: Comparing against iterator from different set or iterator invalidated by reallocation!");
588 return (myCurrent != that.myCurrent);
592 return myCurrent == myEnd;
597 if (myCurrent == myEnd) {
602 }
while (myCurrent != myEnd && Clearer::isClear(*myCurrent));
623 UT_ASSERT_MSG_P(myCurrent <= myEnd,
"Dereferencing iterator past end!");
628 UT_ASSERT_MSG_P(myCurrent <= myEnd,
"Dereferencing iterator past end!");
684 return const_iterator(pend,pend,
false);
687 const_iterator
end()
const
690 return const_iterator(pend,pend,
false);
702 return iterator(
nullptr,
nullptr,
false);
707 for (
pointer p = search_start; p != pend; ++p)
711 if (Clearer::isClear(*p))
715 for (
pointer p = search_start-1; p >= pstart; --p)
719 if (Clearer::isClear(*p))
724 const_iterator
find(
const Key &key)
const
730 return const_iterator(
nullptr,
nullptr,
false);
738 return const_iterator(p,pend,
false);
739 if (Clearer::isClear(*p))
740 return const_iterator(pend,pend,
false);
746 return const_iterator(p,pend,
false);
747 if (Clearer::isClear(*p))
748 return const_iterator(pend,pend,
false);
750 return const_iterator(pend,pend,
false);
775 else if (Clearer::isClear(*p))
776 return MULTI ? count : 0;
787 else if (Clearer::isClear(*p))
788 return MULTI ? count : 0;
790 return MULTI ? count : 0;
809 if (Clearer::isClear(*p))
817 if (Clearer::isClear(*p))
826 std::pair<const_iterator,const_iterator>
equal_range(
const Key &key)
const
833 return std::make_pair(const_iterator(
nullptr,
nullptr,
false), const_iterator(
nullptr,
nullptr,
false));
841 return std::make_pair(const_iterator(p,pend,
false), const_iterator(p+1,pend,
true));
842 if (Clearer::isClear(*p))
843 return std::make_pair(const_iterator(pend,pend,
false), const_iterator(pend,pend,
false));
849 return std::make_pair(const_iterator(p,pend,
false), const_iterator(p+1,pend,
true));
850 if (Clearer::isClear(*p))
851 return std::make_pair(const_iterator(pend,pend,
false), const_iterator(pend,pend,
false));
853 return std::make_pair(const_iterator(pend,pend,
false), const_iterator(pend,pend,
false));
866 else if (first_found)
868 if (first_found != search_start)
869 return std::make_pair(const_iterator(first_found,pend,
false), const_iterator(p,pend,
true));
874 else if (Clearer::isClear(*p))
877 return std::make_pair(const_iterator(pend,pend,
false), const_iterator(pend,pend,
false));
886 return std::make_pair(const_iterator(p+1,pend,
false), const_iterator(end_found,pend,
true));
889 return std::make_pair(const_iterator(pstart,pend,
false), const_iterator(end_found,pend,
true));
898 return std::make_pair(
iterator(
nullptr,
nullptr,
false),
iterator(
nullptr,
nullptr,
false));
903 for (
pointer p = search_start; p != pend; ++p)
907 if (Clearer::isClear(*p))
908 return std::make_pair(
iterator(pend,pend,
false),
iterator(pend,pend,
false));
911 for (
pointer p = search_start-1; p >= pstart; --p)
915 if (Clearer::isClear(*p))
916 return std::make_pair(
iterator(pend,pend,
false),
iterator(pend,pend,
false));
918 return std::make_pair(
iterator(pend,pend,
false),
iterator(pend,pend,
false));
924 for (
pointer p = search_start; p != pend; ++p)
931 else if (first_found)
933 if (first_found != search_start)
934 return std::make_pair(
iterator(first_found,pend,
false),
iterator(p,pend,
true));
939 else if (Clearer::isClear(*p))
942 return std::make_pair(
iterator(pend,pend,
false),
iterator(pend,pend,
false));
947 for (
pointer p = search_start-1; p >= pstart; --p)
951 return std::make_pair(
iterator(p+1,pend,
false),
iterator(end_found,pend,
true));
954 return std::make_pair(
iterator(pstart,pend,
false),
iterator(end_found,pend,
true));
981 *p = std::move(
value);
989 template<
typename INPUT_ITERATOR>
990 void insert(INPUT_ITERATOR start_input, INPUT_ITERATOR end_input)
1003 for (; start_input != end_input; ++start_input)
1008 *pdest = *start_input;
1016 void insert(std::initializer_list<value_type> list)
1019 insert(list.begin(),list.end());
1026 template <
typename... Args>
1048 UT_ASSERT_MSG_P(p >= pstart && p < pend && !Clearer::isClear(*p),
"An iterator to erase can't point to a clear item!");
1060 bool end_case = (pnext == pend);
1063 if (Clearer::isClear(*pnext))
1074 end_case = (pnext == pend);
1075 }
while (!end_case && !Clearer::isClear(*pnext));
1078 if (end_case && (p != pstart) && !Clearer::isClear(*(p-1)))
1086 while (pprev != pstart && !Clearer::isClear(*(pprev-1)))
1098 if (ideal_bucket_num > (pprev-pstart))
1101 for (
pointer pdest = p; pdest != pprev; --pdest)
1103 *pdest = std::move(*(pdest-1));
1105 Clearer::clear(*pprev);
1110 }
while (pprev != p);
1123 for (
pointer pdest = p; pdest+1 != pnext; ++pdest)
1128 if (ideal_bucket_num > empty_bucket_num)
1130 Clearer::clear(*pdest);
1131 return iterator(p+(pdest==p),pend,
false);
1134 *pdest = std::move(*(pdest+1));
1137 Clearer::clear(*(pnext-1));
1147 #if 0 // This isn't fully implemented, so it's excluded to avoid anyone accidentally using it.
1158 if (start_iter == end_iter)
1167 UT_ASSERT_MSG_P(prange_start >= pstart && prange_start < prange_end && prange_end <= pend && !Clearer::isClear(*prange_start),
"An iterator to erase can't point to a clear item!");
1172 Clearer::clear(*prange_start);
1173 for (
pointer p = prange_start+1; p != prange_end; ++p)
1175 if (!Clearer::isClear(*p))
1178 ++nitems_in_last_block;
1183 nitems_in_last_block = 0;
1195 pointer block_end = prange_end;
1197 if (prange_end != pend)
1203 if (nitems_in_last_block == 0)
1210 }
while (block_end != pend && !Clearer::isClear(*block_end));
1216 if (nitems_in_last_block != prange_end-prange_start)
1229 if (block_end == pend && nitems_in_last_block == prange_end-prange_start && prange_start != pstart && !Clearer::isClear(*(prange_start-1)))
1232 pointer block_start = prange_start;
1236 }
while (block_start != pstart && !Clearer::isClear(*(block_start-1)));
1294 int64 mem = inclusive ?
sizeof(*this) : 0;
1299 template<
typename FUNCTOR>
1305 for (; p != pend; ++p)
1307 if (!Clearer::isClear(*p))
1321 if ((256%MAX_LOAD_FACTOR_256) == 0)
1323 return size * (256/MAX_LOAD_FACTOR_256) + 1;
1325 return (size*256 + MAX_LOAD_FACTOR_256-1)/MAX_LOAD_FACTOR_256;
1338 template<
bool fail_on_equal=!MULTI,
bool check_realloc=true>
1343 if (check_realloc && nbuckets == 0)
1350 const pointer pend = pstart + nbuckets;
1352 const size_type ideal_bucket = (hash%nbuckets);
1353 pointer init_searchp = pstart + ideal_bucket;
1354 pointer searchp = init_searchp;
1356 if (Clearer::isClear(*searchp))
1372 if (!fail_on_equal && check_realloc)
1387 if ((
hasher()(*searchp)%nbuckets) <= ideal_bucket)
1392 if (searchp == pend || Clearer::isClear(*searchp))
1396 if (fail_on_equal && other_hash==hash &&
key_equal()(*searchp,value))
1401 if (ideal_bucket < (other_hash%nbuckets))
1416 while (searchp != pend && !Clearer::isClear(*searchp))
1421 if (searchp != pend)
1432 if (fail_on_equal && check_realloc)
1447 while (searchp != insertp)
1449 *searchp = std::move(*(searchp-1));
1461 if (insertp == init_searchp)
1465 UT_ASSERT_P(insertp-1 >= pstart || (fail_on_equal && insertp == pstart));
1466 while ((!fail_on_equal || insertp != pstart) && !Clearer::isClear(*(insertp-1)))
1469 if (fail_on_equal && other_hash == hash &&
key_equal()(*(insertp-1),value))
1477 if ((other_hash%nbuckets) <= ideal_bucket)
1480 UT_ASSERT_P(insertp-1 >= pstart || (fail_on_equal && insertp == pstart));
1498 pointer blockstart = (init_searchp < insertp) ? init_searchp : insertp;
1499 if (fail_on_equal && check_realloc)
1505 if (blockstart == pstart)
1516 bool in_ideal_bucket_span =
true;
1517 bool checked_realloc =
false;
1518 while (!Clearer::isClear(*(blockstart-1)))
1523 if (fail_on_equal && in_ideal_bucket_span)
1526 if ((other_hash == hash) &&
key_equal()(*blockstart,value))
1531 in_ideal_bucket_span = ((other_hash%nbuckets) == ideal_bucket);
1533 if (fail_on_equal && check_realloc && !checked_realloc)
1535 if (!in_ideal_bucket_span)
1549 checked_realloc =
true;
1554 else if (blockstart == pstart)
1565 if (fail_on_equal && check_realloc && !checked_realloc)
1579 while (blockstart != insertp)
1581 *(blockstart-1) = std::move(*blockstart);
1596 std::size_t MAX_LOAD_FACTOR_256,
1611 static const bool clearNeedsDestruction =
false;
1616 template<
typename Key,
1618 int MAX_LOAD_FACTOR_256 = 128,
1620 class Hash = hboost::hash<Key>,
1621 class KeyEqual = std::equal_to<Key> >
1625 template<
typename Key,
1627 int MAX_LOAD_FACTOR_256,
float load_factor() const
Returns the current portion of buckets that are occupied.
const_iterator find(const Key &key) const
const_pointer searchStart(const Key &key) const
static void clearConstruct(bool *p)
ArraySet(const set_type &that)
ArraySet(size_type init_bucket_count)
UT_ASSERT_COMPILETIME(BRAY_EVENT_MAXFLAGS<=32)
std::ptrdiff_t difference_type
std::pair< iterator, bool > insert(const value_type &value)
size_type size() const
Returns the number of items in the set.
UT_API exint UTbumpAllocToPrime(exint current_size)
void setNumBuckets(size_type new_num_buckets)
static const bool clearNeedsDestruction
STATIC_INLINE size_t Hash(const char *s, size_t len)
void swap(UT::ArraySet< Key, MULTI, MAX_LOAD_FACTOR_256, Clearer, Hash, KeyEqual > &a, UT::ArraySet< Key, MULTI, MAX_LOAD_FACTOR_256, Clearer, Hash, KeyEqual > &b)
pointer getCurrent() const
GLsizei const GLfloat * value
static void clearConstruct(T *p)
static size_type max_bucket_count()
std::pair< iterator, bool > insert(value_type &&value)
static void clear(bool &v)
constexpr bool SYSisNan(const F f)
set_type & operator=(set_type &&that)
GLboolean GLboolean GLboolean GLboolean a
bool empty() const
Returns true iff there are no items in the set.
ImageBuf OIIO_API min(Image_or_Const A, Image_or_Const B, ROI roi={}, int nthreads=0)
iterator end()
Returns a non-const end iterator for the set.
iterator_t & operator=(const iterator_t &)=default
#define UT_ASSERT_MSG_P(ZZ,...)
static bool isClear(bool v)
std::ptrdiff_t difference_type
bool insertHelper(pointer pstart, size_type nbuckets, const value_type &value, pointer &destp)
static bool isClear(const std::pair< S0, S1 > &v)
ArraySet< Key, MULTI, MAX_LOAD_FACTOR_256, Clearer, Hash, KeyEqual > set_type
#define UT_ASSERT_MSG(ZZ,...)
iterator erase(iterator iter)
void insert(INPUT_ITERATOR start_input, INPUT_ITERATOR end_input)
Inserts all of the items in the range [start_input,end_input).
iterator_t(pointer current, const_pointer end, bool scan=true)
static SYS_FORCE_INLINE bool isClear(TheType &v)
static size_type minBuckets(size_type size)
reference operator*() const
static void clearConstruct(std::pair< S0, S1 > *p)
void destroy()
Removes all items from the set and frees all the memory.
static bool isClear(S *v)
ArraySet(std::initializer_list< value_type > init, size_type init_bucket_count=0)
iterator begin()
Returns a non-const iterator for the beginning of the set.
set_type & operator=(const set_type &that)
set_type & operator=(std::initializer_list< value_type > init)
static key_equal key_eq()
static void clearConstruct(S **p)
void bumpNumBuckets(size_type new_num_items)
const_iterator cbegin() const
Returns a const iterator for the beginning of the set.
static SYS_FORCE_INLINE void clear(TheType &v)
GLboolean GLboolean GLboolean b
const_iterator cend() const
Returns a const end iterator for the set.
iterator find(const Key &key)
std::conditional< constant_type, const value_type, value_type >::type & reference
std::forward_iterator_tag iterator_category
int64 getMemoryUsage(bool inclusive) const
ArraySet(set_type &&that)
Move constructor, destroying the source.
size_type count(const Key &key) const
bool operator!=(const set_type &that) const
size_type bucket_size(size_type i) const
std::pair< iterator, bool > emplace(Args &&...args)
std::conditional< constant_type, const typename ArraySet::value_type, typename ArraySet::value_type >::type value_type
SYS_FORCE_INLINE void forEach(FUNCTOR &&functor) const
void insert(std::initializer_list< value_type > list)
Inserts all of the items from the initializer_list.
const value_type * const_pointer
const_pointer getEnd() const
std::pair< const_iterator, const_iterator > equal_range(const Key &key) const
ImageBuf OIIO_API max(Image_or_Const A, Image_or_Const B, ROI roi={}, int nthreads=0)
iterator_t< constant_type > & operator++()
void swap(set_type &that)
Swaps another set with this one.
const value_type & const_reference
pointer operator->() const
**If you just want to fire and args
static void clear(std::pair< S0, S1 > &v)
static size_type max_size()
void rehash(size_type new_num_buckets)
std::pair< iterator, iterator > equal_range(const Key &key)
static float max_load_factor()
std::conditional< constant_type, typename set_type::const_pointer, typename set_type::pointer >::type pointer
static hasher hash_function()
const_iterator begin() const
Returns a const iterator for the beginning of the set.
iterator_t< false > iterator
Iterator type for iterating over non-constant elements.
SIM_API const UT_StringHolder distance
bool operator!=(const iterator_t &that) const
bool contains(const Key &key) const
static SYS_FORCE_INLINE void clearConstruct(TheType *p)
size_type bucket_count() const
Returns the current number of buckets.
pointer searchStart(const Key &key)
const_iterator(const iterator &non_const_it)
bool operator==(const iterator_t &that) const
size_type erase(const Key &key)
ArraySet(INPUT_ITERATOR start_input, INPUT_ITERATOR end_input, size_type init_bucket_count=0)
Inserts all of the items in the range [start_input,end_input).
const_iterator end() const
Returns a const end iterator for the set.
bool operator==(const set_type &that) const
void reserve(size_type num_items)