Add out files
[idzebra-moved-to-github.git] / dfa / set.c
1 /* $Id: set.c,v 1.8 2002-08-02 19:26:55 adam Exp $
2    Copyright (C) 1995,1996,1997,1998,1999,2000,2001,2002
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 <set.h>
31 #include "imalloc.h"
32
33
34 static Set mk_SetElement (SetType st, int n);
35
36 SetType mk_SetType (int chunk)
37 {
38     SetType st;
39
40     assert (chunk > 8 && chunk < 8000);
41
42     st = (SetType) imalloc (sizeof(*st));
43     assert (st);
44
45     st->alloclist = st->freelist = NULL;
46     st->used = 0;
47     st->chunk = chunk;
48     return st;
49 }
50
51 int inf_SetType (SetType st, long *used, long *allocated)
52 {
53     Set s;
54     assert (st);
55     *used = st->used;
56     *allocated = 0;
57     for (s = st->alloclist; s; s = s->next)
58          *allocated += st->chunk;
59     return sizeof (SetElement);
60 }
61
62 SetType rm_SetType (SetType st)
63 {
64     Set s, s1;
65     for (s = st->alloclist; (s1 = s);)
66     {
67         s = s->next;
68         ifree (s1);
69     }
70     ifree (st);
71     return NULL;
72 }
73
74 Set mk_Set (SetType st)
75 {
76     assert (st);
77     return NULL;
78 }
79
80 static Set mk_SetElement (SetType st, int n)
81 {
82     Set s;
83     int i;
84     assert (st);
85
86     assert (st->chunk > 8);
87     if (! st->freelist)
88     {
89         s = (Set) imalloc (sizeof(*s) * (1+st->chunk));
90         assert (s);
91         s->next = st->alloclist;
92         st->alloclist = s;
93         st->freelist = ++s;
94         for (i=st->chunk; --i > 0; s++)
95             s->next = s+1;
96         s->next = NULL;
97     }
98     st->used++;
99     s = st->freelist;
100     st->freelist = s->next;
101     s->value = n;
102     return s;
103 }
104
105 #if 0
106 static void rm_SetElement (SetType st, SetElement *p)
107 {
108     assert (st);
109     assert (st->used > 0);
110     p->next = st->freelist;
111     st->freelist = p;
112     st->used--;
113 }
114 #endif
115
116 Set rm_Set (SetType st, Set s)
117 {
118     Set s1 = s;
119     int i = 1;
120
121     if (s)
122     {
123         while (s->next)
124         {
125             s = s->next;
126             ++i;
127         }
128         s->next = st->freelist;
129         st->freelist = s1;
130         st->used -= i;
131         assert (st->used >= 0);
132     }
133     return NULL;
134 }
135
136 Set add_Set (SetType st, Set s, int n)
137 {
138     SetElement dummy;
139     Set p = &dummy, snew;
140     p->next = s;
141     while (p->next && p->next->value < n)
142         p = p->next;
143     assert (p);
144     if (!(p->next && p->next->value == n))
145     {
146         snew = mk_SetElement (st, n);
147         snew->next = p->next;
148         p->next = snew;
149     }
150     return dummy.next;
151 }
152
153 Set union_Set (SetType st, Set s1, Set s2)
154 {
155     SetElement dummy;
156     Set p;
157     assert (st);
158
159     for (p = &dummy; s1 && s2;)
160         if (s1->value < s2->value)
161         {
162             p = p->next = s1;
163             s1 = s1->next;
164         }
165         else if (s1->value > s2->value)
166         {
167             p = p->next = mk_SetElement (st, s2->value);
168             s2 = s2->next;
169         }
170         else
171         {
172             p = p->next = s1;
173             s1 = s1->next;
174             s2 = s2->next;
175         }
176     if (s1)
177         p->next = s1;
178     else
179     {
180         while (s2)
181         {
182             p = p->next = mk_SetElement (st, s2->value);
183             s2 = s2->next;
184         }
185         p->next = NULL;
186     }
187     return dummy.next;
188 }
189
190 Set cp_Set (SetType st, Set s)
191 {
192     return merge_Set (st, s, NULL);
193 }
194
195 Set merge_Set (SetType st, Set s1, Set s2)
196 {
197     SetElement dummy;
198     Set p;
199     assert (st);
200     for (p = &dummy; s1 && s2; p = p->next)
201         if (s1->value < s2->value)
202         {
203             p->next = mk_SetElement (st, s1->value);
204             s1 = s1->next;
205         }
206         else if (s1->value > s2->value)
207         {
208             p->next = mk_SetElement (st, s2->value);
209             s2 = s2->next;
210         }
211         else
212         {
213             p->next = mk_SetElement (st, s1->value);
214             s1 = s1->next;
215             s2 = s2->next;
216         }
217     if (!s1)
218         s1 = s2;
219     while (s1)
220     {
221         p = p->next = mk_SetElement (st, s1->value);
222         s1 = s1->next;
223     }
224     p->next = NULL;
225     return dummy.next;
226 }
227
228 void pr_Set (SetType st, Set s)
229 {
230     assert (st);
231     while (s)
232     {
233         printf (" %d", s->value);
234         s = s->next;
235     }
236     putchar ('\n');
237 }
238
239 unsigned hash_Set (SetType st, Set s)
240 {
241     unsigned n = 0;
242     while (s)
243     {
244         n += 11*s->value;
245         s = s->next;
246     }
247     return n;
248 }
249
250 int eq_Set (SetType st, Set s1, Set s2)
251 {
252     for (; s1 && s2; s1=s1->next, s2=s2->next)
253         if (s1->value != s2->value)
254             return 0;
255     return s1 == s2;
256 }