Subversion Repositories tendra.SVN

Rev

Rev 5 | Show entire file | Ignore whitespace | Details | Blame | Last modification | View Log | RSS feed

Rev 5 Rev 6
Line -... Line 1...
- 
 
 1 
/*
- 
 
 2 
 * Copyright (c) 2002-2005 The TenDRA Project <http://www.tendra.org/>.
- 
 
 3 
 * All rights reserved.
- 
 
 4 
 *
- 
 
 5 
 * Redistribution and use in source and binary forms, with or without
- 
 
 6 
 * modification, are permitted provided that the following conditions are met:
- 
 
 7 
 *
- 
 
 8 
 * 1. Redistributions of source code must retain the above copyright notice,
- 
 
 9 
 *    this list of conditions and the following disclaimer.
- 
 
 10 
 * 2. Redistributions in binary form must reproduce the above copyright notice,
- 
 
 11 
 *    this list of conditions and the following disclaimer in the documentation
- 
 
 12 
 *    and/or other materials provided with the distribution.
- 
 
 13 
 * 3. Neither the name of The TenDRA Project nor the names of its contributors
- 
 
 14 
 *    may be used to endorse or promote products derived from this software
- 
 
 15 
 *    without specific, prior written permission.
- 
 
 16 
 *
- 
 
 17 
 * THIS SOFTWARE IS PROVIDED BY THE COPYRIGHT HOLDERS AND CONTRIBUTORS ``AS
- 
 
 18 
 * IS'' AND ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO,
- 
 
 19 
 * THE IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR
- 
 
 20 
 * PURPOSE ARE DISCLAIMED.  IN NO EVENT SHALL THE COPYRIGHT HOLDERS OR
- 
 
 21 
 * CONTRIBUTORS BE LIABLE FOR ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL,
- 
 
 22 
 * EXEMPLARY OR CONSEQUENTIAL DAMAGES (INCLUDING, BUT NOT LIMITED TO,
- 
 
 23 
 * PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES; LOSS OF USE, DATA, OR PROFITS;
- 
 
 24 
 * OR BUSINESS INTERRUPTION) HOWEVER CAUSED AND ON ANY THEORY OF LIABILITY,
- 
 
 25 
 * WHETHER IN CONTRACT, STRICT LIABILITY, OR TORT (INCLUDING NEGLIGENCE OR
- 
 
 26 
 * OTHERWISE) ARISING IN ANY WAY OUT OF THE USE OF THIS SOFTWARE, EVEN IF
- 
 
 27 
 * ADVISED OF THE POSSIBILITY OF SUCH DAMAGE.
- 
 
 28 
 *
- 
 
 29 
 * $Id$
- 
 
 30 
 */
1 
/*
 31 
/*
2 
    		 Crown Copyright (c) 1997
 32 
    		 Crown Copyright (c) 1997
3
33 
 
4 
    This TenDRA(r) Computer Program is subject to Copyright
 34 
    This TenDRA(r) Computer Program is subject to Copyright
5 
    owned by the United Kingdom Secretary of State for Defence
 35 
    owned by the United Kingdom Secretary of State for Defence
6 
    acting through the Defence Evaluation and Research Agency
 36 
    acting through the Defence Evaluation and Research Agency
7 
    (DERA).  It is made available to Recipients with a
 37 
    (DERA).  It is made available to Recipients with a
8 
    royalty-free licence for its use, reproduction, transfer
 38 
    royalty-free licence for its use, reproduction, transfer
9 
    to other parties and amendment for any purpose not excluding
 39 
    to other parties and amendment for any purpose not excluding
10 
    product development provided that any such use et cetera
 40 
    product development provided that any such use et cetera
11 
    shall be deemed to be acceptance of the following conditions:-
 41 
    shall be deemed to be acceptance of the following conditions:-
12
42 
 
13 
        (1) Its Recipients shall ensure that this Notice is
 43 
        (1) Its Recipients shall ensure that this Notice is
14 
        reproduced upon any copies or amended versions of it;
 44 
        reproduced upon any copies or amended versions of it;
15
45 
 
16 
        (2) Any amended version of it shall be clearly marked to
 46 
        (2) Any amended version of it shall be clearly marked to
17 
        show both the nature of and the organisation responsible
 47 
        show both the nature of and the organisation responsible
18 
        for the relevant amendment or amendments;
 48 
        for the relevant amendment or amendments;
19
49 
 
20 
        (3) Its onward transfer from a recipient to another
 50 
        (3) Its onward transfer from a recipient to another
21 
        party shall be deemed to be that party's acceptance of
 51 
        party shall be deemed to be that party's acceptance of
22 
        these conditions;
 52 
        these conditions;
23
53 
 
24 
        (4) DERA gives no warranty or assurance as to its
 54 
        (4) DERA gives no warranty or assurance as to its
25 
        quality or suitability for any purpose and DERA accepts
 55 
        quality or suitability for any purpose and DERA accepts
26 
        no liability whatsoever in relation to any use to which
 56 
        no liability whatsoever in relation to any use to which
27 
        it may be put.
 57 
        it may be put.
28 
*/
 58 
