r2070: Let's try to overload srnlen and strndup for AIX where they are natly broken.
[tprouty/samba.git] / source / lib / 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 2 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, write to the Free Software
18    Foundation, Inc., 675 Mass Ave, Cambridge, MA 02139, USA.
19 */
20
21 #include "includes.h"
22
23 /* these functions provide a simple way to allocate integers from a
24    pool without repetition */
25
26 /****************************************************************************
27 allocate a bitmap of the specified size
28 ****************************************************************************/
29 struct bitmap *bitmap_allocate(int n)
30 {
31         struct bitmap *bm;
32
33         bm = (struct bitmap *)malloc(sizeof(*bm));
34
35         if (!bm) return NULL;
36         
37         bm->n = n;
38         bm->b = (uint32 *)malloc(sizeof(bm->b[0])*(n+31)/32);
39         if (!bm->b) {
40                 SAFE_FREE(bm);
41                 return NULL;
42         }
43
44         memset(bm->b, 0, sizeof(bm->b[0])*(n+31)/32);
45
46         return bm;
47 }
48
49 /****************************************************************************
50 free a bitmap.
51 ****************************************************************************/
52
53 void bitmap_free(struct bitmap *bm)
54 {
55         if (!bm)
56                 return;
57
58         SAFE_FREE(bm->b);
59         SAFE_FREE(bm);
60 }
61
62 /****************************************************************************
63 talloc a bitmap
64 ****************************************************************************/
65 struct bitmap *bitmap_talloc(TALLOC_CTX *mem_ctx, int n)
66 {
67         struct bitmap *bm;
68
69         if (!mem_ctx) return NULL;
70
71         bm = (struct bitmap *)talloc(mem_ctx, sizeof(*bm));
72
73         if (!bm) return NULL;
74         
75         bm->n = n;
76         bm->b = (uint32 *)talloc(mem_ctx, sizeof(bm->b[0])*(n+31)/32);
77         if (!bm->b) {
78                 return NULL;
79         }
80
81         memset(bm->b, 0, sizeof(bm->b[0])*(n+31)/32);
82
83         return bm;
84 }
85
86 /****************************************************************************
87 copy as much of the source bitmap as will fit in the destination bitmap.
88 ****************************************************************************/
89
90 int bitmap_copy(struct bitmap * const dst, const struct bitmap * const src)
91 {
92         int count = MIN(dst->n, src->n);
93
94         SMB_ASSERT(dst->b != src->b);
95         memcpy(dst->b, src->b, sizeof(dst->b[0])*(count+31)/32);
96
97         return count;
98 }
99
100 /****************************************************************************
101 set a bit in a bitmap
102 ****************************************************************************/
103 BOOL bitmap_set(struct bitmap *bm, unsigned i)
104 {
105         if (i >= bm->n) {
106                 DEBUG(0,("Setting invalid bitmap entry %d (of %d)\n",
107                       i, bm->n));
108                 return False;
109         }
110         bm->b[i/32] |= (1<<(i%32));
111         return True;
112 }
113
114 /****************************************************************************
115 clear a bit in a bitmap
116 ****************************************************************************/
117 BOOL bitmap_clear(struct bitmap *bm, unsigned i)
118 {
119         if (i >= bm->n) {
120                 DEBUG(0,("clearing invalid bitmap entry %d (of %d)\n",
121                       i, bm->n));
122                 return False;
123         }
124         bm->b[i/32] &= ~(1<<(i%32));
125         return True;
126 }
127
128 /****************************************************************************
129 query a bit in a bitmap
130 ****************************************************************************/
131 BOOL bitmap_query(struct bitmap *bm, unsigned i)
132 {
133         if (i >= bm->n) return False;
134         if (bm->b[i/32] & (1<<(i%32))) {
135                 return True;
136         }
137         return False;
138 }
139
140 /****************************************************************************
141 find a zero bit in a bitmap starting at the specified offset, with
142 wraparound
143 ****************************************************************************/
144 int bitmap_find(struct bitmap *bm, unsigned ofs)
145 {
146         unsigned int i, j;
147
148         if (ofs > bm->n) ofs = 0;
149
150         i = ofs;
151         while (i < bm->n) {
152                 if (~(bm->b[i/32])) {
153                         j = i;
154                         do {
155                                 if (!bitmap_query(bm, j)) return j;
156                                 j++;
157                         } while (j & 31 && j < bm->n);
158                 }
159                 i += 32;
160                 i &= ~31;
161         }
162
163         i = 0;
164         while (i < ofs) {
165                 if (~(bm->b[i/32])) {
166                         j = i;
167                         do {
168                                 if (!bitmap_query(bm, j)) return j;
169                                 j++;
170                         } while (j & 31 && j < bm->n);
171                 }
172                 i += 32;
173                 i &= ~31;
174         }
175
176         return -1;
177 }