text:
var CloudWatchAlarm = require('./lib/cw-alarm.js');
var async = require('async');
var sleep = require('sleep');

exports.handler = function(event, context, callback){

  console.log('Received event:', JSON.stringify(event, null, 2));
  // Event stops triggering within a few minutes without a delay
  sleep.sleep(1);

  var message = JSON.parse(event.Records[0].Sns.Message);
  var cw = new CloudWatchAlarm(message);

  //Reset alarm state to OK
  cw.resetAlarm(function(err, data){
    if(err){
      console.log("Error setting alarm state", err, err.stack);
    }else{
      console.log("Successfully set alarm state");
      setMetrics(cw, event, callback);
    }
  });
}

function setMetrics(cw, event, callback){
  async.parallel({
    errors: function(callback){ cw.getMetrics('Errors', callback) },
    invocations: function(callback){ cw.getMetrics('Invocations', callback) }
    },
    function(err, results){
      if(err){
        console.log("ERROR fetching metrics", err, err.stack);
        callback(err);
      }else{
        var errors = results.errors;
        var invocations = results.invocations;
        console.log("Metrics retrieved");
        console.log("Errors: ",errors," Invocations: ",invocations);
        if(invocations != 0){
          var percentFailure = (errors / invocations) * 100
          console.log("Percent failure: ", percentFailure);
          cw.putCustomMetrics(percentFailure, function(err, data){
            if(err){
              console.log("ERROR - unable to post custom metric", err, err.stack);
              callback(err);
            }else{
              console.log("Successfully posted custom metric");
              console.log(data);
              callback();
            }
          });
        }else{
          console.log("Warning - no invocations found");
          callback();
        }
      }
    });
}


text:
import sublime, sublime_plugin
import subprocess, threading
import re
from os.path import dirname, realpath

class DocumentCommand(sublime_plugin.TextCommand):

    def run(self, edit):
        rootFolder = dirname(realpath(__file__))

        view = self.view

        for region in view.sel():
            line = view.line(region)
            line_contents = view.substr(line)

            cmdletName = re.search('\s*function\s*([\w\d\-]+)', line_contents).group(1)

            executer = RunExternalThread("powershell -InputFormat None -NonInteractive -File \"{0}\\Get-HelpTemplate.ps1\" {1}".format(rootFolder, cmdletName))
            executer.start()
            executer.join(5)

            if executer.isAlive():
                executer.kill()
                executer.error = '"{0}" killed after {1} seconds'.format(cmdletName, 5)

            if executer.error:
                sublime.error_message(executer.error)
            else:
                view.insert(edit, line.begin(), executer.output)

class RunExternalThread(threading.Thread):

    command = None
    output = None
    error = None
    process = None

    def __init__(self, command):
        threading.Thread.__init__(self)
        self.command = command

    def run(self):
        self.process = subprocess.Popen(
            self.command,
            shell = True,
            bufsize = -1,
            stdout = subprocess.PIPE,
            stderr = subprocess.PIPE,
            stdin = subprocess.PIPE,
            universal_newlines = True)

        self.output, self.error = self.process.communicate()

    def kill(self):
        self.process.kill()

redpajama_set_name: RedPajamaGithub


text:
namespace gorc {

    template <typename RangeT>
    RangeT internal_get_word(RangeT const &rng)
    {
        auto word_begin = std::begin(rng);

        // Scan to start of word.
        while((word_begin != std::end(rng)) &&
              (std::isspace(*word_begin))) {
            ++word_begin;
        }

        auto word_end = word_begin;

        // Scan to end of word.
        while((word_end != std::end(rng)) &&
              (!std::isspace(*word_end))) {
            ++word_end;
        }

        return make_range(word_begin, word_end);
    }

}

std::string gorc::wrapped(std::string const &msg, size_t width)
{
    return wrapped("", msg, width);
}

std::string gorc::wrapped(std::string const &tag,
                          std::string const &msg,
                          size_t width)
{
    std::string output;

    size_t margin = 0;
    bool needs_margin = false;

    if(!tag.empty()) {
        margin = tag.size() + 3;
        output.append("[");
        output.append(tag);
        output.append("] ");
    }

    auto line_begin = std::begin(msg);
    auto line_end = line_begin;
    while(line_begin != std::end(msg)) {
        auto next_word_rng = internal_get_word(make_range(line_end, std::end(msg)));
        auto new_line_length = static_cast<size_t>(std::end(next_word_rng) - line_begin);

        if((new_line_length > (width - margin)) ||
           (std::begin(next_word_rng) == std::end(msg))) {
            if(needs_margin) {
                output.push_back('\n');
                for(size_t i = 0; i < margin; ++i) {
                    output.push_back(' ');
                }
            }

            needs_margin = true;

            bool contains_newline = false;
            for( ; line_begin != line_end; ++line_begin) {
                if(*line_begin == '\n') {
                    ++line_begin;
                    contains_newline = true;
                    break;
                }
                else {
                    output.push_back(*line_begin);
                }
            }

            if(!contains_newline) {
                line_begin = std::begin(next_word_rng);
                line_end = std::end(next_word_rng);
            }
        }
        else {
            line_end = std::end(next_word_rng);
        }
    }

    return output;
}


text:
This is a minimal working example to get you started.

## How to run this example

Run:

    doxygen Doxyfile

within this folder and the documentation for this minimal example will be generated in Doc/html.

## How to Integrate

This example uses the provided header and footer as well as the root projects customdoxygen.css and doxyboot.js files.

* HTML_HEADER=header.html
* HTML_FOOTER=footer.html
* HTML\_EXTRA_STYLESHEET=../customdoxygen.css
* HTML\_EXTRA_FILES=../doxy-boot.js


text:
<?php
namespace keeko\framework\exceptions;

class ModuleException extends \Exception {
}


text: default content


text:
Sequelize supports read replication, i.e. having multiple servers that you can connect to when you want to do a SELECT query. When you do read replication, you specify one or more servers to act as read replicas, and one server to act as the write master, which handles all writes and updates and propagates them to the replicas (note that the actual replication process is **not** handled by Sequelize, but should be set up by database backend).

```js
const sequelize = new Sequelize('database', null, null, {
  dialect: 'mysql',
  port: 3306
  replication: {
    read: [
      { host: '8.8.8.8', username: 'read-username', password: 'some-password' },
      { host: '9.9.9.9', username: 'another-username', password: null }
    ],
    write: { host: '1.1.1.1', username: 'write-username', password: 'any-password' }
  },
  pool: { // If you want to override the options used for the read/write pool you can do so here
    max: 20,
    idle: 30000
  },
})
```

If you have any general settings that apply to all replicas you do not need to provide them for each instance. In the code above, database name and port is propagated to all replicas. The same will happen for user and password, if you leave them out for any of the replicas. Each replica has the following options:`host`,`port`,`username`,`password`,`database`.

Sequelize uses a pool to manage connections to your replicas. Internally Sequelize will maintain two pools created using `pool` configuration.

If you want to modify these, you can pass pool as an options when instantiating Sequelize, as shown above.

Each `write` or `useMaster: true` query will use write pool. For `SELECT` read pool will be used. Read replica are switched using a basic round robin scheduling.


text:
/**
 * Gulp images task
 * Optimize images
 *
 * @param  {Gulp} gulp
 * @param  {Object} plugins Available gulp plugins
 * @param  {Object} config  Configuration options
 * @return {function} Gulp task
 *
 * @example gulp images
 * @see gulpfile.js
 */
module.exports = function (gulp, plugins, config) {
	'use strict';

	return function() {
		gulp.src(config.app + '/assets/img/*')
	        .pipe(plugins.imagemin({
	            progressive: true,
	            svgoPlugins: [{removeViewBox: false}],
      			interlaced: true
	        }))
	        .pipe(gulp.dest(config.public));
    };
};


text:
import("stringutils");
import("sqlbase.sqlobj");

import("etherpad.licensing");

jimport("java.util.Random");

function run() {
  var r = new Random(0);

  function testLicense(name, org, expires, editionId, userQuota) {
    function keydataString() {
      return "{name: "+name+", org: "+org+", expires: "+expires+", editionId: "+editionId+", userQuota: "+userQuota+"}";
    }
    var key = licensing.generateNewKey(name, org, expires, editionId, userQuota);
    var info = licensing.decodeLicenseInfoFromKey(key);
    if (!info) {
      println("Generated key does not decode at all: "+keydataString());
      println("   generated key: "+key);
      throw new Error("Generated key does not decode at all.  See stdout.");
    }
    function testMatch(name, x, y) {
      if (x != y) {
        println("key match error ("+name+"): ["+x+"] != ["+y+"]");
        println("   key data: "+keydataString());
        println("   generated key: "+key);
        println("   decoded key: "+info.toSource());
        throw new Error(name+" mismatch.  see stdout.");
      }
    }
    testMatch("personName", info.personName, name);
    testMatch("orgName", info.organizationName, org);
    testMatch("expires", +info.expiresDate, +expires);
    testMatch("editionName", info.editionName, licensing.getEditionName(editionId));
    testMatch("userQuota", +info.userQuota, +userQuota);
  }

  testLicense("aaron", "test", +(new Date)+1000*60*60*24*30, licensing.getEditionId('PRIVATE_NETWORK_EVALUATION'), 1001);

  for (var editionId = 0; editionId < 3; editionId++) {
    for (var unlimitedUsers = 0; unlimitedUsers <= 1; unlimitedUsers++) {
      for (var noExpiry = 0; noExpiry <= 1; noExpiry++) {
        for (var j = 0; j < 100; j++) {
          var name = stringutils.randomString(1+r.nextInt(39));
          var org = stringutils.randomString(1+r.nextInt(39));
          var expires = null;
          if (noExpiry == 0) {
            expires = +(new Date)+(1000*60*60*24*r.nextInt(100));
          }
          var userQuota = -1;
          if (unlimitedUsers == 1) {
            userQuota = r.nextInt(1e6);
          }

          testLicense(name, org, expires, editionId, userQuota);
        }
      }
    }
  }

  // test that all previously generated keys continue to decode.
  var historicalKeys = sqlobj.selectMulti('eepnet_signups', {}, {});
  historicalKeys.forEach(function(d) {
    var key = d.licenseKey;
    if (key && !licensing.isValidKey(key)) {
      throw new Error("Historical license key no longer validates: "+key);
    }
  });

}


text:
			{{ network.name }}

		Please email me or contact me on
		{{ $first ? '' : ($last ? ' or ' : ', ') }}{{ network.name }}