*/
Line 55... Line 85...
55 
 
 85 
 
56 
#include "bitvec.h"
 86 
#include "bitvec.h"
57 
 
 87 
 
58 
/*--------------------------------------------------------------------------*/
 88 
/*--------------------------------------------------------------------------*/
59 
 
 89 
 
60 
static unsigned			bitvec_size;
 90 
static unsigned		bitvec_size;
61 
static unsigned			bitvec_valid_bits;
 91 
static unsigned		bitvec_valid_bits;
62 
static ByteT			bitvec_mask;
 92 
static ByteT		bitvec_mask;
63 
 
 93 
 
64 
#define NUM_BITS ((unsigned) (CHAR_BIT))
 94 
#define NUM_BITS	((unsigned)(CHAR_BIT))
65 
 
 95 
 
66 
/*--------------------------------------------------------------------------*/
 96 
/*--------------------------------------------------------------------------*/
67 
 
 97 
 
68 
void
 98 
void
69 
bitvec_set_size PROTO_N ((size))
 99 
bitvec_set_size(unsigned size)
70 
		PROTO_T (unsigned size)
 - 
 
71 
{
 100 
{
72 
    bitvec_valid_bits = size;
 101 
    bitvec_valid_bits = size;
73 
    bitvec_size       = ((size + NUM_BITS - (unsigned) 1) / NUM_BITS);
 102 
    bitvec_size       = ((size + NUM_BITS - (unsigned)1) / NUM_BITS);
74 
    bitvec_mask       = (ByteT) 0;
 103 
    bitvec_mask       = (ByteT)0;
75 
    if (size % NUM_BITS) {
 104 
    if (size % NUM_BITS) {
76 
	unsigned i;
 105 
	unsigned i;
77 
	unsigned mask =0;
 106 
	unsigned mask =0;
78 
 
 107 
 
79 
	for (i = (NUM_BITS - (size % NUM_BITS)); i; i --) {
 108 
	for (i = (NUM_BITS - (size % NUM_BITS)); i; i--) {
80 
	    mask >>= 1;
 109 
	    mask >>= 1;
81 
	    mask  |= ((unsigned) 1 << (NUM_BITS - (unsigned) 1));
 110 
	    mask  |= ((unsigned)1 << (NUM_BITS - (unsigned)1));
82 
	}
 111 
	}
83 
	bitvec_mask = (ByteT) mask;
 112 
	bitvec_mask = (ByteT)mask;
84 
    }
 113 
    }
85 
    bitvec_mask = (~bitvec_mask);
 114 
    bitvec_mask = (~bitvec_mask);
86 
}
 115 
}
87 
 
 116 
 
88 
void
 117 
void
89 
bitvec_init PROTO_N ((bitvec))
 118 
bitvec_init(BitVecP bitvec)
90 
	    PROTO_T (BitVecP bitvec)
 - 
 
91 
{
 119 
{
92 
    bitvec->bits = ALLOCATE_VECTOR (ByteT, bitvec_size);
 120 
    bitvec->bits = ALLOCATE_VECTOR(ByteT, bitvec_size);
93 
}
 121 
}
94 
 
 122 
 
95 
void
 123 
