StableSeq

[demotomohiro]

In this `StableSeq`, `[]` do only one pointer dereference and it is O(1) if 
`fastLog2` is O(1). `sizeof(StableSeq)` become bigger as it contains `array[N, 
ptr UncheckedArray]` but its length can be reduced by making `log2MinCap` to 
constant and reducing the length according to `log2MinCap`.
    
    
    import std/[bitops, math]
    
    type
      StableSeq*[T] = object
        len, log2MinCap: int
        chunks: array[sizeof(pointer) * 8, ptr UncheckedArray[T]] # or seq[ptr 
UncheckedArray[T]] to make StableSeq smaller
    
    proc createChunk[T](cap: int): ptr UncheckedArray[T] {.inline.} =
      cast[ptr UncheckedArray[T]](alloc0(sizeof(T) * cap))
    
    proc createStableSeq*[T](cap = 8): StableSeq[T] =
      # fastLog2(0) can be undefined!
      doAssert cap > 1
      let cap2 = nextPowerOfTwo(cap)
      result = StableSeq[T](log2MinCap: cap2.fastLog2)
      result.chunks[0] = createChunk[T](cap2)
    
    proc destroy*[T](s: StableSeq[T]) =
      var i = 0
      while s.chunks[i] != nil and i <= s.chunks.high:
        dealloc s.chunks[i]
        inc i
    
    func chunkIdAndOffset[T](s: StableSeq[T]; i: int): tuple[chunk, offset: 
int] {.inline.} =
      if i == 0:
        (0, 0)
      else:
        let
          lg2 = i.fastLog2
          chunkId = max(lg2 - s.log2MinCap + 1, 0)
        (chunkId, if chunkId == 0: i else: (i and ((1 shl lg2) - 1)))
    
    proc append*[T](s: var StableSeq[T]; data: sink T): ptr T =
      let (chunkId, offset) = s.chunkIdAndOffset(s.len)
      if s.len.isPowerOfTwo and chunkId > 0:
        if s.chunks[chunkId] == nil:
          s.chunks[chunkId] = createChunk[T](s.len)
      
      result = addr s.chunks[chunkId][offset]
      result[] = ensureMove data
      inc s.len
    
    proc add*[T](s: var StableSeq[T]; data: sink T) =
      discard append(s, data)
    
    iterator items*[T](s: StableSeq[T]): lent T =
      block exitIter:
        var
          i, c = 0
          l = 1 shl s.log2MinCap
        while i <= s.chunks.high:
          for j in 0 ..< l:
            yield s.chunks[i][j]
            inc c
            if c == s.len:
              break exitIter
          if i != 0:
            l *= 2
          inc i
    
    proc `[]`*[T](s: var StableSeq[T]; index: int): var T =
      if index < s.len:
        let (chunkId, offset) = s.chunkIdAndOffset(index)
        assert s.chunks[chunkId] != nil
        return s.chunks[chunkId][offset]
      else:
        raise newException(IndexDefect, "index out of bounds")
    
    proc `[]`*[T](s: StableSeq[T]; index: int): lent T =
      if index < s.len:
        let (chunkId, offset) = s.chunkIdAndOffset(index)
        assert s.chunks[chunkId] != nil
        return s.chunks[chunkId][offset]
      else:
        raise newException(IndexDefect, "index out of bounds")
    
    proc `[]=`*[T](s: var StableSeq[T]; index: int; elem: sink T) =
      if index < s.len:
        let (chunkId, offset) = s.chunkIdAndOffset(index)
        assert s.chunks[chunkId] != nil
        s.chunks[chunkId][offset] = elem
      else:
        raise newException(IndexDefect, "index out of bounds")
    
    when isMainModule:
      for i in 1 .. 8:
        var s = createStableSeq[int](1 shl i)
        for j in 0 ..< 100:
          discard s.append j
        
        for j in 0 ..< 100:
          doAssert s[j] == j
        
        var j = 0
        for elem in s:
          doAssert elem == j
          inc j
        
        destroy s
    
    Run