regexec.c: Replace infamous if-else-if sequence by loop
authorKarl Williamson <public@khwilliamson.com>
Fri, 7 Dec 2012 18:50:25 +0000 (11:50 -0700)
committerKarl Williamson <public@khwilliamson.com>
Sun, 9 Dec 2012 19:08:29 +0000 (12:08 -0700)
This saves 1.5 KB in the text section on my machine in regexec.o
(unoptimized) and 820 optimized.  I did not benchmark, as we don't
really care very much about performance under 'use locale'.

embed.fnc
embed.h
handy.h
proto.h
regexec.c

index b851e3c..6d6befe 100644 (file)
--- a/embed.fnc
+++ b/embed.fnc
@@ -2025,6 +2025,7 @@ Es        |U8     |regtail_study  |NN struct RExC_state_t *pRExC_state \
 #endif
 
 #if defined(PERL_IN_REGEXEC_C)
+ERs    |bool   |isFOO_lc       |const U8 classnum|const U8 character
 ERs    |I32    |regmatch       |NN regmatch_info *reginfo|NN char *startpos|NN regnode *prog
 ERs    |I32    |regrepeat      |NN const regexp *prog|NN char **startposp|NN const regnode *p|I32 max|int depth
 ERs    |I32    |regtry         |NN regmatch_info *reginfo|NN char **startposp
diff --git a/embed.h b/embed.h
index ad691a6..fbb49f6 100644 (file)
--- a/embed.h
+++ b/embed.h
 #  if defined(PERL_IN_REGEXEC_C)
 #define core_regclass_swash(a,b,c,d)   S_core_regclass_swash(aTHX_ a,b,c,d)
 #define find_byclass(a,b,c,d,e)        S_find_byclass(aTHX_ a,b,c,d,e)
+#define isFOO_lc(a,b)          S_isFOO_lc(aTHX_ a,b)
 #define is_utf8_X_LVT(a)       S_is_utf8_X_LVT(aTHX_ a)
 #define reg_check_named_buff_matched(a,b)      S_reg_check_named_buff_matched(aTHX_ a,b)
 #define regcppop(a)            S_regcppop(aTHX_ a)
diff --git a/handy.h b/handy.h
index f7cd8fe..9f67d44 100644 (file)
--- a/handy.h
+++ b/handy.h
@@ -717,7 +717,8 @@ patched there.  The file as of this writing is cpan/Devel-PPPort/parts/inc/misc
  * has a name not used here, it won't compile.
  *
  * The first group of these is ordered in what I (khw) estimate to be the
- * frequency of their use. */
+ * frequency of their use.  This gives a slight edge to exiting a loop earlier
+ * (in reginclass() in regexec.c) */
 #  define _CC_WORDCHAR           0      /* \w and [:word:] */
 #  define _CC_DIGIT              1      /* \d and [:digit:] */
 #  define _CC_ALPHA              2      /* [:alpha:] */
