Root/
Source at commit a3b3ed4925927211fbb2a114cf183678bfc30346 created 13 years 5 months ago. By Xiangfu Liu, use the new version rules. | |
---|---|
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 | |
23 | struct bitset { |
24 | int v_n; |
25 | unsigned *v; |
26 | }; |
27 | |
28 | #define BITS (sizeof(unsigned)*8) |
29 | |
30 | |
31 | struct 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 | |
42 | struct 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 | |
56 | void bitset_free(struct bitset *set) |
57 | { |
58 | free(set->v); |
59 | free(set); |
60 | } |
61 | |
62 | |
63 | void 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 | |
70 | void 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 | |
77 | int 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 | |
84 | int 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 | |
95 | void 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 | |
104 | void 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 | |
114 | void 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 | |
124 | int 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 |
Branches:
master