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 29class Block; 30class InternalNode; 31class VKey; 32class LeafNode; 33class Node; 34class Tree; 35 36// TreePath 37class TreePath { 38public: 39 class Element; 40 41public: 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 55private: 56 uint32 fMaxLength; 57 uint32 fLength; 58 Element *fElements; 59}; 60 61// TreePath::Element 62class TreePath::Element { 63public: 64 Element() {} 65 ~Element() {} 66 67 status_t SetTo(uint64 blockNumber, int32 index); 68 69 uint64 GetBlockNumber() const; 70 int32 GetIndex() const; 71 72private: 73 uint64 fBlockNumber; 74 uint32 fIndex; 75}; 76 77 78// TreeIterator 79class TreeIterator { 80public: 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 102public: 103 enum { 104 FORWARD, 105 BACKWARDS, 106 UP, 107 DOWN, 108 }; 109 110private: 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 115private: 116 Tree *fTree; 117 Node *fCurrentNode; 118 int32 fIndex; 119 TreePath *fPath; 120}; 121 122// ItemIterator 123class ItemIterator { 124public: 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 141private: 142 status_t _GetLeafNode(LeafNode **node) const; 143 status_t _SearchRightMost(LeafNode *node, const VKey *k, 144 int32 *index) const; 145 146private: 147 TreeIterator fTreeIterator; 148 int32 fIndex; 149}; 150 151// ObjectItemIterator 152class ObjectItemIterator { 153public: 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 174private: 175 ItemIterator fItemIterator; 176 uint32 fDirID; 177 uint32 fObjectID; 178 uint64 fOffset; 179 bool fFindFirst; 180 bool fDone; 181}; 182 183// DirEntryIterator 184class DirEntryIterator { 185public: 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 208private: 209 ObjectItemIterator fItemIterator; 210 DirItem fDirItem; 211 int32 fIndex; 212 bool fFixedHash; 213 bool fDone; 214}; 215 216// StreamReader 217class StreamReader { 218public: 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 237private: 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 243private: 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