 # A Streamline.js friendly evented I/O b&#x2011;tree for Node.js.
 #
+# TK Define ***least child page***.
+#
+# **REMEMBER**: Alan! Your audience is you, or someone who knows enough Node.js,
+# CoffeeScript and algorithms to hack on this. This is not a lesson on
+# b&#x2011;trees. (Note to self as I write Docco.)
+#
 # ## Purpose
-#
-# TK Define ***least child page***.
 #
 # Strata stores JSON objects on disk, according to a sort order of your
 # choosing, indexed for fast retrieval.

    if fs.readdir(@directory, _).filter((f) -> not /^\./.test(f)).length
      throw new Error "database #{@directory} is not empty."
    # Create a root branch with a single empty leaf.
    root = @encache @createBranch @nextAddress++, penultimate: true, loaded: true
    leaf = @encache @createLeaf -(@nextAddress++), loaded: true
    @splice root, 0, 0, leaf.address
    # Write the root branch.
    @rewriteBranches root, "replace", _
    @rewriteLeaf leaf, "replace", _
    @replace leaf, "replace", _
    @replace root, "replace", _

    # The queue is implemented using an array of arrays. Shared locks are
    # grouped inside one of the arrays in the queue element. Exclusive locks are
    # queued alone as a single element in the array in the queue element.

    #
    if page = @cache[address]
      # Move the page to the head of the most-recently user list.
      @link @mru, @unlink page
    #
    else
      # Create a page to load with an empty `load` queue. The presence of the
      # `load` queue indicates that the page needs to be read from file.
      creator = "create#{if address < 0 then "Leaf" else "Branch"}"
      page = @encache @[creator](address, { load: [] })

    # #### Lock Implementation
    #
    # We don't use mutexes, of course, because Node.js doesn't have the concept
    # of mutexes to protect critical sections of code the way that threaded
    # programming platforms do. 
    #
    # Nor do we use file system locking.
    #
    # Instead, we simulate locks using callbacks. A call to `lock` is an evented
    # function call that provides a callback. If the `lock` method can grant the
    # lock request to the caller, the lock method will invoke the callback.
    #
    # If the `lock` method cannot grant the lock request, the `lock` method will
    # queue the callback into a queue of callbacks associated with the page.
    # When other descents release the locks that prevent the lock request, the
    # lock request callback is dequeued, and the callback invoked.

    # The callback is always added to the queue, even if it is not blocked and
    # will execute immediately. The array in the queue element acts as a lock
    # count.
    #
    # If the callback we add to the queue is added to the first queue element is
    # executed immediately. Otherwise, it will be executed when the preceding
    # queue elements have completed.
    #
    # When an exclusive lock is queued, an empty array is appended to the queue.
    # Subsequent read lock callbacks are appended to the array in the last
    # element. This gives exclusive lock callbacks priority.

    locks = page.locks
    if exclusive
      throw new Error "already locked" unless locks.length % 2
      locks.push [ callback ]
      locks.push []
      if locks[0].length is 0
        locks.shift()
        @load page, callback
    else
      locks[locks.length - 1].push callback
      if locks.length is 1
        @load page, callback

  # #### Check JSON Size

  # Here's a temporary block of code that will assert that we're keeping an
  # accurate count of the heft of our pages. After a while, this code will be
  # removed, and we'll count on assertions in our unit tests to catch errors.

  # This only check that the JSON size is correct for the give page contents,
  # not for the entire b&#x2011;tree.
  @checkJSONSize: (page) ->
    size = 0
    if page.address < 0
      if page.positions.length
        size += JSON.stringify(page.positions).length
      for position, object of page.cache
        { record, key } = object
        if object.size isnt JSON.stringify({ record, key }).length
          throw new Error "sizes are wrong"
        size += object.size
    else
      if page.addresses.length
        size += JSON.stringify(page.addresses).length
      for position, object of page.cache
        size += JSON.stringify(object).length
    if size isnt page.size
      throw new Error "sizes are wrong"

  # ### Load

  # One or more descents may encounter the same unloaded page. Only one descent
  # should load it, the others should wait.
  #
  # In `load` we ensure that only the first descent will actually invoke the
  # load function for the page. If we are the first to encounter an unloaded
  # page, we push our callback onto the `load` queue of the page, and invoke the
  # correct read function for the page time. We provide a callback that will
  # invoke all the queued callbacks in the `load` queue to the read function.
  #
  # If we encounter an unloaded page, but there are already callbacks in the
  # queue, we know that the first descent through has invoked read, and that our
  # callback will be invoked if we will simply place it in the `load` queue and
  # do nothing more.

  # &mdash;
  load: (page, callback) ->
    # If the page is not loaded, load it.
    if page.load
      # Add our callback to the list of waiting callback.
      page.load.push callback
      # If we are the first one through, create a group callback function, then
      # pass it to the load function for the page type.
      if page.load.length is 1
        # Create a callback that will invoke all the callbacks queued to wait
        # for the page to load.
        loaded = (error) ->
          for callback in page.load
            do (callback) -> process.nextTick -> callback error, page
          # On error we reset the load list.
          if error
            page.load.length = 0
          # Otherwise, we delete the load list, because no load list means the
          # page is loaded.
          else
            IO.checkJSONSize page
            delete page.load
        # Invoke the correct read function for the page type.
        if page.address < 0
          @readLeaf page, loaded
        else
          @readBranch page, loaded
    # If the page is already loaded, we wave the descent on through.
    else
      #
      IO.checkJSONSize
      callback null, page

  # #### Unlock

