lib:util: Fix undefined behavior in bitmap.c
[bbaumbach/samba-autobuild/.git] / 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 "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 struct bitmap *bitmap_talloc(TALLOC_CTX *mem_ctx, int n)
38 {
39         struct bitmap *bm;
40
41         bm = (struct bitmap *)talloc_zero_size(
42                 mem_ctx,
43                 offsetof(struct bitmap, b) + sizeof(uint32_t)*((n+31)/32));
44
45         if (!bm) return NULL;
46
47         talloc_set_name_const(bm, "struct bitmap");
48
49         bm->n = n;
50         return bm;
51 }
52
53 /****************************************************************************
54 copy as much of the source bitmap as will fit in the destination bitmap.
55 ****************************************************************************/
56
57 int bitmap_copy(struct bitmap * const dst, const struct bitmap * const src)
58 {
59         int count = MIN(dst->n, src->n);
60
61         SMB_ASSERT(dst->b != src->b);
62         memcpy(dst->b, src->b, sizeof(uint32_t)*((count+31)/32));
63
64         return count;
65 }
66
67 /****************************************************************************
68 set a bit in a bitmap
69 ****************************************************************************/
70 bool bitmap_set(struct bitmap *bm, unsigned i)
71 {
72         if (i >= bm->n) {
73                 DEBUG(0,("Setting invalid bitmap entry %d (of %d)\n",
74                       i, bm->n));
75                 return false;
76         }
77         bm->b[i/32] |= (1U<<(i%32));
78         return true;
79 }
80
81 /****************************************************************************
82 clear a bit in a bitmap
83 ****************************************************************************/
84 bool bitmap_clear(struct bitmap *bm, unsigned i)
85 {
86         if (i >= bm->n) {
87                 DEBUG(0,("clearing invalid bitmap entry %d (of %d)\n",
88                       i, bm->n));
89                 return false;
90         }
91         bm->b[i/32] &= ~(1U<<(i%32));
92         return true;
93 }
94
95 /****************************************************************************
96 query a bit in a bitmap
97 ****************************************************************************/
98 bool bitmap_query(struct bitmap *bm, unsigned i)
99 {
100         if (i >= bm->n) return false;
101         if (bm->b[i/32] & (1U<<(i%32))) {
102                 return true;
103         }
104         return false;
105 }
106
107 /****************************************************************************
108 find a zero bit in a bitmap starting at the specified offset, with
109 wraparound
110 ****************************************************************************/
111 int bitmap_find(struct bitmap *bm, unsigned ofs)
112 {
113         unsigned int i, j;
114
115         if (ofs > bm->n) ofs = 0;
116
117         i = ofs;
118         while (i < bm->n) {
119                 if (~(bm->b[i/32])) {
120                         j = i;
121                         do {
122                                 if (!bitmap_query(bm, j)) return j;
123                                 j++;
124                         } while (j & 31 && j < bm->n);
125                 }
126                 i += 32;
127                 i &= ~31;
128         }
129
130         i = 0;
131         while (i < ofs) {
132                 if (~(bm->b[i/32])) {
133                         j = i;
134                         do {
135                                 if (!bitmap_query(bm, j)) return j;
136                                 j++;
137                         } while (j & 31 && j < bm->n);
138                 }
139                 i += 32;
140                 i &= ~31;
141         }
142
143         return -1;
144 }