boltdb源码分析系列-迭代器

type Cursor struct {
 bucket *Bucket
 stack  []elemRef
}

type elemRef struct {
 page  *page
 node  *node
 index int
}

func (c *Cursor) First() (key []byte, value []byte) {
 _assert(c.bucket.tx.db != nil, "tx closed")
 // 重置stack
 c.stack = c.stack[:0]
 // 加载根节点
 p, n := c.bucket.pageNode(c.bucket.root)
 // 根节点信息加入stack
 c.stack = append(c.stack, elemRef{page: p, node: n, index: 0})
 // 一路向下走到第一个叶子节点，内部通过for循环走到最左侧的叶子节点
 c.first()

 // https://github.com/boltdb/bolt/issues/450
 // 叶子节点中没有元素，移动到下一个叶子节点
 if c.stack[len(c.stack)-1].count() == 0 {
  c.next()
 }
    // 获取最左侧叶子节点中的第一个key-value
 k, v, flags := c.keyValue()
 // 如果是一个桶节点，value为空
 if (flags & uint32(bucketLeafFlag)) != 0 {
  return k, nil
 }
 // 存储的是数据，返回key-value
 return k, v

}

func (c *Cursor) Last() (key []byte, value []byte) {
 _assert(c.bucket.tx.db != nil, "tx closed")
 c.stack = c.stack[:0]
 // 加载根节点
 p, n := c.bucket.pageNode(c.bucket.root)
 ref := elemRef{page: p, node: n}
 // 设置index为最后一个元素位置
 ref.index = ref.count() - 1
 // 加入路径缓存stack
 c.stack = append(c.stack, ref)
 // 一路向下走到最右侧的节点
 c.last()
 // 获取游标位置（最右边节点的最后一个）元素
 k, v, flags := c.keyValue()
 // 如果是Bucket，返回value为空
 if (flags & uint32(bucketLeafFlag)) != 0 {
  return k, nil
 }
 // 返回key-value
 return k, v
}

func (c *Cursor) Next() (key []byte, value []byte) {
 _assert(c.bucket.tx.db != nil, "tx closed")
 k, v, flags := c.next()
 if (flags & uint32(bucketLeafFlag)) != 0 {
  return k, nil
 }
 return k, v
}

func (c *Cursor) next() (key []byte, value []byte, flags uint32) {
 for {
  var i int
  // 切片c.stack中保存的是访问的前缀信息，i从大到小循环，先处理游标最后位置
  // 先在节点内部找到下一个元素，如果节点内部元素已全部访问完，i--走到下一个节点
  for i = len(c.stack) - 1; i >= 0; i-- {
   elem := &c.stack[i]
   // 移动到节点中的下一个元素
   if elem.index < elem.count()-1 {
    elem.index++
    break
   }
  }

  // i为-1说明整颗树已经处理完了
  if i == -1 {
   return nil, nil, 0
  }

  // 清理掉已经处理过的节点，保留剩下未访问处理的
  c.stack = c.stack[:i+1]
  // 定位到剩下未处理完成的节点，c.stack[i]即为待处理的节点
  // c.stack[i].index已经定位到节点中位置
  c.first()

  // https://github.com/boltdb/bolt/issues/450
  // 节点中没有数据，跳出
  if c.stack[len(c.stack)-1].count() == 0 {
   continue
  }
  // 返回key-value
  return c.keyValue()
 }
}

func (c *Cursor) Prev() (key []byte, value []byte) {
 _assert(c.bucket.tx.db != nil, "tx closed")

 // 现在当前节点内部移动到前一个元素，特殊情况，当前已经位于节点的第一个元素位置
 // 这时需要找到当前节点的前驱叶子节点
 for i := len(c.stack) - 1; i >= 0; i-- {
  elem := &c.stack[i]
  if elem.index > 0 {
   elem.index--
   break
  }
  // 调整stack，c.stack[i]为当前活动的节点
  c.stack = c.stack[:i]
 }

 // 已经遍历完整颗树
 if len(c.stack) == 0 {
  return nil, nil
 }

 // 调用c.last定位到c.stack游标位置节点的最后一个节点的最后一个元素
 c.last()
 k, v, flags := c.keyValue()
 // 是桶，value为nil
 if (flags & uint32(bucketLeafFlag)) != 0 {
  return k, nil
 }
 return k, v
}

func (c *Cursor) Seek(seek []byte) (key []byte, value []byte) {
 k, v, flags := c.seek(seek)

 if ref := &c.stack[len(c.stack)-1]; ref.index >= ref.count() {
  k, v, flags = c.next()
 }

 if k == nil {
  return nil, nil
 } else if (flags & uint32(bucketLeafFlag)) != 0 {
  return k, nil
 }
 return k, v
}

search-->searchNode-->search

serach-->searchPage-->search

func (c *Cursor) seek(seek []byte) (key []byte, value []byte, flags uint32) {
 _assert(c.bucket.tx.db != nil, "tx closed")

 // 清理stack
 c.stack = c.stack[:0]
 // 从根节点开始查找
 c.search(seek, c.bucket.root)
 ref := &c.stack[len(c.stack)-1]

 // key不存在
 if ref.index >= ref.count() {
  return nil, nil, 0
 }

 return c.keyValue()
}

func (c *Cursor) search(key []byte, pgid pgid) {
 p, n := c.bucket.pageNode(pgid)
 if p != nil && (p.flags&(branchPageFlag|leafPageFlag)) == 0 {
  panic(fmt.Sprintf("invalid page type: %d: %x", p.id, p.flags))
 }
 e := elemRef{page: p, node: n}
 c.stack = append(c.stack, e)

 // e是叶子节点
 if e.isLeaf() {
  // 在叶子节点中查找key
  c.nsearch(key)
  return
 }

 if n != nil {
  // 先从node中查找
  c.searchNode(key, n)
  return
 }
 // 从page中查找
 c.searchPage(key, p)
}