[trafficserver] 05/08: IntrusiveHashMap: Update erase methods. Add additional iterator_for methods for erase.

[am...@apache.org]

This is an automated email from the ASF dual-hosted git repository.

amc pushed a commit to branch master
in repository https://gitbox.apache.org/repos/asf/trafficserver.git

commit 546a267efd94805f8c7655b4784c15fb31d3dc8e
Author: Alan M. Carroll <am...@apache.org>
AuthorDate: Sun Jul 22 21:25:15 2018 -0500

    IntrusiveHashMap: Update erase methods.
    Add additional iterator_for methods for erase.
---
 lib/ts/IntrusiveHashMap.h | 103 ++++++++++++++++++++++++++++++++++------------
 1 file changed, 76 insertions(+), 27 deletions(-)

diff --git a/lib/ts/IntrusiveHashMap.h b/lib/ts/IntrusiveHashMap.h
index c69a9a5..003326b 100644
--- a/lib/ts/IntrusiveHashMap.h
+++ b/lib/ts/IntrusiveHashMap.h
@@ -225,23 +225,30 @@ public:
 
   /** Get an @c iterator for the value @a v.
 
-      This is a bit obscure but needed in certain cases. It should only be used on a @a value that
-      is already known to be in the table.
+      This is a bit obscure but needed in certain cases. Because the interface assumes iterators are always valid
+      this avoid containment checks, which is useful if @a v is already known to be in the container.
    */
   iterator iterator_for(value_type *v);
+  const_iterator iterator_for(const value_type *v) const;
 
   /** Remove the value at @a loc from the table.
 
       @note This does @b not clean up the removed elements. Use carefully to avoid leaks.
 
-      @return @c true if the value was removed, @c false otherwise.
+      @return An iterator the next value past @a loc. [STL compatibility]
   */
-  bool erase(iterator const &loc);
+  iterator erase(iterator const &loc);
 
   /// Remove all elements in the @c range @a r.
-  bool erase(range const &r);
-  /// Remove all elements in the range (first, last]
-  bool erase(iterator const &first, iterator const &last);
+  iterator erase(range const &r);
+
+  /// Remove all elements in the range (start, limit]
+  iterator erase(iterator const &start, iterator const &limit);
+
+  /// Remove a @a value from the container.
+  /// @a value is checked for being a member of the container.
+  /// @return @c true if @a value was in the container and removed, @c false if it was not in the container.
+  bool erase(value_type *value);
 
   /** Apply @a F(value_type&) to every element in the hash map.
    *
@@ -479,6 +486,13 @@ IntrusiveHashMap<H>::equal_range(key_type key) const -> const_range
 
 template <typename H>
 auto
+IntrusiveHashMap<H>::iterator_for(const value_type *v) const -> const_iterator
+{
+  return _list.iterator_for(v);
+}
+
+template <typename H>
+auto
 IntrusiveHashMap<H>::iterator_for(value_type *v) -> iterator
 {
   return _list.iterator_for(v);
@@ -541,31 +555,66 @@ IntrusiveHashMap<H>::insert(value_type *v)
 }
 
 template <typename H>
-bool
-IntrusiveHashMap<H>::erase(iterator const &loc)
+auto
+IntrusiveHashMap<H>::erase(iterator const &loc) -> iterator
 {
-  bool zret = false;
+  value_type *v     = loc;
+  iterator zret     = ++(this->iterator_for(v)); // get around no const_iterator -> iterator.
+  Bucket *b         = this->bucket_for(H::key_of(v));
+  value_type *nv    = H::next_ptr(v);
+  value_type *limit = b->limit();
+  if (b->_v == v) {    // removed first element in bucket, update bucket
+    if (limit == nv) { // that was also the only element, deactivate bucket
+      _active_buckets.erase(b);
+      b->clear();
+    } else {
+      b->_v = nv;
+      --b->_count;
+    }
+  }
+  _list.erase(loc);
+  return zret;
+}
 
+template <typename H>
+bool
+IntrusiveHashMap<H>::erase(value_type *value)
+{
+  auto loc = this->find(value);
   if (loc != this->end()) {
-    value_type *v = &*loc;
-    Bucket *b     = this->bucket_for(H::key_of(v));
-    if (b->contains(v)) {
-      value_type *nv    = H::next_ptr(v);
-      value_type *limit = b->limit();
-      if (b->_v == v) {    // removed first element in bucket, update bucket
-        if (limit == nv) { // that was also the only element, deactivate bucket
-          _active_buckets.erase(b);
-          b->clear();
-        } else {
-          b->_v = nv;
-          --b->_count;
-        }
-      }
-      zret = true;
-      _list.erase(v);
+    this->erase(loc);
+    return true;
+  }
+  return false;
+}
+
+template <typename H>
+auto
+IntrusiveHashMap<H>::erase(iterator const &start, iterator const &limit) -> iterator
+{
+  auto spot{start};
+  Bucket *bucket{this->bucket_for(spot)};
+  while (spot != limit) {
+    auto target         = bucket;
+    bucket              = bucket->_link._next; // bump now to avoid forward iteration problems in case of bucket removal.
+    value_type *v_limit = bucket ? bucket->_v : nullptr;
+    while (spot != v_limit && spot != limit) {
+      --(target->_count);
+      ++spot;
+    }
+    if (target->_count == 0) {
+      _active_buckets.erase(target);
     }
   }
-  return zret;
+  _list.erase(start, limit);
+  return _list.iterator_for(limit); // convert from const_iterator back to iterator
+};
+
+template <typename H>
+auto
+IntrusiveHashMap<H>::erase(range const &r) -> iterator
+{
+  return this->erase(r.first, r.second);
 }
 
 template <typename H>