array.js.svn-base

Google浏览器V8内核代码

function ArrayReverse() {
  var j = ToUint32(this.length) - 1;

  if (UseSparseVariant(this, j, IS_ARRAY(this))) {
    SparseReverse(this, j+1);
    return this;
  }

  for (var i = 0; i < j; i++, j--) {
    var current_i = this[i];
    if (!IS_UNDEFINED(current_i) || i in this) {
      var current_j = this[j];
      if (!IS_UNDEFINED(current_j) || j in this) {
        this[i] = current_j;
        this[j] = current_i;
      } else {
        this[j] = current_i;
        delete this[i];
      }
    } else {
      var current_j = this[j];
      if (!IS_UNDEFINED(current_j) || j in this) {
        this[i] = current_j;
        delete this[j];
      }
    }
  }
  return this;
};


function ArrayShift() {
  var len = ToUint32(this.length);
  
  if (len === 0) {
    this.length = 0;
    return;
  }
  
  var first = this[0];
  
  if (IS_ARRAY(this))
    SmartMove(this, 0, 1, len, 0);
  else
    SimpleMove(this, 0, 1, len, 0);
  
  this.length = len - 1;
  
  return first;
};


function ArrayUnshift(arg1) {  // length == 1
  var len = ToUint32(this.length);
  var num_arguments = %_ArgumentsLength();
  
  if (IS_ARRAY(this))
    SmartMove(this, 0, 0, len, num_arguments);
  else
    SimpleMove(this, 0, 0, len, num_arguments);
  
  for (var i = 0; i < num_arguments; i++) {
    this[i] = %_Arguments(i);
  }
  
  this.length = len + num_arguments;
  
  return len + num_arguments;
};


function ArraySlice(start, end) {
  var len = ToUint32(this.length);
  var start_i = TO_INTEGER(start);
  var end_i = len;
  
  if (end !== void 0) end_i = TO_INTEGER(end);
  
  if (start_i < 0) {
    start_i += len;
    if (start_i < 0) start_i = 0;
  } else {
    if (start_i > len) start_i = len;
  }
  
  if (end_i < 0) {
    end_i += len;
    if (end_i < 0) end_i = 0;
  } else {
    if (end_i > len) end_i = len;
  }
  
  var result = [];
  
  if (end_i < start_i)
    return result;
  
  if (IS_ARRAY(this))
    SmartSlice(this, start_i, end_i - start_i, len, result);
  else 
    SimpleSlice(this, start_i, end_i - start_i, len, result);
  
  result.length = end_i - start_i;
  
  return result;
};


function ArraySplice(start, delete_count) {
  var num_arguments = %_ArgumentsLength();
  
  // SpiderMonkey and KJS return undefined in the case where no
  // arguments are given instead of using the implicit undefined
  // arguments.  This does not follow ECMA-262, but we do the same for
  // compatibility.
  if (num_arguments == 0) return;
  
  var len = ToUint32(this.length);
  var start_i = TO_INTEGER(start);
  
  if (start_i < 0) {
    start_i += len;
    if (start_i < 0) start_i = 0;
  } else {
    if (start_i > len) start_i = len;
  }
  
  // SpiderMonkey and KJS treat the case where no delete count is
  // given differently from when an undefined delete count is given.
  // This does not follow ECMA-262, but we do the same for
  // compatibility.
  var del_count = 0;
  if (num_arguments > 1) {
    del_count = TO_INTEGER(delete_count);
    if (del_count < 0) del_count = 0;
    if (del_count > len - start_i) del_count = len - start_i;
  } else {
    del_count = len - start_i;
  }
  
  var deleted_elements = [];
  deleted_elements.length = del_count;
  
  // Number of elements to add.
  var num_additional_args = 0;
  if (num_arguments > 2) {
    num_additional_args = num_arguments - 2;
  }
  
  var use_simple_splice = true;
  
  if (IS_ARRAY(this) && num_additional_args !== del_count) {
    // If we are only deleting/moving a few things near the end of the
    // array then the simple version is going to be faster, because it
    // doesn't touch most of the array.
    var estimated_non_hole_elements = %EstimateNumberOfElements(this);
    if (len > 20 && (estimated_non_hole_elements >> 2) < (len - start_i)) {
      use_simple_splice = false;
    }
  }
  
  if (use_simple_splice) {
    SimpleSlice(this, start_i, del_count, len, deleted_elements);
    SimpleMove(this, start_i, del_count, len, num_additional_args);
  } else {
    SmartSlice(this, start_i, del_count, len, deleted_elements);
    SmartMove(this, start_i, del_count, len, num_additional_args);
  }
  
  // Insert the arguments into the resulting array in
  // place of the deleted elements.
  var i = start_i;
  var arguments_index = 2;
  var arguments_length = %_ArgumentsLength();
  while (arguments_index < arguments_length) {
    this[i++] = %_Arguments(arguments_index++);
  }
  this.length = len - del_count + num_additional_args;
  
  // Return the deleted elements.
  return deleted_elements;
};


