1/*
2 * Copyright 2008, Salvatore Benedetto, salvatore.benedetto@gmail.com
3 * Copyright 2003, Tyler Dauwalder, tyler@dauwalder.net.
4 * Distributed under the terms of the MIT License.
5 */
6
7#ifndef _UDF_ALLOCATION_DESCRIPTOR_LIST_H
8#define _UDF_ALLOCATION_DESCRIPTOR_LIST_H
9
10/*! \file AllocationDescriptorList.h */
11
12#include "UdfDebug.h"
13
14#include "Icb.h"
15#include "UdfStructures.h"
16#include "Volume.h"
17
18#include <util/kernel_cpp.h>
19
20/*!	\brief Common interface for dealing with the three standard
21	forms of allocation descriptors used in UDF icbs.
22
23	The \c Accessor class is an allocation descriptor accessor class
24	for the allocation scheme of interest. Instances of it should be
25	passable by	value, and should define the following public members:
26	- typedef DescriptorType;
27	- inline uint8 GetType(DescriptorType &descriptor);
28	- inline uint32 GetBlock(DescriptorType &descriptor);
29	- inline uint16 GetPartition(DescriptorType &descriptor);
30	- inline uint32 GetLength(DescriptorType &descriptor);
31*/
32template <class Accessor>
33class AllocationDescriptorList {
34private:
35	typedef typename Accessor::DescriptorType Descriptor;
36
37public:
38							AllocationDescriptorList(Icb *icb,
39								Accessor accessor = Accessor());
40
41	status_t				FindExtent(off_t start, long_address *extent,
42								bool *isEmpty);
43
44private:
45
46	off_t					_BlockIndex() const { return fBlockIndex; }
47	Descriptor				*_CurrentDescriptor() const;
48	Descriptor				*_DescriptorArray() const;
49	size_t 					_DescriptorArraySize() const;
50	int32					_DescriptorIndex() const { return fDescriptorIndex; }
51	int32					_DescriptorNumber() const { return fDescriptorNumber; }
52	status_t				_MoveToNextDescriptor();
53	void					_Rewind();
54	void					_WalkContinuationChain(Descriptor *descriptor);
55
56	Accessor 				fAccessor;
57	CachedBlock				fAdditionalDescriptors;
58	off_t					fBlockIndex;
59	int32					fDescriptorIndex;
60	int32					fDescriptorNumber;
61	Icb						*fIcb;
62	Descriptor				*fIcbDescriptors;
63	int32					fIcbDescriptorsSize;
64	bool					fReadFromIcb;
65	Volume					*fVolume;
66};
67
68
69template<class Accessor>
70AllocationDescriptorList<Accessor>::AllocationDescriptorList(Icb *icb,
71	Accessor accessor)
72		:
73		fAccessor(accessor),
74		fAdditionalDescriptors(icb->GetVolume()),
75		fBlockIndex(0),
76		fDescriptorIndex(0),
77		fDescriptorNumber(0),
78		fIcb(icb),
79		fIcbDescriptors((Descriptor *)icb->AllocationDescriptors()),
80		fIcbDescriptorsSize(icb->AllocationDescriptorsSize()),
81		fReadFromIcb(true),
82		fVolume(icb->GetVolume())
83{
84	TRACE(("AllocationDescriptorList<>::AllocationDescriptorList\n"));
85	_WalkContinuationChain(_CurrentDescriptor());
86}
87
88
89/*! \brief Finds the extent for the given address in the stream,
90	returning it in the address pointed to by \a blockRun.
91
92	\param start The byte address of interest
93	\param extent The extent containing the stream address given
94			by \c start.
95	\param isEmpty If set to true, indicates that the given extent is
96			unrecorded  and thus its contents should be interpreted
97			as all zeros.
98*/
99template<class Accessor>
100status_t
101AllocationDescriptorList<Accessor>::FindExtent(off_t start,
102	long_address *extent, bool *isEmpty)
103{
104	TRACE(("AllocationDescriptorList<>::FindExtent: start: %" B_PRIdOFF ", "
105		"extent: %p, isEmpty: %p\n", start, extent, isEmpty));
106
107	off_t startBlock = start >> fVolume->BlockShift();
108
109	// This should never have to happen, as FindExtent is only called by
110	// Icb::_Read() sequentially, as a file read is performed, but you
111	// never know. :-)
112	if (startBlock < _BlockIndex())
113		_Rewind();
114
115	status_t status = B_OK;
116	while (true) {
117		Descriptor *descriptor = _CurrentDescriptor();
118		if (descriptor) {
119			if (_BlockIndex() <= startBlock && startBlock
120				< _BlockIndex() + fAccessor.GetLength(*descriptor)) {
121				// The start block is somewhere in this extent, so return
122				// the applicable tail end portion.
123				off_t offset = startBlock - _BlockIndex();
124				extent->set_block(fAccessor.GetBlock(*descriptor) + offset);
125				extent->set_partition(fAccessor.GetPartition(*descriptor));
126				extent->set_length(fAccessor.GetLength(*descriptor)
127					- (offset*fVolume->BlockSize()));
128				extent->set_type(fAccessor.GetType(*descriptor));
129				break;
130			} else {
131				_MoveToNextDescriptor();
132			}
133		} else {
134			TRACE_ERROR(("AllocationDescriptorList<>::FindExtent: "
135				"Descriptor #%" B_PRId32 " found NULL\n",
136				_DescriptorNumber()));
137			status = B_ERROR;
138			break;
139		}
140	}
141
142	return status;
143}
144
145
146//	#pragma - Private methods
147
148
149template<class Accessor>
150typename AllocationDescriptorList<Accessor>::Descriptor*
151AllocationDescriptorList<Accessor>::_CurrentDescriptor() const
152{
153	TRACE(("AllocationDescriptorList<>::_CurrentDescriptor:\n"
154		"\t_DescriptorIndex() + 1 * sizeof(Descriptor) = %ld\n"
155		"\t_DescriptorArraySize() = %ld\n"
156		"\t_DescriptorArray() = %p\n",
157		(_DescriptorIndex() + 1) * sizeof(Descriptor),
158		_DescriptorArraySize(), _DescriptorArray()));
159
160	return ((_DescriptorIndex() + 1) * sizeof(Descriptor)
161		<= _DescriptorArraySize())
162		? &(_DescriptorArray()[_DescriptorIndex()])
163		: NULL;
164}
165
166
167template<class Accessor>
168status_t
169AllocationDescriptorList<Accessor>::_MoveToNextDescriptor()
170{
171	Descriptor* descriptor = _CurrentDescriptor();
172	if (!descriptor)
173		return B_ENTRY_NOT_FOUND;
174
175	// Increment our indices and get the next descriptor
176	// from this extent.
177	fBlockIndex += fAccessor.GetLength(*descriptor);
178	fDescriptorIndex++;
179	fDescriptorNumber++;
180	descriptor = _CurrentDescriptor();
181
182	// If no such descriptor exists, we've run out of
183	// descriptors in this extent, and we're done. The
184	// next time _CurrentDescriptor() is called, it will
185	// return NULL, signifying this. Otherwise, we have to
186	// see if the new descriptor identifies the next extent
187	// of allocation descriptors, in which case we have to
188	// load up the appropriate extent (guaranteed to be at
189	// most one block in length by UDF-2.01 5.1 and UDF-2.01
190	// 2.3.11).
191	_WalkContinuationChain(descriptor);
192
193	return B_ERROR;
194}
195
196
197template<class Accessor>
198void
199AllocationDescriptorList<Accessor>::_WalkContinuationChain(Descriptor *descriptor)
200{
201	TRACE(("AllocationDescriptorList<>::_WalkContinuationChain: descriptor = %p\n",
202		descriptor));
203	if (descriptor
204		&& fAccessor.GetType(*descriptor) == EXTENT_TYPE_CONTINUATION) {
205		// Load the new block, make sure we're not trying
206		// to read from the icb descriptors anymore, and
207		// reset the descriptor index.
208		fAdditionalDescriptors.SetTo(fAccessor, *descriptor);
209		fReadFromIcb = false;
210		fDescriptorIndex = 0;
211
212		// Make sure that the first descriptor in this extent isn't
213		// another continuation. That would be stupid, but not
214		// technically illegal.
215		_WalkContinuationChain(_CurrentDescriptor());
216	}
217}
218
219
220template<class Accessor>
221void
222AllocationDescriptorList<Accessor>::_Rewind()
223{
224	fDescriptorIndex = 0;
225	fDescriptorNumber = 0;
226	fReadFromIcb = true;
227}
228
229
230template<class Accessor>
231typename AllocationDescriptorList<Accessor>::Descriptor*
232AllocationDescriptorList<Accessor>::_DescriptorArray() const
233{
234	return fReadFromIcb ? fIcbDescriptors
235		: (typename AllocationDescriptorList<Accessor>::Descriptor *)
236			fAdditionalDescriptors.Block();
237}
238
239
240template<class Accessor>
241size_t
242AllocationDescriptorList<Accessor>::_DescriptorArraySize() const
243{
244	return fReadFromIcb ? fIcbDescriptorsSize
245		: fAdditionalDescriptors.BlockSize();
246}
247
248
249//	pragma - Accessors
250
251
252class ShortDescriptorAccessor {
253public:
254	ShortDescriptorAccessor(uint16 partition)
255		:
256		fPartition(partition)
257	{
258	}
259
260	typedef short_address DescriptorType;
261
262	inline uint32 GetBlock(DescriptorType &descriptor) const
263	{
264		return descriptor.block();
265	}
266
267	inline uint32 GetLength(DescriptorType &descriptor) const
268	{
269		return descriptor.length();
270	}
271
272	inline uint16 GetPartition(DescriptorType &descriptor) const
273	{
274		return fPartition;
275	}
276
277	inline uint8 GetType(DescriptorType &descriptor) const
278	{
279		return descriptor.type();
280	}
281
282private:
283	uint16 			fPartition;
284};
285
286
287class LongDescriptorAccessor {
288public:
289	typedef long_address DescriptorType;
290
291	inline uint32 GetBlock(DescriptorType &descriptor) const
292	{
293		return descriptor.block();
294	}
295
296	inline uint32 GetLength(DescriptorType &descriptor) const
297	{
298		return descriptor.length();
299	}
300
301	inline uint16 GetPartition(DescriptorType &descriptor) const
302	{
303		return descriptor.partition();
304	}
305
306	inline uint8 GetType(DescriptorType &descriptor) const
307	{
308		return descriptor.type();
309	}
310};
311
312#endif	// _UDF_ALLOCATION_DESCRIPTOR_LIST_H
313