Updated footer comment
[idzebra-moved-to-github.git] / dfa / bset.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 <idzebra/util.h>
28 #include <bset.h>
29 #include "imalloc.h"
30
31 #define GET_BIT(s,m) (s[(m)/(sizeof(BSetWord)*8)]&(1<<(m&(sizeof(BSetWord)*8-1)))) 
32 #define SET_BIT(s,m) (s[(m)/(sizeof(BSetWord)*8)]|=(1<<(m&(sizeof(BSetWord)*8-1))))
33
34 BSetHandle *mk_BSetHandle (int size, int chunk)
35 {
36     int wsize = 1+size/(sizeof(BSetWord)*8);    
37     BSetHandle *sh;
38
39     if (chunk <= 1)
40         chunk = 32;
41     sh = (BSetHandle *) imalloc (sizeof(BSetHandle) + 
42                                 chunk*sizeof(BSetWord)*wsize);
43
44     sh->size = size;
45     sh->wsize = wsize;
46     sh->chunk = chunk * wsize;
47     sh->offset = 0;
48     sh->setchain = NULL;
49     return sh;
50 }
51
52 void rm_BSetHandle (BSetHandle **shp)
53 {
54     BSetHandle *sh, *sh1;
55
56     assert (shp);
57     sh = *shp;
58     assert (sh);
59     while (sh)
60     {
61         sh1 = sh->setchain;
62         ifree (sh);
63         sh = sh1;
64     }
65 }
66
67 int inf_BSetHandle (BSetHandle *sh, long *used, long *allocated)
68 {
69     int wsize;
70
71     assert (sh);
72     *used = 0;
73     *allocated = 0;
74     wsize = sh->wsize;
75     do
76     {
77         *used += sh->offset;
78         *allocated += sh->chunk;
79     } while ((sh = sh->setchain));
80     return wsize;
81 }
82
83 BSet mk_BSet (BSetHandle **shp)
84 {
85     BSetHandle *sh, *sh1;
86     unsigned off;
87     assert (shp);
88     sh = *shp;
89     assert (sh);
90
91     off = sh->offset;
92     if ((off + sh->wsize) > sh->chunk)
93     {
94         sh1 = (BSetHandle *) imalloc (sizeof(BSetHandle) + 
95                                      sh->chunk*sizeof(BSetWord));
96         sh1->size = sh->size;
97         sh1->wsize = sh->wsize;
98         sh1->chunk = sh->chunk;
99         off = sh1->offset = 0;
100         sh1->setchain = sh;
101         sh = *shp = sh1;
102     }
103     sh->offset = off + sh->wsize;
104     return sh->setarray + off;
105 }
106
107 void add_BSet (BSetHandle *sh, BSet dst, unsigned member)
108 {
109     assert (dst);
110     assert (sh);
111     assert (member <= sh->size);
112     SET_BIT(dst, member);
113 }
114
115 unsigned test_BSet (BSetHandle *sh, BSet src, unsigned member)
116 {
117     assert (src);
118     assert (sh);
119     assert (member <= sh->size);
120     return GET_BIT (src , member) != 0;
121 }
122
123 BSet cp_BSet (BSetHandle *sh, BSet dst, BSet src)
124 {
125     assert (sh);
126     assert (dst);
127     assert (src);
128     memcpy (dst, src, sh->wsize * sizeof(BSetWord));
129     return dst;
130 }
131
132 void res_BSet (BSetHandle *sh, BSet dst)
133 {
134     assert (dst);
135     memset (dst, 0, sh->wsize * sizeof(BSetWord));
136 }
137
138 void union_BSet (BSetHandle *sh, BSet dst, BSet src)
139 {
140     int i;
141     assert (sh);
142     assert (dst);
143     assert (src);
144     for (i=sh->wsize; --i >= 0;)
145         *dst++ |= *src++;
146 }
147
148 unsigned hash_BSet (BSetHandle *sh, BSet src)
149 {
150     int i;
151     unsigned s = 0;
152     assert (sh);
153     assert (src);
154     for (i=sh->wsize; --i >= 0;)
155         s += *src++;
156     return s;
157 }
158
159 void com_BSet (BSetHandle *sh, BSet dst)
160 {
161     int i;
162     assert (sh);
163     assert (dst);
164     for (i=sh->wsize; --i >= 0; dst++)
165         *dst = ~*dst;
166 }
167
168 int eq_BSet (BSetHandle *sh, BSet dst, BSet src)
169 {
170     int i;
171     assert (sh);
172     assert (dst);
173     assert (src);
174     for (i=sh->wsize; --i >= 0;)
175         if (*dst++ != *src++)
176             return 0;
177     return 1;
178 }
179
180 int trav_BSet (BSetHandle *sh, BSet src, unsigned member)
181 {
182     int i = sh->size - member;
183     BSetWord *sw = src+member/(sizeof(BSetWord)*8);
184     unsigned b = member & (sizeof(BSetWord)*8-1);
185     while(i >= 0)
186         if (b == 0 && *sw == 0)
187         {
188             member += sizeof(BSetWord)*8;
189             ++sw;
190             i -= sizeof(BSetWord)*8;
191         }
192         else if (*sw & (1<<b))
193             return member;
194         else
195         {
196             ++member;
197             --i;
198             if (++b == sizeof(BSetWord)*8)
199             {
200                 b = 0;
201                 ++sw;
202             }
203         }
204     return -1;
205 }
206
207 int travi_BSet (BSetHandle *sh, BSet src, unsigned member)
208 {
209     int i = sh->size - member;
210     BSetWord *sw = src+member/(sizeof(BSetWord)*8);
211     unsigned b = member & (sizeof(BSetWord)*8-1);
212     while(i >= 0)
213         if (b == 0 && *sw == (BSetWord) ~ 0)
214         {
215             member += sizeof(BSetWord)*8;
216             ++sw;
217             i -= sizeof(BSetWord)*8;
218         }
219         else if ((*sw & (1<<b)) == 0)
220             return member;
221         else
222         {
223             ++member;
224             --i;
225             if (++b == sizeof(BSetWord)*8)
226             {
227                 b = 0;
228                 ++sw;
229             }
230         }
231     return -1;
232 }
233
234
235 void pr_BSet (BSetHandle *sh, BSet src)
236 {
237     int i;
238     assert (sh);
239     assert (src);
240     for (i=0; (i=trav_BSet(sh,src,i)) != -1; i++)
241         printf (" %d", i);
242     putchar ('\n');
243 }
244
245 void pr_charBSet (BSetHandle *sh, BSet src, void (*f) (int))
246 {
247     int i0, i1, i;
248
249     assert (sh);
250     assert (src);
251     i = trav_BSet (sh, src, 0);
252     while (i != -1)
253     {
254         i0 = i;
255         if (i == '-')
256             f ('\\');
257         f(i);
258         i1 = trav_BSet (sh, src, ++i);
259         if (i1 == i)
260         {
261             while ((i1=trav_BSet (sh, src, ++i)) == i)
262                 ;
263             if (i != i0+2)
264                 f ('-');
265             if (i-1 == '-')
266                 f ('\\');
267             f(i-1);
268         }
269         i = i1;
270     }
271 }
272
273
274 /*
275  * Local variables:
276  * c-basic-offset: 4
277  * c-file-style: "Stroustrup"
278  * indent-tabs-mode: nil
279  * End:
280  * vim: shiftwidth=4 tabstop=8 expandtab
281  */
282