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