1/* 2 * Copyright 2011, Ingo Weinhold, ingo_weinhold@gmx.de. 3 * Distributed under the terms of the MIT License. 4 */ 5#ifndef INDEX_IMPL_H 6#define INDEX_IMPL_H 7 8 9#include "Index.h" 10#include "Node.h" 11#include "NodeListener.h" 12 13 14class AbstractIndexIterator { 15public: 16 AbstractIndexIterator(); 17 virtual ~AbstractIndexIterator(); 18 19 virtual bool HasNext() const = 0; 20 virtual Node* Next(void* buffer, size_t* _keyLength) = 0; 21 22 virtual status_t Suspend(); 23 virtual status_t Resume(); 24}; 25 26 27template<typename Policy> 28class GenericIndexIterator : public AbstractIndexIterator, 29 public NodeListener { 30public: 31 typedef typename Policy::Index Index; 32 typedef typename Policy::Value Value; 33 typedef typename Policy::NodeTree NodeTree; 34 typedef typename Policy::TreePolicy TreePolicy; 35 typedef typename NodeTree::Node TreeNode; 36 37public: 38 GenericIndexIterator(); 39 virtual ~GenericIndexIterator(); 40 41 virtual bool HasNext() const; 42 virtual Node* Next(void* buffer, size_t* _keyLength); 43 44 virtual status_t Suspend(); 45 virtual status_t Resume(); 46 47 bool SetTo(Index* index, const Value& name, 48 bool ignoreValue = false); 49 50 inline void NodeChangeBegin(Node* node); 51 inline void NodeChangeEnd(Node* node); 52 53 virtual void NodeRemoved(Node* node); 54 55protected: 56 Index* fIndex; 57 TreeNode* fNextTreeNode; 58 bool fSuspended; 59}; 60 61 62template<typename Policy> 63GenericIndexIterator<Policy>::GenericIndexIterator() 64 : 65 AbstractIndexIterator(), 66 fIndex(NULL), 67 fNextTreeNode(NULL), 68 fSuspended(false) 69{ 70} 71 72 73template<typename Policy> 74GenericIndexIterator<Policy>::~GenericIndexIterator() 75{ 76 SetTo(NULL, Value()); 77} 78 79 80template<typename Policy> 81bool 82GenericIndexIterator<Policy>::HasNext() const 83{ 84 return fNextTreeNode != NULL; 85} 86 87 88template<typename Policy> 89Node* 90GenericIndexIterator<Policy>::Next(void* buffer, size_t* _keyLength) 91{ 92 if (fSuspended || fNextTreeNode == NULL) 93 return NULL; 94 95 96 if (buffer != NULL) 97 TreePolicy::GetTreeNodeValue(fNextTreeNode, buffer, _keyLength); 98 99 TreeNode* treeNode = fNextTreeNode; 100 fNextTreeNode = Policy::GetNodeTree(fIndex)->Next(fNextTreeNode); 101 102 return TreePolicy::GetNode(treeNode); 103} 104 105 106template<typename Policy> 107status_t 108GenericIndexIterator<Policy>::Suspend() 109{ 110 if (fSuspended) 111 return B_BAD_VALUE; 112 113 if (fNextTreeNode != NULL) { 114 fIndex->GetVolume()->AddNodeListener(this, 115 TreePolicy::GetNode(fNextTreeNode)); 116 } 117 118 fSuspended = true; 119 return B_OK; 120} 121 122 123template<typename Policy> 124status_t 125GenericIndexIterator<Policy>::Resume() 126{ 127 if (!fSuspended) 128 return B_BAD_VALUE; 129 130 if (fNextTreeNode != NULL) 131 fIndex->GetVolume()->RemoveNodeListener(this); 132 133 fSuspended = false; 134 return B_OK; 135} 136 137 138template<typename Policy> 139bool 140GenericIndexIterator<Policy>::SetTo(Index* index, const Value& value, 141 bool ignoreValue) 142{ 143 Resume(); 144 145 fIndex = index; 146 fSuspended = false; 147 fNextTreeNode = NULL; 148 149 if (fIndex == NULL) 150 return false; 151 152 if (ignoreValue) 153 fNextTreeNode = TreePolicy::GetFirstTreeNode(fIndex); 154 else 155 fNextTreeNode = TreePolicy::FindClosestTreeNode(fIndex, value); 156 157 return fNextTreeNode != NULL; 158} 159 160 161/*! Moves the iterator temporarily off the current node. 162 Called when the node the iterator currently points to has been modified and 163 the index is about to remove it from and reinsert it into the tree. After 164 having done that NodeChangeEnd() must be called. 165*/ 166template<typename Policy> 167void 168GenericIndexIterator<Policy>::NodeChangeBegin(Node* node) 169{ 170 fNextTreeNode = Policy::GetNodeTree(fIndex)->Previous(fNextTreeNode); 171} 172 173 174/*! Brackets a NodeChangeBegin() call. 175*/ 176template<typename Policy> 177void 178GenericIndexIterator<Policy>::NodeChangeEnd(Node* node) 179{ 180 if (fNextTreeNode != NULL) 181 fNextTreeNode = Policy::GetNodeTree(fIndex)->Next(fNextTreeNode); 182 else 183 fNextTreeNode = TreePolicy::GetFirstTreeNode(fIndex); 184 185 // If the node is no longer the one we originally pointed to, re-register 186 // the node listener. 187 if (fNextTreeNode == NULL) { 188 fIndex->GetVolume()->RemoveNodeListener(this); 189 } else { 190 Node* newNode = TreePolicy::GetNode(fNextTreeNode); 191 if (newNode != node) { 192 fIndex->GetVolume()->RemoveNodeListener(this); 193 fIndex->GetVolume()->AddNodeListener(this, newNode); 194 } 195 } 196} 197 198 199template<typename Policy> 200void 201GenericIndexIterator<Policy>::NodeRemoved(Node* node) 202{ 203 Resume(); 204 Next(NULL, NULL); 205 Suspend(); 206} 207 208 209template<typename Policy> 210struct GenericIndexIteratorTreePolicy { 211 typedef typename Policy::Index Index; 212 typedef typename Policy::Value Value; 213 typedef typename Policy::NodeTree NodeTree; 214 typedef typename NodeTree::Node TreeNode; 215 216 static Node* GetNode(TreeNode* treeNode) 217 { 218 typename Policy::NodeTree::NodeStrategy strategy; 219 return strategy.GetValue(treeNode); 220 } 221 222 static TreeNode* GetFirstTreeNode(Index* index) 223 { 224 typename NodeTree::Iterator iterator; 225 Policy::GetNodeTree(index)->GetIterator(&iterator); 226 return iterator.CurrentNode(); 227 } 228 229 static TreeNode* FindClosestTreeNode(Index* index, const Value& value) 230 { 231 typename NodeTree::Iterator iterator; 232 if (Policy::GetNodeTree(index)->FindFirstClosest(value, false, 233 &iterator) == NULL) { 234 return NULL; 235 } 236 237 return iterator.CurrentNode(); 238 } 239 240 static void GetTreeNodeValue(TreeNode* treeNode, void* buffer, 241 size_t* _keyLength) 242 { 243 Policy::GetNodeValue(GetNode(treeNode), buffer, _keyLength); 244 } 245}; 246 247 248#endif // INDEX_IMPL_H 249