1 /* 2 * bitmask header file 3 * 4 * Copyright (c) 2004 Silicon Graphics, Inc. All rights reserved. 5 * 6 * Paul Jackson <pj@sgi.com> 7 */ 8 9 /* 10 * This program is free software; you can redistribute it and/or modify 11 * it under the terms of the GNU Lesser General Public License as published by 12 * the Free Software Foundation; either version 2.1 of the License, or 13 * (at your option) any later version. 14 * 15 * This program is distributed in the hope that it will be useful, 16 * but WITHOUT ANY WARRANTY; without even the implied warranty of 17 * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the 18 * GNU Lesser General Public License for more details. 19 * 20 * You should have received a copy of the GNU Lesser General Public License 21 * along with this program; if not, write to the Free Software 22 * Foundation, Inc., 59 Temple Place, Suite 330, Boston, MA 02111-1307 USA 23 */ 24 25 /* 26 * bitmasks - dynamically sized multi-word bit masks, with many operators 27 * 28 * link with -lbitmask 29 * 30 * ==== Allocate and free `struct bitmask *` 31 * 32 * bitmask_alloc(n): Allocate a new struct bitmask with a size of n bits 33 * bitmask_free(bmp): Free struct bitmask 34 * 35 * ==== Display and parse ascii string representations 36 * 37 * bitmask_displayhex(buf, len, bmp): Write hex word bmp to buf 38 * bitmask_displaylist(buf, len, bmp): Write decimal list bmp to buf 39 * bitmask_parsehex(buf, bmp): Parse hex words in buf to bmp 40 * bitmask_parselist(buf, bmp): Parse decimal list in buf to bmp 41 * 42 * ==== Basic initialization operations 43 * 44 * bitmask_copy(bmp1, bmp2): Copy bmp2 to bmp1 45 * bitmask_setall(bmp): Set all bits in bitmask: bmp = ~0 46 * bitmask_clearall(bmp): Clear all bits in bitmask: bmp = 0 47 * 48 * ==== Interface to kernel sched_{set,get}affinity system calls 49 * 50 * bitmask_nbytes(bmp): Length in bytes of mask - use as second argument 51 * bitmask_mask(bmp): Direct pointer to bit mask - use as third argument 52 * 53 * ==== Unary numeric queries 54 * 55 * bitmask_nbits(bmp): Size in bits of entire bitmask 56 * bitmask_weight(bmp): Hamming Weight: number of set bits 57 * 58 * ==== Unary Boolean queries 59 * 60 * bitmask_isbitset(bmp, i): True if specified bit i is set 61 * bitmask_isbitclear(bmp, i): True if specified bit i is clear 62 * bitmask_isallset(bmp): True if all bits are set 63 * bitmask_isallclear(bmp): True if all bits are clear 64 * 65 * ==== Single bit operations 66 * 67 * bitmask_setbit(bmp, i): Set a single bit i in bitmask 68 * bitmask_clearbit(bmp, i): Clear a single bit i in bitmask 69 * 70 * ==== Binary Boolean operations: bmp1 op? bmp2 71 * 72 * bitmask_equal(bmp1, bmp2): True if two bitmasks are equal 73 * bitmask_subset(bmp1, bmp2): True if first bitmask is subset of second 74 * bitmask_disjoint(bmp1, bmp2): True if two bitmasks don't overlap 75 * bitmask_intersects(bmp1, bmp2): True if two bitmasks do overlap 76 * 77 * ==== Range operations 78 * 79 * bitmask_setrange(bmp, i, j): Set bits of bitmask in specified range [i, j) 80 * bitmask_clearrange(bmp, i, j): Clear bits of bitmask in specified range 81 * bitmask_keeprange(bmp, i, j): Clear all but specified range 82 * 83 * ==== Unary operations 84 * 85 * bitmask_complement(bmp1, bmp2): Complement: bmp1 = ~bmp2 86 * bitmask_shiftright(bmp1, bmp2, n): Right shift: bmp1 = bmp2 >> n 87 * bitmask_shiftleft(bmp1, bmp2, n): Left shift: bmp1 = bmp2 << n 88 * 89 * ==== Binary operations 90 * 91 * bitmask_and(bmp1, bmp2, bmp3): Logical `and`: bmp1 = bmp2 & bmp3 92 * bitmask_andnot(bmp1, bmp2, bmp3): Logical `andnot`: bmp1 = bmp2 & ~bmp3 93 * bitmask_or(bmp1, bmp2, bmp3): Logical `or`: bmp1 = bmp2 | bmp3 94 * bitmask_eor(bmp1, bmp2, bmp3): Logical `eor`: bmp1 = bmp2 ^ bmp3 95 * 96 * ==== Iteration operators 97 * 98 * bitmask_first(bmp): Number of lowest set bit (min) 99 * bitmask_next(bmp, i): Number of next set bit at or above given bit i 100 * bitmask_rel_to_abs_pos(bmp, n): Absolute position of nth set bit 101 * bitmask_abs_to_rel_pos(bmp, n): Relative position amongst set bits of bit n 102 * bitmask_last(bmp): Number of highest set bit (max) 103 * 104 * ==== Example: 105 * 106 * == allocate some bitmasks == 107 * struct bitmask *a = bitmask_alloc(10); 108 * struct bitmask *b = bitmask_alloc(10); 109 * struct bitmask *c = bitmask_alloc(10); 110 * struct bitmask *d = bitmask_alloc(10); 111 * struct bitmask *e = bitmask_alloc(10); 112 * struct bitmask *f = bitmask_alloc(10); 113 * struct bitmask *g = bitmask_alloc(10); 114 * 115 * == stuff some data in first two == 116 * bitmask_setrange(a, 2, 6); # set bits 2,3,4,5 117 * bitmask_shiftleft(b, a, 2); # set bits 4,5,6,7 118 * 119 * == d is complement of union == 120 * bitmask_complement(d, bitmask_or(c, a, b)); 121 * 122 * == g is intersection of complements == 123 * bitmask_and(g, bitmask_complement(e, a), bitmask_complement(f, b)); 124 * 125 * == d should equal g == 126 * if (bitmask_equal(d, g)) 127 * puts("DeMorgan's Law works!"); 128 * 129 * == free up bitmasks == 130 * bitmask_free(a); 131 * bitmask_free(b); 132 * bitmask_free(c); 133 * bitmask_free(d); 134 * bitmask_free(e); 135 * bitmask_free(f); 136 * bitmask_free(g); 137 */ 138 139 #ifndef _BITMASK_H 140 #define _BITMASK_H 141 142 #ifdef __cplusplus 143 extern "C" { 144 #endif 145 146 struct bitmask; 147 148 struct bitmask *bitmask_alloc(unsigned int n); 149 void bitmask_free(struct bitmask *bmp); 150 151 int bitmask_displayhex(char *buf, int len, const struct bitmask *bmp); 152 int bitmask_displaylist(char *buf, int len, const struct bitmask *bmp); 153 int bitmask_parsehex(const char *buf, struct bitmask *bmp); 154 int bitmask_parselist(const char *buf, struct bitmask *bmp); 155 156 struct bitmask *bitmask_copy(struct bitmask *bmp1, const struct bitmask *bmp2); 157 struct bitmask *bitmask_setall(struct bitmask *bmp); 158 struct bitmask *bitmask_clearall(struct bitmask *bmp); 159 160 unsigned int bitmask_nbytes(struct bitmask *bmp); 161 unsigned long *bitmask_mask(struct bitmask *bmp); 162 163 unsigned int bitmask_nbits(const struct bitmask *bmp); 164 unsigned int bitmask_weight(const struct bitmask *bmp); 165 166 int bitmask_isbitset(const struct bitmask *bmp, unsigned int i); 167 int bitmask_isbitclear(const struct bitmask *bmp, unsigned int i); 168 int bitmask_isallset(const struct bitmask *bmp); 169 int bitmask_isallclear(const struct bitmask *bmp); 170 171 struct bitmask *bitmask_setbit(struct bitmask *bmp, unsigned int i); 172 struct bitmask *bitmask_clearbit(struct bitmask *bmp, unsigned int i); 173 174 int bitmask_equal(const struct bitmask *bmp1, const struct bitmask *bmp2); 175 int bitmask_subset(const struct bitmask *bmp1, const struct bitmask *bmp2); 176 int bitmask_disjoint(const struct bitmask *bmp1, const struct bitmask *bmp2); 177 int bitmask_intersects(const struct bitmask *bmp1, const struct bitmask *bmp2); 178 179 struct bitmask *bitmask_setrange(struct bitmask *bmp, 180 unsigned int i, unsigned int j); 181 struct bitmask *bitmask_clearrange(struct bitmask *bmp, 182 unsigned int i, unsigned int j); 183 struct bitmask *bitmask_keeprange(struct bitmask *bmp, 184 unsigned int i, unsigned int j); 185 186 struct bitmask *bitmask_complement(struct bitmask *bmp1, 187 const struct bitmask *bmp2); 188 struct bitmask *bitmask_shiftright(struct bitmask *bmp1, 189 const struct bitmask *bmp2, unsigned int n); 190 struct bitmask *bitmask_shiftleft(struct bitmask *bmp1, 191 const struct bitmask *bmp2, unsigned int n); 192 193 struct bitmask *bitmask_and(struct bitmask *bmp1,const struct bitmask *bmp2, 194 const struct bitmask *bmp3); 195 struct bitmask *bitmask_andnot(struct bitmask *bmp1, const struct bitmask *bmp2, 196 const struct bitmask *bmp3); 197 struct bitmask *bitmask_or(struct bitmask *bmp1, const struct bitmask *bmp2, 198 const struct bitmask *bmp3); 199 struct bitmask *bitmask_eor(struct bitmask *bmp1, const struct bitmask *bmp2, 200 const struct bitmask *bmp3); 201 202 unsigned int bitmask_first(const struct bitmask *bmp); 203 unsigned int bitmask_next(const struct bitmask *bmp, unsigned int i); 204 unsigned int bitmask_rel_to_abs_pos(const struct bitmask *bmp, unsigned int n); 205 unsigned int bitmask_abs_to_rel_pos(const struct bitmask *bmp, unsigned int n); 206 unsigned int bitmask_last(const struct bitmask *bmp); 207 208 #ifdef __cplusplus 209 } 210 #endif 211 212 #endif 213