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