2 Unix SMB/CIFS implementation.
3 simple bitmap functions
4 Copyright (C) Andrew Tridgell 1992-1998
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.
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.
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.
23 /* these functions provide a simple way to allocate integers from a
24 pool without repetition */
26 /****************************************************************************
27 allocate a bitmap of the specified size
28 ****************************************************************************/
29 struct bitmap
*bitmap_allocate(int n
)
33 bm
= (struct bitmap
*)malloc(sizeof(*bm
));
38 bm
->b
= (uint32
*)malloc(sizeof(bm
->b
[0])*(n
+31)/32);
44 memset(bm
->b
, 0, sizeof(bm
->b
[0])*(n
+31)/32);
49 /****************************************************************************
51 ****************************************************************************/
53 void bitmap_free(struct bitmap
*bm
)
62 /****************************************************************************
64 ****************************************************************************/
65 struct bitmap
*bitmap_talloc(TALLOC_CTX
*mem_ctx
, int n
)
69 if (!mem_ctx
) return NULL
;
71 bm
= (struct bitmap
*)talloc(mem_ctx
, sizeof(*bm
));
76 bm
->b
= (uint32
*)talloc(mem_ctx
, sizeof(bm
->b
[0])*(n
+31)/32);
81 memset(bm
->b
, 0, sizeof(bm
->b
[0])*(n
+31)/32);
86 /****************************************************************************
87 copy as much of the source bitmap as will fit in the destination bitmap.
88 ****************************************************************************/
90 int bitmap_copy(struct bitmap
* const dst
, const struct bitmap
* const src
)
92 int count
= MIN(dst
->n
, src
->n
);
94 SMB_ASSERT(dst
->b
!= src
->b
);
95 memcpy(dst
->b
, src
->b
, sizeof(dst
->b
[0])*(count
+31)/32);
100 /****************************************************************************
101 set a bit in a bitmap
102 ****************************************************************************/
103 BOOL
bitmap_set(struct bitmap
*bm
, unsigned i
)
106 DEBUG(0,("Setting invalid bitmap entry %d (of %d)\n",
110 bm
->b
[i
/32] |= (1<<(i
%32));
114 /****************************************************************************
115 clear a bit in a bitmap
116 ****************************************************************************/
117 BOOL
bitmap_clear(struct bitmap
*bm
, unsigned i
)
120 DEBUG(0,("clearing invalid bitmap entry %d (of %d)\n",
124 bm
->b
[i
/32] &= ~(1<<(i
%32));
128 /****************************************************************************
129 query a bit in a bitmap
130 ****************************************************************************/
131 BOOL
bitmap_query(struct bitmap
*bm
, unsigned i
)
133 if (i
>= bm
->n
) return False
;
134 if (bm
->b
[i
/32] & (1<<(i
%32))) {
140 /****************************************************************************
141 find a zero bit in a bitmap starting at the specified offset, with
143 ****************************************************************************/
144 int bitmap_find(struct bitmap
*bm
, unsigned ofs
)
148 if (ofs
> bm
->n
) ofs
= 0;
152 if (~(bm
->b
[i
/32])) {
155 if (!bitmap_query(bm
, j
)) return j
;
157 } while (j
& 31 && j
< bm
->n
);
165 if (~(bm
->b
[i
/32])) {
168 if (!bitmap_query(bm
, j
)) return j
;
170 } while (j
& 31 && j
< bm
->n
);