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