Remove count field from Deque (#23318)

This PR removes `count` field from `Deque` and get `count` from `tail -
head`.

1 files changed, 46 insertions, 51 deletions

diff --git a/lib/pure/collections/deques.nim b/lib/pure/collections/deques.nim
index a26078887..d2b0099f2 100644
--- a/lib/pure/collections/deques.nim
+++ b/lib/pure/collections/deques.nim
@@ -50,7 +50,7 @@ runnableExamples:
 
 import std/private/since
 
-import std/[hashes, math]
+import std/[assertions, hashes, math]
 
 type
   Deque*[T] = object
@@ -59,7 +59,14 @@ type
     ## To initialize an empty deque,
     ## use the `initDeque proc <#initDeque,int>`_.
     data: seq[T]
-    head, tail, count: int
+
+    # `head` and `tail` are masked only when accessing an element of `data`
+    # so that `tail - head == data.len` when the deque is full.
+    # They are uint so that incrementing/decrementing them doesn't cause
+    # over/underflow. You can get a number of items with `tail - head`
+    # even if `tail` or `head` is wraps around and `tail < head`, because
+    # `tail - head == (uint.high + 1 + tail) - head` when `tail < head`.
+    head, tail: uint
 
 const
   defaultInitialSize* = 4
@@ -72,8 +79,8 @@ template checkIfInitialized(deq: typed) =
   if deq.data.len == 0:
     initImpl(deq, defaultInitialSize)
 
-func mask[T](deq: Deque[T]): int {.inline.} =
-  deq.data.len - 1
+func mask[T](deq: Deque[T]): uint {.inline.} =
+  uint(deq.data.len) - 1
 
 proc initDeque*[T](initialSize: int = defaultInitialSize): Deque[T] =
   ## Creates a new empty deque.
@@ -87,22 +94,22 @@ proc initDeque*[T](initialSize: int = defaultInitialSize): Deque[T] =
   ## * `toDeque proc <#toDeque,openArray[T]>`_
   result.initImpl(initialSize)
 
-proc len*[T](deq: Deque[T]): int {.inline.} =
+func len*[T](deq: Deque[T]): int {.inline.} =
   ## Returns the number of elements of `deq`.
-  result = deq.count
+  int(deq.tail - deq.head)
 
 template emptyCheck(deq) =
   # Bounds check for the regular deque access.
   when compileOption("boundChecks"):
-    if unlikely(deq.count < 1):
+    if unlikely(deq.len < 1):
       raise newException(IndexDefect, "Empty deque.")
 
 template xBoundsCheck(deq, i) =
   # Bounds check for the array like accesses.
   when compileOption("boundChecks"): # `-d:danger` or `--checks:off` should disable this.
-    if unlikely(i >= deq.count): # x < deq.low is taken care by the Natural parameter
+    if unlikely(i >= deq.len): # x < deq.low is taken care by the Natural parameter
       raise newException(IndexDefect,
-                         "Out of bounds: " & $i & " > " & $(deq.count - 1))
+                         "Out of bounds: " & $i & " > " & $(deq.len - 1))
     if unlikely(i < 0): # when used with BackwardsIndex
       raise newException(IndexDefect,
                          "Out of bounds: " & $i & " < 0")
@@ -116,7 +123,7 @@ proc `[]`*[T](deq: Deque[T], i: Natural): lent T {.inline.} =
     doAssertRaises(IndexDefect, echo a[8])
 
   xBoundsCheck(deq, i)
-  return deq.data[(deq.head + i) and deq.mask]
+  return deq.data[(deq.head + i.uint) and deq.mask]
 
 proc `[]`*[T](deq: var Deque[T], i: Natural): var T {.inline.} =
   ## Accesses the `i`-th element of `deq` and returns a mutable
@@ -127,7 +134,7 @@ proc `[]`*[T](deq: var Deque[T], i: Natural): var T {.inline.} =
     assert a[0] == 11
 
   xBoundsCheck(deq, i)
-  return deq.data[(deq.head + i) and deq.mask]
+  return deq.data[(deq.head + i.uint) and deq.mask]
 
 proc `[]=`*[T](deq: var Deque[T], i: Natural, val: sink T) {.inline.} =
   ## Sets the `i`-th element of `deq` to `val`.
