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