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 20 namespace 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 */ 34 template <class Accessor> 35 class AllocationDescriptorList { 36 private: 37 typedef typename Accessor::DescriptorType Descriptor; 38 public: 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 102 private: 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 209 class ShortDescriptorAccessor { 210 public: 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 } 233 private: 234 uint16 fPartition; 235 }; 236 237 class LongDescriptorAccessor { 238 public: 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