void
96 
bitvec_copy PROTO_N ((to, from))
 124 
bitvec_copy(BitVecP to, BitVecP from)
97 
	    PROTO_T (BitVecP to X
 - 
 
98 
		     BitVecP from)
 - 
 
99 
{
 125 
{
100 
    to->bits = ALLOCATE_VECTOR (ByteT, bitvec_size);
 126 
    to->bits = ALLOCATE_VECTOR(ByteT, bitvec_size);
101 
    (void) memcpy ((GenericP) (to->bits), (GenericP) (from->bits),
 127 
   (void)memcpy((GenericP)(to->bits), (GenericP)(from->bits),
102 
		   (SizeT) bitvec_size);
 128 
		(SizeT)bitvec_size);
103 
}
 129 
}
104 
 
 130 
 
105 
void
 131 
void
106 
bitvec_replace PROTO_N ((to, from))
 132 
bitvec_replace(BitVecP to, BitVecP from)
107 
	       PROTO_T (BitVecP to X
 - 
 
108 
			BitVecP from)
 - 
 
109 
{
 133 
{
110 
    (void) memcpy ((GenericP) (to->bits), (GenericP) (from->bits),
 134 
   (void)memcpy((GenericP)(to->bits), (GenericP)(from->bits),
111 
		   (SizeT) bitvec_size);
 135 
		(SizeT)bitvec_size);
112 
}
 136 
}
113 
 
 137 
 
114 
void
 138 
void
115 
bitvec_empty PROTO_N ((bitvec))
 139 
bitvec_empty(BitVecP bitvec)
116 
	     PROTO_T (BitVecP bitvec)
 - 
 
117 
{
 140 
{
118 
    (void) memset ((GenericP) (bitvec->bits), 0, (SizeT) bitvec_size);
 141 
   (void)memset((GenericP)(bitvec->bits), 0, (SizeT)bitvec_size);
119 
}
 142 
}
120 
 
 143 
 
121 
BoolT
 144 
BoolT
122 
bitvec_is_empty PROTO_N ((bitvec))
 145 
bitvec_is_empty(BitVecP bitvec)
123 
		PROTO_T (BitVecP bitvec)
 - 
 
124 
{
 146 
{
125 
    ByteP    bitvec_bits = (bitvec->bits);
 147 
    ByteP    bitvec_bits = (bitvec->bits);
126 
    unsigned bytes       = bitvec_size;
 148 
    unsigned bytes       = bitvec_size;
127 
 
 149 
 
128 
    while (bytes --) {
 150 
    while (bytes--) {
129 
	if (*bitvec_bits ++) {
 151 
	if (*bitvec_bits++) {
130 
	    return (FALSE);
 152 
	    return(FALSE);
131 
	}
 153 
	}
132 
    }
 154 
    }
133 
    return (TRUE);
 155 
    return(TRUE);
134 
}
 156 
}
135 
 
 157 
 
136 
BoolT
 158 
BoolT
137 
bitvec_is_full PROTO_N ((bitvec))
 159 
bitvec_is_full(BitVecP bitvec)
138 
	       PROTO_T (BitVecP bitvec)
 - 
 
139 
{
 160 
{
140 
    ByteP    bitvec_bits = (bitvec->bits);
 161 
    ByteP    bitvec_bits = (bitvec->bits);
141 
    unsigned bytes       = bitvec_size;
 162 
    unsigned bytes       = bitvec_size;
142 
 
 163 
 
143 
    while (bytes --) {
 164 
    while (bytes--) {
144 
	ByteT byte = (*bitvec_bits ++);
 165 
	ByteT byte = (*bitvec_bits++);
145 
 
 166 
 
146 
	if (bytes == 0) {
 167 
	if (bytes == 0) {
147 
	    byte |= (ByteT) ~bitvec_mask;
 168 
	    byte |= (ByteT)~bitvec_mask;
148 
	}
 169 
	}
149 
	byte = ~byte;
 170 
	byte = ~byte;
150 
	if (byte) {
 171 
	if (byte) {
151 
	    return (FALSE);
 172 
	    return(FALSE);
152 
	}
 173 
	}
153 
    }
 174 
    }
154 
    return (TRUE);
 175 
    return(TRUE);
155 
}
 176 
}
156 
 
 177 
 
