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/****************************************************************************
27allocate a bitmap of the specified size
28****************************************************************************/
29struct bitmap *bitmap_allocate(int n)
30{
31	struct bitmap *bm;
32
33	bm = SMB_MALLOC_P(struct bitmap);
34
35	if (!bm) return NULL;
36
37	bm->n = n;
38	bm->b = SMB_MALLOC_ARRAY(uint32, (n+31)/32);
39	if (!bm->b) {
40		SAFE_FREE(bm);
41		return NULL;
42	}
43
44	memset(bm->b, 0, sizeof(uint32)*((n+31)/32));
45
46	return bm;
47}
48
49/****************************************************************************
50free a bitmap.
51****************************************************************************/
52
53void bitmap_free(struct bitmap *bm)
54{
55	if (!bm)
56		return;
57
58	SAFE_FREE(bm->b);
59	SAFE_FREE(bm);
60}
61
62/****************************************************************************
63talloc a bitmap
64****************************************************************************/
65struct bitmap *bitmap_talloc(TALLOC_CTX *mem_ctx, int n)
66{
67	struct bitmap *bm;
68
69	if (!mem_ctx) return NULL;
70
71	bm = TALLOC_P(mem_ctx, struct bitmap);
72
73	if (!bm) return NULL;
74
75	bm->n = n;
76	bm->b = TALLOC_ARRAY(mem_ctx, uint32, (n+31)/32);
77	if (!bm->b) {
78		return NULL;
79	}
80
81	memset(bm->b, 0, sizeof(uint32)*((n+31)/32));
82
83	return bm;
84}
85
86/****************************************************************************
87copy as much of the source bitmap as will fit in the destination bitmap.
88****************************************************************************/
89
90int 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(uint32)*((count+31)/32));
96
97        return count;
98}
99
100/****************************************************************************
101set a bit in a bitmap
102****************************************************************************/
103BOOL 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/****************************************************************************
115clear a bit in a bitmap
116****************************************************************************/
117BOOL 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/****************************************************************************
129query a bit in a bitmap
130****************************************************************************/
131BOOL 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/****************************************************************************
141find a zero bit in a bitmap starting at the specified offset, with
142wraparound
143****************************************************************************/
144int 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}
178