rx/rxunfa.c

   1 /* classes: src_files */
   2
   3 /*      Copyright (C) 1995, 1996 Tom Lord
   4  *
   5  * This program is free software; you can redistribute it and/or modify
   6  * it under the terms of the GNU Library General Public License as published by
   7  * the Free Software Foundation; either version 2, or (at your option)
   8  * any later version.
   9  *
  10  * This program is distributed in the hope that it will be useful,
  11  * but WITHOUT ANY WARRANTY; without even the implied warranty of
  12  * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
  13  * GNU Library General Public License for more details.
  14  *
  15  * You should have received a copy of the GNU Library General Public License
  16  * along with this software; see the file COPYING.  If not, write to
  17  * the Free Software Foundation, 59 Temple Place - Suite 330,
  18  * Boston, MA 02111-1307, USA.
  19  */
  20
  21
  22 \f
  23 #include "rxall.h"
  24 #include "rx.h"
  25 #include "rxunfa.h"
  26 #include "rxnfa.h"
  27 \f
  28
  29 #ifdef __STDC__
  30 static int
  31 unfa_equal (void * va, void * vb)
  32 #else
  33 static int
  34 unfa_equal (va, vb)
  35      void * va;
  36      void * vb;
  37 #endif
  38 {
  39   return rx_rexp_equal ((struct rexp_node *)va, (struct rexp_node *)vb);
  40 }
  41
  42
  43 struct rx_hash_rules unfa_rules = { unfa_equal, 0, 0, 0, 0 };
  44
  45
  46 #ifdef __STDC__
  47 static struct rx_cached_rexp *
  48 canonical_unfa (struct rx_hash * table, struct rexp_node * rexp, int cset_size)
  49 #else
  50 static struct rx_cached_rexp *
  51 canonical_unfa (table, rexp, cset_size)
  52      struct rx_hash * table;
  53      struct rexp_node * rexp;
  54      int cset_size;
  55 #endif
  56 {
  57   struct rx_hash_item * it;
  58   it = rx_hash_store (table, rx_rexp_hash (rexp, 0), rexp, &unfa_rules);
  59
  60   if (it->binding == 0)
  61     {
  62       struct rx_cached_rexp * cr;
  63
  64       if (it->data == (void *)rexp)
  65         rx_save_rexp (rexp);
  66
  67       cr = (struct rx_cached_rexp *)malloc (sizeof (*cr));
  68       rx_bzero ((char *)cr, sizeof (*cr));
  69       if (!cr)
  70         return 0;
  71       it->binding = (void *)cr;
  72       cr->unfa.nfa = 0;
  73       cr->unfa.exp = rexp;
  74       cr->hash_item = it;
  75       rx_save_rexp (rexp);
  76     }
  77   return (struct rx_cached_rexp *)it->binding;
  78 }
  79
  80
  81 #ifdef __STDC__
  82 static struct rx *
  83 rx_unfa_rx (struct rx_cached_rexp * cr, struct rexp_node * exp, int cset_size)
  84 #else
  85 static struct rx *
  86 rx_unfa_rx (cr, exp, cset_size)
  87      struct rx_cached_rexp * cr;
  88      struct rexp_node * exp;
  89      int cset_size;
  90 #endif
  91 {
  92   struct rx * new_rx;
  93
  94   if (cr->unfa.nfa)
  95     return cr->unfa.nfa;
  96
  97   new_rx = rx_make_rx (cset_size);
  98   if (!new_rx)
  99     return 0;
 100   {
 101     struct rx_nfa_state * start;
 102     struct rx_nfa_state * end;
 103     start = end = 0;
 104     if (!rx_build_nfa (new_rx, exp, &start, &end))
 105       {
 106         free (new_rx);
 107         return 0;
 108       }
 109     new_rx->start_nfa_states = start;
 110     end->is_final = 1;
 111     start->is_start = 1;
 112     {
 113       struct rx_nfa_state * s;
 114       int x;
 115       x = 0;
 116       for (s = new_rx->nfa_states; s; s = s->next)
 117         s->id = x++;
 118     }
 119   }
 120   cr->unfa.nfa = new_rx;
 121   return new_rx;
 122 }
 123
 124
 125 \f
 126
 127 #ifdef __STDC__
 128 struct rx_unfaniverse *
 129 rx_make_unfaniverse (int delay)
 130 #else
 131 struct rx_unfaniverse *
 132 rx_make_unfaniverse (delay)
 133      int delay;
 134 #endif
 135 {
 136   struct rx_unfaniverse * it;
 137   it = (struct rx_unfaniverse *)malloc (sizeof (*it));
 138   if (!it) return 0;
 139   rx_bzero ((char *)it, sizeof (*it));
 140   it->delay = delay;
 141   return it;
 142 }
 143
 144
 145 #ifdef __STDC__
 146 void
 147 rx_free_unfaniverse (struct rx_unfaniverse * it)
 148 #else
 149 void
 150 rx_free_unfaniverse (it)
 151      struct rx_unfaniverse * it;
 152 #endif
 153 {
 154 }
 155
 156
 157
 158 \f
 159
 160 #ifdef __STDC__
 161 struct rx_unfa *
 162 rx_unfa (struct rx_unfaniverse * unfaniverse, struct rexp_node * exp, int cset_size)
 163 #else
 164 struct rx_unfa *
 165 rx_unfa (unfaniverse, exp, cset_size)
 166      struct rx_unfaniverse * unfaniverse;
 167      struct rexp_node * exp;
 168      int cset_size;
 169 #endif
 170 {
 171   struct rx_cached_rexp * cr;
 172   if (exp && exp->cr)
 173     cr = exp->cr;
 174   else
 175     {
 176       cr = canonical_unfa (&unfaniverse->table, exp, cset_size);
 177       if (exp)
 178         exp->cr = cr;
 179     }
 180   if (!cr)
 181     return 0;
 182   if (cr->next)
 183     {
 184       if (unfaniverse->free_queue == cr)
 185         {
 186           unfaniverse->free_queue = cr->next;
 187           if (unfaniverse->free_queue == cr)
 188             unfaniverse->free_queue = 0;
 189         }
 190       cr->next->prev = cr->prev;
 191       cr->prev->next = cr->next;
 192       cr->next = 0;
 193       cr->prev = 0;
 194       --unfaniverse->delayed;
 195     }
 196   ++cr->unfa.refs;
 197   cr->unfa.cset_size = cset_size;
 198   cr->unfa.verse = unfaniverse;
 199   rx_unfa_rx (cr, exp, cset_size);
 200   return &cr->unfa;
 201 }
 202
 203
 204 #ifdef __STDC__
 205 void
 206 rx_free_unfa (struct rx_unfa * unfa)
 207 #else
 208 void
 209 rx_free_unfa (unfa)
 210      struct rx_unfa * unfa;
 211 #endif
 212 {
 213   struct rx_cached_rexp * cr;
 214   cr = (struct rx_cached_rexp *)unfa;
 215   if (!cr)
 216     return;
 217   if (!--cr->unfa.refs)
 218     {
 219       if (!unfa->verse->free_queue)
 220         {
 221           unfa->verse->free_queue = cr;
 222           cr->next = cr->prev = cr;
 223         }
 224       else
 225         {
 226           cr->next = unfa->verse->free_queue;
 227           cr->prev = unfa->verse->free_queue->prev;
 228           cr->next->prev = cr;
 229           cr->prev->next = cr;
 230         }
 231
 232       ++unfa->verse->delayed;
 233       while (unfa->verse->delayed > unfa->verse->delay)
 234         {
 235           struct rx_cached_rexp * it;
 236           it = unfa->verse->free_queue;
 237           unfa->verse->free_queue = it->next;
 238           if (!--unfa->verse->delayed)
 239             unfa->verse->free_queue = 0;
 240           it->prev->next = it->next;
 241           it->next->prev = it->prev;
 242           if (it->unfa.exp)
 243             it->unfa.exp->cr = 0;
 244           rx_free_rexp ((struct rexp_node *)it->hash_item->data);
 245           rx_hash_free (it->hash_item, &unfa_rules);
 246           rx_free_rx (it->unfa.nfa);
 247           rx_free_rexp (it->unfa.exp);
 248           free (it);
 249           if (it == cr)
 250             break;
 251         }
 252     }
 253   else
 254     return;
 255 }
 256
 257
 258 #ifdef __STDC__
 259 void
 260 rx_save_unfa (struct rx_unfa * unfa)
 261 #else
 262 void
 263 rx_save_unfa (unfa)
 264      struct rx_unfa * unfa;
 265 #endif
 266 {
 267   ++(unfa->refs);
 268 }
 269