Subversion Repositories tendra.SVN

Rev

Rev 2 | Details | Compare with Previous | Last modification | View Log | RSS feed

Rev Author Line No. Line
2 7u83 1 
/*
2 
    		 Crown Copyright (c) 1997
3 
 
4 
    This TenDRA(r) Computer Program is subject to Copyright
5 
    owned by the United Kingdom Secretary of State for Defence
6 
    acting through the Defence Evaluation and Research Agency
7 
    (DERA).  It is made available to Recipients with a
8 
    royalty-free licence for its use, reproduction, transfer
9 
    to other parties and amendment for any purpose not excluding
10 
    product development provided that any such use et cetera
11 
    shall be deemed to be acceptance of the following conditions:-
12 
 
13 
        (1) Its Recipients shall ensure that this Notice is
14 
        reproduced upon any copies or amended versions of it;
15 
 
16 
        (2) Any amended version of it shall be clearly marked to
17 
        show both the nature of and the organisation responsible
18 
        for the relevant amendment or amendments;
19 
 
20 
        (3) Its onward transfer from a recipient to another
21 
        party shall be deemed to be that party's acceptance of
22 
        these conditions;
23 
 
24 
        (4) DERA gives no warranty or assurance as to its
25 
        quality or suitability for any purpose and DERA accepts
26 
        no liability whatsoever in relation to any use to which
27 
        it may be put.
28 
*/
29 
 
30 
 
31 
/**** bitvec.c --- Bit vector manipulation.
32 
 *
33 
 ** Author: Steve Folkes <smf@hermes.mod.uk>
34 
 *
35 
 **** Commentary:
36 
 *
37 
 * This file implements the bit vector manipulation routines specified in
38 
 * "bitvec.h".  See that file for more details.
39 
 *
40 
 **** Change Log:
41 
 * $Log: bitvec.c,v $
42 
 * Revision 1.1.1.1  1998/01/17  15:57:43  release
43 
 * First version to be checked into rolling release.
44 
 *
45 
 * Revision 1.2  1994/12/15  09:56:59  smf
46 
 * Brought into line with OSSG C Coding Standards Document, as per
47 
 * "CR94_178.sid+tld-update".
48 
 *
49 
 * Revision 1.1.1.1  1994/07/25  16:05:47  smf
50 
 * Initial import of library shared files.
51 
 *
52 
**/
53 
 
54 
/****************************************************************************/
55 
 
56 
#include "bitvec.h"
57 
 
58 
/*--------------------------------------------------------------------------*/
59 
 
60 
static unsigned			bitvec_size;
61 
static unsigned			bitvec_valid_bits;
62 
static ByteT			bitvec_mask;
63 
 
64 
#define NUM_BITS ((unsigned) (CHAR_BIT))
65 
 
66 
/*--------------------------------------------------------------------------*/
67 
 
68 
void
69 
bitvec_set_size PROTO_N ((size))
70 
		PROTO_T (unsigned size)
71 
{
72 
    bitvec_valid_bits = size;
73 
    bitvec_size       = ((size + NUM_BITS - (unsigned) 1) / NUM_BITS);
74 
    bitvec_mask       = (ByteT) 0;
75 
    if (size % NUM_BITS) {
76 
	unsigned i;
77 
	unsigned mask =0;
78 
 
79 
	for (i = (NUM_BITS - (size % NUM_BITS)); i; i --) {
80 
	    mask >>= 1;
81 
	    mask  |= ((unsigned) 1 << (NUM_BITS - (unsigned) 1));
82 
	}
83 
	bitvec_mask = (ByteT) mask;
84 
    }
85 
    bitvec_mask = (~bitvec_mask);
86 
}
87 
 
88 
void
89 
bitvec_init PROTO_N ((bitvec))
90 
	    PROTO_T (BitVecP bitvec)
91 
{
92 
    bitvec->bits = ALLOCATE_VECTOR (ByteT, bitvec_size);
93 
}
94 
 
95 
void
96 
bitvec_copy PROTO_N ((to, from))
97 
	    PROTO_T (BitVecP to X
98 
		     BitVecP from)
