Groups | Search | Server Info | Keyboard shortcuts | Login | Register [http] [https] [nntp] [nntps]

Groups > comp.lang.c > #21807 > unrolled thread

Breakthrough

Back to article view | Back to comp.lang.c

Contents

  Breakthrough jacob navia <jacob@spamsink.net> - 2012-06-04 13:38 +0200
    Re: Breakthrough MelissA <melis@a.com> - 2012-06-04 14:20 +0200
      Re: Breakthrough Juha Nieminen <nospam@thanks.invalid> - 2012-06-04 15:32 +0000
        Re: Breakthrough Ike Naar <ike@iceland.freeshell.org> - 2012-06-04 15:44 +0000
          Re: Breakthrough jacob navia <jacob@spamsink.net> - 2012-06-04 18:03 +0200
            Re: Breakthrough Ian Collins <ian-news@hotmail.com> - 2012-06-05 10:23 +1200
              Re: Breakthrough jacob navia <jacob@spamsink.net> - 2012-06-05 00:31 +0200
                Re: Breakthrough Luca Risolia <luca.risolia@studio.unibo.it> - 2012-06-05 01:43 +0200
                  Re: Breakthrough Martin Shobe <martin.shobe@yahoo.com> - 2012-06-05 00:26 +0000
        Re: Breakthrough jacob navia <jacob@spamsink.net> - 2012-06-04 17:47 +0200
          Re: Breakthrough Juha Nieminen <nospam@thanks.invalid> - 2012-06-05 05:36 +0000
        Re: Breakthrough Paul <nospam@needed.com> - 2012-06-04 12:32 -0400
        Re: Breakthrough MelissA <melis@a.com> - 2012-06-04 21:44 +0200
          Re: Breakthrough MelissA <melis@a.com> - 2012-06-04 22:01 +0200
            Re: Breakthrough jacob navia <jacob@spamsink.net> - 2012-06-04 22:42 +0200
              Re: Breakthrough MelissA <melis@a.com> - 2012-06-05 00:16 +0200
                Re: Breakthrough MelissA <melis@a.com> - 2012-06-05 00:47 +0200
                Re: Breakthrough MelissA <melis@a.com> - 2012-06-05 03:34 +0200
        Re: Breakthrough 88888 Dihedral <dihedral88888@googlemail.com> - 2012-06-06 17:28 -0700
    Re: Breakthrough "BartC" <bc@freeuk.com> - 2012-06-04 17:30 +0100
      Re: Breakthrough jacob navia <jacob@spamsink.net> - 2012-06-04 19:30 +0200
        Re: Breakthrough "BartC" <bc@freeuk.com> - 2012-06-04 19:18 +0100
          Re: Breakthrough jacob navia <jacob@spamsink.net> - 2012-06-04 20:50 +0200
            Re: Breakthrough "BartC" <bc@freeuk.com> - 2012-06-05 00:31 +0100
    Re: Breakthrough pete <pfiland@mindspring.com> - 2012-06-04 17:23 -0400
      Re: Breakthrough Noob <root@localhost> - 2012-06-05 09:10 +0200
        Re: Breakthrough Ike Naar <ike@sverige.freeshell.org> - 2012-06-05 08:03 +0000
        Re: Breakthrough pete <pfiland@mindspring.com> - 2012-06-06 00:20 -0400
          Re: Breakthrough Robert Wessel <robertwessel2@yahoo.com> - 2012-06-06 00:06 -0500
            Re: Breakthrough pete <pfiland@mindspring.com> - 2012-06-06 09:10 -0400
              Re: Breakthrough Robert Wessel <robertwessel2@yahoo.com> - 2012-06-06 09:23 -0500
                Re: Breakthrough pete <pfiland@mindspring.com> - 2012-06-06 19:49 -0400
                  Re: Breakthrough Willem <willem@toad.stack.nl> - 2012-06-07 15:10 +0000
                  Re: Breakthrough jacob navia <jacob@spamsink.net> - 2012-06-08 01:37 +0200
                    Re: Breakthrough pete <pfiland@mindspring.com> - 2012-06-08 09:55 -0400
                    Re: Breakthrough pete <pfiland@mindspring.com> - 2012-06-08 21:26 -0400
                    Re: Breakthrough pete <pfiland@mindspring.com> - 2012-06-09 23:49 -0400
                      Re: Breakthrough 88888 Dihedral <dihedral88888@googlemail.com> - 2012-06-11 06:50 -0700
                        Re: Breakthrough pete <pfiland@mindspring.com> - 2012-06-11 22:36 -0400
    Re: Breakthrough Ian Collins <ian-news@hotmail.com> - 2012-06-05 10:02 +1200
      Re: Breakthrough jacob navia <jacob@spamsink.net> - 2012-06-05 00:26 +0200

Page 2 of 3 — ← Prev page 1 [2] 3  Next page →

#21824

Le 04/06/12 18:30, BartC a écrit :
> "jacob navia" <jacob@spamsink.net> wrote in message
> news:jqi6o4$gqf$1@speranza.aioe.org...
>
>
>> I have uploaded the latest code to:
>>
>> http://code.google.com/p/ccl/
>>
>> There you will find (in listgen.c) the "templated" version of quick
>> sort in C.
>
> How do you build this thing? Typing make gives errors:
>
> c:\lcc\bin\make says something about bitstrings.o.
>
> Copying makefile.lcc to makefile then doing the same:
>
> c:\lcc\bin\make now complains about something in lcc64.
>
> (I never use 'make' so haven't got a clue. A readme file might be
> helpful though.)
>


Sorry, I did not test under windows. I tested now, and you should
just type

make -f makefile.lcc

That compiles in 32 bits lcc

make -f makefile.lcc64

That compiles 64 bit lcc
I upddated the zip file. Please download again and tell me how it goes.

Thanks

[toc] | [prev] | [next] | [standalone]

#21825

"jacob navia" <jacob@spamsink.net> wrote in message
news:jqirb6$imi$1@speranza.aioe.org...
> Le 04/06/12 18:30, BartC a écrit :

>> How do you build this thing? Typing make gives errors:

> Sorry, I did not test under windows.

That explains the funny line endings in the files..

> I tested now, and you should
> just type
>
> make -f makefile.lcc

Thanks. Downloading the latest lcc 32-bits to make sure, this now gets hung 
up on errors in wchar.h (first on line 521, then on line 509).

> That compiles in 32 bits lcc
>
> make -f makefile.lcc64

I couldn't see a .lcc64 file (in the distribution downloaded after your
post)

Anyway I've now given up on make files (I always have trouble with them.
Always.) I found I could build your test program by manually compiling and
linking these files:

intlist.c
buffer.c
vector.c
bitstrings.c
bloom.c
containererror.c
deque.c
dictionary.c
dlist.c
fgetline.c
generic.c
hashtable.c
heap.c
iMask.c
list.c
malloc_debug.c
pool.c
pooldebug.c
qsortex.c
queue.c
redblacktree.c
scapegoat.c
searchtree.c
strcollection.c
valarraydouble.c
valarrayint.c
valarrayuint.c
valarraysize_t.c
valarrayfloat.c
valarraylongdouble.c
valarrayuint.c
valarraylonglong.c
valarrayulonglong.c
valarrayshort.c
observer.c
memorymanager.c
sequential.c
wstrcollection.c

-- 
Bartc 

[toc] | [prev] | [next] | [standalone]

#21826

Le 04/06/12 20:18, BartC a écrit :
>
>
> "jacob navia" <jacob@spamsink.net> wrote in message
> news:jqirb6$imi$1@speranza.aioe.org...
>> Le 04/06/12 18:30, BartC a écrit :
>
>>> How do you build this thing? Typing make gives errors:
>
>> Sorry, I did not test under windows.
>
> That explains the funny line endings in the files..
>
>> I tested now, and you should
>> just type
>>
>> make -f makefile.lcc
>
> Thanks. Downloading the latest lcc 32-bits to make sure, this now gets
> hung up on errors in wchar.h (first on line 521, then on line 509).
>

Ahhh you are using the distribution that comes with the compiler?

That's not really up-to-date. Please download the ccl code from

http://code.google.com/p/ccl/

[toc] | [prev] | [next] | [standalone]

#21844

"jacob navia" <jacob@spamsink.net> wrote in message 
news:jqj017$vai$1@speranza.aioe.org...
> Le 04/06/12 20:18, BartC a écrit :

>> Thanks. Downloading the latest lcc 32-bits to make sure, this now gets
>> hung up on errors in wchar.h (first on line 521, then on line 509).
>>
>
> Ahhh you are using the distribution that comes with the compiler?

No. I updated lcc in case it was out-of-date and causing the problem. The 
CCL stuff is separate.

In any case, this project doesn't need a makefile as it's straightforward 
(now I know what's needed); I will leave that to the experts.

I wanted to test the speed of container lists versus ordinary arrays (I know 
containers are more sophisticated but your test is simple so I'm looking at 
just that).

The results of your test program weren't so interesting, because 95% of the 
runtime seemed to be in sorting. So got rid of that, and just tested 
allocating and iterating over 100M (not 10M) int objects. This took about 8 
seconds and seem to use about 1.3GB of memory (is there a per-element 
overhead?)

Using an ordinary allocated array, took only 1.7 seconds, and used the 
expected 0.4GB of memory.

However this was *preallocated*, a possible advantage. (I ran the same test 
on a dynamic language, which took 16 seconds, whether the int-array was 
preallocated or not. Interestingly (need to verify this), using a 
preallocated generic list only took 10 seconds, not far off the CCL timing 
for a non-generic list).

It seems the conclusion, if my results are valid, is that if the 
requirements are very simple, that ordinary C array handling should be 
considered if speed and memory are important. Maybe you might want to put 
forward a more elaborate test that isn't so easy to rewrite in standard C...

-- 
Bartc 

[toc] | [prev] | [next] | [standalone]

#21832

jacob navia wrote:
 
> The expression used to compare two list elements is:
> #define COMPARE_EXPRESSION(A, B) \
>      ((*B)->Data > (*A)->Data ? -1 : (*B)->Data != (*A)->Data)
> 
> I thank Pete for that proposal, I wouldn't have come to it
> alone :-)

