1 <?xml version="1.0" encoding="utf-8"?>

     2 <!-- Copyright (c) 2007-2010 Nokia Corporation and/or its subsidiary(-ies) All rights reserved. -->

     3 <!-- This component and the accompanying materials are made available under the terms of the License 

     4 "Eclipse Public License v1.0" which accompanies this distribution, 

     5 and is available at the URL "http://www.eclipse.org/legal/epl-v10.html". -->

     6 <!-- Initial Contributors:

     7     Nokia Corporation - initial contribution.

     8 Contributors: 

     9 -->

    10 <!DOCTYPE concept

    11   PUBLIC "-//OASIS//DTD DITA Concept//EN" "concept.dtd">

    12 <concept id="GUID-B1D63E7B-81EB-5F75-96C3-789E5C3E4C03" xml:lang="en"><title>How to

    13 construct and manipulate a doubly linked list</title><shortdesc>This document describes how to construct and use a doubly linked

    14 list.</shortdesc><prolog><metadata><keywords/></metadata></prolog><conbody>

    15 <p>The following code fragments show how a doubly linked list can be constructed

    16 and manipulated. The list consists of <codeph>CItem</codeph> objects. In this

    17 example, a <codeph>CItem</codeph> object can contain an item of text implemented

    18 as an <codeph>HBufC</codeph>. The <codeph>CItem</codeph> objects can form

    19 elements of a doubly linked list using the <codeph>iDlink</codeph> data member

    20 as the link object. </p>

    21 <p>The class is declared as:</p>

    22 <codeblock id="GUID-F98B0D2C-486A-59C5-B487-A0F1D7D022FD" xml:space="preserve">class CItem : public CBase

    23     {

    24 public  :

    25     static CItem* NewL(const TDesC& aText);

    26     static CItem* NewLC(const TDesC& aText); 

    27     virtual       ~CItem();

    28 public   :

    29     static const  TInt iOffset;

    30 private  :

    31     void          ConstructL(const TDesC& aText);

    32 private  :

    33     TDblQueLink  iDlink;

    34     HBufC*       iText;

    35     friend class CXy;

    36     };</codeblock>

    37 <p>The <codeph>CItem</codeph> member functions are implemented as:</p>

    38 <codeblock id="GUID-1DAC73DB-A599-5BAC-AAB5-707BA89B8382" xml:space="preserve">const TInt CItem::iOffset = _FOFF(CItem,iDlink);</codeblock>

    39 <codeblock id="GUID-6FEA34D4-0937-56E3-ACA5-3912E1595511" xml:space="preserve">CItem* CItem::NewLC(const TDesC&amp; aText)

    40     {

    41     CItem* self = new (ELeave) CItem;

    42     CleanupStack::PushL(self);

    43     self->ConstructL(aText);

    44     return self;

    45     }</codeblock>

    46 <codeblock id="GUID-75110620-3EDC-5B4D-84EB-C4D6C78BF2F9" xml:space="preserve">CItem* CItem::NewL(const TDesC&amp; aText)

    47     {

    48     CItem* self = CItem::NewLC(aText);

    49     CleanupStack::Pop();

    50     return self;

    51     }</codeblock>

    52 <codeblock id="GUID-8EABC406-6C95-5139-9A97-AB467D526019" xml:space="preserve">void CItem::ConstructL(const TDesC&amp; aText)

    53     {

    54     iText    = aText.AllocL();

    55     }</codeblock>

    56 <codeblock id="GUID-235AC477-3C7E-52E2-B85B-57C404C8BC08" xml:space="preserve">CItem::~CItem()

    57     {

    58     delete (iText);

    59     }</codeblock>

    60 <p>As part of its construction process, a <codeph>CItem</codeph> constructs

    61 an <codeph>HBufC</codeph> of the correct length and copies the content of

    62 the descriptor parameter into it.</p>

    63 <p>A <codeph>CXy</codeph> object maintains the list by:</p>

    64 <ul>

    65 <li id="GUID-048EFEF6-B2EC-5333-A835-BC735C334220"><p> creating <codeph>CItem</codeph> objects

    66 and adding them into the list</p> </li>

    67 <li id="GUID-310AB703-85C5-5DFC-8AB6-2A0938095134"><p>removing <codeph>CItem</codeph> objects

    68 from the list and then destroying them</p> </li>

    69 </ul>

    70 <p>The class is declared as:</p>

    71 <codeblock id="GUID-F5CF044D-650A-5446-9713-BE84362FD793" xml:space="preserve">class CXy : public CBase

    72     {

    73 public :

    74     CXy();

    75     virtual ~CXy();

    76     void    DoItems();

    77     TBool   AddItem(const TDesC& anItem,TItemPos aPos);

    78 private :

    79     TDblQue<CItem>     iHdr; 

    80     TDblQueIter<CItem> iIter;

    81     };</codeblock>

    82 <p>Here, the list header, <codeph>iHdr</codeph>, and the iterator, <codeph>iIter</codeph>,

    83 are declared as data members of the class and are constructed when the <codeph>CXy</codeph> object

    84 is constructed. A C++ constructor must be supplied so that <codeph>iIter</codeph> can

    85 be properly constructed. (<codeph>TDblQueIter</codeph> has no default constructor).</p>

    86 <p>Specifically:</p>

    87 <ul>

    88 <li id="GUID-36B75BBC-B6EA-5717-9E88-8C1FFB4F9119"><p><codeph>AddItem()</codeph> constructs

    89 a new <codeph>CItem</codeph> and adds it to the list, either after the current

    90 item or at the end of the list.</p> </li>

    91 <li id="GUID-B85DEE50-218E-5CC9-B60D-D6EA2176643F"><p><codeph>DoItems()</codeph> scans

    92 through the list, removing and destroying each element from the list.</p> </li>

    93 </ul>

    94 <p>The <codeph>CXy</codeph> member functions are implemented as:</p>

    95 <codeblock id="GUID-910891C0-DBEF-592F-8CA3-FC354DE16B3E" xml:space="preserve">CXy::CXy()

    96     : iHdr(CItem::iOffset),iIter(iHdr) //construct header & iterator

    97     {}</codeblock>

    98 <codeblock id="GUID-C471B1FC-05A6-56AD-B3D6-C65FB045B864" xml:space="preserve">CXy::~CXy()

    99     {

   100     CItem*  anyitem;

   101     

   102     iIter.SetToFirst();

   103     while ((anyitem = iIter++) != NULL)

   104         {

   105         anyitem->iDlink.Deque();

   106         delete anyitem;

   107         };

   108     }</codeblock>

   109 <p>Before destroying a <codeph>CXy</codeph> object, the list is destroyed.

   110 This is achieved using the iterator. The iterator pointer is set to point

   111 to each element in turn, removing that element from the list before destroying

   112 it.</p>

   113 <p>Once the iterator has reached the end of the list, the operator<codeph>++</codeph> returns <codeph>NULL</codeph>.</p>

   114 <p>The destruction process is safe if the list is empty; the statement <codeph>iter.SetToFirst()</codeph> is

   115 harmless, the operator<codeph>++</codeph> returns <codeph>NULL</codeph> and

   116 execution of the body of the <codeph>while</codeph> loop never happens.</p>

   117 <codeblock id="GUID-8E2FD32B-B8FF-5F37-9C66-20695B296079" xml:space="preserve">TBool CXy::AddItem(const TDesC&amp; aText,TItemPos aPos)

   118     {

   119     CItem* newitem;

   120     

   121     TRAPD(leavecode,newitem = CItem::NewL(aText));

   122     if (leavecode != KErrNone)

   123         return EFalse;              // Cannot create a CItem</codeblock>

   124 <codeblock id="GUID-6A38CF3D-9547-562D-BB4C-F53938943D15" xml:space="preserve">    switch (aPos)

   125         {

   126     case EAtEnd:

   127         iHdr.AddLast(*newitem);     // Add at back of list

   128         return ETrue;

   129 

   130     case EAfterCurrent:

   131         CItem* currentitem = iIter; 

   132         if (currentitem)

   133             {

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

   135             iIter.Set(*newitem);

   136             }

   137         else

   138             {

   139             iHdr.AddFirst(*newitem);

   140             iIter.SetToFirst();    

   141             }

   142         return ETrue;

   143         }

   144                 

   145     return EFalse;

   146         }</codeblock>

   147 <p>This member function creates a new <codeph>CItem</codeph> and then, depending

   148 on the value of <codeph>aPos</codeph>, either adds it at the back of the list

   149 or after the current element. <codeph>TItemPos</codeph> is just an enumeration

   150 taking the enumerators <codeph>EAtEnd</codeph> and <codeph>EAfterCurrent</codeph>.</p>

   151 <p>The statement:</p>

   152 <codeblock id="GUID-FBCE5C8F-D42A-50E6-BA1E-A6B2887AF0C1" xml:space="preserve">newitem-&gt;iDlink.Enque(&amp;currentitem-&gt;iDlink);</codeblock>

   153 <p>inserts the newly created <codeph>CItem</codeph> with pointer <codeph>newitem</codeph>, <i>after</i> the

   154 existing item with pointer <codeph>currentitem</codeph>.</p>

   155 <p>Note also that the statement:</p>

   156 <codeblock id="GUID-F875FA76-2768-5713-8462-44610B17F35A" xml:space="preserve">CItem* currentitem = iIter; 

   157 </codeblock>

   158 <p>implicitly uses the conversion operator <codeph>T*()</codeph> where, in

   159 general, <codeph>T</codeph> is the class forming elements of the list. In

   160 this specific example, the conversion operator returns a pointer to the current

   161 element, of type <codeph>CItem</codeph>, in the list. Immediately after construction

   162 of the iterator <codeph>iIter</codeph>, the value of <codeph>currentitem</codeph> is <codeph>NULL</codeph>.</p>

   163 <codeblock id="GUID-96C01CEC-29F5-537B-9E44-531A313D8796" xml:space="preserve">void CXy::DoItems()

   164     {

   165     CItem* currentitem;

   166 

   167     iIter.SetToFirst();

   168 

   169     while((currentitem = iIter++) != NULL)

   170         {

   171         // do something with the text;

   172         currentitem->iDlink.Deque();

   173         delete currentitem;

   174         };

   175     }</codeblock>

   176 <p>The <codeph>DoItems()</codeph> member function iterates through the whole

   177 list, removing each <codeph>CItem</codeph> object in turn before destroying

   178 it. This member function could be modified to include extra functionality

   179 before the removal and destruction of the <codeph>CItem</codeph> element.</p>

   180 <p>If the list is empty on entry to this function, the <codeph>iter.SetToFirst()</codeph> statement

   181 is safe, <codeph>currentitem</codeph> is <codeph>NULL</codeph> on the first

   182 execution of the <codeph>while</codeph> condition and the body of the <codeph>while</codeph> loop

   183 is never executed.</p>

   184 <p>Executing the code:</p>

   185 <codeblock id="GUID-081282AE-93D7-59FB-93A7-93D7E1F2080C" xml:space="preserve">    {

   186     _LIT(KTxtOne,"one");

   187     _LIT(KTxtTwo,"two");

   188     _LIT(KTxtThree",three");

   189     _LIT(KTxtFour,"four");

   190     _LIT(KTxtFive,"five");

   191     _LIT(KTxtSix,"six");

   192 

   193     CXy* items;

   194 

   195     items = new CXy;

   196 

   197     items->AddItem(KTxtone,EAfterCurrent);

   198     items->AddItem(KTxttwo,EAtEnd);

   199     items->AddItem(KTxtthree,EAfterCurrent);

   200     items->AddItem(KTxtfour,EAtEnd);

   201     items->AddItem(KTxtfive,EAfterCurrent);

   202     items->AddItem(KTxtsix,EAtEnd);

   203     ...

   204 </codeblock>

   205 <p>results in the construction of a doubly linked list of <codeph>CItem</codeph> objects

   206 each containing a pointer to an <codeph>HBufC</codeph> descriptor containing

   207 the text as shown:</p>

   208 <fig id="GUID-10DC05B0-64A2-52D0-ABC6-ACD231F402C4">

   209 <title/>

   210 <image href="GUID-03AC137D-173A-558C-A2F3-9522870AC43C_d0e217986_href.png" placement="inline"/>

   211 </fig>

   212 <p>The following code destroys the list elements and the <codeph>CXy</codeph> object

   213 containing the list header and iterator:</p>

   214 <codeblock id="GUID-37EF4182-834F-51BF-9250-61B479BFD3D1" xml:space="preserve">    ...

   215     items->DoItems();

   216     delete items;

   217     }</codeblock>

   218 <p>There are a number of other possible ways to proceed, depending on the

   219 precise needs of an application. In the previous example, the list header

   220 and the iterator are declared as members of the class.</p>

   221 <p>Some situations may demand that a list be created, used and destroyed within

   222 the scope of a member function. Because list headers and iterators are “<codeph>T</codeph> ”

   223 types, they can be declared on the stack; for example:</p>

   224 <codeblock id="GUID-E29EDC0D-C7DE-5E35-B39F-DA63110DF630" xml:space="preserve">void CXy::SomeFunction();

   225     {

   226     TDblQue<CItem>     iHdr(CItem::iOffset); 

   227     TDblQueIter<CItem> iIter(iHdr);

   228 

   229     // the body of the function

   230     //

   231 

   232     }

   233 </codeblock>

   234 <p>The list header and the iterator go out of scope at the end of the function

   235 and are destroyed. Unless the list elements themselves are “<codeph>T</codeph> ”

   236 types and exist on the stack, make sure that they are explicitly destroyed

   237 before the function terminates.</p>

   238 </conbody></concept>