1/* 2 * Copyright 2011, Ingo Weinhold, ingo_weinhold@gmx.de. 3 * Distributed under the terms of the MIT License. 4 */ 5 6 7#include "AttributeIndex.h" 8 9#include <new> 10 11#include <TypeConstants.h> 12 13#include <util/AVLTree.h> 14#include <util/SinglyLinkedList.h> 15 16#include <file_systems/QueryParserUtils.h> 17 18#include "AttributeIndexer.h" 19#include "DebugSupport.h" 20#include "IndexImpl.h" 21#include "Node.h" 22#include "Volume.h" 23 24 25struct AttributeIndexTreeKey { 26 const void* data; 27 size_t length; 28 29 AttributeIndexTreeKey() 30 { 31 } 32 33 AttributeIndexTreeKey(const void* data, size_t length) 34 : 35 data(data), 36 length(length) 37 { 38 } 39}; 40 41 42struct AttributeIndexTreeValue : AVLTreeNode { 43 Node* node; 44 IndexedAttributeOwner* owner; 45 void* attributeCookie; 46 size_t length; 47 uint8 data[0]; 48 49 static AttributeIndexTreeValue* Create(IndexedAttributeOwner* owner, 50 void* attributeCookie, size_t length) 51 { 52 AttributeIndexTreeValue* self = (AttributeIndexTreeValue*)malloc( 53 sizeof(AttributeIndexTreeValue) + length); 54 if (self == NULL) 55 return NULL; 56 57 self->owner = owner; 58 self->attributeCookie = attributeCookie; 59 self->length = length; 60 return self; 61 } 62 63 void Delete() 64 { 65 free(this); 66 } 67}; 68 69 70struct AttributeIndex::TreeDefinition { 71 typedef TreeKey Key; 72 typedef TreeValue Value; 73 74 TreeDefinition(uint32 type) 75 : 76 fType(type) 77 { 78 } 79 80 AVLTreeNode* GetAVLTreeNode(Value* value) const 81 { 82 return value; 83 } 84 85 Value* GetValue(AVLTreeNode* node) const 86 { 87 return static_cast<Value*>(node); 88 } 89 90 int Compare(const Key& a, const Value* b) const 91 { 92 return QueryParser::compareKeys(fType, a.data, a.length, b->data, 93 b->length); 94 } 95 96 int Compare(const Value* a, const Value* b) const 97 { 98 return QueryParser::compareKeys(fType, a->data, a->length, b->data, 99 b->length); 100 } 101 102private: 103 uint32 fType; 104}; 105 106 107// #pragma mark - NodeTree 108 109 110struct AttributeIndex::NodeTree : public AVLTree<TreeDefinition> { 111 typedef TreeValue Node; 112 113 NodeTree(const TreeDefinition& definition) 114 : 115 AVLTree<TreeDefinition>(definition) 116 { 117 } 118}; 119 120 121// #pragma mark - IteratorList 122 123 124class AttributeIndex::IteratorList : public SinglyLinkedList<Iterator> {}; 125 126 127// #pragma mark - Iterator 128 129 130struct AttributeIndex::IteratorPolicy { 131 typedef AttributeIndex Index; 132 typedef TreeKey Value; 133 typedef AttributeIndex::NodeTree NodeTree; 134 typedef TreeValue TreeNode; 135 typedef IteratorPolicy TreePolicy; 136 137 static NodeTree* GetNodeTree(Index* index) 138 { 139 return index->fNodes; 140 } 141 142 static void GetTreeNodeValue(TreeNode* node, void* buffer, 143 size_t* _keyLength) 144 { 145 if (node->length > 0) 146 memcpy(buffer, node->data, node->length); 147 *_keyLength = node->length; 148 } 149 150 static Node* GetNode(TreeNode* treeNode) 151 { 152 return treeNode->node; 153 } 154 155 static TreeNode* GetFirstTreeNode(Index* index) 156 { 157 return index->fNodes->GetIterator().Next(); 158 } 159 160 static TreeNode* FindClosestTreeNode(Index* index, const Value& value) 161 { 162 return index->fNodes->FindClosest(value, false); 163 } 164}; 165 166 167class AttributeIndex::Iterator : public GenericIndexIterator<IteratorPolicy>, 168 public SinglyLinkedListLinkImpl<Iterator> { 169public: 170 virtual void NodeChanged(Node* node, uint32 statFields, 171 const OldNodeAttributes& oldAttributes); 172}; 173 174 175// #pragma mark - AttributeIndexer 176 177 178AttributeIndexer::AttributeIndexer(AttributeIndex* index) 179 : 180 fIndex(index), 181 fIndexName(index->Name()), 182 fIndexType(index->Type()), 183 fCookie(NULL) 184{ 185} 186 187 188AttributeIndexer::~AttributeIndexer() 189{ 190} 191 192 193status_t 194AttributeIndexer::CreateCookie(IndexedAttributeOwner* owner, 195 void* attributeCookie, uint32 attributeType, size_t attributeSize, 196 void*& _data, size_t& _toRead) 197{ 198 // check the attribute type and size 199 if (attributeType != fIndexType) 200 return B_ERROR; 201 202 if (fIndex->HasFixedKeyLength()) { 203 if (attributeSize != fIndex->KeyLength()) 204 return B_ERROR; 205 } else if (attributeSize > kMaxIndexKeyLength) 206 attributeSize = kMaxIndexKeyLength; 207 208 // create the tree value 209 fCookie = AttributeIndexTreeValue::Create(owner, attributeCookie, 210 attributeSize); 211 if (fCookie == NULL) 212 return B_NO_MEMORY; 213 214 _data = fCookie->data; 215 _toRead = attributeSize; 216 217 return B_OK; 218} 219 220 221void 222AttributeIndexer::DeleteCookie() 223{ 224 fCookie->Delete(); 225 fCookie = NULL; 226} 227 228 229// #pragma mark - AttributeIndex 230 231 232AttributeIndex::AttributeIndex() 233 : 234 Index(), 235 fNodes(NULL), 236 fIteratorsToUpdate(NULL), 237 fIndexer(NULL) 238{ 239} 240 241 242AttributeIndex::~AttributeIndex() 243{ 244 if (IsListening()) 245 fVolume->RemoveNodeListener(this); 246 247 ASSERT(fIteratorsToUpdate->IsEmpty()); 248 249 delete fIteratorsToUpdate; 250 delete fNodes; 251 delete fIndexer; 252} 253 254 255status_t 256AttributeIndex::Init(Volume* volume, const char* name, uint32 type, 257 size_t keyLength) 258{ 259 status_t error = Index::Init(volume, name, type, keyLength > 0, keyLength); 260 if (error != B_OK) 261 return error; 262 263 // TODO: Letting each attribute index be a listener is gets more expensive 264 // the more attribute indices we have. Since most attribute indices are 265 // rather sparse, it might be a good idea to rather let Volume iterate 266 // through the actual attributes of an added node and look up and call the 267 // index for each one explicitly. When removing the node, the volume would 268 // iterate through the attributes again and determine based on the index 269 // cookie whether an index has to be notified. 270 fVolume->AddNodeListener(this, NULL); 271 272 fNodes = new(std::nothrow) NodeTree(TreeDefinition(type)); 273 fIteratorsToUpdate = new(std::nothrow) IteratorList; 274 fIndexer = new(std::nothrow) AttributeIndexer(this); 275 276 if (fNodes == NULL || fIteratorsToUpdate == NULL || fIndexer == NULL) 277 return B_NO_MEMORY; 278 279 return B_OK; 280} 281 282 283int32 284AttributeIndex::CountEntries() const 285{ 286 return fNodes->Count(); 287} 288 289 290void 291AttributeIndex::NodeAdded(Node* node) 292{ 293 if (node->IndexAttribute(fIndexer) != B_OK) 294 return; 295 296 TreeValue* treeValue = fIndexer->Cookie(); 297 treeValue->node = node; 298 299 fNodes->Insert(treeValue); 300} 301 302 303void 304AttributeIndex::NodeRemoved(Node* node) 305{ 306 TreeValue* treeValue = (TreeValue*)node->IndexCookieForAttribute(Name()); 307 if (treeValue == NULL) 308 return; 309 310 treeValue->owner->UnsetIndexCookie(treeValue->attributeCookie); 311 fNodes->Remove(treeValue); 312} 313 314 315void 316AttributeIndex::NodeChanged(Node* node, uint32 statFields, 317 const OldNodeAttributes& oldAttributes) 318{ 319 IteratorList iterators; 320 iterators.MoveFrom(fIteratorsToUpdate); 321 322 TreeValue* oldTreeValue 323 = (TreeValue*)oldAttributes.IndexCookieForAttribute(Name()); 324 TreeValue* treeValue = (TreeValue*)node->IndexCookieForAttribute(Name()); 325 if (treeValue == NULL && oldTreeValue == NULL) 326 return; 327 328 // move the iterators that point to the node to the previous node 329 if (oldTreeValue != NULL) { 330 for (IteratorList::Iterator it = iterators.GetIterator(); 331 Iterator* iterator = it.Next();) { 332 iterator->NodeChangeBegin(node); 333 } 334 335 // remove the node 336 fNodes->Remove(oldTreeValue); 337 } 338 339 // re-insert the node 340 if (treeValue != NULL) 341 fNodes->Insert(treeValue); 342 343 // Move the iterators to the next node again. If the node hasn't changed 344 // its place, they will point to it again, otherwise to the node originally 345 // succeeding it. 346 if (oldTreeValue != NULL) { 347 for (IteratorList::Iterator it = iterators.GetIterator(); 348 Iterator* iterator = it.Next();) { 349 iterator->NodeChangeEnd(node); 350 } 351 } 352 353 // update live queries 354 fVolume->UpdateLiveQueries(node, Name(), Type(), 355 oldTreeValue != NULL ? oldTreeValue->data : NULL, 356 oldTreeValue != NULL ? oldTreeValue->length : 0, 357 treeValue != NULL ? treeValue->data : NULL, 358 treeValue != NULL ? treeValue->length : 0); 359 360 if (oldTreeValue != NULL) 361 oldTreeValue->Delete(); 362} 363 364 365AbstractIndexIterator* 366AttributeIndex::InternalGetIterator() 367{ 368 Iterator* iterator = new(std::nothrow) Iterator; 369 if (iterator != NULL) { 370 if (!iterator->SetTo(this, TreeKey(), true)) { 371 delete iterator; 372 iterator = NULL; 373 } 374 } 375 return iterator; 376} 377 378 379AbstractIndexIterator* 380AttributeIndex::InternalFind(const void* key, size_t length) 381{ 382 if (HasFixedKeyLength() && length != KeyLength()) 383 return NULL; 384 385 Iterator* iterator = new(std::nothrow) Iterator; 386 if (iterator != NULL) { 387 if (!iterator->SetTo(this, TreeKey(key, length))) { 388 delete iterator; 389 iterator = NULL; 390 } 391 } 392 return iterator; 393} 394 395 396void 397AttributeIndex::_AddIteratorToUpdate(Iterator* iterator) 398{ 399 fIteratorsToUpdate->Add(iterator); 400} 401 402 403// #pragma mark - Iterator 404 405 406void 407AttributeIndex::Iterator::NodeChanged(Node* node, uint32 statFields, 408 const OldNodeAttributes& oldAttributes) 409{ 410 fIndex->_AddIteratorToUpdate(this); 411} 412