99 
{
100 
    to->bits = ALLOCATE_VECTOR (ByteT, bitvec_size);
101 
    (void) memcpy ((GenericP) (to->bits), (GenericP) (from->bits),
102 
		   (SizeT) bitvec_size);
103 
}
104 
 
105 
void
106 
bitvec_replace PROTO_N ((to, from))
107 
	       PROTO_T (BitVecP to X
108 
			BitVecP from)
109 
{
110 
    (void) memcpy ((GenericP) (to->bits), (GenericP) (from->bits),
111 
		   (SizeT) bitvec_size);
112 
}
113 
 
114 
void
115 
bitvec_empty PROTO_N ((bitvec))
116 
	     PROTO_T (BitVecP bitvec)
117 
{
118 
    (void) memset ((GenericP) (bitvec->bits), 0, (SizeT) bitvec_size);
119 
}
120 
 
121 
BoolT
122 
bitvec_is_empty PROTO_N ((bitvec))
123 
		PROTO_T (BitVecP bitvec)
124 
{
125 
    ByteP    bitvec_bits = (bitvec->bits);
126 
    unsigned bytes       = bitvec_size;
127 
 
128 
    while (bytes --) {
129 
	if (*bitvec_bits ++) {
130 
	    return (FALSE);
131 
	}
132 
    }
133 
    return (TRUE);
134 
}
135 
 
136 
BoolT
137 
bitvec_is_full PROTO_N ((bitvec))
138 
	       PROTO_T (BitVecP bitvec)
139 
{
140 
    ByteP    bitvec_bits = (bitvec->bits);
141 
    unsigned bytes       = bitvec_size;
142 
 
143 
    while (bytes --) {
144 
	ByteT byte = (*bitvec_bits ++);
145 
 
146 
	if (bytes == 0) {
147 
	    byte |= (ByteT) ~bitvec_mask;
148 
	}
149 
	byte = ~byte;
150 
	if (byte) {
151 
	    return (FALSE);
152 
	}
153 
    }
154 
    return (TRUE);
155 
}
156 
 
157 
void
158 
bitvec_set PROTO_N ((bitvec, bit))
159 
	   PROTO_T (BitVecP  bitvec X
160 
		    unsigned bit)
161 
{
162 
    ASSERT (bit < bitvec_valid_bits);
163 
    (bitvec->bits) [bit / NUM_BITS] |= (ByteT) (1 << (bit % NUM_BITS));
164 
}
165 
 
166 
BoolT
167 
bitvec_is_set PROTO_N ((bitvec, bit))
168 
	      PROTO_T (BitVecP  bitvec X
169 
		       unsigned bit)
170 
{
171 
    ASSERT (bit < bitvec_valid_bits);
172 
    return ((bitvec->bits) [bit / NUM_BITS] & ((ByteT) 1 << (bit % NUM_BITS)));
173 
}
174 
 
175 
void
176 
bitvec_or PROTO_N ((to, from))
177 
	  PROTO_T (BitVecP to X
178 
		   BitVecP from)
179 
{
180 
    ByteP    to_bits   = (to->bits);
181 
    ByteP    from_bits = (from->bits);
182 
    unsigned bytes     = bitvec_size;
183 
 
184 
    while (bytes --) {
185 
	(*to_bits ++) |= (*from_bits ++);
186 
    }
187 
}
188 
 
189 
void
190 
bitvec_and PROTO_N ((to, from))
191 
	   PROTO_T (BitVecP to X
192 
		    BitVecP from)
193 
{
194 
    ByteP    to_bits   = (to->bits);
195 
    ByteP    from_bits = (from->bits);
196 
    unsigned bytes     = bitvec_size;
197 
 
198 
    while (bytes --) {
199 
	(*to_bits ++) &= (*from_bits ++);
200 
    }
201 
}
202 
 
203 
void
204 
bitvec_not PROTO_N ((to))
205 
	   PROTO_T (BitVecP to)
206 
{
207 
    ByteP    to_bits = (to->bits);
208 
    unsigned bytes   = bitvec_size;
209 
 
210 
    while (bytes --) {
211 
	(*to_bits) = (~(*to_bits));
212 
	to_bits ++;
213 
    }
214 
    (to->bits) [bitvec_size - 1] &= bitvec_mask;
215 
}
216 
 
