Root/bitset.c

1/*
2 * bitset.c - Arbitrary-length bit sets
3 *
4 * Written 2010 by Werner Almesberger
5 * Copyright 2010 by Werner Almesberger
6 *
7 * This program is free software; you can redistribute it and/or modify
8 * it under the terms of the GNU General Public License as published by
9 * the Free Software Foundation; either version 2 of the License, or
10 * (at your option) any later version.
11 */
12
13
14#include <stdlib.h>
15#include <string.h>
16#include <assert.h>
17#include <sys/types.h>
18
19#include "util.h"
20#include "bitset.h"
21
22
23struct bitset {
24    int v_n;
25    unsigned *v;
26};
27
28#define BITS (sizeof(unsigned)*8)
29
30
31struct bitset *bitset_new(int n)
32{
33    struct bitset *new;
34
35    new = alloc_type(struct bitset);
36    new->v_n = (n+BITS-1) & ~(BITS-1);
37    new->v = zalloc_size(sizeof(unsigned)*new->v_n);
38    return new;
39}
40
41
42struct bitset *bitset_clone(const struct bitset *old)
43{
44    struct bitset *new;
45    size_t bytes;
46
47    new = alloc_type(struct bitset);
48    bytes = sizeof(unsigned)*old->v_n;
49    new->v_n = old->v_n;
50    new->v = alloc_size(bytes);
51    memcpy(new->v, old->v, bytes);
52    return new;
53}
54
55
56void bitset_free(struct bitset *set)
57{
58    free(set->v);
59    free(set);
60}
61
62
63void bitset_set(struct bitset *set, int n)
64{
65    assert(n < set->v_n*BITS);
66    set->v[n/BITS] |= 1U << (n % BITS);
67}
68
69
70void bitset_clear(struct bitset *set, int n)
71{
72    assert(n < set->v_n*BITS);
73    set->v[n/BITS] &= ~(1U << (n % BITS));
74}
75
76
77int bitset_pick(const struct bitset *set, int n)
78{
79    assert(n < set->v_n*BITS);
80    return !!(set->v[n/BITS] & (1U << (n % BITS)));
81}
82
83
84int bitset_is_empty(const struct bitset *set)
85{
86    int i;
87
88    for (i = 0; i != set->v_n; i++)
89        if (set->v[i])
90            return 0;
91    return 1;
92}
93
94
95void bitset_zero(struct bitset *a)
96{
97    int i;
98
99    for (i = 0; i != a->v_n; i++)
100        a->v[i] = 0;
101}
102
103
104void bitset_and(struct bitset *a, const struct bitset *b)
105{
106    int i;
107
108    assert(a->v_n == b->v_n);
109    for (i = 0; i != a->v_n; i++)
110        a->v[i] &= b->v[i];
111}
112
113
114void bitset_or(struct bitset *a, const struct bitset *b)
115{
116    int i;
117
118    assert(a->v_n == b->v_n);
119    for (i = 0; i != a->v_n; i++)
120        a->v[i] |= b->v[i];
121}
122
123
124int bitset_ge(const struct bitset *a, const struct bitset *b)
125{
126    int i;
127
128    assert(a->v_n == b->v_n);
129    for (i = 0; i != a->v_n; i++)
130        if (~a->v[i] & b->v[i])
131            return 0;
132    return 1;
133}
134

Archive Download this file

Branches:
master



interactive