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
21 template<typename Key>
22 static inline
23 int
compare_integral(const Key & a,const Key & b)24 compare_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
34 static
35 int
compare_keys(const uint8 * key1,size_t length1,const uint8 * key2,size_t length2,uint32 type)36 compare_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
67 class AttributeIndexImpl::PrimaryKey {
68 public:
PrimaryKey(Attribute * attribute,const uint8 * theKey,size_t length)69 PrimaryKey(Attribute *attribute, const uint8 *theKey,
70 size_t length)
71 : attribute(attribute), length(length)
72 { memcpy(key, theKey, length); }
PrimaryKey(Attribute * attribute)73 PrimaryKey(Attribute *attribute)
74 : attribute(attribute) { attribute->GetKey(key, &length); }
PrimaryKey(const uint8 * theKey,size_t 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
85 class AttributeIndexImpl::GetPrimaryKey {
86 public:
operator ()(Attribute * a)87 inline PrimaryKey operator()(Attribute *a)
88 {
89 return PrimaryKey(a);
90 }
91
operator ()(Attribute * a) const92 inline PrimaryKey operator()(Attribute *a) const
93 {
94 return PrimaryKey(a);
95 }
96 };
97
98 // PrimaryKeyCompare
99 class AttributeIndexImpl::PrimaryKeyCompare
100 {
101 public:
PrimaryKeyCompare(uint32 type)102 PrimaryKeyCompare(uint32 type) : fType(type) {}
103
operator ()(const PrimaryKey & a,const PrimaryKey & b) const104 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
116 template<typename AttributeIterator>
117 class AttributeNodeIterator {
118 public:
GetCurrent()119 inline Node **GetCurrent()
120 {
121 if (Attribute **attribute = fIterator.GetCurrent()) {
122 fNode = (*attribute)->GetNode();
123 return &fNode;
124 }
125 return NULL;
126 }
127
GetNext()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
143 class AttributeIndexImpl::AttributeTree
144 : public TwoKeyAVLTree<Attribute*, PrimaryKey, PrimaryKeyCompare,
145 GetPrimaryKey> {
146 public:
AttributeTree(uint32 type)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
158 class AttributeIndexImpl::Iterator
159 : public NodeEntryIterator<
160 AttributeNodeIterator<AttributeTree::Iterator> >,
161 public DoublyLinkedListLinkImpl<Iterator>, public EntryListener,
162 public NodeListener {
163 public:
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
180 private:
181 typedef NodeEntryIterator<
182 AttributeNodeIterator<AttributeTree::Iterator> > BaseClass;
183
184 private:
185 AttributeIndexImpl *fIndex;
186 };
187
188
189 // IteratorList
190 class AttributeIndexImpl::IteratorList : public DoublyLinkedList<Iterator> {};
191
192
193 // AttributeIndexImpl
194
195 // constructor
AttributeIndexImpl(Volume * volume,const char * name,uint32 type,size_t keyLength)196 AttributeIndexImpl::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
~AttributeIndexImpl()207 AttributeIndexImpl::~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
229 int32
CountEntries() const230 AttributeIndexImpl::CountEntries() const
231 {
232 return fAttributes->CountItems();
233 }
234
235 // Changed
236 status_t
Changed(Attribute * attribute,const uint8 * oldKey,size_t oldLength)237 AttributeIndexImpl::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
276 status_t
Added(Attribute * attribute)277 AttributeIndexImpl::Added(Attribute *attribute)
278 {
279 PRINT("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
295 bool
Removed(Attribute * attribute)296 AttributeIndexImpl::Removed(Attribute *attribute)
297 {
298 PRINT("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
309 AbstractIndexEntryIterator *
InternalGetIterator()310 AttributeIndexImpl::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
323 AbstractIndexEntryIterator *
InternalFind(const uint8 * key,size_t length)324 AttributeIndexImpl::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
339 void
_AddIterator(Iterator * iterator)340 AttributeIndexImpl::_AddIterator(Iterator *iterator)
341 {
342 fIterators->Insert(iterator);
343 }
344
345 // _RemoveIterator
346 void
_RemoveIterator(Iterator * iterator)347 AttributeIndexImpl::_RemoveIterator(Iterator *iterator)
348 {
349 fIterators->Remove(iterator);
350 }
351
352
353 // Iterator
354
355 // constructor
Iterator()356 AttributeIndexImpl::Iterator::Iterator()
357 : BaseClass(),
358 fIndex(NULL)
359 {
360 }
361
362 // destructor
~Iterator()363 AttributeIndexImpl::Iterator::~Iterator()
364 {
365 SetTo(NULL, NULL, 0);
366 }
367
368 // GetCurrent
369 Entry *
GetCurrent()370 AttributeIndexImpl::Iterator::GetCurrent()
371 {
372 return BaseClass::GetCurrent();
373 }
374
375 // GetCurrent
376 Entry *
GetCurrent(uint8 * buffer,size_t * keyLength)377 AttributeIndexImpl::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
402 status_t
Suspend()403 AttributeIndexImpl::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
424 status_t
Resume()425 AttributeIndexImpl::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
442 bool
SetTo(AttributeIndexImpl * index,const uint8 * key,size_t length,bool ignoreValue)443 AttributeIndexImpl::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
487 void
Unset()488 AttributeIndexImpl::Iterator::Unset()
489 {
490 if (fIndex) {
491 fIndex->_RemoveIterator(this);
492 fIndex = NULL;
493 }
494 BaseClass::Unset();
495 }
496
497 // EntryRemoved
498 void
EntryRemoved(Entry *)499 AttributeIndexImpl::Iterator::EntryRemoved(Entry */*entry*/)
500 {
501 Resume();
502 fIsNext = BaseClass::GetNext();
503 Suspend();
504 }
505
506 // NodeRemoved
507 void
NodeRemoved(Node *)508 AttributeIndexImpl::Iterator::NodeRemoved(Node */*node*/)
509 {
510 Resume();
511 fEntry = NULL;
512 fIsNext = BaseClass::GetNext();
513 Suspend();
514 }
515
516