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 14 class AbstractIndexIterator { 15 public: 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 27 template<typename Policy> 28 class GenericIndexIterator : public AbstractIndexIterator, 29 public NodeListener { 30 public: 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 37 public: 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 55 protected: 56 Index* fIndex; 57 TreeNode* fNextTreeNode; 58 bool fSuspended; 59 }; 60 61 62 template<typename Policy> 63 GenericIndexIterator<Policy>::GenericIndexIterator() 64 : 65 AbstractIndexIterator(), 66 fIndex(NULL), 67 fNextTreeNode(NULL), 68 fSuspended(false) 69 { 70 } 71 72 73 template<typename Policy> 74 GenericIndexIterator<Policy>::~GenericIndexIterator() 75 { 76 SetTo(NULL, Value()); 77 } 78 79 80 template<typename Policy> 81 bool 82 GenericIndexIterator<Policy>::HasNext() const 83 { 84 return fNextTreeNode != NULL; 85 } 86 87 88 template<typename Policy> 89 Node* 90 GenericIndexIterator<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 106 template<typename Policy> 107 status_t 108 GenericIndexIterator<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 123 template<typename Policy> 124 status_t 125 GenericIndexIterator<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 138 template<typename Policy> 139 bool 140 GenericIndexIterator<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 */ 166 template<typename Policy> 167 void 168 GenericIndexIterator<Policy>::NodeChangeBegin(Node* node) 169 { 170 fNextTreeNode = Policy::GetNodeTree(fIndex)->Previous(fNextTreeNode); 171 } 172 173 174 /*! Brackets a NodeChangeBegin() call. 175 */ 176 template<typename Policy> 177 void 178 GenericIndexIterator<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 199 template<typename Policy> 200 void 201 GenericIndexIterator<Policy>::NodeRemoved(Node* node) 202 { 203 Resume(); 204 Next(NULL, NULL); 205 Suspend(); 206 } 207 208 209 template<typename Policy> 210 struct 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