text:
/**
 * @file aes256cbc.c
 * @brief SIDP Encryption Layer - AES256 Encrypt/Decrypt Interface
 */

/*
   Secure Inter-Device Protocol Library

   Copyright 2012-2014 Pedro A. Hortas (pah@ucodev.org)

   Licensed under the Apache License, Version 2.0 (the "License");
   you may not use this file except in compliance with the License.
   You may obtain a copy of the License at

       http://www.apache.org/licenses/LICENSE-2.0

   Unless required by applicable law or agreed to in writing, software
   distributed under the License is distributed on an "AS IS" BASIS,
   WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
   See the License for the specific language governing permissions and
   limitations under the License.
*/

#include <stdio.h>
#include <stdlib.h>
#include <string.h>

#include <openssl/evp.h>
#include <openssl/hmac.h>
#include <openssl/rand.h>

#include "el_aes256cbc.h"

/**
 * @brief AES256 Initialization function.
 * @return 0 on success, -1 on error.
 */
int el_aes256_init(void) {
	/* Nothing to do */
	return 0;
}

/**
 * @brief AES256 Create Key function
 * @see el_aes256_encrypt_data()
 * @see el_aes256_decrypt_data()
 * @param key_data The data that will be used to create the key (eg. user+pass)
 * @param key The key generated, based on key_data value
 * @return 0 on success, -1 on error.
 */
int el_aes256_create_key(const unsigned char *key_data, unsigned char *key) {
	int ret, nrounds = 5;
	unsigned char iv[32];

	ret = EVP_BytesToKey(EVP_aes_256_cbc(), EVP_sha256(), NULL, key_data, strlen((char *) key_data), nrounds, key, iv);

	return -(ret != 32);
}

/**
 * @brief AES256 encrypted data size
 * @see el_aes256_decrypt_output_len()
 * @param plain_data_len The size of the plain-text data
 * @return The required size for the 'out' param of the el_aes256_encrypt_data()
 * function.
 */
size_t el_aes256_encrypt_output_len(size_t plain_data_len) {
	return (plain_data_len | 0xf) + 1 + EVP_MAX_MD_SIZE + EVP_MAX_IV_LENGTH;
}

/**
 * @brief AES256 decrypted data size
 * @see el_aes256_encrypt_output_len()
 * @param enc_data_len The size of encrypted data
 * @return The required size for the 'out' param of the el_aes256_decrypt_data()
 * function
 */
size_t el_aes256_decrypt_output_len(size_t enc_data_len) {
	return enc_data_len;
}

/**
 * @brief AES256 data encryption
 * @see el_aes256_create_key()
 * @see el_aes256_decrypt_data()
 * @param key The key generated by el_aes256_create_key()
 * @param out Output buffer containing the encrypted data
 * @param in Input buffer containing the plain-text data
 * @param in_len The size of the plain-text data buffer
 * @return The size of encrypted data buffer (output) or -1 on error
 */
int el_aes256_encrypt_data(
		const unsigned char *key,
		unsigned char *out,
		const unsigned char *in,
		size_t in_len) {
	EVP_CIPHER_CTX e_ctx;
	unsigned int mdlen;
	int clen, flen;

	unsigned char *iv = out + EVP_MAX_MD_SIZE;
	unsigned char *enctext = out + EVP_MAX_MD_SIZE + EVP_MAX_IV_LENGTH;

	/* Just in case */
	memset(out, 0, EVP_MAX_MD_SIZE + EVP_MAX_IV_LENGTH);

	if (!RAND_bytes(iv, EVP_MAX_IV_LENGTH))
		return -1;

	EVP_CIPHER_CTX_init(&e_ctx);

	if (!EVP_EncryptInit_ex(&e_ctx, EVP_aes_256_cbc(), NULL, key, iv)) {
		EVP_CIPHER_CTX_cleanup(&e_ctx);
		return -2;
	}

	if (!EVP_EncryptUpdate(&e_ctx, enctext, &clen, in, in_len)) {
		EVP_CIPHER_CTX_cleanup(&e_ctx);
		return -3;
	}

	if (!EVP_EncryptFinal_ex(&e_ctx, enctext + clen, &flen)) {
		EVP_CIPHER_CTX_cleanup(&e_ctx);
		return -4;
	}

	EVP_CIPHER_CTX_cleanup(&e_ctx);

	clen += flen;

	if (!HMAC(EVP_sha256(), key, EVP_MAX_KEY_LENGTH, out + EVP_MAX_MD_SIZE, clen + EVP_MAX_IV_LENGTH, out, &mdlen))
		return -5;

	return clen + EVP_MAX_MD_SIZE + EVP_MAX_IV_LENGTH;
}

/**
 * @brief AES256 data decryption
 * @see el_aes256_create_key()
 * @see el_aes256_encrypt_data()
 * @param key The key generated by el_aes256_create_key()
 * @param out Output buffer containing the decrypted data
 * @param in Input buffer containing the encrypted data
 * @param in_len The size of encrypted data buffer
 * @return The size of decrypted data buffer (output) or -1 on error
 */
int el_aes256_decrypt_data(
		const unsigned char *key,
		unsigned char *out,
		const unsigned char *in,
		size_t in_len) {
	EVP_CIPHER_CTX e_ctx;
	unsigned char hmac[EVP_MAX_MD_SIZE];
	unsigned int mdlen;
	int mlen, flen;

	const unsigned char *enctext = in + EVP_MAX_MD_SIZE + EVP_MAX_IV_LENGTH;
	const unsigned char *iv = in + EVP_MAX_MD_SIZE;

	if (!HMAC(EVP_sha256(), key, EVP_MAX_KEY_LENGTH, in + EVP_MAX_MD_SIZE, in_len - EVP_MAX_MD_SIZE, hmac, &mdlen))
		return -1;

	/* Switch to constant-time comparison function */
	if (memcmp(in, hmac, mdlen))
		return -2;

	EVP_CIPHER_CTX_init(&e_ctx);

	if (!EVP_DecryptInit_ex(&e_ctx, EVP_aes_256_cbc(), NULL, key, iv)) {
		EVP_CIPHER_CTX_cleanup(&e_ctx);
		return -3;
	}

	if (!EVP_DecryptUpdate(&e_ctx, out, &mlen, enctext, in_len - EVP_MAX_MD_SIZE - EVP_MAX_IV_LENGTH)) {
		EVP_CIPHER_CTX_cleanup(&e_ctx);
		return -4;
	}

	EVP_DecryptFinal_ex(&e_ctx, out + mlen, &flen);

	EVP_CIPHER_CTX_cleanup(&e_ctx);

	return mlen + flen;
}


text:
 var x = {};

 WScript.Echo("x.valueOf()");
 try {
    x.valueOf();  //Fine - there's no way to inject null or undefined as the 'this' value
 }
 catch (e)
 {
    WScript.Echo(e);
 }

WScript.Echo("x.valueOf.call(undefined)");
 try {
    x.valueOf.call(undefined);  //SHOULD throw a TypeError in ES5/IE10
 }
 catch (e)
 {
    WScript.Echo(e);
 }

WScript.Echo("x.valueOf.call(null)");
 try {
    x.valueOf.call(null);  //SHOULD throw a TypeError in ES5/IE10
 }
 catch (e)
 {
    WScript.Echo(e);
 }

WScript.Echo("x.valueOf.call()");
 try {
    x.valueOf.call();  //SHOULD throw a TypeError in ES5/IE10
 }
 catch (e)
 {
    WScript.Echo(e);
 }

WScript.Echo("typeof x.valueOf.call(true)");
 WScript.Echo(typeof x.valueOf.call(true));  //SHOULD print 'object' in ES5/IE10

WScript.Echo("typeof x.valueOf.call(42)");
 WScript.Echo(typeof x.valueOf.call(42));  //SHOULD print 'object' in ES5/IE10

WScript.Echo("typeof x.valueOf.call('Hello')");
 WScript.Echo(typeof x.valueOf.call('Hello'));  //SHOULD print 'object' in ES5/IE10

redpajama_set_name: RedPajamaGithub


text:
import collections
import itertools

from oslo.config import cfg
from oslo.serialization import jsonutils
from oslo.utils import units
import six

from nova import context
from nova import exception
from nova.i18n import _
from nova import objects
from nova.openstack.common import log as logging

virt_cpu_opts = [
    cfg.StrOpt('vcpu_pin_set',
                help='Defines which pcpus that instance vcpus can use. '
               'For example, "4-12,^8,15"'),
]

CONF = cfg.CONF
CONF.register_opts(virt_cpu_opts)

LOG = logging.getLogger(__name__)

MEMPAGES_SMALL = -1
MEMPAGES_LARGE = -2
MEMPAGES_ANY = -3

def get_vcpu_pin_set():
    """Parsing vcpu_pin_set config.

    Returns a set of pcpu ids can be used by instances.
    """
    if not CONF.vcpu_pin_set:
        return None

    cpuset_ids = parse_cpu_spec(CONF.vcpu_pin_set)
    if not cpuset_ids:
        raise exception.Invalid(_("No CPUs available after parsing %r") %
                                CONF.vcpu_pin_set)
    return cpuset_ids

def parse_cpu_spec(spec):
    """Parse a CPU set specification.

    :param spec: cpu set string eg "1-4,^3,6"

    Each element in the list is either a single
    CPU number, a range of CPU numbers, or a
    caret followed by a CPU number to be excluded
    from a previous range.

    :returns: a set of CPU indexes
    """

    cpuset_ids = set()
    cpuset_reject_ids = set()
    for rule in spec.split(','):
        rule = rule.strip()
        # Handle multi ','
        if len(rule) < 1:
            continue
        # Note the count limit in the .split() call
        range_parts = rule.split('-', 1)
        if len(range_parts) > 1:
            # So, this was a range; start by converting the parts to ints
            try:
                start, end = [int(p.strip()) for p in range_parts]
            except ValueError:
                raise exception.Invalid(_("Invalid range expression %r")
                                        % rule)
            # Make sure it's a valid range
            if start > end:
                raise exception.Invalid(_("Invalid range expression %r")
                                        % rule)
            # Add available CPU ids to set
            cpuset_ids |= set(range(start, end + 1))
        elif rule[0] == '^':
            # Not a range, the rule is an exclusion rule; convert to int
            try:
                cpuset_reject_ids.add(int(rule[1:].strip()))
            except ValueError:
                raise exception.Invalid(_("Invalid exclusion "
                                          "expression %r") % rule)
        else:
            # OK, a single CPU to include; convert to int
            try:
                cpuset_ids.add(int(rule))
            except ValueError:
                raise exception.Invalid(_("Invalid inclusion "
                                          "expression %r") % rule)

    # Use sets to handle the exclusion rules for us
    cpuset_ids -= cpuset_reject_ids

    return cpuset_ids

def format_cpu_spec(cpuset, allow_ranges=True):
    """Format a libvirt CPU range specification.

    :param cpuset: set (or list) of CPU indexes

    Format a set/list of CPU indexes as a libvirt CPU
    range specification. It allow_ranges is true, it
    will try to detect continuous ranges of CPUs,
    otherwise it will just list each CPU index explicitly.

    :returns: a formatted CPU range string
    """

    # We attempt to detect ranges, but don't bother with
    # trying to do range negations to minimize the overall
    # spec string length
    if allow_ranges:
        ranges = []
        previndex = None
        for cpuindex in sorted(cpuset):
            if previndex is None or previndex != (cpuindex - 1):
                ranges.append([])
            ranges[-1].append(cpuindex)
            previndex = cpuindex

        parts = []
        for entry in ranges:
            if len(entry) == 1:
                parts.append(str(entry[0]))
            else:
                parts.append("%d-%d" % (entry[0], entry[len(entry) - 1]))
        return ",".join(parts)
    else:
        return ",".join(str(id) for id in sorted(cpuset))

