kernel/util/MinMaxHeap.h

91 			void		_MoveUp(MinMaxHeapLink<Element, Key>* link);
92 			void		_MoveDown(MinMaxHeapLink<Element, Key>* link);
93 			bool		_ChangeTree(MinMaxHeapLink<Element, Key>* link);
233 	MinMaxHeapLink<Element, Key>* link = sGetLink(element);
235 	Key oldKey = link->fKey;
236 	link->fKey = newKey;
241 	if (sCompare(newKey, oldKey) ^ !link->fMinTree)
242 		_MoveUp(link);
244 		_MoveDown(link);
260 	MinMaxHeapLink<Element, Key>* link = sGetLink(element);
261 	ASSERT(link->fIndex != -1);
262 	link->fIndex = -1;
281 	MinMaxHeapLink<Element, Key>* link = sGetLink(element);
282 	ASSERT(link->fIndex != -1);
283 	link->fIndex = -1;
303 	MinMaxHeapLink<Element, Key>* link = sGetLink(element);
305 	ASSERT(link->fIndex == -1);
307 	link->fMinTree = fMinLastElement < fMaxLastElement;
309 	int& lastElement = link->fMinTree ? fMinLastElement : fMaxLastElement;
310 	Element** tree = link->fMinTree ? fMinElements : fMaxElements;
313 	link->fIndex = lastElement++;
314 	link->fKey = key;
316 	if (!_ChangeTree(link))
317 		_MoveUp(link);
349 MIN_MAX_HEAP_CLASS_NAME::_MoveUp(MinMaxHeapLink<Element, Key>* link)
351 	Element** tree = link->fMinTree ? fMinElements : fMaxElements;
353 		if (link->fIndex <= 0)
356 		int parent = (link->fIndex - 1) / 2;
357 		bool isSmaller = sCompare(link->fKey, sGetLink(tree[parent])->fKey);
358 		if (isSmaller ^ !link->fMinTree) {
360 			sGetLink(tree[parent])->fIndex = link->fIndex;
362 			Element* element = tree[link->fIndex];
363 			tree[link->fIndex] = tree[parent];
366 			link->fIndex = parent;
375 MIN_MAX_HEAP_CLASS_NAME::_MoveDown(MinMaxHeapLink<Element, Key>* link)
379 	int lastElement = link->fMinTree ? fMinLastElement : fMaxLastElement;
380 	Element** tree = link->fMinTree ? fMinElements : fMaxElements;
382 		current = link->fIndex;
384 		int child = 2 * link->fIndex + 1;
386 			bool isSmaller = sCompare(sGetLink(tree[child])->fKey, link->fKey);
387 			if (isSmaller ^ !link->fMinTree)
391 		child = 2 * link->fIndex + 2;
395 			if (isSmaller ^ !link->fMinTree)
399 		if (link->fIndex == current)
403 		sGetLink(tree[current])->fIndex = link->fIndex;
405 		Element* element = tree[link->fIndex];
406 		tree[link->fIndex] = tree[current];
409 		link->fIndex = current;
412 	if (2 * link->fIndex + 1 >= lastElement)
413 		_ChangeTree(link);
419 MIN_MAX_HEAP_CLASS_NAME::_ChangeTree(MinMaxHeapLink<Element, Key>* link)
421 	int otherLastElement = link->fMinTree ? fMaxLastElement : fMinLastElement;
423 	Element** currentTree = link->fMinTree ? fMinElements : fMaxElements;
424 	Element** otherTree = link->fMinTree ? fMaxElements : fMinElements;
427 		ASSERT(link->fMinTree ? fMinLastElement : fMaxLastElement == 1);
431 	ASSERT((link->fIndex - 1) / 2 < otherLastElement);
434 	if (2 * link->fIndex + 1 < otherLastElement) {
435 		predecessor = otherTree[2 * link->fIndex + 1];
436 		ASSERT(sGetLink(predecessor)->fIndex == 2 * link->fIndex + 1);
437 	} else if (link->fIndex < otherLastElement) {
438 		predecessor = otherTree[link->fIndex];
439 		ASSERT(sGetLink(predecessor)->fIndex == link->fIndex);
441 		predecessor = otherTree[(link->fIndex - 1) / 2];
442 		ASSERT(sGetLink(predecessor)->fIndex == (link->fIndex - 1) / 2);
446 	bool isSmaller = sCompare(predecessorLink->fKey, link->fKey);
447 	if (isSmaller ^ !link->fMinTree) {
448 		Element* element = currentTree[link->fIndex];
449 		currentTree[link->fIndex] = otherTree[predecessorLink->fIndex];
452 		int index = link->fIndex;
453 		link->fIndex = predecessorLink->fIndex;
457 		link->fMinTree = !link->fMinTree;
459 		_MoveUp(link);
488 	MinMaxHeapLink<Element, Key>* link = sGetLink(element);
489 	link->fIndex = 0;
490 	link->fMinTree = minTree;
491 	_MoveDown(link);