Bug 530366 - don't use std::sort in jsregexp (r=dmandelin)
authorLuke Wagner <lw@mozilla.com>
Mon, 30 Nov 2009 09:03:43 -0800
changeset 35383 a34ee79b0c62222fe33c479f7f019f747daab510
parent 35382 8cb445224dc5eca1de8290c317af9de3cd1d55c2
child 35385 64a5fc31849612234e5803240ce3f7ebef0b8918
push id10560
push userrsayre@mozilla.com
push dateTue, 01 Dec 2009 18:15:12 +0000
treeherdermozilla-central@e2860a4dcf0c [default view] [failures only]
perfherder[talos] [build metrics] [platform microbench] (compared to previous push)
reviewersdmandelin
bugs530366
milestone1.9.3a1pre
Bug 530366 - don't use std::sort in jsregexp (r=dmandelin)
js/src/jsregexp.cpp
--- a/js/src/jsregexp.cpp
+++ b/js/src/jsregexp.cpp
@@ -63,18 +63,16 @@
 #include "jsopcode.h"
 #include "jsregexp.h"
 #include "jsscan.h"
 #include "jsscope.h"
 #include "jsstaticcheck.h"
 #include "jsstr.h"
 #include "jsvector.h"
 
-#include <algorithm>
-
 #ifdef JS_TRACER
 #include "jstracer.h"
 using namespace avmplus;
 using namespace nanojit;
 #endif
 
 typedef enum REOp {
 #define REOP_DEF(opcode, name) opcode,
@@ -2072,17 +2070,19 @@ static const bool js_ws[] = {
 /*  3 */ false, false, true
 };
 
 /* Sets of characters are described in terms of individuals and classes. */
 class CharSet {
   public:
     CharSet() : charEnd(charBuf), classes(0) {}
 
-    bool full() { return charEnd == charBuf + BufSize; }
+    static const uintN sBufSize = 8;
+
+    bool full() { return charEnd == charBuf + sBufSize; }
 
     /* Add a single char to the set. */
     bool addChar(jschar c)
     {
         if (full())
             return false;
         *charEnd++ = c;
         return true;
@@ -2105,18 +2105,17 @@ class CharSet {
     void addClass(Class c) { classes |= c; }
 
     /* Return whether two sets of chars are disjoint. */
     bool disjoint(const CharSet &) const;
 
   private:
     static bool disjoint(const jschar *beg, const jschar *end, uintN classes);
 
-    static const uintN BufSize = 8;
-    mutable jschar charBuf[BufSize];
+    mutable jschar charBuf[sBufSize];
     jschar *charEnd;
     uintN classes;
 };
 
 /* Appease the type checker. */
 static inline CharSet::Class
 operator|(CharSet::Class c1, CharSet::Class c2) {
     return (CharSet::Class)(((int)c1) | ((int)c2));
@@ -2176,34 +2175,45 @@ set_disjoint(InputIterator1 p1, InputIte
             ++p2;
             if (p2 == end2)
                 return true;
         }
     }
     return false;
 }
 
+static JSBool
+CharCmp(void *arg, const void *a, const void *b, int *result)
+{
+    jschar ca = *(jschar *)a, cb = *(jschar *)b;
+    *result = ca - cb;
+    return JS_TRUE;
+}
+
 bool
 CharSet::disjoint(const CharSet &other) const
 {
     /* Check overlap between classes. */
     if (classes & other.classes)
         return false;
 
     /*
      * Check char-class overlap. Compare this->charBuf with other.classes and
      * vice versa with a loop.
      */
     if (!disjoint(this->charBuf, this->charEnd, other.classes) ||
         !disjoint(other.charBuf, other.charEnd, this->classes))
         return false;
 
     /* Check char-char overlap. */
-    std::sort(charBuf, charEnd);
-    std::sort(other.charBuf, other.charEnd);
+    jschar tmp[CharSet::sBufSize];
+    js_MergeSort(charBuf, charEnd - charBuf, sizeof(jschar),
+                 CharCmp, 0, tmp);
+    js_MergeSort(other.charBuf, other.charEnd - other.charBuf, sizeof(jschar),
+                 CharCmp, 0, tmp);
     return set_disjoint(charBuf, charEnd, other.charBuf, other.charEnd);
 }
 
 /*
  * Return true if the given subexpression may match the empty string. The
  * conservative answer is |true|. If |next| is true, then the subexpression is
  * considered to be |node| followed by the rest of |node->next|. Otherwise, the
  * subexpression is considered to be |node| by itself.