function ArraySort(comparefn) {
  // Standard in-place HeapSort algorithm.

  function Compare(x,y) {
    if (IS_UNDEFINED(x)) {
      if (IS_UNDEFINED(y)) return 0;
      return 1;
    }
    if (IS_UNDEFINED(y)) return -1;

    if (IS_FUNCTION(comparefn)) {
      return comparefn.call(null, x, y);
    }
    if (%_IsSmi(x) && %_IsSmi(y)) {
      return %SmiLexicographicCompare(x, y);
    }
    x = ToString(x);
    y = ToString(y);
    if (x == y) return 0;
    else return x < y ? -1 : 1;
  };

  var old_length = ToUint32(this.length);

  %RemoveArrayHoles(this);

  var length = ToUint32(this.length);

  // Bottom-up max-heap construction.
  for (var i = 1; i < length; ++i) {
    var child_index = i;
    while (child_index > 0) {
      var parent_index = ((child_index + 1) >> 1) - 1;
      var parent_value = this[parent_index], child_value = this[child_index];
      if (Compare(parent_value, child_value) < 0) {
        this[parent_index] = child_value;
        this[child_index] = parent_value;
      } else {
        break;
      }
      child_index = parent_index;
    }
  }

  // Extract element and create sorted array.
  for (var i = length - 1; i > 0; --i) {
    // Put the max element at the back of the array.
    var t0 = this[0]; this[0] = this[i]; this[i] = t0;
    // Sift down the new top element.
    var parent_index = 0;
    while (true) {
      var child_index = ((parent_index + 1) << 1) - 1;
      if (child_index >= i) break;
      var child1_value = this[child_index];
      var child2_value = this[child_index + 1];
      var parent_value = this[parent_index];
      if (child_index + 1 >= i || Compare(child1_value, child2_value) > 0) {
        if (Compare(parent_value, child1_value) > 0) break;
        this[child_index] = parent_value;
        this[parent_index] = child1_value;
        parent_index = child_index;
      } else {
        if (Compare(parent_value, child2_value) > 0) break;
        this[child_index + 1] = parent_value;
        this[parent_index] = child2_value;
        parent_index = child_index + 1;
      }
    }
  }

  // We only changed the length of the this object (in
  // RemoveArrayHoles) if it was an array.  We are not allowed to set
  // the length of the this object if it is not an array because this
  // might introduce a new length property.
  if (IS_ARRAY(this)) {
    this.length = old_length;
  }

  return this;
};


// The following functions cannot be made efficient on sparse arrays while
// preserving the semantics, since the calls to the receiver function can add
// or delete elements from the array.

function ArrayFilter(f, receiver) {
  if (!IS_FUNCTION(f)) {
    throw MakeTypeError('called_non_callable', [ f ]);
  }
  // Pull out the length so that modifications to the length in the
  // loop will not affect the looping.
  var length = this.length;
  var result = [];
  for (var i = 0; i < length; i++) {
    var current = this[i];
    if (!IS_UNDEFINED(current) || i in this) {
      if (f.call(receiver, current, i, this)) result.push(current);
    }
  }
  return result;
};


function ArrayForEach(f, receiver) {
  if (!IS_FUNCTION(f)) {
    throw MakeTypeError('called_non_callable', [ f ]);
  }
  // Pull out the length so that modifications to the length in the
  // loop will not affect the looping.
  var length = this.length;
  for (var i = 0; i < length; i++) {
    var current = this[i];
    if (!IS_UNDEFINED(current) || i in this) {
      f.call(receiver, current, i, this);
    }
  }
};


