openrat-cms

Unnamed repository; edit this file 'description' to name the repository.
Log | Files | Refs | README

chunk.js (5356B)


      1 import { cleanUpLine } from "../line/line_data.js"
      2 import { indexOf } from "../util/misc.js"
      3 import { signalLater } from "../util/operation_group.js"
      4 
      5 // The document is represented as a BTree consisting of leaves, with
      6 // chunk of lines in them, and branches, with up to ten leaves or
      7 // other branch nodes below them. The top node is always a branch
      8 // node, and is the document object itself (meaning it has
      9 // additional methods and properties).
     10 //
     11 // All nodes have parent links. The tree is used both to go from
     12 // line numbers to line objects, and to go from objects to numbers.
     13 // It also indexes by height, and is used to convert between height
     14 // and line object, and to find the total height of the document.
     15 //
     16 // See also http://marijnhaverbeke.nl/blog/codemirror-line-tree.html
     17 
     18 export function LeafChunk(lines) {
     19   this.lines = lines
     20   this.parent = null
     21   let height = 0
     22   for (let i = 0; i < lines.length; ++i) {
     23     lines[i].parent = this
     24     height += lines[i].height
     25   }
     26   this.height = height
     27 }
     28 
     29 LeafChunk.prototype = {
     30   chunkSize() { return this.lines.length },
     31 
     32   // Remove the n lines at offset 'at'.
     33   removeInner(at, n) {
     34     for (let i = at, e = at + n; i < e; ++i) {
     35       let line = this.lines[i]
     36       this.height -= line.height
     37       cleanUpLine(line)
     38       signalLater(line, "delete")
     39     }
     40     this.lines.splice(at, n)
     41   },
     42 
     43   // Helper used to collapse a small branch into a single leaf.
     44   collapse(lines) {
     45     lines.push.apply(lines, this.lines)
     46   },
     47 
     48   // Insert the given array of lines at offset 'at', count them as
     49   // having the given height.
     50   insertInner(at, lines, height) {
     51     this.height += height
     52     this.lines = this.lines.slice(0, at).concat(lines).concat(this.lines.slice(at))
     53     for (let i = 0; i < lines.length; ++i) lines[i].parent = this
     54   },
     55 
     56   // Used to iterate over a part of the tree.
     57   iterN(at, n, op) {
     58     for (let e = at + n; at < e; ++at)
     59       if (op(this.lines[at])) return true
     60   }
     61 }
     62 
     63 export function BranchChunk(children) {
     64   this.children = children
     65   let size = 0, height = 0
     66   for (let i = 0; i < children.length; ++i) {
     67     let ch = children[i]
     68     size += ch.chunkSize(); height += ch.height
     69     ch.parent = this
     70   }
     71   this.size = size
     72   this.height = height
     73   this.parent = null
     74 }
     75 
     76 BranchChunk.prototype = {
     77   chunkSize() { return this.size },
     78 
     79   removeInner(at, n) {
     80     this.size -= n
     81     for (let i = 0; i < this.children.length; ++i) {
     82       let child = this.children[i], sz = child.chunkSize()
     83       if (at < sz) {
     84         let rm = Math.min(n, sz - at), oldHeight = child.height
     85         child.removeInner(at, rm)
     86         this.height -= oldHeight - child.height
     87         if (sz == rm) { this.children.splice(i--, 1); child.parent = null }
     88         if ((n -= rm) == 0) break
     89         at = 0
     90       } else at -= sz
     91     }
     92     // If the result is smaller than 25 lines, ensure that it is a
     93     // single leaf node.
     94     if (this.size - n < 25 &&
     95         (this.children.length > 1 || !(this.children[0] instanceof LeafChunk))) {
     96       let lines = []
     97       this.collapse(lines)
     98       this.children = [new LeafChunk(lines)]
     99       this.children[0].parent = this
    100     }
    101   },
    102 
    103   collapse(lines) {
    104     for (let i = 0; i < this.children.length; ++i) this.children[i].collapse(lines)
    105   },
    106 
    107   insertInner(at, lines, height) {
    108     this.size += lines.length
    109     this.height += height
    110     for (let i = 0; i < this.children.length; ++i) {
    111       let child = this.children[i], sz = child.chunkSize()
    112       if (at <= sz) {
    113         child.insertInner(at, lines, height)
    114         if (child.lines && child.lines.length > 50) {
    115           // To avoid memory thrashing when child.lines is huge (e.g. first view of a large file), it's never spliced.
    116           // Instead, small slices are taken. They're taken in order because sequential memory accesses are fastest.
    117           let remaining = child.lines.length % 25 + 25
    118           for (let pos = remaining; pos < child.lines.length;) {
    119             let leaf = new LeafChunk(child.lines.slice(pos, pos += 25))
    120             child.height -= leaf.height
    121             this.children.splice(++i, 0, leaf)
    122             leaf.parent = this
    123           }
    124           child.lines = child.lines.slice(0, remaining)
    125           this.maybeSpill()
    126         }
    127         break
    128       }
    129       at -= sz
    130     }
    131   },
    132 
    133   // When a node has grown, check whether it should be split.
    134   maybeSpill() {
    135     if (this.children.length <= 10) return
    136     let me = this
    137     do {
    138       let spilled = me.children.splice(me.children.length - 5, 5)
    139       let sibling = new BranchChunk(spilled)
    140       if (!me.parent) { // Become the parent node
    141         let copy = new BranchChunk(me.children)
    142         copy.parent = me
    143         me.children = [copy, sibling]
    144         me = copy
    145      } else {
    146         me.size -= sibling.size
    147         me.height -= sibling.height
    148         let myIndex = indexOf(me.parent.children, me)
    149         me.parent.children.splice(myIndex + 1, 0, sibling)
    150       }
    151       sibling.parent = me.parent
    152     } while (me.children.length > 10)
    153     me.parent.maybeSpill()
    154   },
    155 
    156   iterN(at, n, op) {
    157     for (let i = 0; i < this.children.length; ++i) {
    158       let child = this.children[i], sz = child.chunkSize()
    159       if (at < sz) {
    160         let used = Math.min(n, sz - at)
    161         if (child.iterN(at, used, op)) return true
    162         if ((n -= used) == 0) break
    163         at = 0
    164       } else at -= sz
    165     }
    166   }
    167 }