def get_number_of_serial_ports(flavor, image_meta):
    """Get the number of serial consoles from the flavor or image

    :param flavor: Flavor object to read extra specs from
    :param image_meta: Image object to read image metadata from

    If flavor extra specs is not set, then any image meta value is permitted.
    If flavour extra specs *is* set, then this provides the default serial
    port count. The image meta is permitted to override the extra specs, but
    *only* with a lower value. ie

    - flavor hw:serial_port_count=4
      VM gets 4 serial ports
    - flavor hw:serial_port_count=4 and image hw_serial_port_count=2
      VM gets 2 serial ports
    - image hw_serial_port_count=6
      VM gets 6 serial ports
    - flavor hw:serial_port_count=4 and image hw_serial_port_count=6
      Abort guest boot - forbidden to exceed flavor value

    :returns: number of serial ports
    """

    def get_number(obj, property):
        num_ports = obj.get(property)
        if num_ports is not None:
            try:
                num_ports = int(num_ports)
            except ValueError:
                raise exception.ImageSerialPortNumberInvalid(
                    num_ports=num_ports, property=property)
        return num_ports

    image_meta_prop = (image_meta or {}).get('properties', {})

    flavor_num_ports = get_number(flavor.extra_specs, "hw:serial_port_count")
    image_num_ports = get_number(image_meta_prop, "hw_serial_port_count")

    if (flavor_num_ports and image_num_ports) is not None:
        if image_num_ports > flavor_num_ports:
            raise exception.ImageSerialPortNumberExceedFlavorValue()
        return image_num_ports

    return flavor_num_ports or image_num_ports or 1

class InstanceInfo(object):

    def __init__(self, state=None, max_mem_kb=0, mem_kb=0, num_cpu=0,
                 cpu_time_ns=0, id=None):
        """Create a new Instance Info object

        :param state: the running state, one of the power_state codes
        :param max_mem_kb: (int) the maximum memory in KBytes allowed
        :param mem_kb: (int) the memory in KBytes used by the instance
        :param num_cpu: (int) the number of virtual CPUs for the instance
        :param cpu_time_ns: (int) the CPU time used in nanoseconds
        :param id: a unique ID for the instance
        """
        self.state = state
        self.max_mem_kb = max_mem_kb
        self.mem_kb = mem_kb
        self.num_cpu = num_cpu
        self.cpu_time_ns = cpu_time_ns
        self.id = id

    def __eq__(self, other):
        return (self.__class__ == other.__class__ and
                self.__dict__ == other.__dict__)

def _score_cpu_topology(topology, wanttopology):
    """Calculate score for the topology against a desired configuration

    :param wanttopology: nova.objects.VirtCPUTopology instance for
                         preferred topology

    Calculate a score indicating how well this topology
    matches against a preferred topology. A score of 3
    indicates an exact match for sockets, cores and threads.
    A score of 2 indicates a match of sockets & cores or
    sockets & threads or cores and threads. A score of 1
    indicates a match of sockets or cores or threads. A
    score of 0 indicates no match

    :returns: score in range 0 (worst) to 3 (best)
    """

    score = 0
    if (wanttopology.sockets != -1 and
        topology.sockets == wanttopology.sockets):
        score = score + 1
    if (wanttopology.cores != -1 and
        topology.cores == wanttopology.cores):
        score = score + 1
    if (wanttopology.threads != -1 and
        topology.threads == wanttopology.threads):
        score = score + 1
    return score

def _get_cpu_topology_constraints(flavor, image_meta):
    """Get the topology constraints declared in flavor or image

    :param flavor: Flavor object to read extra specs from
    :param image_meta: Image object to read image metadata from

    Gets the topology constraints from the configuration defined
    in the flavor extra specs or the image metadata. In the flavor
    this will look for

     hw:cpu_sockets - preferred socket count
     hw:cpu_cores - preferred core count
     hw:cpu_threads - preferred thread count
     hw:cpu_maxsockets - maximum socket count
     hw:cpu_maxcores - maximum core count
     hw:cpu_maxthreads - maximum thread count

    In the image metadata this will look at

     hw_cpu_sockets - preferred socket count
     hw_cpu_cores - preferred core count
     hw_cpu_threads - preferred thread count
     hw_cpu_maxsockets - maximum socket count
     hw_cpu_maxcores - maximum core count
     hw_cpu_maxthreads - maximum thread count

    The image metadata must be strictly lower than any values
    set in the flavor. All values are, however, optional.

    This will return a pair of nova.objects.VirtCPUTopology instances,
    the first giving the preferred socket/core/thread counts,
    and the second giving the upper limits on socket/core/
    thread counts.

    exception.ImageVCPULimitsRangeExceeded will be raised
    if the maximum counts set against the image exceed
    the maximum counts set against the flavor

    exception.ImageVCPUTopologyRangeExceeded will be raised
    if the preferred counts set against the image exceed
    the maximum counts set against the image or flavor

    :returns: (preferred topology, maximum topology)
    """

    # Obtain the absolute limits from the flavor
    flvmaxsockets = int(flavor.extra_specs.get(
        "hw:cpu_max_sockets", 65536))
    flvmaxcores = int(flavor.extra_specs.get(
        "hw:cpu_max_cores", 65536))
    flvmaxthreads = int(flavor.extra_specs.get(
        "hw:cpu_max_threads", 65536))

    LOG.debug("Flavor limits %(sockets)d:%(cores)d:%(threads)d",
              {"sockets": flvmaxsockets,
               "cores": flvmaxcores,
               "threads": flvmaxthreads})

    # Get any customized limits from the image
    maxsockets = int(image_meta.get("properties", {})
                     .get("hw_cpu_max_sockets", flvmaxsockets))
    maxcores = int(image_meta.get("properties", {})
                   .get("hw_cpu_max_cores", flvmaxcores))
    maxthreads = int(image_meta.get("properties", {})
                     .get("hw_cpu_max_threads", flvmaxthreads))

    LOG.debug("Image limits %(sockets)d:%(cores)d:%(threads)d",
              {"sockets": maxsockets,
               "cores": maxcores,
               "threads": maxthreads})

    # Image limits are not permitted to exceed the flavor
    # limits. ie they can only lower what the flavor defines
    if ((maxsockets > flvmaxsockets) or
        (maxcores > flvmaxcores) or
        (maxthreads > flvmaxthreads)):
        raise exception.ImageVCPULimitsRangeExceeded(
            sockets=maxsockets,
            cores=maxcores,
            threads=maxthreads,
            maxsockets=flvmaxsockets,
            maxcores=flvmaxcores,
            maxthreads=flvmaxthreads)

    # Get any default preferred topology from the flavor
    flvsockets = int(flavor.extra_specs.get("hw:cpu_sockets", -1))
    flvcores = int(flavor.extra_specs.get("hw:cpu_cores", -1))
    flvthreads = int(flavor.extra_specs.get("hw:cpu_threads", -1))

    LOG.debug("Flavor pref %(sockets)d:%(cores)d:%(threads)d",
              {"sockets": flvsockets,
               "cores": flvcores,
               "threads": flvthreads})

    # If the image limits have reduced the flavor limits
    # we might need to discard the preferred topology
    # from the flavor
    if ((flvsockets > maxsockets) or
        (flvcores > maxcores) or
        (flvthreads > maxthreads)):
        flvsockets = flvcores = flvthreads = -1

    # Finally see if the image has provided a preferred
    # topology to use
    sockets = int(image_meta.get("properties", {})
                  .get("hw_cpu_sockets", -1))
    cores = int(image_meta.get("properties", {})
                .get("hw_cpu_cores", -1))
    threads = int(image_meta.get("properties", {})
                  .get("hw_cpu_threads", -1))

    LOG.debug("Image pref %(sockets)d:%(cores)d:%(threads)d",
              {"sockets": sockets,
               "cores": cores,
               "threads": threads})

    # Image topology is not permitted to exceed image/flavor
    # limits
    if ((sockets > maxsockets) or
        (cores > maxcores) or
        (threads > maxthreads)):
        raise exception.ImageVCPUTopologyRangeExceeded(
            sockets=sockets,
            cores=cores,
            threads=threads,
            maxsockets=maxsockets,
            maxcores=maxcores,
            maxthreads=maxthreads)

    # If no preferred topology was set against the image
    # then use the preferred topology from the flavor
    # We use 'and' not 'or', since if any value is set
    # against the image this invalidates the entire set
    # of values from the flavor
    if sockets == -1 and cores == -1 and threads == -1:
        sockets = flvsockets
        cores = flvcores
        threads = flvthreads

    LOG.debug("Chosen %(sockets)d:%(cores)d:%(threads)d limits "
              "%(maxsockets)d:%(maxcores)d:%(maxthreads)d",
              {"sockets": sockets, "cores": cores,
               "threads": threads, "maxsockets": maxsockets,
               "maxcores": maxcores, "maxthreads": maxthreads})

    return (objects.VirtCPUTopology(sockets=sockets, cores=cores,
                                    threads=threads),
            objects.VirtCPUTopology(sockets=maxsockets, cores=maxcores,
                                    threads=maxthreads))

def _get_possible_cpu_topologies(vcpus, maxtopology, allow_threads):
    """Get a list of possible topologies for a vCPU count
    :param vcpus: total number of CPUs for guest instance
    :param maxtopology: nova.objects.VirtCPUTopology for upper limits
    :param allow_threads: if the hypervisor supports CPU threads

    Given a total desired vCPU count and constraints on the
    maximum number of sockets, cores and threads, return a
    list of nova.objects.VirtCPUTopology instances that represent every
    possible topology that satisfies the constraints.

    exception.ImageVCPULimitsRangeImpossible is raised if
    it is impossible to achieve the total vcpu count given
    the maximum limits on sockets, cores & threads.

    :returns: list of nova.objects.VirtCPUTopology instances
    """

    # Clamp limits to number of vcpus to prevent
    # iterating over insanely large list
    maxsockets = min(vcpus, maxtopology.sockets)
    maxcores = min(vcpus, maxtopology.cores)
    maxthreads = min(vcpus, maxtopology.threads)

    if not allow_threads:
        maxthreads = 1

    LOG.debug("Build topologies for %(vcpus)d vcpu(s) "
              "%(maxsockets)d:%(maxcores)d:%(maxthreads)d",
              {"vcpus": vcpus, "maxsockets": maxsockets,
               "maxcores": maxcores, "maxthreads": maxthreads})

    # Figure out all possible topologies that match
    # the required vcpus count and satisfy the declared
    # limits. If the total vCPU count were very high
    # it might be more efficient to factorize the vcpu
    # count and then only iterate over its factors, but
    # that's overkill right now
    possible = []
    for s in range(1, maxsockets + 1):
        for c in range(1, maxcores + 1):
            for t in range(1, maxthreads + 1):
                if t * c * s == vcpus:
                    o = objects.VirtCPUTopology(sockets=s, cores=c,
                                                threads=t)

                    possible.append(o)

    # We want to
    #  - Minimize threads (ie larger sockets * cores is best)
    #  - Prefer sockets over cores
    possible = sorted(possible, reverse=True,
                      key=lambda x: (x.sockets * x.cores,
                                     x.sockets,
                                     x.threads))

    LOG.debug("Got %d possible topologies", len(possible))
    if len(possible) == 0:
        raise exception.ImageVCPULimitsRangeImpossible(vcpus=vcpus,
                                                       sockets=maxsockets,
                                                       cores=maxcores,
                                                       threads=maxthreads)

    return possible

def _sort_possible_cpu_topologies(possible, wanttopology):
    """Sort the topologies in order of preference
    :param possible: list of nova.objects.VirtCPUTopology instances
    :param wanttopology: nova.objects.VirtCPUTopology for preferred
                         topology

    This takes the list of possible topologies and resorts
    it such that those configurations which most closely
    match the preferred topology are first.

    :returns: sorted list of nova.objects.VirtCPUTopology instances
    """

    # Look at possible topologies and score them according
    # to how well they match the preferred topologies
    # We don't use python's sort(), since we want to
    # preserve the sorting done when populating the
    # 'possible' list originally
    scores = collections.defaultdict(list)
    for topology in possible:
        score = _score_cpu_topology(topology, wanttopology)
        scores[score].append(topology)

    # Build list of all possible topologies sorted
    # by the match score, best match first
    desired = []
    desired.extend(scores[3])
    desired.extend(scores[2])
    desired.extend(scores[1])
    desired.extend(scores[0])

    return desired