// Executes the function once for each element present in the
// array until it finds one where callback returns true.
function ArraySome(f, receiver) {
  if (!IS_FUNCTION(f)) {
    throw MakeTypeError('called_non_callable', [ f ]);
  }
  // Pull out the length so that modifications to the length in the
  // loop will not affect the looping.
  var length = this.length;
  for (var i = 0; i < length; i++) {
    var current = this[i];
    if (!IS_UNDEFINED(current) || i in this) {
      if (f.call(receiver, current, i, this)) return true;
    }
  }
  return false;
};


function ArrayEvery(f, receiver) {
  if (!IS_FUNCTION(f)) {
    throw MakeTypeError('called_non_callable', [ f ]);
  }
  // Pull out the length so that modifications to the length in the
  // loop will not affect the looping.
  var length = this.length;
  for (var i = 0; i < length; i++) {
    var current = this[i];
    if (!IS_UNDEFINED(current) || i in this) {
      if (!f.call(receiver, current, i, this)) return false;
    }
  }
  
  return true;
};


function ArrayMap(f, receiver) {
  if (!IS_FUNCTION(f)) {
    throw MakeTypeError('called_non_callable', [ f ]);
  }
  // Pull out the length so that modifications to the length in the
  // loop will not affect the looping.
  var length = this.length;
  var result = new $Array(length);
  for (var i = 0; i < length; i++) {
    var current = this[i];
    if (!IS_UNDEFINED(current) || i in this) {
      result[i] = f.call(receiver, current, i, this);
    }
  }
  return result;
};


function ArrayIndexOf(element, index) {
  var length = this.length;
  if (index == null) {
    index = 0;
  } else {
    index = TO_INTEGER(index);
    // If index is negative, index from the end of the array.
    if (index < 0) index = length + index;
    // If index is still negative, search the entire array.
    if (index < 0) index = 0;
  }
  // Lookup through the array.
  for (var i = index; i < length; i++) {
    var current = this[i];
    if (!IS_UNDEFINED(current) || i in this) {
      if (current === element) return i;
    }
  }
  return -1;
};


function ArrayLastIndexOf(element, index) {
  var length = this.length;
  if (index == null) {
    index = length - 1;
  } else {
    index = TO_INTEGER(index);
    // If index is negative, index from end of the array.
    if (index < 0) index = length + index;
    // If index is still negative, do not search the array.
    if (index < 0) index = -1;
    else if (index >= length) index = length - 1;
  }
  // Lookup through the array.
  for (var i = index; i >= 0; i--) {
    var current = this[i];
    if (!IS_UNDEFINED(current) || i in this) {
      if (current === element) return i;
    }
  }
  return -1;
};


// -------------------------------------------------------------------

function InstallProperties(prototype, attributes, properties) {
  for (var key in properties) {
    %AddProperty(prototype, key, properties[key], attributes);
  }
};


function UpdateFunctionLengths(lengths) {
  for (var key in lengths) {
    %FunctionSetLength(this[key], lengths[key]);
  }
};


// -------------------------------------------------------------------

function SetupArray() {
  // Setup non-enumerable properties of the Array.prototype object.
  InstallProperties($Array.prototype, DONT_ENUM, {
    constructor: $Array,
    toString: ArrayToString,
    toLocaleString: ArrayToLocaleString,
    join: ArrayJoin,
    pop: ArrayPop,
    push: ArrayPush,
    concat: ArrayConcat,
    reverse: ArrayReverse,
    shift: ArrayShift,
    unshift: ArrayUnshift,
    slice: ArraySlice,
    splice: ArraySplice,
    sort: ArraySort,
    filter: ArrayFilter,
    forEach: ArrayForEach,
    some: ArraySome,
    every: ArrayEvery,
    map: ArrayMap,
    indexOf: ArrayIndexOf,
    lastIndexOf: ArrayLastIndexOf
  });

  // Manipulate the length of some of the functions to meet
  // expectations set by ECMA-262 or Mozilla.
  UpdateFunctionLengths({
    ArrayFilter: 1,
    ArrayForEach: 1,
    ArraySome: 1,
    ArrayEvery: 1,
    ArrayMap: 1,
    ArrayIndexOf: 1,
    ArrayLastIndexOf: 1,
    ArrayPush: 1
  });
};


SetupArray();