page.go

Documentation: go.etcd.io/bbolt

     1  package bbolt
     2  
     3  import (
     4  	"fmt"
     5  	"os"
     6  	"sort"
     7  	"unsafe"
     8  )
     9  
    10  const pageHeaderSize = unsafe.Sizeof(page{})
    11  
    12  const minKeysPerPage = 2
    13  
    14  const branchPageElementSize = unsafe.Sizeof(branchPageElement{})
    15  const leafPageElementSize = unsafe.Sizeof(leafPageElement{})
    16  
    17  const (
    18  	branchPageFlag   = 0x01
    19  	leafPageFlag     = 0x02
    20  	metaPageFlag     = 0x04
    21  	freelistPageFlag = 0x10
    22  )
    23  
    24  const (
    25  	bucketLeafFlag = 0x01
    26  )
    27  
    28  type pgid uint64
    29  
    30  type page struct {
    31  	id       pgid
    32  	flags    uint16
    33  	count    uint16
    34  	overflow uint32
    35  }
    36  
    37  // typ returns a human readable page type string used for debugging.
    38  func (p *page) typ() string {
    39  	if (p.flags & branchPageFlag) != 0 {
    40  		return "branch"
    41  	} else if (p.flags & leafPageFlag) != 0 {
    42  		return "leaf"
    43  	} else if (p.flags & metaPageFlag) != 0 {
    44  		return "meta"
    45  	} else if (p.flags & freelistPageFlag) != 0 {
    46  		return "freelist"
    47  	}
    48  	return fmt.Sprintf("unknown<%02x>", p.flags)
    49  }
    50  
    51  // meta returns a pointer to the metadata section of the page.
    52  func (p *page) meta() *meta {
    53  	return (*meta)(unsafeAdd(unsafe.Pointer(p), unsafe.Sizeof(*p)))
    54  }
    55  
    56  func (p *page) fastCheck(id pgid) {
    57  	_assert(p.id == id, "Page expected to be: %v, but self identifies as %v", id, p.id)
    58  	// Only one flag of page-type can be set.
    59  	_assert(p.flags == branchPageFlag ||
    60  		p.flags == leafPageFlag ||
    61  		p.flags == metaPageFlag ||
    62  		p.flags == freelistPageFlag,
    63  		"page %v: has unexpected type/flags: %x", p.id, p.flags)
    64  }
    65  
    66  // leafPageElement retrieves the leaf node by index
    67  func (p *page) leafPageElement(index uint16) *leafPageElement {
    68  	return (*leafPageElement)(unsafeIndex(unsafe.Pointer(p), unsafe.Sizeof(*p),
    69  		leafPageElementSize, int(index)))
    70  }
    71  
    72  // leafPageElements retrieves a list of leaf nodes.
    73  func (p *page) leafPageElements() []leafPageElement {
    74  	if p.count == 0 {
    75  		return nil
    76  	}
    77  	var elems []leafPageElement
    78  	data := unsafeAdd(unsafe.Pointer(p), unsafe.Sizeof(*p))
    79  	unsafeSlice(unsafe.Pointer(&elems), data, int(p.count))
    80  	return elems
    81  }
    82  
    83  // branchPageElement retrieves the branch node by index
    84  func (p *page) branchPageElement(index uint16) *branchPageElement {
    85  	return (*branchPageElement)(unsafeIndex(unsafe.Pointer(p), unsafe.Sizeof(*p),
    86  		unsafe.Sizeof(branchPageElement{}), int(index)))
    87  }
    88  
    89  // branchPageElements retrieves a list of branch nodes.
    90  func (p *page) branchPageElements() []branchPageElement {
    91  	if p.count == 0 {
    92  		return nil
    93  	}
    94  	var elems []branchPageElement
    95  	data := unsafeAdd(unsafe.Pointer(p), unsafe.Sizeof(*p))
    96  	unsafeSlice(unsafe.Pointer(&elems), data, int(p.count))
    97  	return elems
    98  }
    99  
   100  // dump writes n bytes of the page to STDERR as hex output.
   101  func (p *page) hexdump(n int) {
   102  	buf := unsafeByteSlice(unsafe.Pointer(p), 0, 0, n)
   103  	fmt.Fprintf(os.Stderr, "%x\n", buf)
   104  }
   105  
   106  type pages []*page
   107  
   108  func (s pages) Len() int           { return len(s) }
   109  func (s pages) Swap(i, j int)      { s[i], s[j] = s[j], s[i] }
   110  func (s pages) Less(i, j int) bool { return s[i].id < s[j].id }
   111  
   112  // branchPageElement represents a node on a branch page.
   113  type branchPageElement struct {
   114  	pos   uint32
   115  	ksize uint32
   116  	pgid  pgid
   117  }
   118  
   119  // key returns a byte slice of the node key.
   120  func (n *branchPageElement) key() []byte {
   121  	return unsafeByteSlice(unsafe.Pointer(n), 0, int(n.pos), int(n.pos)+int(n.ksize))
   122  }
   123  
   124  // leafPageElement represents a node on a leaf page.
   125  type leafPageElement struct {
   126  	flags uint32
   127  	pos   uint32
   128  	ksize uint32
   129  	vsize uint32
   130  }
   131  
   132  // key returns a byte slice of the node key.
   133  func (n *leafPageElement) key() []byte {
   134  	i := int(n.pos)
   135  	j := i + int(n.ksize)
   136  	return unsafeByteSlice(unsafe.Pointer(n), 0, i, j)
   137  }
   138  
   139  // value returns a byte slice of the node value.
   140  func (n *leafPageElement) value() []byte {
   141  	i := int(n.pos) + int(n.ksize)
   142  	j := i + int(n.vsize)
   143  	return unsafeByteSlice(unsafe.Pointer(n), 0, i, j)
   144  }
   145  
   146  // PageInfo represents human readable information about a page.
   147  type PageInfo struct {
   148  	ID            int
   149  	Type          string
   150  	Count         int
   151  	OverflowCount int
   152  }
   153  
   154  type pgids []pgid
   155  
   156  func (s pgids) Len() int           { return len(s) }
   157  func (s pgids) Swap(i, j int)      { s[i], s[j] = s[j], s[i] }
   158  func (s pgids) Less(i, j int) bool { return s[i] < s[j] }
   159  
   160  // merge returns the sorted union of a and b.
   161  func (a pgids) merge(b pgids) pgids {
   162  	// Return the opposite slice if one is nil.
   163  	if len(a) == 0 {
   164  		return b
   165  	}
   166  	if len(b) == 0 {
   167  		return a
   168  	}
   169  	merged := make(pgids, len(a)+len(b))
   170  	mergepgids(merged, a, b)
   171  	return merged
   172  }
   173  
   174  // mergepgids copies the sorted union of a and b into dst.
   175  // If dst is too small, it panics.
   176  func mergepgids(dst, a, b pgids) {
   177  	if len(dst) < len(a)+len(b) {
   178  		panic(fmt.Errorf("mergepgids bad len %d < %d + %d", len(dst), len(a), len(b)))
   179  	}
   180  	// Copy in the opposite slice if one is nil.
   181  	if len(a) == 0 {
   182  		copy(dst, b)
   183  		return
   184  	}
   185  	if len(b) == 0 {
   186  		copy(dst, a)
   187  		return
   188  	}
   189  
   190  	// Merged will hold all elements from both lists.
   191  	merged := dst[:0]
   192  
   193  	// Assign lead to the slice with a lower starting value, follow to the higher value.
   194  	lead, follow := a, b
   195  	if b[0] < a[0] {
   196  		lead, follow = b, a
   197  	}
   198  
   199  	// Continue while there are elements in the lead.
   200  	for len(lead) > 0 {
   201  		// Merge largest prefix of lead that is ahead of follow[0].
   202  		n := sort.Search(len(lead), func(i int) bool { return lead[i] > follow[0] })
   203  		merged = append(merged, lead[:n]...)
   204  		if n >= len(lead) {
   205  			break
   206  		}
   207  
   208  		// Swap lead and follow.
   209  		lead, follow = follow, lead[n:]
   210  	}
   211  
   212  	// Append what's left in follow.
   213  	_ = append(merged, follow...)
   214  }
   215
View as plain text