Better terms github/erikj/chunks_backwards erikj/chunks_backwards

1 files changed, 24 insertions, 53 deletions

diff --git a/synapse/storage/chunk_ordered_table.py b/synapse/storage/chunk_ordered_table.py
index 2809b10ec3..586b19b280 100644
--- a/synapse/storage/chunk_ordered_table.py
+++ b/synapse/storage/chunk_ordered_table.py
@@ -393,7 +393,8 @@ class ChunkDBOrderedListStore(OrderedListStore):
         old_order = self._get_order(node_id)
 
         a, b, c, d = find_farey_terms(old_order, self.rebalance_md)
-        n = max(b, d)
+        assert old_order < Fraction(a, b)
+        assert c + d > self.rebalance_md
 
         with_sql = """
             WITH RECURSIVE chunks (chunk_id, next, n, a, b, c, d) AS (
@@ -427,46 +428,24 @@ class ChunkDBOrderedListStore(OrderedListStore):
             """
 
         self.txn.execute(sql, (
-            n, a, b, c, d, node_id
+            self.rebalance_md, a, b, c, d, node_id
         ))
 
         rebalance_counter.inc()
 
 
-def stern_brocot_range(n, min_frac, max_frac):
-    assert 0 < min_frac < max_frac
-
-    states = deque([(0, 1, 1, 0)])
-
-    result = []
-
-    while len(result) < n:
-        a, b, c, d = states.popleft()
-
-        f = (a + c) / float(b + d)
-        if f < min_frac:
-            states.append((a + c, b + d, c, d))
-
-        elif min_frac <= f <= max_frac:
-            states.append((a, b, a + c, b + d))
-            states.append((a + c, b + d, c, d))
-
-            result.append(Fraction(a + c, b + d))
-        else:
-            states.append((a, b, a + c, b + d))
-
-    return result
-
-
 def stern_brocot_single(min_frac, max_frac):
     assert 0 <= min_frac < max_frac
 
-    denom = (
+    # If the determinant is 1 then the fraction with smallest numerator and
+    # denominator in the range is the mediant, so we don't have to use the
+    # stern brocot tree to search for it.
+    determinant = (
         min_frac.denominator * max_frac.numerator
         - min_frac.numerator * max_frac.denominator
     )
 
-    if denom == 1:
+    if determinant == 1:
         return Fraction(
             min_frac.numerator + max_frac.numerator,
             min_frac.denominator + max_frac.denominator,
@@ -486,29 +465,21 @@ def stern_brocot_single(min_frac, max_frac):
 
 
 def find_farey_terms(min_frac, max_denom):
-    states = deque([(0, 1, 1, 0)])
+    a, b, c, d =  0, 1, 1, 0
 
     while True:
-        a, b, c, d = states.popleft()
-
-        left = a / float(b)
-        mid = (a + c) / float(b + d)
-        right = c / float(d) if d > 0 else None
-
-        if min_frac < left:
-            if b >= max_denom or d >= max_denom:
-                return a, b, c, d
-            if b + d >= max_denom:
-                return a + c, b + d, c, d
-
-            states.append((a, b, a + c, b + d))
-        elif min_frac < mid:
-            if b + d >= max_denom:
-                return a + c, b + d, c, d
-
-            states.append((a, b, a + c, b + d))
-            states.append((a + c, b + d, c, d))
-        elif right is None or min_frac < right:
-            states.append((a + c, b + d, c, d))
-        else:
-            states.append((a + c, b + d, c, d))
+        cur_frac = Fraction(a + c, b + d)
+
+        if b + d > max_denom:
+            break
+
+        if cur_frac <= min_frac:
+            a, b, c, d = a + c, b + d, c, d
+        elif min_frac < cur_frac:
+            a, b, c, d = a, b, a + c, b + d
+
+    if Fraction(a, b) <= min_frac:
+        k = int((max_denom + b) / d)
+        a, b, c, d = c, d, (k*c-a), (k*d-b)
+
+    return a, b, c, d