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: %Ld, "
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 #%ld found NULL\n", _DescriptorNumber()));
136			status = B_ERROR;
137			break;
138		}
139	}
140
141	return status;
142}
143
144
145//	#pragma - Private methods
146
147
148template<class Accessor>
149typename AllocationDescriptorList<Accessor>::Descriptor*
150AllocationDescriptorList<Accessor>::_CurrentDescriptor() const
151{
152	TRACE(("AllocationDescriptorList<>::_CurrentDescriptor:\n"
153		"\t_DescriptorIndex() + 1 * sizeof(Descriptor) = %ld\n"
154		"\t_DescriptorArraySize() = %ld\n"
155		"\t_DescriptorArray() = %p\n",
156		(_DescriptorIndex() + 1) * sizeof(Descriptor),
157		_DescriptorArraySize(), _DescriptorArray()));
158
159	return ((_DescriptorIndex() + 1) * sizeof(Descriptor)
160		<= _DescriptorArraySize())
161		? &(_DescriptorArray()[_DescriptorIndex()])
162		: NULL;
163}
164
165
166template<class Accessor>
167status_t
168AllocationDescriptorList<Accessor>::_MoveToNextDescriptor()
169{
170	Descriptor* descriptor = _CurrentDescriptor();
171	if (!descriptor)
172		return B_ENTRY_NOT_FOUND;
173
174	// Increment our indices and get the next descriptor
175	// from this extent.
176	fBlockIndex += fAccessor.GetLength(*descriptor);
177	fDescriptorIndex++;
178	fDescriptorNumber++;
179	descriptor = _CurrentDescriptor();
180
181	// If no such descriptor exists, we've run out of
182	// descriptors in this extent, and we're done. The
183	// next time _CurrentDescriptor() is called, it will
184	// return NULL, signifying this. Otherwise, we have to
185	// see if the new descriptor identifies the next extent
186	// of allocation descriptors, in which case we have to
187	// load up the appropriate extent (guaranteed to be at
188	// most one block in length by UDF-2.01 5.1 and UDF-2.01
189	// 2.3.11).
190	_WalkContinuationChain(descriptor);
191
192	return B_ERROR;
193}
194
195
196template<class Accessor>
197void
198AllocationDescriptorList<Accessor>::_WalkContinuationChain(Descriptor *descriptor)
199{
200	TRACE(("AllocationDescriptorList<>::_WalkContinuationChain: descriptor = %p\n",
201		descriptor));
202	if (descriptor
203		&& fAccessor.GetType(*descriptor) == EXTENT_TYPE_CONTINUATION) {
204		// Load the new block, make sure we're not trying
205		// to read from the icb descriptors anymore, and
206		// reset the descriptor index.
207		fAdditionalDescriptors.SetTo(fAccessor, *descriptor);
208		fReadFromIcb = false;
209		fDescriptorIndex = 0;
210
211		// Make sure that the first descriptor in this extent isn't
212		// another continuation. That would be stupid, but not
213		// technically illegal.
214		_WalkContinuationChain(_CurrentDescriptor());
215	}
216}
217
218
219template<class Accessor>
220void
221AllocationDescriptorList<Accessor>::_Rewind()
222{
223	fDescriptorIndex = 0;
224	fDescriptorNumber = 0;
225	fReadFromIcb = true;
226}
227
228
229template<class Accessor>
230typename AllocationDescriptorList<Accessor>::Descriptor*
231AllocationDescriptorList<Accessor>::_DescriptorArray() const
232{
233	return fReadFromIcb ? fIcbDescriptors
234		: (typename AllocationDescriptorList<Accessor>::Descriptor *)
235			fAdditionalDescriptors.Block();
236}
237
238
239template<class Accessor>
240size_t
241AllocationDescriptorList<Accessor>::_DescriptorArraySize() const
242{
243	return fReadFromIcb ? fIcbDescriptorsSize
244		: fAdditionalDescriptors.BlockSize();
245}
246
247
248//	pragma - Accessors
249
250
251class ShortDescriptorAccessor {
252public:
253	ShortDescriptorAccessor(uint16 partition)
254		:
255		fPartition(partition)
256	{
257	}
258
259	typedef short_address DescriptorType;
260
261	inline uint32 GetBlock(DescriptorType &descriptor) const
262	{
263		return descriptor.block();
264	}
265
266	inline uint32 GetLength(DescriptorType &descriptor) const
267	{
268		return descriptor.length();
269	}
270
271	inline uint16 GetPartition(DescriptorType &descriptor) const
272	{
273		return fPartition;
274	}
275
276	inline uint8 GetType(DescriptorType &descriptor) const
277	{
278		return descriptor.type();
279	}
280
281private:
282	uint16 			fPartition;
283};
284
285
286class LongDescriptorAccessor {
287public:
288	typedef long_address DescriptorType;
289
290	inline uint32 GetBlock(DescriptorType &descriptor) const
291	{
292		return descriptor.block();
293	}
294
295	inline uint32 GetLength(DescriptorType &descriptor) const
296	{
297		return descriptor.length();
298	}
299
300	inline uint16 GetPartition(DescriptorType &descriptor) const
301	{
302		return descriptor.partition();
303	}
304
305	inline uint8 GetType(DescriptorType &descriptor) const
306	{
307		return descriptor.type();
308	}
309};
310
311#endif	// _UDF_ALLOCATION_DESCRIPTOR_LIST_H
312