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