You're welcome.
I hope that I can give you an even handier tip.
I've never needed the three way comparison 
to implement any sorting algorithm.

It has always been sufficient for me
to merely use a (Greater Than) macro, GT(A, B),
to implement any sorting algorithm.

#define GT(A, B)     ((*A)->Data > (*B)->Data)

I have never needed to know whether two keys compare equal,
in order to implement a sorting algorithm.

-- 
pete

[toc] | [prev] | [next] | [standalone]

#21855

pete wrote:

> I've never needed the three way comparison 
> to implement any sorting algorithm.
> 
> It has always been sufficient for me
> to merely use a (Greater Than) macro, GT(A, B),
> to implement any sorting algorithm.
> 
> #define GT(A, B)     ((*A)->Data > (*B)->Data)
> 
> I have never needed to know whether two keys compare equal,
> in order to implement a sorting algorithm.

Perhaps it is needed when writing "stable" sorting algorithms?
http://en.wikipedia.org/wiki/Sorting_algorithm#Stability

[toc] | [prev] | [next] | [standalone]

#21859

On 2012-06-05, Noob <root@localhost> wrote:
> pete wrote:
>
>> I've never needed the three way comparison 
>> to implement any sorting algorithm.
>> 
>> It has always been sufficient for me
>> to merely use a (Greater Than) macro, GT(A, B),
>> to implement any sorting algorithm.
>> 
>> #define GT(A, B)     ((*A)->Data > (*B)->Data)
>> 
>> I have never needed to know whether two keys compare equal,
>> in order to implement a sorting algorithm.
>
> Perhaps it is needed when writing "stable" sorting algorithms?
> http://en.wikipedia.org/wiki/Sorting_algorithm#Stability

Equality of A and B follows from

  !(GT(A, B) || GT(B, A))

provided that GT defines a total order.

[toc] | [prev] | [next] | [standalone]

#21886

Noob wrote:
> 
> pete wrote:
> 
> > I've never needed the three way comparison
> > to implement any sorting algorithm.
> >
> > It has always been sufficient for me
> > to merely use a (Greater Than) macro, GT(A, B),
> > to implement any sorting algorithm.
> >
> > #define GT(A, B)     ((*A)->Data > (*B)->Data)
> >
> > I have never needed to know whether two keys compare equal,
> > in order to implement a sorting algorithm.
> 
> Perhaps it is needed when writing "stable" sorting algorithms?
> http://en.wikipedia.org/wiki/Sorting_algorithm#Stability

No. Definitely not.
When implementing any of the inherently stable algorithms,
such as bubble sort, insertion sort or merge sort,
it is sufficient to know only 
whether or not the two keys being compared, are out of order. 

The wikipedia article claims that the order
of the keys can be used as a tie breaker to convert 
an unstable algorithm into a stable one, 
but that is wrong because,
when two distant unequal keys are compared,
the only way to maintain stability
between those two keys and all of the keys in between them,
is to move all of the keys in between them.

Example:
Suppose you have this array:

    char numbers[][sizeof "eight"] = {"seven","eight","six"};

and you want to do a stable sort according to string length,
the result of a stable sort would be {"six","seven","eight"}.

If you sorted {"seven","eight","six"}
by using a non stable sort such as simple selection sort,
using the key addresses as a tie breaker,
"seven" would not be out of order compared to "eight",
regardless of whether their addresses were used as a tie breaker.
But when "seven" was compared to "six",
those two keys would be out of order and swapped
with the final sort result being {"six","eight","seven"}.

-- 
pete

[toc] | [prev] | [next] | [standalone]

#21887

On Wed, 06 Jun 2012 00:20:21 -0400, pete <pfiland@mindspring.com>
wrote:

>Noob wrote:
>> 
>> pete wrote:
>> 
>> > I've never needed the three way comparison
>> > to implement any sorting algorithm.
>> >
>> > It has always been sufficient for me
>> > to merely use a (Greater Than) macro, GT(A, B),
>> > to implement any sorting algorithm.
>> >
>> > #define GT(A, B)     ((*A)->Data > (*B)->Data)
>> >
>> > I have never needed to know whether two keys compare equal,
>> > in order to implement a sorting algorithm.
>> 
>> Perhaps it is needed when writing "stable" sorting algorithms?
>> http://en.wikipedia.org/wiki/Sorting_algorithm#Stability
>
>No. Definitely not.
>When implementing any of the inherently stable algorithms,
>such as bubble sort, insertion sort or merge sort,
>it is sufficient to know only 
>whether or not the two keys being compared, are out of order. 
>
>The wikipedia article claims that the order
>of the keys can be used as a tie breaker to convert 
>an unstable algorithm into a stable one, 
>but that is wrong because,
>when two distant unequal keys are compared,
>the only way to maintain stability
>between those two keys and all of the keys in between them,
>is to move all of the keys in between them.
>
>Example:
>Suppose you have this array:
>
>    char numbers[][sizeof "eight"] = {"seven","eight","six"};
>
>and you want to do a stable sort according to string length,
>the result of a stable sort would be {"six","seven","eight"}.
>
>If you sorted {"seven","eight","six"}
>by using a non stable sort such as simple selection sort,
>using the key addresses as a tie breaker,
>"seven" would not be out of order compared to "eight",
>regardless of whether their addresses were used as a tie breaker.
>But when "seven" was compared to "six",
>those two keys would be out of order and swapped
>with the final sort result being {"six","eight","seven"}.


You're misreading the Wikipedia article.  It actually says "One way of
doing this is to artificially extend the key comparison, so that
comparisons between two objects with otherwise equal keys are decided
using the order of the entries in the original data order as a
tie-breaker."  The critical bit is "the order of the entries in the
*original* data order as a tie-breaker."  And that's quite correct. In
the case of "distant" records with nominally equal keys, you're
extending the comparison to be between (key, original record number)
tuples.

[toc] | [prev] | [next] | [standalone]

#21904

Robert Wessel wrote:
> 
> On Wed, 06 Jun 2012 00:20:21 -0400, pete <pfiland@mindspring.com>
> wrote:
> 
> >Noob wrote:
> >>
> >> pete wrote:
> >>
> >> > I've never needed the three way comparison
> >> > to implement any sorting algorithm.
> >> >
> >> > It has always been sufficient for me
> >> > to merely use a (Greater Than) macro, GT(A, B),
> >> > to implement any sorting algorithm.
> >> >
> >> > #define GT(A, B)     ((*A)->Data > (*B)->Data)
> >> >
> >> > I have never needed to know whether two keys compare equal,
> >> > in order to implement a sorting algorithm.
> >>
> >> Perhaps it is needed when writing "stable" sorting algorithms?
> >> http://en.wikipedia.org/wiki/Sorting_algorithm#Stability
> >
> >No. Definitely not.
> >When implementing any of the inherently stable algorithms,
> >such as bubble sort, insertion sort or merge sort,
> >it is sufficient to know only
> >whether or not the two keys being compared, are out of order.
> >
> >The wikipedia article claims that the order
> >of the keys can be used as a tie breaker to convert
> >an unstable algorithm into a stable one,
> >but that is wrong because,
> >when two distant unequal keys are compared,
> >the only way to maintain stability
> >between those two keys and all of the keys in between them,
> >is to move all of the keys in between them.
> >
> >Example:
> >Suppose you have this array:
> >
> >    char numbers[][sizeof "eight"] = {"seven","eight","six"};
> >
> >and you want to do a stable sort according to string length,
> >the result of a stable sort would be {"six","seven","eight"}.
> >
> >If you sorted {"seven","eight","six"}
> >by using a non stable sort such as simple selection sort,
> >using the key addresses as a tie breaker,
> >"seven" would not be out of order compared to "eight",
> >regardless of whether their addresses were used as a tie breaker.
> >But when "seven" was compared to "six",
> >those two keys would be out of order and swapped
> >with the final sort result being {"six","eight","seven"}.
> 
> You're misreading the Wikipedia article. 

It says 
    "Unstable sorting algorithms can be specially
     implemented to be stable.""

> It actually says "One way of
> doing this is to artificially extend the key comparison, so that
> comparisons between two objects with otherwise equal keys are decided
> using the order of the entries in the original data order as a
> tie-breaker." 
> The critical bit is "the order of the entries in the
> *original* data order as a tie-breaker."  And that's quite correct. In
> the case of "distant" records with nominally equal keys, you're
> extending the comparison to be between (key, original record number)
> tuples.

But that is not one way of doing it,
that is only *part* of one way of doing it.

The example that I showed, 
*did* use the original order as a tie breaker.
To convert a nonstable algorithm to a stable one,
is more complicated
than just using the original order as a tiebreaker.

The article then says
"Remembering this order,  however, 
 often involves an additional computational cost."

But
 "Remembering this order" 
is more complicated than merely
 "additional computational cost."

"Remembering this order" also requires additional memory usage,
at which point it becomes simpler to stable sort using merge sort,
which merely requires the simple GT(A,B) macro.

A fast merge sort can be either done directly,
using a buffer half the size of the original array,
or if the element size is greater than (4 * sizeof(void *))
a fast merge sort can be done with less additional memory
using 2 arrays of pointers instead.


-- 
pete

[toc] | [prev] | [next] | [standalone]

#21910

On Wed, 06 Jun 2012 09:10:37 -0400, pete <pfiland@mindspring.com>
wrote:

