Ticket #1102: z-bitflag.c

File z-bitflag.c, 12.8 KB (added by MarbleDice, 10 years ago)

Preliminary bitflag code file.

Line 
1/*
2 * File: z-bitflag.c
3 * Purpose: Low-level bit vector manipulation
4 *
5 * Copyright (c) 2009 Andrew Sidwell
6 *
7 * This work is free software; you can redistribute it and/or modify it
8 * under the terms of either:
9 *
10 * a) the GNU General Public License as published by the Free Software
11 *    Foundation, version 2, or
12 *
13 * b) the "Angband licence":
14 *    This software may be copied and distributed for educational, research,
15 *    and not for profit purposes provided that this copyright and statement
16 *    are included in all such copies.  Other copyrights may also apply.
17 */
18
19#include "z-bitflag.h"
20
21
22/**
23 * Tests if a bitflag is set in a bitfield.
24 *
25 * TRUE is returned when `flag` is set in `field`, and FALSE otherwise.
26 * The bitfield size is supplied in `size`.
27 */
28bool field_has(const size_t size, const bitfield *field, const int flag)
29{
30        const size_t flag_offset = FLAG_OFFSET(flag);
31        const int flag_binary = FLAG_BINARY(flag);
32
33        if (flag == FLAG_END) return FALSE;
34
35        if (flag < FLAG_START || !(flag < MAX_FLAGS(size)))
36        {
37                fprintf(stderr, "FAIL Flag[%d] FO[%d] FB[%d] Size[%d]\n", flag, flag_offset, flag_binary, size);
38        }
39
40        assert(flag_offset < size);
41
42        if (field[flag_offset] & flag_binary) return TRUE;
43
44        return FALSE;
45}
46
47
48/**
49 * Interates over the set flags in a bitfield.
50 *
51 * Returns the next set flag in `field`, starting from (but not including)
52 * `flag`. FLAG_END will be returned when the end of the bitfield is reached.
53 * Iteration will start at the beginning of the bitfield when `flag` is
54 * FLAG_END. The bitfield size is supplied in `size`.
55 */
56int field_next(const size_t size, const bitfield *field, const int flag)
57{
58        const int max_flags = MAX_FLAGS(size);
59        int f, flag_offset, flag_binary;
60
61        assert(flag < max_flags);
62
63        for (f = flag + 1; f < max_flags; f++)
64        {
65                flag_offset = FLAG_OFFSET(f);
66                flag_binary = FLAG_BINARY(f);
67
68                if (field[flag_offset] & flag_binary) return f;
69        }
70
71        return FLAG_END;
72}
73
74
75/**
76 * Tests a bitfield for emptiness.
77 *
78 * TRUE is returned when no flags are set in `field`, and FALSE otherwise.
79 * The bitfield size is supplied in `size`.
80 */
81bool field_is_empty(const size_t size, const bitfield *field)
82{
83        size_t i;
84
85        for (i = 0; i < size; i++)
86                if (field[i] > 0) return FALSE;
87
88        return TRUE;
89}
90
91
92/**
93 * Tests a bitfield for fullness.
94 *
95 * TRUE is returned when all flags are set in `field`, and FALSE otherwise.
96 * The bitfield size is supplied in `size`.
97 */
98bool field_is_full(const size_t size, const bitfield *field)
99{
100        size_t i;
101
102        for (i = 0; i < size; i++)
103                if (field[i] != (bitfield) -1) return FALSE;
104
105        return TRUE;
106}
107
108
109/**
110 * Tests two bitfields for intersection.
111 *
112 * TRUE is returned when any flag is set in both `field1` and `field2`, and
113 * FALSE otherwise. The size of the bitfields is supplied in `size`.
114 */
115bool field_is_inter(const size_t size, const bitfield *field1, const bitfield *field2)
116{
117        size_t i;
118
119        for (i = 0; i < size; i++)
120                if (field1[i] & field2[i]) return TRUE;
121
122        return FALSE;
123}
124
125
126/**
127 * Test if one bitfield is a subset of another.
128 *
129 * TRUE is returned when every set flag in `field2` is also set in `field1`,
130 * and FALSE otherwise. The size of the bitfields is supplied in `size`.
131 */
132bool field_is_subset(const size_t size, const bitfield *field1, const bitfield *field2)
133{
134        size_t i;
135
136        for (i = 0; i < size; i++)
137                if (!(~field1[i] & field2[i])) return FALSE;
138
139        return TRUE;
140}
141
142
143/**
144 * Tests two bitfields for equality.
145 *
146 * TRUE is returned when the flags set in `field1` and `field2` are identical,
147 * and FALSE otherwise. the size of the bitfields is supplied in `size`.
148 */
149bool field_is_equal(const size_t size, const bitfield *field1, const bitfield *field2)
150{
151        size_t i;
152       
153        for (i = 0; i < size; i++)
154                if(field1[i] != field2[i]) return FALSE;
155
156        return TRUE;
157}
158
159
160/**
161 * Sets one bitflag in a bitfield.
162 *
163 * The bitflag identified by `flag` is set in `field`. The bitfield size is
164 * supplied in `size`.  TRUE is returned when changes were made, FALSE
165 * otherwise.
166 */
167bool field_on(const size_t size, bitfield *field, const int flag)
168{
169        const size_t flag_offset = FLAG_OFFSET(flag);
170        const int flag_binary = FLAG_BINARY(flag);
171
172        assert(flag_offset < size);
173
174        if (field[flag_offset] & flag_binary) return FALSE;
175
176        field[flag_offset] |= flag_binary;
177
178        return TRUE;
179}
180
181
182/**
183 * Clears one flag in a bitfield.
184 *
185 * The bitflag identified by `flag` is cleared in `field`. The bitfield size
186 * is supplied in `size`.  TRUE is returned when changes were made, FALSE
187 * otherwise.
188 */
189bool field_off(const size_t size, bitfield *field, const int flag)
190{
191        const size_t flag_offset = FLAG_OFFSET(flag);
192        const int flag_binary = FLAG_BINARY(flag);
193
194        assert(flag_offset < size);
195
196        if (!(field[flag_offset] & flag_binary)) return FALSE;
197
198        field[flag_offset] &= ~flag_binary;
199
200        return TRUE;
201}
202
203
204/**
205 * Clears all flags in a bitfield.
206 *
207 * All flags in `field` are cleared. The bitfield size is supplied in `size`.
208 */
209void field_wipe(const size_t size, bitfield *field)
210{
211        size_t i;
212       
213        for (i = 0; i < size; i++)
214                field[i] = 0;
215}
216
217
218/**
219 * Sets all flags in a bitfield.
220 *
221 * All flags in `field` are set. The bitfield size is supplied in `size`.
222 */
223void field_setall(const size_t size, bitfield *field)
224{
225        size_t i;
226
227        for (i = 0; i < size; i++)
228                field[i] = -1;
229}
230
231
232/**
233 * Negates all flags in a bitfield.
234 *
235 * All flags in `field` are toggled. The bitfield size is supplied in `size`.
236 */
237void field_negate(const size_t size, bitfield *field)
238{
239        size_t i;
240       
241        for (i = 0; i < size; i++)
242                field[i] = ~field[i];
243}
244
245
246/**
247 * Copies one bitfield into another.
248 *
249 * All flags in `field2` are copied into `field`. The size of the bitfields is
250 * supplied in `size`.
251 */
252void field_copy(const size_t size, bitfield *field1, const bitfield *field2)
253{
254        size_t i;
255       
256        for (i = 0; i < size; i++)
257                field1[i] = field2[i];
258}
259
260
261/**
262 * Computes the union of two bitfields.
263 *
264 * For every set flag in `field2`, the corresponding flag is set in `field1`.
265 * The size of the bitfields is supplied in `size`. TRUE is returned when
266 * changes were made, and FALSE otherwise.
267 */
268bool field_union(const size_t size, bitfield *field1, const bitfield *field2)
269{
270        size_t i;
271        bool delta = FALSE;
272
273        for (i = 0; i < size; i++)
274        {
275                /* !field_is_subset() */
276                if (~field1[i] & field2[i]) delta = TRUE;
277
278                field1[i] |= field2[i];
279        }
280
281        return delta;
282}
283
284
285/**
286 * Computes the union of one bitfield and the complement of another.
287 *
288 * For every unset flag in `field2`, the corresponding flag is set in `field1`.
289 * The size of the bitfields is supplied in `size`. TRUE is returned when
290 * changes were made, and FALSE otherwise.
291 */
292bool field_comp_union(const size_t size, bitfield *field1, const bitfield *field2)
293{
294        size_t i;
295        bool delta = FALSE;
296
297        for (i = 0; i < size; i++)
298        {
299                /* no equivalent fn */
300                if (!(~field1[i] & ~field2[i])) delta = TRUE;
301
302                field1[i] |= ~field2[i];
303        }
304
305        return delta;
306}
307
308
309/**
310 * Computes the intersection of two bitfields.
311 *
312 * For every unset flag in `field2`, the corresponding flag is cleared in
313 * `field1`. The size of the bitfields is supplied in `size`. TRUE is returned
314 * when changes were made, and FALSE otherwise.
315 */
316bool field_inter(const size_t size, bitfield *field1, const bitfield *field2)
317{
318        size_t i;
319        bool delta = FALSE;
320
321        for (i = 0; i < size; i++)
322        {
323                /* !field_is_equal() */
324                if (!(field1[i] == field2[i])) delta = TRUE;
325
326                field1[i] &= field2[i];
327        }
328
329        return delta;
330
331}
332
333
334/**
335 * Computes the difference of two bitfields.
336 *
337 * For every set flag in `field2`, the corresponding flag is cleared in
338 * `field1`. The size of the bitfields is supplied in `size`. TRUE is returned
339 * when changes were made, and FALSE otherwise.
340 */
341bool field_diff(const size_t size, bitfield *field1, const bitfield *field2)
342{
343        size_t i;
344        bool delta = FALSE;
345
346        for (i = 0; i < size; i++)
347        {
348                /* field_is_inter() */
349                if (field1[i] & field2[i]) delta = TRUE;
350
351                field1[i] &= ~field2[i];
352        }
353
354        return delta;
355}
356
357
358
359
360
361/**
362 * Tests if any of multiple bitflags are set in a bitfield.
363 *
364 * TRUE is returned if any of the flags specified in `...` are set in `field`,
365 * FALSE otherwise. The bitfield size is supplied in `size`.
366 *
367 * WARNING: FLAG_END must be the final argument in the `...` list.
368 */
369bool field_test_flags(const size_t size, const bitfield *field, ...)
370{
371        size_t flag_offset;
372        int flag_binary;
373        int f;
374        va_list args;
375        bool delta = FALSE;
376
377        va_start(args, field);
378
379        /* Process each flag in the va-args */
380        for (f = va_arg(args, int); f != FLAG_END; f = va_arg(args, int))
381        {
382                flag_offset = FLAG_OFFSET(f);
383                flag_binary = FLAG_BINARY(f);
384
385                assert(flag_offset < size);
386
387                /* field_has() */
388                if (field[flag_offset] & flag_binary)
389                {
390                        delta = TRUE;
391                        break;
392                }
393        }
394
395        va_end(args);
396       
397        return delta;
398}
399
400
401/**
402 * Tests if all of the multiple bitflags are set in a bitfield.
403 *
404 * TRUE is returned if all of the flags specified in `...` are set in `field`,
405 * FALSE otherwise. The bitfield size is supplied in `size`.
406 *
407 * WARNING: FLAG_END must be the final argument in the `...` list.
408 */
409bool field_test_all_flags(const size_t size, const bitfield *field, ...)
410{
411        size_t flag_offset;
412        int flag_binary;
413        int f;
414        va_list args;
415        bool delta = TRUE;
416
417        va_start(args, field);
418
419        /* Process each flag in the va-args */
420        for (f = va_arg(args, int); f != FLAG_END; f = va_arg(args, int))
421        {
422                flag_offset = FLAG_OFFSET(f);
423                flag_binary = FLAG_BINARY(f);
424
425                assert(flag_offset < size);
426
427                /* !field_has() */
428                if (!(field[flag_offset] & flag_binary))
429                {
430                        delta = FALSE;
431                        break;
432                }
433        }
434
435        va_end(args);
436       
437        return delta;
438}
439
440
441/**
442 * Clears multiple bitflags in a bitfield.
443 *
444 * The flags specified in `...` are cleared in `field`. The bitfield size is
445 * supplied in `size`. TRUE is returned when changes were made, FALSE
446 * otherwise.
447 *
448 * WARNING: FLAG_END must be the final argument in the `...` list.
449 */
450bool field_clear_flags(const size_t size, bitfield *field, ...)
451{
452        size_t flag_offset;
453        int flag_binary;
454        int f;
455        va_list args;
456        bool delta = FALSE;
457
458        va_start(args, field);
459
460        /* Process each flag in the va-args */
461        for (f = va_arg(args, int); f != FLAG_END; f = va_arg(args, int))
462        {
463                flag_offset = FLAG_OFFSET(f);
464                flag_binary = FLAG_BINARY(f);
465
466                assert(flag_offset < size);
467
468                /* field_has() */
469                if (field[flag_offset] & flag_binary) delta = TRUE;
470
471                /* field_off() */
472                field[flag_offset] &= ~flag_binary;
473        }
474
475        va_end(args);
476
477        return delta;
478}
479
480
481/**
482 * Sets multiple bitflags in a bitfield.
483 *
484 * The flags specified in `...` are set in `field`. The bitfield size is
485 * supplied in `size`. TRUE is returned when changes were made, FALSE
486 * otherwise.
487 *
488 * WARNING: FLAG_END must be the final argument in the `...` list.
489 */
490bool field_set_flags(const size_t size, bitfield *field, ...)
491{
492        size_t flag_offset;
493        int flag_binary;
494        int f;
495        va_list args;
496        bool delta = FALSE;
497
498        va_start(args, field);
499
500        /* Process each flag in the va-args */
501        for (f = va_arg(args, int); f != FLAG_END; f = va_arg(args, int))
502        {
503                flag_offset = FLAG_OFFSET(f);
504                flag_binary = FLAG_BINARY(f);
505
506                assert(flag_offset < size);
507
508                /* !field_has() */
509                if (!(field[flag_offset] & flag_binary)) delta = TRUE;
510
511                /* field_on() */
512                field[flag_offset] |= flag_binary;
513        }
514
515        va_end(args);
516
517        return delta;
518}
519
520
521/**
522 * Wipes a bitfield, and then sets multiple bitflags.
523 *
524 * The flags specified in `...` are set in `field`, while all other flags are
525 * cleared. The bitfield size is supplied in `size`.
526 *
527 * WARNING: FLAG_END must be the final argument in the `...` list.
528 */
529void field_init_flags(const size_t size, bitfield *field, ...)
530{
531        int f;
532        va_list args;
533
534        field_wipe(size, field);
535
536        va_start(args, field);
537
538        /* Process each flag in the va-args */
539        for (f = va_arg(args, int); f != FLAG_END; f = va_arg(args, int))
540                field_on(size, field, f);
541
542        va_end(args);
543}
544
545
546/**
547 * Computes the intersection of a bitfield and multiple bitflags.
548 *
549 * The flags not specified in `...` are cleared in `field`. The bitfeild size
550 * is supplied in `size`. TRUE is returned when changes were made, FALSE
551 * otherwise.
552 *
553 * WARNING: FLAG_END must be the final argument in the `...` list.
554 */
555bool field_mask_flags(const size_t size, bitfield *field, ...)
556{
557        int f;
558        va_list args;
559        bool delta = FALSE;
560
561        bitfield *mask;
562
563        /* Build the mask */
564        mask = C_ZNEW(size, bitfield);
565
566        va_start(args, field);
567
568        /* Process each flag in the va-args */
569        for (f = va_arg(args, int); f != FLAG_END; f = va_arg(args, int))
570                field_on(size, mask, f);
571
572        va_end(args);
573
574        delta = field_inter(size, field, mask);
575
576        /* Free the mask */
577
578        FREE(mask);
579
580        return delta;
581}