157 
void
 178 
void
158 
bitvec_set PROTO_N ((bitvec, bit))
 179 
bitvec_set(BitVecP bitvec, unsigned bit)
159 
	   PROTO_T (BitVecP  bitvec X
 - 
 
160 
		    unsigned bit)
 - 
 
161 
{
 180 
{
162 
    ASSERT (bit < bitvec_valid_bits);
 181 
    ASSERT(bit < bitvec_valid_bits);
163 
    (bitvec->bits) [bit / NUM_BITS] |= (ByteT) (1 << (bit % NUM_BITS));
 182 
   (bitvec->bits)[bit / NUM_BITS] |= (ByteT)(1 << (bit % NUM_BITS));
164 
}
 183 
}
165 
 
 184 
 
166 
BoolT
 185 
BoolT
167 
bitvec_is_set PROTO_N ((bitvec, bit))
 186 
bitvec_is_set(BitVecP bitvec, unsigned bit)
168 
	      PROTO_T (BitVecP  bitvec X
 - 
 
169 
		       unsigned bit)
 - 
 
170 
{
 187 
{
171 
    ASSERT (bit < bitvec_valid_bits);
 188 
    ASSERT(bit < bitvec_valid_bits);
172 
    return ((bitvec->bits) [bit / NUM_BITS] & ((ByteT) 1 << (bit % NUM_BITS)));
 189 
    return((bitvec->bits)[bit / NUM_BITS] & ((ByteT)1 << (bit % NUM_BITS)));
173 
}
 190 
}
174 
 
 191 
 
175 
void
 192 
void
176 
bitvec_or PROTO_N ((to, from))
 193 
bitvec_or(BitVecP to, BitVecP from)
177 
	  PROTO_T (BitVecP to X
 - 
 
178 
		   BitVecP from)
 - 
 
179 
{
 194 
{
180 
    ByteP    to_bits   = (to->bits);
 195 
    ByteP    to_bits   = (to->bits);
181 
    ByteP    from_bits = (from->bits);
 196 
    ByteP    from_bits = (from->bits);
182 
    unsigned bytes     = bitvec_size;
 197 
    unsigned bytes     = bitvec_size;
183 
 
 198 
 
184 
    while (bytes --) {
 199 
    while (bytes--) {
185 
	(*to_bits ++) |= (*from_bits ++);
 200 
	(*to_bits++) |= (*from_bits++);
186 
    }
 201 
    }
187 
}
 202 
}
188 
 
 203 
 
189 
void
 204 
void
190 
bitvec_and PROTO_N ((to, from))
 205 
bitvec_and(BitVecP to, BitVecP from)
191 
	   PROTO_T (BitVecP to X
 - 
 
192 
		    BitVecP from)
 - 
 
193 
{
 206 
{
194 
    ByteP    to_bits   = (to->bits);
 207 
    ByteP    to_bits   = (to->bits);
195 
    ByteP    from_bits = (from->bits);
 208 
    ByteP    from_bits = (from->bits);
196 
    unsigned bytes     = bitvec_size;
 209 
    unsigned bytes     = bitvec_size;
197 
 
 210 
 
198 
    while (bytes --) {
 211 
    while (bytes--) {
199 
	(*to_bits ++) &= (*from_bits ++);
 212 
	(*to_bits++) &= (*from_bits++);
200 
    }
 213 
    }
201 
}
 214 
}
202 
 
 215 
 
203 
void
 216 
void
204 
bitvec_not PROTO_N ((to))
 217 
bitvec_not(BitVecP to)
205 
	   PROTO_T (BitVecP to)
 - 
 
206 
{
 218 
{
207 
    ByteP    to_bits = (to->bits);
 219 
    ByteP    to_bits = (to->bits);
208 
    unsigned bytes   = bitvec_size;
 220 
    unsigned bytes   = bitvec_size;
209 
 
 221 
 
210 
    while (bytes --) {
 222 
    while (bytes--) {
211 
	(*to_bits) = (~(*to_bits));
 223 
	(*to_bits) = (~(*to_bits));
212 
	to_bits ++;
 224 
	to_bits++;
213 
    }
 225 
    }
214 
    (to->bits) [bitvec_size - 1] &= bitvec_mask;
 226 
   (to->bits)[bitvec_size - 1] &= bitvec_mask;
215 
}
 227 
}
216 
 
 228 
 
