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