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