Updated footer comment
[idzebra-moved-to-github.git] / dfa / set.c
1 /* This file is part of the Zebra server.
2    Copyright (C) 1994-2009 Index Data
3
4 Zebra is free software; you can redistribute it and/or modify it under
5 the terms of the GNU General Public License as published by the Free
6 Software Foundation; either version 2, or (at your option) any later
7 version.
8
9 Zebra is distributed in the hope that it will be useful, but WITHOUT ANY
10 WARRANTY; without even the implied warranty of MERCHANTABILITY or
11 FITNESS FOR A PARTICULAR PURPOSE.  See the GNU General Public License
12 for more details.
13
14 You should have received a copy of the GNU General Public License
15 along with this program; if not, write to the Free Software
16 Foundation, Inc., 51 Franklin St, Fifth Floor, Boston, MA  02110-1301  USA
17
18 */
19
20
21 #include <stdio.h>
22 #include <assert.h>
23
24 #include <stdlib.h>
25 #include <string.h>
26
27 #include <dfaset.h>
28 #include "imalloc.h"
29
30 static DFASet mk_DFASetElement (DFASetType st, int n);
31
32 DFASetType mk_DFASetType (int chunk)
33 {
34     DFASetType st;
35
36     assert (chunk > 8 && chunk < 8000);
37
38     st = (DFASetType) imalloc (sizeof(*st));
39     assert (st);
40
41     st->alloclist = st->freelist = NULL;
42     st->used = 0;
43     st->chunk = chunk;
44     return st;
45 }
46
47 int inf_DFASetType (DFASetType st, long *used, long *allocated)
48 {
49     DFASet s;
50     assert (st);
51     *used = st->used;
52     *allocated = 0;
53     for (s = st->alloclist; s; s = s->next)
54          *allocated += st->chunk;
55     return sizeof (DFASetElement);
56 }
57
58 DFASetType rm_DFASetType (DFASetType st)
59 {
60     DFASet s, s1;
61     for (s = st->alloclist; (s1 = s);)
62     {
63         s = s->next;
64         ifree (s1);
65     }
66     ifree (st);
67     return NULL;
68 }
69
70 DFASet mk_DFASet (DFASetType st)
71 {
72     assert (st);
73     return NULL;
74 }
75
76 static DFASet mk_DFASetElement (DFASetType st, int n)
77 {
78     DFASet s;
79     int i;
80     assert (st);
81
82     assert (st->chunk > 8);
83     if (! st->freelist)
84     {
85         s = (DFASet) imalloc (sizeof(*s) * (1+st->chunk));
86         assert (s);
87         s->next = st->alloclist;
88         st->alloclist = s;
89         st->freelist = ++s;
90         for (i=st->chunk; --i > 0; s++)
91             s->next = s+1;
92         s->next = NULL;
93     }
94     st->used++;
95     s = st->freelist;
96     st->freelist = s->next;
97     s->value = n;
98     return s;
99 }
100
101 #if 0
102 static void rm_DFASetElement (DFASetType st, DFASetElement *p)
103 {
104     assert (st);
105     assert (st->used > 0);
106     p->next = st->freelist;
107     st->freelist = p;
108     st->used--;
109 }
110 #endif
111
112 DFASet rm_DFASet (DFASetType st, DFASet s)
113 {
114     DFASet s1 = s;
115     int i = 1;
116
117     if (s)
118     {
119         while (s->next)
120         {
121             s = s->next;
122             ++i;
123         }
124         s->next = st->freelist;
125         st->freelist = s1;
126         st->used -= i;
127         assert (st->used >= 0);
128     }
129     return NULL;
130 }
131
132 DFASet add_DFASet (DFASetType st, DFASet s, int n)
133 {
134     DFASetElement dummy;
135     DFASet p = &dummy, snew;
136     p->next = s;
137     while (p->next && p->next->value < n)
138         p = p->next;
139     assert (p);
140     if (!(p->next && p->next->value == n))
141     {
142         snew = mk_DFASetElement (st, n);
143         snew->next = p->next;
144         p->next = snew;
145     }
146     return dummy.next;
147 }
148
149 DFASet union_DFASet (DFASetType st, DFASet s1, DFASet s2)
150 {
151     DFASetElement dummy;
152     DFASet p;
153     assert (st);
154
155     for (p = &dummy; s1 && s2;)
156         if (s1->value < s2->value)
157         {
158             p = p->next = s1;
159             s1 = s1->next;
160         }
161         else if (s1->value > s2->value)
162         {
163             p = p->next = mk_DFASetElement (st, s2->value);
164             s2 = s2->next;
165         }
166         else
167         {
168             p = p->next = s1;
169             s1 = s1->next;
170             s2 = s2->next;
171         }
172     if (s1)
173         p->next = s1;
174     else
175     {
176         while (s2)
177         {
178             p = p->next = mk_DFASetElement (st, s2->value);
179             s2 = s2->next;
180         }
181         p->next = NULL;
182     }
183     return dummy.next;
184 }
185
186 DFASet cp_DFASet (DFASetType st, DFASet s)
187 {
188     return merge_DFASet (st, s, NULL);
189 }
190
191 DFASet merge_DFASet (DFASetType st, DFASet s1, DFASet s2)
192 {
193     DFASetElement dummy;
194     DFASet p;
195     assert (st);
196     for (p = &dummy; s1 && s2; p = p->next)
197         if (s1->value < s2->value)
198         {
199             p->next = mk_DFASetElement (st, s1->value);
200             s1 = s1->next;
201         }
202         else if (s1->value > s2->value)
203         {
204             p->next = mk_DFASetElement (st, s2->value);
205             s2 = s2->next;
206         }
207         else
208         {
209             p->next = mk_DFASetElement (st, s1->value);
210             s1 = s1->next;
211             s2 = s2->next;
212         }
213     if (!s1)
214         s1 = s2;
215     while (s1)
216     {
217         p = p->next = mk_DFASetElement (st, s1->value);
218         s1 = s1->next;
219     }
220     p->next = NULL;
221     return dummy.next;
222 }
223
224 void pr_DFASet (DFASetType st, DFASet s)
225 {
226     assert (st);
227     while (s)
228     {
229         printf (" %d", s->value);
230         s = s->next;
231     }
232     putchar ('\n');
233 }
234
235 unsigned hash_DFASet (DFASetType st, DFASet s)
236 {
237     unsigned n = 0;
238     while (s)
239     {
240         n += 11*s->value;
241         s = s->next;
242     }
243     return n;
244 }
245
246 int eq_DFASet (DFASetType st, DFASet s1, DFASet s2)
247 {
248     for (; s1 && s2; s1=s1->next, s2=s2->next)
249         if (s1->value != s2->value)
250             return 0;
251     return s1 == s2;
252 }
253 /*
254  * Local variables:
255  * c-basic-offset: 4
256  * c-file-style: "Stroustrup"
257  * indent-tabs-mode: nil
258  * End:
259  * vim: shiftwidth=4 tabstop=8 expandtab
260  */
261