Mercurial > octave-nkf
changeset 8820:89b95972e178
fix previously introduced problem in octave_sort, improve design
| author | Jaroslav Hajek <highegg@gmail.com> |
|---|---|
| date | Fri, 20 Feb 2009 07:08:09 +0100 |
| parents | 96d87674b818 |
| children | 352f111b04ce |
| files | liboctave/ChangeLog liboctave/oct-sort.cc liboctave/oct-sort.h scripts/general/accumarray.m |
| diffstat | 4 files changed, 73 insertions(+), 117 deletions(-) [+] |
line wrap: on
line diff
--- a/liboctave/ChangeLog Fri Feb 20 01:00:25 2009 -0500 +++ b/liboctave/ChangeLog Fri Feb 20 07:08:09 2009 +0100 @@ -1,3 +1,15 @@ +2009-02-20 Jaroslav Hajek <highegg@gmail.com> + + * oct-sort.h (octave_sort<T>::MergeState::MergeState): New + constructor. + (octave_sort<T>::MergeState::~MergeState): New destructor. + (octave_sort<T>::MergeState::reset, + octave_sort<T>::MergeState::getmem, + octave_sort<T>::MergeState::getmemi): New methods. + (octave_sort<T>::sort, + octave_sort<T>::merge_lo, octave_sort<T>::merge_hi + octave_sort<T>::merge_at): Reflect change. + 2009-02-19 Jaroslav Hajek <highegg@gmail.com> * oct-types.h (sortmode): Move enum here.
--- a/liboctave/oct-sort.cc Fri Feb 20 01:00:25 2009 -0500 +++ b/liboctave/oct-sort.cc Fri Feb 20 07:08:09 2009 +0100 @@ -37,6 +37,15 @@ * duplicate methods to avoid by-the-way indexed sorting +* add methods for verifying sortedness of array + +* row sorting via breadth-first tree subsorting + +* binary lookup and sequential binary lookup optimized for dense downsampling. + +* NOTE: the memory management routines rely on the fact that delete [] silently + ignores null pointers. Don't gripe about the missing checks - they're there. + The Python license is @@ -120,7 +129,6 @@ template <class T> octave_sort<T>::~octave_sort () { - merge_freemem (); delete ms; } @@ -479,37 +487,6 @@ return ofs; } -/* Conceptually a MergeState's constructor. */ -template <class T> -void -octave_sort<T>::merge_init (void) -{ - if (! ms) ms = new MergeState; - ms->a = 0; - ms->ia = 0; - ms->alloced = 0; - ms->n = 0; - ms->min_gallop = MIN_GALLOP; -} - -/* Free all the temp memory owned by the MergeState. This must be called - * when you're done with a MergeState, and may be called before then if - * you want to free the temp memory early. - */ -template <class T> -void -octave_sort<T>::merge_freemem (void) -{ - if (ms) - { - delete [] ms->a; - delete [] ms->ia; - ms->alloced = 0; - ms->a = 0; - ms->ia = 0; - } -} - static inline octave_idx_type roundupsize (octave_idx_type n) { @@ -551,50 +528,40 @@ * Returns 0 on success and -1 if the memory can't be gotten. */ template <class T> -int -octave_sort<T>::merge_getmem (octave_idx_type need) +void +octave_sort<T>::MergeState::getmem (octave_idx_type need) { - if (need <= ms->alloced) - return 0; + if (need <= alloced) + return; need = roundupsize (need); /* Don't realloc! That can cost cycles to copy the old data, but * we don't care what's in the block. */ - merge_freemem (); - ms->a = new T[need]; - if (ms->a) - { - ms->alloced = need; - return 0; - } - merge_freemem (); /* reset to sane state */ + delete [] a; + delete [] ia; // Must do this or fool possible next getmemi. + a = new T[need]; + alloced = need; - return -1; } template <class T> -int -octave_sort<T>::merge_getmemi (octave_idx_type need) +void +octave_sort<T>::MergeState::getmemi (octave_idx_type need) { - if (need <= ms->alloced && ms->a && ms->ia) - return 0; + if (ia && need <= alloced) + return; need = roundupsize (need); /* Don't realloc! That can cost cycles to copy the old data, but * we don't care what's in the block. */ - merge_freemem (); - ms->a = new T[need]; - ms->ia = new octave_idx_type[need]; - if (ms->a && ms->ia) - { - ms->alloced = need; - return 0; - } - merge_freemem (); /* reset to sane state */ + delete [] a; + delete [] ia; - return -1; + a = new T[need]; + ia = new octave_idx_type[need]; + alloced = need; } /* Merge the na elements starting at pa with the nb elements starting at pb @@ -615,8 +582,8 @@ int result = -1; /* guilty until proved innocent */ octave_idx_type min_gallop = ms->min_gallop; - if (merge_getmem (na) < 0) - return -1; + ms->getmem (na); + std::copy (pa, pa + na, ms->a); dest = pa; pa = ms->a; @@ -751,8 +718,8 @@ int result = -1; /* guilty until proved innocent */ octave_idx_type min_gallop = ms->min_gallop; - if (merge_getmemi (na) < 0) - return -1; + ms->getmemi (na); + std::copy (pa, pa + na, ms->a); std::copy (ipa, ipa + na, ms->ia); dest = pa; idest = ipa; @@ -898,8 +865,8 @@ T *basea, *baseb; octave_idx_type min_gallop = ms->min_gallop; - if (merge_getmem (nb) < 0) - return -1; + ms->getmem (nb); + dest = pb + nb - 1; std::copy (pb, pb + nb, ms->a); basea = pa; @@ -1037,8 +1004,8 @@ octave_idx_type *ibasea, *ibaseb; octave_idx_type min_gallop = ms->min_gallop; - if (merge_getmemi (nb) < 0) - return -1; + ms->getmemi (nb); + dest = pb + nb - 1; idest = ipb + nb - 1; std::copy (pb, pb + nb, ms->a); @@ -1419,13 +1386,10 @@ octave_sort<T>::sort (T *data, octave_idx_type nel, Comp comp) { /* Re-initialize the Mergestate as this might be the second time called */ - if (ms) - { - ms->n = 0; - ms->min_gallop = MIN_GALLOP; - } - else - merge_init (); + if (! ms) ms = new MergeState; + + ms->reset (); + ms->getmem (1024); if (nel > 1) { @@ -1480,6 +1444,12 @@ octave_sort<T>::sort (T *data, octave_idx_type *idx, octave_idx_type nel, Comp comp) { + /* Re-initialize the Mergestate as this might be the second time called */ + if (! ms) ms = new MergeState; + + ms->reset (); + ms->getmemi (1024); + if (nel > 1) { octave_idx_type nremaining = nel; @@ -1534,17 +1504,6 @@ void octave_sort<T>::sort (T *data, octave_idx_type nel) { - /* Re-initialize the Mergestate as this might be the second time called */ - if (ms) - { - ms->n = 0; - ms->min_gallop = MIN_GALLOP; - } - else - merge_init (); - - merge_getmem (1024); - #ifdef INLINE_ASCENDING_SORT if (compare == ascending_compare) sort (data, nel, std::less<T> ()); @@ -1563,17 +1522,6 @@ void octave_sort<T>::sort (T *data, octave_idx_type *idx, octave_idx_type nel) { - /* Re-initialize the Mergestate as this might be the second time called */ - if (ms) - { - ms->n = 0; - ms->min_gallop = MIN_GALLOP; - } - else - merge_init (); - - merge_getmemi (1024); - #ifdef INLINE_ASCENDING_SORT if (compare == ascending_compare) sort (data, idx, nel, std::less<T> ()); @@ -1686,12 +1634,12 @@ if (comp (lbuf[lst], lbuf[i])) { if (i > lst + 1) - runs.push (run_t (col+1, lst, i - lst)); + runs.push (run_t (col+1, ofs + lst, i - lst)); lst = i; } } if (nel > lst + 1) - runs.push (run_t (col+1, lst, nel - lst)); + runs.push (run_t (col+1, ofs + lst, nel - lst)); } } } @@ -1701,17 +1649,6 @@ octave_sort<T>::sort_rows (const T *data, octave_idx_type *idx, octave_idx_type rows, octave_idx_type cols) { - /* Re-initialize the Mergestate as this might be the second time called */ - if (ms) - { - ms->n = 0; - ms->min_gallop = MIN_GALLOP; - } - else - merge_init (); - - merge_getmemi (1024); - #ifdef INLINE_ASCENDING_SORT if (compare == ascending_compare) sort_rows (data, idx, rows, cols, std::less<T> ());
--- a/liboctave/oct-sort.h Fri Feb 20 01:00:25 2009 -0500 +++ b/liboctave/oct-sort.h Fri Feb 20 07:08:09 2009 +0100 @@ -171,6 +171,20 @@ struct MergeState { + MergeState (void) + : a (0), ia (0), alloced (0) + { reset (); } + + ~MergeState (void) + { delete [] a; delete [] ia; } + + void reset (void) + { min_gallop = MIN_GALLOP; n = 0; } + + void getmem (octave_idx_type need); + + void getmemi (octave_idx_type need); + // This controls when we get *into* galloping mode. It's // initialized to MIN_GALLOP. merge_lo and merge_hi tend to nudge // it higher for random data, and lower for highly structured @@ -219,14 +233,6 @@ octave_idx_type gallop_right (T key, T *a, octave_idx_type n, octave_idx_type hint, Comp comp); - void merge_init (void); - - void merge_freemem (void); - - int merge_getmem (octave_idx_type need); - - int merge_getmemi (octave_idx_type need); - template <class Comp> int merge_lo (T *pa, octave_idx_type na, T *pb, octave_idx_type nb,