← Back to branch summary

~vcs-imports/samba/main

« back to all changes in this revision

Viewing changes to source/lib/bitmap.c

  • Committer: jerry
  • Date: 2006-07-14 21:48:39 UTC
  • Revision ID: vcs-imports@canonical.com-20060714214839-586d8c489a8fcead
gutting trunk to move to svn:externals

Show diffs side-by-side

added added

removed removed

Lines of Context:
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 = 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
 
/****************************************************************************
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 = 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
 
/****************************************************************************
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(uint32)*((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
 
}