def _get_desirable_cpu_topologies(flavor, image_meta, allow_threads=True):
    """Get desired CPU topologies according to settings

    :param flavor: Flavor object to query extra specs from
    :param image_meta: ImageMeta object to query properties from
    :param allow_threads: if the hypervisor supports CPU threads

    Look at the properties set in the flavor extra specs and
    the image metadata and build up a list of all possible
    valid CPU topologies that can be used in the guest. Then
    return this list sorted in order of preference.

    :returns: sorted list of nova.objects.VirtCPUTopology instances
    """

    LOG.debug("Getting desirable topologies for flavor %(flavor)s "
              "and image_meta %(image_meta)s",
              {"flavor": flavor, "image_meta": image_meta})

    preferred, maximum = _get_cpu_topology_constraints(flavor, image_meta)

    possible = _get_possible_cpu_topologies(flavor.vcpus,
                                            maximum,
                                            allow_threads)
    desired = _sort_possible_cpu_topologies(possible, preferred)

    return desired

def get_best_cpu_topology(flavor, image_meta, allow_threads=True):
    """Get best CPU topology according to settings

    :param flavor: Flavor object to query extra specs from
    :param image_meta: ImageMeta object to query properties from
    :param allow_threads: if the hypervisor supports CPU threads

    Look at the properties set in the flavor extra specs and
    the image metadata and build up a list of all possible
    valid CPU topologies that can be used in the guest. Then
    return the best topology to use

    :returns: a nova.objects.VirtCPUTopology instance for best topology
    """

    return _get_desirable_cpu_topologies(flavor, image_meta, allow_threads)[0]

class VirtNUMATopologyCell(object):
    """Class for reporting NUMA resources in a cell

    The VirtNUMATopologyCell class represents the
    hardware resources present in a NUMA cell.
    """

    def __init__(self, id, cpuset, memory):
        """Create a new NUMA Cell

        :param id: integer identifier of cell
        :param cpuset: set containing list of CPU indexes
        :param memory: RAM measured in MiB

        Creates a new NUMA cell object to record the hardware
        resources.

        :returns: a new NUMA cell object
        """

        super(VirtNUMATopologyCell, self).__init__()

        self.id = id
        self.cpuset = cpuset
        self.memory = memory

    def _to_dict(self):
        return {'cpus': format_cpu_spec(self.cpuset, allow_ranges=False),
                'mem': {'total': self.memory},
                'id': self.id}

    @classmethod
    def _from_dict(cls, data_dict):
        cpuset = parse_cpu_spec(data_dict.get('cpus', ''))
        memory = data_dict.get('mem', {}).get('total', 0)
        cell_id = data_dict.get('id')
        return cls(cell_id, cpuset, memory)

class VirtNUMATopologyCellLimit(VirtNUMATopologyCell):
    def __init__(self, id, cpuset, memory, cpu_limit, memory_limit):
        """Create a new NUMA Cell with usage

        :param id: integer identifier of cell
        :param cpuset: set containing list of CPU indexes
        :param memory: RAM measured in MiB
        :param cpu_limit: maximum number of  CPUs allocated
        :param memory_usage: maxumum RAM allocated in MiB

        Creates a new NUMA cell object to represent the max hardware
        resources and utilization. The number of CPUs specified
        by the @cpu_usage parameter may be larger than the number
        of bits set in @cpuset if CPU overcommit is used. Likewise
        the amount of RAM specified by the @memory_usage parameter
        may be larger than the available RAM in @memory if RAM
        overcommit is used.

        :returns: a new NUMA cell object
        """

        super(VirtNUMATopologyCellLimit, self).__init__(
            id, cpuset, memory)

        self.cpu_limit = cpu_limit
        self.memory_limit = memory_limit

    def _to_dict(self):
        data_dict = super(VirtNUMATopologyCellLimit, self)._to_dict()
        data_dict['mem']['limit'] = self.memory_limit
        data_dict['cpu_limit'] = self.cpu_limit
        return data_dict

    @classmethod
    def _from_dict(cls, data_dict):
        cpuset = parse_cpu_spec(data_dict.get('cpus', ''))
        memory = data_dict.get('mem', {}).get('total', 0)
        cpu_limit = data_dict.get('cpu_limit', len(cpuset))
        memory_limit = data_dict.get('mem', {}).get('limit', memory)
        cell_id = data_dict.get('id')
        return cls(cell_id, cpuset, memory, cpu_limit, memory_limit)

def _numa_cell_supports_pagesize_request(host_cell, inst_cell):
    """Determines whether the cell can accept the request.

    :param host_cell: host cell to fit the instance cell onto
    :param inst_cell: instance cell we want to fit

    :returns: The page size able to be handled by host_cell
    """
    avail_pagesize = [page.size_kb for page in host_cell.mempages]
    avail_pagesize.sort(reverse=True)

    def verify_pagesizes(host_cell, inst_cell, avail_pagesize):
        inst_cell_mem = inst_cell.memory * units.Ki
        for pagesize in avail_pagesize:
            if host_cell.can_fit_hugepages(pagesize, inst_cell_mem):
                return pagesize

    if inst_cell.pagesize == MEMPAGES_SMALL:
        return verify_pagesizes(host_cell, inst_cell, avail_pagesize[-1:])
    elif inst_cell.pagesize == MEMPAGES_LARGE:
        return verify_pagesizes(host_cell, inst_cell, avail_pagesize[:-1])
    elif inst_cell.pagesize == MEMPAGES_ANY:
        return verify_pagesizes(host_cell, inst_cell, avail_pagesize)
    else:
        return verify_pagesizes(host_cell, inst_cell, [inst_cell.pagesize])

def _pack_instance_onto_cores(available_siblings, instance_cell, host_cell_id):
    """Pack an instance onto a set of siblings

    :param available_siblings: list of sets of CPU id's - available
                               siblings per core
    :param instance_cell: An instance of objects.InstanceNUMACell describing
                          the pinning requirements of the instance

    :returns: An instance of objects.InstanceNUMACell containing the pinning
              information, and potentially a new topology to be exposed to the
              instance. None if there is no valid way to satisfy the sibling
              requirements for the instance.

    This method will calculate the pinning for the given instance and it's
    topology, making sure that hyperthreads of the instance match up with
    those of the host when the pinning takes effect.
    """

    # We build up a data structure 'can_pack' that answers the question:
    # 'Given the number of threads I want to pack, give me a list of all
    # the available sibling sets that can accomodate it'
    can_pack = collections.defaultdict(list)
    for sib in available_siblings:
        for threads_no in range(1, len(sib) + 1):
            can_pack[threads_no].append(sib)

    def _can_pack_instance_cell(instance_cell, threads_per_core, cores_list):
        """Determines if instance cell can fit an avail set of cores."""

        if threads_per_core * len(cores_list) < len(instance_cell):
            return False
        if instance_cell.siblings:
            return instance_cell.cpu_topology.threads <= threads_per_core
        else:
            return len(instance_cell) % threads_per_core == 0

    # We iterate over the can_pack dict in descending order of cores that
    # can be packed - an attempt to get even distribution over time
    for cores_per_sib, sib_list in sorted(
            (t for t in can_pack.items()), reverse=True):
        if _can_pack_instance_cell(instance_cell,
                                   cores_per_sib, sib_list):
            sliced_sibs = map(lambda s: list(s)[:cores_per_sib], sib_list)
            if instance_cell.siblings:
                pinning = zip(itertools.chain(*instance_cell.siblings),
                              itertools.chain(*sliced_sibs))
            else:
                pinning = zip(sorted(instance_cell.cpuset),
                              itertools.chain(*sliced_sibs))

            topology = (instance_cell.cpu_topology or
                        objects.VirtCPUTopology(sockets=1,
                                                cores=len(sliced_sibs),
                                                threads=cores_per_sib))
            instance_cell.pin_vcpus(*pinning)
            instance_cell.cpu_topology = topology
            instance_cell.id = host_cell_id
            return instance_cell

def _numa_fit_instance_cell_with_pinning(host_cell, instance_cell):
    """Figure out if cells can be pinned to a host cell and return details

    :param host_cell: objects.NUMACell instance - the host cell that
                      the isntance should be pinned to
    :param instance_cell: objects.InstanceNUMACell instance without any
                          pinning information

    :returns: objects.InstanceNUMACell instance with pinning information,
              or None if instance cannot be pinned to the given host
    """
    if (host_cell.avail_cpus < len(instance_cell.cpuset) or
        host_cell.avail_memory < instance_cell.memory):
        # If we do not have enough CPUs available or not enough memory
        # on the host cell, we quit early (no oversubscription).
        return

    if host_cell.siblings:
        # Instance requires hyperthreading in it's topology
        if instance_cell.cpu_topology and instance_cell.siblings:
            return _pack_instance_onto_cores(host_cell.free_siblings,
                                             instance_cell, host_cell.id)

        else:
            # Try to pack the instance cell in one core
            largest_free_sibling_set = sorted(
                host_cell.free_siblings, key=len)[-1]
            if (len(instance_cell.cpuset) <=
                    len(largest_free_sibling_set)):
                return _pack_instance_onto_cores(
                    [largest_free_sibling_set], instance_cell, host_cell.id)

            # We can't to pack it onto one core so try with avail siblings
            else:
                return _pack_instance_onto_cores(
                    host_cell.free_siblings, instance_cell, host_cell.id)
    else:
        # Straightforward to pin to available cpus when there is no
        # hyperthreading on the host
        return _pack_instance_onto_cores(
            [host_cell.free_cpus], instance_cell, host_cell.id)

def _numa_fit_instance_cell(host_cell, instance_cell, limit_cell=None):
    """Check if a instance cell can fit and set it's cell id

    :param host_cell: host cell to fit the instance cell onto
    :param instance_cell: instance cell we want to fit
    :param limit_cell: cell with limits of the host_cell if any

    Make sure we can fit the instance cell onto a host cell and if so,
    return a new objects.InstanceNUMACell with the id set to that of
    the host, or None if the cell exceeds the limits of the host

    :returns: a new instance cell or None
    """
    # NOTE (ndipanov): do not allow an instance to overcommit against
    # itself on any NUMA cell
    if (instance_cell.memory > host_cell.memory or
            len(instance_cell.cpuset) > len(host_cell.cpuset)):
        return None

    if instance_cell.cpu_pinning is not None:
        new_instance_cell = _numa_fit_instance_cell_with_pinning(
            host_cell, instance_cell)
        if not new_instance_cell:
            return
        new_instance_cell.pagesize = instance_cell.pagesize
        instance_cell = new_instance_cell

    elif limit_cell:
        memory_usage = host_cell.memory_usage + instance_cell.memory
        cpu_usage = host_cell.cpu_usage + len(instance_cell.cpuset)
        if (memory_usage > limit_cell.memory_limit or
                cpu_usage > limit_cell.cpu_limit):
            return None

    pagesize = None
    if instance_cell.pagesize:
        pagesize = _numa_cell_supports_pagesize_request(
            host_cell, instance_cell)
        if not pagesize:
            return

    instance_cell.id = host_cell.id
    instance_cell.pagesize = pagesize
    return instance_cell

class VirtNUMATopology(object):
    """Base class for tracking NUMA topology information

    The VirtNUMATopology class represents the NUMA hardware
    topology for memory and CPUs in any machine. It is
    later specialized for handling either guest instance
    or compute host NUMA topology.
    """

    def __init__(self, cells=None):
        """Create a new NUMA topology object

        :param cells: list of VirtNUMATopologyCell instances

        """

        super(VirtNUMATopology, self).__init__()

        self.cells = cells or []

    def __len__(self):
        """Defined so that boolean testing works the same as for lists."""
        return len(self.cells)

    def __repr__(self):
        return "<%s: %s>" % (self.__class__.__name__, str(self._to_dict()))

    def _to_dict(self):
        return {'cells': [cell._to_dict() for cell in self.cells]}

    @classmethod
    def _from_dict(cls, data_dict):
        return cls(cells=[cls.cell_class._from_dict(cell_dict)
                          for cell_dict in data_dict.get('cells', [])])

    def to_json(self):
        return jsonutils.dumps(self._to_dict())

    @classmethod
    def from_json(cls, json_string):
        return cls._from_dict(jsonutils.loads(json_string))

