1 /* 2 * CDDL HEADER START 3 * 4 * The contents of this file are subject to the terms of the 5 * Common Development and Distribution License, Version 1.0 only 6 * (the "License"). You may not use this file except in compliance 7 * with the License. 8 * 9 * You can obtain a copy of the license at usr/src/OPENSOLARIS.LICENSE 10 * or http://www.opensolaris.org/os/licensing. 11 * See the License for the specific language governing permissions 12 * and limitations under the License. 13 * 14 * When distributing Covered Code, include this CDDL HEADER in each 15 * file and include the License file at usr/src/OPENSOLARIS.LICENSE. 16 * If applicable, add the following below this CDDL HEADER, with the 17 * fields enclosed by brackets "[]" replaced with your own identifying 18 * information: Portions Copyright [yyyy] [name of copyright owner] 19 * 20 * CDDL HEADER END 21 */ 22 /* Copyright (c) 1984, 1986, 1987, 1988, 1989 AT&T */ 23 /* All Rights Reserved */ 24 25 26 /* 27 * Copyright 2004 Sun Microsystems, Inc. All rights reserved. 28 * Use is subject to license terms. 29 */ 30 31 #pragma ident "%Z%%M% %I% %E% SMI" 32 33 /* 34 * Operations on bitmaps of arbitrary size 35 * A bitmap is a vector of 1 or more ulongs. 36 * The user of the package is responsible for range checks and keeping 37 * track of sizes. 38 */ 39 40 #include <sys/types.h> 41 #include <sys/bitmap.h> 42 #include <sys/debug.h> /* ASSERT */ 43 44 /* 45 * Return index of first available bit in denoted bitmap, or -1 for 46 * failure. Size is the cardinality of the bitmap; that is, the 47 * number of bits. 48 * No side-effects. In particular, does not update bitmap. 49 * Caller is responsible for range checks. 50 */ 51 index_t 52 bt_availbit(ulong_t *bitmap, size_t nbits) 53 { 54 index_t maxword; /* index of last in map */ 55 index_t wx; /* word index in map */ 56 57 /* 58 * Look for a word with a bit off. 59 * Subtract one from nbits because we're converting it to a 60 * a range of indices. 61 */ 62 nbits -= 1; 63 maxword = nbits >> BT_ULSHIFT; 64 for (wx = 0; wx <= maxword; wx++) 65 if (bitmap[wx] != ~0) 66 break; 67 68 if (wx <= maxword) { 69 /* 70 * Found a word with a bit off. Now find the bit in the word. 71 */ 72 index_t bx; /* bit index in word */ 73 index_t maxbit; /* last bit to look at */ 74 ulong_t word; 75 ulong_t bit; 76 77 maxbit = wx == maxword ? nbits & BT_ULMASK : BT_NBIPUL - 1; 78 word = bitmap[wx]; 79 bit = 1; 80 for (bx = 0; bx <= maxbit; bx++, bit <<= 1) { 81 if (!(word & bit)) { 82 return (wx << BT_ULSHIFT | bx); 83 } 84 } 85 } 86 return (-1); 87 } 88 89 90 /* 91 * Find highest order bit that is on, and is within or below 92 * the word specified by wx. 93 */ 94 int 95 bt_gethighbit(ulong_t *mapp, int wx) 96 { 97 ulong_t word; 98 99 while ((word = mapp[wx]) == 0) { 100 wx--; 101 if (wx < 0) { 102 return (-1); 103 } 104 } 105 return (wx << BT_ULSHIFT | (highbit(word) - 1)); 106 } 107 108 109 /* 110 * Search the bitmap for a consecutive pattern of 1's. 111 * Search starts at position pos1. 112 * Returns 1 on success and 0 on failure. 113 * Side effects. 114 * Returns indices to the first bit (pos1) 115 * and one past the last bit (pos2) in the pattern. 116 */ 117 int 118 bt_range(ulong_t *bitmap, size_t *pos1, size_t *pos2, size_t end_pos) 119 { 120 size_t pos; 121 122 for (pos = *pos1; pos < end_pos; pos++) 123 if (BT_TEST(bitmap, pos)) 124 break; 125 126 if (pos == end_pos) 127 return (0); 128 129 *pos1 = pos; 130 131 for (; pos < end_pos; pos++) 132 if (!BT_TEST(bitmap, pos)) 133 break; 134 *pos2 = pos; 135 136 return (1); 137 } 138 139 140 /* 141 * return the parity of the supplied long 142 * 143 * this works by successively partitioning the argument in half, and 144 * setting the parity of the result to the parity of the 2 halfs, until 145 * only one bit is left 146 */ 147 int 148 odd_parity(ulong_t i) 149 { 150 #ifdef _LP64 151 i ^= i >> 32; 152 #endif 153 i ^= i >> 16; 154 i ^= i >> 8; 155 i ^= i >> 4; 156 i ^= i >> 2; 157 i ^= i >> 1; 158 159 return (i & 0x01); 160 } 161 162 163 /* 164 * get the lowest bit in the range of 'start' and 'stop', inclusive. 165 * I.e., if caller calls bt_getlowbit(map, X, Y), any value between X and Y, 166 * including X and Y can be returned. 167 * Neither start nor stop is required to align with word boundaries. 168 * If a bit is set in the range, the bit position is returned; otherwise, 169 * a -1 is returned. 170 */ 171 int 172 bt_getlowbit(ulong_t *map, size_t start, size_t stop) 173 { 174 ulong_t word; 175 int counter = start >> BT_ULSHIFT; 176 int limit = stop >> BT_ULSHIFT; 177 index_t partial_start = start & BT_ULMASK; 178 index_t partial_stop = stop & BT_ULMASK; 179 180 if (start > stop) { 181 return (-1); 182 } 183 184 /* 185 * The range between 'start' and 'stop' can be very large, and the 186 * '1' bits in this range can be sparse. 187 * For performance reason, the underlying implementation operates 188 * on words, not on bits. 189 */ 190 word = map[counter]; 191 192 if (partial_start) { 193 /* 194 * Since the start is not aligned on word boundary, we 195 * need to patch the unwanted low order bits with 0's before 196 * operating on the first bitmap word. 197 */ 198 word = word & (BT_ULMAXMASK << partial_start); 199 } 200 201 /* 202 * Locate a word from the map array with one of the bits set. 203 */ 204 205 while ((word == 0) && (counter < limit)) { 206 word = map[++counter]; 207 } 208 209 /* 210 * The end of range has similar problems if it is not aligned. 211 * Taking care of the end which is not aligned. 212 */ 213 214 if ((counter == limit) && (partial_stop != BT_ULMASK)) { 215 /* 216 * Take care the partial word by patch the high order 217 * bits with 0's. Here we dealing with the case that 218 * the last word of the bitmap is not aligned. 219 */ 220 221 ASSERT(partial_stop < BT_ULMASK); 222 word = word & (~(BT_ULMAXMASK << partial_stop + 1)); 223 } 224 225 /* 226 * Examine the word. 227 */ 228 if (word == 0) { 229 return (-1); 230 } else { 231 return ((counter << BT_ULSHIFT) | (lowbit(word) - 1)); 232 } 233 } 234 235 /* 236 * Copy the bitmap. 237 */ 238 void 239 bt_copy(ulong_t *from, ulong_t *to, ulong_t size) 240 { 241 ulong_t i; 242 for (i = 0; i < size; i++) 243 *to++ = *from++; 244 } 245