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 int cmp = QueryParser::compareKeys(fType, a.data, a.length, b->data, 93 b->length); 94 if (cmp != 0) 95 return cmp; 96 97 // The attribute value is the same. Since the tree value is the tree 98 // node itself, we must not return 0, though. We consider a node-less 99 // key always less than an actual tree node with the same attribute 100 // value. 101 return -1; 102 } 103 104 int Compare(const Value* a, const Value* b) const 105 { 106 if (a == b) 107 return 0; 108 109 int cmp = QueryParser::compareKeys(fType, a->data, a->length, b->data, 110 b->length); 111 if (cmp != 0) 112 return cmp; 113 114 return a < b ? -1 : 1; 115 } 116 117private: 118 uint32 fType; 119}; 120 121 122// #pragma mark - NodeTree 123 124 125struct AttributeIndex::NodeTree : public AVLTree<TreeDefinition> { 126 typedef TreeValue Node; 127 128 NodeTree(const TreeDefinition& definition) 129 : 130 AVLTree<TreeDefinition>(definition) 131 { 132 } 133}; 134 135 136// #pragma mark - IteratorList 137 138 139class AttributeIndex::IteratorList : public SinglyLinkedList<Iterator> {}; 140 141 142// #pragma mark - Iterator 143 144 145struct AttributeIndex::IteratorPolicy { 146 typedef AttributeIndex Index; 147 typedef TreeKey Value; 148 typedef AttributeIndex::NodeTree NodeTree; 149 typedef TreeValue TreeNode; 150 typedef IteratorPolicy TreePolicy; 151 152 static NodeTree* GetNodeTree(Index* index) 153 { 154 return index->fNodes; 155 } 156 157 static void GetTreeNodeValue(TreeNode* node, void* buffer, 158 size_t* _keyLength) 159 { 160 if (node->length > 0) 161 memcpy(buffer, node->data, node->length); 162 *_keyLength = node->length; 163 } 164 165 static Node* GetNode(TreeNode* treeNode) 166 { 167 return treeNode->node; 168 } 169 170 static TreeNode* GetFirstTreeNode(Index* index) 171 { 172 return index->fNodes->GetIterator().Next(); 173 } 174 175 static TreeNode* FindClosestTreeNode(Index* index, const Value& value) 176 { 177 return index->fNodes->FindClosest(value, false); 178 } 179}; 180 181 182class AttributeIndex::Iterator : public GenericIndexIterator<IteratorPolicy>, 183 public SinglyLinkedListLinkImpl<Iterator> { 184public: 185 virtual void NodeChanged(Node* node, uint32 statFields, 186 const OldNodeAttributes& oldAttributes); 187}; 188 189 190// #pragma mark - AttributeIndexer 191 192 193AttributeIndexer::AttributeIndexer(AttributeIndex* index) 194 : 195 fIndex(index), 196 fIndexName(index->Name()), 197 fIndexType(index->Type()), 198 fCookie(NULL) 199{ 200} 201 202 203AttributeIndexer::~AttributeIndexer() 204{ 205} 206 207 208status_t 209AttributeIndexer::CreateCookie(IndexedAttributeOwner* owner, 210 void* attributeCookie, uint32 attributeType, size_t attributeSize, 211 void*& _data, size_t& _toRead) 212{ 213 // check the attribute type and size 214 if (attributeType != fIndexType) 215 return B_ERROR; 216 217 if (fIndex->HasFixedKeyLength()) { 218 if (attributeSize != fIndex->KeyLength()) 219 return B_ERROR; 220 } else if (attributeSize > kMaxIndexKeyLength) 221 attributeSize = kMaxIndexKeyLength; 222 223 // create the tree value 224 fCookie = AttributeIndexTreeValue::Create(owner, attributeCookie, 225 attributeSize); 226 if (fCookie == NULL) 227 return B_NO_MEMORY; 228 229 _data = fCookie->data; 230 _toRead = attributeSize; 231 232 return B_OK; 233} 234 235 236void 237AttributeIndexer::DeleteCookie() 238{ 239 fCookie->Delete(); 240 fCookie = NULL; 241} 242 243 244// #pragma mark - AttributeIndex 245 246 247AttributeIndex::AttributeIndex() 248 : 249 Index(), 250 fNodes(NULL), 251 fIteratorsToUpdate(NULL), 252 fIndexer(NULL) 253{ 254} 255 256 257AttributeIndex::~AttributeIndex() 258{ 259 if (IsListening()) 260 fVolume->RemoveNodeListener(this); 261 262 ASSERT(fIteratorsToUpdate->IsEmpty()); 263 264 delete fIteratorsToUpdate; 265 delete fNodes; 266 delete fIndexer; 267} 268 269 270status_t 271AttributeIndex::Init(Volume* volume, const char* name, uint32 type, 272 size_t keyLength) 273{ 274 status_t error = Index::Init(volume, name, type, keyLength > 0, keyLength); 275 if (error != B_OK) 276 return error; 277 278 // TODO: Letting each attribute index be a listener is gets more expensive 279 // the more attribute indices we have. Since most attribute indices are 280 // rather sparse, it might be a good idea to rather let Volume iterate 281 // through the actual attributes of an added node and look up and call the 282 // index for each one explicitly. When removing the node, the volume would 283 // iterate through the attributes again and determine based on the index 284 // cookie whether an index has to be notified. 285 fVolume->AddNodeListener(this, NULL); 286 287 fNodes = new(std::nothrow) NodeTree(TreeDefinition(type)); 288 fIteratorsToUpdate = new(std::nothrow) IteratorList; 289 fIndexer = new(std::nothrow) AttributeIndexer(this); 290 291 if (fNodes == NULL || fIteratorsToUpdate == NULL || fIndexer == NULL) 292 return B_NO_MEMORY; 293 294 return B_OK; 295} 296 297 298int32 299AttributeIndex::CountEntries() const 300{ 301 return fNodes->Count(); 302} 303 304 305void 306AttributeIndex::NodeAdded(Node* node) 307{ 308 if (node->IndexAttribute(fIndexer) != B_OK) 309 return; 310 311 TreeValue* treeValue = fIndexer->Cookie(); 312 treeValue->node = node; 313 314 fNodes->Insert(treeValue); 315} 316 317 318void 319AttributeIndex::NodeRemoved(Node* node) 320{ 321 TreeValue* treeValue = (TreeValue*)node->IndexCookieForAttribute(Name()); 322 if (treeValue == NULL) 323 return; 324 325 treeValue->owner->UnsetIndexCookie(treeValue->attributeCookie); 326 fNodes->Remove(treeValue); 327} 328 329 330void 331AttributeIndex::NodeChanged(Node* node, uint32 statFields, 332 const OldNodeAttributes& oldAttributes) 333{ 334 IteratorList iterators; 335 iterators.MoveFrom(fIteratorsToUpdate); 336 337 TreeValue* oldTreeValue 338 = (TreeValue*)oldAttributes.IndexCookieForAttribute(Name()); 339 TreeValue* treeValue = (TreeValue*)node->IndexCookieForAttribute(Name()); 340 if (treeValue == NULL && oldTreeValue == NULL) 341 return; 342 343 // move the iterators that point to the node to the previous node 344 if (oldTreeValue != NULL) { 345 for (IteratorList::Iterator it = iterators.GetIterator(); 346 Iterator* iterator = it.Next();) { 347 iterator->NodeChangeBegin(node); 348 } 349 350 // remove the node 351 fNodes->Remove(oldTreeValue); 352 } 353 354 // re-insert the node 355 if (treeValue != NULL) 356 fNodes->Insert(treeValue); 357 358 // Move the iterators to the next node again. If the node hasn't changed 359 // its place, they will point to it again, otherwise to the node originally 360 // succeeding it. 361 if (oldTreeValue != NULL) { 362 for (IteratorList::Iterator it = iterators.GetIterator(); 363 Iterator* iterator = it.Next();) { 364 iterator->NodeChangeEnd(node); 365 } 366 } 367 368 // update live queries 369 fVolume->UpdateLiveQueries(node, Name(), Type(), 370 oldTreeValue != NULL ? oldTreeValue->data : NULL, 371 oldTreeValue != NULL ? oldTreeValue->length : 0, 372 treeValue != NULL ? treeValue->data : NULL, 373 treeValue != NULL ? treeValue->length : 0); 374 375 if (oldTreeValue != NULL) 376 oldTreeValue->Delete(); 377} 378 379 380AbstractIndexIterator* 381AttributeIndex::InternalGetIterator() 382{ 383 Iterator* iterator = new(std::nothrow) Iterator; 384 if (iterator != NULL) { 385 if (!iterator->SetTo(this, TreeKey(), true)) { 386 delete iterator; 387 iterator = NULL; 388 } 389 } 390 return iterator; 391} 392 393 394AbstractIndexIterator* 395AttributeIndex::InternalFind(const void* key, size_t length) 396{ 397 if (HasFixedKeyLength() && length != KeyLength()) 398 return NULL; 399 400 Iterator* iterator = new(std::nothrow) Iterator; 401 if (iterator != NULL) { 402 if (!iterator->SetTo(this, TreeKey(key, length))) { 403 delete iterator; 404 iterator = NULL; 405 } 406 } 407 return iterator; 408} 409 410 411void 412AttributeIndex::_AddIteratorToUpdate(Iterator* iterator) 413{ 414 fIteratorsToUpdate->Add(iterator); 415} 416 417 418// #pragma mark - Iterator 419 420 421void 422AttributeIndex::Iterator::NodeChanged(Node* node, uint32 statFields, 423 const OldNodeAttributes& oldAttributes) 424{ 425 fIndex->_AddIteratorToUpdate(this); 426} 427