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