|
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& 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& 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& 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& 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->iDlink.Enque(&currentitem->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_d0e189390_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> |