dfa/states.c

   1 /*
   2  * Copyright (C) 1994, Index Data I/S
   3  * All rights reserved.
   4  * Sebastian Hammer, Adam Dickmeiss
   5  *
   6  * $Log: states.c,v $
   7  * Revision 1.1  1994-09-26 10:16:58  adam
   8  * First version of dfa module in alex. This version uses yacc to parse
   9  * regular expressions. This should be hand-made instead.
  10  *
  11  */
  12 #include <stdio.h>
  13 #include <assert.h>
  14
  15 #include <stdlib.h>
  16 #include <string.h>
  17
  18 #include <util.h>
  19 #include <dfa.h>
  20 #include "imalloc.h"
  21
  22 #define DFA_CHUNK 200
  23 #define TRAN_CHUNK 800
  24
  25 int init_DFA_states (DFA_states **dfasp, SetType st, int hash)
  26 {
  27     DFA_states *dfas;
  28     DFA_trans *tm;
  29     int i;
  30
  31     dfas = (DFA_states *) imalloc( sizeof(DFA_states) );
  32     assert( dfas );
  33     dfas->hasharray = (DFA_state **) imalloc( sizeof(DFA_state*) * hash );
  34     assert( dfas->hasharray );
  35     *dfasp = dfas;
  36     dfas->freelist = dfas->unmarked = dfas->marked = NULL;
  37     dfas->statemem = NULL;
  38     dfas->hash = hash;
  39     dfas->st = st;
  40     dfas->no = 0;
  41
  42     dfas->transmem = tm = (DFA_trans *) imalloc( sizeof(DFA_trans) );
  43     assert( tm );
  44     tm->next = NULL;
  45     tm->size = TRAN_CHUNK;
  46     tm->ptr = 0;
  47     tm->tran_block = (DFA_tran *) imalloc( sizeof(DFA_tran) * tm->size );
  48     assert( tm->tran_block );
  49
  50     dfas->sortarray = NULL;
  51     for( i=0; i<dfas->hash; i++ )
  52         dfas->hasharray[i] = NULL;
  53     return 0;
  54 }
  55
  56 int rm_DFA_states (DFA_states **dfasp)
  57 {
  58     DFA_states *dfas = *dfasp;
  59     DFA_stateb *sm, *sm1;
  60     DFA_trans  *tm, *tm1;
  61
  62     assert( dfas );
  63     ifree( dfas->hasharray );
  64     ifree( dfas->sortarray );
  65
  66     for( tm=dfas->transmem; tm; tm=tm1 )
  67     {
  68         ifree( tm->tran_block );
  69         tm1 = tm->next;
  70         ifree( tm );
  71     }
  72     for( sm=dfas->statemem; sm; sm=sm1 )
  73     {
  74         ifree( sm->state_block );
  75         sm1 = sm->next;
  76         ifree( sm );
  77     }
  78     ifree( dfas );
  79     *dfasp = NULL;
  80     return 0;
  81 }
  82
  83 int add_DFA_state (DFA_states *dfas, Set *s, DFA_state **sp)
  84 {
  85     int i;
  86     DFA_state *si, **sip;
  87     DFA_stateb *sb;
  88
  89     assert( dfas );
  90     assert( *s );
  91     sip = dfas->hasharray + (hash_Set( dfas->st, *s ) % dfas->hash);
  92     for( si = *sip; si; si=si->link )
  93         if( eq_Set( dfas->st, si->set, *s ) )
  94         {
  95             *sp = si;
  96             *s = rm_Set( dfas->st, *s );
  97             return 0;
  98         }
  99     if( !dfas->freelist )
 100     {
 101         sb = (DFA_stateb *) imalloc( sizeof(*sb) );
 102         sb->next = dfas->statemem;
 103         dfas->statemem = sb;
 104         sb->state_block = si = dfas->freelist =
 105             (DFA_state *) imalloc( sizeof(DFA_state)*DFA_CHUNK);
 106         for( i = 0; i<DFA_CHUNK-1; i++, si++ )
 107             si->next = si+1;
 108         si->next = NULL;
 109     }
 110
 111     si = dfas->freelist;
 112     dfas->freelist = si->next;
 113
 114     si->next = dfas->unmarked;
 115     dfas->unmarked = si;
 116
 117     si->link = *sip;
 118     *sip = si;
 119
 120     si->no = (dfas->no)++;
 121     si->tran_no = 0;
 122     si->set = *s;
 123     *s = NULL;
 124     *sp = si;
 125     return 1;
 126 }
 127
 128 void add_DFA_tran (DFA_states *dfas, DFA_state *s, int ch0, int ch1, int to)
 129 {
 130     DFA_trans *tm;
 131     DFA_tran *t;
 132
 133     tm = dfas->transmem;
 134     if( tm->ptr == tm->size )
 135     {
 136         tm = (DFA_trans *) imalloc( sizeof(DFA_trans) );
 137         assert( tm );
 138         tm->next = dfas->transmem;
 139         dfas->transmem = tm;
 140         tm->size = s->tran_no >= TRAN_CHUNK ? s->tran_no+8 : TRAN_CHUNK;
 141         tm->tran_block = (DFA_tran *) imalloc( sizeof(DFA_tran) * tm->size );
 142         assert( tm->tran_block );
 143         if( s->tran_no )
 144             memcpy( tm->tran_block, s->trans, s->tran_no*sizeof( DFA_tran ) );
 145         tm->ptr = s->tran_no;
 146         s->trans = tm->tran_block;
 147     }
 148     s->tran_no++;
 149     t = tm->tran_block + tm->ptr++;
 150     t->ch[0] = ch0;
 151     t->ch[1] = ch1;
 152     t->to = to;
 153 }
 154
 155 DFA_state *get_DFA_state (DFA_states *dfas)
 156 {
 157     DFA_state *si;
 158     assert( dfas );
 159     if( !(si = dfas->unmarked) )
 160         return NULL;
 161     dfas->unmarked = si->next;
 162     si->next = dfas->marked;
 163     dfas->marked = si;
 164     si->trans = dfas->transmem->tran_block + dfas->transmem->ptr;
 165
 166     return si;
 167 }
 168
 169 void sort_DFA_states (DFA_states *dfas)
 170 {
 171     DFA_state *s;
 172     assert( dfas );
 173     dfas->sortarray = (DFA_state **) imalloc( sizeof(DFA_state *)*dfas->no );
 174     for( s = dfas->marked; s; s=s->next )
 175         dfas->sortarray[s->no] = s;
 176 }