B2G/gaia/apps/email/js/ext/mailapi/worker-bootstrap.js
/**
   * Find the right block to insert a header/body into using its date and UID.
   * This is an asynchronous operation because we potentially need to load
   * blocks from disk.
   *
   * == Usage patterns
   *
   * - In initial-sync cases and scrolling down through the list, we will
   *   generate messages from a younger-to-older direction.  The insertion point
   *   will then likely occur after the last block.
   * - In update-sync cases, we should be primarily dealing with new mail which
   *   is still retrieved endTS to startTS.  The insertion point will start
   *   before the first block and then move backwards within that block.
   * - Update-sync cases may also encounter messages moved into the folder
   *   from other folders since the last sync.  An archive folder is the
   *   most likely case for this, and we would expect random additions with a
   *   high degree of clustering on message date.
   * - Update-sync cases may experience a lot of apparent message deletion due
   *   to actual deletion or moves to other folders.  These can shrink blocks
   *   and we need to consider block merges to avoid pathological behavior.
   * - Forgetting messages that are no longer being kept alive by sync settings
   *   or apparent user interest.  There's no benefit to churn for the sake of
   *   churn, so we can just forget messages in blocks wholesale when we
   *   experience disk space pressure (from ourselves or elsewhere).  In that
   *   case we will want to traverse from the startTS messages, dropping them and
   *   consolidating blocks as we go until we have freed up enough space.
   *
   * == General strategy
   *
   * - If we fall in an existing block and it won't overflow, use it.
   * - If we fall in an existing block and it would overflow, split it.
   * - If we fall outside existing blocks, check older and newer blocks in that
   *   order for a non-overflow fit.  If we would overflow, pick the existing
   *   block further from the center to perform a split.
   * - If there are no existing blocks at all, create a new one.
   * - When splitting, if we are the first or last block, split 2/3 towards the
   *   center and 1/3 towards the edge.  The idea is that growth is most likely
   *   to occur near the edges, so concentrate the empty space there without
   *   leaving the center blocks so overloaded they can't accept random
   *   additions without further splits.
   * - When splitting, otherwise, split equally-ish.
   *
   * == Block I/O
   *
   * While we can make decisions about where to insert things, we need to have
   * blocks in memory in order to perform the actual splits.  The outcome
   * of splits can't be predicted because the size of things in blocks is
   * only known when the block is loaded.
   *
   * @args[
   *   @param[type @oneof['header' 'body']]
   *   @param[date DateMS]
   *   @param[estSizeCost Number]{
   *     The rough byte cost of whatever we want to stick in a block.
   *   }
   *   @param[thing Object]
   *   @param[blockPickedCallback @func[
   *     @args[
   *       @param[blockInfo FolderBlockInfo]
   *       @param[block @oneof[HeaderBlock BodyBlock]]
   *     ]
   *   ]]{
   *     Callback function to invoke once we have found/created/made-room-for
   *     the thing in the block.  This needs to be a callback because if we need
   *     to perform any splits, we require that the block be loaded into memory
   *     first.  (For consistency and simplicity, we then made us always return
   *     the block.)
   *   }
   * ]
   */
Find the right block to insert a header/body into using its date and UID.
This is an asynchronous operation because we potentially need to load
blocks from disk.

== Usage patterns

- In initial-sync cases and scrolling down through the list, we will
generate messages from a younger-to-older direction.  The insertion point
will then likely occur after the last block.
- In update-sync cases, we should be primarily dealing with new mail which
is still retrieved endTS to startTS.  The insertion point will start
before the first block and then move backwards within that block.
- Update-sync cases may also encounter messages moved into the folder
from other folders since the last sync.  An archive folder is the
most likely case for this, and we would expect random additions with a
high degree of clustering on message date.
- Update-sync cases may experience a lot of apparent message deletion due
to actual deletion or moves to other folders.  These can shrink blocks
and we need to consider block merges to avoid pathological behavior.
- Forgetting messages that are no longer being kept alive by sync settings
or apparent user interest.  There's no benefit to churn for the sake of
churn, so we can just forget messages in blocks wholesale when we
experience disk space pressure (from ourselves or elsewhere).  In that
case we will want to traverse from the startTS messages, dropping them and
consolidating blocks as we go until we have freed up enough space.

