Line data    Source code

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