How to -construct and manipulate a doubly linked list

diff -r 51a74ef9ed63 -r ae94777fff8f Symbian3/SDK/Source/GUID-B1D63E7B-81EB-5F75-96C3-789E5C3E4C03.dita --- a/Symbian3/SDK/Source/GUID-B1D63E7B-81EB-5F75-96C3-789E5C3E4C03.dita Wed Mar 31 11:11:55 2010 +0100 +++ b/Symbian3/SDK/Source/GUID-B1D63E7B-81EB-5F75-96C3-789E5C3E4C03.dita Fri Jun 11 12:39:03 2010 +0100 @@ -1,238 +1,238 @@ - - - - - -How to -construct and manipulate a doubly linked listThis document describes how to construct and use a doubly linked -list. -

The following code fragments show how a doubly linked list can be constructed -and manipulated. The list consists of CItem objects. In this -example, a CItem object can contain an item of text implemented -as an HBufC. The CItem objects can form -elements of a doubly linked list using the iDlink data member -as the link object.

The class is declared as:

-class CItem : public CBase - { -public : - static CItem* NewL(const TDesC& aText); - static CItem* NewLC(const TDesC& aText); - virtual ~CItem(); -public : - static const TInt iOffset; -private : - void ConstructL(const TDesC& aText); -private : - TDblQueLink iDlink; - HBufC* iText; - friend class CXy; - }; -

The CItem member functions are implemented as:

-const TInt CItem::iOffset = _FOFF(CItem,iDlink); -CItem* CItem::NewLC(const TDesC& aText) - { - CItem* self = new (ELeave) CItem; - CleanupStack::PushL(self); - self->ConstructL(aText); - return self; - } -CItem* CItem::NewL(const TDesC& aText) - { - CItem* self = CItem::NewLC(aText); - CleanupStack::Pop(); - return self; - } -void CItem::ConstructL(const TDesC& aText) - { - iText = aText.AllocL(); - } -CItem::~CItem() - { - delete (iText); - } -

As part of its construction process, a CItem constructs -an HBufC of the correct length and copies the content of -the descriptor parameter into it.

A CXy object maintains the list by:

creating CItem objects -and adding them into the list
removing CItem objects -from the list and then destroying them

The class is declared as:

-class CXy : public CBase - { -public : - CXy(); - virtual ~CXy(); - void DoItems(); - TBool AddItem(const TDesC& anItem,TItemPos aPos); -private : - TDblQue<CItem> iHdr; - TDblQueIter<CItem> iIter; - }; -

Here, the list header, iHdr, and the iterator, iIter, -are declared as data members of the class and are constructed when the CXy object -is constructed. A C++ constructor must be supplied so that iIter can -be properly constructed. (TDblQueIter has no default constructor).

Specifically:

AddItem() constructs -a new CItem and adds it to the list, either after the current -item or at the end of the list.
DoItems() scans -through the list, removing and destroying each element from the list.

The CXy member functions are implemented as:

-CXy::CXy() - : iHdr(CItem::iOffset),iIter(iHdr) //construct header & iterator - {} -CXy::~CXy() - { - CItem* anyitem; - - iIter.SetToFirst(); - while ((anyitem = iIter++) != NULL) - { - anyitem->iDlink.Deque(); - delete anyitem; - }; - } -

Before destroying a CXy object, the list is destroyed. -This is achieved using the iterator. The iterator pointer is set to point -to each element in turn, removing that element from the list before destroying -it.

Once the iterator has reached the end of the list, the operator++ returns NULL.

The destruction process is safe if the list is empty; the statement iter.SetToFirst() is -harmless, the operator++ returns NULL and -execution of the body of the while loop never happens.

