aboutsummaryrefslogtreecommitdiff
path: root/src/list.h
diff options
context:
space:
mode:
Diffstat (limited to '')
-rw-r--r--src/list.h373
1 files changed, 209 insertions, 164 deletions
diff --git a/src/list.h b/src/list.h
index 934766b..d711a2e 100644
--- a/src/list.h
+++ b/src/list.h
@@ -10,7 +10,8 @@
10 10
11#include <memory> 11#include <memory>
12#include "bu/exceptionbase.h" 12#include "bu/exceptionbase.h"
13#include "bu/util.h" 13#include "bu/sharedcore.h"
14//#include "bu/util.h"
14 15
15namespace Bu 16namespace Bu
16{ 17{
@@ -22,6 +23,153 @@ namespace Bu
22 ListLink *pPrev; 23 ListLink *pPrev;
23 }; 24 };
24 25
26 template<typename value, typename cmpfunc, typename valuealloc,
27 typename linkalloc>
28 struct ListCore
29 {
30 typedef struct ListLink<value> Link;
31 ListCore() :
32 pFirst( NULL ),
33 pLast( NULL ),
34 nSize( 0 )
35 { }
36 Link *pFirst;
37 Link *pLast;
38 long nSize;
39 cmpfunc cmp;
40 linkalloc la;
41 valuealloc va;
42
43 /**
44 * Append a value to the list.
45 *@param v (const value_type &) The value to append.
46 */
47 void append( const value &v )
48 {
49 Link *pNew = la.allocate( 1 );
50 pNew->pValue = va.allocate( 1 );
51 va.construct( pNew->pValue, v );
52 nSize++;
53 if( pFirst == NULL )
54 {
55 // Empty list
56 pFirst = pLast = pNew;
57 pNew->pNext = pNew->pPrev = NULL;
58 }
59 else
60 {
61 pNew->pNext = NULL;
62 pNew->pPrev = pLast;
63 pLast->pNext = pNew;
64 pLast = pNew;
65 }
66 }
67
68 /**
69 * Prepend a value to the list.
70 *@param v (const value_type &) The value to prepend.
71 */
72 void prepend( const value &v )
73 {
74 Link *pNew = la.allocate( 1 );
75 pNew->pValue = va.allocate( 1 );
76 va.construct( pNew->pValue, v );
77 nSize++;
78 if( pFirst == NULL )
79 {
80 // Empty list
81 pFirst = pLast = pNew;
82 pNew->pNext = pNew->pPrev = NULL;
83 }
84 else
85 {
86 pNew->pNext = pFirst;
87 pNew->pPrev = NULL;
88 pFirst->pPrev = pNew;
89 pFirst = pNew;
90 }
91 }
92
93 void clear()
94 {
95 Link *pCur = pFirst;
96 for(;;)
97 {
98 if( pCur == NULL ) break;
99 va.destroy( pCur->pValue );
100 va.deallocate( pCur->pValue, 1 );
101 Link *pTmp = pCur->pNext;
102 la.destroy( pCur );
103 la.deallocate( pCur, 1 );
104 pCur = pTmp;
105 }
106 pFirst = pLast = NULL;
107 nSize = 0;
108 }
109
110 void insert( Link *pLink, const value &v )
111 {
112 Link *pAfter = pLink;
113 if( pAfter == NULL )
114 {
115 append( v );
116 return;
117 }
118 Link *pPrev = pAfter->pPrev;
119 if( pPrev == NULL )
120 {
121 prepend( v );
122 return;
123 }
124
125 Link *pNew = la.allocate( 1 );
126 pNew->pValue = va.allocate( 1 );
127 va.construct( pNew->pValue, v );
128 nSize++;
129
130 pNew->pNext = pAfter;
131 pNew->pPrev = pPrev;
132 pAfter->pPrev = pNew;
133 pPrev->pNext = pNew;
134 }
135
136 /**
137 * Erase an item from the list.
138 *@param i (iterator) The item to erase.
139 */
140 void erase( Link *pLink )
141 {
142 Link *pCur = pLink;
143 if( pCur == NULL ) return;
144 Link *pPrev = pCur->pPrev;
145 if( pPrev == NULL )
146 {
147 va.destroy( pCur->pValue );
148 va.deallocate( pCur->pValue, 1 );
149 pFirst = pCur->pNext;
150 la.destroy( pCur );
151 la.deallocate( pCur, 1 );
152 if( pFirst == NULL )
153 pLast = NULL;
154 else
155 pFirst->pPrev = NULL;
156 nSize--;
157 }
158 else
159 {
160 va.destroy( pCur->pValue );
161 va.deallocate( pCur->pValue, 1 );
162 Link *pTmp = pCur->pNext;
163 la.destroy( pCur );
164 la.deallocate( pCur, 1 );
165 pPrev->pNext = pTmp;
166 if( pTmp != NULL )
167 pTmp->pPrev = pPrev;
168 nSize--;
169 }
170 }
171 };
172
25 /** 173 /**
26 * Linked list template container. This class is similar to the stl list 174 * Linked list template container. This class is similar to the stl list
27 * class except for a few minor changes. First, it doesn't mimic a stack or 175 * class except for a few minor changes. First, it doesn't mimic a stack or
@@ -38,61 +186,46 @@ namespace Bu
38 template<typename value, typename cmpfunc=__basicGTCmp<value>, 186 template<typename value, typename cmpfunc=__basicGTCmp<value>,
39 typename valuealloc=std::allocator<value>, 187 typename valuealloc=std::allocator<value>,
40 typename linkalloc=std::allocator<struct ListLink<value> > > 188 typename linkalloc=std::allocator<struct ListLink<value> > >
41 class List 189 class List : public SharedCore< struct ListCore<value, cmpfunc, valuealloc,
190 linkalloc> >
42 { 191 {
43 private: 192 private:
44 typedef struct ListLink<value> Link; 193 typedef struct ListLink<value> Link;
45 typedef class List<value, cmpfunc, valuealloc, linkalloc> MyType; 194 typedef class List<value, cmpfunc, valuealloc, linkalloc> MyType;
195 typedef struct ListCore<value, cmpfunc, valuealloc, linkalloc> Core;
196
197 protected:
198 using SharedCore< Core >::core;
199 using SharedCore< Core >::_hardCopy;
200 using SharedCore< Core >::_allocateCore;
46 201
47 public: 202 public:
48 struct const_iterator; 203 struct const_iterator;
49 struct iterator; 204 struct iterator;
50 205
51 List() : 206 List()
52 pFirst( NULL ),
53 pLast( NULL ),
54 nSize( 0 )
55 { 207 {
56 } 208 }
57 209
58 List( const MyType &src ) : 210 List( const MyType &src ) :
59 pFirst( NULL ), 211 SharedCore< Core >( src )
60 pLast( NULL ),
61 nSize( 0 )
62 { 212 {
63 for( Link *pCur = src.pFirst; pCur; pCur = pCur->pNext )
64 {
65 append( *pCur->pValue );
66 }
67 } 213 }
68 214
69 ~List() 215 ~List()
70 { 216 {
71 clear();
72 }
73
74 /**
75 * Assignment operator.
76 *@param src (const MyType &) The list to assign to your list.
77 */
78 MyType &operator=( const MyType &src )
79 {
80 clear();
81 for( Link *pCur = src.pFirst; pCur; pCur = pCur->pNext )
82 {
83 append( *pCur->pValue );
84 }
85 return *this;
86 } 217 }
87 218
88 MyType &operator+=( const value &v ) 219 MyType &operator+=( const value &v )
89 { 220 {
221 _hardCopy();
90 append( v ); 222 append( v );
91 return *this; 223 return *this;
92 } 224 }
93 225
94 MyType &operator+=( const MyType &src ) 226 MyType &operator+=( const MyType &src )
95 { 227 {
228 _hardCopy();
96 append( src ); 229 append( src );
97 return *this; 230 return *this;
98 } 231 }
@@ -102,67 +235,43 @@ namespace Bu
102 */ 235 */
103 void clear() 236 void clear()
104 { 237 {
105 Link *pCur = pFirst; 238 _hardCopy();
106 for(;;) 239 core->clear();
107 {
108 if( pCur == NULL ) break;
109 va.destroy( pCur->pValue );
110 va.deallocate( pCur->pValue, 1 );
111 Link *pTmp = pCur->pNext;
112 la.destroy( pCur );
113 la.deallocate( pCur, 1 );
114 pCur = pTmp;
115 }
116 pFirst = pLast = NULL;
117 nSize = 0;
118 } 240 }
119 241
120 void enqueue( const value &v ) 242 void enqueue( const value &v )
121 { 243 {
244 _hardCopy();
122 append( v ); 245 append( v );
123 } 246 }
124 247
125 value dequeue() 248 value dequeue()
126 { 249 {
127 value v = *pFirst->pValue; 250 // _hardCopy(); erase will call this for me
251 value v = *core->pFirst->pValue;
128 252
129 erase( begin() ); 253 erase( begin() );
130 254
131 return v; 255 return v;
132 } 256 }
133 257
134
135 /** 258 /**
136 * Append a value to the list. 259 * Append a value to the list.
137 *@param v (const value_type &) The value to append. 260 *@param v (const value_type &) The value to append.
138 */ 261 */
139 void append( const value &v ) 262 void append( const value &v )
140 { 263 {
141 Link *pNew = la.allocate( 1 ); 264 _hardCopy();
142 pNew->pValue = va.allocate( 1 ); 265 core->append( v );
143 va.construct( pNew->pValue, v );
144 nSize++;
145 if( pFirst == NULL )
146 {
147 // Empty list
148 pFirst = pLast = pNew;
149 pNew->pNext = pNew->pPrev = NULL;
150 }
151 else
152 {
153 pNew->pNext = NULL;
154 pNew->pPrev = pLast;
155 pLast->pNext = pNew;
156 pLast = pNew;
157 }
158 } 266 }
159 267
160 void append( const MyType &rSrc ) 268 void append( const MyType &rSrc )
161 { 269 {
270 _hardCopy();
162 for( typename MyType::const_iterator i = rSrc.begin(); 271 for( typename MyType::const_iterator i = rSrc.begin();
163 i != rSrc.end(); i++ ) 272 i != rSrc.end(); i++ )
164 { 273 {
165 append( *i ); 274 core->append( *i );
166 } 275 }
167 } 276 }
168 277
@@ -172,23 +281,8 @@ namespace Bu
172 */ 281 */
173 void prepend( const value &v ) 282 void prepend( const value &v )
174 { 283 {
175 Link *pNew = la.allocate( 1 ); 284 _hardCopy();
176 pNew->pValue = va.allocate( 1 ); 285 core->prepend( v );
177 va.construct( pNew->pValue, v );
178 nSize++;
179 if( pFirst == NULL )
180 {
181 // Empty list
182 pFirst = pLast = pNew;
183 pNew->pNext = pNew->pPrev = NULL;
184 }
185 else
186 {
187 pNew->pNext = pFirst;
188 pNew->pPrev = NULL;
189 pFirst->pPrev = pNew;
190 pFirst = pNew;
191 }
192 } 286 }
193 287
194 /** 288 /**
@@ -197,37 +291,19 @@ namespace Bu
197 */ 291 */
198 void prepend( const MyType &rSrc ) 292 void prepend( const MyType &rSrc )
199 { 293 {
294 _hardCopy();
200 for( typename MyType::const_iterator i = rSrc.begin(); 295 for( typename MyType::const_iterator i = rSrc.begin();
201 i != rSrc.end(); i++ ) 296 i != rSrc.end(); i++ )
202 { 297 {
203 prepend( *i ); 298 core->prepend( *i );
204 } 299 }
205 } 300 }
206 301
207 void insert( MyType::iterator &i, const value &v ) 302 void insert( MyType::iterator &i, const value &v )
208 { 303 {
209 Link *pAfter = i.pLink; 304 _hardCopy();
210 if( pAfter == NULL )
211 {
212 append( v );
213 return;
214 }
215 Link *pPrev = pAfter->pPrev;
216 if( pPrev == NULL )
217 {
218 prepend( v );
219 return;
220 }
221 305
222 Link *pNew = la.allocate( 1 ); 306 core->insert( i.pLink, v );
223 pNew->pValue = va.allocate( 1 );
224 va.construct( pNew->pValue, v );
225 nSize++;
226
227 pNew->pNext = pAfter;
228 pNew->pPrev = pPrev;
229 pAfter->pPrev = pNew;
230 pPrev->pNext = pNew;
231 } 307 }
232 308
233 /** 309 /**
@@ -239,40 +315,27 @@ namespace Bu
239 */ 315 */
240 void insertSorted( const value &v ) 316 void insertSorted( const value &v )
241 { 317 {
242 Link *pNew = la.allocate( 1 ); 318 _hardCopy();
243 pNew->pValue = va.allocate( 1 ); 319 if( core->pFirst == NULL )
244 va.construct( pNew->pValue, v );
245 nSize++;
246 if( pFirst == NULL )
247 { 320 {
248 // Empty list 321 // Empty list
249 pFirst = pLast = pNew; 322 core->append( v );
250 pNew->pNext = pNew->pPrev = NULL;
251 return; 323 return;
252 } 324 }
253 else 325 else
254 { 326 {
255 Link *pCur = pFirst; 327 Link *pCur = core->pFirst;
256 for(;;) 328 for(;;)
257 { 329 {
258 if( !cmp( v, *(pCur->pValue)) ) 330 if( !core->cmp( v, *(pCur->pValue)) )
259 { 331 {
260 pNew->pNext = pCur; 332 core->insert( pCur, v );
261 pNew->pPrev = pCur->pPrev;
262 pCur->pPrev = pNew;
263 if( pNew->pPrev == NULL )
264 pFirst = pNew;
265 else
266 pNew->pPrev->pNext = pNew;
267 return; 333 return;
268 } 334 }
269 pCur = pCur->pNext; 335 pCur = pCur->pNext;
270 if( pCur == NULL ) 336 if( pCur == NULL )
271 { 337 {
272 pNew->pNext = NULL; 338 core->append( v );
273 pNew->pPrev = pLast;
274 pLast->pNext = pNew;
275 pLast = pNew;
276 return; 339 return;
277 } 340 }
278 } 341 }
@@ -541,7 +604,8 @@ namespace Bu
541 */ 604 */
542 iterator begin() 605 iterator begin()
543 { 606 {
544 return iterator( pFirst ); 607 _hardCopy();
608 return iterator( core->pFirst );
545 } 609 }
546 610
547 /** 611 /**
@@ -550,7 +614,7 @@ namespace Bu
550 */ 614 */
551 const_iterator begin() const 615 const_iterator begin() const
552 { 616 {
553 return const_iterator( pFirst ); 617 return const_iterator( core->pFirst );
554 } 618 }
555 619
556 /** 620 /**
@@ -579,34 +643,8 @@ namespace Bu
579 */ 643 */
580 void erase( iterator i ) 644 void erase( iterator i )
581 { 645 {
582 Link *pCur = i.pLink; 646 _hardCopy();
583 if( pCur == NULL ) return; 647 core->erase( i.pLink );
584 Link *pPrev = pCur->pPrev;
585 if( pPrev == NULL )
586 {
587 va.destroy( pCur->pValue );
588 va.deallocate( pCur->pValue, 1 );
589 pFirst = pCur->pNext;
590 la.destroy( pCur );
591 la.deallocate( pCur, 1 );
592 if( pFirst == NULL )
593 pLast = NULL;
594 else
595 pFirst->pPrev = NULL;
596 nSize--;
597 }
598 else
599 {
600 va.destroy( pCur->pValue );
601 va.deallocate( pCur->pValue, 1 );
602 Link *pTmp = pCur->pNext;
603 la.destroy( pCur );
604 la.deallocate( pCur, 1 );
605 pPrev->pNext = pTmp;
606 if( pTmp != NULL )
607 pTmp->pPrev = pPrev;
608 nSize--;
609 }
610 } 648 }
611 649
612 /** 650 /**
@@ -615,7 +653,7 @@ namespace Bu
615 */ 653 */
616 void erase( const value &v ) 654 void erase( const value &v )
617 { 655 {
618 for( iterator i = begin(); i != end(); i++ ) 656 for( const_iterator i = begin(); i != end(); i++ )
619 { 657 {
620 if( (*i) == v ) 658 if( (*i) == v )
621 { 659 {
@@ -631,7 +669,7 @@ namespace Bu
631 */ 669 */
632 long getSize() const 670 long getSize() const
633 { 671 {
634 return nSize; 672 return core->nSize;
635 } 673 }
636 674
637 /** 675 /**
@@ -640,7 +678,8 @@ namespace Bu
640 */ 678 */
641 value &first() 679 value &first()
642 { 680 {
643 return *pFirst->pValue; 681 _hardCopy();
682 return *core->pFirst->pValue;
644 } 683 }
645 684
646 /** 685 /**
@@ -649,7 +688,7 @@ namespace Bu
649 */ 688 */
650 const value &first() const 689 const value &first() const
651 { 690 {
652 return *pFirst->pValue; 691 return *core->pFirst->pValue;
653 } 692 }
654 693
655 /** 694 /**
@@ -658,7 +697,8 @@ namespace Bu
658 */ 697 */
659 value &last() 698 value &last()
660 { 699 {
661 return *pLast->pValue; 700 _hardCopy();
701 return *core->pLast->pValue;
662 } 702 }
663 703
664 /** 704 /**
@@ -667,21 +707,26 @@ namespace Bu
667 */ 707 */
668 const value &last() const 708 const value &last() const
669 { 709 {
670 return *pLast->pValue; 710 return *core->pLast->pValue;
671 } 711 }
672 712
673 bool isEmpty() const 713 bool isEmpty() const
674 { 714 {
675 return (nSize == 0); 715 return (core->nSize == 0);
676 } 716 }
677 717
718 protected:
719 virtual Core *_copyCore( Core *src )
720 {
721 Core *pRet = _allocateCore();
722 for( Link *pCur = src->pFirst; pCur; pCur = pCur->pNext )
723 {
724 pRet->append( *pCur->pValue );
725 }
726 return pRet;
727 }
728
678 private: 729 private:
679 Link *pFirst;
680 Link *pLast;
681 linkalloc la;
682 valuealloc va;
683 long nSize;
684 cmpfunc cmp;
685 }; 730 };
686 731
687 class Formatter; 732 class Formatter;
generated by cgit v1.2.3 (git 2.39.1) at 2024-11-11 11:12:03 +0000