78 /**

    79 @internalComponent

    80 */

    81 union TUint64HL

    82 	{

    83 	TUint64		i64;

    84 	TUint32		i32[2];

    85 	};

    86 

    87 

    88 /**

    89 @internalComponent

    90 

    91 Ratio represented = iM*2^iX

    92 e.g. 1.0 has iM=0x80000000, iX=-31

    93 */

    94 struct SRatio

    95 	{

    96 	void Set(TUint32 aInt, TInt aDivisorExp=0);		// set this ratio to aInt/2^aDivisorExp

    97 	TInt Reciprocal();								// this = 1/this

    98 	TInt Mult(TUint32& aInt32);						// Multiply aInt32 by this ratio

    99 //	TInt Mult(TUint64& aInt64);						// Multiply aInt64 by this ratio

   100 

   101 	TUint32		iM;		// mantissa, normalised so bit 31=1

   102 	TInt16		iX;		// -exponent.

   103 	TUint8		iSpare1;

   104 	TUint8		iSpare2;

   105 	};

   106 

   107 /**

   108 @internalComponent

   109 

   110 Ratio and inverse ratio

   111 */

   112 struct SRatioInv

   113 	{

   114 	void Set(const SRatio* aR);

   115 

   116 	SRatio		iR;

   117 	SRatio		iI;

   118 	};

   153 /******************************************************************************

   154  *

   155  * SIMPLE DOUBLY-LINKED CIRCULAR LIST

   156  *

   157  ******************************************************************************/

   158 

   413 /******************************************************************************

   414  *

   415  * ITERABLE DOUBLY-LINKED CIRCULAR LIST

   416  *

   417  ******************************************************************************/

   418 

   419 /**

   420 @internalComponent

   421 

   422 An object that forms part of an iterable doubly linked list.

   423 

   424 SIterDQLink can also be embedded within another object so that that object

   425 can form part of the doubly linked list.

   426 

   427 @see SIterDQ

   428 */

   429 struct SIterDQ;

   430 struct SIterDQIterator;

   431 struct SIterDQLink

   432 	{

   433 	

   434     /**

   435     Default constructor; only defined for debug builds.

   436     

   437     It initialises the link pointers.

   438     */

   439 	FORCE_INLINE SIterDQLink() {iNext=iPrev=0;}

   440 

   441 	enum

   442 		{

   443 		ENonAddressMask=3u,

   444 		EIterator=1u,

   445 		EAnchor=2u,

   446 		};

   447 

   448 	FORCE_INLINE SIterDQLink* Next() const

   449 		{ return (SIterDQLink*)(iNext & ~ENonAddressMask); }

   450 

   451 	FORCE_INLINE SIterDQLink* Prev() const

   452 		{ return (SIterDQLink*)(iPrev & ~ENonAddressMask); }

   453 

   454 	FORCE_INLINE TBool IsObject() const

   455 		{ return !(iNext & ENonAddressMask); }

   456 

   457 	FORCE_INLINE TBool IsIterator() const

   458 		{ return iNext & EIterator; }

   459 

   460 	FORCE_INLINE TBool IsAnchor() const

   461 		{ return iNext & EAnchor; }

   462 

   463 	FORCE_INLINE void SetNext(SIterDQLink* aNext)

   464 		{ iNext = (iNext & ENonAddressMask) | (TUintPtr(aNext) & ~ENonAddressMask); }

   465 

   466 	FORCE_INLINE void SetPrev(SIterDQLink* aPrev)

   467 		{ iPrev = (iPrev & ENonAddressMask) | (TUintPtr(aPrev) & ~ENonAddressMask); }

   468 

   469     /**

   470     Removes this link item from the doubly linked list.

   471     

   472     @return A pointer to this link item.

   473     */

   474 	FORCE_INLINE SIterDQLink* Deque()

   475 		{

   476 		SIterDQLink* next = Next();

   477 		SIterDQLink* prev = Prev();

   478 		next->SetPrev(prev);

   479 		prev->SetNext(next);

   480 #ifdef _DEBUG

   481 		SetNext((SIterDQLink*)4);

   482 		SetPrev((SIterDQLink*)4);

   483 #endif

   484 		return this;

   485 		}

   486 

   487 

   488     /**

   489     Inserts this link item into the list so that it precedes the specified link item.

   490     

   491     @param aL A pointer to the link item which is to follow this link item.

   492     */

   493 	FORCE_INLINE void InsertBefore(SIterDQLink* aL)

   494 		{

   495 		SIterDQLink* prev = aL->Prev();

   496 		SetNext(aL);

   497 		SetPrev(prev);

   498 		prev->SetNext(this);

   499 		aL->SetPrev(this);

   500 		}

   501 	

   502 		

   503 	/**

   504 	Inserts this link item into the list so that it follows the specified link item.

   505     

   506     @param aL A pointer to the link item which is to precede this link item.

   507     */

   508 	FORCE_INLINE void InsertAfter(SIterDQLink* aL)

   509 		{

   510 		SIterDQLink* next = aL->Next();

   511 		SetPrev(aL);

   512 		SetNext(next);

   513 		next->SetPrev(this);

   514 		aL->SetNext(this);

   515 		}

   516 	

   517 	

   518 	/**

   519 	Tests whether this is the only link item in the list.

   520 	

   521 	@return True, if this is the only link item in the list; false, otherwise.

   522     */

   523 	FORCE_INLINE TBool Alone() const

   524 		{ return (iNext==iPrev); }

   525     

   526 private:

   527 	/**

   528 	Bits 2-31 = Address of the next link item in the list.

   529 	Bit 0 = 1 for iterator, 0 for object

   530 	*/

   531 	TUintPtr iNext;

   532 

   533 	/**

   534 	Bits 2-31 = Address of the previous link item in the list.

   535 	Bit 0 = 1 for iterator, 0 for object

   536 	*/

   537 	TUintPtr iPrev;

   538 

   539 	friend struct SIterDQ;

   540 	friend struct SIterDQIterator;

   541 	};

   542 

   543 

   544 

   545 

   546 /**

   547 @internalComponent

   548 

   549 Anchor for an iterable circular doubly linked list of SIterDQLink items.

   550 

   551 @see SIterDQLink

   552 */

   553 struct SIterDQ

   554 	{

   555 	

   556 	/**

   557 	Default constructor.

   558 	*/

   559 	FORCE_INLINE SIterDQ()

   560 		{ iA.iNext = iA.iPrev = TUintPtr(&iA)|SIterDQLink::EAnchor; }

   561 		

   562 	

   563 	/**

   564 	Moves link items from the specified list onto this list, and clears the specified list

   565 	

   566 	@param aQ The source linked list. This list must not be empty.

   567 	*/	

   568 	inline SIterDQ(SIterDQ* aQ, TInt)		// move entries from aQ onto this queue and clear aQ - aQ must not be empty

   569 		{ iA.iNext=aQ->iA.iNext; iA.iPrev=aQ->iA.iPrev; First()->SetPrev(&iA); Last()->SetNext(&iA); new (aQ) SIterDQ; }

   570 		

   571 		

   572 	/**

   573 	Tests whether this doubly linked list is empty.

   574 	

   575 	@return True, if the list is empty; false, otherwise.

   576 	*/

   577 	FORCE_INLINE TBool IsEmpty() const

   578 		{ return (iA.iNext &~ SIterDQLink::ENonAddressMask) == TUintPtr(&iA); }

   579 	

   580 		

   581     /**

   582     Gets a pointer to the first item in this doubly linked list.

   583     

   584     @return A pointer to the first item.

   585     */		

   586 	FORCE_INLINE SIterDQLink* First() const

   587 		{ return iA.Next(); }

   588 	

   589 		

   590     /**

   591     Gets a pointer to the last item in this doubly linked list.

   592     

   593     @return A pointer to the last item.

   594     */		

   595 	FORCE_INLINE SIterDQLink* Last() const

   596 		{ return iA.Prev(); }

   597 	

   598 		

   599 	/**

   600 	Adds the specified link item onto the end of this doubly linked list.

   601 	

   602 	@param aL A pointer to the link item to be added.

   603 	*/

   604 	FORCE_INLINE void Add(SIterDQLink* aL)

   605 		{

   606 		aL->InsertBefore(&iA);

   607 		}

   608 	

   609 		

   610 	/**

   611 	Adds the specified link item onto the front of this doubly linked list.

   612 	

   613 	@param aL A pointer to the link item to be added.

   614 	*/

   615 	FORCE_INLINE void AddHead(SIterDQLink* aL)

   616 		{

   617 		aL->InsertAfter(&iA);

   618 		}

   619 	

   620 		

   621 	/**

   622 	Gets the first link item in the linked list.

   623 	

   624 	@return The first link item in the list; NULL, if the list is empty.

   625 	*/

   626 	inline SIterDQLink* GetFirst()

   627 		{ if (IsEmpty()) return NULL; else return First()->Deque(); }

   628 

   629 

   630 	/**

   631 	Gets the last link item in the linked list.

   632 	

   633 	@return The last link item in the list; NULL, if the list is empty.

   634 	*/

   635 	inline SIterDQLink* GetLast()

   636 		{ if (IsEmpty()) return NULL; else return Last()->Deque(); }

   637 

   638 

   639 	/**

   640 	Appends entries from the specified linked list onto this list, and clears

   641 	the specified link list anchor.

   642 	

   643 	@param aQ The source linked list.

   644 	*/

   645 	inline void MoveFrom(SIterDQ* aQ)	// append entries from aQ onto this queue and clear aQ

   646 		{ if (!aQ->IsEmpty())

   647 			{

   648 			SIterDQLink* last = Last();		// last current

   649 			SIterDQLink* fx = aQ->First();	// first extra

   650 			SIterDQLink* lx = aQ->Last();	// last extra

   651 			last->SetNext(fx);

   652 			fx->SetPrev(last);

   653 			iA.SetPrev(lx);

   654 			lx->SetNext(&iA);

   655 			new (aQ) SIterDQ;

   656 			}

   657 		}

   658 

   659 private:

   660     /**

   661     The anchor point for the doubly linked list.

   662     */

   663 	SIterDQLink	iA;

   664 	};

   665 

   666 

   667 #ifdef __VC32__

   668 #pragma warning( disable : 4127 )	// conditional expression is constant

   669 #endif

   670 

   671 /**

   672 @internalComponent

   673 

   674 Iterator for an iterable circular doubly linked list of SIterDQLink items.

   675 

   676 @see SIterDQLink

   677 @see SIterDQ

   678 */

   679 struct SIterDQIterator : public SIterDQLink

   680 	{

   681 

   682 	/**

   683 	Default constructor.

   684 

   685 	Iterator starts out not attached to any queue

   686 	*/

   687 	FORCE_INLINE SIterDQIterator()

   688 		{ iNext = iPrev = SIterDQLink::EIterator; }

   689 

   690 	/**

   691 	Destructor ensures iterator detached before destruction

   692 	*/

   693 	FORCE_INLINE ~SIterDQIterator()

   694 		{

   695 #ifdef _DEBUG

   696 		if (iNext != SIterDQLink::EIterator) { __crash(); }

   697 #endif

   698 		}

   699 

   700 	/**

   701 	Detach the iterator if it is currently attached to a queue

   702 	*/

   703 	FORCE_INLINE void Detach()

   704 		{ if (Next()) {Deque(); SetNext(0);} }

   705 

   706 	/**

   707 	Attach the iterator to a queue at the beginning.

   708 	*/

   709 	FORCE_INLINE void Attach(SIterDQ* aQ)

   710 		{

   711 #ifdef _DEBUG

   712 		if (iNext != SIterDQLink::EIterator) { __crash(); }

   713 #endif

   714 		aQ->AddHead(this);

   715 		}

   716 

   717 	/**

   718 	Step the iterator over the next object.

   719 	Return KErrNone if we stepped over an object.

   720 	Return KErrEof if we reached the end of the list.

   721 	Return KErrGeneral if we stepped over aMaxSteps other iterators.

   722 	In first case aObj is set to point to the object stepped over.

   723 	In other cases aObj is set to NULL.

   724 	*/

   725 	TInt Step(SIterDQLink*& aObj, TInt aMaxSteps=0);	// 0 means use default value

   726 

   727 	};

   728 

   729 #ifdef __VC32__

   730 #pragma warning( default : 4127 )	// conditional expression is constant

   731 #endif

   732 

   733 

   734 

   735 /******************************************************************************

   736  *

   737  * ORDERED DOUBLY-LINKED CIRCULAR LIST

   738  *

   739  ******************************************************************************/

   740 

   792 /******************************************************************************

   793  *

   794  * DELTA-ORDERED DOUBLY-LINKED CIRCULAR LIST

   795  *

   796  ******************************************************************************/

   920 /******************************************************************************

   921  *

   922  * O(1) PRIORITY ORDERED LIST

   923  *

   924  ******************************************************************************/