@@ -139,7 +146,7 @@ proc `[]=`*[T](deq: var Deque[T], i: Natural, val: sink T) {.inline.} =
 
   checkIfInitialized(deq)
   xBoundsCheck(deq, i)
-  deq.data[(deq.head + i) and deq.mask] = val
+  deq.data[(deq.head + i.uint) and deq.mask] = val
 
 proc `[]`*[T](deq: Deque[T], i: BackwardsIndex): lent T {.inline.} =
   ## Accesses the backwards indexed `i`-th element.
@@ -192,10 +199,8 @@ iterator items*[T](deq: Deque[T]): lent T =
     let a = [10, 20, 30, 40, 50].toDeque
     assert toSeq(a.items) == @[10, 20, 30, 40, 50]
 
-  var i = deq.head
-  for c in 0 ..< deq.count:
-    yield deq.data[i]
-    i = (i + 1) and deq.mask
+  for c in 0 ..< deq.len:
+    yield deq.data[(deq.head + c.uint) and deq.mask]
 
 iterator mitems*[T](deq: var Deque[T]): var T =
   ## Yields every element of `deq`, which can be modified.
@@ -209,10 +214,8 @@ iterator mitems*[T](deq: var Deque[T]): var T =
       x = 5 * x - 1
     assert $a == "[49, 99, 149, 199, 249]"
 
-  var i = deq.head
-  for c in 0 ..< deq.count:
-    yield deq.data[i]
-    i = (i + 1) and deq.mask
+  for c in 0 ..< deq.len:
+    yield deq.data[(deq.head + c.uint) and deq.mask]
 
 iterator pairs*[T](deq: Deque[T]): tuple[key: int, val: T] =
   ## Yields every `(position, value)`-pair of `deq`.
@@ -222,10 +225,8 @@ iterator pairs*[T](deq: Deque[T]): tuple[key: int, val: T] =
     let a = [10, 20, 30].toDeque
     assert toSeq(a.pairs) == @[(0, 10), (1, 20), (2, 30)]
 
-  var i = deq.head
-  for c in 0 ..< deq.count:
-    yield (c, deq.data[i])
-    i = (i + 1) and deq.mask
+  for c in 0 ..< deq.len:
+    yield (c, deq.data[(deq.head + c.uint) and deq.mask])
 
 proc contains*[T](deq: Deque[T], item: T): bool {.inline.} =
   ## Returns true if `item` is in `deq` or false if not found.
@@ -244,8 +245,9 @@ proc contains*[T](deq: Deque[T], item: T): bool {.inline.} =
 
 proc expandIfNeeded[T](deq: var Deque[T]) =
   checkIfInitialized(deq)
-  var cap = deq.data.len
-  if unlikely(deq.count >= cap):
+  let cap = deq.data.len
+  assert deq.len <= cap
+  if unlikely(deq.len == cap):
     var n = newSeq[T](cap * 2)
     var i = 0
     for x in mitems(deq):
@@ -253,7 +255,7 @@ proc expandIfNeeded[T](deq: var Deque[T]) =
       else: n[i] = move(x)
       inc i
     deq.data = move(n)
-    deq.tail = deq.count
+    deq.tail = cap.uint
     deq.head = 0
 
 proc addFirst*[T](deq: var Deque[T], item: sink T) =
@@ -268,9 +270,8 @@ proc addFirst*[T](deq: var Deque[T], item: sink T) =
     assert $a == "[50, 40, 30, 20, 10]"
 
   expandIfNeeded(deq)
-  inc deq.count
-  deq.head = (deq.head - 1) and deq.mask
-  deq.data[deq.head] = item
+  dec deq.head
+  deq.data[deq.head and deq.mask] = item
 
 proc addLast*[T](deq: var Deque[T], item: sink T) =
   ## Adds an `item` to the end of `deq`.
@@ -284,9 +285,8 @@ proc addLast*[T](deq: var Deque[T], item: sink T) =
     assert $a == "[10, 20, 30, 40, 50]"
 
   expandIfNeeded(deq)