== General strategy

- If we fall in an existing block and it won't overflow, use it.
- If we fall in an existing block and it would overflow, split it.
- If we fall outside existing blocks, check older and newer blocks in that
order for a non-overflow fit.  If we would overflow, pick the existing
block further from the center to perform a split.
- If there are no existing blocks at all, create a new one.
- When splitting, if we are the first or last block, split 2/3 towards the
center and 1/3 towards the edge.  The idea is that growth is most likely
to occur near the edges, so concentrate the empty space there without
leaving the center blocks so overloaded they can't accept random
additions without further splits.
- When splitting, otherwise, split equally-ish.

== Block I/O

While we can make decisions about where to insert things, we need to have
blocks in memory in order to perform the actual splits.  The outcome
of splits can't be predicted because the size of things in blocks is
only known when the block is loaded.


Find the right block to insert a header / body into using its date and UID . This is an asynchronous operation because we potentially need to load blocks from disk . == Usage patterns - In initial - sync cases and scrolling down through the list we will generate messages from a younger - to - older direction . The insertion point will then likely occur after the last block . - In update - sync cases we should be primarily dealing with new mail which is still retrieved endTS to startTS . The insertion point will start before the first block and then move backwards within that block . - Update - sync cases may also encounter messages moved into the folder from other folders since the last sync . An archive folder is the most likely case for this and we would expect random additions with a high degree of clustering on message date . - Update - sync cases may experience a lot of apparent message deletion due to actual deletion or moves to other folders . These can shrink blocks and we need to consider block merges to avoid pathological behavior . - Forgetting messages that are no longer being kept alive by sync settings or apparent user interest . There ' s no benefit to churn for the sake of churn so we can just forget messages in blocks wholesale when we experience disk space pressure ( from ourselves or elsewhere ) . In that case we will want to traverse from the startTS messages dropping them and consolidating blocks as we go until we have freed up enough space . == General strategy - If we fall in an existing block and it won ' t overflow use it . - If we fall in an existing block and it would overflow split it . - If we fall outside existing blocks check older and newer blocks in that order for a non - overflow fit . If we would overflow pick the existing block further from the center to perform a split . - If there are no existing blocks at all create a new one . - When splitting if we are the first or last block split 2 / 3 towards the center and 1 / 3 towards the edge . The idea is that growth is most likely to occur near the edges so concentrate the empty space there without leaving the center blocks so overloaded they can ' t accept random additions without further splits . - When splitting otherwise split equally - ish . == Block I / O While we can make decisions about where to insert things we need to have blocks in memory in order to perform the actual splits . The outcome of splits can ' t be predicted because the size of things in blocks is only known when the block is loaded .
function ifs__pickInsertionBlocks(
      type, date, uid, srvid, estSizeCost, thing, blockPickedCallback) {
    var blockInfoList, loadedBlockInfoList, blockMap, makeBlock, insertInBlock,
        splitBlock, serverIdBlockMapping;
    if (type === 'header') {
      blockInfoList = this._headerBlockInfos;
      loadedBlockInfoList = this._loadedHeaderBlockInfos;
      blockMap = this._headerBlocks;
      serverIdBlockMapping = this._serverIdHeaderBlockMapping;
      makeBlock = this._bound_makeHeaderBlock;
      insertInBlock = this._bound_insertHeaderInBlock;
      splitBlock = this._bound_splitHeaderBlock;
    }
    else {
      blockInfoList = this._bodyBlockInfos;
      loadedBlockInfoList = this._loadedBodyBlockInfos;
      blockMap = this._bodyBlocks;
      serverIdBlockMapping = null; 
      makeBlock = this._bound_makeBodyBlock;
      insertInBlock = this._bound_insertBodyInBlock;
      splitBlock = this._bound_splitBodyBlock;
    }
    var infoTuple = this._findRangeObjIndexForDateAndID(blockInfoList,
                                                        date, uid),
        iInfo = infoTuple[0], info = infoTuple[1];
    if (!info) {
      if (blockInfoList.length === 0) {
        info = makeBlock(date, uid, date, uid);
        blockInfoList.splice(iInfo, 0, info);
        loadedBlockInfoList.push(info);
      }
      else if (iInfo < blockInfoList.length &&
               blockInfoList[iInfo].estSize + estSizeCost < MAX_BLOCK_SIZE) {
        info = blockInfoList[iInfo];
        if (STRICTLY_AFTER(date, info.endTS)) {
          info.endTS = date;
          info.endUID = uid;
        }
        else if (date === info.endTS &&
                 uid > info.endUID) {
          info.endUID = uid;
        }
      }
      else if (iInfo > 0 &&
               blockInfoList[iInfo - 1].estSize + estSizeCost < MAX_BLOCK_SIZE){
        info = blockInfoList[--iInfo];
        if (BEFORE(date, info.startTS)) {
          info.startTS = date;
          info.startUID = uid;
        }
        else if (date === info.startTS &&
                 uid < info.startUID) {
          info.startUID = uid;
        }
      }
      else if ((iInfo > 0 && iInfo < blockInfoList.length / 2) ||
               (iInfo === blockInfoList.length)) {
        info = blockInfoList[--iInfo];
        if (BEFORE(date, info.startTS)) {
          info.startTS = date;
          info.startUID = uid;
        }
        else if (date === info.startTS &&
                 uid < info.startUID) {
          info.startUID = uid;
        }
      }
      else {
        info = blockInfoList[iInfo];
        if (STRICTLY_AFTER(date, info.endTS)) {
          info.endTS = date;
          info.endUID = uid;
        }
        else if (date === info.endTS &&
                 uid > info.endUID) {
          info.endUID = uid;
        }
      }
    }
    function processBlock(block) { 
      info.estSize += estSizeCost;
      info.count++;
      insertInBlock(thing, uid, info, block);
      if (info.count > 1 && info.estSize >= MAX_BLOCK_SIZE) {
        var firstBlockTarget;
        if (iInfo === 0)
          firstBlockTarget = BLOCK_SPLIT_SMALL_PART;
        else if (iInfo === blockInfoList.length - 1)
          firstBlockTarget = BLOCK_SPLIT_LARGE_PART;
        else
          firstBlockTarget = BLOCK_SPLIT_EQUAL_PART;
        var olderInfo;
        olderInfo = splitBlock(info, block, firstBlockTarget);
        blockInfoList.splice(iInfo + 1, 0, olderInfo);
        loadedBlockInfoList.push(olderInfo);
        if (BEFORE(date, olderInfo.endTS) ||
            ((date === olderInfo.endTS) && (uid <= olderInfo.endUID))) {
          iInfo++;
          info = olderInfo;
          block = blockMap[info.blockId];
        }
      }
      if (serverIdBlockMapping && srvid)
        serverIdBlockMapping[srvid] = info.blockId;
      if (blockPickedCallback) {
        blockPickedCallback(info, block);
      }
    }
    if (blockMap.hasOwnProperty(info.blockId))
      processBlock.call(this, blockMap[info.blockId]);
    else
      this._loadBlock(type, info, processBlock.bind(this));
  }