>Robert Wessel wrote:
>> 
>> On Wed, 06 Jun 2012 00:20:21 -0400, pete <pfiland@mindspring.com>
>> wrote:
>> 
>> >Noob wrote:
>> >>
>> >> pete wrote:
>> >>
>> >> > I've never needed the three way comparison
>> >> > to implement any sorting algorithm.
>> >> >
>> >> > It has always been sufficient for me
>> >> > to merely use a (Greater Than) macro, GT(A, B),
>> >> > to implement any sorting algorithm.
>> >> >
>> >> > #define GT(A, B)     ((*A)->Data > (*B)->Data)
>> >> >
>> >> > I have never needed to know whether two keys compare equal,
>> >> > in order to implement a sorting algorithm.
>> >>
>> >> Perhaps it is needed when writing "stable" sorting algorithms?
>> >> http://en.wikipedia.org/wiki/Sorting_algorithm#Stability
>> >
>> >No. Definitely not.
>> >When implementing any of the inherently stable algorithms,
>> >such as bubble sort, insertion sort or merge sort,
>> >it is sufficient to know only
>> >whether or not the two keys being compared, are out of order.
>> >
>> >The wikipedia article claims that the order
>> >of the keys can be used as a tie breaker to convert
>> >an unstable algorithm into a stable one,
>> >but that is wrong because,
>> >when two distant unequal keys are compared,
>> >the only way to maintain stability
>> >between those two keys and all of the keys in between them,
>> >is to move all of the keys in between them.
>> >
>> >Example:
>> >Suppose you have this array:
>> >
>> >    char numbers[][sizeof "eight"] = {"seven","eight","six"};
>> >
>> >and you want to do a stable sort according to string length,
>> >the result of a stable sort would be {"six","seven","eight"}.
>> >
>> >If you sorted {"seven","eight","six"}
>> >by using a non stable sort such as simple selection sort,
>> >using the key addresses as a tie breaker,
>> >"seven" would not be out of order compared to "eight",
>> >regardless of whether their addresses were used as a tie breaker.
>> >But when "seven" was compared to "six",
>> >those two keys would be out of order and swapped
>> >with the final sort result being {"six","eight","seven"}.
>> 
>> You're misreading the Wikipedia article. 
>
>It says 
>    "Unstable sorting algorithms can be specially
>     implemented to be stable.""
>
>> It actually says "One way of
>> doing this is to artificially extend the key comparison, so that
>> comparisons between two objects with otherwise equal keys are decided
>> using the order of the entries in the original data order as a
>> tie-breaker." 
>> The critical bit is "the order of the entries in the
>> *original* data order as a tie-breaker."  And that's quite correct. In
>> the case of "distant" records with nominally equal keys, you're
>> extending the comparison to be between (key, original record number)
>> tuples.
>
>But that is not one way of doing it,
>that is only *part* of one way of doing it.
>
>The example that I showed, 
>*did* use the original order as a tie breaker.
>To convert a nonstable algorithm to a stable one,
>is more complicated
>than just using the original order as a tiebreaker.


That's not what a tie breaker does.  The sort keys for the three items
in your sample list are (5,1), (5,2) and (3,3).  The (only) ordered
version of that is (3,3), (5,1), (5,2).  With a multi-part key you
compare each segment, first to last, until you find an unequal one.
There's still just the one sort, just the comparison is more complex
(ignoring the issue, in this case, of where you get the information
about the original order - which is typically just stored as a counter
with each record).


>The article then says
>"Remembering this order,  however, 
> often involves an additional computational cost."
>
>But
> "Remembering this order" 
>is more complicated than merely
> "additional computational cost."
>
>"Remembering this order" also requires additional memory usage,
>at which point it becomes simpler to stable sort using merge sort,
>which merely requires the simple GT(A,B) macro.


Yes, and I never disputed that.


>A fast merge sort can be either done directly,
>using a buffer half the size of the original array,
>or if the element size is greater than (4 * sizeof(void *))
>a fast merge sort can be done with less additional memory
>using 2 arrays of pointers instead.


If you have the conditions for a merge sort, it's one of the best
choices, if not the best choice.  It does require additional storage
beyond the records to be sorted itself.  Obviously so does adding the
extra key segment need to force a sort to be stable.  Whether or not
stability is important is one of the tradeoffs in selecting a sort (in
fact, it's actually a fairly rare requirement).

[toc] | [prev] | [next] | [standalone]

#21922

Robert Wessel wrote:
> 
> On Wed, 06 Jun 2012 09:10:37 -0400, pete <pfiland@mindspring.com>
> wrote:
> 
> >Robert Wessel wrote:
> >>
> >> On Wed, 06 Jun 2012 00:20:21 -0400, pete <pfiland@mindspring.com>
> >> wrote:
> >>
> >> >Noob wrote:
> >> >>
> >> >> pete wrote:
> >> >>
> >> >> > I've never needed the three way comparison
> >> >> > to implement any sorting algorithm.
> >> >> >
> >> >> > It has always been sufficient for me
> >> >> > to merely use a (Greater Than) macro, GT(A, B),
> >> >> > to implement any sorting algorithm.
> >> >> >
> >> >> > #define GT(A, B)     ((*A)->Data > (*B)->Data)

> If you have the conditions for a merge sort, it's one of the best
> choices, if not the best choice.  It does require additional storage
> beyond the records to be sorted itself.  Obviously so does adding the
> extra key segment need to force a sort to be stable.  Whether or not
> stability is important is one of the tradeoffs in selecting a sort (in
> fact, it's actually a fairly rare requirement).

Anyway, 
the point that I was was originally trying to make to Jacob Navia, 
still stands; Which is, 
that I have never needed anything else but a GreaterThan macro,
to implement any kind of comparison sorting algorithm,
stable or otherwise.

-- 
pete

[toc] | [prev] | [next] | [standalone]

#21933

pete wrote:
) Anyway, 
) the point that I was was originally trying to make to Jacob Navia, 
) still stands; Which is, 
) that I have never needed anything else but a GreaterThan macro,
) to implement any kind of comparison sorting algorithm,
) stable or otherwise.

Speaking theoretically: You can implement an 'Equals' macro in terms
of a 'GreaterThan' macro easily, so all you need is 'GreaterThan'.


SaSW, Willem
-- 
Disclaimer: I am in no way responsible for any of the statements
            made in the above text. For all I know I might be
            drugged or something..
            No I'm not paranoid. You all think I'm paranoid, don't you !
#EOT

[toc] | [prev] | [next] | [standalone]

#21938

Le 07/06/12 01:49, pete a écrit :
>
> Anyway,
> the point that I was was originally trying to make to Jacob Navia,
> still stands; Which is,
> that I have never needed anything else but a GreaterThan macro,
> to implement any kind of comparison sorting algorithm,
> stable or otherwise.
>

Maybe you have some spare time?

I am convinced my code would benefit from your critical eye Pete.

Just download it from

http://code.google.com/p/ccl/

and look at it. The file listgen.c contains the templated sort function.

[toc] | [prev] | [next] | [standalone]

#21955

jacob navia wrote:
> 
> Le 07/06/12 01:49, pete a écrit :
> >
> > Anyway,
> > the point that I was was originally trying to make to Jacob Navia,
> > still stands; Which is,
> > that I have never needed anything else but a GreaterThan macro,
> > to implement any kind of comparison sorting algorithm,
> > stable or otherwise.
> >
> 
> Maybe you have some spare time?

From time to time, I have some time.
 
> I am convinced my code would benefit from your critical eye Pete.
> 
> Just download it from
> 
> http://code.google.com/p/ccl/
> 
> and look at it.
> The file listgen.c contains the templated sort function.

I will take a look at it.

At this point, it occurs to me 
that if you have searching functions
which use exactly the same COMPARE_EXPRESSION macro,
as your sorting functions use,
then it might be necessary to use the three way comparison.

Do you have searching functions which use 
exactly the same COMPARE_EXPRESSION macro,
as your sorting functions use?

-- 
pete

[toc] | [prev] | [next] | [standalone]

#22031

jacob navia wrote:
 
> I am convinced my code would benefit from your critical eye Pete.
> 
> Just download it from
> 
> http://code.google.com/p/ccl/
> 
> and look at it.
> The file listgen.c contains the templated sort function.

The first mistake that I noticed, is a common one.

In 
    static void QSORT(LIST_ELEMENT **base, size_t num)
these two expressions
     COMPARE_EXPRESSION(loguy,lo) <= 0
     COMPARE_EXPRESSION(higuy,lo) >= 0
should be written this way
     COMPARE_EXPRESSION(loguy,lo) < 0
     COMPARE_EXPRESSION(higuy,lo) > 0
to properly address the issue of
     How to handle keys equal to the partitioning element?

See page 4 of
    http://www.cs.princeton.edu/~rs/talks/QuicksortIsOptimal.pdf
    How to handle keys equal to the partitioning element?
by Robert Sedgewick and Jon Bentley.

-- 
pete

[toc] | [prev] | [next] | [standalone]

#22085

jacob navia wrote:

> Maybe you have some spare time?
> 
> I am convinced my code would benefit from your critical eye Pete.
> 
> Just download it from
> 
> http://code.google.com/p/ccl/
> 
> and look at it.
> The file listgen.c contains the templated sort function.

/*
** On 6 September 2008, I posted pqsort.
**
** http://groups.google.com/group/comp.lang.c/msg/6a73e359f4814457
**
** This is a version of listgen.c with a new QSORT based on pqsort.
** It's an introspective quicksort.
** If you like, I can toss in a PRNG for the pivot selection.
** Try it.
*/
/* BEGIN listgen.c */
/*
 * Value types generic list routines sample implementation 
 * ----------------------------------- ------------------
 * Thisroutines handle the List container class. This is a very general
 * implementation and efficiency considerations aren't yet primordial.
Lists
 * can have elements of any size. This implement single linked Lists.
The
 * design goals here are just correctness and showing how the
implementation
 * of the proposed interface COULD be done.
 *
----------------------------------------------------------------------
 */

#include "listgen.h"
#include "ccl_internal.h"

#include <assert.h>

/* Forward declarations */
static LIST_TYPE *SetVTable(LIST_TYPE *result);
static LIST_TYPE * Create(size_t elementsize);
static LIST_TYPE *CreateWithAllocator(size_t elementsize, const
ContainerAllocator * allocator);
#define CONTAINER_LIST_SMALL    2
#define CHUNK_SIZE    1000

static int DefaultListCompareFunction(const void * left, const void *
right, CompareInfo * ExtraArgs)
{
    size_t          siz = ((LIST_TYPE *)
ExtraArgs->ContainerLeft)->ElementSize;
    return memcmp(left, right, siz);
}

