xref: /haiku/src/add-ons/kernel/file_systems/udf/AllocationDescriptorList.h (revision 29f8805f6c70f1c819eb58ac2220647d8e40d6e7) 
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 */
32 template <class Accessor>
33 class AllocationDescriptorList {
34 private:
35 	typedef typename Accessor::DescriptorType Descriptor;
36 
37 public:
38 							AllocationDescriptorList(Icb *icb,
39 								Accessor accessor = Accessor());
40 
41 	status_t				FindExtent(off_t start, long_address *extent,
42 								bool *isEmpty);
43 
44 private:
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 
69 template<class Accessor>
70 AllocationDescriptorList<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 */
99 template<class Accessor>
100 status_t
101 AllocationDescriptorList<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 
149 template<class Accessor>
150 typename AllocationDescriptorList<Accessor>::Descriptor*
151 AllocationDescriptorList<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 
167 template<class Accessor>
168 status_t
169 AllocationDescriptorList<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 
197 template<class Accessor>
198 void
199 AllocationDescriptorList<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 
220 template<class Accessor>
221 void
222 AllocationDescriptorList<Accessor>::_Rewind()
223 {
224 	fDescriptorIndex = 0;
225 	fDescriptorNumber = 0;
226 	fReadFromIcb = true;
227 }
228 
229 
230 template<class Accessor>
231 typename AllocationDescriptorList<Accessor>::Descriptor*
232 AllocationDescriptorList<Accessor>::_DescriptorArray() const
233 {
234 	return fReadFromIcb ? fIcbDescriptors
235 		: (typename AllocationDescriptorList<Accessor>::Descriptor *)
236 			fAdditionalDescriptors.Block();
237 }
238 
239 
240 template<class Accessor>
241 size_t
242 AllocationDescriptorList<Accessor>::_DescriptorArraySize() const
243 {
244 	return fReadFromIcb ? fIcbDescriptorsSize
245 		: fAdditionalDescriptors.BlockSize();
246 }
247 
248 
249 //	pragma - Accessors
250 
251 
252 class ShortDescriptorAccessor {
253 public:
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 
282 private:
283 	uint16 			fPartition;
284 };
285 
286 
287 class LongDescriptorAccessor {
288 public:
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