xref: /haiku/src/add-ons/kernel/file_systems/ramfs/AttributeIndexImpl.cpp (revision 2222d0559df303a9846a2fad53741f8b20b14d7c) 
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
18 template<typename Key>
19 static inline
20 int
21 compare_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
31 static
32 int
33 compare_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
64 class AttributeIndexImpl::PrimaryKey {
65 public:
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
80 class AttributeIndexImpl::GetPrimaryKey {
81 public:
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
94 class AttributeIndexImpl::PrimaryKeyCompare
95 {
96 public:
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
111 template<typename AttributeIterator>
112 class AttributeNodeIterator {
113 public:
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
138 class AttributeIndexImpl::AttributeTree
139 	: public TwoKeyAVLTree<Attribute*, PrimaryKey, PrimaryKeyCompare,
140 						   GetPrimaryKey> {
141 public:
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
153 class AttributeIndexImpl::Iterator
154 	: public NodeEntryIterator<
155 		AttributeNodeIterator<AttributeTree::Iterator> >,
156 	  public DoublyLinkedListLinkImpl<Iterator>, public EntryListener,
157 	  public NodeListener {
158 public:
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 
175 private:
176 	typedef NodeEntryIterator<
177 		AttributeNodeIterator<AttributeTree::Iterator> > BaseClass;
178 
179 private:
180 	AttributeIndexImpl	*fIndex;
181 };
182 
183 
184 // IteratorList
185 class AttributeIndexImpl::IteratorList : public DoublyLinkedList<Iterator> {};
186 
187 
188 // AttributeIndexImpl
189 
190 // constructor
191 AttributeIndexImpl::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
202 AttributeIndexImpl::~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
224 int32
225 AttributeIndexImpl::CountEntries() const
226 {
227 	return fAttributes->CountItems();
228 }
229 
230 // Changed
231 status_t
232 AttributeIndexImpl::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
271 status_t
272 AttributeIndexImpl::Added(Attribute *attribute)
273 {
274 PRINT(("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
290 bool
291 AttributeIndexImpl::Removed(Attribute *attribute)
292 {
293 PRINT(("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
304 AbstractIndexEntryIterator *
305 AttributeIndexImpl::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
318 AbstractIndexEntryIterator *
319 AttributeIndexImpl::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
334 void
335 AttributeIndexImpl::_AddIterator(Iterator *iterator)
336 {
337 	fIterators->Insert(iterator);
338 }
339 
340 // _RemoveIterator
341 void
342 AttributeIndexImpl::_RemoveIterator(Iterator *iterator)
343 {
344 	fIterators->Remove(iterator);
345 }
346 
347 
348 // Iterator
349 
350 // constructor
351 AttributeIndexImpl::Iterator::Iterator()
352 	: BaseClass(),
353 	  fIndex(NULL)
354 {
355 }
356 
357 // destructor
358 AttributeIndexImpl::Iterator::~Iterator()
359 {
360 	SetTo(NULL, NULL, 0);
361 }
362 
363 // GetCurrent
364 Entry *
365 AttributeIndexImpl::Iterator::GetCurrent()
366 {
367 	return BaseClass::GetCurrent();
368 }
369 
370 // GetCurrent
371 Entry *
372 AttributeIndexImpl::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
397 status_t
398 AttributeIndexImpl::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
419 status_t
420 AttributeIndexImpl::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
437 bool
438 AttributeIndexImpl::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
482 void
483 AttributeIndexImpl::Iterator::Unset()
484 {
485 	if (fIndex) {
486 		fIndex->_RemoveIterator(this);
487 		fIndex = NULL;
488 	}
489 	BaseClass::Unset();
490 }
491 
492 // EntryRemoved
493 void
494 AttributeIndexImpl::Iterator::EntryRemoved(Entry */*entry*/)
495 {
496 	Resume();
497 	fIsNext = BaseClass::GetNext();
498 	Suspend();
499 }
500 
501 // NodeRemoved
502 void
503 AttributeIndexImpl::Iterator::NodeRemoved(Node */*node*/)
504 {
505 	Resume();
506 	fEntry = NULL;
507 	fIsNext = BaseClass::GetNext();
508 	Suspend();
509 }
510 
511