From 7f9f56849e1bab8d0f3710638adc111e3ccef3ff Mon Sep 17 00:00:00 2001
From: Norihiro Tanaka <address@hidden>
Date: Wed, 7 May 2014 14:15:01 +0900
Subject: [PATCH] dfa: efficient memory allocation

* src/dfa.c (struct must): Define new member `next'.
(allocmust): Consider the reuse of must.
(dfamust): Don't deallocate must with CAT or OR.
---
 src/dfa.c | 53 +++++++++++++++++++++++++++++++++++++----------------
 1 file changed, 37 insertions(+), 16 deletions(-)

diff --git a/src/dfa.c b/src/dfa.c
index fc2acdc..dee3fed 100644
--- a/src/dfa.c
+++ b/src/dfa.c
@@ -3852,12 +3852,29 @@ struct must
   bool begline;
   bool endline;
   must *prev;
+  must *next;
 };
 
+static void
+resetmust (must *mp)
+{
+  freelist (mp->in);
+  mp->in[0] = NULL;
+  mp->left[0] = mp->right[0] = mp->is[0] = '\0';
+  mp->begline = false;
+  mp->endline = false;
+}
+
 static must *
 allocmust (must *mp)
 {
-  must *new_mp = xmalloc (sizeof *new_mp);
+  must *new_mp;
+  if (mp && mp->next)
+    {
+      resetmust (mp->next);
+      return mp->next;
+    }
+  new_mp = xmalloc (sizeof *new_mp);
   new_mp->in = xzalloc (sizeof *new_mp->in);
   new_mp->left = xzalloc (2);
   new_mp->right = xzalloc (2);
@@ -3865,20 +3882,13 @@ allocmust (must *mp)
   new_mp->begline = false;
   new_mp->endline = false;
   new_mp->prev = mp;
+  new_mp->next = NULL;
+  if (mp)
+    mp->next = new_mp;
   return new_mp;
 }
 
 static void
-resetmust (must *mp)
-{
-  freelist (mp->in);
-  mp->in[0] = NULL;
-  mp->left[0] = mp->right[0] = mp->is[0] = '\0';
-  mp->begline = false;
-  mp->endline = false;
-}
-
-static void
 freemust (must *mp)
 {
   freelist (mp->in);
@@ -3967,7 +3977,6 @@ dfamust (struct dfa *d)
             freelist (lmp->in);
             free (lmp->in);
             lmp->in = new;
-            freemust (rmp);
           }
           break;
 
@@ -4027,7 +4036,6 @@ dfamust (struct dfa *d)
                 lmp->begline = false;
                 lmp->endline = false;
               }
-            freemust (rmp);
           }
           break;
 
@@ -4078,11 +4086,24 @@ done:
       d->musts = dm;
     }
 
-  while (mp)
+  if (mp)
     {
-      must *prev = mp->prev;
+      must *mp_tmp;
+      mp_tmp = mp->prev;
+      while (mp_tmp)
+        {
+          must *prev = mp_tmp->prev;
+          freemust (mp_tmp);
+          mp_tmp = prev;
+        }
+      mp_tmp = mp->next;
+      while (mp_tmp)
+        {
+          must *next = mp_tmp->next;
+          freemust (mp_tmp);
+          mp_tmp = next;
+        }
       freemust (mp);
-      mp = prev;
     }
 }
 
-- 
1.9.2