[Top][All Lists]
[Date Prev][Date Next][Thread Prev][Thread Next][Date Index][Thread Index]
[Gnash-commit] gnash ChangeLog server/array.cpp server/array.h...
|
From: |
Sandro Santilli |
|
Subject: |
[Gnash-commit] gnash ChangeLog server/array.cpp server/array.h... |
|
Date: |
Wed, 19 Mar 2008 11:40:18 +0000 |
CVSROOT: /sources/gnash
Module name: gnash
Changes by: Sandro Santilli <strk> 08/03/19 11:40:16
Modified files:
. : ChangeLog
server : array.cpp array.h
testsuite/actionscript.all: array.as
Log message:
* server/array.{cpp,h}: use boost's mapped_vector for a sparse
array implementation. Saves space at some cpu cycles till all
gaps are filled (which happens by most modifiers, as an
expected
behaviour :/).
* testsuite/actionscript.all/array.as: successes in gaps
filling.
CVSWeb URLs:
http://cvs.savannah.gnu.org/viewcvs/gnash/ChangeLog?cvsroot=gnash&r1=1.5974&r2=1.5975
http://cvs.savannah.gnu.org/viewcvs/gnash/server/array.cpp?cvsroot=gnash&r1=1.96&r2=1.97
http://cvs.savannah.gnu.org/viewcvs/gnash/server/array.h?cvsroot=gnash&r1=1.44&r2=1.45
http://cvs.savannah.gnu.org/viewcvs/gnash/testsuite/actionscript.all/array.as?cvsroot=gnash&r1=1.57&r2=1.58
Patches:
Index: ChangeLog
===================================================================
RCS file: /sources/gnash/gnash/ChangeLog,v
retrieving revision 1.5974
retrieving revision 1.5975
diff -u -b -r1.5974 -r1.5975
--- ChangeLog 19 Mar 2008 10:13:38 -0000 1.5974
+++ ChangeLog 19 Mar 2008 11:40:12 -0000 1.5975
@@ -1,5 +1,13 @@
2008-03-18 Sandro Santilli <address@hidden>
+ * server/array.{cpp,h}: use boost's mapped_vector for a sparse
+ array implementation. Saves space at some cpu cycles till all
+ gaps are filled (which happens by most modifiers, as an expected
+ behaviour :/).
+ * testsuite/actionscript.all/array.as: successes in gaps filling.
+
+2008-03-18 Sandro Santilli <address@hidden>
+
* testsuite/actionscript.all/array.as:
test splice() and members access on a sparse array.
Index: server/array.cpp
===================================================================
RCS file: /sources/gnash/gnash/server/array.cpp,v
retrieving revision 1.96
retrieving revision 1.97
diff -u -b -r1.96 -r1.97
--- server/array.cpp 18 Mar 2008 11:26:54 -0000 1.96
+++ server/array.cpp 19 Mar 2008 11:40:15 -0000 1.97
@@ -511,26 +511,18 @@
// extract fUniqueSort and fReturnIndexedArray from first flag
if (it != itEnd)
{
- as_array_object::ValOrNone v = *it++;
- if ( v.which() == as_array_object::itemValue )
- {
- boost::uint8_t flag =
static_cast<boost::uint8_t>(boost::get<as_value>(v).to_number());
+ boost::uint8_t flag =
static_cast<boost::uint8_t>((*it++).to_number());
flag = flag_preprocess(flag, uniq, index);
flgs.push_back(flag);
}
- }
while (it != itEnd)
{
- as_array_object::ValOrNone v = *it++;
- if ( v.which() == as_array_object::itemValue )
- {
- boost::uint8_t flag =
static_cast<boost::uint8_t>(boost::get<as_value>(v).to_number());
+ boost::uint8_t flag =
static_cast<boost::uint8_t>((*it++).to_number());
flag &= ~(as_array_object::fReturnIndexedArray);
flag &= ~(as_array_object::fUniqueSort);
flgs.push_back(flag);
}
- }
return flgs;
}
@@ -568,10 +560,7 @@
for (const_iterator it = elements.begin();
it != elements.end(); ++it)
{
- if ( it->which() == itemValue )
- {
-
indexed_elements.push_back(indexed_as_value(boost::get<as_value>(*it), i++));
- }
+ indexed_elements.push_back(indexed_as_value(*it, i++));
}
return indexed_elements;
}
@@ -606,20 +595,25 @@
void
as_array_object::push(const as_value& val)
{
- elements.push_back(val);
+ size_t s=elements.size();
+ elements.resize(s+1);
+ elements[s] = val;
}
void
as_array_object::unshift(const as_value& val)
{
- elements.push_front(val);
+ shiftElementsRight(1);
+ elements[0] = val;
}
as_value
as_array_object::pop()
{
// If the array is empty, report an error and return undefined!
- if ( elements.empty() )
+ size_t sz = elements.size();
+
+ if ( ! sz )
{
IF_VERBOSE_ASCODING_ERRORS(
log_aserror(_("tried to pop element from back of empty array,
returning undef"));
@@ -627,11 +621,9 @@
return as_value(); // undefined
}
- ValOrNone last = elements.back();
- as_value ret;
- if ( last.which() == itemValue ) ret = boost::get<as_value>(last);
- else log_error("Last element of Array (on pop) is not a value");
- elements.pop_back();
+ --sz;
+ as_value ret = elements[sz];
+ elements.resize(sz);
return ret;
}
@@ -639,8 +631,10 @@
as_value
as_array_object::shift()
{
+ size_t sz = elements.size();
+
// If the array is empty, report an error and return undefined!
- if ( elements.empty() )
+ if ( ! sz )
{
IF_VERBOSE_ASCODING_ERRORS(
log_aserror(_("tried to shift element from front of empty
array, returning undef"));
@@ -648,10 +642,8 @@
return as_value(); // undefined
}
- ValOrNone first = elements.front();
- as_value ret;
- if ( first.which() == itemValue ) ret = boost::get<as_value>(first);
- elements.pop_front();
+ as_value ret = elements[0];
+ shiftElementsLeft(1);
return ret;
}
@@ -659,8 +651,20 @@
void
as_array_object::reverse()
{
- // Reverse the deque elements
- std::reverse(elements.begin(), elements.end());
+ size_t sz = elements.size();
+ if ( sz < 2 ) return; // nothing to do (CHECKME: might be a single
hole!)
+
+ // We create another container, as we want to fill the gaps
+ // There could likely be an in-place version for this, but
+ // filling the gaps would need more care
+ container newelements(sz);
+
+ for (size_t i=0, n=sz-1; i<sz; ++i, --n)
+ {
+ newelements[i] = elements[n];
+ }
+
+ elements = newelements;
}
std::string
@@ -674,25 +678,19 @@
// We should change output based on SWF version --strk 2006-04-28
std::string temp;
+
//std::string temp = "("; // SWF > 7
- int swfversion = _vm.getSWFVersion();
+ size_t sz = elements.size();
- if ( ! elements.empty() )
+ if ( sz )
{
- bool printed=false;
-
- const_iterator it=elements.begin(), itEnd=elements.end();
+ int swfversion = _vm.getSWFVersion();
- while ( it != itEnd )
+ for (size_t i=0; i<sz; ++i)
{
- ValOrNone v = *it++;
- if ( printed ) temp += separator;
- if ( v.which() == itemValue )
- temp +=
boost::get<as_value>(v).to_string_versioned(swfversion);
- else
- temp +=
as_value().to_string_versioned(swfversion);
- printed=true;
+ if ( i ) temp += separator;
+ temp += elements[i].to_string_versioned(swfversion);
}
}
@@ -705,8 +703,8 @@
void
as_array_object::concat(const as_array_object& other)
{
- elements.insert(elements.end(), other.elements.begin(),
- other.elements.end());
+ for (size_t i=0, e=other.size(); i<e; i++)
+ push(other.at(i));
}
std::string
@@ -722,18 +720,10 @@
}
as_value
-as_array_object::at(unsigned int index)
+as_array_object::at(unsigned int index) const
{
- if ( index > elements.size()-1 )
- {
- return as_value();
- }
- else
- {
- ValOrNone v = elements[index];
- if ( v.which() != itemValue ) return as_value();
- return boost::get<as_value>(v);
- }
+ if ( index > elements.size()-1 ) return as_value();
+ else return elements[index];
}
std::auto_ptr<as_array_object>
@@ -762,59 +752,14 @@
}
-std::auto_ptr<as_array_object>
-as_array_object::splice(unsigned start, unsigned len,
- const std::vector<as_value>& replace)
-{
- assert(len <= size()-start);
- assert(start <= size());
-
-#ifdef GNASH_DEBUG
- std::stringstream ss;
- ss << "Array.splice(" << start << ", " << len << ", ";
- std::ostream_iterator<as_value> ostrIter(ss, "," ) ;
- std::copy(replace.begin(), replace.end(), ostrIter);
- ss << ") called";
- log_debug("%s", ss.str().c_str());
- log_debug(_("Current array is %s"), toString().c_str());
-#endif
-
- container::iterator itStart = elements.begin()+start;
- container::iterator itEnd = itStart+len;
-
- // This will be returned...
- std::auto_ptr<as_array_object> ret(new as_array_object);
-
- // If something has to be removed do it and assign
- // to the returned object
- if ( itStart != itEnd )
- {
- ret->elements.assign(itStart, itEnd);
-
- elements.erase(itStart, itEnd);
- }
-
- // Now insert the new stuff, if needed
- if ( ! replace.empty() )
- {
- container::iterator itStart = elements.begin()+start;
- elements.insert(itStart, replace.begin(), replace.end());
- }
-
- return ret;
-}
-
bool
as_array_object::removeFirst(const as_value& v)
{
for (iterator it = elements.begin(); it != elements.end(); ++it)
{
- ValOrNone x = *it;
- if ( x.which() != itemValue ) continue;
-
- if ( v.equals(boost::get<as_value>(x)) )
+ if ( v.equals(*it) )
{
- elements.erase(it);
+ splice(it.index(), 1);
return true;
}
}
@@ -828,12 +773,14 @@
{
// an index has been requested
int index = index_requested(name);
- if ( index >= 0 && (unsigned int)index < elements.size() )
+
+ if ( index >= 0 ) // a valid index was requested
{
- ValOrNone x = elements[index];
- if ( x.which() == itemValue )
+ size_t i = index;
+ const_iterator it = elements.find(i);
+ if ( it != elements.end() && it.index() == i )
{
- *val = boost::get<as_value>(x);
+ *val = *it;
return true;
}
}
@@ -871,7 +818,7 @@
// if we were sent a valid array index and not a normal member
if (index >= 0)
{
- if (index >= int(elements.size()))
+ if ( size_t(index) >= elements.size() )
{
// if we're setting index (x), the vector
// must be size (x+1)
@@ -883,6 +830,7 @@
return;
}
+
as_object::set_member_default(name,val, nsname);
}
@@ -959,9 +907,8 @@
replace.push_back(fn.arg(i));
}
- std::auto_ptr<as_array_object> spliced ( array->splice(startoffset,
len, replace) );
-
- boost::intrusive_ptr<as_object> ret = spliced.release();
+ as_array_object* ret = new as_array_object();
+ array->splice(startoffset, len, &replace, ret);
return as_value(ret);
}
@@ -1084,13 +1031,9 @@
for (as_array_object::const_iterator it = props->begin();
it != props->end(); ++it)
{
- as_array_object::ValOrNone v = *it;
- if ( v.which() == as_array_object::itemValue )
- {
- string_table::key s =
st.find(PROPNAME(boost::get<as_value>(v).to_string_versioned(sv)));
+ string_table::key s =
st.find(PROPNAME((*it).to_string_versioned(sv)));
prp.push_back(s);
}
- }
// case: sortOn(["prop1", "prop2"])
if (fn.nargs == 1)
@@ -1306,7 +1249,10 @@
boost::intrusive_ptr<as_array_object> array =
ensureType<as_array_object>(fn.this_ptr);
// use copy ctor
- as_array_object* newarray = new as_array_object(*array);
+ as_array_object* newarray = new as_array_object();
+
+ for (size_t i=0, e=array->size(); i<e; i++)
+ newarray->push(array->at(i));
for (unsigned int i=0; i<fn.nargs; i++)
{
@@ -1571,13 +1517,87 @@
// TODO: only actually defined elements should be pushed on the env
// but we currently have no way to distinguish between defined
// and non-defined elements
- for (unsigned int i=0; i<size(); ++i)
+ for (const_iterator it = elements.begin(),
+ itEnd = elements.end(); it != itEnd; ++it)
{
- if ( elements[i].which() == itemValue )
+ env.push(as_value(it.index()));
+ }
+}
+
+void
+as_array_object::shiftElementsLeft(unsigned int count)
+{
+ container& v = elements;
+
+ if ( count >= v.size() )
{
- env.push(as_value(i));
+ v.clear();
+ return;
}
+
+ for (unsigned int i=0; i<count; ++i) v.erase_element(i);
+
+ for (container::iterator i=v.begin(), e=v.end(); i!=e; ++i)
+ {
+ int currentIndex = i.index();
+ int newIndex = currentIndex-count;
+ v[newIndex] = *i;
}
+ v.resize(v.size()-count);
+}
+
+void
+as_array_object::shiftElementsRight(unsigned int count)
+{
+ container& v = elements;
+
+ v.resize(v.size()+count);
+ for (container::reverse_iterator i=v.rbegin(), e=v.rend(); i!=e; ++i)
+ {
+ int currentIndex = i.index();
+ int newIndex = currentIndex+count;
+ v[newIndex] = *i;
+ }
+ while (count--) v.erase_element(count);
+}
+
+void
+as_array_object::splice(unsigned int start, unsigned int count, const
std::vector<as_value>* replace, as_array_object* receive)
+{
+ size_t sz = elements.size();
+
+ assert ( start <= sz );
+ assert ( start+count <= sz );
+
+ size_t newsize = sz-count;
+ if ( replace ) newsize += replace->size();
+ container newelements(newsize);
+
+ size_t ni=0;
+
+ // add initial portion
+ for (size_t i=0; i<start; ++i )
+ newelements[ni++] = elements[i];
+
+ // add replacement, if any
+ if ( replace )
+ {
+ for (size_t i=0, e=replace->size(); i<e; ++i)
+ newelements[ni++] = replace->at(i);
+ }
+
+ // add final portion
+ for (size_t i=start+count; i<sz; ++i )
+ newelements[ni++] = elements[i];
+
+ // push trimmed data to the copy array, if any
+ if ( receive )
+ {
+ for (size_t i=start; i<start+count; ++i )
+ receive->push(elements[i]);
+ }
+
+ elements = newelements;
}
#ifdef GNASH_USE_GC
@@ -1586,11 +1606,7 @@
{
for (const_iterator i=elements.begin(), e=elements.end(); i!=e; ++i)
{
- ValOrNone v = *i;
- if ( v.which() == itemValue )
- {
- boost::get<as_value>(v).setReachable();
- }
+ (*i).setReachable();
}
markAsObjectReachable();
}
Index: server/array.h
===================================================================
RCS file: /sources/gnash/gnash/server/array.h,v
retrieving revision 1.44
retrieving revision 1.45
diff -u -b -r1.44 -r1.45
--- server/array.h 18 Mar 2008 11:26:54 -0000 1.44
+++ server/array.h 19 Mar 2008 11:40:15 -0000 1.45
@@ -23,6 +23,7 @@
#include <deque>
#include <vector>
#include <memory> // for auto_ptr
+#include <boost/numeric/ublas/vector_sparse.hpp>
#include <string>
@@ -62,9 +63,10 @@
enum { itemBlank, itemValue };
- typedef boost::variant<blank, as_value> ValOrNone;
+ //typedef boost::variant<blank, as_value> ValOrNone;
+ //typedef std::deque<ValOrNone> container;
- typedef std::deque<ValOrNone> container;
+ typedef boost::numeric::ublas::mapped_vector<as_value> container;
typedef container::const_iterator const_iterator;
typedef container::iterator iterator;
@@ -78,10 +80,10 @@
// NOTE: we copy the elements as the visitor might call
arbitrary code
// possibly modifying the container itself.
container copy = elements;
+
+ // iterating this way will skip holes
for (iterator i=copy.begin(), ie=copy.end(); i!=ie; ++i)
- {
- if ( i->which() == itemValue )
v.visit(boost::get<as_value>(*i));
- }
+ v.visit(*i);
}
/// Sort flags
@@ -133,7 +135,7 @@
as_value pop();
- as_value at(unsigned int index);
+ as_value at(unsigned int index) const;
as_array_object* get_indices(std::deque<indexed_as_value> origElems);
@@ -191,6 +193,9 @@
//
/// Return true if any element was removed, false otherwise
///
+ /// NOTE: if an element is removed, holes in the array will be
+ /// filled.
+ ///
/// @param v
/// The value to compare elements against
///
@@ -200,27 +205,24 @@
bool removeFirst(const as_value& v);
/// \brief
- /// Substitute 'len' elements from 'start' with elements from
- /// the given array.
+ /// Replace count elements from start with given values, optionally
+ /// returning the erased ones.
//
- /// NOTE: assertions are:
- ///
- /// assert(len <= size()-start);
- /// assert(start <= size());
- ///
/// @param start
- /// 0-index based offset of first element to replace.
+ /// First element to remove. Will abort if invalid.
///
- /// @param len
- /// Number of elements to replace.
+ /// @param count
+ /// Number of elements to remove. Will abort if > then available.
///
- /// @param replacement
- /// The element to use as replacement
+ /// @param replace
+ /// If not null, use as a replacement for the cutted values
///
- /// TODO: should we return by intrusive_ptr instead ?
+ /// @param copy
+ /// If not null, an array to push cutted values to.
///
- std::auto_ptr<as_array_object> splice(unsigned start, unsigned len,
- const std::vector<as_value>& replacement);
+ void splice(unsigned int start, unsigned int count,
+ const std::vector<as_value>* replace=NULL,
+ as_array_object* copy=NULL);
/// \brief
/// Sort the array, using given values comparator
@@ -255,8 +257,12 @@
size_t oldSize = elements.size(); // custom comparator might
change input size
nelem.sort(avc);
- elements.assign(nelem.begin(), nelem.end());
- resize(oldSize);
+ elements.resize(oldSize, false);
+ size_t idx=0;
+ for (ValueList::iterator i=nelem.begin(), e=nelem.end(); i!=e;
++i)
+ {
+ elements[idx++] = *i;
+ };
}
/// \brief
@@ -305,8 +311,12 @@
if (std::adjacent_find(nelem.begin(), nelem.end(), ave) !=
nelem.end() )
return as_value(0);
- elements.assign(nelem.begin(), nelem.end());
- resize(oldSize);
+ elements.resize(oldSize, false);
+ size_t idx=0;
+ for (ValueList::iterator i=nelem.begin(), e=nelem.end(); i!=e;
++i)
+ {
+ elements[idx++] = *i;
+ };
return as_value(this);
}
@@ -388,6 +398,19 @@
// if the string does not refer to an index, or an appropriate int if
the string does refer to an index
int index_requested(string_table::key name);
+ /// Shift all elements to the left by count positions
+ //
+ /// Pre-condition: size of the array must be >= count
+ /// Post-condition: size of the array will reduce by 'count'
+ ///
+ void shiftElementsLeft(unsigned int count);
+
+ /// Shift all elements to the right by count positions
+ //
+ /// Pre-condition: none
+ /// Post-condition: size of the array will incremented by 'count'
+ ///
+ void shiftElementsRight(unsigned int count);
};
Index: testsuite/actionscript.all/array.as
===================================================================
RCS file: /sources/gnash/gnash/testsuite/actionscript.all/array.as,v
retrieving revision 1.57
retrieving revision 1.58
diff -u -b -r1.57 -r1.58
--- testsuite/actionscript.all/array.as 19 Mar 2008 10:13:38 -0000 1.57
+++ testsuite/actionscript.all/array.as 19 Mar 2008 11:40:16 -0000 1.58
@@ -19,7 +19,7 @@
// Initial test written by Mike Carlson
-rcsid="$Id: array.as,v 1.57 2008/03/19 10:13:38 strk Exp $";
+rcsid="$Id: array.as,v 1.58 2008/03/19 11:40:16 strk Exp $";
#include "check.as"
check_equals(typeof(Array), 'function');
@@ -464,7 +464,7 @@
#endif
sparse.reverse();
count=0; for (var i in sparse) count++;
-xcheck_equals(count, 6); // no more holes
+check_equals(count, 6); // no more holes
#if OUTPUT_VERSION > 5
xcheck(sparse.hasOwnProperty(0));
xcheck(sparse.hasOwnProperty(5));
@@ -552,11 +552,11 @@
check_equals(count, 1);
count=0; for (var i in csp) count++;
-xcheck_equals(count, 7); // concat filled any holes
+check_equals(count, 7); // concat filled any holes
csp = sparse1.concat('onemore');
count=0; for (var i in csp) count++;
-xcheck_equals(count, 5); // concat filled any holes
+check_equals(count, 5); // concat filled any holes
//-------------------------------
// Test Array.splice
@@ -665,22 +665,22 @@
spliced = ary.splice(3, 0); // no op ?
check_equals(ary.length, 8); // no change in length
count=0; for (var i in ary) count++;
-xcheck_equals(count, 8); // but fills the gaps !
+check_equals(count, 8); // but fills the gaps !
ary = new Array(); ary[2] = 2; ary[7] = 7;
spliced = ary.splice(3, 0, 3); // add 3 at index 3
check_equals(ary.length, 9);
count=0; for (var i in ary) count++;
-xcheck_equals(count, 9); // fills the gaps !
+check_equals(count, 9); // fills the gaps !
check_equals(ary[3], 3);
check_equals(ary[2], 2);
ary = new Array(); ary[2] = 2; ary[7] = 7;
spliced = ary.splice(3, 1, 3); // replace index 3 (an hole) with a 3 value
count=0; for (var i in ary) count++;
-xcheck_equals(count, 8); // fills the gaps
+check_equals(count, 8); // fills the gaps
count=0; for (var i in spliced) count++;
-xcheck_equals(count, 1); // the returned array contains an actual value, not
an hole
+check_equals(count, 1); // the returned array contains an actual value, not an
hole
//-------------------------------
// Test single parameter constructor, and implicitly expanding array