golangÔ´Âë·ÖÎö£ºboltdb£¨3£©

// freelist represents a list of all pages that are available for allocation.
// It also tracks pages that have been freed but are still in use by open transactions.
type freelist struct {
  ids     []pgid          // all free and available free page ids.
  pending map[txid][]pgid // mapping of soon-to-be free page ids by tx.
  cache   map[pgid]bool   // fast lookup of all free and pending page ids.
}

// newFreelist returns an empty, initialized freelist.
func newFreelist() *freelist {
  return &freelist{
    pending: make(map[txid][]pgid),
    cache:   make(map[pgid]bool),
  }
}

    func (f *freelist) read(p *page) {
            ids := ((*[maxAllocSize]pgid)(unsafe.Pointer(&p.ptr)))[idx:count]
    f.ids = make([]pgid, len(ids))
    copy(f.ids, ids)


    // Make sure they're sorted.
    sort.Sort(pgids(f.ids))
        f.reindex()

// reindex rebuilds the free cache based on available and pending free lists.
func (f *freelist) reindex() {
  f.cache = make(map[pgid]bool, len(f.ids))
  for _, id := range f.ids {
    f.cache[id] = true
  }
  for _, pendingIDs := range f.pending {
    for _, pendingID := range pendingIDs {
      f.cache[pendingID] = true
    }
  }
}

// maxAllocSize is the size used when creating array pointers.
const maxAllocSize = 0x7FFFFFFF

func (b *Bucket) dereference() {
  if b.rootNode != nil {
    b.rootNode.root().dereference()
  }


  for _, child := range b.buckets {
    child.dereference()
  }
}

// Bucket represents a collection of key/value pairs inside the database.
type Bucket struct {
  *bucket
  tx       *Tx                // the associated transaction
  buckets  map[string]*Bucket // subbucket cache
  page     *page              // inline page reference
  rootNode *node              // materialized node for the root page.
  nodes    map[pgid]*node     // node cache


  // Sets the threshold for filling nodes when they split. By default,
  // the bucket will fill to 50% but it can be useful to increase this
  // amount if you know that your write workloads are mostly append-only.
  //
  // This is non-persisted across transactions so it must be set in every Tx.
  FillPercent float64
}

// bucket represents the on-file representation of a bucket.
// This is stored as the "value" of a bucket key. If the bucket is small enough,
// then its root page can be stored inline in the "value", after the bucket
// header. In the case of inline buckets, the "root" will be 0.
type bucket struct {
  root     pgid   // page id of the bucket's root-level page
  sequence uint64 // monotonically incrementing, used by NextSequence()
}

// node represents an in-memory, deserialized page.

type node struct {

  bucket     *Bucket

  isLeaf     bool

  unbalanced bool

  spilled    bool

  key        []byte

  pgid       pgid

  parent     *node

  children   nodes

  inodes     inodes

}

type inode struct {
  flags uint32
  pgid  pgid
  key   []byte
  value []byte
}
        / inode represents an internal node inside of a node.
// It can be used to point to elements in a page or point
// to an element which hasn't been added to a page yet.

type inodes []inode

// dereference causes the node to copy all its inode key/value references to heap memory.
// This is required when the mmap is reallocated so inodes are not pointing to stale data.
func (n *node) dereference() {
  if n.key != nil {
    key := make([]byte, len(n.key))
    copy(key, n.key)
    n.key = key
    _assert(n.pgid == 0 || len(n.key) > 0, "dereference: zero-length node key on existing node")
  }
          for i := range n.inodes {
    inode := &n.inodes[i]


    key := make([]byte, len(inode.key))
    copy(key, inode.key)
    inode.key = key
    _assert(len(inode.key) > 0, "dereference: zero-length inode key")


    value := make([]byte, len(inode.value))
    copy(value, inode.value)
    inode.value = value
  }
          for _, child := range n.children {
    child.dereference()
  }


  // Update statistics.
  n.bucket.tx.stats.NodeDeref++

func (n *node) root() *node {
  if n.parent == nil {
    return n
  }
  return n.parent.root()
}