1/* 2 Unix SMB/CIFS implementation. 3 simple bitmap functions 4 Copyright (C) Andrew Tridgell 1992-1998 5 6 This program is free software; you can redistribute it and/or modify 7 it under the terms of the GNU General Public License as published by 8 the Free Software Foundation; either version 2 of the License, or 9 (at your option) any later version. 10 11 This program is distributed in the hope that it will be useful, 12 but WITHOUT ANY WARRANTY; without even the implied warranty of 13 MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the 14 GNU General Public License for more details. 15 16 You should have received a copy of the GNU General Public License 17 along with this program; if not, write to the Free Software 18 Foundation, Inc., 675 Mass Ave, Cambridge, MA 02139, USA. 19*/ 20 21#include "includes.h" 22 23/* these functions provide a simple way to allocate integers from a 24 pool without repetition */ 25 26/**************************************************************************** 27allocate a bitmap of the specified size 28****************************************************************************/ 29struct bitmap *bitmap_allocate(int n) 30{ 31 struct bitmap *bm; 32 33 bm = SMB_MALLOC_P(struct bitmap); 34 35 if (!bm) return NULL; 36 37 bm->n = n; 38 bm->b = SMB_MALLOC_ARRAY(uint32, (n+31)/32); 39 if (!bm->b) { 40 SAFE_FREE(bm); 41 return NULL; 42 } 43 44 memset(bm->b, 0, sizeof(uint32)*((n+31)/32)); 45 46 return bm; 47} 48 49/**************************************************************************** 50free a bitmap. 51****************************************************************************/ 52 53void bitmap_free(struct bitmap *bm) 54{ 55 if (!bm) 56 return; 57 58 SAFE_FREE(bm->b); 59 SAFE_FREE(bm); 60} 61 62/**************************************************************************** 63talloc a bitmap 64****************************************************************************/ 65struct bitmap *bitmap_talloc(TALLOC_CTX *mem_ctx, int n) 66{ 67 struct bitmap *bm; 68 69 if (!mem_ctx) return NULL; 70 71 bm = TALLOC_P(mem_ctx, struct bitmap); 72 73 if (!bm) return NULL; 74 75 bm->n = n; 76 bm->b = TALLOC_ARRAY(mem_ctx, uint32, (n+31)/32); 77 if (!bm->b) { 78 return NULL; 79 } 80 81 memset(bm->b, 0, sizeof(uint32)*((n+31)/32)); 82 83 return bm; 84} 85 86/**************************************************************************** 87copy as much of the source bitmap as will fit in the destination bitmap. 88****************************************************************************/ 89 90int bitmap_copy(struct bitmap * const dst, const struct bitmap * const src) 91{ 92 int count = MIN(dst->n, src->n); 93 94 SMB_ASSERT(dst->b != src->b); 95 memcpy(dst->b, src->b, sizeof(uint32)*((count+31)/32)); 96 97 return count; 98} 99 100/**************************************************************************** 101set a bit in a bitmap 102****************************************************************************/ 103BOOL bitmap_set(struct bitmap *bm, unsigned i) 104{ 105 if (i >= bm->n) { 106 DEBUG(0,("Setting invalid bitmap entry %d (of %d)\n", 107 i, bm->n)); 108 return False; 109 } 110 bm->b[i/32] |= (1<<(i%32)); 111 return True; 112} 113 114/**************************************************************************** 115clear a bit in a bitmap 116****************************************************************************/ 117BOOL bitmap_clear(struct bitmap *bm, unsigned i) 118{ 119 if (i >= bm->n) { 120 DEBUG(0,("clearing invalid bitmap entry %d (of %d)\n", 121 i, bm->n)); 122 return False; 123 } 124 bm->b[i/32] &= ~(1<<(i%32)); 125 return True; 126} 127 128/**************************************************************************** 129query a bit in a bitmap 130****************************************************************************/ 131BOOL bitmap_query(struct bitmap *bm, unsigned i) 132{ 133 if (i >= bm->n) return False; 134 if (bm->b[i/32] & (1<<(i%32))) { 135 return True; 136 } 137 return False; 138} 139 140/**************************************************************************** 141find a zero bit in a bitmap starting at the specified offset, with 142wraparound 143****************************************************************************/ 144int bitmap_find(struct bitmap *bm, unsigned ofs) 145{ 146 unsigned int i, j; 147 148 if (ofs > bm->n) ofs = 0; 149 150 i = ofs; 151 while (i < bm->n) { 152 if (~(bm->b[i/32])) { 153 j = i; 154 do { 155 if (!bitmap_query(bm, j)) return j; 156 j++; 157 } while (j & 31 && j < bm->n); 158 } 159 i += 32; 160 i &= ~31; 161 } 162 163 i = 0; 164 while (i < ofs) { 165 if (~(bm->b[i/32])) { 166 j = i; 167 do { 168 if (!bitmap_query(bm, j)) return j; 169 j++; 170 } while (j & 31 && j < bm->n); 171 } 172 i += 32; 173 i &= ~31; 174 } 175 176 return -1; 177} 178