217 
BoolT
 229 
BoolT
218 
bitvec_equal PROTO_N ((bitvec1, bitvec2))
 230 
bitvec_equal(BitVecP bitvec1, BitVecP bitvec2)
219 
	     PROTO_T (BitVecP bitvec1 X
 - 
 
220 
		      BitVecP bitvec2)
 - 
 
221 
{
 231 
{
222 
    ByteP    bitvec1_bits = (bitvec1->bits);
 232 
    ByteP    bitvec1_bits = (bitvec1->bits);
223 
    ByteP    bitvec2_bits = (bitvec2->bits);
 233 
    ByteP    bitvec2_bits = (bitvec2->bits);
224 
    unsigned bytes        = bitvec_size;
 234 
    unsigned bytes        = bitvec_size;
225 
 
 235 
 
226 
    while (bytes --) {
 236 
    while (bytes--) {
227 
	if ((*bitvec1_bits ++) != (*bitvec2_bits ++)) {
 237 
	if ((*bitvec1_bits++) != (*bitvec2_bits++)) {
228 
	    return (FALSE);
 238 
	    return(FALSE);
229 
	}
 239 
	}
230 
    }
 240 
    }
231 
    return (TRUE);
 241 
    return(TRUE);
232 
}
 242 
}
233 
 
 243 
 
234 
BoolT
 244 
BoolT
235 
bitvec_intersects PROTO_N ((bitvec1, bitvec2))
 245 
bitvec_intersects(BitVecP bitvec1, BitVecP bitvec2)
236 
		  PROTO_T (BitVecP bitvec1 X
 - 
 
237 
			   BitVecP bitvec2)
 - 
 
238 
{
 246 
{
239 
    ByteP    bitvec1_bits = (bitvec1->bits);
 247 
    ByteP    bitvec1_bits = (bitvec1->bits);
240 
    ByteP    bitvec2_bits = (bitvec2->bits);
 248 
    ByteP    bitvec2_bits = (bitvec2->bits);
241 
    unsigned bytes        = bitvec_size;
 249 
    unsigned bytes        = bitvec_size;
242 
 
 250 
 
243 
    while (bytes --) {
 251 
    while (bytes--) {
244 
	if ((*bitvec1_bits ++) & (*bitvec2_bits ++)) {
 252 
	if ((*bitvec1_bits++) & (*bitvec2_bits++)) {
245 
	    return (TRUE);
 253 
	    return(TRUE);
246 
	}
 254 
	}
247 
    }
 255 
    }
248 
    return (FALSE);
 256 
    return(FALSE);
249 
}
 257 
}
250 
 
 258 
 
251 
unsigned
 259 
unsigned
252 
bitvec_num_bits PROTO_N ((bitvec))
 260 
bitvec_num_bits(BitVecP bitvec)
253 
		PROTO_T (BitVecP  bitvec)
 - 
 
254 
{
 261 
{
255 
    unsigned i;
 262 
    unsigned i;
256 
    unsigned num_bits = 0;
 263 
    unsigned num_bits = 0;
257 
 
 264 
 
258 
    for (i = 0; i < bitvec_valid_bits; i ++) {
 265 
    for (i = 0; i < bitvec_valid_bits; i++) {
259 
	if (bitvec_is_set (bitvec, i)) {
 266 
	if (bitvec_is_set(bitvec, i)) {
260 
	    num_bits ++;
 267 
	    num_bits++;
261 
	}
 268 
	}
262 
    }
 269 
    }
263 
    return (num_bits);
 270 
    return(num_bits);
264 
}
 271 
}
265 
 
 272 
 
266 
unsigned
 273 
unsigned
267 
bitvec_first_bit PROTO_N ((bitvec))
 274 
bitvec_first_bit(BitVecP bitvec)
268 
		 PROTO_T (BitVecP  bitvec)
 - 
 
