1a1b0ec30SJérôme Duval/*
2a1b0ec30SJérôme Duval * Copyright 2001-2010, Haiku Inc. All rights reserved.
3a1b0ec30SJérôme Duval * This file may be used under the terms of the MIT License.
4a1b0ec30SJérôme Duval *
5a1b0ec30SJérôme Duval * Authors:
6a1b0ec30SJérôme Duval *		Janito V. Ferreira Filho
7eb7aa0daSJérôme Duval *		J��r��me Duval
8a1b0ec30SJérôme Duval */
9a1b0ec30SJérôme Duval
10a1b0ec30SJérôme Duval
11a1b0ec30SJérôme Duval#include "BitmapBlock.h"
12a1b0ec30SJérôme Duval
13ce4e12caSJérôme Duval#include "CRCTable.h"
14ce4e12caSJérôme Duval
15a1b0ec30SJérôme Duval
16a1b0ec30SJérôme Duval//#define TRACE_EXT2
17a1b0ec30SJérôme Duval#ifdef TRACE_EXT2
18a1b0ec30SJérôme Duval#	define TRACE(x...) dprintf("\33[34mext2:\33[0m " x)
19a1b0ec30SJérôme Duval#else
20a1b0ec30SJérôme Duval#	define TRACE(x...) ;
21a1b0ec30SJérôme Duval#endif
22eb7aa0daSJérôme Duval#define ERROR(x...) dprintf("\33[34mext2:\33[0m " x)
23a1b0ec30SJérôme Duval
24a1b0ec30SJérôme Duval
25a1b0ec30SJérôme DuvalBitmapBlock::BitmapBlock(Volume* volume, uint32 numBits)
26a1b0ec30SJérôme Duval	:
27a1b0ec30SJérôme Duval	CachedBlock(volume),
28ce4e12caSJérôme Duval	fVolume(volume),
29a1b0ec30SJérôme Duval	fData(NULL),
30a1b0ec30SJérôme Duval	fReadOnlyData(NULL),
314359b745SJérôme Duval	fNumBits(numBits),
324359b745SJérôme Duval	fMaxIndex(fNumBits >> 5)
33a1b0ec30SJérôme Duval{
34a130bab3SJérôme Duval	TRACE("BitmapBlock::BitmapBlock(): num bits: %" B_PRIu32 "\n", fNumBits);
35a1b0ec30SJérôme Duval}
36a1b0ec30SJérôme Duval
37a1b0ec30SJérôme Duval
38a1b0ec30SJérôme DuvalBitmapBlock::~BitmapBlock()
39a1b0ec30SJérôme Duval{
40a1b0ec30SJérôme Duval}
41a1b0ec30SJérôme Duval
42a1b0ec30SJérôme Duval
43fd4998dcSJérôme Duvalbool
44eb7aa0daSJérôme DuvalBitmapBlock::SetTo(off_t block)
45a1b0ec30SJérôme Duval{
46a1b0ec30SJérôme Duval	fData = NULL;
47a1b0ec30SJérôme Duval	fReadOnlyData = (uint32*)CachedBlock::SetTo(block);
48a1b0ec30SJérôme Duval
49a1b0ec30SJérôme Duval	return fReadOnlyData != NULL;
50a1b0ec30SJérôme Duval}
51a1b0ec30SJérôme Duval
52a1b0ec30SJérôme Duval
53fd4998dcSJérôme Duvalbool
54eb7aa0daSJérôme DuvalBitmapBlock::SetToWritable(Transaction& transaction, off_t block, bool empty)
55a1b0ec30SJérôme Duval{
56a1b0ec30SJérôme Duval	fReadOnlyData = NULL;
57a1b0ec30SJérôme Duval	fData = (uint32*)CachedBlock::SetToWritable(transaction, block, empty);
58a1b0ec30SJérôme Duval
59a1b0ec30SJérôme Duval	return fData != NULL;
60a1b0ec30SJérôme Duval}
61a1b0ec30SJérôme Duval
62a1b0ec30SJérôme Duval
63fd4998dcSJérôme Duvalbool
64fd4998dcSJérôme DuvalBitmapBlock::_Check(uint32 start, uint32 length, bool marked)
65a1b0ec30SJérôme Duval{
66a1b0ec30SJérôme Duval	const uint32* data = fData == NULL ? fReadOnlyData : fData;
67a1b0ec30SJérôme Duval	if (data == NULL)
68a1b0ec30SJérôme Duval		return false;
69a1b0ec30SJérôme Duval
70a1b0ec30SJérôme Duval	if (start + length > fNumBits)
71a1b0ec30SJérôme Duval		return false;
72d8772e0cSJérôme Duval	if (length == 0)
73d8772e0cSJérôme Duval		return true;
74a1b0ec30SJérôme Duval
75a1b0ec30SJérôme Duval	uint32 startIndex = start >> 5;
76a1b0ec30SJérôme Duval	uint32 startBit = start & 0x1F;
77d8772e0cSJérôme Duval	uint32 remainingBits = (length + startBit) & 0x1F;
78a1b0ec30SJérôme Duval
79a1b0ec30SJérôme Duval	uint32 iterations;
80fd4998dcSJérôme Duval
81a1b0ec30SJérôme Duval	if (length < 32) {
82a1b0ec30SJérôme Duval		if (startBit + length < 32) {
83eb7aa0daSJérôme Duval			uint32 bits = B_LENDIAN_TO_HOST_INT32(data[startIndex]);
84a1b0ec30SJérôme Duval
85a1b0ec30SJérôme Duval			uint32 mask = (1 << (startBit + length)) - 1;
86a1b0ec30SJérôme Duval			mask &= ~((1 << startBit) - 1);
87fd4998dcSJérôme Duval
88fd4998dcSJérôme Duval			return (bits & mask) == (marked ? mask : 0);
89a1b0ec30SJérôme Duval		} else
90a1b0ec30SJérôme Duval			iterations = 0;
91a1b0ec30SJérôme Duval	} else
92a1b0ec30SJérôme Duval		iterations = (length - 32 + startBit) >> 5;
93a1b0ec30SJérôme Duval
94a1b0ec30SJérôme Duval	uint32 index = startIndex;
95fd4998dcSJérôme Duval
96a1b0ec30SJérôme Duval	if (startBit != 0) {
97fd4998dcSJérôme Duval		uint32 mask = ~((1 << startBit) - 1);
98a1b0ec30SJérôme Duval		uint32 bits = B_LENDIAN_TO_HOST_INT32(data[index]);
99a1b0ec30SJérôme Duval
100fd4998dcSJérôme Duval		if ((bits & mask) != (marked ? mask : 0)) {
101a130bab3SJérôme Duval			TRACE("BitmapBlock::_Check(): start %" B_PRIx32 " mask %" B_PRIx32
102a130bab3SJérôme Duval				"\n", bits, mask);
103a1b0ec30SJérôme Duval			return false;
104d8772e0cSJérôme Duval		}
105a1b0ec30SJérôme Duval
106a1b0ec30SJérôme Duval		index += 1;
107de66992bSJérôme Duval	} else
108de66992bSJérôme Duval		iterations++;
109a1b0ec30SJérôme Duval
110a1b0ec30SJérôme Duval	for (; iterations > 0; --iterations) {
111fd4998dcSJérôme Duval		if (data[index++] != (marked ? 0xFFFFFFFF : 0)) {
112a130bab3SJérôme Duval			TRACE("BitmapBlock::_Check(): iterations %" B_PRIu32 " bits: %"
113a130bab3SJérôme Duval				B_PRIx32 "\n", iterations, data[index - 1]);
114a1b0ec30SJérôme Duval			return false;
115d8772e0cSJérôme Duval		}
116a1b0ec30SJérôme Duval	}
117a1b0ec30SJérôme Duval
118a1b0ec30SJérôme Duval	if (remainingBits != 0) {
119fd4998dcSJérôme Duval		uint32 mask = (1 << remainingBits) - 1;
120a1b0ec30SJérôme Duval
121a1b0ec30SJérôme Duval		uint32 bits = B_LENDIAN_TO_HOST_INT32(data[index]);
122fd4998dcSJérôme Duval		if ((bits & mask) != (marked ? mask : 0)) {
123a130bab3SJérôme Duval			TRACE("BitmapBlock::_Check(): remainingBits %" B_PRIu32
124a130bab3SJérôme Duval				" remaining %" B_PRIx32 " mask %" B_PRIx32 "\n", remainingBits,
125a130bab3SJérôme Duval				bits, mask);
126a1b0ec30SJérôme Duval			return false;
127d8772e0cSJérôme Duval		}
128a1b0ec30SJérôme Duval	}
129a1b0ec30SJérôme Duval
130a1b0ec30SJérôme Duval	return true;
131a1b0ec30SJérôme Duval}
132a1b0ec30SJérôme Duval
133a1b0ec30SJérôme Duval
134fd4998dcSJérôme Duvalbool
135fd4998dcSJérôme DuvalBitmapBlock::_Update(uint32 start, uint32 length, bool mark, bool force)
136a1b0ec30SJérôme Duval{
137a130bab3SJérôme Duval	TRACE("BitmapBlock::_Update(%" B_PRIu32 ", %" B_PRIu32 ", %c, %c)\n",
138a130bab3SJérôme Duval		start, length, mark ? 't' : 'f', force ? 't' : 'f');
139a1b0ec30SJérôme Duval
140a1b0ec30SJérôme Duval	if (fData == NULL || start + length > fNumBits)
141a1b0ec30SJérôme Duval		return false;
142a1b0ec30SJérôme Duval
143a1b0ec30SJérôme Duval	uint32 startIndex = start >> 5;
144a1b0ec30SJérôme Duval	uint32 startBit = start & 0x1F;
145d8772e0cSJérôme Duval	uint32 remainingBits = (length + startBit) & 0x1F;
146a1b0ec30SJérôme Duval
147a130bab3SJérôme Duval	TRACE("BitmapBlock::_Update(): start index: %" B_PRIu32 ", start bit: %"
148a130bab3SJérôme Duval		B_PRIu32 ", remaining bits: %" B_PRIu32 ")\n", startIndex, startBit,
149a130bab3SJérôme Duval		remainingBits);
150a1b0ec30SJérôme Duval	uint32 iterations;
151fd4998dcSJérôme Duval
152a1b0ec30SJérôme Duval	if (length < 32) {
153a1b0ec30SJérôme Duval		if (startBit + length < 32) {
154a1b0ec30SJérôme Duval			uint32 bits = B_LENDIAN_TO_HOST_INT32(fData[startIndex]);
155a130bab3SJérôme Duval			TRACE("BitmapBlock::_Update(): bits: %" B_PRIx32 "\n", bits);
156a1b0ec30SJérôme Duval
157a1b0ec30SJérôme Duval			uint32 mask = (1 << (startBit + length)) - 1;
158a1b0ec30SJérôme Duval			mask &= ~((1 << startBit) - 1);
159fd4998dcSJérôme Duval
160a130bab3SJérôme Duval			TRACE("BitmapBlock::_Update(): mask: %" B_PRIx32 "\n", mask);
161a1b0ec30SJérôme Duval
162fd4998dcSJérôme Duval			if ((bits & mask) != (mark ? 0 : mask)) {
163a130bab3SJérôme Duval				ERROR("BitmapBlock::_Update() Marking failed bits %" B_PRIx32
164a130bab3SJérôme Duval					" startBit %" B_PRIu32 "\n", bits, startBit);
165a1b0ec30SJérôme Duval				return false;
166d8772e0cSJérôme Duval			}
167fd4998dcSJérôme Duval
168fd4998dcSJérôme Duval			if (mark)
169fd4998dcSJérôme Duval			    bits |= mask;
170fd4998dcSJérôme Duval			else
171fd4998dcSJérôme Duval			    bits &= ~mask;
172fd4998dcSJérôme Duval
173a130bab3SJérôme Duval			TRACE("BitmapBlock::_Update(): updated bits: %" B_PRIx32 "\n",
174a130bab3SJérôme Duval				bits);
175a1b0ec30SJérôme Duval			fData[startIndex] = B_HOST_TO_LENDIAN_INT32(bits);
176fd4998dcSJérôme Duval
177a1b0ec30SJérôme Duval			return true;
178a1b0ec30SJérôme Duval		} else
179a1b0ec30SJérôme Duval			iterations = 0;
180a1b0ec30SJérôme Duval	} else
181a1b0ec30SJérôme Duval		iterations = (length - 32 + startBit) >> 5;
182a1b0ec30SJérôme Duval
183a130bab3SJérôme Duval	TRACE("BitmapBlock::_Update(): iterations: %" B_PRIu32 "\n", iterations);
184a1b0ec30SJérôme Duval	uint32 index = startIndex;
185fd4998dcSJérôme Duval
186a1b0ec30SJérôme Duval	if (startBit != 0) {
187fd4998dcSJérôme Duval		uint32 mask = ~((1 << startBit) - 1);
188a1b0ec30SJérôme Duval		uint32 bits = B_LENDIAN_TO_HOST_INT32(fData[index]);
189a1b0ec30SJérôme Duval
190a130bab3SJérôme Duval		TRACE("BitmapBlock::_Update(): mask: %" B_PRIx32 ", bits: %" B_PRIx32
191a130bab3SJérôme Duval			"\n", mask, bits);
192a1b0ec30SJérôme Duval
193fd4998dcSJérôme Duval		if (!force && (bits & mask) != (mark ? 0 : mask))
194a1b0ec30SJérôme Duval			return false;
195a1b0ec30SJérôme Duval
196fd4998dcSJérôme Duval		if (mark)
197fd4998dcSJérôme Duval			bits |= mask;
198fd4998dcSJérôme Duval		else
199fd4998dcSJérôme Duval			bits &= ~mask;
200a1b0ec30SJérôme Duval		fData[index] = B_HOST_TO_LENDIAN_INT32(bits);
201a1b0ec30SJérôme Duval
202a130bab3SJérôme Duval		TRACE("BitmapBlock::_Update(): updated bits: %" B_PRIx32 "\n", bits);
203a1b0ec30SJérôme Duval		index += 1;
204de66992bSJérôme Duval	} else
205de66992bSJérôme Duval		iterations++;
206a1b0ec30SJérôme Duval
207a1b0ec30SJérôme Duval	for (; iterations > 0; --iterations) {
208fd4998dcSJérôme Duval		if (!force && fData[index] != (mark ? 0 : 0xFFFFFFFF)) {
209fd4998dcSJérôme Duval			ERROR("BitmapBlock::_Update() Marking failed "
210a130bab3SJérôme Duval				"index %" B_PRIu32 ", iterations %" B_PRId32 "\n", index,
211a130bab3SJérôme Duval				iterations);
212a1b0ec30SJérôme Duval			return false;
213d8772e0cSJérôme Duval		}
214fd4998dcSJérôme Duval		fData[index++] = (mark ? 0xFFFFFFFF : 0);
215a1b0ec30SJérôme Duval	}
216a1b0ec30SJérôme Duval
217fd4998dcSJérôme Duval	TRACE("BitmapBlock::_Update(): Finished iterations\n");
218a1b0ec30SJérôme Duval
219a1b0ec30SJérôme Duval	if (remainingBits != 0) {
220fd4998dcSJérôme Duval		uint32 mask = (1 << remainingBits) - 1;
221a1b0ec30SJérôme Duval		uint32 bits = B_LENDIAN_TO_HOST_INT32(fData[index]);
222a1b0ec30SJérôme Duval
223a130bab3SJérôme Duval		TRACE("BitmapBlock::_Update(): mask: %" B_PRIx32 ", bits: %" B_PRIx32
224a130bab3SJérôme Duval			"\n", mask, bits);
225a1b0ec30SJérôme Duval
226fd4998dcSJérôme Duval		if (!force && (bits & mask) != (mark ? 0 : mask)) {
227fd4998dcSJérôme Duval			ERROR("BitmapBlock::_Update() Marking failed remaining\n");
228a1b0ec30SJérôme Duval			return false;
229d8772e0cSJérôme Duval		}
230a1b0ec30SJérôme Duval
231fd4998dcSJérôme Duval		if (mark)
232fd4998dcSJérôme Duval			bits |= mask;
233fd4998dcSJérôme Duval		else
234fd4998dcSJérôme Duval			bits &= ~mask;
235a1b0ec30SJérôme Duval		fData[index] = B_HOST_TO_LENDIAN_INT32(bits);
236a1b0ec30SJérôme Duval
237a130bab3SJérôme Duval		TRACE("BitmapBlock::_Update(): updated bits: %" B_PRIx32 "\n", bits);
238a1b0ec30SJérôme Duval	}
239a1b0ec30SJérôme Duval
240a1b0ec30SJérôme Duval	return true;
241a1b0ec30SJérôme Duval}
242a1b0ec30SJérôme Duval
243a1b0ec30SJérôme Duval
244a1b0ec30SJérôme Duvalvoid
24509af5be2SJérôme DuvalBitmapBlock::_FindNext(uint32& pos, bool marked)
246a1b0ec30SJérôme Duval{
247a130bab3SJérôme Duval	TRACE("BitmapBlock::_FindNext(): pos: %" B_PRIu32 "\n", pos);
248a1b0ec30SJérôme Duval
249a1b0ec30SJérôme Duval	const uint32* data = fData == NULL ? fReadOnlyData : fData;
250a1b0ec30SJérôme Duval	if (data == NULL)
251a1b0ec30SJérôme Duval		return;
252a1b0ec30SJérôme Duval
253a1b0ec30SJérôme Duval	if (pos >= fNumBits) {
254a1b0ec30SJérôme Duval		pos = fNumBits;
255a1b0ec30SJérôme Duval		return;
256a1b0ec30SJérôme Duval	}
257a1b0ec30SJérôme Duval
258a1b0ec30SJérôme Duval	uint32 index = pos >> 5;
259a1b0ec30SJérôme Duval	uint32 bit = pos & 0x1F;
2604359b745SJérôme Duval	uint32 maxBit = 32;
261a1b0ec30SJérôme Duval
2624359b745SJérôme Duval	uint32 mask = ~((1 << bit) - 1);
263a1b0ec30SJérôme Duval	uint32 bits = B_LENDIAN_TO_HOST_INT32(data[index]);
264a1b0ec30SJérôme Duval
265a130bab3SJérôme Duval	TRACE("BitmapBlock::_FindNext(): index: %" B_PRIu32 ", bit: %" B_PRIu32
266a130bab3SJérôme Duval		", mask: %" B_PRIx32 ", bits: %" B_PRIx32 "\n", index, bit, mask,
267a130bab3SJérôme Duval		bits);
268a1b0ec30SJérôme Duval
2694359b745SJérôme Duval	bits &= mask;
27009af5be2SJérôme Duval	if (bits == (marked ? 0 : mask) && index < fMaxIndex) {
27109af5be2SJérôme Duval		// Find a 32 bits block that has a marked bit
272a1b0ec30SJérôme Duval		do {
273a1b0ec30SJérôme Duval			index++;
27409af5be2SJérôme Duval		} while (index < fMaxIndex && data[index] == (marked ? 0 : 0xFFFFFFFF));
275a1b0ec30SJérôme Duval		bit = 0;
2764359b745SJérôme Duval		mask = 0xffffffff;
277a1b0ec30SJérôme Duval	}
278a1b0ec30SJérôme Duval
2794359b745SJérôme Duval	if (index >= fMaxIndex) {
2804359b745SJérôme Duval		maxBit = fNumBits & 0x1F;
2814359b745SJérôme Duval
2824359b745SJérôme Duval		if (maxBit == 0) {
2834359b745SJérôme Duval			// Not found
28409af5be2SJérôme Duval			TRACE("BitmapBlock::_FindNext(): reached end of block, "
285a130bab3SJérôme Duval				"num bits: %" B_PRIu32 "\n", fNumBits);
2864359b745SJérôme Duval			pos = fNumBits;
2874359b745SJérôme Duval			return;
2884359b745SJérôme Duval		}
2894359b745SJérôme Duval		bits = B_LENDIAN_TO_HOST_INT32(data[fMaxIndex]);
2904359b745SJérôme Duval		mask &= (1 << maxBit) - 1;
29109af5be2SJérôme Duval		if ((bits & mask) == (marked ? 0 : mask)) {
29209af5be2SJérôme Duval			TRACE("BitmapBlock::_FindNext(): reached end of block, "
293a130bab3SJérôme Duval				"num bits: %" B_PRIu32 "\n", fNumBits);
2944359b745SJérôme Duval			pos = fNumBits;
2954359b745SJérôme Duval			return;
2964359b745SJérôme Duval		}
2974359b745SJérôme Duval		maxBit++;
2984359b745SJérôme Duval	} else
2994359b745SJérôme Duval		bits = B_LENDIAN_TO_HOST_INT32(data[index]);
3004359b745SJérôme Duval
301583f39e9SJérôme Duval	for (; bit < maxBit; ++bit) {
30209af5be2SJérôme Duval		// Find the marked bit
30309af5be2SJérôme Duval		if ((bits >> bit & 1) != (marked ? 0U : 1U)) {
304a1b0ec30SJérôme Duval			pos = index << 5 | bit;
305a130bab3SJérôme Duval			TRACE("BitmapBlock::_FindNext(): found bit: %" B_PRIu32 "\n", pos);
306a1b0ec30SJérôme Duval			return;
307a1b0ec30SJérôme Duval		}
308a1b0ec30SJérôme Duval	}
309a1b0ec30SJérôme Duval
310a130bab3SJérôme Duval	panic("Couldn't find bit inside an uint32 (%" B_PRIx32 ")\n", bits);
311a1b0ec30SJérôme Duval}
312a1b0ec30SJérôme Duval
313a1b0ec30SJérôme Duval
314a1b0ec30SJérôme Duvalvoid
315a1b0ec30SJérôme DuvalBitmapBlock::FindPreviousMarked(uint32& pos)
316a1b0ec30SJérôme Duval{
317a130bab3SJérôme Duval	TRACE("BitmapBlock::FindPreviousMarked(%" B_PRIu32 ")\n", pos);
318a1b0ec30SJérôme Duval	const uint32* data = fData == NULL ? fReadOnlyData : fData;
319a1b0ec30SJérôme Duval	if (data == NULL)
320a1b0ec30SJérôme Duval		return;
321a1b0ec30SJérôme Duval
322a1b0ec30SJérôme Duval	if (pos >= fNumBits)
323a1b0ec30SJérôme Duval		pos = fNumBits;
324a1b0ec30SJérôme Duval
325a1b0ec30SJérôme Duval	if (pos == 0)
326a1b0ec30SJérôme Duval		return;
327a1b0ec30SJérôme Duval
328a1b0ec30SJérôme Duval	uint32 index = pos >> 5;
329a1b0ec30SJérôme Duval	int32 bit = pos & 0x1F;
330a1b0ec30SJérôme Duval
33125a55b41SJérôme Duval	uint32 mask = (1 << bit) - 1;
332a1b0ec30SJérôme Duval	uint32 bits = B_LENDIAN_TO_HOST_INT32(data[index]);
333a1b0ec30SJérôme Duval	bits = bits & mask;
334a1b0ec30SJérôme Duval
335a130bab3SJérôme Duval	TRACE("BitmapBlock::FindPreviousMarked(): index: %" B_PRIu32 " bit: %"
336a130bab3SJérôme Duval		B_PRIu32 " bits: %" B_PRIx32 "\n", index, bit, bits);
337a1b0ec30SJérôme Duval
338a1b0ec30SJérôme Duval	if (bits == 0) {
339a1b0ec30SJérôme Duval		// Find an block of 32 bits that has a marked bit
340a1b0ec30SJérôme Duval		do {
341a1b0ec30SJérôme Duval			index--;
34225a55b41SJérôme Duval		} while (data[index] == 0 && index > 0);
343a1b0ec30SJérôme Duval
344a1b0ec30SJérôme Duval		bits = B_LENDIAN_TO_HOST_INT32(data[index]);
345a1b0ec30SJérôme Duval		if (bits == 0) {
346a1b0ec30SJérôme Duval			// Not found
347a1b0ec30SJérôme Duval			pos = 0;
348a1b0ec30SJérôme Duval			return;
349a1b0ec30SJérôme Duval		}
350a1b0ec30SJérôme Duval
351a1b0ec30SJérôme Duval		bit = 31;
352a1b0ec30SJérôme Duval	}
353a1b0ec30SJérôme Duval
354a130bab3SJérôme Duval	TRACE("BitmapBlock::FindPreviousMarked(): index: %" B_PRIu32 " bit: %"
355a130bab3SJérôme Duval		B_PRIu32 " bits: %" B_PRIx32 "\n", index, bit, bits);
356d8772e0cSJérôme Duval
357a1b0ec30SJérôme Duval	for (; bit >= 0; --bit) {
35825a55b41SJérôme Duval		// Find the marked bit
359a1b0ec30SJérôme Duval		if ((bits >> bit & 1) != 0) {
360a1b0ec30SJérôme Duval			pos = index << 5 | bit;
361a1b0ec30SJérôme Duval			return;
362a1b0ec30SJérôme Duval		}
363a1b0ec30SJérôme Duval	}
364a1b0ec30SJérôme Duval
365d8772e0cSJérôme Duval	panic("Couldn't find marked bit inside an int32 with value different than "
366a1b0ec30SJérôme Duval		"zero!?\n");
367a1b0ec30SJérôme Duval}
368a1b0ec30SJérôme Duval
369a1b0ec30SJérôme Duval
370a1b0ec30SJérôme Duvalvoid
371a1b0ec30SJérôme DuvalBitmapBlock::FindLargestUnmarkedRange(uint32& start, uint32& length)
372a1b0ec30SJérôme Duval{
373a1b0ec30SJérôme Duval	const uint32* data = fData == NULL ? fReadOnlyData : fData;
374a1b0ec30SJérôme Duval	if (data == NULL)
375a1b0ec30SJérôme Duval		return;
376a1b0ec30SJérôme Duval
377a1b0ec30SJérôme Duval	uint32 wordSpan = length >> 5;
378a1b0ec30SJérôme Duval	uint32 startIndex = 0;
379a1b0ec30SJérôme Duval	uint32 index = 0;
380a1b0ec30SJérôme Duval	uint32 bits = B_LENDIAN_TO_HOST_INT32(data[0]);
381a1b0ec30SJérôme Duval
382a130bab3SJérôme Duval	TRACE("BitmapBlock::FindLargestUnmarkedRange(): word span: %" B_PRIu32
383a130bab3SJérôme Duval		", last index: %" B_PRIu32 ", start index: %" B_PRIu32 ", index: %"
384a130bab3SJérôme Duval		B_PRIu32 ", bits: %" B_PRIx32 ", start: %" B_PRIu32 ", length: %"
385a130bab3SJérôme Duval		B_PRIu32 "\n", wordSpan, fMaxIndex, startIndex, index, bits, start,
386a1b0ec30SJérôme Duval		length);
387a1b0ec30SJérôme Duval
388a1b0ec30SJérôme Duval	if (wordSpan == 0) {
389a1b0ec30SJérôme Duval		uint32 startPos = 0;
390a1b0ec30SJérôme Duval		uint32 endPos = 0;
391a1b0ec30SJérôme Duval
392a1b0ec30SJérôme Duval		while (endPos < fNumBits) {
393a1b0ec30SJérôme Duval			FindNextUnmarked(startPos);
394a1b0ec30SJérôme Duval			endPos = startPos;
395a1b0ec30SJérôme Duval
396