/*------------------------------------------------------------------------
 Procedure:     Contains ID:1
 Purpose:       Determines if the given data is in the container
 Input:         The list and the data to be searched
 Output:        Returns 1 (true) if the data is in there, false
                otherwise
 Errors:        The same as the function IndexOf
------------------------------------------------------------------------*/
static int Contains(const LIST_TYPE * l, const DATA_TYPE data)
{
    size_t idx;
    return (iList.IndexOf((List *)l, &data, NULL, &idx) < 0) ? 0 : 1;
}

static int Add(LIST_TYPE * l, const DATA_TYPE elem)
{
    return iList.Add((List *)l,&elem);
}

/*------------------------------------------------------------------------
 Procedure:     GetElement ID:1
 Purpose:       Returns the data associated with a given position
 Input:         The list and the position
 Output:        A pointer to the data
 Errors:        NULL if error in the positgion index
------------------------------------------------------------------------*/
static DATA_TYPE GetElement(const LIST_TYPE * l, size_t position)
{
    DATA_TYPE *pdata = iList.GetElement((List *)l,position);

    if (pdata == NULL) return ERROR_RETURN;
    return *pdata;
}

static DATA_TYPE Back(const LIST_TYPE * l)
{
    DATA_TYPE *p = (DATA_TYPE *)iList.Back((List *)l);
    if (p == NULL) return ERROR_RETURN;
    return *p;
}

static DATA_TYPE Front(const LIST_TYPE * l)
{
    DATA_TYPE *p = (DATA_TYPE *)iList.Front((List *)l);
    if (p == NULL) return ERROR_RETURN;
    return *p;
}

static int CopyElement(const LIST_TYPE * l, size_t position, DATA_TYPE
*outBuffer)
{
    return iList.CopyElement((List *)l,position,outBuffer);
}

static int ReplaceAt(LIST_TYPE * l, size_t position, const DATA_TYPE
data)
{
    return iList.ReplaceAt((List *)l,position,&data);;
}

static int PushFront(LIST_TYPE * l, const DATA_TYPE pdata)
{
    return iList.PushFront((List *)l,&pdata);
}


static int PopFront(LIST_TYPE * l, DATA_TYPE *result)
{
    return iList.PushFront((List *)l,result);
}


static int InsertAt(LIST_TYPE * l, size_t pos, const DATA_TYPE pdata)
{
    return iList.InsertAt((List *)l,pos,&pdata);
}

static int Erase(LIST_TYPE * l, const DATA_TYPE elem)
{
    return iList.Erase((List *)l, &elem);
}

static int EraseAll(LIST_TYPE * l, const DATA_TYPE elem)
{
    return iList.EraseAll((List *)l, &elem);
}

static int IndexOf(const LIST_TYPE * l, const DATA_TYPE ElementToFind,
void *ExtraArgs, size_t * result)
{
    return iList.IndexOf((List *)l, &ElementToFind, ExtraArgs, result);
}

static size_t Sizeof(const LIST_TYPE * l)
{
    if (l == NULL) {
        return sizeof(List);
    }
    return sizeof(LIST_TYPE) + l->ElementSize * l->count + l->count *
offsetof(LIST_ELEMENT,Data);
}

static size_t SizeofIterator(const LIST_TYPE * l)
{
    return sizeof(struct ITERATOR(DATA_TYPE));
}

static LIST_TYPE *Load(FILE * stream, ReadFunction loadFn, void *arg)
{
    LIST_TYPE *result = (LIST_TYPE *)iList.Load(stream,loadFn,arg);
    return SetVTable(result);
}

/*
 *
---------------------------------------------------------------------------
 *
 *                           Iterators
 *
 *
---------------------------------------------------------------------------
 */
static int ReplaceWithIterator(Iterator * it, DATA_TYPE data, int
direction)
{
    struct ITERATOR(DATA_TYPE) *iter = (struct ITERATOR(DATA_TYPE) *)it;
    return iter->ListReplace(it,&data,direction);
}

static Iterator *SetupIteratorVTable(struct ITERATOR(DATA_TYPE) *result)
{
    if (result == NULL) return NULL;
    result->ListReplace = result->it.Replace;
    result->it.Replace = (int (*)(Iterator * , void * , int
))ReplaceWithIterator;
    return &result->it;
}

static Iterator *NewIterator(LIST_TYPE * L)
{
    return SetupIteratorVTable((struct ITERATOR(DATA_TYPE)
*)iList.NewIterator((List *)L));
}
static int InitIterator(LIST_TYPE * L, void *r)
{
    iList.InitIterator((List *)L,r);
    SetupIteratorVTable(r);
    return 1;
}
static size_t GetElementSize(const LIST_TYPE * l)
{
    return sizeof(DATA_TYPE);
}

static int Finalize(LIST_TYPE *l)
{
    iList.Finalize((List *)l);
    return 1;
}

static LIST_TYPE  *Copy(const LIST_TYPE * l)
{
    LIST_TYPE *result = (LIST_TYPE *)iList.Copy((List *)l);
    return SetVTable(result);
}


static LIST_TYPE *SelectCopy(const LIST_TYPE *l,const Mask *m)
{
    LIST_TYPE *result = (LIST_TYPE *)iList.SelectCopy((const List
*)l,m);
    return SetVTable(result);
}

/*---------------------------------------------------------------------------*/
/* qsort() - perform a quicksort on an
array                                 */
/*---------------------------------------------------------------------------*/

#ifndef COMPARE_EXPRESSION
#error foo
#define COMPARE_EXPRESSION(l,lo) comp(l, lo)
//COMPAR(A, B) (B > A ? -1 : B != A)
#endif

#define E_TYPE          LIST_ELEMENT *e_type
#define GT(A, B)        (COMPARE_EXPRESSION((A), (B)) > 0)
#define MOV(A, B)       ((void)(*(A) = *(B)))
#define SMALL_PARTITION 8

#define SWAP(A, B, T)                                   \
    (MOV((T), (A)), MOV((A), (B)), MOV((B), (T)))

#define SORT_3(A, B, C, T)                              \
    if (GT((A), (B))) {                                 \
        MOV((T), (A));                                  \
        if (GT((C), (B))) {                             \
            MOV((A), (B));                              \
            if (GT((T), (C))) {                         \
                MOV((B), (C));                          \
                MOV((C), (T));                          \
            } else {                                    \
                MOV((B), (T));                          \
            }                                           \
        } else {                                        \
            MOV((A), (C));                              \
            MOV((C), (T));                              \
        }                                               \
    } else {                                            \
        if (GT((B), (C))) {                             \
            MOV((T), (B));                              \
            if (GT((A), (C))) {                         \
                MOV((B), (A));                          \
                MOV((A), (C));                          \
            } else {                                    \
                MOV((B), (C));                          \
            }                                           \
            MOV((C), (T));                              \
        }                                               \
    }

#define SIFTDOWNM(P)                                    \
{                                                       \
    parent = (P);                                       \
    child = parent * 2;                                 \
    MOV(&temp, array + parent);                         \
    while (nmemb - parent > parent) {                   \
        if (GT(array + child + 1, array + child)) {     \
            ++child;                                    \
        }                                               \
        if (GT(array + child, &temp)) {                 \
            MOV(array + parent, array + child);         \
            parent = child;                             \
            child *= 2;                                 \
        } else {                                        \
            break;                                      \
        }                                               \
    }                                                   \
    if (nmemb == child && GT(array + child, &temp)) {   \
        MOV(array + parent, array + child);             \
        parent = child;                                 \
    }                                                   \
    MOV(array + parent, &temp);                         \
}

typedef E_TYPE;  

static void sisort(e_type *array, size_t nmemb)
{
    e_type *base, *low, *high, temp;

    if (nmemb-- > 1) {
        base = array;
        do {
            low = array++;
            if (GT(low, array)) {
                high = array;
                MOV(&temp, high);
                do {
                    MOV(high, low);
                    if (--high == base) {
                        break;
                    }
                    --low;
                } while (GT(low, &temp));
                MOV(high, &temp);
            }
        } while (--nmemb != 0);
    } 
}

static void jnloop(e_type *array, size_t nmemb, size_t d)
{
    e_type *i, *j, temp;
        
    while (nmemb > SMALL_PARTITION) {
        if (!d--) {
            hsortm(array, nmemb);
            return;
        }
        i = nmemb / 2 + array;
        SWAP(array, i, &temp);
        i = 1 + array;
        j = --nmemb + array;
        SORT_3(j, array, i, &temp);
        do {
            SWAP(j, i, &temp);
            do {
                ++i;
            } while (GT(array, i));
            do {
                --j;
            } while (GT(j, array));
        } while (j > i);
        SWAP(array, j, &temp);
        jnloop(j + 1, nmemb + array - j, d);
        nmemb = j - array;
    }
    sisort(array, nmemb);
}

static void hsortm(e_type *array, size_t nmemb)
{
    size_t p, child, parent;
    e_type temp;

    if (nmemb > 1) {
        p = --nmemb / 2;
        do {
            SIFTDOWNM(p);
        } while (p-- != 0);
        SWAP(array, array + nmemb, &temp);
        while (--nmemb != 0) {
            SIFTDOWNM(0);
            SWAP(array, array + nmemb, &temp);
        }
    }
}

static void QSORT(e_type *array, size_t nmemb)
{
    size_t d, n;
    
    assert(SMALL_PARTITION >= 4);
    d = 2;    
    for (n = nmemb / 4; n != 0; n /= 2) {
        ++d;        
    }
    jnloop(array, nmemb, 2 * d);
}