text:
.omni-search {
  color: #c8c8c8;
  background-color: #fafafa;
  border: 3px solid #252526;
  box-shadow: 0 0 30px rgba(102, 96, 91, 0.26); }
  .omni-search input[type="text"], .omni-search input[type="text"]:focus, .omni-search input[type="text"]:active {
    background: #3c3c3c;
    color: #c8c8c8; }
  .omni-search ul.search-results-list li.selected-search-result, .omni-search ul.search-results-list li:hover {
    background-color: #073655; }
  .omni-search ul.search-results-list li.selected-search-result {
    color: #c8c8c8; }
  .omni-search .search-results-list li {
    background-color: #252526; }
  .omni-search .search-results-list li:not(:last-of-type) {
    border-bottom: none; }

/*# sourceMappingURL=omni-search-dark.css.map */


text:
import dedent from 'dedent-js';

import { FormatFn } from 'src/sqlFormatter';

export default function supportsLogicalOperatorNewline(format: FormatFn) {
  it('by default adds newline before logical operator', () => {
    const result = format('SELECT a WHERE true AND false;');
    expect(result).toBe(dedent`
      SELECT
        a
      WHERE
        true
        AND false;
    `);
  });

  it('supports newline after logical operator', () => {
    const result = format('SELECT a WHERE true AND false;', {
      logicalOperatorNewline: 'after',
    });
    expect(result).toBe(dedent`
      SELECT
        a
      WHERE
        true AND
        false;
    `);
  });
}


text:
set ( CMAKE_SYSTEM_NAME Linux )
set ( CMAKE_SYSTEM_PROCESSOR arm )
set ( TOOLCHAIN_PREFIX "arm-linux-gnueabi" )

set ( CMAKE_SYSROOT "/home/havard/Code/Maemo5/maemo-root" )
#set ( CMAKE_SYSROOT /usr/${TOOLCHAIN_PREFIX} )

#set ( GCC_ROOT "${CMAKE_SYSROOT}/opt/gcc-6.1" )'

set ( MAEMO TRUE CACHE BOOL "" )

set ( MAEMO_SDK "${MAEMO_SDK}" CACHE PATH "" )

set ( CMAKE_C_COMPILER "${TOOLCHAIN_PREFIX}-gcc-5" )
set ( CMAKE_CXX_COMPILER "${TOOLCHAIN_PREFIX}-g++-5" )

set ( CMAKE_C_COMPILER_TARGET ${TOOLCHAIN_PREFIX} )
set ( CMAKE_CXX_COMPILER_TARGET ${TOOLCHAIN_PREFIX} )

set ( CMAKE_RANLIB "${TOOLCHAIN_PREFIX}-ranlib" CACHE FILEPATH "" )
set ( CMAKE_AR "${TOOLCHAIN_PREFIX}-ar" CACHE FILEPATH "" )
set ( CMAKE_LINKER "${TOOLCHAIN_PREFIX}-ld" CACHE FILEPATH "" )

set ( CMAKE_CXX_FLAGS
    "${CMAKE_CXX_FLAGS} -mfpu=vfp -mfloat-abi=soft -mtune=cortex-a8"
    CACHE STRING "" )

add_definitions(
    -D__MAEMOFREMANTLE__
    -D__MAEMO__
#    -D__linux__
#    -D__unix__
    )

link_libraries (
#    c
#    rt
    -static-libstdc++
    -static-libgcc
#    atomic
    )

include_directories (
#    /usr/arm-linux-gnueabi/include/c++/5/arm-linux-gnueabi/
#    /usr/arm-linux-gnueabi/include/c++/5/
#    /usr/arm-linux-gnueabi/include
    )


text:
package org.apache.hadoop.hdfs.server.namenode;

import java.io.*;
import java.util.*;

import org.apache.hadoop.conf.Configuration;
import org.apache.hadoop.fs.FileStatus;
import org.apache.hadoop.fs.Path;
import org.apache.hadoop.fs.ContentSummary;
import org.apache.hadoop.fs.permission.*;
import org.apache.hadoop.metrics.MetricsRecord;
import org.apache.hadoop.metrics.MetricsUtil;
import org.apache.hadoop.metrics.MetricsContext;
import org.apache.hadoop.hdfs.protocol.FSConstants;
import org.apache.hadoop.hdfs.protocol.Block;
import org.apache.hadoop.hdfs.protocol.QuotaExceededException;
import org.apache.hadoop.hdfs.server.common.HdfsConstants.StartupOption;
import org.apache.hadoop.hdfs.server.namenode.BlocksMap.BlockInfo;

/*************************************************
 * FSDirectory stores the filesystem directory state. It handles writing/loading
 * values to disk, and logging changes as we go.
 *
 * It keeps the filename->blockset mapping always-current and logged to disk.
 *
 *************************************************/
class FSDirectory implements FSConstants, Closeable {

    final FSNamesystem namesystem;
    final INodeDirectoryWithQuota rootDir;
    FSImage fsImage;
    private boolean ready = false;
    // Metrics record
    private MetricsRecord directoryMetrics = null;

    /** Access an existing dfs name directory. */
    FSDirectory(FSNamesystem ns, Configuration conf) {
        this(new FSImage(), ns, conf);
        fsImage.setCheckpointDirectories(FSImage.getCheckpointDirs(conf, null),
                FSImage.getCheckpointEditsDirs(conf, null));
    }

    FSDirectory(FSImage fsImage, FSNamesystem ns, Configuration conf) {
        rootDir = new INodeDirectoryWithQuota(INodeDirectory.ROOT_NAME, ns.createFsOwnerPermissions(new FsPermission(
                (short) 0755)), Integer.MAX_VALUE, -1);
        this.fsImage = fsImage;
        namesystem = ns;
        initialize(conf);
    }

    private void initialize(Configuration conf) {
        MetricsContext metricsContext = MetricsUtil.getContext("dfs");
        directoryMetrics = MetricsUtil.createRecord(metricsContext, "FSDirectory");
        directoryMetrics.setTag("sessionId", conf.get("session.id"));
    }

    void loadFSImage(Collection<File> dataDirs, Collection<File> editsDirs, StartupOption startOpt) throws IOException {
        // format before starting up if requested
        if (startOpt == StartupOption.FORMAT) {
            fsImage.setStorageDirectories(dataDirs, editsDirs);
            fsImage.format();
            startOpt = StartupOption.REGULAR;
        }
        try {
            if (fsImage.recoverTransitionRead(dataDirs, editsDirs, startOpt)) {
                fsImage.saveFSImage();
            }
            FSEditLog editLog = fsImage.getEditLog();
            assert editLog != null : "editLog must be initialized";
            if (!editLog.isOpen())
                editLog.open();
            fsImage.setCheckpointDirectories(null, null);
        } catch (IOException e) {
            fsImage.close();
            throw e;
        }
        synchronized (this) {
            this.ready = true;
            this.notifyAll();
        }
    }

    private void incrDeletedFileCount(int count) {
        directoryMetrics.incrMetric("files_deleted", count);
        directoryMetrics.update();
    }

    /**
     * Shutdown the filestore
     */
    public void close() throws IOException {
        fsImage.close();
    }

    /**
     * Block until the object is ready to be used.
     */
    void waitForReady() {
        if (!ready) {
            synchronized (this) {
                while (!ready) {
                    try {
                        this.wait(5000);
                    } catch (InterruptedException ie) {
                    }
                }
            }
        }
    }

    /**
     * Add the given filename to the fs.
     */
    INodeFileUnderConstruction addFile(String path, PermissionStatus permissions, short replication,
            long preferredBlockSize, String clientName, String clientMachine, DatanodeDescriptor clientNode,
            long generationStamp) throws IOException {
        waitForReady();

        // Always do an implicit mkdirs for parent directory tree.
        long modTime = FSNamesystem.now();
        if (!mkdirs(new Path(path).getParent().toString(), permissions, true, modTime)) {
            return null;
        }
        INodeFileUnderConstruction newNode = new INodeFileUnderConstruction(permissions, replication,
                preferredBlockSize, modTime, clientName, clientMachine, clientNode);
        synchronized (rootDir) {
            newNode = addNode(path, newNode, -1, false);
        }
        if (newNode == null) {
            NameNode.stateChangeLog
                    .info("DIR* FSDirectory.addFile: " + "failed to add " + path + " to the file system");
            return null;
        }
        // add create file record to log, record new generation stamp
        fsImage.getEditLog().logOpenFile(path, newNode);

        NameNode.stateChangeLog.debug("DIR* FSDirectory.addFile: " + path + " is added to the file system");
        return newNode;
    }

    /**
   */
    INode unprotectedAddFile(String path, PermissionStatus permissions, Block[] blocks, short replication,
            long modificationTime, long atime, long preferredBlockSize) {
        INode newNode;
        long diskspace = -1; // unknown
        if (blocks == null)
            newNode = new INodeDirectory(permissions, modificationTime);
        else {
            newNode = new INodeFile(permissions, blocks.length, replication, modificationTime, atime,
                    preferredBlockSize);
            diskspace = ((INodeFile) newNode).diskspaceConsumed(blocks);
        }
        synchronized (rootDir) {
            try {
                newNode = addNode(path, newNode, diskspace, false);
                if (newNode != null && blocks != null) {
                    int nrBlocks = blocks.length;
                    // Add file->block mapping
                    INodeFile newF = (INodeFile) newNode;
                    for (int i = 0; i < nrBlocks; i++) {
                        newF.setBlock(i, namesystem.blocksMap.addINode(blocks[i], newF));
                    }
                }
            } catch (IOException e) {
                return null;
            }
            return newNode;
        }
    }

    INodeDirectory addToParent(String src, INodeDirectory parentINode, PermissionStatus permissions, Block[] blocks,
            short replication, long modificationTime, long atime, long nsQuota, long dsQuota, long preferredBlockSize) {
        // NOTE: This does not update space counts for parents
        // create new inode
        INode newNode;
        if (blocks == null) {
            if (nsQuota >= 0 || dsQuota >= 0) {
                newNode = new INodeDirectoryWithQuota(permissions, modificationTime, nsQuota, dsQuota);
            } else {
                newNode = new INodeDirectory(permissions, modificationTime);
            }
        } else
            newNode = new INodeFile(permissions, blocks.length, replication, modificationTime, atime,
                    preferredBlockSize);
        // add new node to the parent
        INodeDirectory newParent = null;
        synchronized (rootDir) {
            try {
                newParent = rootDir.addToParent(src, newNode, parentINode, false);
            } catch (FileNotFoundException e) {
                return null;
            }
            if (newParent == null)
                return null;
            if (blocks != null) {
                int nrBlocks = blocks.length;
                // Add file->block mapping
                INodeFile newF = (INodeFile) newNode;
                for (int i = 0; i < nrBlocks; i++) {
                    newF.setBlock(i, namesystem.blocksMap.addINode(blocks[i], newF));
                }
            }
        }
        return newParent;
    }

    /**
     * Add a block to the file. Returns a reference to the added block.
     */
    Block addBlock(String path, INode[] inodes, Block block) throws IOException {
        waitForReady();

        synchronized (rootDir) {
            INodeFile fileNode = (INodeFile) inodes[inodes.length - 1];

            // check quota limits and updated space consumed
            updateCount(inodes, inodes.length - 1, 0, fileNode.getPreferredBlockSize() * fileNode.getReplication());

            // associate the new list of blocks with this file
            namesystem.blocksMap.addINode(block, fileNode);
            BlockInfo blockInfo = namesystem.blocksMap.getStoredBlock(block);
            fileNode.addBlock(blockInfo);

            NameNode.stateChangeLog.debug("DIR* FSDirectory.addFile: " + path + " with " + block
                    + " block is added to the in-memory " + "file system");
        }
        return block;
    }

    /**
     * Persist the block list for the inode.
     */
    void persistBlocks(String path, INodeFileUnderConstruction file) throws IOException {
        waitForReady();

        synchronized (rootDir) {
            fsImage.getEditLog().logOpenFile(path, file);
            NameNode.stateChangeLog.debug("DIR* FSDirectory.persistBlocks: " + path + " with "
                    + file.getBlocks().length + " blocks is persisted to the file system");
        }
    }

    /**
     * Close file.
     */
    void closeFile(String path, INodeFile file) throws IOException {
        waitForReady();
        synchronized (rootDir) {
            // file is closed
            fsImage.getEditLog().logCloseFile(path, file);
            if (NameNode.stateChangeLog.isDebugEnabled()) {
                NameNode.stateChangeLog.debug("DIR* FSDirectory.closeFile: " + path + " with "
                        + file.getBlocks().length + " blocks is persisted to the file system");
            }
        }
    }

    /**
     * Remove a block to the file.
     */
    boolean removeBlock(String path, INodeFileUnderConstruction fileNode, Block block) throws IOException {
        waitForReady();

        synchronized (rootDir) {
            // modify file-> block and blocksMap
            fileNode.removeBlock(block);
            namesystem.blocksMap.removeINode(block);
            // If block is removed from blocksMap remove it from
            // corruptReplicasMap
            namesystem.corruptReplicas.removeFromCorruptReplicasMap(block);

            // write modified block locations to log
            fsImage.getEditLog().logOpenFile(path, fileNode);
            NameNode.stateChangeLog.debug("DIR* FSDirectory.addFile: " + path + " with " + block
                    + " block is added to the file system");
        }
        return true;
    }

    /**
     * @see #unprotectedRenameTo(String, String, long)
     */
    boolean renameTo(String src, String dst) throws QuotaExceededException {
        if (NameNode.stateChangeLog.isDebugEnabled()) {
            NameNode.stateChangeLog.debug("DIR* FSDirectory.renameTo: " + src + " to " + dst);
        }
        waitForReady();
        long now = FSNamesystem.now();
        if (!unprotectedRenameTo(src, dst, now))
            return false;
        fsImage.getEditLog().logRename(src, dst, now);
        return true;
    }

    /**
     * Change a path name
     *
     * @param src
     *            source path
     * @param dst
     *            destination path
     * @return true if rename succeeds; false otherwise
     * @throws QuotaExceededException
     *             if the operation violates any quota limit
     */
    boolean unprotectedRenameTo(String src, String dst, long timestamp) throws QuotaExceededException {
        synchronized (rootDir) {
            INode[] srcInodes = rootDir.getExistingPathINodes(src);

            // check the validation of the source
            if (srcInodes[srcInodes.length - 1] == null) {
                NameNode.stateChangeLog.warn("DIR* FSDirectory.unprotectedRenameTo: " + "failed to rename " + src
                        + " to " + dst + " because source does not exist");
                return false;
            } else if (srcInodes.length == 1) {
                NameNode.stateChangeLog.warn("DIR* FSDirectory.unprotectedRenameTo: " + "failed to rename " + src
                        + " to " + dst + " because source is the root");
                return false;
            }
            if (isDir(dst)) {
                dst += Path.SEPARATOR + new Path(src).getName();
            }

            // remove source
            INode srcChild = null;
            try {
                srcChild = removeChild(srcInodes, srcInodes.length - 1);
            } catch (IOException e) {
                // srcChild == null; go to next if statement
            }
            if (srcChild == null) {
                NameNode.stateChangeLog.warn("DIR* FSDirectory.unprotectedRenameTo: " + "failed to rename " + src
                        + " to " + dst + " because the source can not be removed");
                return false;
            }

            String srcChildName = srcChild.getLocalName();

            // check the validity of the destination
            INode dstChild = null;
            QuotaExceededException failureByQuota = null;

            byte[][] dstComponents = INode.getPathComponents(dst);
            INode[] dstInodes = new INode[dstComponents.length];
            rootDir.getExistingPathINodes(dstComponents, dstInodes);
            if (dstInodes[dstInodes.length - 1] != null) { // check if
                                                           // destination exists
                NameNode.stateChangeLog.warn("DIR* FSDirectory.unprotectedRenameTo: " + "failed to rename " + src
                        + " to " + dst + " because destination exists");
            } else if (dstInodes[dstInodes.length - 2] == null) { // check if
                                                                  // its parent
                                                                  // exists
                NameNode.stateChangeLog.warn("DIR* FSDirectory.unprotectedRenameTo: " + "failed to rename " + src
                        + " to " + dst + " because destination's parent does not exists");
            } else {
                // add to the destination
                srcChild.setLocalName(dstComponents[dstInodes.length - 1]);
                try {
                    // add it to the namespace
                    dstChild = addChild(dstInodes, dstInodes.length - 1, srcChild, false);
                } catch (QuotaExceededException qe) {
                    failureByQuota = qe;
                }
            }
            if (dstChild != null) {
                if (NameNode.stateChangeLog.isDebugEnabled()) {
                    NameNode.stateChangeLog.debug("DIR* FSDirectory.unprotectedRenameTo: " + src + " is renamed to "
                            + dst);
                }

                // update modification time of dst and the parent of src
                srcInodes[srcInodes.length - 2].setModificationTime(timestamp);
                dstInodes[dstInodes.length - 2].setModificationTime(timestamp);
                return true;
            } else {
                NameNode.stateChangeLog.warn("DIR* FSDirectory.unprotectedRenameTo: " + "failed to rename " + src
                        + " to " + dst);
                try {
                    // put it back
                    srcChild.setLocalName(srcChildName);
                    addChild(srcInodes, srcInodes.length - 1, srcChild, false);
                } catch (IOException ignored) {
                }
                if (failureByQuota != null) {
                    throw failureByQuota;
                } else {
                    return false;
                }
            }
        }
    }

    /**
     * Set file replication
     *
     * @param src
     *            file name
     * @param replication
     *            new replication
     * @param oldReplication
     *            old replication - output parameter
     * @return array of file blocks
     * @throws IOException
     */
    Block[] setReplication(String src, short replication, int[] oldReplication) throws IOException {
        waitForReady();
        Block[] fileBlocks = unprotectedSetReplication(src, replication, oldReplication);
        if (fileBlocks != null) // log replication change
            fsImage.getEditLog().logSetReplication(src, replication);
        return fileBlocks;
    }

    Block[] unprotectedSetReplication(String src, short replication, int[] oldReplication) throws IOException {
        if (oldReplication == null)
            oldReplication = new int[1];
        oldReplication[0] = -1;
        Block[] fileBlocks = null;
        synchronized (rootDir) {
            INode[] inodes = rootDir.getExistingPathINodes(src);
            INode inode = inodes[inodes.length - 1];
            if (inode == null)
                return null;
            if (inode.isDirectory())
                return null;
            INodeFile fileNode = (INodeFile) inode;
            oldReplication[0] = fileNode.getReplication();

            // check disk quota
            long dsDelta = (replication - oldReplication[0]) * (fileNode.diskspaceConsumed() / oldReplication[0]);
            updateCount(inodes, inodes.length - 1, 0, dsDelta);

            fileNode.setReplication(replication);
            fileBlocks = fileNode.getBlocks();
        }
        return fileBlocks;
    }

    /**
     * Get the blocksize of a file
     *
     * @param filename
     *            the filename
     * @return the number of bytes
     * @throws IOException
     *             if it is a directory or does not exist.
     */
    long getPreferredBlockSize(String filename) throws IOException {
        synchronized (rootDir) {
            INode fileNode = rootDir.getNode(filename);
            if (fileNode == null) {
                throw new IOException("Unknown file: " + filename);
            }
            if (fileNode.isDirectory()) {
                throw new IOException("Getting block size of a directory: " + filename);
            }
            return ((INodeFile) fileNode).getPreferredBlockSize();
        }
    }

    boolean exists(String src) {
        src = normalizePath(src);
        synchronized (rootDir) {
            INode inode = rootDir.getNode(src);
            if (inode == null) {
                return false;
            }
            return inode.isDirectory() ? true : ((INodeFile) inode).getBlocks() != null;
        }
    }

    void setPermission(String src, FsPermission permission) throws IOException {
        unprotectedSetPermission(src, permission);
        fsImage.getEditLog().logSetPermissions(src, permission);
    }

    void unprotectedSetPermission(String src, FsPermission permissions) throws FileNotFoundException {
        synchronized (rootDir) {
            INode inode = rootDir.getNode(src);
            if (inode == null)
                throw new FileNotFoundException("File does not exist: " + src);
            inode.setPermission(permissions);
        }
    }

    void setOwner(String src, String username, String groupname) throws IOException {
        unprotectedSetOwner(src, username, groupname);
        fsImage.getEditLog().logSetOwner(src, username, groupname);
    }

    void unprotectedSetOwner(String src, String username, String groupname) throws FileNotFoundException {
        synchronized (rootDir) {
            INode inode = rootDir.getNode(src);
            if (inode == null)
                throw new FileNotFoundException("File does not exist: " + src);
            if (username != null) {
                inode.setUser(username);
            }
            if (groupname != null) {
                inode.setGroup(groupname);
            }
        }
    }

    /**
     * Remove the file from management, return blocks
     */
    INode delete(String src) {
        if (NameNode.stateChangeLog.isDebugEnabled()) {
            NameNode.stateChangeLog.debug("DIR* FSDirectory.delete: " + src);
        }
        waitForReady();
        long now = FSNamesystem.now();
        INode deletedNode = unprotectedDelete(src, now);
        if (deletedNode != null) {
            fsImage.getEditLog().logDelete(src, now);
        }
        return deletedNode;
    }

    /** Return if a directory is empty or not **/
    boolean isDirEmpty(String src) {
        boolean dirNotEmpty = true;
        if (!isDir(src)) {
            return true;
        }
        synchronized (rootDir) {
            INode targetNode = rootDir.getNode(src);
            assert targetNode != null : "should be taken care in isDir() above";
            if (((INodeDirectory) targetNode).getChildren().size() != 0) {
                dirNotEmpty = false;
            }
        }
        return dirNotEmpty;
    }

    /**
     * Delete a path from the name space Update the count at each ancestor
     * directory with quota
     *
     * @param src
     *            a string representation of a path to an inode
     * @param modificationTime
     *            the time the inode is removed
     * @param deletedBlocks
     *            the place holder for the blocks to be removed
     * @return if the deletion succeeds
     */
    INode unprotectedDelete(String src, long modificationTime) {
        src = normalizePath(src);

        synchronized (rootDir) {
            INode[] inodes = rootDir.getExistingPathINodes(src);
            INode targetNode = inodes[inodes.length - 1];

            if (targetNode == null) { // non-existent src
                NameNode.stateChangeLog.debug("DIR* FSDirectory.unprotectedDelete: " + "failed to remove " + src
                        + " because it does not exist");
                return null;
            } else if (inodes.length == 1) { // src is the root
                NameNode.stateChangeLog.warn("DIR* FSDirectory.unprotectedDelete: " + "failed to remove " + src
                        + " because the root is not allowed to be deleted");
                return null;
            } else {
                try {
                    // Remove the node from the namespace
                    removeChild(inodes, inodes.length - 1);
                    // set the parent's modification time
                    inodes[inodes.length - 2].setModificationTime(modificationTime);
                    // GC all the blocks underneath the node.
                    ArrayList<Block> v = new ArrayList<Block>();
                    int filesRemoved = targetNode.collectSubtreeBlocksAndClear(v);
                    incrDeletedFileCount(filesRemoved);
                    namesystem.removePathAndBlocks(src, v);
                    if (NameNode.stateChangeLog.isDebugEnabled()) {
                        NameNode.stateChangeLog.debug("DIR* FSDirectory.unprotectedDelete: " + src + " is removed");
                    }
                    return targetNode;
                } catch (IOException e) {
                    NameNode.stateChangeLog.warn("DIR* FSDirectory.unprotectedDelete: " + "failed to remove " + src
                            + " because " + e.getMessage());
                    return null;
                }
            }
        }
    }

    /**
     * Replaces the specified inode with the specified one.
     */
    void replaceNode(String path, INodeFile oldnode, INodeFile newnode) throws IOException {
        replaceNode(path, oldnode, newnode, true);
    }

    /**
     * @see #replaceNode(String, INodeFile, INodeFile)
     */
    private void replaceNode(String path, INodeFile oldnode, INodeFile newnode, boolean updateDiskspace)
            throws IOException {
        synchronized (rootDir) {
            long dsOld = oldnode.diskspaceConsumed();

            //
            // Remove the node from the namespace
            //
            if (!oldnode.removeNode()) {
                NameNode.stateChangeLog.warn("DIR* FSDirectory.replaceNode: " + "failed to remove " + path);
                throw new IOException("FSDirectory.replaceNode: " + "failed to remove " + path);
            }

            /*
             * Currently oldnode and newnode are assumed to contain the same
             * blocks. Otherwise, blocks need to be removed from the blocksMap.
             */

            rootDir.addNode(path, newnode);

            // check if disk space needs to be updated.
            long dsNew = 0;
            if (updateDiskspace && (dsNew = newnode.diskspaceConsumed()) != dsOld) {
                try {
                    updateSpaceConsumed(path, 0, dsNew - dsOld);
                } catch (QuotaExceededException e) {
                    // undo
                    replaceNode(path, newnode, oldnode, false);
                    throw e;
                }
            }

            int index = 0;
            for (Block b : newnode.getBlocks()) {
                BlockInfo info = namesystem.blocksMap.addINode(b, newnode);
                newnode.setBlock(index, info); // inode refers to the block in
                                               // BlocksMap
                index++;
            }
        }
    }

    /**
     * Get a listing of files given path 'src'
     *
     * This function is admittedly very inefficient right now. We'll make it
     * better later.
     */
    FileStatus[] getListing(String src) {
        String srcs = normalizePath(src);

        synchronized (rootDir) {
            INode targetNode = rootDir.getNode(srcs);
            if (targetNode == null)
                return null;
            if (!targetNode.isDirectory()) {
                return new FileStatus[] { createFileStatus(srcs, targetNode) };
            }
            List<INode> contents = ((INodeDirectory) targetNode).getChildren();
            FileStatus listing[] = new FileStatus[contents.size()];
            if (!srcs.endsWith(Path.SEPARATOR))
                srcs += Path.SEPARATOR;
            int i = 0;
            for (INode cur : contents) {
                listing[i] = createFileStatus(srcs + cur.getLocalName(), cur);
                i++;
            }
            return listing;
        }
    }

    /**
     * Get the file info for a specific file.
     *
     * @param src
     *            The string representation of the path to the file
     * @return object containing information regarding the file or null if file
     *         not found
     */
    FileStatus getFileInfo(String src) {
        String srcs = normalizePath(src);
        synchronized (rootDir) {
            INode targetNode = rootDir.getNode(srcs);
            if (targetNode == null) {
                return null;
            } else {
                return createFileStatus(srcs, targetNode);
            }
        }
    }

    /**
     * Get the blocks associated with the file.
     */
    Block[] getFileBlocks(String src) {
        waitForReady();
        synchronized (rootDir) {
            INode targetNode = rootDir.getNode(src);
            if (targetNode == null)
                return null;
            if (targetNode.isDirectory())
                return null;
            return ((INodeFile) targetNode).getBlocks();
        }
    }

    /**
     * Get {@link INode} associated with the file.
     */
    INodeFile getFileINode(String src) {
        synchronized (rootDir) {
            INode inode = rootDir.getNode(src);
            if (inode == null || inode.isDirectory())
                return null;
            return (INodeFile) inode;
        }
    }

    /**
     * Retrieve the existing INodes along the given path.
     *
     * @param path
     *            the path to explore
     * @return INodes array containing the existing INodes in the order they
     *         appear when following the path from the root INode to the deepest
     *         INodes. The array size will be the number of expected components
     *         in the path, and non existing components will be filled with null
     *
     * @see INodeDirectory#getExistingPathINodes(byte[][], INode[])
     */
    INode[] getExistingPathINodes(String path) {
        synchronized (rootDir) {
            return rootDir.getExistingPathINodes(path);
        }
    }

    /**
     * Check whether the filepath could be created
     */
    boolean isValidToCreate(String src) {
        String srcs = normalizePath(src);
        synchronized (rootDir) {
            if (srcs.startsWith("/") && !srcs.endsWith("/") && rootDir.getNode(srcs) == null) {
                return true;
            } else {
                return false;
            }
        }
    }

    /**
     * Check whether the path specifies a directory
     */
    boolean isDir(String src) {
        synchronized (rootDir) {
            INode node = rootDir.getNode(normalizePath(src));
            return node != null && node.isDirectory();
        }
    }

    /**
     * Updates namespace and diskspace consumed for all directories until the
     * parent directory of file represented by path.
     *
     * @param path
     *            path for the file.
     * @param nsDelta
     *            the delta change of namespace
     * @param dsDelta
     *            the delta change of diskspace
     * @throws QuotaExceededException
     *             if the new count violates any quota limit
     * @throws FileNotFound
     *             if path does not exist.
     */
    void updateSpaceConsumed(String path, long nsDelta, long dsDelta) throws QuotaExceededException,
            FileNotFoundException {
        synchronized (rootDir) {
            INode[] inodes = rootDir.getExistingPathINodes(path);
            int len = inodes.length;
            if (inodes[len - 1] == null) {
                throw new FileNotFoundException(path + " does not exist under rootDir.");
            }
            updateCount(inodes, len - 1, nsDelta, dsDelta);
        }
    }

    /**
     * update count of each inode with quota
     *
     * @param inodes
     *            an array of inodes on a path
     * @param numOfINodes
     *            the number of inodes to update starting from index 0
     * @param nsDelta
     *            the delta change of namespace
     * @param dsDelta
     *            the delta change of diskspace
     * @throws QuotaExceededException
     *             if the new count violates any quota limit
     */
    private void updateCount(INode[] inodes, int numOfINodes, long nsDelta, long dsDelta) throws QuotaExceededException {
        if (!ready) {
            // still intializing. do not check or update quotas.
            return;
        }
        if (numOfINodes > inodes.length) {
            numOfINodes = inodes.length;
        }
        // check existing components in the path
        int i = 0;
        try {
            for (; i < numOfINodes; i++) {
                if (inodes[i].isQuotaSet()) { // a directory with quota
                    INodeDirectoryWithQuota node = (INodeDirectoryWithQuota) inodes[i];
                    node.updateNumItemsInTree(nsDelta, dsDelta);
                }
            }
        } catch (QuotaExceededException e) {
            e.setPathName(getFullPathName(inodes, i));
            // undo updates
            for (; i-- > 0;) {
                try {
                    if (inodes[i].isQuotaSet()) { // a directory with quota
                        INodeDirectoryWithQuota node = (INodeDirectoryWithQuota) inodes[i];
                        node.updateNumItemsInTree(-nsDelta, -dsDelta);
                    }
                } catch (IOException ingored) {
                }
            }
            throw e;
        }
    }

    /** Return the name of the path represented by inodes at [0, pos] */
    private static String getFullPathName(INode[] inodes, int pos) {
        StringBuilder fullPathName = new StringBuilder();
        for (int i = 1; i <= pos; i++) {
            fullPathName.append(Path.SEPARATOR_CHAR).append(inodes[i].getLocalName());
        }
        return fullPathName.toString();
    }

    /**
     * Create a directory If ancestor directories do not exist, automatically
     * create them.
     *
     * @param src
     *            string representation of the path to the directory
     * @param permissions
     *            the permission of the directory
     * @param inheritPermission
     *            if the permission of the directory should inherit from its
     *            parent or not. The automatically created ones always inherit
     *            its permission from its parent
     * @param now
     *            creation time
     * @return true if the operation succeeds false otherwise
     * @throws FileNotFoundException
     *             if an ancestor or itself is a file
     * @throws QuotaExceededException
     *             if directory creation violates any quota limit
     */
    boolean mkdirs(String src, PermissionStatus permissions, boolean inheritPermission, long now)
            throws FileNotFoundException, QuotaExceededException {
        src = normalizePath(src);
        String[] names = INode.getPathNames(src);
        byte[][] components = INode.getPathComponents(names);
        INode[] inodes = new INode[components.length];

        synchronized (rootDir) {
            rootDir.getExistingPathINodes(components, inodes);

            // find the index of the first null in inodes[]
            StringBuilder pathbuilder = new StringBuilder();
            int i = 1;
            for (; i < inodes.length && inodes[i] != null; i++) {
                pathbuilder.append(Path.SEPARATOR + names[i]);
                if (!inodes[i].isDirectory()) {
                    throw new FileNotFoundException("Parent path is not a directory: " + pathbuilder);
                }
            }

            // create directories beginning from the first null index
            for (; i < inodes.length; i++) {
                pathbuilder.append(Path.SEPARATOR + names[i]);
                String cur = pathbuilder.toString();
                unprotectedMkdir(inodes, i, components[i], permissions,
                        inheritPermission || i != components.length - 1, now);
                if (inodes[i] == null) {
                    return false;
                }
                // Directory creation also count towards FilesCreated
                // to match count of files_deleted metric.
                if (namesystem != null)
                    NameNode.getNameNodeMetrics().numFilesCreated.inc();
                fsImage.getEditLog().logMkDir(cur, inodes[i]);
                NameNode.stateChangeLog.debug("DIR* FSDirectory.mkdirs: created directory " + cur);
            }
        }
        return true;
    }

    /**
   */
    INode unprotectedMkdir(String src, PermissionStatus permissions, long timestamp) throws QuotaExceededException {
        byte[][] components = INode.getPathComponents(src);
        INode[] inodes = new INode[components.length];
        synchronized (rootDir) {
            rootDir.getExistingPathINodes(components, inodes);
            unprotectedMkdir(inodes, inodes.length - 1, components[inodes.length - 1], permissions, false, timestamp);
            return inodes[inodes.length - 1];
        }
    }

    /**
     * create a directory at index pos. The parent path to the directory is at
     * [0, pos-1]. All ancestors exist. Newly created one stored at index pos.
     */
    private void unprotectedMkdir(INode[] inodes, int pos, byte[] name, PermissionStatus permission,
            boolean inheritPermission, long timestamp) throws QuotaExceededException {
        inodes[pos] = addChild(inodes, pos, new INodeDirectory(name, permission, timestamp), inheritPermission);
    }

    /**
     * Add a node child to the namespace. The full path name of the node is src.
     * childDiskspace should be -1, if unknown. QuotaExceededException is thrown
     * if it violates quota limit
     */
    private <T extends INode> T addNode(String src, T child, long childDiskspace, boolean inheritPermission)
            throws QuotaExceededException {
        byte[][] components = INode.getPathComponents(src);
        child.setLocalName(components[components.length - 1]);
        INode[] inodes = new INode[components.length];
        synchronized (rootDir) {
            rootDir.getExistingPathINodes(components, inodes);
            return addChild(inodes, inodes.length - 1, child, childDiskspace, inheritPermission);
        }
    }

    /**
     * Add a node child to the inodes at index pos. Its ancestors are stored at
     * [0, pos-1]. QuotaExceededException is thrown if it violates quota limit
     */
    private <T extends INode> T addChild(INode[] pathComponents, int pos, T child, boolean inheritPermission)
            throws QuotaExceededException {
        return addChild(pathComponents, pos, child, -1, inheritPermission);
    }

    /**
     * Add a node child to the inodes at index pos. Its ancestors are stored at
     * [0, pos-1]. QuotaExceededException is thrown if it violates quota limit
     */
    private <T extends INode> T addChild(INode[] pathComponents, int pos, T child, long childDiskspace,
            boolean inheritPermission) throws QuotaExceededException {
        INode.DirCounts counts = new INode.DirCounts();
        child.spaceConsumedInTree(counts);
        if (childDiskspace < 0) {
            childDiskspace = counts.getDsCount();
        }
        updateCount(pathComponents, pos, counts.getNsCount(), childDiskspace);
        T addedNode = ((INodeDirectory) pathComponents[pos - 1]).addChild(child, inheritPermission);
        if (addedNode == null) {
            updateCount(pathComponents, pos, -counts.getNsCount(), -childDiskspace);
        }
        return addedNode;
    }

    /**
     * Remove an inode at index pos from the namespace. Its ancestors are stored
     * at [0, pos-1]. Count of each ancestor with quota is also updated. Return
     * the removed node; null if the removal fails.
     */
    private INode removeChild(INode[] pathComponents, int pos) throws QuotaExceededException {
        INode removedNode = ((INodeDirectory) pathComponents[pos - 1]).removeChild(pathComponents[pos]);
        if (removedNode != null) {
            INode.DirCounts counts = new INode.DirCounts();
            removedNode.spaceConsumedInTree(counts);
            updateCount(pathComponents, pos, -counts.getNsCount(), -counts.getDsCount());
        }
        return removedNode;
    }

    /**
   */
    String normalizePath(String src) {
        if (src.length() > 1 && src.endsWith("/")) {
            src = src.substring(0, src.length() - 1);
        }
        return src;
    }

    ContentSummary getContentSummary(String src) throws IOException {
        String srcs = normalizePath(src);
        synchronized (rootDir) {
            INode targetNode = rootDir.getNode(srcs);
            if (targetNode == null) {
                throw new FileNotFoundException("File does not exist: " + srcs);
            } else {
                return targetNode.computeContentSummary();
            }
        }
    }

    /**
     * Update the count of each directory with quota in the namespace A
     * directory's count is defined as the total number inodes in the tree
     * rooted at the directory.
     *
     * This is an update of existing state of the filesystem and does not throw
     * QuotaExceededException.
     */
    void updateCountForINodeWithQuota() {
        updateCountForINodeWithQuota(rootDir, new INode.DirCounts(), new ArrayList<INode>(50));
    }

    /**
     * Update the count of the directory if it has a quota and return the count
     *
     * This does not throw a QuotaExceededException. This is just an update of
     * of existing state and throwing QuotaExceededException does not help with
     * fixing the state, if there is a problem.
     *
     * @param dir
     *            the root of the tree that represents the directory
     * @param counters
     *            counters for name space and disk space
     * @param nodesInPath
     *            INodes for the each of components in the path.
     * @return the size of the tree
     */
    private static void updateCountForINodeWithQuota(INodeDirectory dir, INode.DirCounts counts,
            ArrayList<INode> nodesInPath) {
        long parentNamespace = counts.nsCount;
        long parentDiskspace = counts.dsCount;

        counts.nsCount = 1L;// for self. should not call
                            // node.spaceConsumedInTree()
        counts.dsCount = 0L;

        /*
         * We don't need nodesInPath if we could use 'parent' field in INode.
         * using 'parent' is not currently recommended.
         */
        nodesInPath.add(dir);

        for (INode child : dir.getChildren()) {
            if (child.isDirectory()) {
                updateCountForINodeWithQuota((INodeDirectory) child, counts, nodesInPath);
            } else { // reduce recursive calls
                counts.nsCount += 1;
                counts.dsCount += ((INodeFile) child).diskspaceConsumed();
            }
        }

        if (dir.isQuotaSet()) {
            ((INodeDirectoryWithQuota) dir).setSpaceConsumed(counts.nsCount, counts.dsCount);

            // check if quota is violated for some reason.
            if ((dir.getNsQuota() >= 0 && counts.nsCount > dir.getNsQuota())
                    || (dir.getDsQuota() >= 0 && counts.dsCount > dir.getDsQuota())) {

                // can only happen because of a software bug. the bug should be
                // fixed.
                StringBuilder path = new StringBuilder(512);
                for (INode n : nodesInPath) {
                    path.append('/');
                    path.append(n.getLocalName());
                }

                NameNode.LOG.warn("Unexpected quota violation in image for " + path + " (Namespace quota : "
                        + dir.getNsQuota() + " consumed : " + counts.nsCount + ")" + " (Diskspace quota : "
                        + dir.getDsQuota() + " consumed : " + counts.dsCount + ").");
            }
        }

        // pop
        nodesInPath.remove(nodesInPath.size() - 1);

        counts.nsCount += parentNamespace;
        counts.dsCount += parentDiskspace;
    }

    /**
     * See {@link ClientProtocol#setQuota(String, long, long)} for the contract.
     * Sets quota for for a directory.
     *
     * @returns INodeDirectory if any of the quotas have changed. null other
     *          wise.
     * @throws FileNotFoundException
     *             if the path does not exist or is a file
     * @throws QuotaExceededException
     *             if the directory tree size is greater than the given quota
     */
    INodeDirectory unprotectedSetQuota(String src, long nsQuota, long dsQuota) throws FileNotFoundException,
            QuotaExceededException {
        // sanity check
        if ((nsQuota < 0 && nsQuota != FSConstants.QUOTA_DONT_SET && nsQuota < FSConstants.QUOTA_RESET)
                || (dsQuota < 0 && dsQuota != FSConstants.QUOTA_DONT_SET && dsQuota < FSConstants.QUOTA_RESET)) {
            throw new IllegalArgumentException("Illegal value for nsQuota or " + "dsQuota : " + nsQuota + " and "
                    + dsQuota);
        }

        String srcs = normalizePath(src);
        INode[] inodes = rootDir.getExistingPathINodes(src);
        INode targetNode = inodes[inodes.length - 1];
        if (targetNode == null) {
            throw new FileNotFoundException("Directory does not exist: " + srcs);
        } else if (!targetNode.isDirectory()) {
            throw new FileNotFoundException("Cannot set quota on a file: " + srcs);
        } else { // a directory inode
            INodeDirectory dirNode = (INodeDirectory) targetNode;
            long oldNsQuota = dirNode.getNsQuota();
            long oldDsQuota = dirNode.getDsQuota();
            if (nsQuota == FSConstants.QUOTA_DONT_SET) {
                nsQuota = oldNsQuota;
            }
            if (dsQuota == FSConstants.QUOTA_DONT_SET) {
                dsQuota = oldDsQuota;
            }

            if (dirNode instanceof INodeDirectoryWithQuota) {
                // a directory with quota; so set the quota to the new value
                ((INodeDirectoryWithQuota) dirNode).setQuota(nsQuota, dsQuota);
            } else {
                // a non-quota directory; so replace it with a directory with
                // quota
                INodeDirectoryWithQuota newNode = new INodeDirectoryWithQuota(nsQuota, dsQuota, dirNode);
                // non-root directory node; parent != null
                INodeDirectory parent = (INodeDirectory) inodes[inodes.length - 2];
                dirNode = newNode;
                parent.replaceChild(newNode);
            }
            return (oldNsQuota != nsQuota || oldDsQuota != dsQuota) ? dirNode : null;
        }
    }

    /**
     * See {@link ClientProtocol#setQuota(String, long, long)} for the contract.
     *
     * @see #unprotectedSetQuota(String, long, long)
     */
    void setQuota(String src, long nsQuota, long dsQuota) throws FileNotFoundException, QuotaExceededException {
        synchronized (rootDir) {
            INodeDirectory dir = unprotectedSetQuota(src, nsQuota, dsQuota);
            if (dir != null) {
                fsImage.getEditLog().logSetQuota(src, dir.getNsQuota(), dir.getDsQuota());
            }
        }
    }

    long totalInodes() {
        synchronized (rootDir) {
            return rootDir.numItemsInTree();
        }
    }

    /**
     * Sets the access time on the file. Logs it in the transaction log
     */
    void setTimes(String src, INodeFile inode, long mtime, long atime, boolean force) throws IOException {
        if (unprotectedSetTimes(src, inode, mtime, atime, force)) {
            fsImage.getEditLog().logTimes(src, mtime, atime);
        }
    }

    boolean unprotectedSetTimes(String src, long mtime, long atime, boolean force) throws IOException {
        INodeFile inode = getFileINode(src);
        return unprotectedSetTimes(src, inode, mtime, atime, force);
    }

    private boolean unprotectedSetTimes(String src, INodeFile inode, long mtime, long atime, boolean force)
            throws IOException {
        boolean status = false;
        if (mtime != -1) {
            inode.setModificationTimeForce(mtime);
            status = true;
        }
        if (atime != -1) {
            long inodeTime = inode.getAccessTime();

            // if the last access time update was within the last precision
            // interval, then
            // no need to store access time
            if (atime <= inodeTime + namesystem.getAccessTimePrecision() && !force) {
                status = false;
            } else {
                inode.setAccessTime(atime);
                status = true;
            }
        }
        return status;
    }

    /**
     * Create FileStatus by file INode
     */
    private static FileStatus createFileStatus(String path, INode node) {
        // length is zero for directories
        return new FileStatus(node.isDirectory() ? 0 : node.computeContentSummary().getLength(), node.isDirectory(),
                node.isDirectory() ? 0 : ((INodeFile) node).getReplication(), node.isDirectory() ? 0
                        : ((INodeFile) node).getPreferredBlockSize(), node.getModificationTime(), node.getAccessTime(),
                node.getFsPermission(), node.getUserName(), node.getGroupName(), new Path(path));
    }
}


text:
pub use self::work::{WorkerEvent, ClientEvent, WorkIdentifier, Work, WorkID};
pub use self::work_event::{WorkEventLoop, WorkEventReceiver, WorkEvent};
pub use self::input_storage::InputStorage;

pub mod work;
mod work_event;
mod input_storage;


text:
<!DOCTYPE animal [
<!ELEMENT animal ANY>
<?῍ an illegal char #x1fcd
 in PITarget ?>
]>
<animal/>


text:
package main

import (
	"encoding/json"
	"fmt"
	"io/ioutil"
	"net/http"
	"os"
	"time"
)

const (
	API_URL        string = "http://pubapi.cryptsy.com/api.php?method=singlemarketdata&marketid="
	DOGE_ID        int    = 132
	RETRY_ATTEMPTS int    = 5
	RETRY_DELAY           = 5
	LOG_FILE_NAME  string = ".wst_log"
)

var (
	currentRetryCount int = 0
	logFile           *os.File
)

// Represents the overall ApiResponse (made up of a market which has many trades)
type ApiResponse struct {
	Success int              `json:"success"`
	Return  MarketCollection `json:"return"`
}

// A wrapper around a map so that I don't need to convert from []interface{} or
// map[string]interface{}
type MarketCollection struct {
	Markets map[string]Market `json:"markets"`
}

// Represents a market on the cryptsy exchange
//
// A lot of these values should be float64s but annoyingly everything comes back as a string
// so conversions are gonna be needed to do anything worthwhile later.
type Market struct {
	MarketId       string  `json:"marketid"`
	Label          string  `json:"label"`
	LastTradePrice string  `json:"lasttradeprice"`
	Volume         string  `json:"volume"`
	LastTradeTime  string  `json:"lasttradetime"`
	PrimaryName    string  `json:"primaryname"`
	PrimaryCode    string  `json:"primarycode"`
	SecondaryName  string  `json:"secondaryname"`
	SecondaryCode  string  `json:"secondarycode"`
	RecentTrades   []Trade `json:"recenttrades"`
	SellOrders     []Order `json:"sellorders"`
	BuyOrders      []Order `json:"buyorders"`
}

// Represents a single trade of DOGE
type Trade struct {
	Id       string
	Time     string
	Price    string
	Quantity string
	Total    string
}

// Represents a single buy or sell order
type Order struct {
	Price    string
	Quantity string
	Total    string
}

func main() {
	openLogFile()
	defer closeLogFile()

	data := makeApiRequest()

	var apiresp ApiResponse

	err := json.Unmarshal(data, &apiresp)
	if err != nil {
		writeLogLine(fmt.Sprintf("Error occurred while parsing api response data: %v\n", err.Error()))
	}

	label := apiresp.Return.Markets["DOGE"].Label
	val := apiresp.Return.Markets["DOGE"].LastTradePrice

	writeLogLine(fmt.Sprintf("SUCCESS: %v : %v\n", label, val))
	fmt.Printf("%v : %v\n", label, val)
}

// Perform the actual HTTP request to the API and return the response
// as a string.  This will do some retrying if it gets a bad gateway error.
func makeApiRequest() []byte {
	reqUrl := fmt.Sprintf("%v%v", API_URL, DOGE_ID)

	resp, err := http.Get(reqUrl)
	if err != nil {
		writeLogLine(fmt.Sprintf("ERROR OCCURRED DURING HTTP REQUEST: %v\n", err.Error()))
	}

	status := resp.StatusCode
	if status != 200 {
		if status == 502 {
			currentRetryCount++
			if currentRetryCount > RETRY_ATTEMPTS {
				return nil
			} else {
				time.Sleep(time.Second * RETRY_DELAY)
				return makeApiRequest()
			}
		} else {
			writeLogLine(fmt.Sprintf("ERROR STATUS RETURNED: %v\n", status))
			return nil
		}
	}

	body := resp.Body
	bodyText, err := ioutil.ReadAll(body)
	body.Close()

	return bodyText
}

func getLogFilePath() string {
	path := os.Getenv("HOME")
	pathStr := ""
	if path != "" {
		pathStr = path + "/" + LOG_FILE_NAME
	} else {
		pathStr = LOG_FILE_NAME
	}

	return pathStr

}

// Sets the logFile file pointer to the log file
func openLogFile() {

	filePtr, err := os.OpenFile(getLogFilePath(), os.O_CREATE|os.O_WRONLY|os.O_APPEND, 0666)
	if err != nil {
		fmt.Println("Couldn't open logfile for writing:", err.Error())
		return
	} else {
		logFile = filePtr
	}
}

// Closes the logFile if it is open
func closeLogFile() {
	if logFile != nil {
		logFile.Close()
	}
}

func writeLogLine(text string) {
	if logFile != nil {
		// Add the timestamp to the string
		currentTime := time.Now()
		writeOut := fmt.Sprintf("%v : %v", currentTime, text)
		bytes := []byte(writeOut)
		_, err := logFile.Write(bytes)
		if err != nil {
			fmt.Println("ERROR WRITING TO LOGFILE:", err.Error())
		}
	}
}


text:
class ActionViewController < UIViewController
  # Disable 'IB' if you want to setup the UI in code
  extend IB
  outlet :imageView, UIImageView

  def initWithNibName(nibNameOrNil, bundle:nibBundleOrNil)
    super
    self
  end

  def viewDidLoad
    super

    # Get the item[s] we're handling from the extension context.

    # For example, look for an image and place it into an image view.
    # Replace this with something appropriate for the type[s] your extension supports.
    imageFound = false
    self.extensionContext.inputItems.each do |item|
      item.attachments.each do |itemProvider|
        if itemProvider.hasItemConformingToTypeIdentifier(KUTTypeImage)
          # This is an image. We'll load it, then place it in our image view.
          imageView = WeakRef.new(self.imageView)
          itemProvider.loadItemForTypeIdentifier(KUTTypeImage, options:nil, completionHandler: proc { |url, error|
            if url
              image = UIImage.alloc.initWithData(NSData.dataWithContentsOfURL(url))
              NSOperationQueue.mainQueue.addOperationWithBlock(proc {
                imageView.setImage(image)
              })
            end
          })

          imageFound = true
          break
        end
      end

      break if imageFound
    end
  end

  def didReceiveMemoryWarning
    super
    # Dispose of any resources that can be recreated.
  end

  def done
    # Return any edited content to the host app.
    # This template doesn't do anything, so we just echo the passed in items.
    self.extensionContext.completeRequestReturningItems(self.extensionContext.inputItems, completionHandler:nil)
  end

end


text:
<meta http-equiv="content-type" content="text/html; charset=utf-8" />
<meta name="renderer" content="webkit|ie-comp|ie-stand">
<meta name="viewport" content="width=device-width, initial-scale=1.0, maximum-scale=1.0, user-scalable=0" />
<meta name="theme-color" content="#474d57">
<!--[if lte IE 9]><meta http-equiv="refresh" content="0;url=/ie.html"><![endif]-->
<title>{{ page.title }} | {{ site.title }}</title>
<meta name="author" content="{{ site.author }}">
{% if page.keywords %}
	<meta name="keywords" content="{{ page.keywords }}">
{% endif %}
{% if page.description  %}
	<meta name="description " content="{{ page.description  }}">
{% endif %}
<link rel="shortcut icon" href="{{ site.favicon }}" />
<link rel="stylesheet" type="text/css" href="/assets/css/style.css">
<link href="/pages/rss.xml" rel="alternate" title="{{site.title}}" type="application/atom+xml">


text:
import {todayAtUtc, todayAtUtcString} from "../support/time-helpers";
import {manifestForDateTime, passengerList} from "../support/manifest-helpers";

describe("CEDAT arrival exports", () => {

    const scheduledDateTime = todayAtUtc(0, 55);

    const cedatExportHeaders = "IATA,ICAO,Origin,Gate/Stand,Status," +
        "Scheduled Date,Scheduled Time,Est Arrival,Act Arrival,Est Chox,Act Chox,Est PCP," +
        "Total Pax,PCP Pax," +
        "API e-Gates,API EEA,API Non-EEA,API Fast Track," +
        "Historical e-Gates,Historical EEA,Historical Non-EEA,Historical Fast Track," +
        "Terminal Average e-Gates,Terminal Average EEA,Terminal Average Non-EEA,Terminal Average Fast Track," +
        "API Actual - B5JSSK to Desk,API Actual - B5JSSK to eGates" +
        ",API Actual - EEA (Machine Readable),API Actual - EEA (Non Machine Readable)," +
        "API Actual - Fast Track (Non Visa),API Actual - Fast Track (Visa),API Actual " +
        "- Non EEA (Non Visa),API Actual - Non EEA (Visa),API Actual - Transfer,API Actual - eGates";

    const schDateLocal = scheduledDateTime.tz("Europe/London").format("YYYY-MM-DD");
    const schTimeLocal = scheduledDateTime.tz("Europe/London").format("HH:mm");

    const estTime = todayAtUtc(1, 5);
    const actTime = todayAtUtc(1, 7);
    const estChoxTime = todayAtUtc(1, 11);
    const actChoxTime = todayAtUtc(1, 12);

    const totalPax = "51";
    const apiEgatePax = "25";
    const eeaDesk = "9";
    const nonEEADesk = "17";

    const estTimeLocal = estTime.tz("Europe/London").format("HH:mm");
    const actTimeLocal = actTime.tz("Europe/London").format("HH:mm");
    const estChoxTimeLocal = estChoxTime.tz("Europe/London").format("HH:mm");
    const actChoxTimeLocal = actChoxTime.tz("Europe/London").format("HH:mm");
    const pcpTimeLocal = actChoxTime.add(13, "minutes").tz("Europe/London").format("HH:mm");

    const csvRow = (apiEgatePax: string, eGateApiActual: string, terminalAverageEGates: string = "13") => "TS0123,TS0123,AMS,46/44R,On Chocks," +
        schDateLocal + "," + schTimeLocal + "," + estTimeLocal + "," + actTimeLocal + "," + estChoxTimeLocal + "," + actChoxTimeLocal + "," + pcpTimeLocal + "," +
        totalPax + "," + totalPax + "," +
        apiEgatePax + "," + eeaDesk + "," + nonEEADesk + ",," +
        ",,,," +
        terminalAverageEGates + ",37,1,,4.0,6.0,5.0,0.0,0.0,0.0,7.0,10.0,0.0," + eGateApiActual + "\n";

    const manifest = (passengerList): object => manifestForDateTime(scheduledDateTime, passengerList)

    it('Exports CEDAT data in the format they expect', () => {
        const cedatCsv = cedatExportHeaders + "\n" +
            csvRow("25", "19.0", "13");
        cy
            .addFlight(
                {
                    "SchDT": todayAtUtcString(0, 55),
                    "EstDT": todayAtUtcString(1, 5),
                    "EstChoxDT": todayAtUtcString(1, 11),
                    "ActDT": todayAtUtcString(1, 7),
                    "ActChoxDT": todayAtUtcString(1, 12)
                }
            )
            .asABorderForceOfficer()
            .waitForFlightToAppear("TS0123")
            .addManifest(manifest(passengerList(24, 10, 7, 10)))
            .get('.pax-api')
            .asABorderForceOfficerWithRoles(["cedat-staff"])
            .get('#export-day-arrivals')
            .then((el) => {
                const href = el.prop('href')
                cy.request({
                    method: 'GET',
                    url: href,
                }).then((resp) => {
                    expect(resp.body).to.equal(cedatCsv, "CSV export for CEDAT doesn't match their expectations")
                })
            })
    });

    it('Uses the port feed passenger numbers not the API passenger numbers in the export', () => {
        const cedatCsv = cedatExportHeaders + "\n" +
            csvRow("24", "18.0", "12");
        cy
            .addFlight(
                {
                    "SchDT": todayAtUtcString(0, 55),
                    "EstDT": todayAtUtcString(1, 5),
                    "EstChoxDT": todayAtUtcString(1, 11),
                    "ActDT": todayAtUtcString(1, 7),
                    "ActChoxDT": todayAtUtcString(1, 12)
                }
            )
            .asABorderForceOfficer()
            .waitForFlightToAppear("TS0123")
            .addManifest(manifest(passengerList(23, 10, 7, 10)))
            .get('.pax-api')
            .asABorderForceOfficerWithRoles(["cedat-staff"])
            .get('#export-day-arrivals')
            .then((el) => {
                const href = el.prop('href')
                cy.request({
                    method: 'GET',
                    url: href,
                }).then((resp) => {
                    expect(resp.body).to.equal(cedatCsv, "CSV export for CEDAT doesn't match their expectations")
                })
            })
    });

})


text:
I am intended to be used in place of two arg sort blocks.

Usage

In the following example, an ascending SortFunction is created based on the result of the #first message send to each object.
#(#(1 2) #(2 3) #(0 0)) sorted: #first ascending.

To sort by the #last element, but descending, the following would be used:
#(#(1 2) #(2 3) #(0 0)) sorted: #last descending.

One can use blocks as well. The following sorts in descending order, the sub elements based on the sum of their values.
| sumBlock |
sumBlock := [:sequence | sequence inject: 0 into: [:sum :each | sum + each]].
#(#(1 2) #(2 3) #(0 0)) sorted: sumBlock descending.

One can even use 2 arg blocks, for those cases where the function isn't expressible with objects that respond to < and =. The only catch, is that such a function has to return not true and false, but instead a collation order, values of -1 (for before), 0 (the same) or 1 (to follow). For example:

| oddBlock |
oddBlock :=
		[:a :b |
		a odd = b odd ifTrue: [0] ifFalse: [a odd ifTrue: [-1] ifFalse: [1]]].
#(1 5 1 3 2 7 9 4 6) asSortedCollection: oddBlock descending

Using #undefinedFirst and #undefinedLast it is possible to deal with nil values, moving them first or last. For Example:

#(a nil z b) sorted: #value ascending undefinedFirst.
#(a nil z b) sorted: #value ascending undefinedLast.

Instance Variables
	collator	<BlockClosure>	This is the collation function that must return a -1, 0, or 1. It is usually composed by an initialization method such as sendMessage: or monadicBlock:, but may be set directly.
	direction	<SmallInteger>	1 for ascending, -1 for descending


text:
\documentclass{beamer}

\usepackage[utf8]{inputenc}
\usepackage[T1]{fontenc}
\usepackage{setspace}
\usepackage{color}
\usepackage{listings}
\usepackage{zi4}
\usepackage{tikz}
\usepackage{bchart}
\usepackage{adjustbox}

\usetikzlibrary{positioning, arrows}

\usetheme{Frankfurt}

\lstset{basicstyle=\ttfamily,breaklines=true}

\definecolor{javared}{rgb}{0.6,0,0} % for strings
\definecolor{javagreen}{rgb}{0.25,0.5,0.35} % comments
\definecolor{javapurple}{rgb}{0.5,0,0.35} % keywords
\definecolor{javadocblue}{rgb}{0.25,0.35,0.75} % javadoc

\lstset{language=Java,
basicstyle=\footnotesize\ttfamily,
keywordstyle=\color{javapurple}\bfseries,
stringstyle=\color{javared},
commentstyle=\color{javagreen},
morecomment=[s][\color{javadocblue}]{/**}{*/},
%numbers=left,
%numberstyle=\tiny\color{black},
%stepnumber=1,
%numbersep=10pt,
tabsize=4,
showspaces=false,
showstringspaces=false}

\lstdefinelanguage{Bytecode}{
  keywords={GETSTATIC, INVOKEVIRTUAL, LDC, RETURN, ICONST, ALOAD, ASTORE},
  keywordstyle=\color{black}\bfseries,
  identifierstyle=\color{black},
  sensitive=false,
  comment=[l]{//},
  morecomment=[s]{/*}{*/},
  commentstyle=\color{purple}\ttfamily,
  stringstyle=\color{red}\ttfamily,
  morestring=[b]',
  morestring=[b]",
  basicstyle=\footnotesize\ttfamily
}

\begin{document}

\title[Optimization]
{Optimizing String manipulation performance}
\author{Markus Wondrak}
\institute
{
  Institute of Computer Science\\
  Johann Wolfgang von Goethe Universität, Frankfurt am Main
}

\frame{\titlepage}

\begin{frame}
  \frametitle{Table of Contents}
  \tableofcontents
\end{frame}

\section{Motivation}

\frame{\sectionpage}

\begin{frame}[fragile]

  \frametitle{Example}
  \framesubtitle{The normal way}

  \begin{lstlisting}[language=Java]
String result = "";

for (int i = 0; i < line.length(); i += 2) {
  result += line.substring(i, i + 1);
}

return result;
  \end{lstlisting}%
\end{frame}

\begin{frame}[fragile]

  \frametitle{Example}
  \framesubtitle{The better way}

  \begin{lstlisting}[language=Java]
StringBuilder result = new StringBuilder();

for (int i = 0; i < line.length(); i+=2) {
   result.append(line.substring(i, i + 1));
}

return result.toString();
  \end{lstlisting}%
\end{frame}

\begin{frame}[fragile]
  \frametitle{Example}
  \framesubtitle{The optimized way}
  \begin{lstlisting}[language=Java]
SubstringString lineOpt = new SubstringString(line);

StringListBuilder builder = new StringListBuilder();

for (int i = 0; i < lineOpt.length(); i+=2) {
  builder.append(lineOpt.substring(i, i + 1));
}

return builder.toString();
  \end{lstlisting}%
\end{frame}

\begin{frame}
  \frametitle{What is the difference?}
	\begin{itemize}
	  \item Java strings are immutable $\rightarrow$ manipulation causes \texttt{char[]} copy
	  \item '\texttt{+}' operator is compiled to a \texttt{StringBuilder}, {\bf but} the loop is not recognized
	  \item \texttt{StringBuilder} also array-based, when filled up the array gets copied
	\end{itemize}
\end{frame}

\begin{frame}
  \frametitle{What is the difference?}
	\begin{itemize}
	  \item optimized types avoid this behavior
	  \item \texttt{SubstringString} returns only a new object pointing to the new boundaries
	  \item \texttt{StringListBuilder} is a linked list
	\end{itemize}
\end{frame}

\begin{frame}
  \frametitle{Measurement}

  \begin{bchart}[step=1000,max=3500]
    \bcbar[text=normal]{3159}
      \smallskip
    \bcbar[text=better]{1205}
      \smallskip
    \bcbar[text=optimized]{1086}
    \bcxlabel{time in $ns$}
  \end{bchart}
\end{frame}

\begin{frame}
  \begin{center}
  \huge Wouldn't it be nice to have the performance of the optimized one with the readability of the normal one?
  \end{center}

\end{frame}

\begin{frame}
  \frametitle{What needs to be done?}
  Given a method optimization definition (e.g. SubstringString), the system should \dots

  \begin{itemize}
    \item \dots be applicable to a already compiled program
    \item \dots identify method calls in the Java bytecode
    \item \dots replace these method calls by the optimized ones
  \end{itemize}
\end{frame}

\section{Bytecode}

\frame{\sectionpage}

\begin{frame}
   \frametitle{Bytecode}
   \begin{itemize}
      \item What the JVM actual executes (platform independence)
      \item Java, Groovy, Scala, JavaScript (and many more)
      \item Assembly language like
      \item Stack-based and imperative
   \end{itemize}
\end{frame}

\begin{frame}[fragile]
  \frametitle{Bytecode Example}
  Java:
  \begin{lstlisting}[language=Java]
String x = "Hallo World";
String y = x.substring(5);
  \end{lstlisting}%
  Bytecode:
  \begin{lstlisting}[language=Bytecode]
LDC "Hallo World!"
ASTORE 1
ALOAD 1
ICONST 5
INVOKEVIRTUAL java/lang/String.substring(I)Ljava/lang/String;
ASTORE 2
  \end{lstlisting}
\end{frame}

\section{WALA}

\frame{\sectionpage}

\begin{frame}
  \frametitle{WALA}
  \begin{itemize}
    \item T.J. Watson Library of Analysis (IBM)
    \item static analysis framework for Java source-/bytecode and Javascript
    \item open source since 2006 at \texttt{http://github.com/wala/WALA}
  \end{itemize}

\end{frame}

\begin{frame}
  \frametitle{Features}

  \begin{itemize}
    \item Java type system and class hierarchy analysis
    \item supports frontends for Java Bytecode from class files
    \item SSA-based Intermediate Representation
    \item bytecode manipulation via the shrike project
  \end{itemize}

\end{frame}

\begin{frame}
  \frametitle{Intermediate Representation}

  \begin{itemize}
    \item central data structure that represents the analyzed method
    \item abstracts the actual bytecode in static single assignment form
    \item consists of a control-flow graph (with $\phi$s)
  \end{itemize}

\end{frame}

\begin{frame}
   \frametitle{Phis}
   \begin{itemize}
      \item Created when two variables are merged in the control flow graph
      \item simple meaning of $v_3 = \phi(v_1, v_2)$: $v_3$ can be $v_1$ or $v_2$
      \item when a basic block has more than one incoming edge
   \end{itemize}

\end{frame}

\begin{frame}[fragile]
  \begin{columns}
    \column{.45\textwidth}
    \begin{lstlisting}[language=Java]
String a = "test";
String b = "test2";
String c = ((is) ? a:b);

return c.substring(9);
    \end{lstlisting}
    \column{.55\textwidth}
    \begin{figure}
      \includegraphics[scale=0.5]{irExample.pdf}
    \end{figure}
  \end{columns}
\end{frame}

\section{Analysis}

\frame{\sectionpage}

\begin{frame}
   \frametitle{Naming}
   \begin{block}{value number}
	   a variable in the IR
   \end{block}

	\begin{block}{local}
		a local variable in the bytecode
	\end{block}

	\begin{block}{label}
    a definition how certain method calls are identified and can be replaced
	\end{block}

\end{frame}

\begin{frame}
  \frametitle{Basic idea}
  \begin{itemize}
      \item Create a dataflow graph of the value numbers in the IR
      \item determine a "bubble" in that graph by
      \begin{itemize}
        \item label all affected method call instructions
        \item inherit the labels to all connected value numbers and instructions, if possible
      \end{itemize}
      \item this "bubble" determines the value numbers for that optimization can applied

  \end{itemize}
\end{frame}

\begin{frame}
  \frametitle{How does the dataflow graph look like?}
  \begin{itemize}
    \item directed graph based on the IR
    \item is composed of 2 kinds of nodes
      \begin{itemize}
        \item \texttt{Reference} merely the value number ($R$)
        \item \texttt{InstructionNode} instruction that uses (or defines) value numbers ($I$)
      \end{itemize}
    \item for $r\in R$, $i \in I$,
    \begin{itemize}
      \item $(i,r)$ is called the definition of $r$
      \item $(r,i)$ is called a use of $r$
    \end{itemize}
    \item $\forall r \in R, in(r) = 1$, so every $r$ has exactly 1 definition, but $n$ uses (SSA)
    \item $\forall i \in I, out(i) \leq 1$, so every $i$ can at most define one $r$
  \end{itemize}
\end{frame}

\begin{frame}
  \frametitle{InstructionNodes}

  \begin{itemize}
    \item \texttt{ConstantNode} a constant definition (e.g. \texttt{"Hallo World"})
    \item \texttt{ParameterNode} a parameter of the method
    \item \texttt{MethodCallNode} a method call (e.g. \texttt{x.f(y)})
    \item \texttt{ReturnNode} a return instruction of the method
    \item \texttt{NewNode} a new instruction of an object
    \item \texttt{PhiNode} a $\phi$ node in the IR
  \end{itemize}

\end{frame}

\begin{frame}
  \frametitle{example graph}
  \begin{center}

  \begin{tikzpicture} [auto, node distance=0.5cm]
    \tikzstyle{every node}=[font=\small]
    \tikzset{
      inst/.style={draw=black, rectangle},
      ref/.style={draw=black, circle}
    }
    \node[inst]                       (constant1) {ConstantNode \texttt{"test"}};
    \node[right = of constant1]         (dummy1) {};
    \node[inst, right = of dummy1]       (constant2) {ConstantNode \texttt{"test2"}};

    \node[ref, below = of constant1]    (v1) {$v_1$};
    \node[below = of dummy1]            (dummy2) {};
    \node[ref, below = of constant2]    (v2) {$v_2$};

    \node[inst, below = of dummy2]       (phi) {$v_3 = \phi(v_1, v_2)$};
    \node[ref, below = of phi]          (v3) {$v_3$};
    \node[inst, below = of v3]          (invoke) {MethodCallNode: $v_5$ = \texttt{java/lang/String.substring(I)}, $v_3$, $v_4$};
    \node[ref, below = of invoke] (v5) {$v_5$};
    \node[inst, below = of v5] (return) {ReturnNode $v_5$};

    \draw[->] (constant1) to (v1);
    \draw[->] (constant2) to (v2);
    \draw[->] (v1) to (phi);
    \draw[->] (v2) to (phi);
    \draw[->] (phi) to (v3);
    \draw[->] (v3) to (invoke);
    \draw[->] (invoke) to (v5);
    \draw[->] (v5) to (return);

  \end{tikzpicture}
  \end{center}
\end{frame}

\begin{frame}[fragile]
  \frametitle{How to define a label?}
  \begin{itemize}
     \item for every optimized type a type implementing \texttt{TypeLabel} must be provided
     \item From the interface \texttt{TypeLabel}:
  \end{itemize}

  \begin{lstlisting}
boolean canBeUsedAsReceiverFor(MethodReference)
boolean canBeUsedAsParamFor(MethodReference,int)
boolean canBeDefinedAsResultOf(MethodReference)
boolean compatibleWith(TypeLabel)
  \end{lstlisting}
\end{frame}

\begin{frame}
  \frametitle{How to deal with phis?}
  \begin{itemize}
    \item $\phi$-nodes just represent the merge of value numbers
    \item any label could be compatible with any $\phi$ instruction
    \item so they are labeled after the analysis has taken place
    \item the decision is made by the count of labeled references connected to the particular $\phi$
  \end{itemize}
\end{frame}

\section{Transformation}

\frame{\sectionpage}

\begin{frame}
	\frametitle{What to do?}
	\begin{itemize}
    \item Create conversation at the "bubbles" barriers
    \item replace the original method calls with the optimized ones
    \item to not overwrite the original values, create appropriate locals for the optimized ones
	\end{itemize}
\end{frame}

\begin{frame}
	\frametitle{How to get the locals for a value number?}
	\begin{itemize}
    \item IR is an abstraction of the actual bytecode
    \item simple stack simulation tries to find the position at which the object is pushed onto / popped of the stack
    \item save the local and the position of the relevant (if any) \texttt{store} / \texttt{load} instruction within the \texttt{InstructionNode}
	\end{itemize}
\end{frame}

\begin{frame}
  \frametitle{Conversations}
  2 different scenarios:
  \begin{enumerate}
    \item \textit{The value is stored to a local}: Double the value and store it to the optimized local
    \item \textit{The value is kept on the stack}: Convert the value on the stack
  \end{enumerate}
\end{frame}

\begin{frame}
  \frametitle{Method call replacement}
  \begin{itemize}
    \item replace the load instruction to load the optimized type
    \item replace the method call itself to match the expected optimized type
    \item replace the store instruction to store the result to the optimized type
  \end{itemize}
\end{frame}

\section{Benchmarks}

\frame{\sectionpage}

\begin{frame}[fragile]
   \frametitle{What is optimized?}

   \begin{itemize}
      \item the normal version with the '\texttt{+}' operator
      \item given the label for the optimized \texttt{SubstringString}
   \end{itemize}

   \begin{lstlisting}[language=Java]
String result = "";

for (int i = 0; i < line.length(); i += 2) {
  result += line.substring(i, i + 1);
}

return result;
   \end{lstlisting}

\end{frame}

\begin{frame}
  \frametitle{What are the results?}
  \begin{bchart}[step=2000,max=6000]
    \bcbar[text=normal]{2956}
      \smallskip
    \bcbar[text=optimized system]{5583}
    \bcxlabel{time in $ns$}
  \end{bchart}
\end{frame}

\begin{frame}
   \frametitle{What went wrong?}
   \begin{itemize}
      \item to append the new substring to the native \texttt{StringBuilder}, conversation is needed
      \item \texttt{char[]} copying takes place within the loop for every iteration
   \end{itemize}
\end{frame}

\begin{frame}[fragile]
   \frametitle{What is optimized?}

   \begin{itemize}
      \item the version with the \texttt{StringBuilder} used around the loop
      \item given labels for the optimized \texttt{SubstringString} and \texttt{StringListBuilder}
   \end{itemize}

   \begin{lstlisting}[language=Java]
StringBuilder result = new StringBuilder();

for (int i = 0; i < line.length(); i+=2) {
   result.append(line.substring(i, i + 1));
}

return result.toString();
   \end{lstlisting}

\end{frame}

\begin{frame}
  \frametitle{What are the results?}
  \begin{bchart}[step=500,max=1500]
    \bcbar[text=normal]{1205}
      \smallskip
    \bcbar[text=optimized manual]{1086}
      \smallskip
    \bcbar[text=optimized system]{1048}
    \bcxlabel{time in $ns$}
  \end{bchart}
\end{frame}

\begin{frame}[fragile]
   \frametitle{Result of JMH}

\begin{lstlisting}[breaklines=false]
Benchmark                    Score  Score error
complexBuilderNormal    608304.032     4526.851
complexBuilderOpt       704025.416     6396.926
complexNormal           442065.793     5267.021
complexOpt              647222.194     4874.660
\end{lstlisting}

\end{frame}

\section{Conclusion}

\frame{\sectionpage}

\begin{frame}
	\frametitle{Lessons learned}
   \begin{itemize}
      \item the growth of the bubble is very limited
      \item many conversations limit the performance (or make it even worse)
      \item provide an additional label that works with the other ones can boost the performance
      \item because of Shrikes loose bytecode creation optimized classes need to be run with \texttt{-noverify}
      \item Automated Tests are great!
   \end{itemize}
\end{frame}

\begin{frame}
	\frametitle{Conclusion}
	\begin{itemize}
      \item the system needs just the definition how to replace a certain method
		\item algorithm to determine the "bubble" is type independent, so not limited to \texttt{String}
		\item transformation on bytecode level makes the system applicable to already compiled programs (libraries in the classpath)
	\end{itemize}
\end{frame}

\begin{frame}
	\frametitle{Future Work}
  \begin{itemize}
    \item loop sensitive \texttt{StringBuilder} optimization
    \item inter procedural optimization would improve performance
    \item a more offensive bubble growing strategy would cause a bigger bubble $\rightarrow$ less conversations
    \item sources and slides at \texttt{github.com/wondee/faststring}
  \end{itemize}
\end{frame}

\end{document}


text:
\documentclass{article}
\usepackage[utf8x]{inputenc}
\usepackage[T1, T2A]{fontenc}
\usepackage[russian]{babel}
\usepackage{amsmath}
\usepackage{amssymb}
\setlength\parindent{0pt}
\usepackage[parfill]{parskip}
\pagenumbering{gobble}

\begin{document}
Все ребра неориентированного ациклического графа покрашены в два цвета: красный и синий. Предложите алгоритм, находящий длину
максимального пути, в котором любые два соседних ребра разного цвета. Ограничение по времени --- $O(V+E)$, где $V$ --- число
вершин графа, $E$ --- число его ребер. Сколько дополнительной памяти требуется вашему алгоритму?
\end{document}