Gauche

[Gauche-devel-jp] Re: rxmatch-afterなどの改良

Rui Ueyama rui31****@gmail*****
2006年 11月 23日 (木) 18:00:32 JST

• 前の記事 [Gauche-devel-jp] Re: rxmatch-afterなどの改良
• 次の記事 [Gauche-devel-jp] WiLiKi: SPAM 投函の消しこみ作業
• 記事の並び順: [ 日付 ] [ スレッド ] [ 件名 ] [ 著者 ]

こんにちは。

見当をつけてスイッチするのはちょっとおおげさかなと思ったの
ですが、思い切ってきちんと作ってカウントをできるだけ少なく
しました。こんなのでどうでしょうか？

マッチした部分文字列に対してカウントできる長さは3つあって、
マッチ対象文字列の長さと以下の2つがわかれば残りの1つは
カウントしなくてもわかります。

・部分文字列の前の長さ
・部分文字列そのものの長さ
・部分文字列の後の長さ

sizeを使って、「まだカウントしていない長さの半分」と「カウント
しようとしている長さ」のどちらが長いのか見当をつけて、短い
ほうを数えるようにしてみました。たとえば後ろの文字列が
ずっと長い場合には、「部分文字列の前の長さ」と「部分文字列
そのものの長さ」を数えることになります。

On 11/23/06, Shiro Kawai <shiro****@lava*****> wrote:
> From: "Rui Ueyama" <rui31****@gmail*****>
> Subject: [Gauche-devel-jp] rxmatch-afterなどの改良
> Date: Wed, 22 Nov 2006 01:22:07 +0900
>
> > rxmatch-afterは、後ろの文字列が短い
> > 場合には逆に効率が悪くなるはずですが、トレードオフとして受け入れられる
> > かと思います。
>
> sizeでもってどちらが長いかの見当をつけてスイッチしたらどうでしょう。
-------------- next part --------------
Index: src/regexp.c
===================================================================
RCS file: /cvsroot/gauche/Gauche/src/regexp.c,v
retrieving revision 1.60
diff -u -r1.60 regexp.c
--- src/regexp.c	4 Nov 2006 09:56:59 -0000	1.60
+++ src/regexp.c	23 Nov 2006 04:39:59 -0000
@@ -2560,6 +2560,7 @@
         ctx.matches[i] = SCM_NEW(struct ScmRegMatchSub);
         ctx.matches[i]->start = -1;
         ctx.matches[i]->length = -1;
+        ctx.matches[i]->after = -1;
         ctx.matches[i]->startp = NULL;
         ctx.matches[i]->endp = NULL;
     }
@@ -2620,16 +2621,71 @@
 /* TODO: MT Warning: these retrival functions change match object's
  * internal state.
  */
-static ScmObj regmatch_substr(struct ScmRegMatchSub *sub)
+
+/* We want to avoid unnecessary character counting as much as
+   possible. */
+
+#define MSUB_BEFORE_SIZE(rm, sub) ((sub)->startp - (rm)->input)
+#define MSUB_SIZE(rm, sub)        ((sub)->endp - (sub)->startp)
+#define MSUB_AFTER_SIZE(rm, sub)  ((rm)->input + (rm)->inputSize - (sub)->endp)
+
+#define MSUB_BEFORE_LENGTH(rm, sub) \
+    Scm_MBLen((rm)->input, (sub)->startp)
+#define MSUB_LENGTH(rm, sub) \
+    Scm_MBLen((sub)->startp, (sub)->endp)
+#define MSUB_AFTER_LENGTH(rm, sub) \
+    Scm_MBLen((sub)->endp, (rm)->input + (rm)->inputSize)
+
+#define UNCOUNTED(rm, sub)                                      \
+    (((sub)->start    >= 0 ? 0 : MSUB_BEFORE_SIZE(rm, sub))     \
+     + ((sub)->length >= 0 ? 0 : MSUB_SIZE(rm, sub))            \
+     + ((sub)->after  >= 0 ? 0 : MSUB_AFTER_SIZE(rm, sub)))
+
+static void regmatch_count_start(ScmRegMatch *rm, 
+                                 struct ScmRegMatchSub *sub)
+{
+    if (SCM_REG_MATCH_SINGLE_BYTE_P(rm)) {
+        sub->start = MSUB_BEFORE_SIZE(rm, sub);
+    } else if (sub->length >= 0 && sub->after >= 0) {
+        sub->start = rm->inputLen - sub->length - sub->after;
+    } else if (UNCOUNTED(rm, sub) / 2 > MSUB_BEFORE_SIZE(rm, sub)) {
+        sub->start = MSUB_BEFORE_LENGTH(rm, sub);
+    } else {
+        if (sub->length < 0) sub->length = MSUB_LENGTH(rm, sub);
+        if (sub->after < 0)  sub->after  = MSUB_AFTER_LENGTH(rm, sub);
+        sub->start = rm->inputLen - sub->start - sub->length;
+    }
+}
+
+static void regmatch_count_length(ScmRegMatch *rm, 
+                                  struct ScmRegMatchSub *sub)
 {
-    if (sub == NULL) return SCM_FALSE;
-    if (sub->length >= 0) {
-        return Scm_MakeString(sub->startp, sub->endp - sub->startp,
-                              sub->length, 0);
+    if (SCM_REG_MATCH_SINGLE_BYTE_P(rm)) {
+        sub->length = MSUB_SIZE(rm, sub);
+    } else if (sub->start >= 0 && sub->after >= 0) {
+        sub->length = rm->inputLen - sub->start - sub->after;
+    } else if (UNCOUNTED(rm, sub) / 2 > MSUB_SIZE(rm, sub)) {
+        sub->length = MSUB_LENGTH(rm, sub);
+    } else {
+        if (sub->start < 0) sub->start = MSUB_BEFORE_LENGTH(rm, sub);
+        if (sub->after < 0) sub->after = MSUB_AFTER_LENGTH(rm, sub);
+        sub->length = rm->inputLen - sub->start - sub->after;
+    }
+}
+
+static void regmatch_count_after(ScmRegMatch *rm, 
+                                 struct ScmRegMatchSub *sub)
+{
+    if (SCM_REG_MATCH_SINGLE_BYTE_P(rm)) {
+        sub->after = MSUB_AFTER_SIZE(rm, sub);
+    } else if (sub->start >= 0 && sub->length >= 0) {
+        sub->after = rm->inputLen - sub->start - sub->length;
+    } else if (UNCOUNTED(rm, sub) / 2 > MSUB_AFTER_SIZE(rm, sub)) {
+        sub->after = MSUB_AFTER_LENGTH(rm, sub);
     } else {
-        ScmObj s = Scm_MakeString(sub->startp, sub->endp - sub->startp, -1, 0);
-        sub->length = SCM_STRING_BODY_LENGTH(SCM_STRING_BODY(s));
-        return s;
+        if (sub->start < 0)  sub->start  = MSUB_BEFORE_LENGTH(rm, sub);
+        if (sub->length < 0) sub->length = MSUB_LENGTH(rm, sub);
+        sub->after = rm->inputLen - sub->start - sub->length;
     }
 }
 
@@ -2659,17 +2715,11 @@
     return NULL;       /* dummy */
 }
 