function ifs__pickInsertionBlocks ( type , date , uid , srvid , estSizeCost , thing , blockPickedCallback ) { var blockInfoList , loadedBlockInfoList , blockMap , makeBlock , insertInBlock , splitBlock , serverIdBlockMapping ; if ( type === 'header' ) { blockInfoList = this . _headerBlockInfos ; loadedBlockInfoList = this . _loadedHeaderBlockInfos ; blockMap = this . _headerBlocks ; serverIdBlockMapping = this . _serverIdHeaderBlockMapping ; makeBlock = this . _bound_makeHeaderBlock ; insertInBlock = this . _bound_insertHeaderInBlock ; splitBlock = this . _bound_splitHeaderBlock ; } else { blockInfoList = this . _bodyBlockInfos ; loadedBlockInfoList = this . _loadedBodyBlockInfos ; blockMap = this . _bodyBlocks ; serverIdBlockMapping = null ; makeBlock = this . _bound_makeBodyBlock ; insertInBlock = this . _bound_insertBodyInBlock ; splitBlock = this . _bound_splitBodyBlock ; } var infoTuple = this . _findRangeObjIndexForDateAndID ( blockInfoList , date , uid ) , iInfo = infoTuple [ 0 ] , info = infoTuple [ 1 ] ; if ( ! info ) { if ( blockInfoList . length === 0 ) { info = makeBlock ( date , uid , date , uid ) ; blockInfoList . splice ( iInfo , 0 , info ) ; loadedBlockInfoList . push ( info ) ; } else if ( iInfo < blockInfoList . length && blockInfoList [ iInfo ] . estSize + estSizeCost < MAX_BLOCK_SIZE ) { info = blockInfoList [ iInfo ] ; if ( STRICTLY_AFTER ( date , info . endTS ) ) { info . endTS = date ; info . endUID = uid ; } else if ( date === info . endTS && uid > info . endUID ) { info . endUID = uid ; } } else if ( iInfo > 0 && blockInfoList [ iInfo - 1 ] . estSize + estSizeCost < MAX_BLOCK_SIZE ) { info = blockInfoList [ -- iInfo ] ; if ( BEFORE ( date , info . startTS ) ) { info . startTS = date ; info . startUID = uid ; } else if ( date === info . startTS && uid < info . startUID ) { info . startUID = uid ; } } else if ( ( iInfo > 0 && iInfo < blockInfoList . length / 2 ) || ( iInfo === blockInfoList . length ) ) { info = blockInfoList [ -- iInfo ] ; if ( BEFORE ( date , info . startTS ) ) { info . startTS = date ; info . startUID = uid ; } else if ( date === info . startTS && uid < info . startUID ) { info . startUID = uid ; } } else { info = blockInfoList [ iInfo ] ; if ( STRICTLY_AFTER ( date , info . endTS ) ) { info . endTS = date ; info . endUID = uid ; } else if ( date === info . endTS && uid > info . endUID ) { info . endUID = uid ; } } } function processBlock ( block ) { info . estSize += estSizeCost ; info . count ++ ; insertInBlock ( thing , uid , info , block ) ; if ( info . count > 1 && info . estSize >= MAX_BLOCK_SIZE ) { var firstBlockTarget ; if ( iInfo === 0 ) firstBlockTarget = BLOCK_SPLIT_SMALL_PART ; else if ( iInfo === blockInfoList . length - 1 ) firstBlockTarget = BLOCK_SPLIT_LARGE_PART ; else firstBlockTarget = BLOCK_SPLIT_EQUAL_PART ; var olderInfo ; olderInfo = splitBlock ( info , block , firstBlockTarget ) ; blockInfoList . splice ( iInfo + 1 , 0 , olderInfo ) ; loadedBlockInfoList . push ( olderInfo ) ; if ( BEFORE ( date , olderInfo . endTS ) || ( ( date === olderInfo . endTS ) && ( uid <= olderInfo . endUID ) ) ) { iInfo ++ ; info = olderInfo ; block = blockMap [ info . blockId ] ; } } if ( serverIdBlockMapping && srvid ) serverIdBlockMapping [ srvid ] = info . blockId ; if ( blockPickedCallback ) { blockPickedCallback ( info , block ) ; } } if ( blockMap . hasOwnProperty ( info . blockId ) ) processBlock . call ( this , blockMap [ info . blockId ] ) ; else this . _loadBlock ( type , info , processBlock . bind ( this ) ) ; }
Find the right block to insert a header/body into using its date and UID.
Find the right block to insert a header / body into using its date and UID .
// only headers have the mapping // -- find the current containing block / insertion point // -- not in a block, find or create one // - Create a block if no blocks exist at all. // - Is there a trailing/older dude and we fit? // We are chronologically/UID-ically more recent, so check the end range // for expansion needs. // - Is there a preceding/younger dude and we fit? // We are chronologically less recent, so check the start range for // expansion needs. // Any adjacent blocks at this point are overflowing, so it's now a // question of who to split.  We pick the one further from the center that // exists. // - Preceding (if possible and) suitable OR the only choice // We are chronologically less recent, so check the start range for // expansion needs. // - It must be the trailing dude // We are chronologically/UID-ically more recent, so check the end range // for expansion needs. // (info now definitely exists and is definitely in blockInfoList) // 'this' gets explicitly bound // -- perform the insertion // We could do this after the split, but this makes things simpler if // we want to factor in the newly inserted thing's size in the // distribution of bytes. // -- split if necessary // - figure the desired resulting sizes // big part to the center at the edges (favoring front edge) // otherwise equal split // - split // - figure which of the blocks our insertion went in // otherwise, no split necessary, just use it