def _numa_get_flavor_or_image_prop(flavor, image_meta, propname):
    """Return the value of propname from flavor or image

    :param flavor: a Flavor object or dict of instance type information
    :param image_meta: a dict of image information

    :returns: a value or None
    """
    flavor_val = flavor.get('extra_specs', {}).get("hw:" + propname)
    image_val = (image_meta or {}).get("properties", {}).get("hw_" + propname)

    if flavor_val is not None:
        if image_val is not None:
            raise exception.ImageNUMATopologyForbidden(
                name='hw_' + propname)

        return flavor_val
    else:
        return image_val

def _numa_get_pagesize_constraints(flavor, image_meta):
    """Return the requested memory page size

    :param flavor: a Flavor object to read extra specs from
    :param image_meta: an Image object to read meta data from

    :raises: MemoryPagesSizeInvalid or MemoryPageSizeForbidden
    :returns: a page size requested or MEMPAGES_*
    """

    def check_and_return_pages_size(request):
        if request == "any":
            return MEMPAGES_ANY
        elif request == "large":
            return MEMPAGES_LARGE
        elif request == "small":
            return MEMPAGES_SMALL
        else:
            try:
                request = int(request)
            except ValueError:
                request = 0

        if request <= 0:
            raise exception.MemoryPageSizeInvalid(pagesize=request)

        return request

    image_meta_prop = (image_meta or {}).get("properties", {})

    flavor_request = flavor.get('extra_specs', {}).get("hw:mem_page_size", "")
    image_request = image_meta_prop.get("hw_mem_page_size", "")

    if not flavor_request and image_request:
        raise exception.MemoryPageSizeForbidden(
            pagesize=image_request,
            against="<empty>")

    if not flavor_request:
        # Nothing was specified for hugepages,
        # let's the default process running.
        return None

    pagesize = check_and_return_pages_size(flavor_request)
    if image_request and (pagesize in (MEMPAGES_ANY, MEMPAGES_LARGE)):
        return check_and_return_pages_size(image_request)
    elif image_request:
        raise exception.MemoryPageSizeForbidden(
            pagesize=image_request,
            against=flavor_request)

    return pagesize

def _numa_get_constraints_manual(nodes, flavor, image_meta):
    cells = []
    totalmem = 0

    availcpus = set(range(flavor['vcpus']))

    for node in range(nodes):
        cpus = _numa_get_flavor_or_image_prop(
            flavor, image_meta, "numa_cpus.%d" % node)
        mem = _numa_get_flavor_or_image_prop(
            flavor, image_meta, "numa_mem.%d" % node)

        # We're expecting both properties set, so
        # raise an error if either is missing
        if cpus is None or mem is None:
            raise exception.ImageNUMATopologyIncomplete()

        mem = int(mem)
        cpuset = parse_cpu_spec(cpus)

        for cpu in cpuset:
            if cpu > (flavor['vcpus'] - 1):
                raise exception.ImageNUMATopologyCPUOutOfRange(
                    cpunum=cpu, cpumax=(flavor['vcpus'] - 1))

            if cpu not in availcpus:
                raise exception.ImageNUMATopologyCPUDuplicates(
                    cpunum=cpu)

            availcpus.remove(cpu)

        cells.append(objects.InstanceNUMACell(
            id=node, cpuset=cpuset, memory=mem))
        totalmem = totalmem + mem

    if availcpus:
        raise exception.ImageNUMATopologyCPUsUnassigned(
            cpuset=str(availcpus))

    if totalmem != flavor['memory_mb']:
        raise exception.ImageNUMATopologyMemoryOutOfRange(
            memsize=totalmem,
            memtotal=flavor['memory_mb'])

    return objects.InstanceNUMATopology(cells=cells)

def _numa_get_constraints_auto(nodes, flavor, image_meta):
    if ((flavor['vcpus'] % nodes) > 0 or
        (flavor['memory_mb'] % nodes) > 0):
        raise exception.ImageNUMATopologyAsymmetric()

    cells = []
    for node in range(nodes):
        cpus = _numa_get_flavor_or_image_prop(
            flavor, image_meta, "numa_cpus.%d" % node)
        mem = _numa_get_flavor_or_image_prop(
            flavor, image_meta, "numa_mem.%d" % node)

        # We're not expecting any properties set, so
        # raise an error if there are any
        if cpus is not None or mem is not None:
            raise exception.ImageNUMATopologyIncomplete()

        ncpus = int(flavor['vcpus'] / nodes)
        mem = int(flavor['memory_mb'] / nodes)
        start = node * ncpus
        cpuset = set(range(start, start + ncpus))

        cells.append(objects.InstanceNUMACell(
            id=node, cpuset=cpuset, memory=mem))

    return objects.InstanceNUMATopology(cells=cells)

# TODO(sahid): Move numa related to hardward/numa.py
def numa_get_constraints(flavor, image_meta):
    """Return topology related to input request

    :param flavor: Flavor object to read extra specs from
    :param image_meta: Image object to read image metadata from

    :returns: InstanceNUMATopology or None
    """
    nodes = _numa_get_flavor_or_image_prop(
        flavor, image_meta, "numa_nodes")
    pagesize = _numa_get_pagesize_constraints(
        flavor, image_meta)

    topology = None
    if nodes or pagesize:
        nodes = nodes and int(nodes) or 1
        # We'll pick what path to go down based on whether
        # anything is set for the first node. Both paths
        # have logic to cope with inconsistent property usage
        auto = _numa_get_flavor_or_image_prop(
            flavor, image_meta, "numa_cpus.0") is None

        if auto:
            topology = _numa_get_constraints_auto(
                nodes, flavor, image_meta)
        else:
            topology = _numa_get_constraints_manual(
                nodes, flavor, image_meta)

        # We currently support same pagesize for all cells.
        [setattr(c, 'pagesize', pagesize) for c in topology.cells]

    return topology

class VirtNUMALimitTopology(VirtNUMATopology):
    """Class to represent the max resources of a compute node used
    for checking oversubscription limits.
    """

    cell_class = VirtNUMATopologyCellLimit

def numa_fit_instance_to_host(
        host_topology, instance_topology, limits_topology=None):
    """Fit the instance topology onto the host topology given the limits

    :param host_topology: objects.NUMATopology object to fit an instance on
    :param instance_topology: objects.InstanceNUMATopology to be fitted
    :param limits_topology: VirtNUMALimitTopology that defines limits

    Given a host and instance topology and optionally limits - this method
    will attempt to fit instance cells onto all permutations of host cells
    by calling the _numa_fit_instance_cell method, and return a new
    InstanceNUMATopology with it's cell ids set to host cell id's of
    the first successful permutation, or None.
    """
    if (not (host_topology and instance_topology) or
        len(host_topology) < len(instance_topology)):
        return
    else:
        if limits_topology is None:
            limits_topology_cells = itertools.repeat(
                None, len(host_topology))
        else:
            limits_topology_cells = limits_topology.cells
        # TODO(ndipanov): We may want to sort permutations differently
        # depending on whether we want packing/spreading over NUMA nodes
        for host_cell_perm in itertools.permutations(
                zip(host_topology.cells, limits_topology_cells),
                len(instance_topology)
        ):
            cells = []
            for (host_cell, limit_cell), instance_cell in zip(
                    host_cell_perm, instance_topology.cells):
                got_cell = _numa_fit_instance_cell(
                    host_cell, instance_cell, limit_cell)
                if got_cell is None:
                    break
                cells.append(got_cell)
            if len(cells) == len(host_cell_perm):
                return objects.InstanceNUMATopology(cells=cells)

def _numa_pagesize_usage_from_cell(hostcell, instancecell, sign):
    topo = []
    for pages in hostcell.mempages:
        if pages.size_kb == instancecell.pagesize:
            topo.append(objects.NUMAPagesTopology(
                size_kb=pages.size_kb,
                total=pages.total,
                used=max(0, pages.used +
                         instancecell.memory * units.Ki /
                         pages.size_kb * sign)))
        else:
            topo.append(pages)
    return topo

def numa_usage_from_instances(host, instances, free=False):
    """Get host topology usage

    :param host: objects.NUMATopology with usage information
    :param instances: list of objects.InstanceNUMATopology
    :param free: If True usage of the host will be decreased

    Sum the usage from all @instances to report the overall
    host topology usage

    :returns: objects.NUMATopology including usage information
    """

    if host is None:
        return

    instances = instances or []
    cells = []
    sign = -1 if free else 1
    for hostcell in host.cells:
        memory_usage = hostcell.memory_usage
        cpu_usage = hostcell.cpu_usage
        mempages = hostcell.mempages
        for instance in instances:
            for instancecell in instance.cells:
                if instancecell.id == hostcell.id:
                    memory_usage = (
                            memory_usage + sign * instancecell.memory)
                    cpu_usage = cpu_usage + sign * len(instancecell.cpuset)
                    if instancecell.pagesize and instancecell.pagesize > 0:
                        mempages = _numa_pagesize_usage_from_cell(
                            hostcell, instancecell, sign)

        cell = objects.NUMACell(
            id=hostcell.id, cpuset=hostcell.cpuset, memory=hostcell.memory,
            cpu_usage=max(0, cpu_usage), memory_usage=max(0, memory_usage),
            mempages=mempages)

        cells.append(cell)

    return objects.NUMATopology(cells=cells)

# TODO(ndipanov): Remove when all code paths are using objects
def instance_topology_from_instance(instance):
    """Convenience method for getting the numa_topology out of instances

    Since we may get an Instance as either a dict, a db object, or an actual
    Instance object, this makes sure we get beck either None, or an instance
    of objects.InstanceNUMATopology class.
    """
    if isinstance(instance, objects.Instance):
        # NOTE (ndipanov): This may cause a lazy-load of the attribute
        instance_numa_topology = instance.numa_topology
    else:
        if 'numa_topology' in instance:
            instance_numa_topology = instance['numa_topology']
        elif 'uuid' in instance:
            try:
                instance_numa_topology = (
                    objects.InstanceNUMATopology.get_by_instance_uuid(
                            context.get_admin_context(), instance['uuid'])
                    )
            except exception.NumaTopologyNotFound:
                instance_numa_topology = None
        else:
            instance_numa_topology = None

    if instance_numa_topology:
        if isinstance(instance_numa_topology, six.string_types):
            instance_numa_topology = (
                objects.InstanceNUMATopology.obj_from_primitive(
                    jsonutils.loads(instance_numa_topology)))

        elif isinstance(instance_numa_topology, dict):
            # NOTE (ndipanov): A horrible hack so that we can use
            # this in the scheduler, since the
            # InstanceNUMATopology object is serialized raw using
            # the obj_base.obj_to_primitive, (which is buggy and
            # will give us a dict with a list of InstanceNUMACell
            # objects), and then passed to jsonutils.to_primitive,
            # which will make a dict out of those objects. All of
            # this is done by scheduler.utils.build_request_spec
            # called in the conductor.
            #
            # Remove when request_spec is a proper object itself!
            dict_cells = instance_numa_topology.get('cells')
            if dict_cells:
                cells = [objects.InstanceNUMACell(
                    id=cell['id'],
                    cpuset=set(cell['cpuset']),
                    memory=cell['memory'],
                    pagesize=cell.get('pagesize'))
                         for cell in dict_cells]
                instance_numa_topology = objects.InstanceNUMATopology(
                    cells=cells)

    return instance_numa_topology