-ScmObj Scm_RegMatchSubstr(ScmRegMatch *rm, ScmObj obj)
-{
-    return regmatch_substr(regmatch_ref(rm, obj));
-}
-
 ScmObj Scm_RegMatchStart(ScmRegMatch *rm, ScmObj obj)
 {
     struct ScmRegMatchSub *sub = regmatch_ref(rm, obj);
     if (sub == NULL) return SCM_FALSE;
-    if (sub->start < 0)
-        sub->start = Scm_MBLen(rm->input, sub->startp);;
+    if (sub->start < 0) regmatch_count_start(rm, sub);
     return Scm_MakeInteger(sub->start);
 }
 
@@ -2677,26 +2727,35 @@
 {
     struct ScmRegMatchSub *sub = regmatch_ref(rm, obj);
     if (sub == NULL) return SCM_FALSE;
-    if (sub->start < 0)
-        sub->start = Scm_MBLen(rm->input, sub->startp);
-    if (sub->length < 0)
-        sub->length = Scm_MBLen(sub->startp, sub->endp);
-    return Scm_MakeInteger(sub->start + sub->length);
+    if (sub->after < 0) regmatch_count_after(rm, sub);
+    return Scm_MakeInteger(rm->inputLen - sub->after);
 }
 
 ScmObj Scm_RegMatchBefore(ScmRegMatch *rm, ScmObj obj)
 {
     struct ScmRegMatchSub *sub = regmatch_ref(rm, obj);
     if (sub == NULL) return SCM_FALSE;
-    return Scm_MakeString(rm->input, sub->startp - rm->input, -1, 0);
+    if (sub->start < 0) regmatch_count_start(rm, sub);
+    return Scm_MakeString(rm->input, MSUB_BEFORE_SIZE(rm, sub),
+                          sub->start, 0);
+}
+
+ScmObj Scm_RegMatchSubstr(ScmRegMatch *rm, ScmObj obj)
+{
+    struct ScmRegMatchSub *sub = regmatch_ref(rm, obj);
+    if (sub == NULL) return SCM_FALSE;
+    if (sub->length < 0) regmatch_count_length(rm, sub);
+    return Scm_MakeString(sub->startp, MSUB_SIZE(rm, sub),
+                          sub->length, 0);
 }
 
 ScmObj Scm_RegMatchAfter(ScmRegMatch *rm, ScmObj obj)
 {
     struct ScmRegMatchSub *sub = regmatch_ref(rm, obj);
     if (sub == NULL) return SCM_FALSE;
-    return Scm_MakeString(sub->endp,
-                          rm->input + rm->inputSize - sub->endp, -1, 0);
+    if (sub->after < 0) regmatch_count_after(rm, sub);
+    return Scm_MakeString(sub->endp, MSUB_AFTER_SIZE(rm, sub),
+                          sub->after, 0);
 }
 
 /* for debug */
Index: src/gauche/regexp.h
===================================================================
RCS file: /cvsroot/gauche/Gauche/src/gauche/regexp.h,v
retrieving revision 1.1
diff -u -r1.1 regexp.h
--- src/gauche/regexp.h	10 Mar 2006 07:28:16 -0000	1.1
+++ src/gauche/regexp.h	23 Nov 2006 04:39:59 -0000
@@ -59,9 +59,13 @@
     struct ScmRegMatchSub {
         int start;
         int length;
+        int after;
         const char *startp;
         const char *endp;
     } **matches;
 };
 
+#define SCM_REG_MATCH_SINGLE_BYTE_P(rm) \
+    ((rm)->inputSize == (rm)->inputLen)
+
 #endif /* GAUCHE_REGEXP_H */

• 前の記事 [Gauche-devel-jp] Re: rxmatch-afterなどの改良
• 次の記事 [Gauche-devel-jp] WiLiKi: SPAM 投函の消しこみ作業
• 記事の並び順: [ 日付 ] [ スレッド ] [ 件名 ] [ 著者 ]