diff options
Diffstat (limited to 'source3/lib/bitmap.c')
| -rw-r--r-- | source3/lib/bitmap.c | 176 |
1 files changed, 176 insertions, 0 deletions
diff --git a/source3/lib/bitmap.c b/source3/lib/bitmap.c new file mode 100644 index 0000000000..5e623f474a --- /dev/null +++ b/source3/lib/bitmap.c @@ -0,0 +1,176 @@ +/* + Unix SMB/CIFS implementation. + simple bitmap functions + Copyright (C) Andrew Tridgell 1992-1998 + + This program is free software; you can redistribute it and/or modify + it under the terms of the GNU General Public License as published by + the Free Software Foundation; either version 3 of the License, or + (at your option) any later version. + + This program is distributed in the hope that it will be useful, + but WITHOUT ANY WARRANTY; without even the implied warranty of + MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the + GNU General Public License for more details. + + You should have received a copy of the GNU General Public License + along with this program. If not, see <http://www.gnu.org/licenses/>. +*/ + +#include "includes.h" + +/* these functions provide a simple way to allocate integers from a + pool without repetition */ + +/**************************************************************************** +allocate a bitmap of the specified size +****************************************************************************/ +struct bitmap *bitmap_allocate(int n) +{ + struct bitmap *bm; + + bm = SMB_MALLOC_P(struct bitmap); + + if (!bm) return NULL; + + bm->n = n; + bm->b = SMB_MALLOC_ARRAY(uint32, (n+31)/32); + if (!bm->b) { + SAFE_FREE(bm); + return NULL; + } + + memset(bm->b, 0, sizeof(uint32)*((n+31)/32)); + + return bm; +} + +/**************************************************************************** +free a bitmap. +****************************************************************************/ + +void bitmap_free(struct bitmap *bm) +{ + if (!bm) + return; + + SAFE_FREE(bm->b); + SAFE_FREE(bm); +} + +/**************************************************************************** +talloc a bitmap +****************************************************************************/ +struct bitmap *bitmap_talloc(TALLOC_CTX *mem_ctx, int n) +{ + struct bitmap *bm; + + if (!mem_ctx) return NULL; + + bm = TALLOC_P(mem_ctx, struct bitmap); + + if (!bm) return NULL; + + bm->n = n; + bm->b = TALLOC_ARRAY(mem_ctx, uint32, (n+31)/32); + if (!bm->b) { + return NULL; + } + + memset(bm->b, 0, sizeof(uint32)*((n+31)/32)); + + return bm; +} + +/**************************************************************************** +copy as much of the source bitmap as will fit in the destination bitmap. +****************************************************************************/ + +int bitmap_copy(struct bitmap * const dst, const struct bitmap * const src) +{ + int count = MIN(dst->n, src->n); + + SMB_ASSERT(dst->b != src->b); + memcpy(dst->b, src->b, sizeof(uint32)*((count+31)/32)); + + return count; +} + +/**************************************************************************** +set a bit in a bitmap +****************************************************************************/ +bool bitmap_set(struct bitmap *bm, unsigned i) +{ + if (i >= bm->n) { + DEBUG(0,("Setting invalid bitmap entry %d (of %d)\n", + i, bm->n)); + return False; + } + bm->b[i/32] |= (1<<(i%32)); + return True; +} + +/**************************************************************************** +clear a bit in a bitmap +****************************************************************************/ +bool bitmap_clear(struct bitmap *bm, unsigned i) +{ + if (i >= bm->n) { + DEBUG(0,("clearing invalid bitmap entry %d (of %d)\n", + i, bm->n)); + return False; + } + bm->b[i/32] &= ~(1<<(i%32)); + return True; +} + +/**************************************************************************** +query a bit in a bitmap +****************************************************************************/ +bool bitmap_query(struct bitmap *bm, unsigned i) +{ + if (i >= bm->n) return False; + if (bm->b[i/32] & (1<<(i%32))) { + return True; + } + return False; +} + +/**************************************************************************** +find a zero bit in a bitmap starting at the specified offset, with +wraparound +****************************************************************************/ +int bitmap_find(struct bitmap *bm, unsigned ofs) +{ + unsigned int i, j; + + if (ofs > bm->n) ofs = 0; + + i = ofs; + while (i < bm->n) { + if (~(bm->b[i/32])) { + j = i; + do { + if (!bitmap_query(bm, j)) return j; + j++; + } while (j & 31 && j < bm->n); + } + i += 32; + i &= ~31; + } + + i = 0; + while (i < ofs) { + if (~(bm->b[i/32])) { + j = i; + do { + if (!bitmap_query(bm, j)) return j; + j++; + } while (j & 31 && j < bm->n); + } + i += 32; + i &= ~31; + } + + return -1; +} |