1 /* 2 * Copyright 2010, Haiku Inc. All rights reserved. 3 * This file may be used under the terms of the MIT License. 4 * 5 * Authors: 6 * Janito V. Ferreira Filho 7 */ 8 9 10 #include "HTreeEntryIterator.h" 11 12 #include <new> 13 14 #include "HTree.h" 15 #include "IndexedDirectoryIterator.h" 16 #include "Inode.h" 17 18 19 //#define TRACE_EXT2 20 #ifdef TRACE_EXT2 21 # define TRACE(x...) dprintf("\33[34mext2:\33[0m " x) 22 #else 23 # define TRACE(x...) ; 24 #endif 25 #define ERROR(x...) dprintf("\33[34mext2:\33[0m " x) 26 27 28 HTreeEntryIterator::HTreeEntryIterator(off_t offset, Inode* directory) 29 : 30 fHasCollision(false), 31 fDirectory(directory), 32 fOffset(offset), 33 fParent(NULL), 34 fChild(NULL) 35 { 36 fBlockSize = fDirectory->GetVolume()->BlockSize(); 37 } 38 39 40 HTreeEntryIterator::HTreeEntryIterator(uint32 block, uint32 blockSize, 41 Inode* directory, HTreeEntryIterator* parent, bool hasCollision) 42 : 43 fHasCollision(hasCollision), 44 fBlockSize(blockSize), 45 fDirectory(directory), 46 fOffset(block * blockSize + sizeof(HTreeFakeDirEntry)), 47 fParent(parent), 48 fChild(NULL) 49 { 50 TRACE("HTreeEntryIterator::HTreeEntryIterator() block %ld offset %Lx\n", 51 block, fOffset); 52 } 53 54 55 status_t 56 HTreeEntryIterator::Init() 57 { 58 size_t length = sizeof(HTreeCountLimit); 59 HTreeCountLimit countLimit; 60 61 status_t status = fDirectory->ReadAt(fOffset, (uint8*)&countLimit, 62 &length); 63 64 if (status != B_OK) 65 return status; 66 67 if (length != sizeof(HTreeCountLimit)) { 68 ERROR("HTreeEntryIterator::Init() bad length %ld fOffset 0x%Lx\n", 69 length, fOffset); 70 fCount = fLimit = 0; 71 return B_ERROR; 72 } 73 74 fCount = countLimit.Count(); 75 fLimit = countLimit.Limit(); 76 77 if (fCount >= fLimit) { 78 ERROR("HTreeEntryIterator::Init() bad fCount %d fOffset 0x%Lx\n", 79 fCount, fOffset); 80 fCount = fLimit = 0; 81 return B_ERROR; 82 } 83 84 if (fParent != NULL && 85 fLimit != ((fBlockSize - sizeof(HTreeFakeDirEntry)) 86 / sizeof(HTreeEntry)) ) { 87 ERROR("HTreeEntryIterator::Init() bad fLimit %d should be %ld " 88 "fOffset 0x%Lx\n", fLimit, (fBlockSize - sizeof(HTreeFakeDirEntry)) 89 / sizeof(HTreeEntry), fOffset); 90 fCount = fLimit = 0; 91 return B_ERROR; 92 } 93 94 TRACE("HTreeEntryIterator::Init() count 0x%x limit 0x%x\n", fCount, 95 fLimit); 96 97 fMaxOffset = fOffset + (fCount - 1) * sizeof(HTreeEntry); 98 99 return B_OK; 100 } 101 102 103 HTreeEntryIterator::~HTreeEntryIterator() 104 { 105 } 106 107 108 status_t 109 HTreeEntryIterator::Lookup(uint32 hash, int indirections, 110 DirectoryIterator** directoryIterator) 111 { 112 off_t start = fOffset + sizeof(HTreeEntry); 113 off_t end = fMaxOffset; 114 off_t middle = start; 115 size_t entrySize = sizeof(HTreeEntry); 116 HTreeEntry entry; 117 118 while (start <= end) { 119 middle = (end - start) / 2; 120 middle -= middle % entrySize; // Alignment 121 middle += start; 122 123 TRACE("HTreeEntryIterator::Lookup() %d 0x%Lx 0x%Lx 0x%Lx\n", 124 indirections, start, end, middle); 125 126 status_t status = fDirectory->ReadAt(middle, (uint8*)&entry, 127 &entrySize); 128 129 TRACE("HTreeEntryIterator::Lookup() %lx %lx\n", hash, entry.Hash()); 130 131 if (status != B_OK) 132 return status; 133 else if (entrySize != sizeof(entry)) { 134 // Fallback to linear search 135 *directoryIterator = new(std::nothrow) 136 DirectoryIterator(fDirectory); 137 138 if (*directoryIterator == NULL) 139 return B_NO_MEMORY; 140 141 return B_OK; 142 } 143 144 if (hash >= entry.Hash()) 145 start = middle + entrySize; 146 else 147 end = middle - entrySize; 148 } 149 150 status_t status = fDirectory->ReadAt(start - entrySize, (uint8*)&entry, 151 &entrySize); 152 if (status != B_OK) 153 return status; 154 155 if (indirections == 0) { 156 *directoryIterator = new(std::nothrow) 157 IndexedDirectoryIterator(entry.Block() * fBlockSize, fBlockSize, 158 fDirectory, this); 159 160 if (*directoryIterator == NULL) 161 return B_NO_MEMORY; 162 163 return B_OK; 164 } 165 166 delete fChild; 167 168 fChild = new(std::nothrow) HTreeEntryIterator(entry.Block(), fBlockSize, 169 fDirectory, this, entry.Hash() & 1 == 1); 170 171 if (fChild == NULL) 172 return B_NO_MEMORY; 173 fChildDeleter.SetTo(fChild); 174 175 status = fChild->Init(); 176 if (status != B_OK) 177 return status; 178 179 return fChild->Lookup(hash, indirections - 1, directoryIterator); 180 } 181 182 183 status_t 184 HTreeEntryIterator::GetNext(off_t& childOffset) 185 { 186 size_t entrySize = sizeof(HTreeEntry); 187 fOffset += entrySize; 188 bool firstEntry = fOffset >= fMaxOffset; 189 190 if (firstEntry) { 191 if (fParent == NULL) 192 return B_ENTRY_NOT_FOUND; 193 194 status_t status = fParent->GetNext(fOffset); 195 if (status != B_OK) 196 return status; 197 198 status = Init(); 199 if (status != B_OK) 200 return status; 201 202 fHasCollision = fParent->HasCollision(); 203 } 204 205 HTreeEntry entry; 206 status_t status = fDirectory->ReadAt(fOffset, (uint8*)&entry, &entrySize); 207 if (status != B_OK) 208 return status; 209 else if (entrySize != sizeof(entry)) { 210 // Weird error, try to skip it 211 return GetNext(childOffset); 212 } 213 214 if (!firstEntry) 215 fHasCollision = (entry.Hash() & 1) == 1; 216 217 childOffset = entry.Block() * fBlockSize; 218 219 return B_OK; 220 } 221