← Back to branch summary

~zulcss/samba/samab-3.4-test

« back to all changes in this revision

Viewing changes to source3/lib/bitmap.c

  • Committer: Chuck Short
  • Date: 2010-05-20 18:57:13 UTC
  • Revision ID: zulcss@ubuntu.com-20100520185713-hwqvf9t50z830wck
Initial commit

Show diffs side-by-side

added added

removed removed

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