a simple url shortening service, in the same vein as bit.ly and tinyurl.com, written in Go and using BoltDB as a backend
You can not select more than 25 topics Topics must start with a letter or number, can include dashes ('-') and can be up to 35 characters long.

776 lines
21KB

  1. package bbolt
  2. import (
  3. "bytes"
  4. "fmt"
  5. "unsafe"
  6. )
  7. const (
  8. // MaxKeySize is the maximum length of a key, in bytes.
  9. MaxKeySize = 32768
  10. // MaxValueSize is the maximum length of a value, in bytes.
  11. MaxValueSize = (1 << 31) - 2
  12. )
  13. const bucketHeaderSize = int(unsafe.Sizeof(bucket{}))
  14. const (
  15. minFillPercent = 0.1
  16. maxFillPercent = 1.0
  17. )
  18. // DefaultFillPercent is the percentage that split pages are filled.
  19. // This value can be changed by setting Bucket.FillPercent.
  20. const DefaultFillPercent = 0.5
  21. // Bucket represents a collection of key/value pairs inside the database.
  22. type Bucket struct {
  23. *bucket
  24. tx *Tx // the associated transaction
  25. buckets map[string]*Bucket // subbucket cache
  26. page *page // inline page reference
  27. rootNode *node // materialized node for the root page.
  28. nodes map[pgid]*node // node cache
  29. // Sets the threshold for filling nodes when they split. By default,
  30. // the bucket will fill to 50% but it can be useful to increase this
  31. // amount if you know that your write workloads are mostly append-only.
  32. //
  33. // This is non-persisted across transactions so it must be set in every Tx.
  34. FillPercent float64
  35. }
  36. // bucket represents the on-file representation of a bucket.
  37. // This is stored as the "value" of a bucket key. If the bucket is small enough,
  38. // then its root page can be stored inline in the "value", after the bucket
  39. // header. In the case of inline buckets, the "root" will be 0.
  40. type bucket struct {
  41. root pgid // page id of the bucket's root-level page
  42. sequence uint64 // monotonically incrementing, used by NextSequence()
  43. }
  44. // newBucket returns a new bucket associated with a transaction.
  45. func newBucket(tx *Tx) Bucket {
  46. var b = Bucket{tx: tx, FillPercent: DefaultFillPercent}
  47. if tx.writable {
  48. b.buckets = make(map[string]*Bucket)
  49. b.nodes = make(map[pgid]*node)
  50. }
  51. return b
  52. }
  53. // Tx returns the tx of the bucket.
  54. func (b *Bucket) Tx() *Tx {
  55. return b.tx
  56. }
  57. // Root returns the root of the bucket.
  58. func (b *Bucket) Root() pgid {
  59. return b.root
  60. }
  61. // Writable returns whether the bucket is writable.
  62. func (b *Bucket) Writable() bool {
  63. return b.tx.writable
  64. }
  65. // Cursor creates a cursor associated with the bucket.
  66. // The cursor is only valid as long as the transaction is open.
  67. // Do not use a cursor after the transaction is closed.
  68. func (b *Bucket) Cursor() *Cursor {
  69. // Update transaction statistics.
  70. b.tx.stats.CursorCount++
  71. // Allocate and return a cursor.
  72. return &Cursor{
  73. bucket: b,
  74. stack: make([]elemRef, 0),
  75. }
  76. }
  77. // Bucket retrieves a nested bucket by name.
  78. // Returns nil if the bucket does not exist.
  79. // The bucket instance is only valid for the lifetime of the transaction.
  80. func (b *Bucket) Bucket(name []byte) *Bucket {
  81. if b.buckets != nil {
  82. if child := b.buckets[string(name)]; child != nil {
  83. return child
  84. }
  85. }
  86. // Move cursor to key.
  87. c := b.Cursor()
  88. k, v, flags := c.seek(name)
  89. // Return nil if the key doesn't exist or it is not a bucket.
  90. if !bytes.Equal(name, k) || (flags&bucketLeafFlag) == 0 {
  91. return nil
  92. }
  93. // Otherwise create a bucket and cache it.
  94. var child = b.openBucket(v)
  95. if b.buckets != nil {
  96. b.buckets[string(name)] = child
  97. }
  98. return child
  99. }
  100. // Helper method that re-interprets a sub-bucket value
  101. // from a parent into a Bucket
  102. func (b *Bucket) openBucket(value []byte) *Bucket {
  103. var child = newBucket(b.tx)
  104. // If unaligned load/stores are broken on this arch and value is
  105. // unaligned simply clone to an aligned byte array.
  106. unaligned := brokenUnaligned && uintptr(unsafe.Pointer(&value[0]))&3 != 0
  107. if unaligned {
  108. value = cloneBytes(value)
  109. }
  110. // If this is a writable transaction then we need to copy the bucket entry.
  111. // Read-only transactions can point directly at the mmap entry.
  112. if b.tx.writable && !unaligned {
  113. child.bucket = &bucket{}
  114. *child.bucket = *(*bucket)(unsafe.Pointer(&value[0]))
  115. } else {
  116. child.bucket = (*bucket)(unsafe.Pointer(&value[0]))
  117. }
  118. // Save a reference to the inline page if the bucket is inline.
  119. if child.root == 0 {
  120. child.page = (*page)(unsafe.Pointer(&value[bucketHeaderSize]))
  121. }
  122. return &child
  123. }
  124. // CreateBucket creates a new bucket at the given key and returns the new bucket.
  125. // Returns an error if the key already exists, if the bucket name is blank, or if the bucket name is too long.
  126. // The bucket instance is only valid for the lifetime of the transaction.
  127. func (b *Bucket) CreateBucket(key []byte) (*Bucket, error) {
  128. if b.tx.db == nil {
  129. return nil, ErrTxClosed
  130. } else if !b.tx.writable {
  131. return nil, ErrTxNotWritable
  132. } else if len(key) == 0 {
  133. return nil, ErrBucketNameRequired
  134. }
  135. // Move cursor to correct position.
  136. c := b.Cursor()
  137. k, _, flags := c.seek(key)
  138. // Return an error if there is an existing key.
  139. if bytes.Equal(key, k) {
  140. if (flags & bucketLeafFlag) != 0 {
  141. return nil, ErrBucketExists
  142. }
  143. return nil, ErrIncompatibleValue
  144. }
  145. // Create empty, inline bucket.
  146. var bucket = Bucket{
  147. bucket: &bucket{},
  148. rootNode: &node{isLeaf: true},
  149. FillPercent: DefaultFillPercent,
  150. }
  151. var value = bucket.write()
  152. // Insert into node.
  153. key = cloneBytes(key)
  154. c.node().put(key, key, value, 0, bucketLeafFlag)
  155. // Since subbuckets are not allowed on inline buckets, we need to
  156. // dereference the inline page, if it exists. This will cause the bucket
  157. // to be treated as a regular, non-inline bucket for the rest of the tx.
  158. b.page = nil
  159. return b.Bucket(key), nil
  160. }
  161. // CreateBucketIfNotExists creates a new bucket if it doesn't already exist and returns a reference to it.
  162. // Returns an error if the bucket name is blank, or if the bucket name is too long.
  163. // The bucket instance is only valid for the lifetime of the transaction.
  164. func (b *Bucket) CreateBucketIfNotExists(key []byte) (*Bucket, error) {
  165. child, err := b.CreateBucket(key)
  166. if err == ErrBucketExists {
  167. return b.Bucket(key), nil
  168. } else if err != nil {
  169. return nil, err
  170. }
  171. return child, nil
  172. }
  173. // DeleteBucket deletes a bucket at the given key.
  174. // Returns an error if the bucket does not exists, or if the key represents a non-bucket value.
  175. func (b *Bucket) DeleteBucket(key []byte) error {
  176. if b.tx.db == nil {
  177. return ErrTxClosed
  178. } else if !b.Writable() {
  179. return ErrTxNotWritable
  180. }
  181. // Move cursor to correct position.
  182. c := b.Cursor()
  183. k, _, flags := c.seek(key)
  184. // Return an error if bucket doesn't exist or is not a bucket.
  185. if !bytes.Equal(key, k) {
  186. return ErrBucketNotFound
  187. } else if (flags & bucketLeafFlag) == 0 {
  188. return ErrIncompatibleValue
  189. }
  190. // Recursively delete all child buckets.
  191. child := b.Bucket(key)
  192. err := child.ForEach(func(k, v []byte) error {
  193. if v == nil {
  194. if err := child.DeleteBucket(k); err != nil {
  195. return fmt.Errorf("delete bucket: %s", err)
  196. }
  197. }
  198. return nil
  199. })
  200. if err != nil {
  201. return err
  202. }
  203. // Remove cached copy.
  204. delete(b.buckets, string(key))
  205. // Release all bucket pages to freelist.
  206. child.nodes = nil
  207. child.rootNode = nil
  208. child.free()
  209. // Delete the node if we have a matching key.
  210. c.node().del(key)
  211. return nil
  212. }
  213. // Get retrieves the value for a key in the bucket.
  214. // Returns a nil value if the key does not exist or if the key is a nested bucket.
  215. // The returned value is only valid for the life of the transaction.
  216. func (b *Bucket) Get(key []byte) []byte {
  217. k, v, flags := b.Cursor().seek(key)
  218. // Return nil if this is a bucket.
  219. if (flags & bucketLeafFlag) != 0 {
  220. return nil
  221. }
  222. // If our target node isn't the same key as what's passed in then return nil.
  223. if !bytes.Equal(key, k) {
  224. return nil
  225. }
  226. return v
  227. }
  228. // Put sets the value for a key in the bucket.
  229. // If the key exist then its previous value will be overwritten.
  230. // Supplied value must remain valid for the life of the transaction.
  231. // Returns an error if the bucket was created from a read-only transaction, if the key is blank, if the key is too large, or if the value is too large.
  232. func (b *Bucket) Put(key []byte, value []byte) error {
  233. if b.tx.db == nil {
  234. return ErrTxClosed
  235. } else if !b.Writable() {
  236. return ErrTxNotWritable
  237. } else if len(key) == 0 {
  238. return ErrKeyRequired
  239. } else if len(key) > MaxKeySize {
  240. return ErrKeyTooLarge
  241. } else if int64(len(value)) > MaxValueSize {
  242. return ErrValueTooLarge
  243. }
  244. // Move cursor to correct position.
  245. c := b.Cursor()
  246. k, _, flags := c.seek(key)
  247. // Return an error if there is an existing key with a bucket value.
  248. if bytes.Equal(key, k) && (flags&bucketLeafFlag) != 0 {
  249. return ErrIncompatibleValue
  250. }
  251. // Insert into node.
  252. key = cloneBytes(key)
  253. c.node().put(key, key, value, 0, 0)
  254. return nil
  255. }
  256. // Delete removes a key from the bucket.
  257. // If the key does not exist then nothing is done and a nil error is returned.
  258. // Returns an error if the bucket was created from a read-only transaction.
  259. func (b *Bucket) Delete(key []byte) error {
  260. if b.tx.db == nil {
  261. return ErrTxClosed
  262. } else if !b.Writable() {
  263. return ErrTxNotWritable
  264. }
  265. // Move cursor to correct position.
  266. c := b.Cursor()
  267. k, _, flags := c.seek(key)
  268. // Return nil if the key doesn't exist.
  269. if !bytes.Equal(key, k) {
  270. return nil
  271. }
  272. // Return an error if there is already existing bucket value.
  273. if (flags & bucketLeafFlag) != 0 {
  274. return ErrIncompatibleValue
  275. }
  276. // Delete the node if we have a matching key.
  277. c.node().del(key)
  278. return nil
  279. }
  280. // Sequence returns the current integer for the bucket without incrementing it.
  281. func (b *Bucket) Sequence() uint64 { return b.bucket.sequence }
  282. // SetSequence updates the sequence number for the bucket.
  283. func (b *Bucket) SetSequence(v uint64) error {
  284. if b.tx.db == nil {
  285. return ErrTxClosed
  286. } else if !b.Writable() {
  287. return ErrTxNotWritable
  288. }
  289. // Materialize the root node if it hasn't been already so that the
  290. // bucket will be saved during commit.
  291. if b.rootNode == nil {
  292. _ = b.node(b.root, nil)
  293. }
  294. // Increment and return the sequence.
  295. b.bucket.sequence = v
  296. return nil
  297. }
  298. // NextSequence returns an autoincrementing integer for the bucket.
  299. func (b *Bucket) NextSequence() (uint64, error) {
  300. if b.tx.db == nil {
  301. return 0, ErrTxClosed
  302. } else if !b.Writable() {
  303. return 0, ErrTxNotWritable
  304. }
  305. // Materialize the root node if it hasn't been already so that the
  306. // bucket will be saved during commit.
  307. if b.rootNode == nil {
  308. _ = b.node(b.root, nil)
  309. }
  310. // Increment and return the sequence.
  311. b.bucket.sequence++
  312. return b.bucket.sequence, nil
  313. }
  314. // ForEach executes a function for each key/value pair in a bucket.
  315. // If the provided function returns an error then the iteration is stopped and
  316. // the error is returned to the caller. The provided function must not modify
  317. // the bucket; this will result in undefined behavior.
  318. func (b *Bucket) ForEach(fn func(k, v []byte) error) error {
  319. if b.tx.db == nil {
  320. return ErrTxClosed
  321. }
  322. c := b.Cursor()
  323. for k, v := c.First(); k != nil; k, v = c.Next() {
  324. if err := fn(k, v); err != nil {
  325. return err
  326. }
  327. }
  328. return nil
  329. }
  330. // Stat returns stats on a bucket.
  331. func (b *Bucket) Stats() BucketStats {
  332. var s, subStats BucketStats
  333. pageSize := b.tx.db.pageSize
  334. s.BucketN += 1
  335. if b.root == 0 {
  336. s.InlineBucketN += 1
  337. }
  338. b.forEachPage(func(p *page, depth int) {
  339. if (p.flags & leafPageFlag) != 0 {
  340. s.KeyN += int(p.count)
  341. // used totals the used bytes for the page
  342. used := pageHeaderSize
  343. if p.count != 0 {
  344. // If page has any elements, add all element headers.
  345. used += leafPageElementSize * int(p.count-1)
  346. // Add all element key, value sizes.
  347. // The computation takes advantage of the fact that the position
  348. // of the last element's key/value equals to the total of the sizes
  349. // of all previous elements' keys and values.
  350. // It also includes the last element's header.
  351. lastElement := p.leafPageElement(p.count - 1)
  352. used += int(lastElement.pos + lastElement.ksize + lastElement.vsize)
  353. }
  354. if b.root == 0 {
  355. // For inlined bucket just update the inline stats
  356. s.InlineBucketInuse += used
  357. } else {
  358. // For non-inlined bucket update all the leaf stats
  359. s.LeafPageN++
  360. s.LeafInuse += used
  361. s.LeafOverflowN += int(p.overflow)
  362. // Collect stats from sub-buckets.
  363. // Do that by iterating over all element headers
  364. // looking for the ones with the bucketLeafFlag.
  365. for i := uint16(0); i < p.count; i++ {
  366. e := p.leafPageElement(i)
  367. if (e.flags & bucketLeafFlag) != 0 {
  368. // For any bucket element, open the element value
  369. // and recursively call Stats on the contained bucket.
  370. subStats.Add(b.openBucket(e.value()).Stats())
  371. }
  372. }
  373. }
  374. } else if (p.flags & branchPageFlag) != 0 {
  375. s.BranchPageN++
  376. lastElement := p.branchPageElement(p.count - 1)
  377. // used totals the used bytes for the page
  378. // Add header and all element headers.
  379. used := pageHeaderSize + (branchPageElementSize * int(p.count-1))
  380. // Add size of all keys and values.
  381. // Again, use the fact that last element's position equals to
  382. // the total of key, value sizes of all previous elements.
  383. used += int(lastElement.pos + lastElement.ksize)
  384. s.BranchInuse += used
  385. s.BranchOverflowN += int(p.overflow)
  386. }
  387. // Keep track of maximum page depth.
  388. if depth+1 > s.Depth {
  389. s.Depth = (depth + 1)
  390. }
  391. })
  392. // Alloc stats can be computed from page counts and pageSize.
  393. s.BranchAlloc = (s.BranchPageN + s.BranchOverflowN) * pageSize
  394. s.LeafAlloc = (s.LeafPageN + s.LeafOverflowN) * pageSize
  395. // Add the max depth of sub-buckets to get total nested depth.
  396. s.Depth += subStats.Depth
  397. // Add the stats for all sub-buckets
  398. s.Add(subStats)
  399. return s
  400. }
  401. // forEachPage iterates over every page in a bucket, including inline pages.
  402. func (b *Bucket) forEachPage(fn func(*page, int)) {
  403. // If we have an inline page then just use that.
  404. if b.page != nil {
  405. fn(b.page, 0)
  406. return
  407. }
  408. // Otherwise traverse the page hierarchy.
  409. b.tx.forEachPage(b.root, 0, fn)
  410. }
  411. // forEachPageNode iterates over every page (or node) in a bucket.
  412. // This also includes inline pages.
  413. func (b *Bucket) forEachPageNode(fn func(*page, *node, int)) {
  414. // If we have an inline page or root node then just use that.
  415. if b.page != nil {
  416. fn(b.page, nil, 0)
  417. return
  418. }
  419. b._forEachPageNode(b.root, 0, fn)
  420. }
  421. func (b *Bucket) _forEachPageNode(pgid pgid, depth int, fn func(*page, *node, int)) {
  422. var p, n = b.pageNode(pgid)
  423. // Execute function.
  424. fn(p, n, depth)
  425. // Recursively loop over children.
  426. if p != nil {
  427. if (p.flags & branchPageFlag) != 0 {
  428. for i := 0; i < int(p.count); i++ {
  429. elem := p.branchPageElement(uint16(i))
  430. b._forEachPageNode(elem.pgid, depth+1, fn)
  431. }
  432. }
  433. } else {
  434. if !n.isLeaf {
  435. for _, inode := range n.inodes {
  436. b._forEachPageNode(inode.pgid, depth+1, fn)
  437. }
  438. }
  439. }
  440. }
  441. // spill writes all the nodes for this bucket to dirty pages.
  442. func (b *Bucket) spill() error {
  443. // Spill all child buckets first.
  444. for name, child := range b.buckets {
  445. // If the child bucket is small enough and it has no child buckets then
  446. // write it inline into the parent bucket's page. Otherwise spill it
  447. // like a normal bucket and make the parent value a pointer to the page.
  448. var value []byte
  449. if child.inlineable() {
  450. child.free()
  451. value = child.write()
  452. } else {
  453. if err := child.spill(); err != nil {
  454. return err
  455. }
  456. // Update the child bucket header in this bucket.
  457. value = make([]byte, unsafe.Sizeof(bucket{}))
  458. var bucket = (*bucket)(unsafe.Pointer(&value[0]))
  459. *bucket = *child.bucket
  460. }
  461. // Skip writing the bucket if there are no materialized nodes.
  462. if child.rootNode == nil {
  463. continue
  464. }
  465. // Update parent node.
  466. var c = b.Cursor()
  467. k, _, flags := c.seek([]byte(name))
  468. if !bytes.Equal([]byte(name), k) {
  469. panic(fmt.Sprintf("misplaced bucket header: %x -> %x", []byte(name), k))
  470. }
  471. if flags&bucketLeafFlag == 0 {
  472. panic(fmt.Sprintf("unexpected bucket header flag: %x", flags))
  473. }
  474. c.node().put([]byte(name), []byte(name), value, 0, bucketLeafFlag)
  475. }
  476. // Ignore if there's not a materialized root node.
  477. if b.rootNode == nil {
  478. return nil
  479. }
  480. // Spill nodes.
  481. if err := b.rootNode.spill(); err != nil {
  482. return err
  483. }
  484. b.rootNode = b.rootNode.root()
  485. // Update the root node for this bucket.
  486. if b.rootNode.pgid >= b.tx.meta.pgid {
  487. panic(fmt.Sprintf("pgid (%d) above high water mark (%d)", b.rootNode.pgid, b.tx.meta.pgid))
  488. }
  489. b.root = b.rootNode.pgid
  490. return nil
  491. }
  492. // inlineable returns true if a bucket is small enough to be written inline
  493. // and if it contains no subbuckets. Otherwise returns false.
  494. func (b *Bucket) inlineable() bool {
  495. var n = b.rootNode
  496. // Bucket must only contain a single leaf node.
  497. if n == nil || !n.isLeaf {
  498. return false
  499. }
  500. // Bucket is not inlineable if it contains subbuckets or if it goes beyond
  501. // our threshold for inline bucket size.
  502. var size = pageHeaderSize
  503. for _, inode := range n.inodes {
  504. size += leafPageElementSize + len(inode.key) + len(inode.value)
  505. if inode.flags&bucketLeafFlag != 0 {
  506. return false
  507. } else if size > b.maxInlineBucketSize() {
  508. return false
  509. }
  510. }
  511. return true
  512. }
  513. // Returns the maximum total size of a bucket to make it a candidate for inlining.
  514. func (b *Bucket) maxInlineBucketSize() int {
  515. return b.tx.db.pageSize / 4
  516. }
  517. // write allocates and writes a bucket to a byte slice.
  518. func (b *Bucket) write() []byte {
  519. // Allocate the appropriate size.
  520. var n = b.rootNode
  521. var value = make([]byte, bucketHeaderSize+n.size())
  522. // Write a bucket header.
  523. var bucket = (*bucket)(unsafe.Pointer(&value[0]))
  524. *bucket = *b.bucket
  525. // Convert byte slice to a fake page and write the root node.
  526. var p = (*page)(unsafe.Pointer(&value[bucketHeaderSize]))
  527. n.write(p)
  528. return value
  529. }
  530. // rebalance attempts to balance all nodes.
  531. func (b *Bucket) rebalance() {
  532. for _, n := range b.nodes {
  533. n.rebalance()
  534. }
  535. for _, child := range b.buckets {
  536. child.rebalance()
  537. }
  538. }
  539. // node creates a node from a page and associates it with a given parent.
  540. func (b *Bucket) node(pgid pgid, parent *node) *node {
  541. _assert(b.nodes != nil, "nodes map expected")
  542. // Retrieve node if it's already been created.
  543. if n := b.nodes[pgid]; n != nil {
  544. return n
  545. }
  546. // Otherwise create a node and cache it.
  547. n := &node{bucket: b, parent: parent}
  548. if parent == nil {
  549. b.rootNode = n
  550. } else {
  551. parent.children = append(parent.children, n)
  552. }
  553. // Use the inline page if this is an inline bucket.
  554. var p = b.page
  555. if p == nil {
  556. p = b.tx.page(pgid)
  557. }
  558. // Read the page into the node and cache it.
  559. n.read(p)
  560. b.nodes[pgid] = n
  561. // Update statistics.
  562. b.tx.stats.NodeCount++
  563. return n
  564. }
  565. // free recursively frees all pages in the bucket.
  566. func (b *Bucket) free() {
  567. if b.root == 0 {
  568. return
  569. }
  570. var tx = b.tx
  571. b.forEachPageNode(func(p *page, n *node, _ int) {
  572. if p != nil {
  573. tx.db.freelist.free(tx.meta.txid, p)
  574. } else {
  575. n.free()
  576. }
  577. })
  578. b.root = 0
  579. }
  580. // dereference removes all references to the old mmap.
  581. func (b *Bucket) dereference() {
  582. if b.rootNode != nil {
  583. b.rootNode.root().dereference()
  584. }
  585. for _, child := range b.buckets {
  586. child.dereference()
  587. }
  588. }
  589. // pageNode returns the in-memory node, if it exists.
  590. // Otherwise returns the underlying page.
  591. func (b *Bucket) pageNode(id pgid) (*page, *node) {
  592. // Inline buckets have a fake page embedded in their value so treat them
  593. // differently. We'll return the rootNode (if available) or the fake page.
  594. if b.root == 0 {
  595. if id != 0 {
  596. panic(fmt.Sprintf("inline bucket non-zero page access(2): %d != 0", id))
  597. }
  598. if b.rootNode != nil {
  599. return nil, b.rootNode
  600. }
  601. return b.page, nil
  602. }
  603. // Check the node cache for non-inline buckets.
  604. if b.nodes != nil {
  605. if n := b.nodes[id]; n != nil {
  606. return nil, n
  607. }
  608. }
  609. // Finally lookup the page from the transaction if no node is materialized.
  610. return b.tx.page(id), nil
  611. }
  612. // BucketStats records statistics about resources used by a bucket.
  613. type BucketStats struct {
  614. // Page count statistics.
  615. BranchPageN int // number of logical branch pages
  616. BranchOverflowN int // number of physical branch overflow pages
  617. LeafPageN int // number of logical leaf pages
  618. LeafOverflowN int // number of physical leaf overflow pages
  619. // Tree statistics.
  620. KeyN int // number of keys/value pairs
  621. Depth int // number of levels in B+tree
  622. // Page size utilization.
  623. BranchAlloc int // bytes allocated for physical branch pages
  624. BranchInuse int // bytes actually used for branch data
  625. LeafAlloc int // bytes allocated for physical leaf pages
  626. LeafInuse int // bytes actually used for leaf data
  627. // Bucket statistics
  628. BucketN int // total number of buckets including the top bucket
  629. InlineBucketN int // total number on inlined buckets
  630. InlineBucketInuse int // bytes used for inlined buckets (also accounted for in LeafInuse)
  631. }
  632. func (s *BucketStats) Add(other BucketStats) {
  633. s.BranchPageN += other.BranchPageN
  634. s.BranchOverflowN += other.BranchOverflowN
  635. s.LeafPageN += other.LeafPageN
  636. s.LeafOverflowN += other.LeafOverflowN
  637. s.KeyN += other.KeyN
  638. if s.Depth < other.Depth {
  639. s.Depth = other.Depth
  640. }
  641. s.BranchAlloc += other.BranchAlloc
  642. s.BranchInuse += other.BranchInuse
  643. s.LeafAlloc += other.LeafAlloc
  644. s.LeafInuse += other.LeafInuse
  645. s.BucketN += other.BucketN
  646. s.InlineBucketN += other.InlineBucketN
  647. s.InlineBucketInuse += other.InlineBucketInuse
  648. }
  649. // cloneBytes returns a copy of a given slice.
  650. func cloneBytes(v []byte) []byte {
  651. var clone = make([]byte, len(v))
  652. copy(clone, v)
  653. return clone
  654. }