269 
{
 275 
{
270 
    unsigned i;
 276 
    unsigned i;
271 
 
 277 
 
272 
    for (i = 0; i < bitvec_valid_bits; i ++) {
 278 
    for (i = 0; i < bitvec_valid_bits; i++) {
273 
	if (bitvec_is_set (bitvec, i)) {
 279 
	if (bitvec_is_set(bitvec, i)) {
274 
	    return (i);
 280 
	    return(i);
275 
	}
 281 
	}
276 
    }
 282 
    }
277 
    return (bitvec_valid_bits);
 283 
    return(bitvec_valid_bits);
278 
}
 284 
}
279 
 
 285 
 
280 
BoolT
 286 
BoolT
281 
bitvec_next_bit PROTO_N ((bitvec, next_ref))
 287 
bitvec_next_bit(BitVecP bitvec, unsigned *next_ref)
282 
		PROTO_T (BitVecP   bitvec X
 - 
 
283 
			 unsigned *next_ref)
 - 
 
284 
{
 288 
{
285 
    unsigned i;
 289 
    unsigned i;
286 
 
 290 
 
287 
    for (i = ((*next_ref) + 1); i < bitvec_valid_bits; i ++) {
 291 
    for (i = ((*next_ref) + 1); i < bitvec_valid_bits; i++) {
288 
	if (bitvec_is_set (bitvec, i)) {
 292 
	if (bitvec_is_set(bitvec, i)) {
289 
	    *next_ref = i;
 293 
	    *next_ref = i;
290 
	    return (TRUE);
 294 
	    return(TRUE);
291 
	}
 295 
	}
292 
    }
 296 
    }
293 
    return (FALSE);
 297 
    return(FALSE);
294 
}
 298 
}
295 
 
 299 
 
296 
void
 300 
void
297 
bitvec_destroy PROTO_N ((bitvec))
 301 
bitvec_destroy(BitVecP bitvec)
298 
	       PROTO_T (BitVecP bitvec)
 - 
 
299 
{
 302 
{
300 
    DEALLOCATE (bitvec->bits);
 303 
    DEALLOCATE(bitvec->bits);
301 
}
 304 
}
302 
 
 305 
 
303 
void
 306 
void
304 
write_bitvec_indices PROTO_N ((ostream, bitvec))
 307 
write_bitvec_indices(OStreamP ostream, BitVecP bitvec)
305 
		     PROTO_T (OStreamP ostream X
 - 
 
306 
			      BitVecP  bitvec)
 - 
 
307 
{
 308 
{
308 
    unsigned num_bits_set = 0;
 309 
    unsigned num_bits_set = 0;
309 
    unsigned i;
 310 
    unsigned i;
310 
 
 311 
 
311 
    for (i = 0; i < bitvec_valid_bits; i ++) {
 312 
    for (i = 0; i < bitvec_valid_bits; i++) {
312 
	if (bitvec_is_set (bitvec, i)) {
 313 
	if (bitvec_is_set(bitvec, i)) {
313 
	    num_bits_set ++;
 314 
	    num_bits_set++;
314 
	}
 315 
	}
315 
    }
 316 
    }
316 
    for (i = 0; i < bitvec_valid_bits; i ++) {
 317 
    for (i = 0; i < bitvec_valid_bits; i++) {
317 
	if (bitvec_is_set (bitvec, i)) {
 318 
	if (bitvec_is_set(bitvec, i)) {
318 
	    write_unsigned (ostream, i);
 319 
	    write_unsigned(ostream, i);
319 
	    num_bits_set --;
 320 
	    num_bits_set--;
320 
	    if (num_bits_set == 1) {
 321 
	    if (num_bits_set == 1) {
321 
		write_cstring (ostream, " & ");
 322 
		write_cstring(ostream, " & ");
322 
	    } else if (num_bits_set != 0) {
 323 
	    } else if (num_bits_set != 0) {
323 
		write_cstring (ostream, ", ");
 324 
		write_cstring(ostream, ", ");
324 
	    }
 325 
	    }
325 
	}
 326 
	}
326 
    }
 327 
    }
327 
}
 328 
}
328
329