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