static int Sort(LIST_TYPE * l)
{
    LIST_ELEMENT   **tab;
    size_t          i;
    LIST_ELEMENT    *rvp;

    if (l == NULL)
        return iError.NullPtrError("Sort");

    if (l->count < 2)
        return 1;
    if (l->Flags & CONTAINER_READONLY) {
        l->RaiseError("iList.Sort", CONTAINER_ERROR_READONLY);
        return CONTAINER_ERROR_READONLY;
    }
    tab = l->Allocator->malloc(l->count * sizeof(LIST_ELEMENT *));
    if (tab == NULL) {
        l->RaiseError("iList.Sort", CONTAINER_ERROR_NOMEMORY);
        return CONTAINER_ERROR_NOMEMORY;
    }
    rvp = l->First;
    for (i = 0; i < l->count; i++) {
        tab[i] = rvp;
        rvp = rvp->Next;
    }
    QSORT(tab, l->count );
    for (i = 0; i < l->count - 1; i++) {
        tab[i]->Next = tab[i + 1];
    }
    tab[l->count - 1]->Next = NULL;
    l->Last = tab[l->count - 1];
    l->First = tab[0];
    l->Allocator->free(tab);
    return 1;

}
static LIST_TYPE *SetVTable(LIST_TYPE *result)
{
    static int Initialized;
    INTERFACE(DATA_TYPE) *intface = &INTERFACE_NAME(DATA_TYPE);
    
    result->VTable = intface;
    if (Initialized) return result;
    Initialized = 1;
    intface->FirstElement = (LIST_ELEMENT *(*)(LIST_TYPE
*))iList.FirstElement;
    intface->LastElement = (LIST_ELEMENT *(*)(LIST_TYPE
*))iList.LastElement;
    intface->Clear = (int (*)(LIST_TYPE *))iList.Clear;
    intface->EraseAt = (int (*)(LIST_TYPE *,size_t))iList.EraseAt;
    intface->RemoveRange = (int (*)(LIST_TYPE
*,size_t,size_t))iList.RemoveRange;
    intface->Select = (int (*)(LIST_TYPE *,const Mask *))iList.Select;
    intface->SetFlags = (unsigned (*)(LIST_TYPE
*,unsigned))iList.SetFlags;
    intface->GetFlags = (unsigned (*)(const LIST_TYPE *))iList.GetFlags;
    intface->SetDestructor = (DestructorFunction (*)(LIST_TYPE *,
DestructorFunction))iList.SetDestructor;
    intface->Apply = (int (*)(LIST_TYPE *, int (Applyfn) (DATA_TYPE *,
void * ), void *))iList.Apply;
    intface->Reverse = (int (*)(LIST_TYPE *))iList.Reverse;
    intface->SetCompareFunction = (CompareFunction (*)(LIST_TYPE *,
CompareFunction ))iList.SetCompareFunction;
    intface->GetRange = (LIST_TYPE *(*)(const LIST_TYPE * , size_t,
size_t))iList.GetRange;
    intface->Skip = (LIST_ELEMENT *(*)(LIST_ELEMENT *,
size_t))iList.Skip;
    intface->Append = (int (*)(LIST_TYPE *, LIST_TYPE *))iList.Append;
    intface->Equal = (int (*)(const LIST_TYPE *, const LIST_TYPE
*))iList.Equal;
    intface->InsertIn = (int (*)(LIST_TYPE *, size_t, LIST_TYPE
*))iList.InsertIn;
    intface->AddRange = (int (*)(LIST_TYPE *, size_t, const DATA_TYPE
*))iList.AddRange;
    intface->SetErrorFunction = (ErrorFunction (*)(LIST_TYPE *,
ErrorFunction))iList.SetErrorFunction;
    intface->SetFlags = (unsigned (*)(LIST_TYPE * l, unsigned
newval))iList.SetFlags;
    intface->RemoveRange = (int (*)(LIST_TYPE *, size_t,
size_t))iList.RemoveRange;
    intface->UseHeap = (int (*)(LIST_TYPE *, const ContainerAllocator
*))iList.UseHeap;
    intface->RotateLeft = (int (*)(LIST_TYPE *,
size_t))iList.RotateLeft;
    intface->RotateRight = (int (*)(LIST_TYPE *,
size_t))iList.RotateRight;
    intface->Save = (int (*)(const LIST_TYPE *, FILE *, SaveFunction,
void *))iList.Save;
    intface->Size = (size_t (*)(const LIST_TYPE *))iList.Size;
    intface->deleteIterator = (int (*)(Iterator *))iList.deleteIterator;
    intface->SplitAfter = (LIST_TYPE *(*)(LIST_TYPE *, LIST_ELEMENT
*))iList.SplitAfter;
    return result;
}

/*------------------------------------------------------------------------
 Procedure:     Create ID:1
 Purpose:       Allocates a new list object header, initializes the
                VTable field and the element size
 Input:         The size of the elements of the list.
 Output:        A pointer to the newly created list or NULL if
                there is no memory.
 Errors:        If element size is smaller than zero an error
                routine is called. If there is no memory result is
                NULL.

------------------------------------------------------------------------*/
static LIST_TYPE *CreateWithAllocator(size_t elementsize, const
ContainerAllocator * allocator)
{
    LIST_TYPE *result =  (LIST_TYPE
*)iList.CreateWithAllocator(sizeof(DATA_TYPE), allocator);
    return SetVTable(result);
}

static LIST_TYPE * Create(size_t elementsize)
{
    LIST_TYPE *result =  (LIST_TYPE
*)iList.CreateWithAllocator(sizeof(DATA_TYPE), CurrentAllocator);
    return SetVTable(result);
}

static LIST_TYPE *InitializeWith(size_t elementSize, size_t n, const
void *Data)
{
    LIST_TYPE *result = (LIST_TYPE
*)iList.InitializeWith(sizeof(DATA_TYPE),n,Data);
    return SetVTable(result);
}

static LIST_TYPE *InitWithAllocator(LIST_TYPE * result, size_t
elementsize,
          const ContainerAllocator * allocator)
{
    iList.InitWithAllocator((List *)result,sizeof(DATA_TYPE),allocator);
    return SetVTable(result);
}

static LIST_TYPE * Init(LIST_TYPE * result, size_t elementsize)
{
    return InitWithAllocator(result, elementsize, CurrentAllocator);
}

static const ContainerAllocator *GetAllocator(const LIST_TYPE * l)
{
    if (l == NULL)
        return NULL;
    return l->Allocator;
}

static LIST_ELEMENT *NextElement(LIST_ELEMENT *le)
{
    if (le == NULL) return NULL;
    return le->Next;
}

static DATA_TYPE ElementData(LIST_ELEMENT *le)
{
    if (le == NULL) return ERROR_RETURN;
    return le->Data;
}

static int SetElementData(LIST_TYPE *l,LIST_ELEMENT *le,DATA_TYPE data)
{
    return iList.SetElementData((List *)l,(ListElement *)le,&data);
}

static DATA_TYPE Advance(LIST_ELEMENT **ple)
{
    LIST_ELEMENT *le;
    DATA_TYPE result;

    if (ple == NULL) {
        iError.NullPtrError("Advance");
        return ERROR_RETURN;
    }
    le = *ple;
    if (le == NULL) return ERROR_RETURN;
    result = le->Data;
    le = le->Next;
    *ple = le;
    return result;
}

INTERFACE(DATA_TYPE)   INTERFACE_NAME(DATA_TYPE) = {
    NULL,         // Size
    NULL,         // GetFlags,
    NULL,         // SetFlags,
    NULL,         // Clear,
    Contains,
    Erase,
    EraseAll,
    Finalize,
    NULL,         // Apply
    NULL,         // Equal
    Copy,
    NULL,         // SetErrorFunction,
    Sizeof,
    NewIterator,
    InitIterator,
    NULL,         // deleteIterator,
    SizeofIterator,
    NULL,          // Save,
    Load,
    GetElementSize,
    /* end of generic part */
    Add,
    GetElement,
    PushFront,
    PopFront,
    InsertAt,
    NULL,         // EraseAt
    ReplaceAt,
    IndexOf,
    /* End of sequential container part */
    NULL,        // InsertIn,
    CopyElement,
    NULL,        // EraseRange,
    Sort,
    NULL,        // Reverse,
    NULL,        // GetRange,
    NULL,        // Append,
    NULL,        // SetCompareFunction,
    DefaultListCompareFunction,
    NULL,        // UseHeap,
    NULL,        // AddRange,
    Create,
    CreateWithAllocator,
    Init,
    InitWithAllocator,
    GetAllocator,
    NULL,          // SetDestructor
    InitializeWith,
    Back,
    Front,
    NULL,          // RemoveRange,
    NULL,          // RotateLeft,
    NULL,          // RotateRight,
    NULL,          // Select,
    SelectCopy,
    NULL,          // FirstElement,
    NULL,          // LastElement,
    NextElement,
    ElementData,
    SetElementData,
    Advance,
    NULL,          // Skip,
    NULL,          // SplitAfter,
};
/* END listgen.c */

-- 
pete

[toc] | [prev] | [next] | [standalone]

#22113