diff --git a/proto.h b/proto.h
index 65049a1..2875e76 100644 (file)
--- a/proto.h
+++ b/proto.h
@@ -6788,6 +6788,9 @@ STATIC char*      S_find_byclass(pTHX_ regexp * prog, const regnode *c, char *s, cons
 #define PERL_ARGS_ASSERT_FIND_BYCLASS  \
        assert(prog); assert(c); assert(s); assert(strend)
 
+STATIC bool    S_isFOO_lc(pTHX_ const U8 classnum, const U8 character)
+                       __attribute__warn_unused_result__;
+
 PERL_STATIC_INLINE bool        S_is_utf8_X_LVT(pTHX_ const U8 *p)
                        __attribute__warn_unused_result__
                        __attribute__nonnull__(pTHX_1);
index b3149f6..a07472d 100644 (file)
--- a/regexec.c
+++ b/regexec.c
@@ -496,6 +496,45 @@ S_regcp_restore(pTHX_ regexp *rex, I32 ix)
 
 #define regcpblow(cp) LEAVE_SCOPE(cp)  /* Ignores regcppush()ed data. */
 
+STATIC bool
+S_isFOO_lc(pTHX_ const U8 classnum, const U8 character)
+{
+    /* Returns a boolean as to whether or not 'character' is a member of the
+     * Posix character class given by 'classnum' that should be equivalent to a
+     * value in the typedef '_char_class_number'.
+     *
+     * Ideally this could be replaced by a just an array of function pointers
+     * to the C library functions that implement the macros this calls.
+     * However, to compile, the precise function signatures are required, and
+     * these may vary from platform to to platform.  To avoid having to figure
+     * out what those all are on each platform, I (khw) am using this method,
+     * which adds an extra layer of function call overhead.  But we don't
+     * particularly care about performance with locales anyway. */
+
+    switch ((_char_class_number) classnum) {
+        case _CC_ENUM_ALNUMC:    return isALNUMC_LC(character);
+        case _CC_ENUM_ALPHA:     return isALPHA_LC(character);
+        case _CC_ENUM_DIGIT:     return isDIGIT_LC(character);
+        case _CC_ENUM_GRAPH:     return isGRAPH_LC(character);
+        case _CC_ENUM_LOWER:     return isLOWER_LC(character);
+        case _CC_ENUM_PRINT:     return isPRINT_LC(character);
+        case _CC_ENUM_PUNCT:     return isPUNCT_LC(character);
+        case _CC_ENUM_UPPER:     return isUPPER_LC(character);
+        case _CC_ENUM_WORDCHAR:  return isWORDCHAR_LC(character);
+        case _CC_ENUM_SPACE:     return isSPACE_LC(character);
+        case _CC_ENUM_BLANK:     return isBLANK_LC(character);
+        case _CC_ENUM_XDIGIT:    return isXDIGIT_LC(character);
+        case _CC_ENUM_CNTRL:     return isCNTRL_LC(character);
+        case _CC_ENUM_PSXSPC:    return isPSXSPC_LC(character);
+        case _CC_ENUM_ASCII:     return isASCII_LC(character);
+        default:    /* VERTSPACE should never occur in locales */
+            Perl_croak(aTHX_ "panic: isFOO_lc() has an unexpected character class '%d'", classnum);
+    }
+
+    assert(0); /* NOTREACHED */
+    return FALSE;
+}
+
 /*
  * pregexec and friends
  */
@@ -7419,40 +7458,40 @@ S_reginclass(pTHX_ const regexp * const prog, const regnode * const n, const U8*
            {
                match = TRUE;
            }
-           else if (ANYOF_CLASS_TEST_ANY_SET(n) &&
-                    ((ANYOF_CLASS_TEST(n, ANYOF_ALNUM)   &&  isALNUM_LC(c))  ||
-                     (ANYOF_CLASS_TEST(n, ANYOF_NALNUM)  && !isALNUM_LC(c))  ||
-                     (ANYOF_CLASS_TEST(n, ANYOF_SPACE)   &&  isSPACE_LC(c))  ||
-                     (ANYOF_CLASS_TEST(n, ANYOF_NSPACE)  && !isSPACE_LC(c))  ||
-                     (ANYOF_CLASS_TEST(n, ANYOF_DIGIT)   &&  isDIGIT_LC(c))  ||
-                     (ANYOF_CLASS_TEST(n, ANYOF_NDIGIT)  && !isDIGIT_LC(c))  ||
-                     (ANYOF_CLASS_TEST(n, ANYOF_ALNUMC)  &&  isALNUMC_LC(c)) ||
-                     (ANYOF_CLASS_TEST(n, ANYOF_NALNUMC) && !isALNUMC_LC(c)) ||
-                     (ANYOF_CLASS_TEST(n, ANYOF_ALPHA)   &&  isALPHA_LC(c))  ||
-                     (ANYOF_CLASS_TEST(n, ANYOF_NALPHA)  && !isALPHA_LC(c))  ||
-                     (ANYOF_CLASS_TEST(n, ANYOF_ASCII)   &&  isASCII_LC(c))  ||
-                     (ANYOF_CLASS_TEST(n, ANYOF_NASCII)  && !isASCII_LC(c))  ||
-                     (ANYOF_CLASS_TEST(n, ANYOF_CNTRL)   &&  isCNTRL_LC(c))  ||
-                     (ANYOF_CLASS_TEST(n, ANYOF_NCNTRL)  && !isCNTRL_LC(c))  ||
-                     (ANYOF_CLASS_TEST(n, ANYOF_GRAPH)   &&  isGRAPH_LC(c))  ||
-                     (ANYOF_CLASS_TEST(n, ANYOF_NGRAPH)  && !isGRAPH_LC(c))  ||
-                     (ANYOF_CLASS_TEST(n, ANYOF_LOWER)   &&  isLOWER_LC(c))  ||
-                     (ANYOF_CLASS_TEST(n, ANYOF_NLOWER)  && !isLOWER_LC(c))  ||
-                     (ANYOF_CLASS_TEST(n, ANYOF_PRINT)   &&  isPRINT_LC(c))  ||
-                     (ANYOF_CLASS_TEST(n, ANYOF_NPRINT)  && !isPRINT_LC(c))  ||
-                     (ANYOF_CLASS_TEST(n, ANYOF_PUNCT)   &&  isPUNCT_LC(c))  ||
-                     (ANYOF_CLASS_TEST(n, ANYOF_NPUNCT)  && !isPUNCT_LC(c))  ||
-                     (ANYOF_CLASS_TEST(n, ANYOF_UPPER)   &&  isUPPER_LC(c))  ||
-                     (ANYOF_CLASS_TEST(n, ANYOF_NUPPER)  && !isUPPER_LC(c))  ||
-                     (ANYOF_CLASS_TEST(n, ANYOF_XDIGIT)  &&  isXDIGIT(c))    ||
-                     (ANYOF_CLASS_TEST(n, ANYOF_NXDIGIT) && !isXDIGIT(c))    ||
-                     (ANYOF_CLASS_TEST(n, ANYOF_PSXSPC)  &&  isPSXSPC(c))    ||
-                     (ANYOF_CLASS_TEST(n, ANYOF_NPSXSPC) && !isPSXSPC(c))    ||
-                     (ANYOF_CLASS_TEST(n, ANYOF_BLANK)   &&  isBLANK_LC(c))  ||
-                     (ANYOF_CLASS_TEST(n, ANYOF_NBLANK)  && !isBLANK_LC(c))
-                    ) /* How's that for a conditional? */
-           ) {
-               match = TRUE;
+           else if (ANYOF_CLASS_TEST_ANY_SET(n)) {
+
+                /* The data structure is arranged so bits 0, 2, 4, ... are set
+                 * if the class includes the Posix character class given by
+                 * bit/2; and 1, 3, 5, ... are set if the class includes the
+                 * complemented Posix class given by int(bit/2).  So we loop
+                 * through the bits, each time changing whether we complement
+                 * the result or not.  Suppose for the sake of illustration
+                 * that bits 0-3 mean respectively, \w, \W, \s, \S.  If bit 0
+                 * is set, it means there is a match for this ANYOF node if the
+                 * character is in the class given by the expression (0 / 2 = 0
+                 * = \w).  If it is in that class, isFOO_lc() will return 1,
+                 * and since 'to_complement' is 0, the result will stay TRUE,
+                 * and we exit the loop.  Suppose instead that bit 0 is 0, but
+                 * bit 1 is 1.  That means there is a match if the character
+                 * matches \W.  We won't bother to call isFOO_lc() on bit 0,
+                 * but will on bit 1.  On the second iteration 'to_complement'
+                 * will be 1, so the exclusive or will reverse things, so we
+                 * are testing for \W.  On the third iteration, 'to_complement'
+                 * will be 0, and we would be testing for \s; the fourth
+                 * iteration would test for \S, etc. */
+
+                int count = 0;
+                int to_complement = 0;
+                while (count < ANYOF_MAX) {
+                    if (ANYOF_CLASS_TEST(n, count)
+                        && to_complement ^ cBOOL(isFOO_lc(count/2, (U8) c)))
+                    {
+                        match = TRUE;
+                        break;
+                    }
+                    count++;
+                    to_complement ^= 1;
+                }
            }
        }
     }