lib/util/bitmap.c

   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 3 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, see <http://www.gnu.org/licenses/>.
  18 */
  19
  20 #include "includes.h"
  21 #include "lib/util/bitmap.h"
  22
  23 /* these functions provide a simple way to allocate integers from a
  24    pool without repetition */
  25
  26 /****************************************************************************
  27 talloc a bitmap
  28 ****************************************************************************/
  29 struct bitmap *bitmap_talloc(TALLOC_CTX *mem_ctx, int n)
  30 {
  31         struct bitmap *bm;
  32
  33         bm = talloc(mem_ctx, struct bitmap);
  34
  35         if (!bm) return NULL;
  36
  37         bm->n = n;
  38         bm->b = talloc_zero_array(bm, uint32_t, (n+31)/32);
  39         if (!bm->b) {
  40                 TALLOC_FREE(bm);
  41                 return NULL;
  42         }
  43         return bm;
  44 }
  45
  46 /****************************************************************************
  47 copy as much of the source bitmap as will fit in the destination bitmap.
  48 ****************************************************************************/
  49
  50 int bitmap_copy(struct bitmap * const dst, const struct bitmap * const src)
  51 {
  52         int count = MIN(dst->n, src->n);
  53
  54         SMB_ASSERT(dst->b != src->b);
  55         memcpy(dst->b, src->b, sizeof(uint32_t)*((count+31)/32));
  56
  57         return count;
  58 }
  59
  60 /****************************************************************************
  61 set a bit in a bitmap
  62 ****************************************************************************/
  63 bool bitmap_set(struct bitmap *bm, unsigned i)
  64 {
  65         if (i >= bm->n) {
  66                 DEBUG(0,("Setting invalid bitmap entry %d (of %d)\n",
  67                       i, bm->n));
  68                 return false;
  69         }
  70         bm->b[i/32] |= (1<<(i%32));
  71         return true;
  72 }
  73
  74 /****************************************************************************
  75 clear a bit in a bitmap
  76 ****************************************************************************/
  77 bool bitmap_clear(struct bitmap *bm, unsigned i)
  78 {
  79         if (i >= bm->n) {
  80                 DEBUG(0,("clearing invalid bitmap entry %d (of %d)\n",
  81                       i, bm->n));
  82                 return false;
  83         }
  84         bm->b[i/32] &= ~(1<<(i%32));
  85         return true;
  86 }
  87
  88 /****************************************************************************
  89 query a bit in a bitmap
  90 ****************************************************************************/
  91 bool bitmap_query(struct bitmap *bm, unsigned i)
  92 {
  93         if (i >= bm->n) return false;
  94         if (bm->b[i/32] & (1<<(i%32))) {
  95                 return true;
  96         }
  97         return false;
  98 }
  99
 100 /****************************************************************************
 101 find a zero bit in a bitmap starting at the specified offset, with
 102 wraparound
 103 ****************************************************************************/
 104 int bitmap_find(struct bitmap *bm, unsigned ofs)
 105 {
 106         unsigned int i, j;
 107
 108         if (ofs > bm->n) ofs = 0;
 109
 110         i = ofs;
 111         while (i < bm->n) {
 112                 if (~(bm->b[i/32])) {
 113                         j = i;
 114                         do {
 115                                 if (!bitmap_query(bm, j)) return j;
 116                                 j++;
 117                         } while (j & 31 && j < bm->n);
 118                 }
 119                 i += 32;
 120                 i &= ~31;
 121         }
 122
 123         i = 0;
 124         while (i < ofs) {
 125                 if (~(bm->b[i/32])) {
 126                         j = i;
 127                         do {
 128                                 if (!bitmap_query(bm, j)) return j;
 129                                 j++;
 130                         } while (j & 31 && j < bm->n);
 131                 }
 132                 i += 32;
 133                 i &= ~31;
 134         }
 135
 136         return -1;
 137 }