-  inc deq.count
-  deq.data[deq.tail] = item
-  deq.tail = (deq.tail + 1) and deq.mask
+  deq.data[deq.tail and deq.mask] = item
+  inc deq.tail
 
 proc toDeque*[T](x: openArray[T]): Deque[T] {.since: (1, 3).} =
   ## Creates a new deque that contains the elements of `x` (in the same order).
@@ -315,7 +315,7 @@ proc peekFirst*[T](deq: Deque[T]): lent T {.inline.} =
     assert len(a) == 5
 
   emptyCheck(deq)
-  result = deq.data[deq.head]
+  result = deq.data[deq.head and deq.mask]
 
 proc peekLast*[T](deq: Deque[T]): lent T {.inline.} =
   ## Returns the last element of `deq`, but does not remove it from the deque.
@@ -345,7 +345,7 @@ proc peekFirst*[T](deq: var Deque[T]): var T {.inline, since: (1, 3).} =
     assert $a == "[99, 20, 30, 40, 50]"
 
   emptyCheck(deq)
-  result = deq.data[deq.head]
+  result = deq.data[deq.head and deq.mask]
 
 proc peekLast*[T](deq: var Deque[T]): var T {.inline, since: (1, 3).} =
   ## Returns a mutable reference to the last element of `deq`,
@@ -378,9 +378,8 @@ proc popFirst*[T](deq: var Deque[T]): T {.inline, discardable.} =
     assert $a == "[20, 30, 40, 50]"
 
   emptyCheck(deq)
-  dec deq.count
-  result = move deq.data[deq.head]
-  deq.head = (deq.head + 1) and deq.mask
+  result = move deq.data[deq.head and deq.mask]
+  inc deq.head
 
 proc popLast*[T](deq: var Deque[T]): T {.inline, discardable.} =
   ## Removes and returns the last element of the `deq`.
@@ -395,9 +394,8 @@ proc popLast*[T](deq: var Deque[T]): T {.inline, discardable.} =
     assert $a == "[10, 20, 30, 40]"
 
   emptyCheck(deq)
-  dec deq.count
-  deq.tail = (deq.tail - 1) and deq.mask
-  result = move deq.data[deq.tail]
+  dec deq.tail
+  result = move deq.data[deq.tail and deq.mask]
 
 proc clear*[T](deq: var Deque[T]) {.inline.} =
   ## Resets the deque so that it is empty.
@@ -411,7 +409,6 @@ proc clear*[T](deq: var Deque[T]) {.inline.} =
     assert len(a) == 0
 
   for el in mitems(deq): destroy(el)
-  deq.count = 0
   deq.tail = deq.head
 
 proc shrink*[T](deq: var Deque[T], fromFirst = 0, fromLast = 0) =
@@ -431,19 +428,17 @@ proc shrink*[T](deq: var Deque[T], fromFirst = 0, fromLast = 0) =
     a.shrink(fromFirst = 2, fromLast = 1)
     assert $a == "[30, 40]"
 
-  if fromFirst + fromLast > deq.count:
+  if fromFirst + fromLast > deq.len:
     clear(deq)
     return
 
   for i in 0 ..< fromFirst:
-    destroy(deq.data[deq.head])
-    deq.head = (deq.head + 1) and deq.mask
+    destroy(deq.data[deq.head and deq.mask])
+    inc deq.head
 
   for i in 0 ..< fromLast:
     destroy(deq.data[(deq.tail - 1) and deq.mask])
-    deq.tail = (deq.tail - 1) and deq.mask
-
-  dec deq.count, fromFirst + fromLast
+    dec deq.tail
 
 proc `$`*[T](deq: Deque[T]): string =
   ## Turns a deque into its string representation.
@@ -468,11 +463,11 @@ func `==`*[T](deq1, deq2: Deque[T]): bool =
     b.addLast(2)
     doAssert a == b
 
-  if deq1.count != deq2.count:
+  if deq1.len != deq2.len:
     return false
 
-  for i in 0 ..< deq1.count:
-    if deq1.data[(deq1.head + i) and deq1.mask] != deq2.data[(deq2.head + i) and deq2.mask]:
+  for i in 0 ..< deq1.len:
+    if deq1.data[(deq1.head + i.uint) and deq1.mask] != deq2.data[(deq2.head + i.uint) and deq2.mask]:
       return false
 
   true