<commit_before>function extend(to, from) {
    for (var key in from) to[key] = from[key]
    return to
}

var __slice = [].slice

/*function say() {
        var args = __slice.call(arguments)
        console.log(require('util').inspect(args, false, null))
}*/

function compare (a, b) { return a < b ? -1 : a > b ? 1 : 0 }

function extract (a) { return a }

function classify () {
    var i, I, name
    for (i = 0, I = arguments.length; i < I; i++) {
        name = arguments[i].name
        if (name[0] == '_')
            this.__defineGetter__(name.slice(1), arguments[i])
        else if (name[name.length - 1] == '_')
            this.__defineSetter__(name.slice(0, name.length - 1), arguments[i])
        else
            this[arguments[i].name] = arguments[i]
    }
    return this
}

function Strata (options) {
    var directory = options.directory,
        extractor = options.extractor || extract,
        comparator = options.comparator || compare,
        fs = options.fs || require('fs'),
        path = options.path || require('path'),
        ok = function (condition, message) { if (!condition) throw new Error(message) },
        cache = {},
        mru = { address: null },
        nextAddress = 0,
        length = 1024,
        balancer = new Balancer(),
        balancing,
        size = 0,
        checksum,
        constructors = {},
        serialize = options.serialize || function (object) { return new Buffer(JSON.stringify(object)) },
        deserialize = options.deserialize || function (buffer) { return JSON.parse(buffer.toString()) },
        tracer = options.tracer || function () { arguments[2]() }

    checksum = (function () {
        if (typeof options.checksum == 'function') return options.checksum
        var algorithm
        switch (algorithm = options.checksum || 'sha1') {
        case 'none':
            return function () {
                return {
                    update: function () {},
                    digest: function () { return '0' }
                }
            }
        default:
            var crypto = require('crypto')
            return function (m) { return crypto.createHash(algorithm) }
        }
    })()

    function validator (callback) {
        return function (forward, type, report) { return validate(callback, forward, type, report) }
    }

    var thrownByUser

    function validate (callback, forward, type, report) {
        ok(typeof forward == 'function', 'no forward function')
        ok(typeof callback == 'function','no callback function')
        return function (error) {
            if (error) {
                toUserLand(callback, error)
            } else {
                try {
                    if (type && report) {
                        tracer(type, report, validate(callback, forward))
                    } else {
                        forward.apply(null, __slice.call(arguments, 1))
                    }
                } catch (error) {
                    if (thrownByUser === error) {
                        throw error
                    }
                    toUserLand(callback, error)
                }
            }
        }
    }

    function toUserLand (callback) {
        try {
            callback.apply(null, __slice.call(arguments, 1))
        } catch (error) {
            thrownByUser = error
            throw error
        }
    }

    function _size () { return size }

    function _nextAddress () { return nextAddress }

    mru.next = mru.previous = mru

    function report () {
        return {
            size: size,
            nextAddress: nextAddress,
            cache: Object.keys(cache)
        }
    }

    function readLine (buffer, isKey) {
        for (var count = 2, i = 0, I = buffer.length; i < I && count; i++) {
            if (buffer[i] == 0x20) count--
        }
        for (count = 1; i < I && count; i++) {
            if (buffer[i] == 0x20 || buffer[i] == 0x0a) count--
        }
        ok(!count, 'corrupt line: could not find end of line header')
        var fields = buffer.toString('utf8', 0, i - 1).split(' ')
        var hash = checksum(), body, length
        hash.update(fields[2])
        if (buffer[i - 1] == 0x20) {
            body = buffer.slice(i, buffer.length - 1)
            length = body.length
            hash.update(body)
        }
        ok(fields[1] == '-' || hash.digest('hex') == fields[1], 'corrupt line: invalid checksum')
        if (buffer[i - 1] == 0x20) {
            body = deserialize(body.toString(), isKey)
        }
        var entry = { length: length, header: JSON.parse(fields[2]), body: body }
        ok(entry.header.every(function (n) { return typeof n == 'number' }), 'header values must be numbers')
        return entry
    }

    function filename (address, suffix) {
        suffix || (suffix = '')
        return path.join(directory, address + suffix)
    }

    function replace (page, suffix, callback) {
        var replacement = filename(page.address, suffix),
            permanent = filename(page.address)

        fs.stat(replacement, validator(callback)(stat))

        function stat (stat) {
            ok(stat.isFile(), 'is not a file')
            fs.unlink(permanent, unlinked)
        }

        function unlinked (error) {
            if (error && error.code != 'ENOENT') callback(error)
            else fs.rename(replacement, permanent, callback)
        }
    }

    function rename (page, from, to, callback) {
        fs.rename(filename(page.address, from), filename(page.address, to), callback)
    }

    function unlink (page, suffix, callback) {
        fs.unlink(filename(page.address, suffix), callback)
    }

    function link (head, entry) {
        var next = head.next
        entry.next = next
        next.previous = entry
        head.next = entry
        entry.previous = head
        return entry
    }

    function _unlink (entry) {
        var next = entry.next, previous = entry.previous
        next.previous = previous
        previous.next = next
        return entry
    }

    function heft (page, s) {
        page.size += s
        size += s
    }

    function createLeaf (override) {
        if (override.address == null) {
            while (!(nextAddress % 2)) nextAddress++
            override.address = nextAddress++
        }
        var page = {
            address: -1,
            cache: {},
            entries: 0,
            locks: [[]],
            ghosts: 0,
            positions: [],
            lengths: [],
            right: 0,
            size: 0
        }
        return extend(page, override)
    }

    constructors.leaf = createLeaf

    function encache (page) {
        return cache[page.address] = link(mru, page)
    }

    function _cacheRecord (page, position, record, length) {
        var key = extractor(record)
        ok(key != null, 'null keys are forbidden')

        var entry = {
            record: record,
            size: length,
            key: key,
            keySize: serialize(key, true).length
        }

        return encacheEntry(page, position, entry)
    }

    function encacheEntry (page, reference, entry) {
        ok (!page.cache[reference], 'record already cached for position')

        page.cache[reference] = entry

        heft(page, entry.size)

        return entry
    }

    function uncacheEntry (page, reference) {
        var entry = page.cache[reference]
        ok (entry, 'entry not cached')
        heft(page, -entry.size)
        delete page.cache[reference]
        return entry
    }

    function writeJSON (options, callback) {
        var check = validator(callback),
            offset = 0,
            entry,
            buffer,
            json,
            line,
            position,
            length

        ok(options.page.position != null, 'page has not been positioned: ' + options.page.position)
        ok(options.header.every(function (n) { return typeof n == 'number' }), 'header values must be numbers')

        if (options.type == 'position') {
            options.page.bookmark = { position: options.page.position }
        }

        entry = options.header.slice()
        json = JSON.stringify(entry)
        var hash = checksum()
        hash.update(json)

        length = 0

        var separator = ''
        if (options.body != null) {
            var body = serialize(options.body, options.isKey)
            separator = ' '
            length += body.length
            hash.update(body)
        }

        line = hash.digest('hex') + ' ' + json + separator

        length += Buffer.byteLength(line, 'utf8') + 1

        var entire = length + String(length).length + 1
        if (entire < length + String(entire).length + 1) {
            length = length + String(entire).length + 1
        } else {
            length = entire
        }

        buffer = new Buffer(length)
        buffer.write(String(length) + ' ' + line)
        if (options.body != null) {
            body.copy(buffer, buffer.length - 1 - body.length)
        }
        buffer[length - 1] = 0x0A

        if (options.type == 'position') {
            options.page.bookmark.length = length
        }

        position = options.page.position

        send()

        function send () {
            fs.write(options.fd, buffer, offset, buffer.length - offset, options.page.position, check(sent))
        }

        function sent(written) {
            options.page.position += written
            offset += written
            if (offset == buffer.length) {
                if (!(options.page.address % 2) || options.type == 'footer') {
                    callback(null, position, length)
                } else {
                    writeFooter(options.fd, options.page, function () {
                        callback(null, position, length, body && body.length)
                    })
                }
            } else {
                send()
            }
        }
    }

    function writeInsert (fd, page, index, record, callback) {
        var header = [ ++page.entries, index + 1 ]
        writeJSON({ fd: fd, page: page, header: header, body: record }, callback)
    }

    function writeDelete (fd, page, index, callback) {
        var header = [ ++page.entries, -(index + 1) ]
        writeJSON({ fd: fd, page: page, header: header }, callback)
    }

    function io (direction, filename, callback) {
        var check = validator(callback)

        fs.open(filename, direction[0], check(opened))

        function opened (fd) {
            fs.fstat(fd, check(stat))

            function stat (stat) {
                callback(null, fd, stat, function (buffer, position, callback) {
                    var check = validator(callback), offset = 0

                    var length = stat.size - position
                    var slice = length < buffer.length ? buffer.slice(0, length) : buffer

                    done(0)

                    function done (count) {
                        if (count < slice.length - offset) {
                            offset += count
                            fs[direction](fd, slice, offset, slice.length - offset, position + offset, check(done))
                        } else {
                            callback(null, slice, position)
                        }
                    }
                })
            }
        }
    }

    function writePositions (fd, page, callback) {
        var header = [ ++page.entries, 0, 1, page.right, page.ghosts ]
        header = header.concat(page.positions).concat(page.lengths)
        writeJSON({ fd: fd, page: page, header: header, type: 'position' }, callback)
    }

    function writeFooter (fd, page, callback) {
        ok(page.address % 2 && page.bookmark != null)
        var header = [
            ++page.entries, 0, 0, page.bookmark.position, page.bookmark.length,
            page.right || 0, page.positions.length - page.ghosts, page.position
        ]
        writeJSON({ fd: fd, page: page, header: header, type: 'footer' }, validate(callback, function (position, length) {
            page.position = header[7]
            page.entries--
            callback(null, position, length)
        }))
    }

    function readLeaf (page, callback) {
        var positions = [],
            lengths = [],
            bookmark,
            check = validator(callback)

        io('read', filename(page.address), check(opened))

        function opened (fd, stat, read) {
            var buffer = new Buffer(options.readLeafStartLength || 1024)
            read(buffer, Math.max(0, stat.size - buffer.length), check(footer))

            function footer (slice) {
                for (var i = slice.length - 2; i != -1; i--) {
                    if (slice[i] == 0x0a) {
                        var footer = readLine(slice.slice(i + 1)).header
                        bookmark = { position: footer[3], length: footer[4] }
                        page.position = footer[7]
                        ok(page.position != null, 'no page position')
                        read(new Buffer(bookmark.length), bookmark.position, check(positioned))
                        return
                    }
                }
                throw new Error('cannot find footer in last ' + buffer.length + ' bytes')
            }

            function positioned (slice) {
                var positions = readLine(slice.slice(0, bookmark.length)).header

                page.entries = positions.shift()
                ok(positions.shift() == 0, 'expected housekeeping type')
                ok(positions.shift() == 1, 'expected position type')
                page.right = positions.shift()
                page.ghosts = positions.shift()

                ok(!(positions.length % 2), 'expecting even number of positions and lengths')
                var lengths = positions.splice(positions.length / 2)

                splice('positions', page, 0, 0, positions)
                splice('lengths', page, 0, 0, lengths)

                page.bookmark = bookmark

                replay(fd, stat, read, page, bookmark.position + bookmark.length, check(done))
            }
        }

        function done () {
            page.entries--
            callback(null, page)
        }
    }

    function replay (fd, stat, read, page, position, callback) {
        var check = validator(callback),
            leaf = !!(page.address % 2),
            seen = {},
            buffer = new Buffer(options.readLeafStartLength || 1024)

        read(buffer, position, check(replay))

        function replay (slice, start) {
            for (var offset = 0, i = 0, I = slice.length; i < I; i++) {
                if (slice[i] == 0x20) {
                    var sip = slice.toString('utf8', offset, i)
                    length = parseInt(sip)
                    ok(String(length).length == sip.length, 'invalid length')
                    if (offset + length > slice.length) {
                        break
                    }
                    var position = start + offset
                    ok(length)
                    var entry = readLine(slice.slice(offset, offset + length), !leaf)
                    var header = entry.header
                    ok(header.shift() == ++page.entries, 'entry count is off')
                    var index = header.shift()
                    if (leaf) {
                        if (index > 0) {
                            seen[position] = true
                            splice('positions', page, index - 1, 0, position)
                            splice('lengths', page, index - 1, 0, length)
                            _cacheRecord(page, position, entry.body, entry.length)
                        } else if (~index == 0 && page.address != 1) {
                            ok(!page.ghosts, 'double ghosts')
                            page.ghosts++
                        } else if (index < 0) {
                            var outgoing = splice('positions', page, -(index + 1), 1).shift()
                            if (seen[outgoing]) uncacheEntry(page, outgoing)
                            splice('lengths', page, -(index + 1), 1)
                        }
                    } else {
                        if (index > 0) {
                            var address = header.shift()
                            splice('addresses', page, index - 1, 0, address)
                            if (index - 1) {
                                encacheKey(page, address, entry.body, entry.length)
                            }
                        } else {
                            var cut = splice('addresses', page, ~index, 1)
                            if (~index) {
                                uncacheEntry(page, cut[0])
                            }
                        }
                    }
                    i = offset = offset + length
                }
            }

            if (start + buffer.length < stat.size) {
                if (offset == 0) {
                    buffer = new Buffer(buffer.length * 2)
                    read(buffer, start, check(replay))
                } else {
                    read(buffer, start + offset, check(replay))
                }
            } else {
                fs.close(fd, check(closed))
            }
        }

        function closed () {
            callback(null, page)
        }
    }

    function readRecord (page, position, length, callback) {
        var check = validator(callback), entry

        if (page.position) positioned()
        else fs.stat(filename(page.address), check(stat))

        function stat (stat) {
            page.position = stat.size
            positioned(stat.size)
        }

        function positioned () {
            fs.open(filename(page.address), 'r', check(input))
        }

        function input (fd) {
            read()

            function read () {
                fs.read(fd, new Buffer(length), 0, length, position, check(json))
            }

            function json (bytes, buffer) {
                ok(bytes == length, 'incomplete read')
                ok(buffer[length - 1] == 0x0A, 'newline expected')
                entry = readLine(buffer, false)
                fs.close(fd, check(closed))
            }
        }

        function closed() {
            callback(null, entry)
        }
    }

    function rewriteLeaf (page, suffix, callback) {
        var check = validator(callback),
            cache = {},
            index = 0,
            fd, positions, lengths

        fs.open(filename(page.address, suffix), 'w', 0644, check(opened))

        function opened ($1) {
            fd = $1

            page.position = 0
            page.entries = 0

            positions = splice('positions', page, 0, page.positions.length)
            lengths = splice('lengths', page, 0, page.lengths.length)

            writePositions(fd, page, check(iterate))
        }

        function iterate () {
            if (positions.length) rewrite()
            else if (page.positions.length) append()
            else close()
        }

        function rewrite () {
            var position = positions.shift(), length = lengths.shift(), entry

            stash(page, position, length, check(stashed))

            function stashed ($) {
                uncacheEntry(page, position)
                writeInsert(fd, page, index++, (entry = $).record, check(written))
            }

            function written (position, length) {
                splice('positions', page, page.positions.length, 0, position)
                splice('lengths', page, page.lengths.length, 0, length)
                cache[position] = entry
                iterate()
            }
        }

        function append() {
            var entry
            for (var position in cache) {
                entry = cache[position]
                encacheEntry(page, position, entry)
            }
            writePositions(fd, page, check(close))
        }

        function close() {
            fs.close(fd, callback)
        }
    }

    function createBranch (override) {
        if (override.address == null) {
            while (nextAddress % 2) nextAddress++
            override.address = nextAddress++
        }
        var page = {
            address: -1,
            addresses: [],
            cache: {},
            locks: [[]],
            penultimate: true,
            entries: 0,
            size: 0
        }
        return extend(page, override)
    }
    constructors.branch = createBranch

    function splice (collection, page, offset, length, insert) {
        ok(typeof collection == 'string', 'incorrect collection passed to splice')

        var values = page[collection], json, removals

        ok(values, 'incorrect collection passed to splice')

        if (length) {
            removals = values.splice(offset, length)

            json = values.length == 0 ? '[' + removals.join(',') + ']'
                                                                : ',' + removals.join(',')

            heft(page, -json.length)
        } else {
            removals = []
        }

        if (insert != null) {
            if (! Array.isArray(insert)) insert = [ insert ]
            if (insert.length) {
                json = values.length == 0 ? '[' + insert.join(',') + ']'
                                                                    : ',' + insert.join(',')

                heft(page, json.length)

                values.splice.apply(values, [ offset, 0 ].concat(insert))
            }
        }
        return removals
    }

    function encacheKey (page, address, key, length) {
        return encacheEntry(page, address, { key: key, size: length })
    }

    function writeBranch (page, suffix, callback) {
        var check = validator(callback),
            addresses = page.addresses.slice(),
            keys = addresses.map(function (address, index) { return page.cache[address] })

        ok(keys[0] === (void(0)), 'first key is null')
        ok(keys.slice(1).every(function (key) { return key != null }), 'null keys')

        page.entries = 0
        page.position = 0

        fs.open(filename(page.address, suffix), 'w', 0644, check(opened))

        function opened (fd) {
            write()

            function write () {
                if (addresses.length) {
                    var address = addresses.shift()
                    var key = page.entries ? getKey(page.cache[address]) : null
                    page.entries++
                    var header = [ page.entries, page.entries, address ]
                    writeJSON({ fd: fd, page: page, header: header, body: key, isKey: true }, check(write))
                } else {
                    fs.close(fd, check(closed))
                }
            }
        }

        function closed () {
            callback(null)
        }
    }

    function readBranch (page, callback) {<commit_msg>Rename to `readEntry` and `writeEntry`.<commit_after>function extend(to, from) {
    for (var key in from) to[key] = from[key]
    return to
}

var __slice = [].slice

/*function say() {
        var args = __slice.call(arguments)
        console.log(require('util').inspect(args, false, null))
}*/

function compare (a, b) { return a < b ? -1 : a > b ? 1 : 0 }

function extract (a) { return a }

function classify () {
    var i, I, name
    for (i = 0, I = arguments.length; i < I; i++) {
        name = arguments[i].name
        if (name[0] == '_')
            this.__defineGetter__(name.slice(1), arguments[i])
        else if (name[name.length - 1] == '_')
            this.__defineSetter__(name.slice(0, name.length - 1), arguments[i])
        else
            this[arguments[i].name] = arguments[i]
    }
    return this
}

function Strata (options) {
    var directory = options.directory,
        extractor = options.extractor || extract,
        comparator = options.comparator || compare,
        fs = options.fs || require('fs'),
        path = options.path || require('path'),
        ok = function (condition, message) { if (!condition) throw new Error(message) },
        cache = {},
        mru = { address: null },
        nextAddress = 0,
        length = 1024,
        balancer = new Balancer(),
        balancing,
        size = 0,
        checksum,
        constructors = {},
        serialize = options.serialize || function (object) { return new Buffer(JSON.stringify(object)) },
        deserialize = options.deserialize || function (buffer) { return JSON.parse(buffer.toString()) },
        tracer = options.tracer || function () { arguments[2]() }

    checksum = (function () {
        if (typeof options.checksum == 'function') return options.checksum
        var algorithm
        switch (algorithm = options.checksum || 'sha1') {
        case 'none':
            return function () {
                return {
                    update: function () {},
                    digest: function () { return '0' }
                }
            }
        default:
            var crypto = require('crypto')
            return function (m) { return crypto.createHash(algorithm) }
        }
    })()

    function validator (callback) {
        return function (forward, type, report) { return validate(callback, forward, type, report) }
    }

    var thrownByUser

    function validate (callback, forward, type, report) {
        ok(typeof forward == 'function', 'no forward function')
        ok(typeof callback == 'function','no callback function')
        return function (error) {
            if (error) {
                toUserLand(callback, error)
            } else {
                try {
                    if (type && report) {
                        tracer(type, report, validate(callback, forward))
                    } else {
                        forward.apply(null, __slice.call(arguments, 1))
                    }
                } catch (error) {
                    if (thrownByUser === error) {
                        throw error
                    }
                    toUserLand(callback, error)
                }
            }
        }
    }

    function toUserLand (callback) {
        try {
            callback.apply(null, __slice.call(arguments, 1))
        } catch (error) {
            thrownByUser = error
            throw error
        }
    }

    function _size () { return size }

    function _nextAddress () { return nextAddress }

    mru.next = mru.previous = mru

    function report () {
        return {
            size: size,
            nextAddress: nextAddress,
            cache: Object.keys(cache)
        }
    }

    function readEntry (buffer, isKey) {
        for (var count = 2, i = 0, I = buffer.length; i < I && count; i++) {
            if (buffer[i] == 0x20) count--
        }
        for (count = 1; i < I && count; i++) {
            if (buffer[i] == 0x20 || buffer[i] == 0x0a) count--
        }
        ok(!count, 'corrupt line: could not find end of line header')
        var fields = buffer.toString('utf8', 0, i - 1).split(' ')
        var hash = checksum(), body, length
        hash.update(fields[2])
        if (buffer[i - 1] == 0x20) {
            body = buffer.slice(i, buffer.length - 1)
            length = body.length
            hash.update(body)
        }
        ok(fields[1] == '-' || hash.digest('hex') == fields[1], 'corrupt line: invalid checksum')
        if (buffer[i - 1] == 0x20) {
            body = deserialize(body.toString(), isKey)
        }
        var entry = { length: length, header: JSON.parse(fields[2]), body: body }
        ok(entry.header.every(function (n) { return typeof n == 'number' }), 'header values must be numbers')
        return entry
    }

    function filename (address, suffix) {
        suffix || (suffix = '')
        return path.join(directory, address + suffix)
    }

    function replace (page, suffix, callback) {
        var replacement = filename(page.address, suffix),
            permanent = filename(page.address)

        fs.stat(replacement, validator(callback)(stat))

        function stat (stat) {
            ok(stat.isFile(), 'is not a file')
            fs.unlink(permanent, unlinked)
        }

        function unlinked (error) {
            if (error && error.code != 'ENOENT') callback(error)
            else fs.rename(replacement, permanent, callback)
        }
    }

    function rename (page, from, to, callback) {
        fs.rename(filename(page.address, from), filename(page.address, to), callback)
    }

    function unlink (page, suffix, callback) {
        fs.unlink(filename(page.address, suffix), callback)
    }

    function link (head, entry) {
        var next = head.next
        entry.next = next
        next.previous = entry
        head.next = entry
        entry.previous = head
        return entry
    }

    function _unlink (entry) {
        var next = entry.next, previous = entry.previous
        next.previous = previous
        previous.next = next
        return entry
    }

    function heft (page, s) {
        page.size += s
        size += s
    }

    function createLeaf (override) {
        if (override.address == null) {
            while (!(nextAddress % 2)) nextAddress++
            override.address = nextAddress++
        }
        var page = {
            address: -1,
            cache: {},
            entries: 0,
            locks: [[]],
            ghosts: 0,
            positions: [],
            lengths: [],
            right: 0,
            size: 0
        }
        return extend(page, override)
    }

    constructors.leaf = createLeaf

    function encache (page) {
        return cache[page.address] = link(mru, page)
    }

    function _cacheRecord (page, position, record, length) {
        var key = extractor(record)
        ok(key != null, 'null keys are forbidden')

        var entry = {
            record: record,
            size: length,
            key: key,
            keySize: serialize(key, true).length
        }

        return encacheEntry(page, position, entry)
    }

    function encacheEntry (page, reference, entry) {
        ok (!page.cache[reference], 'record already cached for position')

        page.cache[reference] = entry

        heft(page, entry.size)

        return entry
    }

    function uncacheEntry (page, reference) {
        var entry = page.cache[reference]
        ok (entry, 'entry not cached')
        heft(page, -entry.size)
        delete page.cache[reference]
        return entry
    }

    function writeEntry (options, callback) {
        var check = validator(callback),
            offset = 0,
            entry,
            buffer,
            json,
            line,
            position,
            length

        ok(options.page.position != null, 'page has not been positioned: ' + options.page.position)
        ok(options.header.every(function (n) { return typeof n == 'number' }), 'header values must be numbers')

        if (options.type == 'position') {
            options.page.bookmark = { position: options.page.position }
        }

        entry = options.header.slice()
        json = JSON.stringify(entry)
        var hash = checksum()
        hash.update(json)

        length = 0

        var separator = ''
        if (options.body != null) {
            var body = serialize(options.body, options.isKey)
            separator = ' '
            length += body.length
            hash.update(body)
        }

        line = hash.digest('hex') + ' ' + json + separator

        length += Buffer.byteLength(line, 'utf8') + 1

        var entire = length + String(length).length + 1
        if (entire < length + String(entire).length + 1) {
            length = length + String(entire).length + 1
        } else {
            length = entire
        }

        buffer = new Buffer(length)
        buffer.write(String(length) + ' ' + line)
        if (options.body != null) {
            body.copy(buffer, buffer.length - 1 - body.length)
        }
        buffer[length - 1] = 0x0A

        if (options.type == 'position') {
            options.page.bookmark.length = length
        }

        position = options.page.position

        send()

        function send () {
            fs.write(options.fd, buffer, offset, buffer.length - offset, options.page.position, check(sent))
        }

        function sent(written) {
            options.page.position += written
            offset += written
            if (offset == buffer.length) {
                if (!(options.page.address % 2) || options.type == 'footer') {
                    callback(null, position, length)
                } else {
                    writeFooter(options.fd, options.page, function () {
                        callback(null, position, length, body && body.length)
                    })
                }
            } else {
                send()
            }
        }
    }

    function writeInsert (fd, page, index, record, callback) {
        var header = [ ++page.entries, index + 1 ]
        writeEntry({ fd: fd, page: page, header: header, body: record }, callback)
    }

    function writeDelete (fd, page, index, callback) {
        var header = [ ++page.entries, -(index + 1) ]
        writeEntry({ fd: fd, page: page, header: header }, callback)
    }

    function io (direction, filename, callback) {
        var check = validator(callback)

        fs.open(filename, direction[0], check(opened))

        function opened (fd) {
            fs.fstat(fd, check(stat))

            function stat (stat) {
                callback(null, fd, stat, function (buffer, position, callback) {
                    var check = validator(callback), offset = 0

                    var length = stat.size - position
                    var slice = length < buffer.length ? buffer.slice(0, length) : buffer

                    done(0)

                    function done (count) {
                        if (count < slice.length - offset) {
                            offset += count
                            fs[direction](fd, slice, offset, slice.length - offset, position + offset, check(done))
                        } else {
                            callback(null, slice, position)
                        }
                    }
                })
            }
        }
    }

    function writePositions (fd, page, callback) {
        var header = [ ++page.entries, 0, 1, page.right, page.ghosts ]
        header = header.concat(page.positions).concat(page.lengths)
        writeEntry({ fd: fd, page: page, header: header, type: 'position' }, callback)
    }

    function writeFooter (fd, page, callback) {
        ok(page.address % 2 && page.bookmark != null)
        var header = [
            ++page.entries, 0, 0, page.bookmark.position, page.bookmark.length,
            page.right || 0, page.positions.length - page.ghosts, page.position
        ]
        writeEntry({ fd: fd, page: page, header: header, type: 'footer' }, validate(callback, function (position, length) {
            page.position = header[7]
            page.entries--
            callback(null, position, length)
        }))
    }

    function readLeaf (page, callback) {
        var positions = [],
            lengths = [],
            bookmark,
            check = validator(callback)

        io('read', filename(page.address), check(opened))

        function opened (fd, stat, read) {
            var buffer = new Buffer(options.readLeafStartLength || 1024)
            read(buffer, Math.max(0, stat.size - buffer.length), check(footer))

            function footer (slice) {
                for (var i = slice.length - 2; i != -1; i--) {
                    if (slice[i] == 0x0a) {
                        var footer = readEntry(slice.slice(i + 1)).header
                        bookmark = { position: footer[3], length: footer[4] }
                        page.position = footer[7]
                        ok(page.position != null, 'no page position')
                        read(new Buffer(bookmark.length), bookmark.position, check(positioned))
                        return
                    }
                }
                throw new Error('cannot find footer in last ' + buffer.length + ' bytes')
            }

            function positioned (slice) {
                var positions = readEntry(slice.slice(0, bookmark.length)).header

                page.entries = positions.shift()
                ok(positions.shift() == 0, 'expected housekeeping type')
                ok(positions.shift() == 1, 'expected position type')
                page.right = positions.shift()
                page.ghosts = positions.shift()

                ok(!(positions.length % 2), 'expecting even number of positions and lengths')
                var lengths = positions.splice(positions.length / 2)

                splice('positions', page, 0, 0, positions)
                splice('lengths', page, 0, 0, lengths)

                page.bookmark = bookmark

                replay(fd, stat, read, page, bookmark.position + bookmark.length, check(done))
            }
        }

        function done () {
            page.entries--
            callback(null, page)
        }
    }

    function replay (fd, stat, read, page, position, callback) {
        var check = validator(callback),
            leaf = !!(page.address % 2),
            seen = {},
            buffer = new Buffer(options.readLeafStartLength || 1024)

        read(buffer, position, check(replay))

        function replay (slice, start) {
            for (var offset = 0, i = 0, I = slice.length; i < I; i++) {
                if (slice[i] == 0x20) {
                    var sip = slice.toString('utf8', offset, i)
                    length = parseInt(sip)
                    ok(String(length).length == sip.length, 'invalid length')
                    if (offset + length > slice.length) {
                        break
                    }
                    var position = start + offset
                    ok(length)
                    var entry = readEntry(slice.slice(offset, offset + length), !leaf)
                    var header = entry.header
                    ok(header.shift() == ++page.entries, 'entry count is off')
                    var index = header.shift()
                    if (leaf) {
                        if (index > 0) {
                            seen[position] = true
                            splice('positions', page, index - 1, 0, position)
                            splice('lengths', page, index - 1, 0, length)
                            _cacheRecord(page, position, entry.body, entry.length)
                        } else if (~index == 0 && page.address != 1) {
                            ok(!page.ghosts, 'double ghosts')
                            page.ghosts++
                        } else if (index < 0) {
                            var outgoing = splice('positions', page, -(index + 1), 1).shift()
                            if (seen[outgoing]) uncacheEntry(page, outgoing)
                            splice('lengths', page, -(index + 1), 1)
                        }
                    } else {
                        if (index > 0) {
                            var address = header.shift()
                            splice('addresses', page, index - 1, 0, address)
                            if (index - 1) {
                                encacheKey(page, address, entry.body, entry.length)
                            }
                        } else {
                            var cut = splice('addresses', page, ~index, 1)
                            if (~index) {
                                uncacheEntry(page, cut[0])
                            }
                        }
                    }
                    i = offset = offset + length
                }
            }

            if (start + buffer.length < stat.size) {
                if (offset == 0) {
                    buffer = new Buffer(buffer.length * 2)
                    read(buffer, start, check(replay))
                } else {
                    read(buffer, start + offset, check(replay))
                }
            } else {
                fs.close(fd, check(closed))
            }
        }

        function closed () {
            callback(null, page)
        }
    }

    function readRecord (page, position, length, callback) {
        var check = validator(callback), entry

        if (page.position) positioned()
        else fs.stat(filename(page.address), check(stat))

        function stat (stat) {
            page.position = stat.size
            positioned(stat.size)
        }

        function positioned () {
            fs.open(filename(page.address), 'r', check(input))
        }

        function input (fd) {
            read()

            function read () {
                fs.read(fd, new Buffer(length), 0, length, position, check(json))
            }

            function json (bytes, buffer) {
                ok(bytes == length, 'incomplete read')
                ok(buffer[length - 1] == 0x0A, 'newline expected')
                entry = readEntry(buffer, false)
                fs.close(fd, check(closed))
            }
        }

        function closed() {
            callback(null, entry)
        }
    }

    function rewriteLeaf (page, suffix, callback) {
        var check = validator(callback),
            cache = {},
            index = 0,
            fd, positions, lengths

        fs.open(filename(page.address, suffix), 'w', 0644, check(opened))

        function opened ($1) {
            fd = $1

            page.position = 0
            page.entries = 0

            positions = splice('positions', page, 0, page.positions.length)
            lengths = splice('lengths', page, 0, page.lengths.length)

            writePositions(fd, page, check(iterate))
        }

        function iterate () {
            if (positions.length) rewrite()
            else if (page.positions.length) append()
            else close()
        }

        function rewrite () {
            var position = positions.shift(), length = lengths.shift(), entry

            stash(page, position, length, check(stashed))

            function stashed ($) {
                uncacheEntry(page, position)
                writeInsert(fd, page, index++, (entry = $).record, check(written))
            }

            function written (position, length) {
                splice('positions', page, page.positions.length, 0, position)
                splice('lengths', page, page.lengths.length, 0, length)
                cache[position] = entry
                iterate()
            }
        }

        function append() {
            var entry
            for (var position in cache) {
                entry = cache[position]
                encacheEntry(page, position, entry)
            }
            writePositions(fd, page, check(close))
        }

        function close() {
            fs.close(fd, callback)
        }
    }

    function createBranch (override) {
        if (override.address == null) {
            while (nextAddress % 2) nextAddress++
            override.address = nextAddress++
        }
        var page = {
            address: -1,
            addresses: [],
            cache: {},
            locks: [[]],
            penultimate: true,
            entries: 0,
            size: 0
        }
        return extend(page, override)
    }
    constructors.branch = createBranch

    function splice (collection, page, offset, length, insert) {
        ok(typeof collection == 'string', 'incorrect collection passed to splice')

        var values = page[collection], json, removals

        ok(values, 'incorrect collection passed to splice')

        if (length) {
            removals = values.splice(offset, length)

            json = values.length == 0 ? '[' + removals.join(',') + ']'
                                                                : ',' + removals.join(',')

            heft(page, -json.length)
        } else {
            removals = []
        }

        if (insert != null) {
            if (! Array.isArray(insert)) insert = [ insert ]
            if (insert.length) {
                json = values.length == 0 ? '[' + insert.join(',') + ']'
                                                                    : ',' + insert.join(',')

                heft(page, json.length)

                values.splice.apply(values, [ offset, 0 ].concat(insert))
            }
        }
        return removals
    }

    function encacheKey (page, address, key, length) {
        return encacheEntry(page, address, { key: key, size: length })
    }

    function writeBranch (page, suffix, callback) {
        var check = validator(callback),
            addresses = page.addresses.slice(),
            keys = addresses.map(function (address, index) { return page.cache[address] })

        ok(keys[0] === (void(0)), 'first key is null')
        ok(keys.slice(1).every(function (key) { return key != null }), 'null keys')

        page.entries = 0
        page.position = 0

        fs.open(filename(page.address, suffix), 'w', 0644, check(opened))

        function opened (fd) {
            write()

            function write () {
                if (addresses.length) {
                    var address = addresses.shift()
                    var key = page.entries ? getKey(page.cache[address]) : null
                    page.entries++
                    var header = [ page.entries, page.entries, address ]
                    writeEntry({ fd: fd, page: page, header: header, body: key, isKey: true }, check(write))
                } else {
                    fs.close(fd, check(closed))
                }
            }
        }

        function closed () {
            callback(null)
        }
    }

    function readBranch (page, callback) {
{'fraction_non_alphanumeric': 0.11685878020613165, 'fraction_numerical': 0.007147059464406336, 'mean_word_length': 1.4563262684649967, 'pattern_counts': {'":': 0, '<': 23, '<?xml version=': 0, '>': 11, 'https://': 0, 'lorem ipsum': 0, 'www.': 0, 'xml': 0}, 'pii_count': 0, 'substrings_counts': 0, 'word_list_counts': {'cursed_substrings.json': 16, 'profanity_word_list.json': 0, 'sexual_word_list.json': 0, 'zh_pornsignals.json': 0}}
{'dir': 'git-commits-cleaned', 'id': '269519', 'n_tokens_mistral': 12478, 'n_tokens_neox': 11681, 'n_words': 3152}