IDZEBRA  2.1.2
set.c
Go to the documentation of this file.
1 /* This file is part of the Zebra server.
2  Copyright (C) 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 #if HAVE_CONFIG_H
22 #include <config.h>
23 #endif
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 
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 
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 
74 {
75  assert (st);
76  return NULL;
77 }
78 
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 
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 
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 
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 
190 {
191  return merge_DFASet (st, s, NULL);
192 }
193 
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 
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 
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 }
256 /*
257  * Local variables:
258  * c-basic-offset: 4
259  * c-file-style: "Stroustrup"
260  * indent-tabs-mode: nil
261  * End:
262  * vim: shiftwidth=4 tabstop=8 expandtab
263  */
264 
DFASet freelist
Definition: dfaset.h:34
struct DFASetElement_ * DFASet
int eq_DFASet(DFASetType st, DFASet s1, DFASet s2)
Definition: set.c:249
static DFASet mk_DFASetElement(DFASetType st, int n)
Definition: set.c:79
DFASet union_DFASet(DFASetType st, DFASet s1, DFASet s2)
Definition: set.c:152
struct DFASetElement_ * next
Definition: dfaset.h:28
void pr_DFASet(DFASetType st, DFASet s)
Definition: set.c:227
long used
Definition: dfaset.h:35
void * imalloc(size_t size)
Definition: imalloc.c:43
DFASet cp_DFASet(DFASetType st, DFASet s)
Definition: set.c:189
DFASet merge_DFASet(DFASetType st, DFASet s1, DFASet s2)
Definition: set.c:194
void ifree(void *p)
Definition: imalloc.c:93
DFASet mk_DFASet(DFASetType st)
Definition: set.c:73
DFASet add_DFASet(DFASetType st, DFASet s, int n)
Definition: set.c:135
unsigned hash_DFASet(DFASetType st, DFASet s)
Definition: set.c:238
DFASet rm_DFASet(DFASetType st, DFASet s)
Definition: set.c:115
DFASet alloclist
Definition: dfaset.h:33
DFASetType mk_DFASetType(int chunk)
Definition: set.c:35
int inf_DFASetType(DFASetType st, long *used, long *allocated)
Definition: set.c:50
int chunk
Definition: dfaset.h:36
DFASetType rm_DFASetType(DFASetType st)
Definition: set.c:61
struct DFASetElement_ DFASetElement