Xbase64 4.0.1
C++ Library for handling Xbase (DBF) format type files
xblnklstord.h
Go to the documentation of this file.
1/* xblnklstord.h
2
3XBase64 Software Library
4
5Copyright (c) 1997,2003,2014,2019,2022 Gary A Kunkel
6
7The xb64 software library is covered under the terms of the GPL Version 3, 2007 license.
8
9Email Contact:
10
11 XDB-devel@lists.sourceforge.net
12 XDB-users@lists.sourceforge.net
13
14*/
15
16
17// Ordered link list
18
19
20
21#ifndef __XB_XBLNKLSTORD_H__
22#define __XB_XBLNKLSTORD_H__
23
24#ifdef XB_LINKLIST_SUPPORT
25
26
27namespace xb{
28
29
30template<class xbNodeType>
31class XBDLLEXPORT xbLinkListOrd {
32 public:
33 xbLinkListOrd();
34 ~xbLinkListOrd();
35
36 void Clear();
37 xbLinkListNode<xbNodeType> *GetHeadNode() const;
38 xbLinkListNode<xbNodeType> *GetEndNode() const;
39 xbLinkListNode<xbNodeType> *GetNodeForKey( const xbString &sKey ) const;
40
41 xbInt16 GetDataForKey ( const xbNodeType &ntKey, xbString &sData );
42
43 xbBool GetDupKeys ();
44
45 xbUInt32 GetNodeCnt () const;
46 xbUInt32 GetNodeCnt ( const xbString &sNodeKey ) const;
47 xbInt16 InsertKey ( const xbNodeType &ntKey );
48 xbInt16 InsertKey ( const xbNodeType &ntKey, const xbString &sData );
49 xbInt16 InsertKey ( const xbNodeType &ntKey, xbUInt32 ulData );
50
51 xbBool KeyExists ( const xbNodeType &ntKey ) const;
52 xbInt16 RemoveKey ( const xbNodeType &ntKey );
53 xbInt16 RemoveFromEnd ( xbNodeType &ntKey );
54 xbInt16 RemoveFromFront( xbNodeType &ntKey );
55 xbInt16 RemoveFromFront();
56 void SetDupKeys ( xbBool bAllowDupKeys );
57 xbInt16 UpdateForKey ( const xbNodeType &ntKey, const xbString &sData );
58
59
60 private:
61 xbUInt32 ulNodeCnt;
62 xbBool bAllowDupKeys;
63 xbLinkListNode<xbNodeType> *llStartPtr;
64 xbLinkListNode<xbNodeType> *llEndPtr;
65
66};
67
68
69template<class xbNodeType>
70xbLinkListOrd<xbNodeType>::xbLinkListOrd(){
71 bAllowDupKeys = xbTrue; // default setting - allow duplicate keys
72 ulNodeCnt = 0;
73 llStartPtr = NULL;
74 llEndPtr = NULL;
75}
76
77template<class xbNodeType>
78xbLinkListOrd<xbNodeType>::~xbLinkListOrd(){
79 Clear();
80}
81
82template<class xbNodeType>
83void xbLinkListOrd<xbNodeType>::Clear(){
84 xbLinkListNode<xbNodeType> *cPtr = llStartPtr, *tPtr;
85 for( xbUInt32 i = 0; i < ulNodeCnt; i++ ){
86 tPtr = cPtr;
87 cPtr = cPtr->GetNextNode();
88
89 // next line might cause seg faults
90 // delete tPtr->GetData();
91
92 delete tPtr;
93 }
94 ulNodeCnt = 0;
95 llStartPtr = NULL;
96 llEndPtr = NULL;
97}
98
99template<class xbNodeType>
100xbLinkListNode<xbNodeType> * xbLinkListOrd<xbNodeType>::GetHeadNode() const{
101 return llStartPtr;
102}
103
104template<class xbNodeType>
105xbLinkListNode<xbNodeType> * xbLinkListOrd<xbNodeType>::GetEndNode() const{
106 return llEndPtr;
107}
108
109template<class xbNodeType>
110xbUInt32 xbLinkListOrd<xbNodeType>::GetNodeCnt() const{
111 return ulNodeCnt;
112}
113
114template<class xbNodeType>
115xbUInt32 xbLinkListOrd<xbNodeType>::GetNodeCnt( const xbString &sNodeKey ) const{
116
117 // won't work if nodekey is not a string
118 xbLinkListNode<xbNodeType> *currPtr = llStartPtr;
119 // skip to sNodeKey
120 while( currPtr && ( sNodeKey > currPtr->GetKey())) {
121 currPtr = currPtr->GetNextNode();
122 }
123 // count entries for sNodeKey
124 xbInt16 iKeyCnt = 0;
125 while( currPtr && ( sNodeKey == currPtr->GetKey())) {
126 iKeyCnt++;
127 currPtr = currPtr->GetNextNode();
128 }
129 return iKeyCnt;
130}
131
132
133template<class xbNodeType>
134xbInt16 xbLinkListOrd<xbNodeType>::InsertKey( const xbNodeType &ntKey ){
135 xbString s;
136 return InsertKey( ntKey, s );
137}
138
139
140
141
142template<class xbNodeType>
143xbInt16 xbLinkListOrd<xbNodeType>::InsertKey( const xbNodeType &ntKey, xbUInt32 ul ){
144
145 xbString s;
146 s.Sprintf( "%ld", ul );
147 return InsertKey( ntKey, s );
148}
149
150
151template<class xbNodeType>
152xbInt16 xbLinkListOrd<xbNodeType>::InsertKey( const xbNodeType &ntKey, const xbString &sData ){
153
154 xbLinkListNode<xbNodeType> *p = new xbLinkListNode<xbNodeType>( ntKey, sData );
155 if( p == 0 )
156 return XB_NO_MEMORY;
157
158 if( ulNodeCnt > 0 ){
159 xbLinkListNode<xbNodeType> *currPtr = llStartPtr;
160 xbLinkListNode<xbNodeType> *prevPtr = NULL;
161
162 // find location in the chain
163 while( currPtr && ntKey > currPtr->GetKey() ){
164 prevPtr = currPtr;
165 currPtr = currPtr->GetNextNode();
166 }
167 if( currPtr && ntKey == currPtr->GetKey() && bAllowDupKeys == 0 ){
168 delete p;
169 return XB_KEY_NOT_UNIQUE;
170 }
171
172 if( currPtr == NULL ){
173 // std::cout << "at the end of the chain\n";
174 llEndPtr = p;
175 prevPtr->SetNextNode( p );
176 p->SetPrevNode( prevPtr );
177
178 } else if( currPtr->GetPrevNode() == NULL ){
179 // std::cout << "at the beginning of the chain\n";
180 p->SetNextNode( llStartPtr );
181 llStartPtr->SetPrevNode( p );
182 llStartPtr = p;
183
184 } else {
185 // std::cout << "in the middle of the chain\n";
186 p->SetNextNode( currPtr );
187 p->SetPrevNode( currPtr->GetPrevNode());
188 currPtr->SetPrevNode( p );
189 prevPtr->SetNextNode( p );
190 }
191 } else {
192 // std::cout << "first addition to the chain\n";
193 llStartPtr = p;
194 llEndPtr = p;
195 }
196 ulNodeCnt++;
197 return XB_NO_ERROR;
198}
199
200template<class xbNodeType>
201xbInt16 xbLinkListOrd<xbNodeType>::RemoveKey( const xbNodeType &ntKey ){
202 // Remove the first instance of ntKey from the node chain
203 xbLinkListNode<xbNodeType> *currPtr = llStartPtr;
204 xbLinkListNode<xbNodeType> *prevPtr = NULL;
205
206 while( currPtr && ntKey > currPtr->GetKey() ){
207 prevPtr = currPtr;
208 currPtr = currPtr->GetNextNode();
209 }
210
211 if( currPtr && ntKey == currPtr->GetKey()){
212// ntKey = currPtr->GetKey();
213 if( prevPtr == NULL ){ // this is the first node
214 llStartPtr = currPtr->GetNextNode();
215 // next line fails
216 if( llStartPtr ){
217 llStartPtr->SetPrevNode( NULL );
218 }
219 delete currPtr;
220 ulNodeCnt--;
221 return XB_NO_ERROR;
222 } else if( currPtr->GetNextNode() == NULL ){ // this is the last node
223 llEndPtr = prevPtr;
224 prevPtr->SetNextNode( NULL );
225 delete currPtr;
226 ulNodeCnt--;
227 return XB_NO_ERROR;
228 } else {
229
230 prevPtr->SetNextNode( currPtr->GetNextNode());
231 currPtr->GetNextNode()->SetPrevNode( prevPtr );
232 delete currPtr;
233 ulNodeCnt--;
234 return XB_NO_ERROR;
235 }
236 } else {
237 return XB_NOT_FOUND;
238 }
239}
240
241template<class xbNodeType>
242xbInt16 xbLinkListOrd<xbNodeType>::RemoveFromFront( xbNodeType &ntKey ){
243
244 if( ulNodeCnt <= 0 )
245 return XB_INVALID_NODELINK;
246 xbLinkListNode<xbNodeType> *p = llStartPtr;
247 llStartPtr = p->GetNextNode();
248 if( llStartPtr )
249 llStartPtr->SetPrevNode( NULL );
250 ntKey = p->GetKey();
251 delete p;
252 ulNodeCnt--;
253 return XB_NO_ERROR;
254}
255
256template<class xbNodeType>
257xbInt16 xbLinkListOrd<xbNodeType>::RemoveFromFront(){
258
259 if( ulNodeCnt <= 0 )
260 return XB_INVALID_NODELINK;
261 xbLinkListNode<xbNodeType> *p = llStartPtr;
262 llStartPtr = p->GetNextNode();
263 if( llStartPtr )
264 llStartPtr->SetPrevNode( NULL );
265
266 if( p->GetKey())
267 delete p->GetKey();
268
269 delete p;
270 ulNodeCnt--;
271
272 return XB_NO_ERROR;
273}
274
275
276template<class xbNodeType>
277xbInt16 xbLinkListOrd<xbNodeType>::RemoveFromEnd( xbNodeType &ntKey ){
278
279 if( ulNodeCnt <= 0 )
280 return XB_INVALID_NODELINK;
281 xbLinkListNode<xbNodeType> *p = llEndPtr;
282 llEndPtr = p->GetPrevNode();
283 llEndPtr->SetNextNode( NULL );
284 ntKey = p->GetKey();
285 delete p;
286 ulNodeCnt--;
287 return XB_NO_ERROR;
288}
289
290template<class xbNodeType>
291xbBool xbLinkListOrd<xbNodeType>::GetDupKeys(){
292 return bAllowDupKeys;
293}
294
295template<class xbNodeType>
296void xbLinkListOrd<xbNodeType>::SetDupKeys( xbBool bAllowDupKeys ){
297 this->bAllowDupKeys = bAllowDupKeys;
298}
299
300
301template<class xbNodeType>
302xbBool xbLinkListOrd<xbNodeType>::KeyExists( const xbNodeType &ntKey ) const {
303
304 xbLinkListNode<xbNodeType> *currPtr = llStartPtr;
305 while( currPtr && ntKey > currPtr->GetKey() ){
306 currPtr = currPtr->GetNextNode();
307 }
308 if( currPtr && ntKey == currPtr->GetKey()){
309 return xbTrue;
310 } else {
311 return xbFalse;
312 }
313}
314
315
316template<class xbNodeType>
317xbInt16 xbLinkListOrd<xbNodeType>::GetDataForKey( const xbNodeType &ntKey, xbString &sData ){
318
319 xbLinkListNode<xbNodeType> *currPtr = llStartPtr;
320 while( currPtr && ntKey > currPtr->GetKey() ){
321 currPtr = currPtr->GetNextNode();
322 }
323
324 if( currPtr && ntKey == currPtr->GetKey()){
325 sData = currPtr->GetData();
326 return XB_NO_ERROR;
327 } else {
328 return XB_NOT_FOUND;
329 }
330}
331
332
333template<class xbNodeType>
334xbInt16 xbLinkListOrd<xbNodeType>::UpdateForKey( const xbNodeType &ntKey, const xbString &sData ){
335
336 if( ulNodeCnt == 0 )
337 return InsertKey( ntKey, sData );
338 xbLinkListNode<xbNodeType> * currPtr = llStartPtr;
339 xbLinkListNode<xbNodeType> * prevPtr = NULL;
340 while( currPtr && ntKey > currPtr->GetKey() ) {
341 prevPtr = currPtr;
342 currPtr = currPtr->GetNextNode();
343 }
344
345 if( currPtr && ntKey == currPtr->GetKey() ) {
346 xbLinkListNode<xbNodeType> *p = new xbLinkListNode<xbNodeType>( ntKey, sData );
347 if( prevPtr )
348 prevPtr->SetNextNode( p );
349 else
350 llStartPtr = p;
351 p->SetNextNode( currPtr->GetNextNode() );
352 p->SetPrevNode( currPtr->GetPrevNode() );
353 delete currPtr;
354 return XB_NO_ERROR;
355 }
356
357 return InsertKey( ntKey, sData );
358
359// return 0;
360}
361
362} // namespace
363
364#endif // XB_LINKLIST_SUPPORT
365#endif // XB_XBLNKLSTORD_H__
366
367
xb
Definition: xbdate.cpp:19
xb::xbBool
short int xbBool
Definition: xbtypes.h:24
XB_INVALID_NODELINK
#define XB_INVALID_NODELINK
Definition: xbretcod.h:28
XB_NOT_FOUND
#define XB_NOT_FOUND
Definition: xbretcod.h:39
XB_NO_ERROR
#define XB_NO_ERROR
Definition: xbretcod.h:24
XB_KEY_NOT_UNIQUE
#define XB_KEY_NOT_UNIQUE
Definition: xbretcod.h:29
XB_NO_MEMORY
#define XB_NO_MEMORY
Definition: xbretcod.h:25
xbTrue
#define xbTrue
Definition: xbtypes.h:28
xbFalse
#define xbFalse
Definition: xbtypes.h:29
Generated by doxygen 1.9.3