217 
BoolT
218 
bitvec_equal PROTO_N ((bitvec1, bitvec2))
219 
	     PROTO_T (BitVecP bitvec1 X
220 
		      BitVecP bitvec2)
221 
{
222 
    ByteP    bitvec1_bits = (bitvec1->bits);
223 
    ByteP    bitvec2_bits = (bitvec2->bits);
224 
    unsigned bytes        = bitvec_size;
225 
 
226 
    while (bytes --) {
227 
	if ((*bitvec1_bits ++) != (*bitvec2_bits ++)) {
228 
	    return (FALSE);
229 
	}
230 
    }
231 
    return (TRUE);
232 
}
233 
 
234 
BoolT
235 
bitvec_intersects PROTO_N ((bitvec1, bitvec2))
236 
		  PROTO_T (BitVecP bitvec1 X
237 
			   BitVecP bitvec2)
238 
{
239 
    ByteP    bitvec1_bits = (bitvec1->bits);
240 
    ByteP    bitvec2_bits = (bitvec2->bits);
241 
    unsigned bytes        = bitvec_size;
242 
 
243 
    while (bytes --) {
244 
	if ((*bitvec1_bits ++) & (*bitvec2_bits ++)) {
245 
	    return (TRUE);
246 
	}
247 
    }
248 
    return (FALSE);
249 
}
250 
 
251 
unsigned
252 
bitvec_num_bits PROTO_N ((bitvec))
253 
		PROTO_T (BitVecP  bitvec)
254 
{
255 
    unsigned i;
256 
    unsigned num_bits = 0;
257 
 
258 
    for (i = 0; i < bitvec_valid_bits; i ++) {
259 
	if (bitvec_is_set (bitvec, i)) {
260 
	    num_bits ++;
261 
	}
262 
    }
263 
    return (num_bits);
264 
}
265 
 
266 
unsigned
267 
bitvec_first_bit PROTO_N ((bitvec))
268 
		 PROTO_T (BitVecP  bitvec)
269 
{
270 
    unsigned i;
271 
 
272 
    for (i = 0; i < bitvec_valid_bits; i ++) {
273 
	if (bitvec_is_set (bitvec, i)) {
274 
	    return (i);
275 
	}
276 
    }
277 
    return (bitvec_valid_bits);
278 
}
279 
 
280 
BoolT
281 
bitvec_next_bit PROTO_N ((bitvec, next_ref))
282 
		PROTO_T (BitVecP   bitvec X
283 
			 unsigned *next_ref)
284 
{
285 
    unsigned i;
286 
 
287 
    for (i = ((*next_ref) + 1); i < bitvec_valid_bits; i ++) {
288 
	if (bitvec_is_set (bitvec, i)) {
289 
	    *next_ref = i;
290 
	    return (TRUE);
291 
	}
292 
    }
293 
    return (FALSE);
294 
}
295 
 
296 
void
297 
bitvec_destroy PROTO_N ((bitvec))
298 
	       PROTO_T (BitVecP bitvec)
299 
{
300 
    DEALLOCATE (bitvec->bits);
301 
}
302 
 
303 
void
304 
write_bitvec_indices PROTO_N ((ostream, bitvec))
305 
		     PROTO_T (OStreamP ostream X
306 
			      BitVecP  bitvec)
307 
{
308 
    unsigned num_bits_set = 0;
309 
    unsigned i;
310 
 
311 
    for (i = 0; i < bitvec_valid_bits; i ++) {
312 
	if (bitvec_is_set (bitvec, i)) {
313 
	    num_bits_set ++;
314 
	}
315 
    }
316 
    for (i = 0; i < bitvec_valid_bits; i ++) {
317 
	if (bitvec_is_set (bitvec, i)) {
318 
	    write_unsigned (ostream, i);
319 
	    num_bits_set --;
320 
	    if (num_bits_set == 1) {
321 
		write_cstring (ostream, " & ");
322 
	    } else if (num_bits_set != 0) {
323 
		write_cstring (ostream, ", ");
324 
	    }
325 
	}
326 
    }
327 
}
328 
 
329 
/*
330 
 * Local variables(smf):
331 
 * eval: (include::add-path-entry "../os-interface" "../generated")
332 
 * end:
333 
**/