pete於 2012年6月10日星期日UTC+8上午11時49分21秒寫道：
> jacob navia wrote:
> 
> > Maybe you have some spare time?
> > 
> > I am convinced my code would benefit from your critical eye Pete.
> > 
> > Just download it from
> > 
> > http://code.google.com/p/ccl/
> > 
> > and look at it.
> > The file listgen.c contains the templated sort function.
> 
> /*
> ** On 6 September 2008, I posted pqsort.
> **
> ** http://groups.google.com/group/comp.lang.c/msg/6a73e359f4814457
> **
> ** This is a version of listgen.c with a new QSORT based on pqsort.
> ** It's an introspective quicksort.
> ** If you like, I can toss in a PRNG for the pivot selection.
> ** Try it.
> */
> /* BEGIN listgen.c */
> /*
>  * Value types generic list routines sample implementation 
>  * ----------------------------------- ------------------
>  * Thisroutines handle the List container class. This is a very general
>  * implementation and efficiency considerations aren't yet primordial.
> Lists
>  * can have elements of any size. This implement single linked Lists.
> The
>  * design goals here are just correctness and showing how the
> implementation
>  * of the proposed interface COULD be done.
>  *
> ----------------------------------------------------------------------
>  */
> 
> #include "listgen.h"
> #include "ccl_internal.h"
> 
> #include <assert.h>
> 
> /* Forward declarations */
> static LIST_TYPE *SetVTable(LIST_TYPE *result);
> static LIST_TYPE * Create(size_t elementsize);
> static LIST_TYPE *CreateWithAllocator(size_t elementsize, const
> ContainerAllocator * allocator);
> #define CONTAINER_LIST_SMALL    2
> #define CHUNK_SIZE    1000
> 
> static int DefaultListCompareFunction(const void * left, const void *
> right, CompareInfo * ExtraArgs)
> {
>     size_t          siz = ((LIST_TYPE *)
> ExtraArgs->ContainerLeft)->ElementSize;
>     return memcmp(left, right, siz);
> }
> 
> /*------------------------------------------------------------------------
>  Procedure:     Contains ID:1
>  Purpose:       Determines if the given data is in the container
>  Input:         The list and the data to be searched
>  Output:        Returns 1 (true) if the data is in there, false
>                 otherwise
>  Errors:        The same as the function IndexOf
> ------------------------------------------------------------------------*/
> static int Contains(const LIST_TYPE * l, const DATA_TYPE data)
> {
>     size_t idx;
>     return (iList.IndexOf((List *)l, &data, NULL, &idx) < 0) ? 0 : 1;
> }
> 
> static int Add(LIST_TYPE * l, const DATA_TYPE elem)
> {
>     return iList.Add((List *)l,&elem);
> }
> 
> /*------------------------------------------------------------------------
>  Procedure:     GetElement ID:1
>  Purpose:       Returns the data associated with a given position
>  Input:         The list and the position
>  Output:        A pointer to the data
>  Errors:        NULL if error in the positgion index
> ------------------------------------------------------------------------*/
> static DATA_TYPE GetElement(const LIST_TYPE * l, size_t position)
> {
>     DATA_TYPE *pdata = iList.GetElement((List *)l,position);
> 
>     if (pdata == NULL) return ERROR_RETURN;
>     return *pdata;
> }
> 
> static DATA_TYPE Back(const LIST_TYPE * l)
> {
>     DATA_TYPE *p = (DATA_TYPE *)iList.Back((List *)l);
>     if (p == NULL) return ERROR_RETURN;
>     return *p;
> }
> 
> static DATA_TYPE Front(const LIST_TYPE * l)
> {
>     DATA_TYPE *p = (DATA_TYPE *)iList.Front((List *)l);
>     if (p == NULL) return ERROR_RETURN;
>     return *p;
> }
> 
> static int CopyElement(const LIST_TYPE * l, size_t position, DATA_TYPE
> *outBuffer)
> {
>     return iList.CopyElement((List *)l,position,outBuffer);
> }
> 
> static int ReplaceAt(LIST_TYPE * l, size_t position, const DATA_TYPE
> data)
> {
>     return iList.ReplaceAt((List *)l,position,&data);;
> }
> 
> static int PushFront(LIST_TYPE * l, const DATA_TYPE pdata)
> {
>     return iList.PushFront((List *)l,&pdata);
> }
> 
> 
> static int PopFront(LIST_TYPE * l, DATA_TYPE *result)
> {
>     return iList.PushFront((List *)l,result);
> }
> 
> 
> static int InsertAt(LIST_TYPE * l, size_t pos, const DATA_TYPE pdata)
> {
>     return iList.InsertAt((List *)l,pos,&pdata);
> }
> 
> static int Erase(LIST_TYPE * l, const DATA_TYPE elem)
> {
>     return iList.Erase((List *)l, &elem);
> }
> 
> static int EraseAll(LIST_TYPE * l, const DATA_TYPE elem)
> {
>     return iList.EraseAll((List *)l, &elem);
> }
> 
> static int IndexOf(const LIST_TYPE * l, const DATA_TYPE ElementToFind,
> void *ExtraArgs, size_t * result)
> {
>     return iList.IndexOf((List *)l, &ElementToFind, ExtraArgs, result);
> }
> 
> static size_t Sizeof(const LIST_TYPE * l)
> {
>     if (l == NULL) {
>         return sizeof(List);
>     }
>     return sizeof(LIST_TYPE) + l->ElementSize * l->count + l->count *
> offsetof(LIST_ELEMENT,Data);
> }
> 
> static size_t SizeofIterator(const LIST_TYPE * l)
> {
>     return sizeof(struct ITERATOR(DATA_TYPE));
> }
> 
> static LIST_TYPE *Load(FILE * stream, ReadFunction loadFn, void *arg)
> {
>     LIST_TYPE *result = (LIST_TYPE *)iList.Load(stream,loadFn,arg);
>     return SetVTable(result);
> }
> 
> /*
>  *
> ---------------------------------------------------------------------------
>  *
>  *                           Iterators
>  *
>  *
> ---------------------------------------------------------------------------
>  */
> static int ReplaceWithIterator(Iterator * it, DATA_TYPE data, int
> direction)
> {
>     struct ITERATOR(DATA_TYPE) *iter = (struct ITERATOR(DATA_TYPE) *)it;
>     return iter->ListReplace(it,&data,direction);
> }
> 
> static Iterator *SetupIteratorVTable(struct ITERATOR(DATA_TYPE) *result)
> {
>     if (result == NULL) return NULL;
>     result->ListReplace = result->it.Replace;
>     result->it.Replace = (int (*)(Iterator * , void * , int
> ))ReplaceWithIterator;
>     return &result->it;
> }
> 
> static Iterator *NewIterator(LIST_TYPE * L)
> {
>     return SetupIteratorVTable((struct ITERATOR(DATA_TYPE)
> *)iList.NewIterator((List *)L));
> }
> static int InitIterator(LIST_TYPE * L, void *r)
> {
>     iList.InitIterator((List *)L,r);
>     SetupIteratorVTable(r);
>     return 1;
> }
> static size_t GetElementSize(const LIST_TYPE * l)
> {
>     return sizeof(DATA_TYPE);
> }
> 
> static int Finalize(LIST_TYPE *l)
> {
>     iList.Finalize((List *)l);
>     return 1;
> }
> 
> static LIST_TYPE  *Copy(const LIST_TYPE * l)
> {
>     LIST_TYPE *result = (LIST_TYPE *)iList.Copy((List *)l);
>     return SetVTable(result);
> }
> 
> 
> static LIST_TYPE *SelectCopy(const LIST_TYPE *l,const Mask *m)
> {
>     LIST_TYPE *result = (LIST_TYPE *)iList.SelectCopy((const List
> *)l,m);
>     return SetVTable(result);
> }
> 
> /*---------------------------------------------------------------------------*/
> /* qsort() - perform a quicksort on an
> array                                 */
> /*---------------------------------------------------------------------------*/
> 
> #ifndef COMPARE_EXPRESSION
> #error foo
> #define COMPARE_EXPRESSION(l,lo) comp(l, lo)
> //COMPAR(A, B) (B > A ? -1 : B != A)
> #endif
> 
> #define E_TYPE          LIST_ELEMENT *e_type
> #define GT(A, B)        (COMPARE_EXPRESSION((A), (B)) > 0)
> #define MOV(A, B)       ((void)(*(A) = *(B)))
> #define SMALL_PARTITION 8
> 
> #define SWAP(A, B, T)                                   \
>     (MOV((T), (A)), MOV((A), (B)), MOV((B), (T)))
> 
> #define SORT_3(A, B, C, T)                              \
>     if (GT((A), (B))) {                                 \
>         MOV((T), (A));                                  \
>         if (GT((C), (B))) {                             \
>             MOV((A), (B));                              \
>             if (GT((T), (C))) {                         \
>                 MOV((B), (C));                          \
>                 MOV((C), (T));                          \
>             } else {                                    \
>                 MOV((B), (T));                          \
>             }                                           \
>         } else {                                        \
>             MOV((A), (C));                              \
>             MOV((C), (T));                              \
>         }                                               \
>     } else {                                            \
>         if (GT((B), (C))) {                             \
>             MOV((T), (B));                              \
>             if (GT((A), (C))) {                         \
>                 MOV((B), (A));                          \
>                 MOV((A), (C));                          \
>             } else {                                    \
>                 MOV((B), (C));                          \
>             }                                           \
>             MOV((C), (T));                              \
>         }                                               \
>     }
> 
> #define SIFTDOWNM(P)                                    \
> {                                                       \
>     parent = (P);                                       \
>     child = parent * 2;                                 \
>     MOV(&temp, array + parent);                         \
>     while (nmemb - parent > parent) {                   \
>         if (GT(array + child + 1, array + child)) {     \
>             ++child;                                    \
>         }                                               \
>         if (GT(array + child, &temp)) {                 \
>             MOV(array + parent, array + child);         \
>             parent = child;                             \
>             child *= 2;                                 \
>         } else {                                        \
>             break;                                      \
>         }                                               \
>     }                                                   \
>     if (nmemb == child && GT(array + child, &temp)) {   \
>         MOV(array + parent, array + child);             \
>         parent = child;                                 \
>     }                                                   \
>     MOV(array + parent, &temp);                         \
> }
> 
> typedef E_TYPE;  
> 
> static void sisort(e_type *array, size_t nmemb)
> {
>     e_type *base, *low, *high, temp;
> 
>     if (nmemb-- > 1) {
>         base = array;
>         do {
>             low = array++;
>             if (GT(low, array)) {
>                 high = array;
>                 MOV(&temp, high);
>                 do {
>                     MOV(high, low);
>                     if (--high == base) {
>                         break;
>                     }
>                     --low;
>                 } while (GT(low, &temp));
>                 MOV(high, &temp);
>             }
>         } while (--nmemb != 0);
>     } 

This part is the heap sort here. 

In my experience this is good in sorting  for more than 30 elelments.

If the length of the unsorted array is considered, then one might need
3 to 4 sorting procedures to cover the desired range of the lengths of the arrays for the critical part.





> static void jnloop(e_type *array, size_t nmemb, size_t d)
> {
>     e_type *i, *j, temp;
>         
>     while (nmemb > SMALL_PARTITION) {
>         if (!d--) {
>             hsortm(array, nmemb);
>             return;
>         }
>         i = nmemb / 2 + array;
>         SWAP(array, i, &temp);
>         i = 1 + array;
>         j = --nmemb + array;
>         SORT_3(j, array, i, &temp);
>         do {
>             SWAP(j, i, &temp);
>             do {
>                 ++i;
>             } while (GT(array, i));
>             do {
>                 --j;
>             } while (GT(j, array));
>         } while (j > i);
>         SWAP(array, j, &temp);
>         jnloop(j + 1, nmemb + array - j, d);
>         nmemb = j - array;
>     }
>     sisort(array, nmemb);
> }
> 
> static void hsortm(e_type *array, size_t nmemb)
> {
>     size_t p, child, parent;
>     e_type temp;
> 
>     if (nmemb > 1) {
>         p = --nmemb / 2;
>         do {
>             SIFTDOWNM(p);
>         } while (p-- != 0);
>         SWAP(array, array + nmemb, &temp);
>         while (--nmemb != 0) {
>             SIFTDOWNM(0);
>             SWAP(array, array + nmemb, &temp);
>         }
>     }
> }
> 
> static void QSORT(e_type *array, size_t nmemb)
> {
>     size_t d, n;
>     
>     assert(SMALL_PARTITION >= 4);
>     d = 2;    
>     for (n = nmemb / 4; n != 0; n /= 2) {
>         ++d;        
>     }
>     jnloop(array, nmemb, 2 * d);
> }
> 
> static int Sort(LIST_TYPE * l)
> {
>     LIST_ELEMENT   **tab;
>     size_t          i;
>     LIST_ELEMENT    *rvp;
> 
>     if (l == NULL)
>         return iError.NullPtrError("Sort");
> 
>     if (l->count < 2)
>         return 1;
>     if (l->Flags & CONTAINER_READONLY) {
>         l->RaiseError("iList.Sort", CONTAINER_ERROR_READONLY);
>         return CONTAINER_ERROR_READONLY;
>     }
>     tab = l->Allocator->malloc(l->count * sizeof(LIST_ELEMENT *));
>     if (tab == NULL) {
>         l->RaiseError("iList.Sort", CONTAINER_ERROR_NOMEMORY);
>         return CONTAINER_ERROR_NOMEMORY;
>     }
>     rvp = l->First;
>     for (i = 0; i < l->count; i++) {
>         tab[i] = rvp;
>         rvp = rvp->Next;
>     }
>     QSORT(tab, l->count );
>     for (i = 0; i < l->count - 1; i++) {
>         tab[i]->Next = tab[i + 1];
>     }
>     tab[l->count - 1]->Next = NULL;
>     l->Last = tab[l->count - 1];
>     l->First = tab[0];
>     l->Allocator->free(tab);
>     return 1;
> 
> }
> static LIST_TYPE *SetVTable(LIST_TYPE *result)
> {
>     static int Initialized;
>     INTERFACE(DATA_TYPE) *intface = &INTERFACE_NAME(DATA_TYPE);
>     
>     result->VTable = intface;
>     if (Initialized) return result;
>     Initialized = 1;
>     intface->FirstElement = (LIST_ELEMENT *(*)(LIST_TYPE
> *))iList.FirstElement;
>     intface->LastElement = (LIST_ELEMENT *(*)(LIST_TYPE
> *))iList.LastElement;
>     intface->Clear = (int (*)(LIST_TYPE *))iList.Clear;
>     intface->EraseAt = (int (*)(LIST_TYPE *,size_t))iList.EraseAt;
>     intface->RemoveRange = (int (*)(LIST_TYPE
> *,size_t,size_t))iList.RemoveRange;
>     intface->Select = (int (*)(LIST_TYPE *,const Mask *))iList.Select;
>     intface->SetFlags = (unsigned (*)(LIST_TYPE
> *,unsigned))iList.SetFlags;
>     intface->GetFlags = (unsigned (*)(const LIST_TYPE *))iList.GetFlags;
>     intface->SetDestructor = (DestructorFunction (*)(LIST_TYPE *,
> DestructorFunction))iList.SetDestructor;
>     intface->Apply = (int (*)(LIST_TYPE *, int (Applyfn) (DATA_TYPE *,
> void * ), void *))iList.Apply;
>     intface->Reverse = (int (*)(LIST_TYPE *))iList.Reverse;
>     intface->SetCompareFunction = (CompareFunction (*)(LIST_TYPE *,
> CompareFunction ))iList.SetCompareFunction;
>     intface->GetRange = (LIST_TYPE *(*)(const LIST_TYPE * , size_t,
> size_t))iList.GetRange;
>     intface->Skip = (LIST_ELEMENT *(*)(LIST_ELEMENT *,
> size_t))iList.Skip;
>     intface->Append = (int (*)(LIST_TYPE *, LIST_TYPE *))iList.Append;
>     intface->Equal = (int (*)(const LIST_TYPE *, const LIST_TYPE
> *))iList.Equal;
>     intface->InsertIn = (int (*)(LIST_TYPE *, size_t, LIST_TYPE
> *))iList.InsertIn;
>     intface->AddRange = (int (*)(LIST_TYPE *, size_t, const DATA_TYPE
> *))iList.AddRange;
>     intface->SetErrorFunction = (ErrorFunction (*)(LIST_TYPE *,
> ErrorFunction))iList.SetErrorFunction;
>     intface->SetFlags = (unsigned (*)(LIST_TYPE * l, unsigned
> newval))iList.SetFlags;
>     intface->RemoveRange = (int (*)(LIST_TYPE *, size_t,
> size_t))iList.RemoveRange;
>     intface->UseHeap = (int (*)(LIST_TYPE *, const ContainerAllocator
> *))iList.UseHeap;
>     intface->RotateLeft = (int (*)(LIST_TYPE *,
> size_t))iList.RotateLeft;
>     intface->RotateRight = (int (*)(LIST_TYPE *,
> size_t))iList.RotateRight;
>     intface->Save = (int (*)(const LIST_TYPE *, FILE *, SaveFunction,
> void *))iList.Save;
>     intface->Size = (size_t (*)(const LIST_TYPE *))iList.Size;
>     intface->deleteIterator = (int (*)(Iterator *))iList.deleteIterator;
>     intface->SplitAfter = (LIST_TYPE *(*)(LIST_TYPE *, LIST_ELEMENT
> *))iList.SplitAfter;
>     return result;
> }
> 
> /*------------------------------------------------------------------------
>  Procedure:     Create ID:1
>  Purpose:       Allocates a new list object header, initializes the
>                 VTable field and the element size
>  Input:         The size of the elements of the list.
>  Output:        A pointer to the newly created list or NULL if
>                 there is no memory.
>  Errors:        If element size is smaller than zero an error
>                 routine is called. If there is no memory result is
>                 NULL.
> 
> ------------------------------------------------------------------------*/
> static LIST_TYPE *CreateWithAllocator(size_t elementsize, const
> ContainerAllocator * allocator)
> {
>     LIST_TYPE *result =  (LIST_TYPE
> *)iList.CreateWithAllocator(sizeof(DATA_TYPE), allocator);
>     return SetVTable(result);
> }
> 
> static LIST_TYPE * Create(size_t elementsize)
> {
>     LIST_TYPE *result =  (LIST_TYPE
> *)iList.CreateWithAllocator(sizeof(DATA_TYPE), CurrentAllocator);
>     return SetVTable(result);
> }
> 
> static LIST_TYPE *InitializeWith(size_t elementSize, size_t n, const
> void *Data)
> {
>     LIST_TYPE *result = (LIST_TYPE
> *)iList.InitializeWith(sizeof(DATA_TYPE),n,Data);
>     return SetVTable(result);
> }
> 
> static LIST_TYPE *InitWithAllocator(LIST_TYPE * result, size_t
> elementsize,
>           const ContainerAllocator * allocator)
> {
>     iList.InitWithAllocator((List *)result,sizeof(DATA_TYPE),allocator);
>     return SetVTable(result);
> }
> 
> static LIST_TYPE * Init(LIST_TYPE * result, size_t elementsize)
> {
>     return InitWithAllocator(result, elementsize, CurrentAllocator);
> }
> 
> static const ContainerAllocator *GetAllocator(const LIST_TYPE * l)
> {
>     if (l == NULL)
>         return NULL;
>     return l->Allocator;
> }
> 
> static LIST_ELEMENT *NextElement(LIST_ELEMENT *le)
> {
>     if (le == NULL) return NULL;
>     return le->Next;
> }
> 
> static DATA_TYPE ElementData(LIST_ELEMENT *le)
> {
>     if (le == NULL) return ERROR_RETURN;
>     return le->Data;
> }
> 
> static int SetElementData(LIST_TYPE *l,LIST_ELEMENT *le,DATA_TYPE data)
> {
>     return iList.SetElementData((List *)l,(ListElement *)le,&data);
> }
> 
> static DATA_TYPE Advance(LIST_ELEMENT **ple)
> {
>     LIST_ELEMENT *le;
>     DATA_TYPE result;
> 
>     if (ple == NULL) {
>         iError.NullPtrError("Advance");
>         return ERROR_RETURN;
>     }
>     le = *ple;
>     if (le == NULL) return ERROR_RETURN;
>     result = le->Data;
>     le = le->Next;
>     *ple = le;
>     return result;
> }
> 
> INTERFACE(DATA_TYPE)   INTERFACE_NAME(DATA_TYPE) = {
>     NULL,         // Size
>     NULL,         // GetFlags,
>     NULL,         // SetFlags,
>     NULL,         // Clear,
>     Contains,
>     Erase,
>     EraseAll,
>     Finalize,
>     NULL,         // Apply
>     NULL,         // Equal
>     Copy,
>     NULL,         // SetErrorFunction,
>     Sizeof,
>     NewIterator,
>     InitIterator,
>     NULL,         // deleteIterator,
>     SizeofIterator,
>     NULL,          // Save,
>     Load,
>     GetElementSize,
>     /* end of generic part */
>     Add,
>     GetElement,
>     PushFront,
>     PopFront,
>     InsertAt,
>     NULL,         // EraseAt
>     ReplaceAt,
>     IndexOf,
>     /* End of sequential container part */
>     NULL,        // InsertIn,
>     CopyElement,
>     NULL,        // EraseRange,
>     Sort,
>     NULL,        // Reverse,
>     NULL,        // GetRange,
>     NULL,        // Append,
>     NULL,        // SetCompareFunction,
>     DefaultListCompareFunction,
>     NULL,        // UseHeap,
>     NULL,        // AddRange,
>     Create,
>     CreateWithAllocator,
>     Init,
>     InitWithAllocator,
>     GetAllocator,
>     NULL,          // SetDestructor
>     InitializeWith,
>     Back,
>     Front,
>     NULL,          // RemoveRange,
>     NULL,          // RotateLeft,
>     NULL,          // RotateRight,
>     NULL,          // Select,
>     SelectCopy,
>     NULL,          // FirstElement,
>     NULL,          // LastElement,
>     NextElement,
>     ElementData,
>     SetElementData,
>     Advance,
>     NULL,          // Skip,
>     NULL,          // SplitAfter,
> };
> /* END listgen.c */
> 
> -- 
> pete

[toc] | [prev] | [next] | [standalone]

#22131

88888 Dihedral wrote:
> 
> pete於 2012年6月10日星期日UTC+8上午11時49分21秒寫道：
> > jacob navia wrote:
> >
> > > Maybe you have some spare time?

> > ** This is a version of listgen.c with a new QSORT based on pqsort.
> > ** It's an introspective quicksort.
> > ** If you like, I can toss in a PRNG for the pivot selection.


> > /*---------------------------------------------------------------------------*/
> > /* qsort() - perform a quicksort on an
> > array                                 */
> > /*---------------------------------------------------------------------------*/
> >
> > #ifndef COMPARE_EXPRESSION
> > #error foo
> > #define COMPARE_EXPRESSION(l,lo) comp(l, lo)
> > //COMPAR(A, B) (B > A ? -1 : B != A)
> > #endif
> >
> > #define E_TYPE          LIST_ELEMENT *e_type
> > #define GT(A, B)        (COMPARE_EXPRESSION((A), (B)) > 0)
> > #define MOV(A, B)       ((void)(*(A) = *(B)))
> > #define SMALL_PARTITION 8
> >
> > #define SWAP(A, B, T)                                   \
> >     (MOV((T), (A)), MOV((A), (B)), MOV((B), (T)))
> >
> > #define SORT_3(A, B, C, T)                              \
> >     if (GT((A), (B))) {                                 \
> >         MOV((T), (A));                                  \
> >         if (GT((C), (B))) {                             \
> >             MOV((A), (B));                              \
> >             if (GT((T), (C))) {                         \
> >                 MOV((B), (C));                          \
> >                 MOV((C), (T));                          \
> >             } else {                                    \
> >                 MOV((B), (T));                          \
> >             }                                           \
> >         } else {                                        \
> >             MOV((A), (C));                              \
> >             MOV((C), (T));                              \
> >         }                                               \
> >     } else {                                            \
> >         if (GT((B), (C))) {                             \
> >             MOV((T), (B));                              \
> >             if (GT((A), (C))) {                         \
> >                 MOV((B), (A));                          \
> >                 MOV((A), (C));                          \
> >             } else {                                    \
> >                 MOV((B), (C));                          \
> >             }                                           \
> >             MOV((C), (T));                              \
> >         }                                               \
> >     }
> >
> > #define SIFTDOWNM(P)                                    \
> > {                                                       \
> >     parent = (P);                                       \
> >     child = parent * 2;                                 \
> >     MOV(&temp, array + parent);                         \
> >     while (nmemb - parent > parent) {                   \
> >         if (GT(array + child + 1, array + child)) {     \
> >             ++child;                                    \
> >         }                                               \
> >         if (GT(array + child, &temp)) {                 \
> >             MOV(array + parent, array + child);         \
> >             parent = child;                             \
> >             child *= 2;                                 \
> >         } else {                                        \
> >             break;                                      \
> >         }                                               \
> >     }                                                   \
> >     if (nmemb == child && GT(array + child, &temp)) {   \
> >         MOV(array + parent, array + child);             \
> >         parent = child;                                 \
> >     }                                                   \
> >     MOV(array + parent, &temp);                         \
> > }
> >
> > typedef E_TYPE;
> >
> > static void sisort(e_type *array, size_t nmemb)
> > {
> >     e_type *base, *low, *high, temp;
> >
> >     if (nmemb-- > 1) {
> >         base = array;
> >         do {
> >             low = array++;
> >             if (GT(low, array)) {
> >                 high = array;
> >                 MOV(&temp, high);
> >                 do {
> >                     MOV(high, low);
> >                     if (--high == base) {
> >                         break;
> >                     }
> >                     --low;
> >                 } while (GT(low, &temp));
> >                 MOV(high, &temp);
> >             }
> >         } while (--nmemb != 0);
> >     }
> 
> This part is the heap sort here. 
> In my experience this is good in sorting  for more than 30 elelments.
> 
> If the length of the unsorted array is considered, then one might need
> 3 to 4 sorting procedures to cover the desired range of the lengths of the arrays for the critical part.

sisort is an insertion sort.
hsortm is a heap sort.
QSORT, as implemented in this post, is an introsort.
The purpose of the heap sort is to take over
and keep the sort O(N*log(N))
in case of the quick sort starting to go quadratic.

http://en.wikipedia.org/wiki/Introsort

> > static void jnloop(e_type *array, size_t nmemb, size_t d)
> > {
> >     e_type *i, *j, temp;
> >
> >     while (nmemb > SMALL_PARTITION) {
> >         if (!d--) {
> >             hsortm(array, nmemb);
> >             return;
> >         }
> >         i = nmemb / 2 + array;
> >         SWAP(array, i, &temp);
> >         i = 1 + array;
> >         j = --nmemb + array;
> >         SORT_3(j, array, i, &temp);
> >         do {
> >             SWAP(j, i, &temp);
> >             do {
> >                 ++i;
> >             } while (GT(array, i));
> >             do {
> >                 --j;
> >             } while (GT(j, array));
> >         } while (j > i);
> >         SWAP(array, j, &temp);
> >         jnloop(j + 1, nmemb + array - j, d);
> >         nmemb = j - array;
> >     }
> >     sisort(array, nmemb);
> > }
> >
> > static void hsortm(e_type *array, size_t nmemb)
> > {
> >     size_t p, child, parent;
> >     e_type temp;
> >
> >     if (nmemb > 1) {
> >         p = --nmemb / 2;
> >         do {
> >             SIFTDOWNM(p);
> >         } while (p-- != 0);
> >         SWAP(array, array + nmemb, &temp);
> >         while (--nmemb != 0) {
> >             SIFTDOWNM(0);
> >             SWAP(array, array + nmemb, &temp);
> >         }
> >     }
> > }
> >
> > static void QSORT(e_type *array, size_t nmemb)
> > {
> >     size_t d, n;
> >
> >     assert(SMALL_PARTITION >= 4);
> >     d = 2;
> >     for (n = nmemb / 4; n != 0; n /= 2) {
> >         ++d;
> >     }
> >     jnloop(array, nmemb, 2 * d);
> > }
> >
> > static int Sort(LIST_TYPE * l)
> > {
> >     LIST_ELEMENT   **tab;
> >     size_t          i;
> >     LIST_ELEMENT    *rvp;
> >
> >     if (l == NULL)
> >         return iError.NullPtrError("Sort");
> >
> >     if (l->count < 2)
> >         return 1;
> >     if (l->Flags & CONTAINER_READONLY) {
> >         l->RaiseError("iList.Sort", CONTAINER_ERROR_READONLY);
> >         return CONTAINER_ERROR_READONLY;
> >     }
> >     tab = l->Allocator->malloc(l->count * sizeof(LIST_ELEMENT *));
> >     if (tab == NULL) {
> >         l->RaiseError("iList.Sort", CONTAINER_ERROR_NOMEMORY);
> >         return CONTAINER_ERROR_NOMEMORY;
> >     }
> >     rvp = l->First;
> >     for (i = 0; i < l->count; i++) {
> >         tab[i] = rvp;
> >         rvp = rvp->Next;
> >     }
> >     QSORT(tab, l->count );
> >     for (i = 0; i < l->count - 1; i++) {
> >         tab[i]->Next = tab[i + 1];
> >     }
> >     tab[l->count - 1]->Next = NULL;
> >     l->Last = tab[l->count - 1];
> >     l->First = tab[0];
> >     l->Allocator->free(tab);
> >     return 1;
> >

-- 
pete

[toc] | [prev] | [next] | [standalone]

#21836

On 06/ 4/12 11:38 PM, jacob navia wrote:
> Hi
>
> In a recent discussion ("Open letter to Ian Collins") we found out that
> the main problem in the C containers library was the time taken by the
> Sort function.
>
> The reasons for that is that it was a general sort function calling a
> general comparison function that uses memcmp...
>
> The first step to improve performance was to write data type specific
> functions using a data type generic file. As a bonus, we get compile
> time checking and better syntax.
>
> Still, the generic sort function was taking a lot of time.
>
> I have written then a data type generic quick sort function that
> receives as a parameter a macro that is used to compare two elements.
> This vastly improves performance.
>
> The times are:
>
> Generic sort function without any specialized heap
> (using malloc)
> real	0m17.029s
> user	0m16.654s
> sys	0m0.368s
>
> Generic sort function using a specialized heap
> (reduces the malloc overhead)
> real	0m11.759s
> user	0m11.500s
> sys	0m0.252s
>
> "Templated" sort function using a macro parameter
> (reduces comparisons to a simple expression)
> real	0m6.453s
> user	0m6.165s
> sys	0m0.281s
>
> The expression used to compare two list elements is:
> #define COMPARE_EXPRESSION(A, B) \
>       ((*B)->Data>  (*A)->Data ? -1 : (*B)->Data != (*A)->Data)
>
> I thank Pete for that proposal, I wouldn't have come to it
> alone :-)
>
> I would like to have the corresponding C++ times but I fear that
> if I write it it would be unfair since I am not a C++ wizard...

I don't have the original code to had, but looking back at the original 
thread, the C++ list sort was 5x faster, so I guess from your numbers it 
is now 2-3 times faster.

-- 
Ian Collins

[toc] | [prev] | [next] | [standalone]

Page 2 of 3 — ← Prev page 1 [2] 3  Next page →

Back to top | Article view | comp.lang.c

csiph-web