# TODO(ndipanov): Remove when all code paths are using objects
def host_topology_and_format_from_host(host):
    """Convenience method for getting the numa_topology out of hosts

    Since we may get a host as either a dict, a db object, or an actual
    ComputeNode object, or an instance of HostState class, this makes sure we
    get beck either None, or an instance of objects.NUMATopology class.

    :returns: A two-tuple, first element is the topology itself or None, second
              is a boolean set to True if topology was in json format.
    """
    was_json = False
    try:
        host_numa_topology = host.get('numa_topology')
    except AttributeError:
        host_numa_topology = host.numa_topology

    if host_numa_topology is not None and isinstance(
            host_numa_topology, six.string_types):
        was_json = True

        host_numa_topology = (objects.NUMATopology.obj_from_db_obj(
            host_numa_topology))

    return host_numa_topology, was_json

# TODO(ndipanov): Remove when all code paths are using objects
def get_host_numa_usage_from_instance(host, instance, free=False,
                                     never_serialize_result=False):
    """Calculate new 'numa_usage' of 'host' from 'instance' NUMA usage

    This is a convenience method to help us handle the fact that we use several
    different types throughout the code (ComputeNode and Instance objects,
    dicts, scheduler HostState) which may have both json and deserialized
    versions of VirtNUMATopology classes.

    Handles all the complexity without polluting the class method with it.

    :param host: nova.objects.ComputeNode instance, or a db object or dict
    :param instance: nova.objects.Instance instance, or a db object or dict
    :param free: if True the the returned topology will have it's usage
                 decreased instead.
    :param never_serialize_result: if True result will always be an instance of
                                   objects.NUMATopology class.

    :returns: numa_usage in the format it was on the host or
              objects.NUMATopology instance if never_serialize_result was True
    """
    instance_numa_topology = instance_topology_from_instance(instance)
    if instance_numa_topology:
        instance_numa_topology = [instance_numa_topology]

    host_numa_topology, jsonify_result = host_topology_and_format_from_host(
            host)

    updated_numa_topology = (
        numa_usage_from_instances(
            host_numa_topology, instance_numa_topology, free=free))

    if updated_numa_topology is not None:
        if jsonify_result and not never_serialize_result:
            updated_numa_topology = updated_numa_topology._to_json()

    return updated_numa_topology


text:
@interface AGBoxBCell : UICollectionViewCell

@end


text:
layout: pattern
title: Spatial Partition
folder: spatial-partition
permalink: /patterns/spatial-partition/
categories: Behavioral
tags:
 - Performance
 - Game programming
---

