1 // Iterators.h 2 // 3 // Copyright (c) 2003, Ingo Weinhold (bonefish@cs.tu-berlin.de) 4 // 5 // This program is free software; you can redistribute it and/or modify 6 // it under the terms of the GNU General Public License as published by 7 // the Free Software Foundation; either version 2 of the License, or 8 // (at your option) any later version. 9 // 10 // This program is distributed in the hope that it will be useful, 11 // but WITHOUT ANY WARRANTY; without even the implied warranty of 12 // MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the 13 // GNU General Public License for more details. 14 // 15 // You should have received a copy of the GNU General Public License 16 // along with this program; if not, write to the Free Software 17 // Foundation, Inc., 59 Temple Place, Suite 330, Boston, MA 02111-1307 USA 18 // 19 // You can alternatively use *this file* under the terms of the the MIT 20 // license included in this package. 21 22 #ifndef ITERATORS_H 23 #define ITERATORS_H 24 25 #include <SupportDefs.h> 26 27 #include "DirItem.h" 28 29 class Block; 30 class InternalNode; 31 class VKey; 32 class LeafNode; 33 class Node; 34 class Tree; 35 36 // TreePath 37 class TreePath { 38 public: 39 class Element; 40 41 public: 42 TreePath(uint32 maxLength); 43 ~TreePath(); 44 45 status_t InitCheck() const; 46 47 uint32 GetMaxLength() const; 48 uint32 GetLength() const; 49 const Element *ElementAt(int32 index) const; 50 const Element *GetTopElement() const; 51 52 status_t PushElement(uint64 blockNumber, int32 index); 53 status_t PopElement(); 54 55 private: 56 uint32 fMaxLength; 57 uint32 fLength; 58 Element *fElements; 59 }; 60 61 // TreePath::Element 62 class TreePath::Element { 63 public: 64 Element() {} 65 ~Element() {} 66 67 status_t SetTo(uint64 blockNumber, int32 index); 68 69 uint64 GetBlockNumber() const; 70 int32 GetIndex() const; 71 72 private: 73 uint64 fBlockNumber; 74 uint32 fIndex; 75 }; 76 77 78 // TreeIterator 79 class TreeIterator { 80 public: 81 TreeIterator(Tree *tree); 82 ~TreeIterator(); 83 84 status_t SetTo(Tree *tree); 85 void Unset(); 86 status_t InitCheck() const; 87 88 Tree *GetTree() const { return fTree; } 89 90 Node *GetNode() const; 91 int32 GetLevel() const; 92 93 status_t GoTo(uint32 direction); 94 95 status_t GoToPreviousLeaf(LeafNode **node = NULL); 96 status_t GoToNextLeaf(LeafNode **node = NULL); 97 status_t FindRightMostLeaf(const VKey *k, LeafNode **node = NULL); 98 99 status_t Suspend(); 100 status_t Resume(); 101 102 public: 103 enum { 104 FORWARD, 105 BACKWARDS, 106 UP, 107 DOWN, 108 }; 109 110 private: 111 status_t _PushCurrentNode(Node *newTopNode = NULL, int32 newIndex = 0); 112 status_t _PopTopNode(); 113 status_t _SearchRightMost(InternalNode *node, const VKey *k, int32 *index); 114 115 private: 116 Tree *fTree; 117 Node *fCurrentNode; 118 int32 fIndex; 119 TreePath *fPath; 120 }; 121 122 // ItemIterator 123 class ItemIterator { 124 public: 125 ItemIterator(Tree *tree); 126 127 status_t SetTo(Tree *tree); 128 status_t InitCheck() const; 129 130 Tree *GetTree() const { return fTreeIterator.GetTree(); } 131 132 status_t GetCurrent(Item *item); 133 status_t GoToPrevious(Item *item = NULL); 134 status_t GoToNext(Item *item = NULL); 135 status_t FindRightMostClose(const VKey *k, Item *item = NULL); 136 status_t FindRightMost(const VKey *k, Item *item = NULL); 137 138 status_t Suspend(); 139 status_t Resume(); 140 141 private: 142 status_t _GetLeafNode(LeafNode **node) const; 143 status_t _SearchRightMost(LeafNode *node, const VKey *k, 144 int32 *index) const; 145 146 private: 147 TreeIterator fTreeIterator; 148 int32 fIndex; 149 }; 150 151 // ObjectItemIterator 152 class ObjectItemIterator { 153 public: 154 ObjectItemIterator(Tree *tree, uint32 dirID, uint32 objectID, 155 uint64 startOffset = 0); 156 157 status_t SetTo(Tree *tree, uint32 dirID, uint32 objectID, 158 uint64 startOffset = 0); 159 status_t InitCheck() const; 160 161 Tree *GetTree() const { return fItemIterator.GetTree(); } 162 uint32 GetDirID() const { return fDirID; } 163 uint32 GetObjectID() const { return fObjectID; } 164 uint64 GetOffset() const { return fOffset; } 165 166 status_t GetNext(Item *foundItem); 167 status_t GetNext(Item *foundItem, uint32 type); 168 status_t GetPrevious(Item *foundItem); 169 status_t GetPrevious(Item *foundItem, uint32 type); 170 171 status_t Suspend(); 172 status_t Resume(); 173 174 private: 175 ItemIterator fItemIterator; 176 uint32 fDirID; 177 uint32 fObjectID; 178 uint64 fOffset; 179 bool fFindFirst; 180 bool fDone; 181 }; 182 183 // DirEntryIterator 184 class DirEntryIterator { 185 public: 186 DirEntryIterator(Tree *tree, uint32 dirID, uint32 objectID, 187 uint64 startOffset = 0, bool fixedHash = false); 188 189 status_t SetTo(Tree *tree, uint32 dirID, uint32 objectID, 190 uint64 startOffset = 0, bool fixedHash = false); 191 status_t InitCheck() const; 192 193 status_t Rewind(); 194 195 Tree *GetTree() const { return fItemIterator.GetTree(); } 196 uint32 GetDirID() const { return fItemIterator.GetDirID(); } 197 uint32 GetObjectID() const { return fItemIterator.GetObjectID(); } 198 uint64 GetOffset() const { return fItemIterator.GetOffset(); } 199 200 status_t GetNext(DirItem *foundItem, int32 *entryIndex, 201 DirEntry **entry = NULL); 202 status_t GetPrevious(DirItem *foundItem, int32 *entryIndex, 203 DirEntry **entry = NULL); 204 205 status_t Suspend(); 206 status_t Resume(); 207 208 private: 209 ObjectItemIterator fItemIterator; 210 DirItem fDirItem; 211 int32 fIndex; 212 bool fFixedHash; 213 bool fDone; 214 }; 215 216 // StreamReader 217 class StreamReader { 218 public: 219 StreamReader(Tree *tree, uint32 dirID, uint32 objectID); 220 221 status_t SetTo(Tree *tree, uint32 dirID, uint32 objectID); 222 status_t InitCheck() const; 223 224 Tree *GetTree() const { return fItemIterator.GetTree(); } 225 uint32 GetDirID() const { return fItemIterator.GetDirID(); } 226 uint32 GetObjectID() const { return fItemIterator.GetObjectID(); } 227 uint64 GetOffset() const { return fItemIterator.GetOffset(); } 228 229 off_t StreamSize() const { return fStreamSize; } 230 231 status_t ReadAt(off_t position, void *buffer, size_t bufferSize, 232 size_t *bytesRead); 233 234 status_t Suspend(); 235 status_t Resume(); 236 237 private: 238 status_t _GetStreamSize(); 239 status_t _SeekTo(off_t position); 240 status_t _ReadIndirectItem(off_t offset, void *buffer, size_t bufferSize); 241 status_t _ReadDirectItem(off_t offset, void *buffer, size_t bufferSize); 242 243 private: 244 ObjectItemIterator fItemIterator; 245 Item fItem; 246 off_t fStreamSize; 247 off_t fItemOffset; 248 off_t fItemSize; 249 uint32 fBlockSize; 250 }; 251 252 #endif // ITERATORS_H 253