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(), AVLTreeStandardCompare<Attribute*>(), 146 AVLTreeStandardGetKey<Attribute*, Attribute*>(), 147 AVLTreeStandardNodeAllocator<Attribute*, 148 AVLTreeStandardNode<Attribute*> >(), 149 AVLTreeStandardGetValue<Attribute*, 150 AVLTreeStandardNode<Attribute*> >()) 151 { 152 } 153}; 154 155 156// Iterator 157class AttributeIndexImpl::Iterator 158 : public NodeEntryIterator< 159 AttributeNodeIterator<AttributeTree::Iterator> >, 160 public DoublyLinkedListLinkImpl<Iterator>, public EntryListener, 161 public NodeListener { 162public: 163 Iterator(); 164 virtual ~Iterator(); 165 166 virtual Entry *GetCurrent(); 167 virtual Entry *GetCurrent(uint8 *buffer, size_t *keyLength); 168 169 virtual status_t Suspend(); 170 virtual status_t Resume(); 171 172 bool SetTo(AttributeIndexImpl *index, const uint8 *key, size_t length, 173 bool ignoreValue = false); 174 void Unset(); 175 176 virtual void EntryRemoved(Entry *entry); 177 virtual void NodeRemoved(Node *node); 178 179private: 180 typedef NodeEntryIterator< 181 AttributeNodeIterator<AttributeTree::Iterator> > BaseClass; 182 183private: 184 AttributeIndexImpl *fIndex; 185}; 186 187 188// IteratorList 189class AttributeIndexImpl::IteratorList : public DoublyLinkedList<Iterator> {}; 190 191 192// AttributeIndexImpl 193 194// constructor 195AttributeIndexImpl::AttributeIndexImpl(Volume *volume, const char *name, 196 uint32 type, size_t keyLength) 197 : AttributeIndex(volume, name, type, (keyLength > 0), keyLength), 198 fAttributes(new(nothrow) AttributeTree(type)), 199 fIterators(new(nothrow) IteratorList) 200{ 201 if (fInitStatus == B_OK && (!fAttributes || !fIterators)) 202 fInitStatus = B_NO_MEMORY; 203} 204 205// destructor 206AttributeIndexImpl::~AttributeIndexImpl() 207{ 208 if (fIterators) { 209 // unset the iterators 210 for (Iterator *iterator = fIterators->First(); 211 iterator; 212 iterator = fIterators->GetNext(iterator)) { 213 iterator->SetTo(NULL, NULL, 0); 214 } 215 delete fIterators; 216 } 217 // unset all attributes and delete the tree 218 if (fAttributes) { 219 AttributeTree::Iterator it; 220 fAttributes->GetIterator(&it); 221 for (Attribute **attribute = it.GetCurrent(); attribute; it.GetNext()) 222 (*attribute)->SetIndex(NULL, false); 223 delete fAttributes; 224 } 225} 226 227// CountEntries 228int32 229AttributeIndexImpl::CountEntries() const 230{ 231 return fAttributes->CountItems(); 232} 233 234// Changed 235status_t 236AttributeIndexImpl::Changed(Attribute *attribute, const uint8 *oldKey, 237 size_t oldLength) 238{ 239 status_t error = B_BAD_VALUE; 240 if (attribute && attribute->GetIndex() == this) { 241 // update the iterators and remove the attribute from the tree 242 error = B_OK; 243 if (attribute->IsInIndex()) { 244 AttributeTree::Iterator it; 245 Attribute **foundAttribute = fAttributes->Find( 246 PrimaryKey(attribute, oldKey, oldLength), attribute, &it); 247 if (foundAttribute && *foundAttribute == attribute) { 248 Node *node = attribute->GetNode(); 249 // update the iterators 250 for (Iterator *iterator = fIterators->First(); 251 iterator; 252 iterator = fIterators->GetNext(iterator)) { 253 if (iterator->GetCurrentNode() == node) 254 iterator->NodeRemoved(node); 255 } 256 // remove and re-insert the attribute 257 fAttributes->Remove(it); 258 } 259 } 260 // re-insert the attribute 261 if (fKeyLength > 0 && attribute->GetSize() != fKeyLength) { 262 attribute->SetIndex(this, false); 263 } else { 264 error = fAttributes->Insert(attribute); 265 if (error == B_OK) 266 attribute->SetIndex(this, true); 267 else 268 attribute->SetIndex(NULL, false); 269 } 270 } 271 return error; 272} 273 274// Added 275status_t 276AttributeIndexImpl::Added(Attribute *attribute) 277{ 278PRINT(("AttributeIndex::Add(%p)\n", attribute)); 279 status_t error = (attribute ? B_OK : B_BAD_VALUE); 280 if (error == B_OK) { 281 size_t size = attribute->GetSize(); 282 if (fKeyLength > 0 && size != fKeyLength) { 283 attribute->SetIndex(this, false); 284 } else { 285 error = fAttributes->Insert(attribute); 286 if (error == B_OK) 287 attribute->SetIndex(this, true); 288 } 289 } 290 return error; 291} 292 293// Removed 294bool 295AttributeIndexImpl::Removed(Attribute *attribute) 296{ 297PRINT(("AttributeIndex::Removed(%p)\n", attribute)); 298 bool result = (attribute && attribute->GetIndex() == this); 299 if (result) { 300 if (attribute->IsInIndex()) 301 fAttributes->Remove(attribute, attribute); 302 attribute->SetIndex(NULL, false); 303 } 304 return result; 305} 306 307// InternalGetIterator 308AbstractIndexEntryIterator * 309AttributeIndexImpl::InternalGetIterator() 310{ 311 Iterator *iterator = new(nothrow) Iterator; 312 if (iterator) { 313 if (!iterator->SetTo(this, NULL, 0, true)) { 314 delete iterator; 315 iterator = NULL; 316 } 317 } 318 return iterator; 319} 320 321// InternalFind 322AbstractIndexEntryIterator * 323AttributeIndexImpl::InternalFind(const uint8 *key, size_t length) 324{ 325 if (!key || (fKeyLength > 0 && length != fKeyLength)) 326 return NULL; 327 Iterator *iterator = new(nothrow) Iterator; 328 if (iterator) { 329 if (!iterator->SetTo(this, key, length)) { 330 delete iterator; 331 iterator = NULL; 332 } 333 } 334 return iterator; 335} 336 337// _AddIterator 338void 339AttributeIndexImpl::_AddIterator(Iterator *iterator) 340{ 341 fIterators->Insert(iterator); 342} 343 344// _RemoveIterator 345void 346AttributeIndexImpl::_RemoveIterator(Iterator *iterator) 347{ 348 fIterators->Remove(iterator); 349} 350 351 352// Iterator 353 354// constructor 355AttributeIndexImpl::Iterator::Iterator() 356 : BaseClass(), 357 fIndex(NULL) 358{ 359} 360 361// destructor 362AttributeIndexImpl::Iterator::~Iterator() 363{ 364 SetTo(NULL, NULL, 0); 365} 366 367// GetCurrent 368Entry * 369AttributeIndexImpl::Iterator::GetCurrent() 370{ 371 return BaseClass::GetCurrent(); 372} 373 374// GetCurrent 375Entry * 376AttributeIndexImpl::Iterator::GetCurrent(uint8 *buffer, size_t *keyLength) 377{ 378 Entry *entry = GetCurrent(); 379 if (entry) { 380 if (Attribute **attribute = fIterator.fIterator.GetCurrent()) { 381 if ((*attribute)->GetNode() == entry->GetNode()) { 382 (*attribute)->GetKey(buffer, keyLength); 383 } else { 384 FATAL(("Node of current attribute and node of current entry " 385 "differ: %Ld vs. %Ld\n", 386 (*attribute)->GetNode()->GetID(), 387 entry->GetNode()->GetID())); 388 entry = NULL; 389 } 390 } else { 391 FATAL(("We have a current entry (`%s', node: %Ld), but no current " 392 "attribute.\n", entry->GetName(), 393 entry->GetNode()->GetID())); 394 entry = NULL; 395 } 396 } 397 return entry; 398} 399 400// Suspend 401status_t 402AttributeIndexImpl::Iterator::Suspend() 403{ 404 status_t error = BaseClass::Suspend(); 405 if (error == B_OK) { 406 if (fNode) { 407 error = fIndex->GetVolume()->AddNodeListener(this, fNode, 408 NODE_LISTEN_REMOVED); 409 if (error == B_OK && fEntry) { 410 error = fIndex->GetVolume()->AddEntryListener(this, fEntry, 411 ENTRY_LISTEN_REMOVED); 412 if (error != B_OK) 413 fIndex->GetVolume()->RemoveNodeListener(this, fNode); 414 } 415 if (error != B_OK) 416 BaseClass::Resume(); 417 } 418 } 419 return error; 420} 421 422// Resume 423status_t 424AttributeIndexImpl::Iterator::Resume() 425{ 426 status_t error = BaseClass::Resume(); 427 if (error == B_OK) { 428 if (fEntry) 429 error = fIndex->GetVolume()->RemoveEntryListener(this, fEntry); 430 if (fNode) { 431 if (error == B_OK) 432 error = fIndex->GetVolume()->RemoveNodeListener(this, fNode); 433 else 434 fIndex->GetVolume()->RemoveNodeListener(this, fNode); 435 } 436 } 437 return error; 438} 439 440// SetTo 441bool 442AttributeIndexImpl::Iterator::SetTo(AttributeIndexImpl *index, 443 const uint8 *key, size_t length, bool ignoreValue) 444{ 445 Resume(); 446 Unset(); 447 // set the new values 448 fIndex = index; 449 if (fIndex) 450 fIndex->_AddIterator(this); 451 fInitialized = fIndex; 452 // get the attribute node's first entry 453 if (fIndex) { 454 // get the first node 455 bool found = true; 456 if (ignoreValue) 457 fIndex->fAttributes->GetIterator(&fIterator.fIterator); 458 else { 459 found = fIndex->fAttributes->FindFirst(PrimaryKey(key, length), 460 &(fIterator.fIterator)); 461 } 462 // get the first entry 463 if (found) { 464 if (Node **nodeP = fIterator.GetCurrent()) { 465 fNode = *nodeP; 466 fEntry = fNode->GetFirstReferrer(); 467 if (!fEntry) 468 BaseClass::GetNext(); 469 if (Attribute **attribute = fIterator.fIterator.GetCurrent()) { 470 const uint8 *attrKey; 471 size_t attrKeyLength; 472 (*attribute)->GetKey(&attrKey, &attrKeyLength); 473 if (!ignoreValue 474 && compare_keys(attrKey, attrKeyLength, key, length, 475 fIndex->GetType()) != 0) { 476 Unset(); 477 } 478 } 479 } 480 } 481 } 482 return fEntry; 483} 484 485// Unset 486void 487AttributeIndexImpl::Iterator::Unset() 488{ 489 if (fIndex) { 490 fIndex->_RemoveIterator(this); 491 fIndex = NULL; 492 } 493 BaseClass::Unset(); 494} 495 496// EntryRemoved 497void 498AttributeIndexImpl::Iterator::EntryRemoved(Entry */*entry*/) 499{ 500 Resume(); 501 fIsNext = BaseClass::GetNext(); 502 Suspend(); 503} 504 505// NodeRemoved 506void 507AttributeIndexImpl::Iterator::NodeRemoved(Node */*node*/) 508{ 509 Resume(); 510 fEntry = NULL; 511 fIsNext = BaseClass::GetNext(); 512 Suspend(); 513} 514 515