## Intent
As explained in the book [Game Programming Patterns](http://gameprogrammingpatterns.com/spatial-partition.html) by Bob Nystrom, spatial partition pattern helps to

> efficiently locate objects by storing them in a data structure organized by their positions.

## Explanation
Say, you are building a war game with hundreds, or maybe even thousands of players, who are clashing on the battle field. Each player's position is getting updated every frame. The simple way to handle all interactions taking place on the field is to check each player's position against every other player's position:

```java
public void handleMeLee(Unit units[], int numUnits) {
  for (var a = 0; a < numUnits - 1; a++)
  {
    for (var b = a + 1; b < numUnits; b++)
    {
      if (units[a].position() == units[b].position())
      {
        handleAttack(units[a], units[b]);
      }
    }
  }
}
```

This will include a lot of unnecessary checks between players which are too far apart to have any influence on each other. The nested loops gives this operation an O(n^2) complexity, which has to be performed every frame since many of the objects on the field may be moving each frame.
The idea behind the Spatial Partition design pattern is to enable quick location of objects using a data structure that is organised by their positions, so when performing an operation like the one above, every object's position need not be checked against all other objects' positions. The data structure can be used to store moving and static objects, though in order to keep track of the moving objects, their positions will have to be reset each time they move. This would mean having to create a new instance of the data structure each time an object moves, which would use up additional memory. The common data structures used for this design pattern are:

* Grid
* Quad tree
* k-d tree
* BSP
* Boundary volume hierarchy

In our implementation, we use the Quadtree data structure which will reduce the time complexity of finding the objects within a certain range from O(n^2) to O(nlogn), decreasing the computations required significantly in case of large number of objects.

## Class diagram
![alt text](./etc/spatial-partition.urm.png "Spatial Partition pattern class diagram")

## Applicability
This pattern can be used:

* When you need to keep track of a large number of objects' positions, which are getting updated every frame.
* When it is acceptable to trade memory for speed, since creating and updating data structure will use up extra memory.

## Credits

* [Game Programming Patterns/Spatial Partition](http://gameprogrammingpatterns.com/spatial-partition.html) by Bob Nystrom
* [Quadtree tutorial](https://www.youtube.com/watch?v=OJxEcs0w_kE) by Daniel Schiffman


text:
      subroutine   newrap(
     i                    est,tlrnce,
     m                    func,newval)
c
c     + + + PURPOSE + + +
c     This subroutine uses the Newton-Raphson method to determine
c     'newval' using func (the function subprogram specified in the
c     calling statement).
c
c     Called from FURADV and FURREC
c     Author(s): E. R. Kottwitz
c     Reference in User Guide: Chapter 12
c
c     Changes:
c
c     Version: This module recoded from WEPP Version 93.06.
c     Date recoded: 07/07/93.
c     Recoded by: Charles R. Meyer.
c
c
c     + + + ARGUMENT DECLARATIONS + + +
      real      est,func,newval,tlrnce
c
c     + + + ARGUMENT DEFINITIONS + + +
c     est    - estimate of function's root coming in
c     func   - external function subprogram to be used
c     newval - function's root returned to calling subprogram
c     tlrnce - tolerance value for Newton-Raphson iterations with units
c              that are the same as the function's root
c
c     + + + LOCAL VARIABLES + + +
      integer   countr
      real      oldval
c
c     + + + LOCAL DEFINITIONS + + +
c     countr - counter of iterations used for non-convergence
c     oldval - old estimate of function's root
c
c     + + + OUTPUT FORMATS + + +
 2010 format(' SR NEWRAP did not converge in 100 iterations.  Model'/
     1       ' will continue with best estimate of parameter value.'/)
c
c     + + + END SPECIFICATIONS + + +
c
c     Initialize variables
c
      oldval = est
      countr = 1
c
c     Iteration loop
c
   20 newval = oldval-func(oldval)
      if(abs(newval-oldval).gt.tlrnce)then
        if(countr.lt.100)then
          oldval = newval
          countr = countr+1
          goto 20
        else
          write (6,2010)
        endif
      endif
c
      return
      end


text:
using System;
using System.Collections.Generic;
using System.Collections.ObjectModel;
using System.Linq;
using System.Text;
using System.Threading.Tasks;
using Livet;
using Grabacr07.KanColleWrapper.Models;

namespace BattleInfoPlugin.Models
{
    public class FleetData : NotificationObject
    {
        #region FleetType変更通知プロパティ
        private FleetType _FleetType;

        public FleetType FleetType
        {
            get
            { return this._FleetType; }
            set
            {
                if (this._FleetType == value)
                    return;
                this._FleetType = value;
                this.RaisePropertyChanged();
            }
        }
        #endregion

        #region Name変更通知プロパティ
        private string _Name;

        public string Name
        {
            get
            { return this._Name; }
            set
            {
                if (this._Name == value)
                    return;
                this._Name = value;
                this.RaisePropertyChanged();
            }
        }
        #endregion

        #region Ships変更通知プロパティ
        private IEnumerable<ShipData> _Ships;

        public IEnumerable<ShipData> Ships
        {
            get
            { return this._Ships; }
            set
            {
                if (this._Ships == value)
                    return;
                this._Ships = value;
                this.RaisePropertyChanged();
            }
        }
        #endregion

        #region Formation変更通知プロパティ
        private Formation _Formation;

        public Formation Formation
        {
            get
            { return this._Formation; }
            set
            {
                if (this._Formation == value)
                    return;
                this._Formation = value;
                this.RaisePropertyChanged();
            }
        }
        #endregion

        #region Rank変更通知プロパティ
        private int[] _Rank;

        public int[] Rank
        {
            get
            { return this._Rank; }
            set
            {
                if (this._Rank == value)
                    return;
                this._Rank = value;
                this.RaisePropertyChanged();
            }
        }
        #endregion

        //#region AirSuperiorityPotential変更通知プロパティ
        //private int _AirSuperiorityPotential;

        //public int AirSuperiorityPotential
        //{
        //    get
        //    { return this._AirSuperiorityPotential; }
        //    set
        //    {
        //        if (this._AirSuperiorityPotential == value)
        //            return;
        //        this._AirSuperiorityPotential = value;
        //        this.RaisePropertyChanged();
        //    }
        //}
        //#endregion

        //public int AirParityRequirements => this.AirSuperiorityPotential * 2 / 3;
        //public int AirSuperiorityRequirements => this.AirSuperiorityPotential * 3 / 2;
        //public int AirSupremacyRequirements => this.AirSuperiorityPotential * 3;

        public FleetData() : this(new ShipData[0], Formation.なし, "", FleetType.Enemy)
        {
        }

        public FleetData(IEnumerable<ShipData> ships, Formation formation, string name, FleetType type, int[] rank = null)
        {
            this._Ships = ships;
            this._Formation = formation;
            this._Name = name;
            this._FleetType = type;
            this._Rank = rank ?? new[] { 0 };
            //this._AirSuperiorityPotential = this._Ships
            //    .SelectMany(s => s.Slots)
            //    .Where(s => s.Source.IsAirSuperiorityFighter)
            //    .Sum(s => (int)(s.AA * Math.Sqrt(s.Current)))
            //    ;
        }
    }

    public static class FleetDataExtensions
    {
        /// <summary>
        /// Actionを使用して値を設定
        /// Zipするので要素数が少ない方に合わせられる
        /// </summary>
        /// <typeparam name="TSource"></typeparam>
        /// <typeparam name="TValue"></typeparam>
        /// <param name="source"></param>
        /// <param name="values"></param>
        /// <param name="setter"></param>
        public static void SetValues<TSource, TValue>(
            this IEnumerable<TSource> source,
            IEnumerable<TValue> values,
            Action<TSource, TValue> setter)
        {
            source.Zip(values, (s, v) => new { s, v })
                .ToList()
                .ForEach(x => setter(x.s, x.v));
        }

        /// <summary>
        /// ダメージ適用
        /// </summary>
        /// <param name="fleet">艦隊</param>
        /// <param name="damages">適用ダメージリスト</param>
        public static void CalcDamages(this FleetData fleet, params FleetDamages[] damages)
        {
            foreach (var damage in damages)
            {
                fleet.Ships.SetValues(damage.ToArray(), (s, d) => s.NowHP -= d);

                // ダメコンによる回復処理。同一戦闘で2度目が発生する事はないという前提……
                // ダメコン優先度: 拡張スロット>インデックス順
                var dameconState = fleet.Ships.Select(x => new { HasDamecon = x.HasDamecon(), HasMegami = x.HasMegami() });
                fleet.Ships.SetValues(dameconState, (s, d) =>
                {
                    if (0 < s.NowHP) return;
                    s.IsUsedDamecon = d.HasDamecon || d.HasMegami;
                    if (d.HasDamecon)
                        s.NowHP = (int)Math.Floor(s.MaxHP * 0.2);
                    else if (d.HasMegami)
                        s.NowHP = s.MaxHP;
                });
            }
        }

        /// <summary>
        /// 演習ダメージ適用
        /// </summary>
        /// <param name="fleet">艦隊</param>
        /// <param name="damages">適用ダメージリスト</param>
        public static void CalcPracticeDamages(this FleetData fleet, params FleetDamages[] damages)
        {
            foreach (var damage in damages)
            {
                fleet.Ships.SetValues(damage.ToArray(), (s, d) => s.NowHP -= d);
            }
        }

        private static bool HasDamecon(this ShipData ship)
        {
            return ship?.ExSlot?.Source?.Id == 42
                || ship?.FirstDameconOrNull()?.Source?.Id == 42;
        }

        private static bool HasMegami(this ShipData ship)
        {
            return ship?.ExSlot?.Source?.Id == 43
                || ship?.FirstDameconOrNull()?.Source?.Id == 43;
        }

        private static ShipSlotData FirstDameconOrNull(this ShipData ship)
        {
            return ship?.Slots?.FirstOrDefault(x => x?.Source?.Id == 42 || x?.Source?.Id == 43);
        }
    }
}


text:
using System.Reflection;
using System.Runtime.InteropServices;
[assembly: AssemblyTitle("PPWCode.Vernacular.Wcf.I")]
[assembly: AssemblyDescription("Main code of the PPWCode Vernacular Wcf")]
[assembly: AssemblyConfiguration("")]
[assembly: ComVisible(false)]
[assembly: Guid("eca4b107-668e-4a71-9912-f94b2e62edab")]


text:
#include "mmal.h"
#include "mmal_port_private.h"
#include "mmal_buffer.h"
#include "mmal_logging.h"

MMAL_EVENT_FORMAT_CHANGED_T *mmal_event_format_changed_get(MMAL_BUFFER_HEADER_T *buffer)
{
   MMAL_EVENT_FORMAT_CHANGED_T *event;
   MMAL_ES_FORMAT_T *format;
   uint32_t size;

   size = sizeof(MMAL_EVENT_FORMAT_CHANGED_T);
   size += sizeof(MMAL_ES_FORMAT_T) + sizeof(MMAL_ES_SPECIFIC_FORMAT_T);

   if (buffer->cmd != MMAL_EVENT_FORMAT_CHANGED || !buffer || buffer->length < size)
      return 0;

   event = (MMAL_EVENT_FORMAT_CHANGED_T *)buffer->data;
   format = event->format = (MMAL_ES_FORMAT_T *)&event[1];
   format->es = (MMAL_ES_SPECIFIC_FORMAT_T *)&format[1];
   format->extradata = (uint8_t *)&format->es[1];
   format->extradata_size = buffer->length - size;
   return event;
}

MMAL_STATUS_T mmal_event_error_send(MMAL_COMPONENT_T *component, MMAL_STATUS_T error_status)
{
   MMAL_BUFFER_HEADER_T* event;
   MMAL_STATUS_T status;

   if(!component)
   {
      LOG_ERROR("invalid component");
      return MMAL_EINVAL;
   }

   status = mmal_port_event_get(component->control, &event, MMAL_EVENT_ERROR);
   if (status != MMAL_SUCCESS)
   {
      LOG_ERROR("event not available for component %s %p, result %d", component->name, component, status);
      return status;
   }

   event->length = sizeof(MMAL_STATUS_T);
   *(MMAL_STATUS_T *)event->data = error_status;
   mmal_port_event_send(component->control, event);

   return MMAL_SUCCESS;
}


text:
package org.apache.taverna.monitor;

import java.util.Date;
import java.util.Set;

/**
 * A single node in the Monitor tree, containing an optional arbitrary workflow
 * object and a set of properties which may or may not be mutable. For tree
 * traversal operations the top level monitor tree must be used, instances of
 * this class are not aware of the surrounding tree structure.
 *
 * @author Tom Oinn
 */
public interface MonitorNode {
	/**
	 * Each monitor node can reference zero or one workflow object. This is the
	 * object which is providing any properties the node exposes, so is likely
	 * to be a workflow or processor but could be anything.
	 *
	 * @return the workflow object providing this node's properties, or null if
	 *         there is no directly corresponding workflow object. Note that
	 *         this workflow object can be anything, and may not be a top level
	 *         workflow object at all.
	 */
	Object getWorkflowObject();

	/**
	 * Each monitor node has an identity corresponding to the identifier stack
	 * of the data flowing through the workflow object that created it. This
	 * string array also defines its position in the monitor tree.
	 */
	String[] getOwningProcess();

	/**
	 * Each monitor node exposes a set of properties, which may or may not be
	 * mutable
	 */
	Set<? extends MonitorableProperty<?>> getProperties();

	/**
	 * Each node has a creation date
	 */
	Date getCreationDate();

	/**
	 * Properties can be added to the monitor node after creation if required,
	 * although this should be used only when necessary to avoid race conditions
	 */
	void addMonitorableProperty(MonitorableProperty<?> newProperty);

	/**
	 * Nodes can persist in the tree after they have expired, in which case this
	 * will return true.
	 */
	boolean hasExpired();
}


text:
<?php

$lang['button_local_upload'] = 'Yerel';
$lang['button_remote_upload'] = 'Uzaktan';
$lang['button_upload_preferences'] = 'Yükleme Tercihleri';
$lang['button_select_files'] = 'DOSYALARI SEÇ';
$lang['button_upload'] = 'Yükle';
$lang['txt_create_short_url'] = 'Kısa URL yaratmak için şunu kullan';
$lang['txt_local_upload'] = 'bilgisayarınızdan yüklemek istediğiniz resimleri seçin';
$lang['txt_remote_upload'] = 'yüklemek istediğiniz resmin URL\'sini girin';
$lang['txt_resizing'] = 'resim boyutunu ayarla';
$lang['txt_resizing_explained'] = 'resminizi otomatik olarak boyutlandırın';
$lang['txt_resizing_width'] = 'Arzu edilen genişlik';
$lang['txt_resizing_pixels'] = 'piksel';
$lang['txt_resizing_keep'] = 'resmin boyutlarını koru';
$lang['txt_cancel'] = 'iptal';
$lang['txt_404_title'] = 'Bulunamadı (404)';
$lang['txt_404_explained'] = 'Sunucu istenilen sayfayı bulamadı.';
$lang['txt_just_uploaded'] = 'Henüz yüklendi';
$lang['txt_images'] = 'Resimler';
$lang['txt_viewing'] = 'Görüntüleniyor';
$lang['txt_socialize'] = 'Sosyal Paylaşım Sitesi Bağlantıları';
$lang['txt_socialize_desc'] = 'Paylaşmak Güzeldir!';
$lang['txt_socialize_label'] = 'Sosyal Ağlar';
$lang['txt_show_viewer_link'] = 'Görüntüleyici';
$lang['txt_show_directly'] = 'Doğrudan Bağlantılar';
$lang['txt_show_directly_desc'] = 'eposta ve mesaj için uygun';
$lang['txt_show_directly_link'] = 'Doğrudan bağlantı';
$lang['txt_show_directly_shorturl'] = 'Kısa URL';
$lang['txt_show_directly_html'] = 'Resim HTML\'i';
$lang['txt_thumb_plus_link'] = 'Küçük resim + bağlantı';
$lang['txt_thumb_plus_link_desc'] = 'Bu resmi küçük resmi ile beraber sitenize ekleyin ya da gönderin';
$lang['txt_thumb_plus_link_html'] = 'HTML';
$lang['txt_thumb_plus_link_bbcode'] = 'BBCode';
$lang['txt_multicodes_directlink'] = 'Doğrudan bağlantılar';
$lang['txt_multicodes_html'] = 'HTML Kodları';
$lang['txt_multicodes_bbcode'] = 'BBKodları';
$lang['txt_multicodes_thumbs_html'] = 'Küçük Resim HTML Kodları';
$lang['txt_multicodes_thumbs_bbcode'] = 'Küçük Resim BBKodları';
$lang['txt_thumb_url'] = 'Küçük resim URL\'si';
$lang['doctitle_404'] = 'Bulunamadı (404)';
$lang['doctitle_viewing_image'] = 'Resim görüntüleniyor';
$lang['doctitle_upload_complete'] = 'Yükleme tamamlandı';
$lang['msg_cancel_upload'] = 'Yükleme işlemini gerçekten iptal etmek istiyor musunuz?';
$lang['error_empty_form'] = 'Devam edebilmek için resim seçmeli ya da bir bağlantı girmelisiniz.';
$lang['error_uploading'] = 'Yüklemede hata';
$lang['error_local_upload'] = 'Hiçbir resim yüklenmedi';
$lang['error_source'] = 'Geçersiz kaynak';
$lang['error_url'] = 'Geçersiz URL';
$lang['error_thumb_size'] = 'Geçersiz küçük resim büyüklüğü';
$lang['error_resize_sise'] = 'Geçersiz boyut değeri';
$lang['error_image_invalid'] = 'Geçersiz resim';
$lang['error_image_weight'] = 'Resim çok büyük';
$lang['critical_js'] = 'Bu sayfayı kullanabilmeniz için tarayıcınızda JavaScript yüklü olmalıdır.';
$lang['critical_js_step_1'] = 'Tarayıcınızda JavaScript\'i etkinleştirmek için bir web araması yapabilirsiniz';
$lang['critical_js_step_2'] = 'Eğer JavaScript halihazırda yüklüyse sayfayı yenilemeyi deneyin.';
$lang['txt_image'] = 'resim';
$lang['txt_enter_password'] = 'Şifrenizi Girin';
$lang['txt_keep_me_login'] = 'Beni Hatırla';
$lang['txt_homepage'] = 'Ana Sayfa';
$lang['txt_logout'] = 'Çıkış Yap';
$lang['txt_no_image_selection'] = 'Resim seçilmedi';
$lang['txt_current_selection'] = 'Mevcut seçilenler';
$lang['txt_image_selected'] = 'Seçilen resim';
$lang['txt_images_selected'] = 'seçilen resimler';
$lang['txt_images_total'] = 'toplam resim sayısı';
$lang['txt_reset_selection'] = 'seçimi sıfırla';
$lang['txt_select_all'] = 'tümünü seç';
$lang['txt_clear_selection'] = 'seçimi temizle';
$lang['button_clear'] = 'Temizle';
$lang['button_close'] = 'Kapat';
$lang['button_delete'] = 'Sil';
$lang['button_delete_selected'] = 'Seçilenleri Sil';
$lang['button_rename'] = 'Adını Değiştir';
$lang['button_rename_all'] = 'Tümünün Adını Değiştir';
$lang['button_resize'] = 'Yeniden Boyutlandır';
$lang['button_resize_all'] = 'Tümünü Yeniden Boyutlandır';
$lang['button_codes'] = 'Kodları Al';
$lang['txt_search_images'] = 'Resimleri Ara';
$lang['txt_all'] = 'tümü';
$lang['txt_loading'] = 'yükleniyor';
$lang['txt_delete_confirm_single'] = 'Resim geri dönüşü olmaksızın silinecektir.';
$lang['txt_delete_confirm_multi'] = 'Seçilen resimler geri dönüşümü olmaksızın kaldırılacaktır.';
$lang['txt_deleted_confirm_single'] = 'Resim kalıcı olarak silindi. Veritabanında artık bulunmuyor.';
$lang['txt_deleted_confirm_multi'] = 'Resimler kalıcı bir biçimde silindi, veritabanında artık bulunmuyorlar.';
$lang['txt_name_changed'] = 'Adı değiştirildi';
$lang['error_name_taken'] = 'Adı sistemde mevcut';
$lang['txt_resized'] = 'Yeniden Boyutlandırıldı';
$lang['txt_type'] = 'Türü';
$lang['txt_sort_by'] = 'Şuna göre sırala';
$lang['txt_newest'] = 'En Yeni';
$lang['txt_oldest'] = 'En Eski';
$lang['txt_filesize_small'] = 'Dosya Boyutu (küçük)';
$lang['txt_filesize_large'] = 'Dosya Boyutu (büyük)';
$lang['doctitle_delete_confirm'] = '';
$lang['txt_image_deleted'] = '';
$lang['txt_error_deleting_image'] = '';
$lang['txt_copy'] = '';

?>


text:
using System;
using System.Collections.Generic;
using System.Linq;
using System.Web;
using System.Web.Mvc;
using System.Web.UI.WebControls.Expressions;
using DevRainSolutions.KyivSmartCity.New.Models;
using DevRainSolutions.KyivSmartCity.New.Areas.Admin.Models;
using PagedList;

namespace DevRainSolutions.KyivSmartCity.New.Areas.Admin.Controllers
{
    public class DocumentsController : BaseAdminController
    {
		private readonly IGroupRepository groupRepository;
		private readonly IDocumentRepository documentRepository;

		// If you are using Dependency Injection, you can delete the following constructor
        public DocumentsController() : this(new GroupRepository(), new DocumentRepository())
        {
        }

        public DocumentsController(IGroupRepository groupRepository, IDocumentRepository documentRepository)
        {
			this.groupRepository = groupRepository;
			this.documentRepository = documentRepository;
        }

        //
        // GET: /Documents/

        public ViewResult Index(int? page)
        {
            var pageNumber = page ?? 1;
            return View(documentRepository.AllIncluding(document => document.Group)
                .OrderBy(i=>i.Title)
                .ToPagedList(pageNumber, 10));
        }

        //
        // GET: /Documents/Details/5

        public ViewResult Details(int id)
        {
            return View(documentRepository.Find(id));
        }

        //
        // GET: /Documents/Create

        public ActionResult Create()
        {
			ViewBag.PossibleGroups = groupRepository.All;
            return View();
        }

        //
        // POST: /Documents/Create

        [HttpPost]
        public ActionResult Create(Document document)
        {
            if (ModelState.IsValid) {
                documentRepository.InsertOrUpdate(document);
                documentRepository.Save();
                return RedirectToAction("Index");
            } else {
				ViewBag.PossibleGroups = groupRepository.All;
				return View();
			}
        }

        //
        // GET: /Documents/Edit/5

        public ActionResult Edit(int id)
        {
			ViewBag.PossibleGroups = groupRepository.All;
             return View(documentRepository.Find(id));
        }

        //
        // POST: /Documents/Edit/5

        [HttpPost]
        public ActionResult Edit(Document document)
        {
            if (ModelState.IsValid) {
                documentRepository.InsertOrUpdate(document);
                documentRepository.Save();
                return RedirectToAction("Index");
            } else {
				ViewBag.PossibleGroups = groupRepository.All;
				return View();
			}
        }

        //
        // GET: /Documents/Delete/5

        public ActionResult Delete(int id)
        {
            return View(documentRepository.Find(id));
        }

        //
        // POST: /Documents/Delete/5

        [HttpPost, ActionName("Delete")]
        public ActionResult DeleteConfirmed(int id)
        {
            documentRepository.Delete(id);
            documentRepository.Save();

            return RedirectToAction("Index");
        }

        protected override void Dispose(bool disposing)
        {
            if (disposing) {
                groupRepository.Dispose();
                documentRepository.Dispose();
            }
            base.Dispose(disposing);
        }
    }
}


text:
cd "$(dirname "$0")"

for cmd in rhino "rhino -require" narwhal ringo phantomjs node; do
  echo "Testing in $cmd..."
  $cmd test.js
  echo ""
done

echo "Testing in a browser..."
open index.html


text:
//
//  AEFClient_Private.h
//  OctoCrash
//
//  Created by Alex Fish on 1/15/14.
//  Copyright (c) 2014 alexefish. All rights reserved.
//

#import "AEFClient.h"

@class OCTClient;

static NSString * const kAEFGithubBaseURL = @"https://github.com/";

/**
 *  AEFClient's private method declarations, shhh.
 */
@interface AEFClient ()

/**
 Protocol properties
 */
@property (nonatomic, copy) NSString *repo;
@property (nonatomic, copy) NSString *clientID;
@property (nonatomic, copy) NSString *clientSecret;

/**
 Callback block fired when the client has authenticated
 */
@property (nonatomic, copy) void (^authenticated)(OCTClient *client);

/**
 *  Send a request to Github via an authentivated OCTIstance.
 *
 *  @param client         An authenticaed OCTClient instance, this method will fail
 *                        if the client isn't previously authenticated.
 *  @param path           The path to request relative to the base API URL
 *  @param method         The HTTP method to use
 *  @param paramaters     A dictionary of paramaters to send with the request
 *  @param completedBlock A completion block containing the response
 *  @param errorBlock     A completion block containing any errors
 */
- (void)requestWithClient:(OCTClient *)client
                     path:(NSString *)path
                   method:(NSString *)method
               parameters:(NSDictionary *)paramaters
                completed:(void (^)(id response))completedBlock
                    error:(void (^)(NSError *error))errorBlock;

/**
 *  Authenticate with a login, password and one time password, it is possible to pass
 *  nil for the one time password as it is optional.
 *
 *  @param login           The users Github login
 *  @param password        The users Github password
 *  @param oneTimePassword The users Github One Time Password (Optional)
 */
- (void)authenticateLogin:(NSString *)login
                 password:(NSString *)password
          oneTimePassword:(NSString *)oneTimePassword;

/**
 *  Handles any NSError object  in an elegant manor, this can be
 *  UI feedback to the user or another attempt at authenticating
 *  with a different authentication method.
 *
 *  @param error The error to handle gracefully
 */
- (void)handleError:(NSError *)error;

/**
 *  The API path for Github issues
 *
 *  @return The API path ready to use with OCTClient requests for issues
 */
- (NSString *)issuesPath;

/**
 *  Convert a report's URL to a Github API ready comments path, this will use elements
 *  of the reports existing path to generate an API URL for adding comments to the report
 *
 *  @param reportPath The report full github path to a github issue
 *  to generate a comments path with
 *
 *  @return A path for comments based on the report path.
 */
- (NSString *)commentsPathWithReportPath:(NSString *)reportPath;

@end


text:
using System;
using System.Collections.Concurrent;
using System.Collections.Generic;
using System.Linq;
using System.Threading.Tasks;

namespace StopGuessing.DataStructures
{
    /// <summary>
    /// An interface for classes that have an async method to call to start
    /// freeing the resources they are using.  This can be handy when a class
    /// needs to store data to a disk or over a network before it releases
    /// itself from memory.
    ///
    /// If implementing IAsyncDisposable and IDisposable, users should call _either_
    /// Dispose or DisposeAsync, not both.  This allows implementers to make the
    /// Dispose method simply call await DisposeAsync();
    /// </summary>
    public interface IAsyncDisposable
    {
        Task DisposeAsync();
    }

    //public interface IHasUniqueIdentityKeyString
    //{
    //    string UniqueIdentityKeyString { Get; }
    //}

    /// <summary>
    /// Implements a cache with a LRU (least-recently used)-like replacement policy.
    /// (Since the cache knows when objects were accessed from the cache -- when it wrote
    /// an item or retrieved it -- it treats these as uses.  It does not actually
    /// know when an object is used after the access happens.)
    ///
    /// This class implements IDicionary via inheritance.
    /// </summary>
    /// <typeparam name="TKey">The type of key used to access items in the cache.</typeparam>
    /// <typeparam name="TValue">The value type of values stored in the cache.</typeparam>
    public class Cache<TKey, TValue> : DictionaryThatTracksAccessRecency<TKey, TValue>
    {
        public virtual TValue ConstructDefaultValueForMissingCacheEntry(TKey key)
        {
            return default(TValue);
        }

        /// <summary>
        /// Requests the removal of items from the cache to free up space, removing the
        /// least-recently accessed items first.
        /// </summary>
        /// <param name="numberOfItemsToRemove">The number of items to remove.</param>
        public void RecoverSpace(int numberOfItemsToRemove)
        {
            // Remove the least-recently-accessed values from the cache
            KeyValuePair<TKey, TValue>[] entriesToRemove = RemoveAndGetLeastRecentlyAccessed(numberOfItemsToRemove).ToArray();

            ConcurrentBag<Task> asyncDisposalTasks = new ConcurrentBag<Task>();

            // Call the disposal method on each class.
            Parallel.For(0, entriesToRemove.Length, (counter, loop) =>
            {
                KeyValuePair<TKey, TValue> entryToRemove = entriesToRemove[counter];
                TValue valueToRemove = entryToRemove.Value;

                // ReSharper disable once CanBeReplacedWithTryCastAndCheckForNull
                if (valueToRemove is IAsyncDisposable)
                {
                    asyncDisposalTasks.Add(((IAsyncDisposable)valueToRemove).DisposeAsync());
                }
                else if (valueToRemove is IDisposable)
                {
                    ((IDisposable)valueToRemove).Dispose();
                }

                // Remove the last reference to the value so that it can be garbage collected immediately.
                entriesToRemove[counter] = default(KeyValuePair<TKey, TValue>);
            });

            Task.WaitAll(asyncDisposalTasks.ToArray());
        }

        /// <summary>
        /// Requests the removal of items from the cache to free up space, removing the
        /// least-recently accessed items first.
        /// </summary>
        /// <param name="fractionOfItemsToRemove">The fraction of items to remove.</param>
        public void RecoverSpace(double fractionOfItemsToRemove)
        {
            // Calculate the number ot items to remove as a fraction of the total number of items in the cache
            int numberOfItemsToRemove = (int)(Count * fractionOfItemsToRemove);
            // Remove that many
            RecoverSpace(numberOfItemsToRemove);
        }
    }

}


text:
case $OS_NAME in
  Linux )
    export PATH="$HOME/.config/composer/vendor/bin:$PATH"
    ;;
  Darwin )
    export PATH="$HOME/.composer/vendor/bin:$PATH"
    ;;
esac


text:
/* global lib, XMLHttpRequest */

'use strict'

const utils = require('../utils')
const logger = require('../logger')

require('httpurl')

let jsonpCnt = 0
const ERROR_STATE = -1

const TYPE_JSON = 'application/json;charset=UTF-8'
const TYPE_FORM = 'application/x-www-form-urlencoded'

const REG_FORM = /^(?:[^&=]+=[^&=]+)(?:&[^&=]+=[^&=]+)*$/

function _jsonp (config, callback, progressCallback) {
  const cbName = 'jsonp_' + (++jsonpCnt)
  let url

  if (!config.url) {
    logger.error('config.url should be set in _jsonp for \'fetch\' API.')
  }

  global[cbName] = (function (cb) {
    return function (response) {
      callback(response)
      delete global[cb]
    }
  })(cbName)

  const script = document.createElement('script')
  try {
    url = lib.httpurl(config.url)
  }
  catch (err) {
    logger.error('invalid config.url in _jsonp for \'fetch\' API: '
      + config.url)
  }
  url.params.callback = cbName
  script.type = 'text/javascript'
  script.src = url.toString()
  // script.onerror is not working on IE or safari.
  // but they are not considered here.
  script.onerror = (function (cb) {
    return function (err) {
      logger.error('unexpected error in _jsonp for \'fetch\' API', err)
      callback(err)
      delete global[cb]
    }
  })(cbName)
  const head = document.getElementsByTagName('head')[0]
  head.insertBefore(script, null)
}

function _xhr (config, callback, progressCallback) {
  const xhr = new XMLHttpRequest()
  xhr.responseType = config.type
  xhr.open(config.method, config.url, true)

  const headers = config.headers || {}
  for (const k in headers) {
    xhr.setRequestHeader(k, headers[k])
  }

  xhr.onload = function (res) {
    callback({
      status: xhr.status,
      ok: xhr.status >= 200 && xhr.status < 300,
      statusText: xhr.statusText,
      data: xhr.response,
      headers: xhr.getAllResponseHeaders().split('\n')
        .reduce(function (obj, headerStr) {
          const headerArr = headerStr.match(/(.+): (.+)/)
          if (headerArr) {
            obj[headerArr[1]] = headerArr[2]
          }
          return obj
        }, {})
    })
  }

  if (progressCallback) {
    xhr.onprogress = function (e) {
      progressCallback({
        readyState: xhr.readyState,
        status: xhr.status,
        length: e.loaded,
        total: e.total,
        statusText: xhr.statusText,
        headers: xhr.getAllResponseHeaders().split('\n')
          .reduce(function (obj, headerStr) {
            const headerArr = headerStr.match(/(.+): (.+)/)
            if (headerArr) {
              obj[headerArr[1]] = headerArr[2]
            }
            return obj
          }, {})
      })
    }
  }

  xhr.onerror = function (err) {
    logger.error('unexpected error in _xhr for \'fetch\' API', err)
    callback({
      status: ERROR_STATE,
      ok: false,
      statusText: '',
      data: '',
      headers: {}
    })
  }

  xhr.send(config.body)
}

const stream = {

  /**
   * sendHttp
   * @deprecated
   * Note: This API is deprecated. Please use stream.fetch instead.
   * send a http request through XHR.
   * @param  {obj} params
   *  - method: 'GET' | 'POST' | 'PUT' | 'DELETE' | 'HEAD' | 'PATCH',
   *  - url: url requested
   * @param  {string} callbackId
   */
  sendHttp: function (param, callbackId) {
    if (typeof param === 'string') {
      try {
        param = JSON.parse(param)
      }
      catch (e) {
        return
      }
    }
    if (typeof param !== 'object' || !param.url) {
      return logger.error(
        'invalid config or invalid config.url for sendHttp API')
    }

    const sender = this.sender
    const method = param.method || 'GET'
    const xhr = new XMLHttpRequest()
    xhr.open(method, param.url, true)
    xhr.onload = function () {
      sender.performCallback(callbackId, this.responseText)
    }
    xhr.onerror = function (error) {
      return logger.error('unexpected error in sendHttp API', error)
      // sender.performCallback(
      //   callbackId,
      //   new Error('unexpected error in sendHttp API')
      // )
    }
    xhr.send()
  },

  /**
   * fetch
   * use stream.fetch to request for a json file, a plain text file or
   * a arraybuffer for a file stream. (You can use Blob and FileReader
   * API implemented by most modern browsers to read a arraybuffer.)
   * @param  {object} options config options
   *   - method: 'GET' | 'POST' | 'PUT' | 'DELETE' | 'HEAD' | 'PATCH'
   *   - headers {obj}
   *   - url {string}
   *   - mode {string} 'cors' | 'no-cors' | 'same-origin' | 'navigate'
   *   - body
   *   - type {string} 'json' | 'jsonp' | 'text'
   * @param  {string} callbackId
   * @param  {string} progressCallbackId
   */
  fetch: function (options, callbackId, progressCallbackId) {
    const DEFAULT_METHOD = 'GET'
    const DEFAULT_MODE = 'cors'
    const DEFAULT_TYPE = 'text'

    const methodOptions = ['GET', 'POST', 'PUT', 'DELETE', 'HEAD', 'PATCH']
    const modeOptions = ['cors', 'no-cors', 'same-origin', 'navigate']
    const typeOptions = ['text', 'json', 'jsonp', 'arraybuffer']

    // const fallback = false  // fallback from 'fetch' API to XHR.
    const sender = this.sender

    const config = utils.extend({}, options)

    // validate options.method
    if (typeof config.method === 'undefined') {
      config.method = DEFAULT_METHOD
      logger.warn('options.method for \'fetch\' API has been set to '
        + 'default value \'' + config.method + '\'')
    }
    else if (methodOptions.indexOf((config.method + '')
        .toUpperCase()) === -1) {
      return logger.error('options.method \''
        + config.method
        + '\' for \'fetch\' API should be one of '
        + methodOptions + '.')
    }

    // validate options.url
    if (!config.url) {
      return logger.error('options.url should be set for \'fetch\' API.')
    }

    // validate options.mode
    if (typeof config.mode === 'undefined') {
      config.mode = DEFAULT_MODE
    }
    else if (modeOptions.indexOf((config.mode + '').toLowerCase()) === -1) {
      return logger.error('options.mode \''
        + config.mode
        + '\' for \'fetch\' API should be one of '
        + modeOptions + '.')
    }

    // validate options.type
    if (typeof config.type === 'undefined') {
      config.type = DEFAULT_TYPE
      logger.warn('options.type for \'fetch\' API has been set to '
        + 'default value \'' + config.type + '\'.')
    }
    else if (typeOptions.indexOf((config.type + '').toLowerCase()) === -1) {
      return logger.error('options.type \''
          + config.type
          + '\' for \'fetch\' API should be one of '
          + typeOptions + '.')
    }

    // validate options.headers
    config.headers = config.headers || {}
    if (!utils.isPlainObject(config.headers)) {
      return logger.error('options.headers should be a plain object')
    }

    // validate options.body
    const body = config.body
    if (!config.headers['Content-Type'] && body) {
      if (utils.isPlainObject(body)) {
        // is a json data
        try {
          config.body = JSON.stringify(body)
          config.headers['Content-Type'] = TYPE_JSON
        }
        catch (e) {}
      }
      else if (utils.getType(body) === 'string' && body.match(REG_FORM)) {
        // is form-data
        config.body = encodeURI(body)
        config.headers['Content-Type'] = TYPE_FORM
      }
    }

    // validate options.timeout
    config.timeout = parseInt(config.timeout, 10) || 2500

    const _callArgs = [config, function (res) {
      sender.performCallback(callbackId, res)
    }]
    if (progressCallbackId) {
      _callArgs.push(function (res) {
        // Set 'keepAlive' to true for sending continuous callbacks
        sender.performCallback(progressCallbackId, res, true)
      })
    }

    if (config.type === 'jsonp') {
      _jsonp.apply(this, _callArgs)
    }
    else {
      _xhr.apply(this, _callArgs)
    }
  }

}

stream._meta = {
  stream: [{
    name: 'sendHttp',
    args: ['object', 'function']
  }, {
    name: 'fetch',
    args: ['object', 'function', 'function']
  }]
}

module.exports = stream


text:
<!DOCTYPE html>
<html lang="en">
<head>
  <base href="/" />
  <meta charset="utf-8">
  <meta name="viewport" content="width=device-width, initial-scale=1">
  <title>AwayWeGo</title>
  <link href="https://fonts.googleapis.com/css?family=Lato:300,300i,400,400i,700,700i|Montserrat:300,300i,400,400i,700,700i" rel="stylesheet">
  <link href="https://fonts.googleapis.com/icon?family=Material+Icons" rel="stylesheet">
  <link rel="stylesheet" href="https://maxcdn.bootstrapcdn.com/bootstrap/4.0.0-alpha.6/css/bootstrap.min.css" integrity="sha384-rwoIResjU2yc3z8GV/NPeZWAv56rSmLldC3R/AZzGRnGxQQKnKkoFVhFQhNUwEyJ" crossorigin="anonymous">
  <script src="https://code.jquery.com/jquery-3.1.1.slim.min.js" integrity="sha384-A7FZj7v+d/sdmMqp/nOQwliLvUsJfDHW+k9Omg/a/EheAdgtzNs3hpfag6Ed950n" crossorigin="anonymous"></script>
  <script src="https://cdnjs.cloudflare.com/ajax/libs/tether/1.4.0/js/tether.min.js" integrity="sha384-DztdAPBWPRXSA/3eYEEUWrWCy7G5KFbe8fFjk5JAIxUYHKkDx6Qin1DkWx51bBrb" crossorigin="anonymous"></script>
  <script src="https://maxcdn.bootstrapcdn.com/bootstrap/4.0.0-alpha.6/js/bootstrap.min.js" integrity="sha384-vBWWzlZJ8ea9aCX4pEW3rVHjgjt7zpkNpZk+02D9phzyeVkE+jo0ieGizqPLForn" crossorigin="anonymous"></script>
  <script src="//cdnjs.cloudflare.com/ajax/libs/moment.js/2.10.6/moment-with-locales.js"></script>
  <link href="//cdn.rawgit.com/indrimuska/angular-moment-picker/master/dist/angular-moment-picker.min.css" rel="stylesheet">

</head>
<body>
  <div class="h100" ng-app="app">
    <ui-view></ui-view>
  </div>
</body>
</html>


text:
package com.github.ambry.router;

import com.codahale.metrics.MetricRegistry;
import com.github.ambry.config.CryptoServiceConfig;
import com.github.ambry.config.VerifiableProperties;
import javax.crypto.spec.SecretKeySpec;

/**
 * {@link GCMCryptoServiceFactory} specific implementation of {@link CryptoServiceFactory}.
 * <p/>
 * Sets up all the supporting cast required for the operation of {@link GCMCryptoService} and returns a new instance on
 * {@link #getCryptoService()}.
 */
public class GCMCryptoServiceFactory implements CryptoServiceFactory<SecretKeySpec> {
  private final CryptoServiceConfig cryptoServiceConfig;

  /**
   * Instantiates {@link GCMCryptoServiceFactory}
   * @param verifiableProperties {@link VerifiableProperties} to load configs from
   * @param registry {@link MetricRegistry} to use
   */
  public GCMCryptoServiceFactory(VerifiableProperties verifiableProperties, MetricRegistry registry) {
    cryptoServiceConfig = new CryptoServiceConfig(verifiableProperties);
  }

  @Override
  public CryptoService<SecretKeySpec> getCryptoService() {
    return new GCMCryptoService(cryptoServiceConfig);
  }
}


text:
/*global WorldScholars _config*/

var WorldScholars = window.WorldScholars || {};
WorldScholars.map = WorldScholars.map || {};

(function profileScopeWrapper($) {
    var authToken;
    WorldScholars.authToken.then(function setAuthToken(token) {
        if (token) {
            authToken = token;
        } else {
            if (window.location.pathname != "/signin.html" &&
                window.location.pathname != "/signup.html" &&
                window.location.pathname != "/verify.html" &&
                window.location.origin != "file://"){
                window.location.href = '/signin.html';
            }
        }
    }).catch(function handleTokenError(error) {
        alert(error);
        window.location.href = '/signin.html';
    });

    function listExams() {

        $.ajax({
            method: 'GET',
            url: _config.api.invokeUrl + '/examlist',
            headers: {
                Authorization: authToken
            },
            contentType: 'application/json',
            success: listExamsInHtml,
            error: function ajaxError(jqXHR, textStatus, errorThrown) {
                console.error('Error reading exams from database: ', textStatus, ', Details: ', errorThrown);
                console.error('Response: ', jqXHR.responseText);
                alert('An error occured when reading your exam\n' + jqXHR.responseText);
            }
        });
    }

    function listExamsInHtml(allExams) {
        allExams.Exams.sort(function(a,b) {
          (new Date(a.submitTime)).getTime() - (new Date(b.submitTime)).getTime()
        });
        allExams.Exams.forEach(function(oneExam){
          //TODO hardcoding parsing of section and question, this should just be in the json object
          slash = "/";
          submitTime = readISODateString(oneExam.submitTime);
          newRow = ('
' + oneExam.ExamNumber + '<'+slash+'td>' + submitTime + '<'+slash+'td>'+
              ' Results<'+slash+''+'<'+slash+'td><'+slash+'tr>');
          $('tbody').append(newRow);
        });

    }

    $(function onDocReady() {
        //TODO figure out how to split this into multiple files
        if (window.location.pathname=="/profile.html"){
          var useremail = document.getElementById('username');
          listExams()
          useremail.innerHTML = WorldScholars.user.username;
        }

        // register handler for signout click
        $('#signOut').click(function() {
            WorldScholars.signOut();
            alert("You have been signed out.");
            window.location = "signin.html";
        });

    });

}(jQuery));


text:
"""

"""

import unittest

from neo.rawio.brainvisionrawio import BrainVisionRawIO

from neo.test.rawiotest.common_rawio_test import BaseTestRawIO

class TestBrainVisionRawIO(BaseTestRawIO, unittest.TestCase, ):
    rawioclass = BrainVisionRawIO
    entities_to_test = [
        'brainvision/File_brainvision_1.vhdr',
        'brainvision/File_brainvision_2.vhdr',
        'brainvision/File_brainvision_3_float32.vhdr',
        'brainvision/File_brainvision_3_int16.vhdr',
        'brainvision/File_brainvision_3_int32.vhdr',
    ]

    entities_to_download = [
        'brainvision'
    ]

if __name__ == "__main__":
    unittest.main()


text:
<?php
/*
* @Author: ydk2 (me@ydk2.tk)
* @Date: 2017-01-21 16:22:09
 * @Last Modified by: ydk2 (me@ydk2.tk)
 * @Last Modified time: 2017-01-21 22:00:35
*/
namespace Test\Controllers\Test;

class E extends \Library\Core\Controller
{
    public function __construct($model){
        parent::__construct();
        $this->ViewData('header',$model->header);
        $this->ViewData('message',$model->message);
    }
   // public function Run(){
        //$this->ViewData('testing', 'ddd');
       // Inc('test/views/test/view','.html');
    //}
}
?>