From c90e94b70c69f14bcf02fe41b7ba1969b38c7da8 Mon Sep 17 00:00:00 2001
From: Alex Ainscow <aainscow@uk.ibm.com>
Date: Wed, 8 Jan 2025 22:16:49 +0000
Subject: [PATCH] interval_set: Enhancements to improve efficiency of insert()
 and to allow more flexibility.

The old insert was restrictive in ranges that could be added in. The new interface allows for a range to be added, whether it extends or joins other intervals.

Also change a number of interfaces to use the new insert.

Signed-off-by: Alex Ainscow <aainscow@uk.ibm.com>
---
 src/include/interval_set.h | 105 ++++++++++++++++---------------------
 1 file changed, 44 insertions(+), 61 deletions(-)

diff --git a/src/include/interval_set.h b/src/include/interval_set.h
index 2e2e47e0d3459..6372b35f818a4 100644
--- a/src/include/interval_set.h
+++ b/src/include/interval_set.h
@@ -495,58 +495,55 @@ class interval_set {
 
   void insert(T start, T len, T *pstart=0, T *plen=0) {
     //cout << "insert " << start << "~" << len << endl;
-    ceph_assert(len > 0);
-    _size += len;
+    T new_len = len;
     auto p = find_adj_m(start);
-    if (p == m.end()) {
+    auto o = std::pair(start, len);
+    T end = start+len;
+
+    if(len == 0) {
+      if (p != m.end() && start >= p->first && start < p->first + p->second) {
+        o = *p;
+      }
+    } else if (p == m.end()) {
       m[start] = len;                  // new interval
-      if (pstart)
-	*pstart = start;
-      if (plen)
-	*plen = len;
     } else {
       if (p->first < start) {
-        
-        if (p->first + p->second != start) {
-          //cout << "p is " << p->first << "~" << p->second << ", start is " << start << ", len is " << len << endl;
-          ceph_abort();
-        }
-        
-        p->second += len;               // append to end
-        
+        T pend = p->first + p->second;
+        new_len = new_len - (std::min(pend, end) - start); // Remove the overlap
+        p->second = std::max(pend, end) - p->first; // Adjust existing
+
+        // Some usages of interval_set do not implement the + operator.
         auto n = p;
         ++n;
-	if (pstart)
-	  *pstart = p->first;
-        if (n != m.end() && 
-            start+len == n->first) {   // combine with next, too!
-          p->second += n->second;
-	  if (plen)
-	    *plen = p->second;
-          m.erase(n);
-        } else {
-	  if (plen)
-	    *plen = p->second;
-	}
+        for (; n != m.end() && end >= n->first; n = m.erase(n)) {
+          // The follow is split out to avoid template issues.
+          // This adds the part of n which is not overlapping with the insert.
+          T a = n->second;
+          T b = end - n->first;
+          new_len = new_len - std::min(a, b);
+          p->second += n->second - std::min(a, b);
+        }
+
+        o = *p;
       } else {
-        if (start+len == p->first) {
-	  if (pstart)
-	    *pstart = start;
-	  if (plen)
-	    *plen = len + p->second;
-	  T psecond = p->second;
-          m.erase(p);
-          m[start] = len + psecond;  // append to front
-        } else {
-          ceph_assert(p->first > start+len);
-	  if (pstart)
-	    *pstart = start;
-	  if (plen)
-	    *plen = len;
-          m[start] = len;              // new interval
+        T old_len = 0;
+        T new_end = end;
+        for (;p != m.end() && end >= p->first; p = m.erase(p)) {
+          T pend = p->first + p->second;
+          new_end = std::max(pend, end);
+          old_len = old_len + p->second;
         }
+        m[start] = o.second = new_end - start;
+        new_len = o.second - old_len;
       }
     }
+
+    _size += new_len;
+
+    if (pstart)
+      *pstart = o.first;
+    if (plen)
+      *plen = o.second;
   }
 
   void swap(interval_set& other) {
@@ -677,31 +674,17 @@ class interval_set {
     ceph_assert(&a != this);
     ceph_assert(&b != this);
     clear();
-    
-    //cout << "union_of" << endl;
-
-    // a
-    m = a.m;
-    _size = a._size;
-
-    // - (a*b)
-    interval_set ab;
-    ab.intersection_of(a, b);
-    subtract(ab);
 
-    // + b
+    insert(a);
     insert(b);
-    return;
   }
+
   void union_of(const interval_set &b) {
-    interval_set a;
-    swap(a);    
-    union_of(a, b);
+    insert(b);
   }
   void union_insert(T off, T len) {
-    interval_set a;
-    a.insert(off, len);
-    union_of(a);
+    // insert supports overlapping entries. This function is redundant.
+    insert(off, len);
   }
 
   bool subset_of(const interval_set &big) const {
-- 
2.39.5