aboutsummaryrefslogtreecommitdiff
path: root/src
diff options
context:
space:
mode:
authorMike Buland <eichlan@xagasoft.com>2006-11-27 10:13:44 +0000
committerMike Buland <eichlan@xagasoft.com>2006-11-27 10:13:44 +0000
commit3025ed54309f793c6afbcbc9a564f71cc741f2ef (patch)
treeb579210f2f894bfeb7562e3339aea58c377c26b7 /src
parentdd049c4b3bbe6a605e41b043d933c02cb8497968 (diff)
downloadlibbu++-3025ed54309f793c6afbcbc9a564f71cc741f2ef.tar.gz
libbu++-3025ed54309f793c6afbcbc9a564f71cc741f2ef.tar.bz2
libbu++-3025ed54309f793c6afbcbc9a564f71cc741f2ef.tar.xz
libbu++-3025ed54309f793c6afbcbc9a564f71cc741f2ef.zip
Added the new OrdHash, check the test file for an example.
Diffstat (limited to '')
-rw-r--r--src/hash.h46
-rw-r--r--src/ordhash.cpp1
-rw-r--r--src/ordhash.h104
-rw-r--r--src/tests/ordhash.cpp48
-rw-r--r--src/tests/qsort.cpp228
-rw-r--r--src/tqsort.h207
6 files changed, 618 insertions, 16 deletions
diff --git a/src/hash.h b/src/hash.h
index d53e2be..cd21a29 100644
--- a/src/hash.h
+++ b/src/hash.h
@@ -92,7 +92,10 @@ public:
92 void erase() 92 void erase()
93 { 93 {
94 if( bFilled ) 94 if( bFilled )
95 {
95 hsh._erase( nPos ); 96 hsh._erase( nPos );
97 hsh.onDelete();
98 }
96 } 99 }
97 100
98 _value operator=( _value nval ) 101 _value operator=( _value nval )
@@ -101,10 +104,12 @@ public:
101 { 104 {
102 hsh.va.destroy( pValue ); 105 hsh.va.destroy( pValue );
103 hsh.va.construct( pValue, nval ); 106 hsh.va.construct( pValue, nval );
107 hsh.onUpdate();
104 } 108 }
105 else 109 else
106 { 110 {
107 hsh.fill( nPos, *pKey, nval, hash ); 111 hsh.fill( nPos, *pKey, nval, hash );
112 hsh.onInsert();
108 } 113 }
109 114
110 return nval; 115 return nval;
@@ -174,7 +179,7 @@ public:
174 return nDeleted; 179 return nDeleted;
175 } 180 }
176 181
177 HashProxy<key, value, sizecalc, keyalloc, valuealloc, challoc> operator[]( key k ) 182 virtual HashProxy<key, value, sizecalc, keyalloc, valuealloc, challoc> operator[]( key k )
178 { 183 {
179 uint32_t hash = __calcHashCode( k ); 184 uint32_t hash = __calcHashCode( k );
180 bool bFill; 185 bool bFill;
@@ -190,7 +195,7 @@ public:
190 } 195 }
191 } 196 }
192 197
193 void insert( key k, value v ) 198 virtual void insert( key k, value v )
194 { 199 {
195 uint32_t hash = __calcHashCode( k ); 200 uint32_t hash = __calcHashCode( k );
196 bool bFill; 201 bool bFill;
@@ -200,14 +205,16 @@ public:
200 { 205 {
201 va.destroy( &aValues[nPos] ); 206 va.destroy( &aValues[nPos] );
202 va.construct( &aValues[nPos], v ); 207 va.construct( &aValues[nPos], v );
208 onUpdate();
203 } 209 }
204 else 210 else
205 { 211 {
206 fill( nPos, k, v, hash ); 212 fill( nPos, k, v, hash );
213 onInsert();
207 } 214 }
208 } 215 }
209 216
210 void erase( key k ) 217 virtual void erase( key k )
211 { 218 {
212 uint32_t hash = __calcHashCode( k ); 219 uint32_t hash = __calcHashCode( k );
213 bool bFill; 220 bool bFill;
@@ -216,10 +223,11 @@ public:
216 if( bFill ) 223 if( bFill )
217 { 224 {
218 _erase( nPos ); 225 _erase( nPos );
226 onDelete();
219 } 227 }
220 } 228 }
221 229
222 void clear() 230 virtual void clear()
223 { 231 {
224 for( uint32_t j = 0; j < nCapacity; j++ ) 232 for( uint32_t j = 0; j < nCapacity; j++ )
225 { 233 {
@@ -228,13 +236,14 @@ public:
228 { 236 {
229 va.destroy( &aValues[j] ); 237 va.destroy( &aValues[j] );
230 ka.destroy( &aKeys[j] ); 238 ka.destroy( &aKeys[j] );
239 onDelete();
231 } 240 }
232 } 241 }
233 242
234 clearBits(); 243 clearBits();
235 } 244 }
236 245
237 value get( key k ) 246 virtual value get( key k )
238 { 247 {
239 uint32_t hash = __calcHashCode( k ); 248 uint32_t hash = __calcHashCode( k );
240 bool bFill; 249 bool bFill;
@@ -253,7 +262,7 @@ public:
253 } 262 }
254 } 263 }
255 264
256 bool has( key k ) 265 virtual bool has( key k )
257 { 266 {
258 bool bFill; 267 bool bFill;
259 probe( __calcHashCode( k ), k, bFill ); 268 probe( __calcHashCode( k ), k, bFill );
@@ -338,8 +347,13 @@ public:
338 return iterator( *this, true ); 347 return iterator( *this, true );
339 } 348 }
340 349
341private: 350protected:
342 void clearBits() 351 virtual void onInsert() {}
352 virtual void onUpdate() {}
353 virtual void onDelete() {}
354 virtual void onReHash() {}
355
356 virtual void clearBits()
343 { 357 {
344 for( uint32_t j = 0; j < nKeysSize; j++ ) 358 for( uint32_t j = 0; j < nKeysSize; j++ )
345 { 359 {
@@ -347,7 +361,7 @@ private:
347 } 361 }
348 } 362 }
349 363
350 void fill( uint32_t loc, key &k, value &v, uint32_t hash ) 364 virtual void fill( uint32_t loc, key &k, value &v, uint32_t hash )
351 { 365 {
352 bFilled[loc/32] |= (1<<(loc%32)); 366 bFilled[loc/32] |= (1<<(loc%32));
353 va.construct( &aValues[loc], v ); 367 va.construct( &aValues[loc], v );
@@ -356,19 +370,19 @@ private:
356 nFilled++; 370 nFilled++;
357 } 371 }
358 372
359 void _erase( uint32_t loc ) 373 virtual void _erase( uint32_t loc )
360 { 374 {
361 bDeleted[loc/32] |= (1<<(loc%32)); 375 bDeleted[loc/32] |= (1<<(loc%32));
362 va.destroy( &aValues[loc] ); 376 va.destroy( &aValues[loc] );
363 ka.destroy( &aKeys[loc] ); 377 ka.destroy( &aKeys[loc] );
364 } 378 }
365 379
366 std::pair<key,value> getAtPos( uint32_t nPos ) 380 virtual std::pair<key,value> getAtPos( uint32_t nPos )
367 { 381 {
368 return std::pair<key,value>(aKeys[nPos],aValues[nPos]); 382 return std::pair<key,value>(aKeys[nPos],aValues[nPos]);
369 } 383 }
370 384
371 uint32_t getFirstPos( bool &bFinished ) 385 virtual uint32_t getFirstPos( bool &bFinished )
372 { 386 {
373 for( uint32_t j = 0; j < nCapacity; j++ ) 387 for( uint32_t j = 0; j < nCapacity; j++ )
374 { 388 {
@@ -381,7 +395,7 @@ private:
381 return 0; 395 return 0;
382 } 396 }
383 397
384 uint32_t getNextPos( uint32_t nPos, bool &bFinished ) 398 virtual uint32_t getNextPos( uint32_t nPos, bool &bFinished )
385 { 399 {
386 for( uint32_t j = nPos+1; j < nCapacity; j++ ) 400 for( uint32_t j = nPos+1; j < nCapacity; j++ )
387 { 401 {
@@ -488,17 +502,17 @@ private:
488 ca.deallocate( aOldHashCodes, nOldCapacity ); 502 ca.deallocate( aOldHashCodes, nOldCapacity );
489 } 503 }
490 504
491 bool isFilled( uint32_t loc ) 505 virtual bool isFilled( uint32_t loc )
492 { 506 {
493 return (bFilled[loc/32]&(1<<(loc%32)))!=0; 507 return (bFilled[loc/32]&(1<<(loc%32)))!=0;
494 } 508 }
495 509
496 bool isDeleted( uint32_t loc ) 510 virtual bool isDeleted( uint32_t loc )
497 { 511 {
498 return (bDeleted[loc/32]&(1<<(loc%32)))!=0; 512 return (bDeleted[loc/32]&(1<<(loc%32)))!=0;
499 } 513 }
500 514
501private: 515protected:
502 uint32_t nCapacity; 516 uint32_t nCapacity;
503 uint32_t nFilled; 517 uint32_t nFilled;
504 uint32_t nDeleted; 518 uint32_t nDeleted;
diff --git a/src/ordhash.cpp b/src/ordhash.cpp
new file mode 100644
index 0000000..77cbd61
--- /dev/null
+++ b/src/ordhash.cpp
@@ -0,0 +1 @@
#include "ordhash.h"
diff --git a/src/ordhash.h b/src/ordhash.h
new file mode 100644
index 0000000..e946f95
--- /dev/null
+++ b/src/ordhash.h
@@ -0,0 +1,104 @@
1#ifndef ORD_HASH_H
2#define ORD_HASH_H
3
4#include "hash.h"
5#include "tqsort.h"
6
7template<typename key, typename value, typename cmpfnc, typename sizecalc = __calcNextTSize_fast, typename keyalloc = std::allocator<key>, typename valuealloc = std::allocator<value>, typename challoc = std::allocator<uint32_t> >
8class OrdHash : public Hash<key, value, sizecalc, keyalloc, valuealloc, challoc>
9{
10public:
11 OrdHash() :
12 bSorted( false ),
13 aData( NULL )
14 {
15 }
16
17 virtual ~OrdHash()
18 {
19 }
20
21protected:
22 virtual void invalidate()
23 {
24 bSorted = false;
25 delete[] aData;
26 aData = NULL;
27 }
28
29 virtual void onInsert()
30 {
31 invalidate();
32 }
33
34 virtual void onUpdate()
35 {
36 invalidate();
37 }
38
39 virtual void onDelete()
40 {
41 invalidate();
42 }
43
44 virtual void onReHash()
45 {
46 invalidate();
47 }
48
49 virtual std::pair<key,value> getAtPos( uint32_t nPos )
50 {
51 return Hash<key, value, sizecalc, keyalloc, valuealloc, challoc>::getAtPos( aData[nPos].nIndex );
52 }
53
54 virtual void buildIndex()
55 {
56 aData = new struct ind[this->nFilled];
57 uint32_t k = 0;
58 for( uint32_t j = 0; j < this->nCapacity; j++ )
59 {
60 if( this->isFilled( j ) )
61 {
62 if( !this->isDeleted( j ) )
63 {
64 aData[k].pVal = &(this->aValues[j]);
65 aData[k].nIndex = j;
66 k++;
67 }
68 }
69 }
70
71 tqsort<typename OrdHash<key, value, cmpfnc, sizecalc, keyalloc, valuealloc, challoc>::ind, cmpfnc, value **>( aData, this->nFilled );
72
73 bSorted = true;
74 }
75
76 virtual uint32_t getFirstPos( bool &bFinished )
77 {
78 if( bSorted == false )
79 buildIndex();
80
81 return 0;
82 }
83
84 virtual uint32_t getNextPos( uint32_t nPos, bool &bFinished )
85 {
86 if( nPos+1 >= this->nFilled )
87 {
88 bFinished = true;
89 return 0;
90 }
91 return ++nPos;
92 }
93public:
94 typedef struct ind
95 {
96 value *pVal;
97 uint32_t nIndex;
98 } ind;
99private:
100 bool bSorted;
101 ind *aData;
102};
103
104#endif
diff --git a/src/tests/ordhash.cpp b/src/tests/ordhash.cpp
new file mode 100644
index 0000000..f1d96ec
--- /dev/null
+++ b/src/tests/ordhash.cpp
@@ -0,0 +1,48 @@
1#include "ordhash.h"
2#include <string>
3
4typedef struct eldef
5{
6 eldef( int a, int b, const std::string &c ) :
7 id( a ), nSequence( b ), sName( c ) {}
8 int id;
9 int nSequence;
10 std::string sName;
11} eldef;
12
13struct seqcmp
14{
15 bool operator()( eldef **a, eldef **b )
16 {
17 return (*a)->nSequence < (*b)->nSequence;
18 }
19};
20
21struct namcmp
22{
23 bool operator()( eldef **a, eldef **b )
24 {
25 return (*a)->sName < (*b)->sName;
26 }
27};
28
29typedef OrdHash<int, eldef, seqcmp> AHash;
30//typedef OrdHash<int, eldef, namcmp> AHash;
31
32int main()
33{
34 AHash hsh;
35 hsh[1] = eldef( 0, 43, "Bob");
36 hsh[4] = eldef( 1, 443, "Abby");
37 hsh[2] = eldef( 2, 1, "Name");
38 hsh[5] = eldef( 3, 0, "Catagory");
39 hsh[32] = eldef( 4, 12, "Epilogue");
40
41 for( AHash::iterator i = hsh.begin(); i != hsh.end(); i++ )
42 {
43 eldef e = (*i).second;
44 printf("%d, %d, %s\n", e.id, e.nSequence, e.sName.c_str() );
45 }
46
47}
48
diff --git a/src/tests/qsort.cpp b/src/tests/qsort.cpp
new file mode 100644
index 0000000..28c6f03
--- /dev/null
+++ b/src/tests/qsort.cpp
@@ -0,0 +1,228 @@
1#define _QSORT_SWAP(a, b, t) ((void)((t = *a), (*a = *b), (*b = t)))
2
3/* Discontinue quicksort algorithm when partition gets below this size.
4 This particular magic number was chosen to work best on a Sun 4/260. */
5#define _QSORT_MAX_THRESH 4
6
7/* Stack node declarations used to store unfulfilled partition obligations
8 * (inlined in QSORT).
9typedef struct {
10 QSORT_TYPE *_lo, *_hi;
11} qsort_stack_node;
12 */
13
14/* The next 4 #defines implement a very fast in-line stack abstraction. */
15/* The stack needs log (total_elements) entries (we could even subtract
16 log(MAX_THRESH)). Since total_elements has type unsigned, we get as
17 upper bound for log (total_elements):
18 bits per byte (CHAR_BIT) * sizeof(unsigned). */
19#define _QSORT_STACK_SIZE (8 * sizeof(unsigned))
20#define _QSORT_PUSH(top, low, high) \
21 (((top->_lo = (low)), (top->_hi = (high)), ++top))
22#define _QSORT_POP(low, high, top) \
23 ((--top, (low = top->_lo), (high = top->_hi)))
24#define _QSORT_STACK_NOT_EMPTY (_stack < _top)
25
26
27/* Order size using quicksort. This implementation incorporates
28 four optimizations discussed in Sedgewick:
29
30 1. Non-recursive, using an explicit stack of pointer that store the
31 next array partition to sort. To save time, this maximum amount
32 of space required to store an array of SIZE_MAX is allocated on the
33 stack. Assuming a 32-bit (64 bit) integer for size_t, this needs
34 only 32 * sizeof(stack_node) == 256 bytes (for 64 bit: 1024 bytes).
35 Pretty cheap, actually.
36
37 2. Chose the pivot element using a median-of-three decision tree.
38 This reduces the probability of selecting a bad pivot value and
39 eliminates certain extraneous comparisons.
40
41 3. Only quicksorts TOTAL_ELEMS / MAX_THRESH partitions, leaving
42 insertion sort to order the MAX_THRESH items within each partition.
43 This is a big win, since insertion sort is faster for small, mostly
44 sorted array segments.
45
46 4. The larger of the two sub-partitions is always pushed onto the
47 stack first, with the algorithm then concentrating on the
48 smaller partition. This *guarantees* no more than log (total_elems)
49 stack size is needed (actually O(1) in this case)! */
50
51/* The main code starts here... */
52
53template<typename QSORT_TYPE, typename QSORT_LTT>
54void qsrt( QSORT_TYPE *QSORT_BASE, int QSORT_NELT )
55{
56 QSORT_LTT QSORT_LT;
57 QSORT_TYPE *const _base = (QSORT_BASE);
58 const unsigned _elems = (QSORT_NELT);
59 QSORT_TYPE _hold;
60
61 /* Don't declare two variables of type QSORT_TYPE in a single
62 * statement: eg `TYPE a, b;', in case if TYPE is a pointer,
63 * expands to `type* a, b;' wich isn't what we want.
64 */
65
66 if (_elems > _QSORT_MAX_THRESH) {
67 QSORT_TYPE *_lo = _base;
68 QSORT_TYPE *_hi = _lo + _elems - 1;
69 struct {
70 QSORT_TYPE *_hi; QSORT_TYPE *_lo;
71 } _stack[_QSORT_STACK_SIZE], *_top = _stack + 1;
72
73 while (_QSORT_STACK_NOT_EMPTY) {
74 QSORT_TYPE *_left_ptr; QSORT_TYPE *_right_ptr;
75
76 /* Select median value from among LO, MID, and HI. Rearrange
77 LO and HI so the three values are sorted. This lowers the
78 probability of picking a pathological pivot value and
79 skips a comparison for both the LEFT_PTR and RIGHT_PTR in
80 the while loops. */
81
82 QSORT_TYPE *_mid = _lo + ((_hi - _lo) >> 1);
83
84 if (QSORT_LT (_mid, _lo))
85 _QSORT_SWAP (_mid, _lo, _hold);
86 if (QSORT_LT (_hi, _mid))
87 _QSORT_SWAP (_mid, _hi, _hold);
88 else
89 goto _jump_over;
90 if (QSORT_LT (_mid, _lo))
91 _QSORT_SWAP (_mid, _lo, _hold);
92 _jump_over:;
93
94 _left_ptr = _lo + 1;
95 _right_ptr = _hi - 1;
96
97 /* Here's the famous ``collapse the walls'' section of quicksort.
98 Gotta like those tight inner loops! They are the main reason
99 that this algorithm runs much faster than others. */
100 do {
101 while (QSORT_LT (_left_ptr, _mid))
102 ++_left_ptr;
103
104 while (QSORT_LT (_mid, _right_ptr))
105 --_right_ptr;
106
107 if (_left_ptr < _right_ptr) {
108 _QSORT_SWAP (_left_ptr, _right_ptr, _hold);
109 if (_mid == _left_ptr)
110 _mid = _right_ptr;
111 else if (_mid == _right_ptr)
112 _mid = _left_ptr;
113 ++_left_ptr;
114 --_right_ptr;
115 }
116 else if (_left_ptr == _right_ptr) {
117 ++_left_ptr;
118 --_right_ptr;
119 break;
120 }
121 } while (_left_ptr <= _right_ptr);
122
123 /* Set up pointers for next iteration. First determine whether
124 left and right partitions are below the threshold size. If so,
125 ignore one or both. Otherwise, push the larger partition's
126 bounds on the stack and continue sorting the smaller one. */
127
128 if (_right_ptr - _lo <= _QSORT_MAX_THRESH) {
129 if (_hi - _left_ptr <= _QSORT_MAX_THRESH)
130 /* Ignore both small partitions. */
131 _QSORT_POP (_lo, _hi, _top);
132 else
133 /* Ignore small left partition. */
134 _lo = _left_ptr;
135 }
136 else if (_hi - _left_ptr <= _QSORT_MAX_THRESH)
137 /* Ignore small right partition. */
138 _hi = _right_ptr;
139 else if (_right_ptr - _lo > _hi - _left_ptr) {
140 /* Push larger left partition indices. */
141 _QSORT_PUSH (_top, _lo, _right_ptr);
142 _lo = _left_ptr;
143 }
144 else {
145 /* Push larger right partition indices. */
146 _QSORT_PUSH (_top, _left_ptr, _hi);
147 _hi = _right_ptr;
148 }
149 }
150 }
151
152 /* Once the BASE array is partially sorted by quicksort the rest
153 is completely sorted using insertion sort, since this is efficient
154 for partitions below MAX_THRESH size. BASE points to the
155 beginning of the array to sort, and END_PTR points at the very
156 last element in the array (*not* one beyond it!). */
157
158 {
159 QSORT_TYPE *const _end_ptr = _base + _elems - 1;
160 QSORT_TYPE *_tmp_ptr = _base;
161 register QSORT_TYPE *_run_ptr;
162 QSORT_TYPE *_thresh;
163
164 _thresh = _base + _QSORT_MAX_THRESH;
165 if (_thresh > _end_ptr)
166 _thresh = _end_ptr;
167
168 /* Find smallest element in first threshold and place it at the
169 array's beginning. This is the smallest array element,
170 and the operation speeds up insertion sort's inner loop. */
171
172 for (_run_ptr = _tmp_ptr + 1; _run_ptr <= _thresh; ++_run_ptr)
173 if (QSORT_LT (_run_ptr, _tmp_ptr))
174 _tmp_ptr = _run_ptr;
175
176 if (_tmp_ptr != _base)
177 _QSORT_SWAP (_tmp_ptr, _base, _hold);
178
179 /* Insertion sort, running from left-hand-side
180 * up to right-hand-side. */
181
182 _run_ptr = _base + 1;
183 while (++_run_ptr <= _end_ptr) {
184 _tmp_ptr = _run_ptr - 1;
185 while (QSORT_LT (_run_ptr, _tmp_ptr))
186 --_tmp_ptr;
187
188 ++_tmp_ptr;
189 if (_tmp_ptr != _run_ptr) {
190 QSORT_TYPE *_trav = _run_ptr + 1;
191 while (--_trav >= _run_ptr) {
192 QSORT_TYPE *_hi; QSORT_TYPE *_lo;
193 _hold = *_trav;
194
195 for (_hi = _lo = _trav; --_lo >= _tmp_ptr; _hi = _lo)
196 *_hi = *_lo;
197 *_hi = _hold;
198 }
199 }
200 }
201 }
202
203}
204
205
206struct cc
207{
208 bool operator()( int *a, int *b )
209 {
210 return *a < *b;
211 }
212};
213
214#include <stdio.h>
215
216int main()
217{
218 int lst[] = { 43, 1, 342, 12, 491, 32, 12321, 32, 3, -3 };
219
220 for( int j = 0; j < 10; j++ )
221 printf("%s%d", (j>0)?", ":"", lst[j] );
222 printf("\n");
223 qsrt<int, cc>( lst, 10 );
224 for( int j = 0; j < 10; j++ )
225 printf("%s%d", (j>0)?", ":"", lst[j] );
226 printf("\n");
227}
228
diff --git a/src/tqsort.h b/src/tqsort.h
new file mode 100644
index 0000000..c836b4f
--- /dev/null
+++ b/src/tqsort.h
@@ -0,0 +1,207 @@
1#ifndef T_QSORT_H
2#define T_QSORT_H
3
4#define _QSORT_SWAP(a, b, t) ((void)((t = *a), (*a = *b), (*b = t)))
5
6/* Discontinue quicksort algorithm when partition gets below this size.
7 This particular magic number was chosen to work best on a Sun 4/260. */
8#define _QSORT_MAX_THRESH 4
9
10/* Stack node declarations used to store unfulfilled partition obligations
11 * (inlined in QSORT).
12typedef struct {
13 QSORT_TYPE *_lo, *_hi;
14} qsort_stack_node;
15 */
16
17/* The next 4 #defines implement a very fast in-line stack abstraction. */
18/* The stack needs log (total_elements) entries (we could even subtract
19 log(MAX_THRESH)). Since total_elements has type unsigned, we get as
20 upper bound for log (total_elements):
21 bits per byte (CHAR_BIT) * sizeof(unsigned). */
22#define _QSORT_STACK_SIZE (8 * sizeof(unsigned))
23#define _QSORT_PUSH(top, low, high) \
24 (((top->_lo = (low)), (top->_hi = (high)), ++top))
25#define _QSORT_POP(low, high, top) \
26 ((--top, (low = top->_lo), (high = top->_hi)))
27#define _QSORT_STACK_NOT_EMPTY (_stack < _top)
28
29
30/* Order size using quicksort. This implementation incorporates
31 four optimizations discussed in Sedgewick:
32
33 1. Non-recursive, using an explicit stack of pointer that store the
34 next array partition to sort. To save time, this maximum amount
35 of space required to store an array of SIZE_MAX is allocated on the
36 stack. Assuming a 32-bit (64 bit) integer for size_t, this needs
37 only 32 * sizeof(stack_node) == 256 bytes (for 64 bit: 1024 bytes).
38 Pretty cheap, actually.
39
40 2. Chose the pivot element using a median-of-three decision tree.
41 This reduces the probability of selecting a bad pivot value and
42 eliminates certain extraneous comparisons.
43
44 3. Only quicksorts TOTAL_ELEMS / MAX_THRESH partitions, leaving
45 insertion sort to order the MAX_THRESH items within each partition.
46 This is a big win, since insertion sort is faster for small, mostly
47 sorted array segments.
48
49 4. The larger of the two sub-partitions is always pushed onto the
50 stack first, with the algorithm then concentrating on the
51 smaller partition. This *guarantees* no more than log (total_elems)
52 stack size is needed (actually O(1) in this case)! */
53
54/* The main code starts here... */
55
56template<typename QSORT_TYPE, typename QSORT_LTT, typename CST>
57void tqsort( QSORT_TYPE *QSORT_BASE, int QSORT_NELT )
58{
59 QSORT_LTT QSORT_LT;
60 QSORT_TYPE *const _base = (QSORT_BASE);
61 const unsigned _elems = (QSORT_NELT);
62 QSORT_TYPE _hold;
63
64 /* Don't declare two variables of type QSORT_TYPE in a single
65 * statement: eg `TYPE a, b;', in case if TYPE is a pointer,
66 * expands to `type* a, b;' wich isn't what we want.
67 */
68
69 if (_elems > _QSORT_MAX_THRESH) {
70 QSORT_TYPE *_lo = _base;
71 QSORT_TYPE *_hi = _lo + _elems - 1;
72 struct {
73 QSORT_TYPE *_hi; QSORT_TYPE *_lo;
74 } _stack[_QSORT_STACK_SIZE], *_top = _stack + 1;
75
76 while (_QSORT_STACK_NOT_EMPTY) {
77 QSORT_TYPE *_left_ptr; QSORT_TYPE *_right_ptr;
78
79 /* Select median value from among LO, MID, and HI. Rearrange
80 LO and HI so the three values are sorted. This lowers the
81 probability of picking a pathological pivot value and
82 skips a comparison for both the LEFT_PTR and RIGHT_PTR in
83 the while loops. */
84
85 QSORT_TYPE *_mid = _lo + ((_hi - _lo) >> 1);
86
87 if (QSORT_LT ((CST)(_mid), (CST)(_lo)))
88 _QSORT_SWAP (_mid, _lo, _hold);
89 if (QSORT_LT ((CST)(_hi), (CST)(_mid)))
90 _QSORT_SWAP (_mid, _hi, _hold);
91 else
92 goto _jump_over;
93 if (QSORT_LT ((CST)(_mid), (CST)(_lo)))
94 _QSORT_SWAP (_mid, _lo, _hold);
95 _jump_over:;
96
97 _left_ptr = _lo + 1;
98 _right_ptr = _hi - 1;
99
100 /* Here's the famous ``collapse the walls'' section of quicksort.
101 Gotta like those tight inner loops! They are the main reason
102 that this algorithm runs much faster than others. */
103 do {
104 while (QSORT_LT ((CST)(_left_ptr), (CST)(_mid)))
105 ++_left_ptr;
106
107 while (QSORT_LT ((CST)(_mid), (CST)(_right_ptr)))
108 --_right_ptr;
109
110 if (_left_ptr < _right_ptr) {
111 _QSORT_SWAP (_left_ptr, _right_ptr, _hold);
112 if (_mid == _left_ptr)
113 _mid = _right_ptr;
114 else if (_mid == _right_ptr)
115 _mid = _left_ptr;
116 ++_left_ptr;
117 --_right_ptr;
118 }
119 else if (_left_ptr == _right_ptr) {
120 ++_left_ptr;
121 --_right_ptr;
122 break;
123 }
124 } while (_left_ptr <= _right_ptr);
125
126 /* Set up pointers for next iteration. First determine whether
127 left and right partitions are below the threshold size. If so,
128 ignore one or both. Otherwise, push the larger partition's
129 bounds on the stack and continue sorting the smaller one. */
130
131 if (_right_ptr - _lo <= _QSORT_MAX_THRESH) {
132 if (_hi - _left_ptr <= _QSORT_MAX_THRESH)
133 /* Ignore both small partitions. */
134 _QSORT_POP (_lo, _hi, _top);
135 else
136 /* Ignore small left partition. */
137 _lo = _left_ptr;
138 }
139 else if (_hi - _left_ptr <= _QSORT_MAX_THRESH)
140 /* Ignore small right partition. */
141 _hi = _right_ptr;
142 else if (_right_ptr - _lo > _hi - _left_ptr) {
143 /* Push larger left partition indices. */
144 _QSORT_PUSH (_top, _lo, _right_ptr);
145 _lo = _left_ptr;
146 }
147 else {
148 /* Push larger right partition indices. */
149 _QSORT_PUSH (_top, _left_ptr, _hi);
150 _hi = _right_ptr;
151 }
152 }
153 }
154
155 /* Once the BASE array is partially sorted by quicksort the rest
156 is completely sorted using insertion sort, since this is efficient
157 for partitions below MAX_THRESH size. BASE points to the
158 beginning of the array to sort, and END_PTR points at the very
159 last element in the array (*not* one beyond it!). */
160
161 {
162 QSORT_TYPE *const _end_ptr = _base + _elems - 1;
163 QSORT_TYPE *_tmp_ptr = _base;
164 register QSORT_TYPE *_run_ptr;
165 QSORT_TYPE *_thresh;
166
167 _thresh = _base + _QSORT_MAX_THRESH;
168 if (_thresh > _end_ptr)
169 _thresh = _end_ptr;
170
171 /* Find smallest element in first threshold and place it at the
172 array's beginning. This is the smallest array element,
173 and the operation speeds up insertion sort's inner loop. */
174
175 for (_run_ptr = _tmp_ptr + 1; _run_ptr <= _thresh; ++_run_ptr)
176 if (QSORT_LT ((CST)(_run_ptr), (CST)(_tmp_ptr)))
177 _tmp_ptr = _run_ptr;
178
179 if (_tmp_ptr != _base)
180 _QSORT_SWAP (_tmp_ptr, _base, _hold);
181
182 /* Insertion sort, running from left-hand-side
183 * up to right-hand-side. */
184
185 _run_ptr = _base + 1;
186 while (++_run_ptr <= _end_ptr) {
187 _tmp_ptr = _run_ptr - 1;
188 while (QSORT_LT ((CST)(_run_ptr), (CST)(_tmp_ptr)))
189 --_tmp_ptr;
190
191 ++_tmp_ptr;
192 if (_tmp_ptr != _run_ptr) {
193 QSORT_TYPE *_trav = _run_ptr + 1;
194 while (--_trav >= _run_ptr) {
195 QSORT_TYPE *_hi; QSORT_TYPE *_lo;
196 _hold = *_trav;
197
198 for (_hi = _lo = _trav; --_lo >= _tmp_ptr; _hi = _lo)
199 *_hi = *_lo;
200 *_hi = _hold;
201 }
202 }
203 }
204 }
205}
206
207#endif
generated by cgit v1.2.3 (git 2.39.1) at 2024-11-11 21:45:19 +0000