1/* 2 * Copyright 2011, Ingo Weinhold, ingo_weinhold@gmx.de. 3 * Distributed under the terms of the MIT License. 4 */ 5 6 7#include "LastModifiedIndex.h" 8 9#include <new> 10 11#include <TypeConstants.h> 12 13#include <util/SinglyLinkedList.h> 14 15#include "DebugSupport.h" 16#include "IndexImpl.h" 17#include "Node.h" 18#include "TwoKeyAVLTree.h" 19#include "Volume.h" 20 21 22// #pragma mark - LastModifiedIndexPrimaryKey 23 24 25class LastModifiedIndexPrimaryKey { 26public: 27 LastModifiedIndexPrimaryKey(Node* node, time_t modified) 28 : 29 node(node), 30 modified(modified) 31 { 32 } 33 34 LastModifiedIndexPrimaryKey(Node* node) 35 : 36 node(node), 37 modified(node->ModifiedTime().tv_sec) 38 { 39 } 40 41 LastModifiedIndexPrimaryKey(time_t modified) 42 : 43 node(NULL), 44 modified(modified) 45 { 46 } 47 48 Node* node; 49 time_t modified; 50}; 51 52 53// #pragma mark - LastModifiedIndexGetPrimaryKey 54 55 56class LastModifiedIndexGetPrimaryKey { 57public: 58 inline LastModifiedIndexPrimaryKey operator()(Node* a) 59 { 60 return LastModifiedIndexPrimaryKey(a); 61 } 62 63 inline LastModifiedIndexPrimaryKey operator()(Node* a) const 64 { 65 return LastModifiedIndexPrimaryKey(a); 66 } 67}; 68 69 70// #pragma mark - LastModifiedIndexPrimaryKeyCompare 71 72 73class LastModifiedIndexPrimaryKeyCompare { 74public: 75 inline int operator()(const LastModifiedIndexPrimaryKey &a, 76 const LastModifiedIndexPrimaryKey &b) const 77 { 78 if (a.node != NULL && a.node == b.node) 79 return 0; 80 if (a.modified < b.modified) 81 return -1; 82 if (a.modified > b.modified) 83 return 1; 84 return 0; 85 } 86}; 87 88 89// #pragma mark - NodeTree 90 91 92typedef TwoKeyAVLTree<Node*, LastModifiedIndexPrimaryKey, 93 LastModifiedIndexPrimaryKeyCompare, LastModifiedIndexGetPrimaryKey> 94 _NodeTree; 95class LastModifiedIndex::NodeTree : public _NodeTree {}; 96 97 98// #pragma mark - IteratorList 99 100 101class LastModifiedIndex::IteratorList : public SinglyLinkedList<Iterator> {}; 102 103 104// #pragma mark - Iterator 105 106 107struct LastModifiedIndex::IteratorPolicy { 108 typedef LastModifiedIndex Index; 109 typedef time_t Value; 110 typedef LastModifiedIndex::NodeTree NodeTree; 111 typedef GenericIndexIteratorTreePolicy<IteratorPolicy> TreePolicy; 112 113 static NodeTree* GetNodeTree(Index* index) 114 { 115 return index->fNodes; 116 } 117 118 static void GetNodeValue(Node* node, void* buffer, size_t* _keyLength) 119 { 120 *(time_t*)buffer = node->ModifiedTime().tv_sec; 121 *_keyLength = sizeof(time_t); 122 } 123}; 124 125 126class LastModifiedIndex::Iterator : public GenericIndexIterator<IteratorPolicy>, 127 public SinglyLinkedListLinkImpl<Iterator> { 128public: 129 virtual void NodeChanged(Node* node, uint32 statFields, 130 const OldNodeAttributes& oldAttributes); 131}; 132 133 134// #pragma mark - LastModifiedIndex 135 136 137LastModifiedIndex::LastModifiedIndex() 138 : 139 Index(), 140 fNodes(NULL), 141 fIteratorsToUpdate(NULL) 142{ 143} 144 145 146LastModifiedIndex::~LastModifiedIndex() 147{ 148 if (IsListening()) 149 fVolume->RemoveNodeListener(this); 150 151 ASSERT(fIteratorsToUpdate->IsEmpty()); 152 153 delete fIteratorsToUpdate; 154 delete fNodes; 155} 156 157 158status_t 159LastModifiedIndex::Init(Volume* volume) 160{ 161 status_t error = Index::Init(volume, "last_modified", B_INT32_TYPE, true, 162 sizeof(time_t)); 163 if (error != B_OK) 164 return error; 165 166 fVolume->AddNodeListener(this, NULL); 167 168 fNodes = new(std::nothrow) NodeTree; 169 fIteratorsToUpdate = new(std::nothrow) IteratorList; 170 if (fNodes == NULL || fIteratorsToUpdate == NULL) 171 return B_NO_MEMORY; 172 173 return B_OK; 174} 175 176 177int32 178LastModifiedIndex::CountEntries() const 179{ 180 return fNodes->CountItems(); 181} 182 183 184void 185LastModifiedIndex::NodeAdded(Node* node) 186{ 187 fNodes->Insert(node); 188} 189 190 191void 192LastModifiedIndex::NodeRemoved(Node* node) 193{ 194 fNodes->Remove(node, node); 195} 196 197 198void 199LastModifiedIndex::NodeChanged(Node* node, uint32 statFields, 200 const OldNodeAttributes& oldAttributes) 201{ 202 IteratorList iterators; 203 iterators.MoveFrom(fIteratorsToUpdate); 204 205 time_t oldLastModified = oldAttributes.ModifiedTime().tv_sec; 206 time_t newLastModified = node->ModifiedTime().tv_sec; 207 if (newLastModified == oldLastModified) 208 return; 209 210 NodeTree::Iterator nodeIterator; 211 Node** foundNode = fNodes->Find( 212 LastModifiedIndexPrimaryKey(node, oldLastModified), node, 213 &nodeIterator); 214 215 if (foundNode == NULL || *foundNode != node) 216 return; 217 218 // move the iterators that point to the node to the previous node 219 for (IteratorList::Iterator it = iterators.GetIterator(); 220 Iterator* iterator = it.Next();) { 221 iterator->NodeChangeBegin(node); 222 } 223 224 // remove and re-insert the node 225 nodeIterator.Remove(); 226 if (fNodes->Insert(node) != B_OK) { 227 fIteratorsToUpdate->MakeEmpty(); 228 return; 229 } 230 231 // Move the iterators to the next node again. If the node hasn't changed 232 // its place, they will point to it again, otherwise to the node originally 233 // succeeding it. 234 for (IteratorList::Iterator it = iterators.GetIterator(); 235 Iterator* iterator = it.Next();) { 236 iterator->NodeChangeEnd(node); 237 } 238 239 // update live queries 240 fVolume->UpdateLiveQueries(node, Name(), Type(), 241 (const uint8*)&oldLastModified, sizeof(oldLastModified), 242 (const uint8*)&newLastModified, sizeof(newLastModified)); 243} 244 245 246AbstractIndexIterator* 247LastModifiedIndex::InternalGetIterator() 248{ 249 Iterator* iterator = new(std::nothrow) Iterator; 250 if (iterator != NULL) { 251 if (!iterator->SetTo(this, 0, true)) { 252 delete iterator; 253 iterator = NULL; 254 } 255 } 256 return iterator; 257} 258 259 260AbstractIndexIterator* 261LastModifiedIndex::InternalFind(const void* key, size_t length) 262{ 263 if (length != sizeof(time_t)) 264 return NULL; 265 Iterator* iterator = new(std::nothrow) Iterator; 266 if (iterator != NULL) { 267 if (!iterator->SetTo(this, *(const time_t*)key)) { 268 delete iterator; 269 iterator = NULL; 270 } 271 } 272 return iterator; 273} 274 275 276void 277LastModifiedIndex::_AddIteratorToUpdate(Iterator* iterator) 278{ 279 fIteratorsToUpdate->Add(iterator); 280} 281 282 283// #pragma mark - Iterator 284 285 286void 287LastModifiedIndex::Iterator::NodeChanged(Node* node, uint32 statFields, 288 const OldNodeAttributes& oldAttributes) 289{ 290 fIndex->_AddIteratorToUpdate(this); 291} 292