-TBool CXy::AddItem(const TDesC& aText,TItemPos aPos) - { - CItem* newitem; - - TRAPD(leavecode,newitem = CItem::NewL(aText)); - if (leavecode != KErrNone) - return EFalse; // Cannot create a CItem - switch (aPos) - { - case EAtEnd: - iHdr.AddLast(*newitem); // Add at back of list - return ETrue; - - case EAfterCurrent: - CItem* currentitem = iIter; - if (currentitem) - { - newitem->iDlink.Enque(&currentitem->iDlink); - iIter.Set(*newitem); - } - else - { - iHdr.AddFirst(*newitem); - iIter.SetToFirst(); - } - return ETrue; - } - - return EFalse; - } -

This member function creates a new CItem and then, depending -on the value of aPos, either adds it at the back of the list -or after the current element. TItemPos is just an enumeration -taking the enumerators EAtEnd and EAfterCurrent.

The statement:

-newitem->iDlink.Enque(&currentitem->iDlink); -

inserts the newly created CItem with pointer newitem, after the -existing item with pointer currentitem.

Note also that the statement:

-CItem* currentitem = iIter; - -

implicitly uses the conversion operator T*() where, in -general, T is the class forming elements of the list. In -this specific example, the conversion operator returns a pointer to the current -element, of type CItem, in the list. Immediately after construction -of the iterator iIter, the value of currentitem is NULL.

-void CXy::DoItems() - { - CItem* currentitem; - - iIter.SetToFirst(); - - while((currentitem = iIter++) != NULL) - { - // do something with the text; - currentitem->iDlink.Deque(); - delete currentitem; - }; - } -

The DoItems() member function iterates through the whole -list, removing each CItem object in turn before destroying -it. This member function could be modified to include extra functionality -before the removal and destruction of the CItem element.

If the list is empty on entry to this function, the iter.SetToFirst() statement -is safe, currentitem is NULL on the first -execution of the while condition and the body of the while loop -is never executed.

Executing the code:

- { - _LIT(KTxtOne,"one"); - _LIT(KTxtTwo,"two"); - _LIT(KTxtThree",three"); - _LIT(KTxtFour,"four"); - _LIT(KTxtFive,"five"); - _LIT(KTxtSix,"six"); - - CXy* items; - - items = new CXy; - - items->AddItem(KTxtone,EAfterCurrent); - items->AddItem(KTxttwo,EAtEnd); - items->AddItem(KTxtthree,EAfterCurrent); - items->AddItem(KTxtfour,EAtEnd); - items->AddItem(KTxtfive,EAfterCurrent); - items->AddItem(KTxtsix,EAtEnd); - ... - -

results in the construction of a doubly linked list of CItem objects -each containing a pointer to an HBufC descriptor containing -the text as shown:

- - -<image href="GUID-03AC137D-173A-558C-A2F3-9522870AC43C_d0e217986_href.png" placement="inline"/> -</fig> -The following code destroys the list elements and the <codeph>CXy</codeph> object -containing the list header and iterator: -<codeblock id="GUID-37EF4182-834F-51BF-9250-61B479BFD3D1" xml:space="preserve"> ... - items->DoItems(); - delete items; - }</codeblock> -There are a number of other possible ways to proceed, depending on the -precise needs of an application. In the previous example, the list header -and the iterator are declared as members of the class. -Some situations may demand that a list be created, used and destroyed within -the scope of a member function. Because list headers and iterators are “<codeph>T</codeph> ” -types, they can be declared on the stack; for example: -<codeblock id="GUID-E29EDC0D-C7DE-5E35-B39F-DA63110DF630" xml:space="preserve">void CXy::SomeFunction(); - { - TDblQue<CItem> iHdr(CItem::iOffset); - TDblQueIter<CItem> iIter(iHdr); - - // the body of the function - // - - } -</codeblock> -The list header and the iterator go out of scope at the end of the function -and are destroyed. Unless the list elements themselves are “<codeph>T</codeph> ” -types and exist on the stack, make sure that they are explicitly destroyed -before the function terminates. +<?xml version="1.0" encoding="utf-8"?> + + + +<!DOCTYPE concept + PUBLIC "-//OASIS//DTD DITA Concept//EN" "concept.dtd"> +<concept id="GUID-B1D63E7B-81EB-5F75-96C3-789E5C3E4C03" xml:lang="en"><title>How to +construct and manipulate a doubly linked listThis document describes how to construct and use a doubly linked +list. +

The following code fragments show how a doubly linked list can be constructed +and manipulated. The list consists of CItem objects. In this +example, a CItem object can contain an item of text implemented +as an HBufC. The CItem objects can form +elements of a doubly linked list using the iDlink data member +as the link object.

The class is declared as:

+class CItem : public CBase + { +public : + static CItem* NewL(const TDesC& aText); + static CItem* NewLC(const TDesC& aText); + virtual ~CItem(); +public : + static const TInt iOffset; +private : + void ConstructL(const TDesC& aText); +private : + TDblQueLink iDlink; + HBufC* iText; + friend class CXy; + }; +

The CItem member functions are implemented as:

+const TInt CItem::iOffset = _FOFF(CItem,iDlink); +CItem* CItem::NewLC(const TDesC& aText) + { + CItem* self = new (ELeave) CItem; + CleanupStack::PushL(self); + self->ConstructL(aText); + return self; + } +CItem* CItem::NewL(const TDesC& aText) + { + CItem* self = CItem::NewLC(aText); + CleanupStack::Pop(); + return self; + } +void CItem::ConstructL(const TDesC& aText) + { + iText = aText.AllocL(); + } +CItem::~CItem() + { + delete (iText); + } +

As part of its construction process, a CItem constructs +an HBufC of the correct length and copies the content of +the descriptor parameter into it.

A CXy object maintains the list by:

creating CItem objects +and adding them into the list
removing CItem objects +from the list and then destroying them

The class is declared as:

+class CXy : public CBase + { +public : + CXy(); + virtual ~CXy(); + void DoItems(); + TBool AddItem(const TDesC& anItem,TItemPos aPos); +private : + TDblQue<CItem> iHdr; + TDblQueIter<CItem> iIter; + }; +

Here, the list header, iHdr, and the iterator, iIter, +are declared as data members of the class and are constructed when the CXy object +is constructed. A C++ constructor must be supplied so that iIter can +be properly constructed. (TDblQueIter has no default constructor).

Specifically:

AddItem() constructs +a new CItem and adds it to the list, either after the current +item or at the end of the list.
DoItems() scans +through the list, removing and destroying each element from the list.

The CXy member functions are implemented as:

+CXy::CXy() + : iHdr(CItem::iOffset),iIter(iHdr) //construct header & iterator + {} +CXy::~CXy() + { + CItem* anyitem; + + iIter.SetToFirst(); + while ((anyitem = iIter++) != NULL) + { + anyitem->iDlink.Deque(); + delete anyitem; + }; + } +

Before destroying a CXy object, the list is destroyed. +This is achieved using the iterator. The iterator pointer is set to point +to each element in turn, removing that element from the list before destroying +it.

Once the iterator has reached the end of the list, the operator++ returns NULL.

The destruction process is safe if the list is empty; the statement iter.SetToFirst() is +harmless, the operator++ returns NULL and +execution of the body of the while loop never happens.

+TBool CXy::AddItem(const TDesC& aText,TItemPos aPos) + { + CItem* newitem; + + TRAPD(leavecode,newitem = CItem::NewL(aText)); + if (leavecode != KErrNone) + return EFalse; // Cannot create a CItem + switch (aPos) + { + case EAtEnd: + iHdr.AddLast(*newitem); // Add at back of list + return ETrue; + + case EAfterCurrent: + CItem* currentitem = iIter; + if (currentitem) + { + newitem->iDlink.Enque(&currentitem->iDlink); + iIter.Set(*newitem); + } + else + { + iHdr.AddFirst(*newitem); + iIter.SetToFirst(); + } + return ETrue; + } + + return EFalse; + } +

This member function creates a new CItem and then, depending +on the value of aPos, either adds it at the back of the list +or after the current element. TItemPos is just an enumeration +taking the enumerators EAtEnd and EAfterCurrent.

The statement:

+newitem->iDlink.Enque(&currentitem->iDlink); +

inserts the newly created CItem with pointer newitem, after the +existing item with pointer currentitem.

Note also that the statement:

+CItem* currentitem = iIter; + +

implicitly uses the conversion operator T*() where, in +general, T is the class forming elements of the list. In +this specific example, the conversion operator returns a pointer to the current +element, of type CItem, in the list. Immediately after construction +of the iterator iIter, the value of currentitem is NULL.

+void CXy::DoItems() + { + CItem* currentitem; + + iIter.SetToFirst(); + + while((currentitem = iIter++) != NULL) + { + // do something with the text; + currentitem->iDlink.Deque(); + delete currentitem; + }; + } +

The DoItems() member function iterates through the whole +list, removing each CItem object in turn before destroying +it. This member function could be modified to include extra functionality +before the removal and destruction of the CItem element.

If the list is empty on entry to this function, the iter.SetToFirst() statement +is safe, currentitem is NULL on the first +execution of the while condition and the body of the while loop +is never executed.

Executing the code:

+ { + _LIT(KTxtOne,"one"); + _LIT(KTxtTwo,"two"); + _LIT(KTxtThree",three"); + _LIT(KTxtFour,"four"); + _LIT(KTxtFive,"five"); + _LIT(KTxtSix,"six"); + + CXy* items; + + items = new CXy; + + items->AddItem(KTxtone,EAfterCurrent); + items->AddItem(KTxttwo,EAtEnd); + items->AddItem(KTxtthree,EAfterCurrent); + items->AddItem(KTxtfour,EAtEnd); + items->AddItem(KTxtfive,EAfterCurrent); + items->AddItem(KTxtsix,EAtEnd); + ... + +

results in the construction of a doubly linked list of CItem objects +each containing a pointer to an HBufC descriptor containing +the text as shown:

+ + +<image href="GUID-03AC137D-173A-558C-A2F3-9522870AC43C_d0e214249_href.png" placement="inline"/> +</fig> +The following code destroys the list elements and the <codeph>CXy</codeph> object +containing the list header and iterator: +<codeblock id="GUID-37EF4182-834F-51BF-9250-61B479BFD3D1" xml:space="preserve"> ... + items->DoItems(); + delete items; + }</codeblock> +There are a number of other possible ways to proceed, depending on the +precise needs of an application. In the previous example, the list header +and the iterator are declared as members of the class. +Some situations may demand that a list be created, used and destroyed within +the scope of a member function. Because list headers and iterators are “<codeph>T</codeph> ” +types, they can be declared on the stack; for example: +<codeblock id="GUID-E29EDC0D-C7DE-5E35-B39F-DA63110DF630" xml:space="preserve">void CXy::SomeFunction(); + { + TDblQue<CItem> iHdr(CItem::iOffset); + TDblQueIter<CItem> iIter(iHdr); + + // the body of the function + // + + } +</codeblock> +The list header and the iterator go out of scope at the end of the function +and are destroyed. Unless the list elements themselves are “<codeph>T</codeph> ” +types and exist on the stack, make sure that they are explicitly destroyed +before the function terminates. </conbody></concept> \ No newline at end of file