IDZEBRA  2.1.2
bset.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 <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 
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 
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  do
265  ++i;
266  while ((i1=trav_BSet (sh, src, i)) == i);
267  if (i != i0+2)
268  f ('-');
269  if (i-1 == '-')
270  f ('\\');
271  f(i-1);
272  }
273  i = i1;
274  }
275 }
276 
277 
278 /*
279  * Local variables:
280  * c-basic-offset: 4
281  * c-file-style: "Stroustrup"
282  * indent-tabs-mode: nil
283  * End:
284  * vim: shiftwidth=4 tabstop=8 expandtab
285  */
286 
void rm_BSetHandle(BSetHandle **shp)
Definition: bset.c:55
unsigned hash_BSet(BSetHandle *sh, BSet src)
Definition: bset.c:151
BSetWord setarray[1]
Definition: bset.h:36
unsigned short BSetWord
Definition: bset.h:27
int eq_BSet(BSetHandle *sh, BSet dst, BSet src)
Definition: bset.c:171
BSet mk_BSet(BSetHandle **shp)
Definition: bset.c:86
struct BSetHandle_ * setchain
Definition: bset.h:35
void * imalloc(size_t size)
Definition: imalloc.c:43
void add_BSet(BSetHandle *sh, BSet dst, unsigned member)
Definition: bset.c:110
void res_BSet(BSetHandle *sh, BSet dst)
Definition: bset.c:135
void ifree(void *p)
Definition: imalloc.c:93
void union_BSet(BSetHandle *sh, BSet dst, BSet src)
Definition: bset.c:141
unsigned wsize
Definition: bset.h:32
BSetHandle * mk_BSetHandle(int size, int chunk)
Definition: bset.c:37
unsigned test_BSet(BSetHandle *sh, BSet src, unsigned member)
Definition: bset.c:118
BSet cp_BSet(BSetHandle *sh, BSet dst, BSet src)
Definition: bset.c:126
unsigned offset
Definition: bset.h:33
unsigned chunk
Definition: bset.h:34
void pr_BSet(BSetHandle *sh, BSet src)
Definition: bset.c:238
int trav_BSet(BSetHandle *sh, BSet src, unsigned member)
Definition: bset.c:183
#define GET_BIT(s, m)
Definition: bset.c:34
int travi_BSet(BSetHandle *sh, BSet src, unsigned member)
Definition: bset.c:210
BSetWord * BSet
Definition: bset.h:28
void com_BSet(BSetHandle *sh, BSet dst)
Definition: bset.c:162
#define SET_BIT(s, m)
Definition: bset.c:35
int inf_BSetHandle(BSetHandle *sh, long *used, long *allocated)
Definition: bset.c:70
void pr_charBSet(BSetHandle *sh, BSet src, void(*f)(int))
Definition: bset.c:248
unsigned size
Definition: bset.h:31