1/* 2 * Copyright 2007, Ingo Weinhold, ingo_weinhold@gmx.de. 3 * All rights reserved. Distributed under the terms of the MIT license. 4 */ 5 6#include <TypeConstants.h> 7 8#include "AttributeIndexImpl.h" 9#include "DebugSupport.h" 10#include "Entry.h" 11#include "EntryListener.h" 12#include "IndexImpl.h" 13#include "Misc.h" 14#include "Node.h" 15#include "NodeListener.h" 16#include "ramfs.h" 17#include "TwoKeyAVLTree.h" 18#include "Volume.h" 19 20// compare_integral 21template<typename Key> 22static inline 23int 24compare_integral(const Key &a, const Key &b) 25{ 26 if (a < b) 27 return -1; 28 else if (a > b) 29 return 1; 30 return 0; 31} 32 33// compare_keys 34static 35int 36compare_keys(const uint8 *key1, size_t length1, const uint8 *key2, 37 size_t length2, uint32 type) 38{ 39 switch (type) { 40 case B_INT32_TYPE: 41 return compare_integral(*(int32*)key1, *(int32*)key2); 42 case B_UINT32_TYPE: 43 return compare_integral(*(uint32*)key1, *(uint32*)key2); 44 case B_INT64_TYPE: 45 return compare_integral(*(int64*)key1, *(int64*)key2); 46 case B_UINT64_TYPE: 47 return compare_integral(*(uint64*)key1, *(uint64*)key2); 48 case B_FLOAT_TYPE: 49 return compare_integral(*(float*)key1, *(float*)key2); 50 case B_DOUBLE_TYPE: 51 return compare_integral(*(double*)key1, *(double*)key2); 52 case B_STRING_TYPE: 53 { 54 int result = strncmp((const char*)key1, (const char*)key2, 55 min(length1, length2)); 56 if (result == 0) { 57 result = compare_integral(strnlen((const char*)key1, length1), 58 strnlen((const char*)key2, length2)); 59 } 60 return result; 61 } 62 } 63 return -1; 64} 65 66// PrimaryKey 67class AttributeIndexImpl::PrimaryKey { 68public: 69 PrimaryKey(Attribute *attribute, const uint8 *theKey, 70 size_t length) 71 : attribute(attribute), length(length) 72 { memcpy(key, theKey, length); } 73 PrimaryKey(Attribute *attribute) 74 : attribute(attribute) { attribute->GetKey(key, &length); } 75 PrimaryKey(const uint8 *theKey, size_t length) 76 : attribute(NULL), length(length) 77 { memcpy(key, theKey, length); } 78 79 Attribute *attribute; 80 uint8 key[kMaxIndexKeyLength]; 81 size_t length; 82}; 83 84// GetPrimaryKey 85class AttributeIndexImpl::GetPrimaryKey { 86public: 87 inline PrimaryKey operator()(Attribute *a) 88 { 89 return PrimaryKey(a); 90 } 91 92 inline PrimaryKey operator()(Attribute *a) const 93 { 94 return PrimaryKey(a); 95 } 96}; 97 98// PrimaryKeyCompare 99class AttributeIndexImpl::PrimaryKeyCompare 100{ 101public: 102 PrimaryKeyCompare(uint32 type) : fType(type) {} 103 104 inline int operator()(const PrimaryKey &a, 105 const PrimaryKey &b) const 106 { 107 if (a.attribute != NULL && a.attribute == b.attribute) 108 return 0; 109 return compare_keys(a.key, a.length, b.key, b.length, fType); 110 } 111 112 uint32 fType; 113}; 114 115// AttributeNodeIterator 116template<typename AttributeIterator> 117class AttributeNodeIterator { 118public: 119 inline Node **GetCurrent() 120 { 121 if (Attribute **attribute = fIterator.GetCurrent()) { 122 fNode = (*attribute)->GetNode(); 123 return &fNode; 124 } 125 return NULL; 126 } 127 128 inline Node **GetNext() 129 { 130 if (Attribute **attribute = fIterator.GetNext()) { 131 fNode = (*attribute)->GetNode(); 132 return &fNode; 133 } 134 return NULL; 135 } 136 137 AttributeIterator fIterator; 138 Node *fNode; 139}; 140 141 142// AttributeTree 143class AttributeIndexImpl::AttributeTree 144 : public TwoKeyAVLTree<Attribute*, PrimaryKey, PrimaryKeyCompare, 145 GetPrimaryKey> { 146public: 147 AttributeTree(uint32 type) 148 : TwoKeyAVLTree<Attribute*, PrimaryKey, PrimaryKeyCompare, 149 GetPrimaryKey>(PrimaryKeyCompare(type), 150 GetPrimaryKey(), TwoKeyAVLTreeStandardCompare<Attribute*>(), 151 TwoKeyAVLTreeStandardGetKey<Attribute*, Attribute*>()) 152 { 153 } 154}; 155 156 157// Iterator 158class AttributeIndexImpl::Iterator 159 : public NodeEntryIterator< 160 AttributeNodeIterator<AttributeTree::Iterator> >, 161 public DoublyLinkedListLinkImpl<Iterator>, public EntryListener, 162 public NodeListener { 163public: 164 Iterator(); 165 virtual ~Iterator(); 166 167 virtual Entry *GetCurrent(); 168 virtual Entry *GetCurrent(uint8 *buffer, size_t *keyLength); 169 170 virtual status_t Suspend(); 171 virtual status_t Resume(); 172 173 bool SetTo(AttributeIndexImpl *index, const uint8 *key, size_t length, 174 bool ignoreValue = false); 175 void Unset(); 176 177 virtual void EntryRemoved(Entry *entry); 178 virtual void NodeRemoved(Node *node); 179 180private: 181 typedef NodeEntryIterator< 182 AttributeNodeIterator<AttributeTree::Iterator> > BaseClass; 183 184private: 185 AttributeIndexImpl *fIndex; 186}; 187 188 189// IteratorList 190class AttributeIndexImpl::IteratorList : public DoublyLinkedList<Iterator> {}; 191 192 193// AttributeIndexImpl 194 195// constructor 196AttributeIndexImpl::AttributeIndexImpl(Volume *volume, const char *name, 197 uint32 type, size_t keyLength) 198 : AttributeIndex(volume, name, type, (keyLength > 0), keyLength), 199 fAttributes(new(nothrow) AttributeTree(type)), 200 fIterators(new(nothrow) IteratorList) 201{ 202 if (fInitStatus == B_OK && (!fAttributes || !fIterators)) 203 fInitStatus = B_NO_MEMORY; 204} 205 206// destructor 207AttributeIndexImpl::~AttributeIndexImpl() 208{ 209 if (fIterators) { 210 // unset the iterators 211 for (Iterator *iterator = fIterators->First(); 212 iterator; 213 iterator = fIterators->GetNext(iterator)) { 214 iterator->SetTo(NULL, NULL, 0); 215 } 216 delete fIterators; 217 } 218 // unset all attributes and delete the tree 219 if (fAttributes) { 220 AttributeTree::Iterator it; 221 fAttributes->GetIterator(&it); 222 for (Attribute **attribute = it.GetCurrent(); attribute; it.GetNext()) 223 (*attribute)->SetIndex(NULL, false); 224 delete fAttributes; 225 } 226} 227 228// CountEntries 229int32 230AttributeIndexImpl::CountEntries() const 231{ 232 return fAttributes->CountItems(); 233} 234 235// Changed 236status_t 237AttributeIndexImpl::Changed(Attribute *attribute, const uint8 *oldKey, 238 size_t oldLength) 239{ 240 status_t error = B_BAD_VALUE; 241 if (attribute && attribute->GetIndex() == this) { 242 // update the iterators and remove the attribute from the tree 243 error = B_OK; 244 if (attribute->IsInIndex()) { 245 AttributeTree::Iterator it; 246 Attribute **foundAttribute = fAttributes->Find( 247 PrimaryKey(attribute, oldKey, oldLength), attribute, &it); 248 if (foundAttribute && *foundAttribute == attribute) { 249 Node *node = attribute->GetNode(); 250 // update the iterators 251 for (Iterator *iterator = fIterators->First(); 252 iterator; 253 iterator = fIterators->GetNext(iterator)) { 254 if (iterator->GetCurrentNode() == node) 255 iterator->NodeRemoved(node); 256 } 257 // remove and re-insert the attribute 258 it.Remove(); 259 } 260 } 261 // re-insert the attribute 262 if (fKeyLength > 0 && attribute->GetSize() != (off_t)fKeyLength) { 263 attribute->SetIndex(this, false); 264 } else { 265 error = fAttributes->Insert(attribute); 266 if (error == B_OK) 267 attribute->SetIndex(this, true); 268 else 269 attribute->SetIndex(NULL, false); 270 } 271 } 272 return error; 273} 274 275// Added 276status_t 277AttributeIndexImpl::Added(Attribute *attribute) 278{ 279PRINT("AttributeIndex::Add(%p)\n", attribute); 280 status_t error = (attribute ? B_OK : B_BAD_VALUE); 281 if (error == B_OK) { 282 size_t size = attribute->GetSize(); 283 if (fKeyLength > 0 && size != fKeyLength) { 284 attribute->SetIndex(this, false); 285 } else { 286 error = fAttributes->Insert(attribute); 287 if (error == B_OK) 288 attribute->SetIndex(this, true); 289 } 290 } 291 return error; 292} 293 294// Removed 295bool 296AttributeIndexImpl::Removed(Attribute *attribute) 297{ 298PRINT("AttributeIndex::Removed(%p)\n", attribute); 299 bool result = (attribute && attribute->GetIndex() == this); 300 if (result) { 301 if (attribute->IsInIndex()) 302 fAttributes->Remove(attribute, attribute); 303 attribute->SetIndex(NULL, false); 304 } 305 return result; 306} 307 308// InternalGetIterator 309AbstractIndexEntryIterator * 310AttributeIndexImpl::InternalGetIterator() 311{ 312 Iterator *iterator = new(nothrow) Iterator; 313 if (iterator) { 314 if (!iterator->SetTo(this, NULL, 0, true)) { 315 delete iterator; 316 iterator = NULL; 317 } 318 } 319 return iterator; 320} 321 322// InternalFind 323AbstractIndexEntryIterator * 324AttributeIndexImpl::InternalFind(const uint8 *key, size_t length) 325{ 326 if (!key || (fKeyLength > 0 && length != fKeyLength)) 327 return NULL; 328 Iterator *iterator = new(nothrow) Iterator; 329 if (iterator) { 330 if (!iterator->SetTo(this, key, length)) { 331 delete iterator; 332 iterator = NULL; 333 } 334 } 335 return iterator; 336} 337 338// _AddIterator 339void 340AttributeIndexImpl::_AddIterator(Iterator *iterator) 341{ 342 fIterators->Insert(iterator); 343} 344 345// _RemoveIterator 346void 347AttributeIndexImpl::_RemoveIterator(Iterator *iterator) 348{ 349 fIterators->Remove(iterator); 350} 351 352 353// Iterator 354 355// constructor 356AttributeIndexImpl::Iterator::Iterator() 357 : BaseClass(), 358 fIndex(NULL) 359{ 360} 361 362// destructor 363AttributeIndexImpl::Iterator::~Iterator() 364{ 365 SetTo(NULL, NULL, 0); 366} 367 368// GetCurrent 369Entry * 370AttributeIndexImpl::Iterator::GetCurrent() 371{ 372 return BaseClass::GetCurrent(); 373} 374 375// GetCurrent 376Entry * 377AttributeIndexImpl::Iterator::GetCurrent(uint8 *buffer, size_t *keyLength) 378{ 379 Entry *entry = GetCurrent(); 380 if (entry) { 381 if (Attribute **attribute = fIterator.fIterator.GetCurrent()) { 382 if ((*attribute)->GetNode() == entry->GetNode()) { 383 (*attribute)->GetKey(buffer, keyLength); 384 } else { 385 FATAL("Node of current attribute and node of current entry " 386 "differ: %" B_PRIdINO " vs. %" B_PRIdINO "\n", 387 (*attribute)->GetNode()->GetID(), 388 entry->GetNode()->GetID()); 389 entry = NULL; 390 } 391 } else { 392 FATAL("We have a current entry (`%s', node: %" B_PRIdINO "), but no current " 393 "attribute.\n", entry->GetName(), 394 entry->GetNode()->GetID()); 395 entry = NULL; 396 } 397 } 398 return entry; 399} 400 401// Suspend 402status_t 403AttributeIndexImpl::Iterator::Suspend() 404{ 405 status_t error = BaseClass::Suspend(); 406 if (error == B_OK) { 407 if (fNode) { 408 error = fIndex->GetVolume()->AddNodeListener(this, fNode, 409 NODE_LISTEN_REMOVED); 410 if (error == B_OK && fEntry) { 411 error = fIndex->GetVolume()->AddEntryListener(this, fEntry, 412 ENTRY_LISTEN_REMOVED); 413 if (error != B_OK) 414 fIndex->GetVolume()->RemoveNodeListener(this, fNode); 415 } 416 if (error != B_OK) 417 BaseClass::Resume(); 418 } 419 } 420 return error; 421} 422 423// Resume 424status_t 425AttributeIndexImpl::Iterator::Resume() 426{ 427 status_t error = BaseClass::Resume(); 428 if (error == B_OK) { 429 if (fEntry) 430 error = fIndex->GetVolume()->RemoveEntryListener(this, fEntry); 431 if (fNode) { 432 if (error == B_OK) 433 error = fIndex->GetVolume()->RemoveNodeListener(this, fNode); 434 else 435 fIndex->GetVolume()->RemoveNodeListener(this, fNode); 436 } 437 } 438 return error; 439} 440 441// SetTo 442bool 443AttributeIndexImpl::Iterator::SetTo(AttributeIndexImpl *index, 444 const uint8 *key, size_t length, bool ignoreValue) 445{ 446 Resume(); 447 Unset(); 448 // set the new values 449 fIndex = index; 450 if (fIndex) 451 fIndex->_AddIterator(this); 452 fInitialized = fIndex; 453 // get the attribute node's first entry 454 if (fIndex) { 455 // get the first node 456 bool found = true; 457 if (ignoreValue) 458 fIndex->fAttributes->GetIterator(&fIterator.fIterator); 459 else { 460 found = fIndex->fAttributes->FindFirst(PrimaryKey(key, length), 461 &(fIterator.fIterator)); 462 } 463 // get the first entry 464 if (found) { 465 if (Node **nodeP = fIterator.GetCurrent()) { 466 fNode = *nodeP; 467 fEntry = fNode->GetFirstReferrer(); 468 if (!fEntry) 469 BaseClass::GetNext(); 470 if (Attribute **attribute = fIterator.fIterator.GetCurrent()) { 471 uint8 attrKey[kMaxIndexKeyLength]; 472 size_t attrKeyLength; 473 (*attribute)->GetKey(attrKey, &attrKeyLength); 474 if (!ignoreValue 475 && compare_keys(attrKey, attrKeyLength, key, length, 476 fIndex->GetType()) != 0) { 477 Unset(); 478 } 479 } 480 } 481 } 482 } 483 return fEntry; 484} 485 486// Unset 487void 488AttributeIndexImpl::Iterator::Unset() 489{ 490 if (fIndex) { 491 fIndex->_RemoveIterator(this); 492 fIndex = NULL; 493 } 494 BaseClass::Unset(); 495} 496 497// EntryRemoved 498void 499AttributeIndexImpl::Iterator::EntryRemoved(Entry */*entry*/) 500{ 501 Resume(); 502 fIsNext = BaseClass::GetNext(); 503 Suspend(); 504} 505 506// NodeRemoved 507void 508AttributeIndexImpl::Iterator::NodeRemoved(Node */*node*/) 509{ 510 Resume(); 511 fEntry = NULL; 512 fIsNext = BaseClass::GetNext(); 513 Suspend(); 514} 515 516