[Bf-blender-cvs] [b0034fd7a27] functions: more comments
Jacques Lucke
noreply at git.blender.org
Wed Aug 21 18:24:54 CEST 2019
Commit: b0034fd7a279716aa30b7606c53615c60ae8db5a
Author: Jacques Lucke
Date: Wed Aug 21 18:24:05 2019 +0200
Branches: functions
https://developer.blender.org/rBb0034fd7a279716aa30b7606c53615c60ae8db5a
more comments
===================================================================
M source/blender/blenlib/BLI_listbase_wrapper.hpp
M source/blender/blenlib/BLI_map.hpp
M source/blender/blenlib/BLI_open_addressing.hpp
===================================================================
diff --git a/source/blender/blenlib/BLI_listbase_wrapper.hpp b/source/blender/blenlib/BLI_listbase_wrapper.hpp
index fdf58d2bbf1..90755d551b1 100644
--- a/source/blender/blenlib/BLI_listbase_wrapper.hpp
+++ b/source/blender/blenlib/BLI_listbase_wrapper.hpp
@@ -17,9 +17,8 @@
/** \file
* \ingroup bli
*
- * The purpose of this wrapper is just to make it more
- * comfortable to iterate of ListBase instances, that
- * are used in many places in Blender.
+ * The purpose of this wrapper is just to make it more comfortable to iterate of ListBase
+ * instances, that are used in many places in Blender.
*/
#pragma once
diff --git a/source/blender/blenlib/BLI_map.hpp b/source/blender/blenlib/BLI_map.hpp
index 6d30a87f6f0..c7d2a0ef581 100644
--- a/source/blender/blenlib/BLI_map.hpp
+++ b/source/blender/blenlib/BLI_map.hpp
@@ -17,9 +17,10 @@
/** \file
* \ingroup bli
*
- * An unordered map implementation with small object optimization.
- * Similar to Set, this builds on top of Vector
- * and ArrayLookup to reduce what this code has to deal with.
+ * This file provides a map implementation that uses open addressing with probing.
+ *
+ * The key and value objects are stored directly in the hash table to avoid indirect memory
+ * lookups. Keys and values are stored in groups of four to avoid wasting memory due to padding.
*/
#pragma once
@@ -166,6 +167,10 @@ template<typename KeyT, typename ValueT, typename Allocator = GuardedAllocator>
public:
Map() = default;
+ /**
+ * Insert a new key-value-pair in the map.
+ * Asserts when the key existed before.
+ */
void add_new(const KeyT &key, const ValueT &value)
{
BLI_assert(!this->contains(key));
@@ -181,6 +186,10 @@ template<typename KeyT, typename ValueT, typename Allocator = GuardedAllocator>
ITER_SLOTS_END(offset);
}
+ /**
+ * Insert a new key-value-pair in the map if the key does not exist yet.
+ * Returns true when the pair was newly inserted, otherwise false.
+ */
bool add(const KeyT &key, const ValueT &value)
{
this->ensure_can_add();
@@ -198,6 +207,10 @@ template<typename KeyT, typename ValueT, typename Allocator = GuardedAllocator>
ITER_SLOTS_END(offset);
}
+ /**
+ * Remove the key from the map.
+ * Asserts when the key does not exist in the map.
+ */
void remove(const KeyT &key)
{
BLI_assert(this->contains(key));
@@ -211,6 +224,10 @@ template<typename KeyT, typename ValueT, typename Allocator = GuardedAllocator>
ITER_SLOTS_END(offset);
}
+ /**
+ * Get the value for the given key and remove it from the map.
+ * Asserts when the key does not exist in the map.
+ */
ValueT pop(const KeyT &key)
{
BLI_assert(this->contains(key));
@@ -225,6 +242,9 @@ template<typename KeyT, typename ValueT, typename Allocator = GuardedAllocator>
ITER_SLOTS_END(offset);
}
+ /**
+ * Returns true when the key exists in the map, otherwise false.
+ */
bool contains(const KeyT &key) const
{
ITER_SLOTS_BEGIN (key, m_array, const, item, offset) {
@@ -238,6 +258,12 @@ template<typename KeyT, typename ValueT, typename Allocator = GuardedAllocator>
ITER_SLOTS_END(offset);
}
+ /**
+ * Check if the key exists in the map.
+ * If it does exist, call the modify function with a reference to the corresponding value.
+ * If it does not exist, call the create function and insert a new key-value-pair.
+ * Returns true when a new pair was inserted, otherwise false.
+ */
template<typename CreateValueF, typename ModifyValueF>
bool add_or_modify(const KeyT &key,
const CreateValueF &create_value,
@@ -259,12 +285,20 @@ template<typename KeyT, typename ValueT, typename Allocator = GuardedAllocator>
ITER_SLOTS_END(offset);
}
+ /**
+ * Similar to add, but overrides the value for the key when it exists already.
+ */
bool add_override(const KeyT &key, const ValueT &value)
{
return this->add_or_modify(
key, [&value]() { return value; }, [&value](ValueT &old_value) { old_value = value; });
}
+ /**
+ * Check if the key exists in the map.
+ * Return a pointer to the value, when it exists.
+ * Otherwise return nullptr.
+ */
const ValueT *lookup_ptr(const KeyT &key) const
{
ITER_SLOTS_BEGIN (key, m_array, const, item, offset) {
@@ -278,9 +312,15 @@ template<typename KeyT, typename ValueT, typename Allocator = GuardedAllocator>
ITER_SLOTS_END(offset);
}
+ /**
+ * Lookup the value that corresponds to the key.
+ * Asserts when the key does not exist.
+ */
const ValueT &lookup(const KeyT &key) const
{
- return *this->lookup_ptr(key);
+ const ValueT *ptr = this->lookup_ptr(key);
+ BLI_assert(ptr != nullptr);
+ return *ptr;
}
ValueT *lookup_ptr(const KeyT &key)
@@ -295,6 +335,11 @@ template<typename KeyT, typename ValueT, typename Allocator = GuardedAllocator>
return const_cast<ValueT &>(const_this->lookup(key));
}
+ /**
+ * Check if the key exists in the map.
+ * If it does, return a copy of the value.
+ * Otherwise, return the default value.
+ */
ValueT lookup_default(const KeyT &key, ValueT default_value) const
{
ValueT *ptr = this->lookup_ptr(key);
@@ -306,6 +351,10 @@ template<typename KeyT, typename ValueT, typename Allocator = GuardedAllocator>
}
}
+ /**
+ * Return the value that corresponds to the given key.
+ * If it does not exist yet, create and insert it first.
+ */
template<typename CreateValueF>
ValueT &lookup_or_add(const KeyT &key, const CreateValueF &create_value)
{
@@ -324,6 +373,9 @@ template<typename KeyT, typename ValueT, typename Allocator = GuardedAllocator>
ITER_SLOTS_END(offset);
}
+ /**
+ * Get the number of elements in the map.
+ */
uint32_t size() const
{
return m_array.slots_set();
@@ -455,16 +507,26 @@ template<typename KeyT, typename ValueT, typename Allocator = GuardedAllocator>
template<typename SubIterator> friend class BaseIterator;
+ /**
+ * Iterate over all keys in the map.
+ */
KeyIterator keys() const
{
return KeyIterator(this, 0);
}
+ /**
+ * Iterate over all values in the map.
+ */
ValueIterator values() const
{
return ValueIterator(this, 0);
}
+ /**
+ * Iterate over all key-value-pairs in the map.
+ * They can be accessed with item.key and item.value.
+ */
ItemIterator items() const
{
return ItemIterator(this, 0);
diff --git a/source/blender/blenlib/BLI_open_addressing.hpp b/source/blender/blenlib/BLI_open_addressing.hpp
index 9ce63603469..4be129ce311 100644
--- a/source/blender/blenlib/BLI_open_addressing.hpp
+++ b/source/blender/blenlib/BLI_open_addressing.hpp
@@ -1,3 +1,33 @@
+/*
+ * This program is free software; you can redistribute it and/or
+ * modify it under the terms of the GNU General Public License
+ * as published by the Free Software Foundation; either version 2
+ * of the License, or (at your option) any later version.
+ *
+ * This program is distributed in the hope that it will be useful,
+ * but WITHOUT ANY WARRANTY; without even the implied warranty of
+ * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the
+ * GNU General Public License for more details.
+ *
+ * You should have received a copy of the GNU General Public License
+ * along with this program; if not, write to the Free Software Foundation,
+ * Inc., 51 Franklin Street, Fifth Floor, Boston, MA 02110-1301, USA.
+ */
+
+/** \file
+ * \ingroup bli
+ *
+ * This class offers a useful abstraction for other containers that implement hash tables using
+ * open addressing. It handles the following aspects:
+ * - Allocation and deallocation of the open addressing array.
+ * - Optional small object optimization.
+ * - Keeps track of how many elements and dummies are in the table.
+ *
+ * The nice thing about this abstraction is that it does not get in the way of any performance
+ * optimizations. The data that is actually stored in the table is still fully defined by the
+ * actual hash table implementation.
+ */
+
#pragma once
#include "BLI_utildefines.h"
More information about the Bf-blender-cvs
mailing list