Board index » delphi » TList.Sort Access Violation

TList.Sort Access Violation

I've got a TList that I created and I'm trying to sort it, however, it keeps
blowing up with an "Access Violation" error.  Here is some of my code:

{here is my define for CalcOrd record}
type
   pCalcOrd = ^CalcOrd;
   CalcOrd = Record
      Order : Double;
      Count : Integer;
   end;

{...skipped a bunch of code...}

aCalcOrd := TList.Create;

{some code to fill up aCalcOrd, (also skipped some code)}

rRecpRec := aRecs[X];
New(rCalcOrd);
rCalcOrd^.Order := rRecpRec.Order;
rCalcOrd^.Count := 1;
aCalcOrd.Add(rCalcOrd);

{by the time I get to this point, aCalcOrd has only one record}
aCalcOrd.Sort(CalcSort);

Here is my CalcSort function:
function CalcSort(Item1, Item2: Pointer) : Integer;
Var
   nOrder1, nOrder2 : Double;
   nCount1, nCount2 : Integer;
Begin
   Result := 0;
   {Blows up on the following line when it hits this function the 3rd time.
   nOrder1 := pCalcOrd(Item1)^.Order;
   nOrder2 := pCalcOrd(Item2)^.Order;
   nCount1 := pCalcOrd(Item1)^.Count;
   nCount2 := pCalcOrd(Item2)^.Count;
   if nCount1 = nCount2 then
      if nOrder1 < nOrder2 then
         Result := -1
      else
         Result := 1
   else
      if nCount1 > nCount2 then
         Result := 1
      else
         Result := -1;
end;

There is only one element in aCalcOrd.  My first question is, Why is it
hitting this function 3 times??  My second question is, why does Item1
appear not to be empty (Access Violation) on the 3rd try?

Any help you can offer is appreciated.

Thanks,
Jesse

 

Re:TList.Sort Access Violation


Quote
Jesse Castleberry wrote in message <6nqih0$lt...@news10.ispnews.com>...
>I've got a TList that I created and I'm trying to sort it, however, it
keeps
>blowing up with an "Access Violation" error.  Here is some of my code:
[ ]
>There is only one element in aCalcOrd.  My first question is, Why is it
>hitting this function 3 times??  My second question is, why does Item1
>appear not to be empty (Access Violation) on the 3rd try?

The TList somehow thinks there's more than one item.
Recall that TList range is 0..N

I can't tell anything else from the posted code.
--
Grace + Peace | Peter N Roth | Engineering Objects Int'l
     Now shipping the CatapultEngine? for Delphi 3+
                http://www.inconresearch.com/eoi

Re:TList.Sort Access Violation


In article <6nqih0$lt...@news10.ispnews.com>

Quote
"Jesse Castleberry" <D...@iThink.net> writes:
> There is only one element in aCalcOrd.  My first question is, Why is it
> hitting this function 3 times??  My second question is, why does Item1
> appear not to be empty (Access Violation) on the 3rd try?

TList.Sort might be hitting your compare function thrice because Sort
uses a quick sort routine if I remember correctly. You'd have to
research the quick sort algorithm to know for sure how many iterations
the algorithm must go through before finishing.

No doubt the sort routine probably swapped Item1 for Item2 at some
point, and perhaps did not clear out the pointer as expected. (pointers
typically have to be reset to nil in Delphi by hand, but which can also
easily be overlooked).

===========================
Mike Powell
mi...@rt66.com
http://www.rt66.com/~mikep/

Re:TList.Sort Access Violation


Quote
>The TList somehow thinks there's more than one item.
>Recall that TList range is 0..N

I remembered that, but I don't think this has any bearing on the sort
routine, does it?

Jesse

Re:TList.Sort Access Violation


In article <6nqih0$lt...@news10.ispnews.com>, "Jesse Castleberry"

Quote
<D...@iThink.net> writes:
>   if nCount1 = nCount2 then
>      if nOrder1 < nOrder2 then
>         Result := -1
>      else
>         Result := 1
>   else
>      if nCount1 > nCount2 then
>         Result := 1
>      else
>         Result := -1;
>end;

I just wonder if it may be because you never return a zero. I think that the
quicksort relies on the value becoming 0 at some time (look in Classes.Pas at
QuickSort()).

In any case it may be more efficient code to write :-

if nCount1 <> nCount2 then
  Result := nCount1 - nCount2
else
  Result := trunc(nOrder1 - nOrder2) {may have to put a *100 here to sort on
cents / pence}
end;

Alan Lloyd
alangll...@aol.com

Re:TList.Sort Access Violation


On Mon, 6 Jul 1998 09:12:10 -0400, "Jesse Castleberry"

Quote
<D...@iThink.net> wrote:
>I've got a TList that I created and I'm trying to sort it, however, it keeps
>blowing up with an "Access Violation" error.

As you've guessed, pCalcOrd(nil)^.Order will cause an access
violation. CalcSort should check for nil pointers.

Quote
>There is only one element in aCalcOrd.  My first question is, Why is it
>hitting this function 3 times??  My second question is, why does Item1
>appear not to be empty (Access Violation) on the 3rd try?

QuickSort wasn't designed for arrays that included only a single item.
You're simply witnessing what happens when one tries to QuickSort a
single item.

Either check for nil pointers in CalcSort or (much easier) change the
call to ACalcOrd.Sort to a

if aCalcOrd.Count>1 then
  aCalcOrd.Sort(CalcSort);

statement.

Re:TList.Sort Access Violation


In article <6nqo6o$10...@news10.ispnews.com>,
  "Jesse Castleberry" <D...@iThink.net> wrote:

Quote

> >The TList somehow thinks there's more than one item.
> >Recall that TList range is 0..N

> I remembered that, but I don't think this has any bearing on the sort
> routine, does it?

        As someone else pointed out elsewhere, your compare function
is confused. What it says in the docs is that the compare function has
to return something positive if Item1 > Item2, 0 if they are "equal",
and something negative if Item1 < Item2 (or the other way around,
I tend to look it up each time.) Based on that you might think
any function at all would work, if it happens to return whatever
you just say that by definition whether Item1 is < or > Item2
is _defined_ by the return value.

        What they don't tell you is that the compare function is
required to make sense. Officially, it's required to be transitive:
if it reports a < b and b < c it had better _also_ report that
a < c. If the compare function says a < b, b < c, and also c < a
that's going to confuse various sort routines.

        I never thought about it, but come to think of it there
are other requirements, all of which will be satisfied automatically
by a compare function that actually makes sense, but some of which
may be violated if the logic in the compare function doesn't do
what you think it does:

if a < b then b > a.
if a < b and b = c then a < c
etc, you get the idea.

A compare function that violates these conditions can confuse things
very badly...

David C. Ullrich

-----== Posted via Deja News, The Leader in Internet Discussion ==-----
http://www.dejanews.com/rg_mkgrp.xp   Create Your Own Free Member Forum

Re:TList.Sort Access Violation


In article <35a12a4d.10919...@news.mia.bellsouth.net>,

Quote
  Mauri...@bellsouth.net wrote:

[...]
> QuickSort wasn't designed for arrays that included only a single item.
> You're simply witnessing what happens when one tries to QuickSort a
> single item.

       I haven't tried it, that would be cheating. How much you
wanna bet that TList.Sort works just fine when Count = 1
(or even when Count = 0). No fair trying it first, I need the
money...

       That is, it works just fine _if_ the Compare function
does what the docs say it should do, including returning
0 when the items are equal. Those comments on what the
Compare function should do are not actually optional (as I
discovered long ago when I was figuring out how TList.Sort
worked - I tried it with a "random" Compare function, just
to get straight how to pass the function to Sort. Imagine
my surprise at the GPF, and my embarassment when I traced
through the code and noticed the sort routine wandering off
into parts of the array that weren't there...)

David C. Ullrich

-----== Posted via Deja News, The Leader in Internet Discussion ==-----
http://www.dejanews.com/rg_mkgrp.xp   Create Your Own Free Member Forum

Re:TList.Sort Access Violation


In article <35a12a4d.10919...@news.mia.bellsouth.net>, Mauri...@bellsouth.net

Quote
({*word*104}Cat) writes:
>QuickSort wasn't designed for arrays that included only a single item.
>You're simply witnessing what happens when one tries to QuickSort a
>single item.

Not so <g>

Both by inspection of QuickSort() in Classes.PAS and by test, it _will_ cope
with a single item. It would be a poor design if it did not.

What it won't cope with is MySort function not returning a 0 for equal items -
and that was what he had done (apart from trying to use nil pointers).

QuickSort actually fails because after calling the sort function it attempts to
access TList.Items[-1] and TList.Items[1] (which ain't there),  when the two
indices should be equal and nothing is done.

Alan Lloyd
alangll...@aol.com

Re:TList.Sort Access Violation


On 07 Jul 1998 11:13:03 GMT, alangll...@aol.com (AlanGLLoyd) wrote:

Quote
>Not so <g>

>Both by inspection of QuickSort() in Classes.PAS and by test, it _will_ cope
>with a single item. It would be a poor design if it did not.

>What it won't cope with is MySort function not returning a 0 for equal items -
>and that was what he had done (apart from trying to use nil pointers).

>QuickSort actually fails because after calling the sort function it attempts to
>access TList.Items[-1] and TList.Items[1] (which ain't there),  when the two
>indices should be equal and nothing is done.

I stand corrected.

Re:TList.Sort Access Violation


Quote
On Tue, 07 Jul 1998 16:57:19 GMT, ullr...@math.okstate.edu wrote:
>       I haven't tried it, that would be cheating. How much you
>wanna bet that TList.Sort works just fine when Count = 1
>(or even when Count = 0). No fair trying it first, I need the
>money...

Heh! Well, I guess it would work - IF the programmer tested for
non-existent entries in the comparison routine. (Something I hadn't
done before; I never guessed it would be necessary. Guess it's time to
dig up my old sorting routines and override TList.Sort.)

Quote
>       That is, it works just fine _if_ the Compare function
>does what the docs say it should do, including returning
>0 when the items are equal. Those comments on what the
>Compare function should do are not actually optional (as I
>discovered long ago when I was figuring out how TList.Sort
>worked - I tried it with a "random" Compare function, just
>to get straight how to pass the function to Sort. Imagine
>my surprise at the GPF, and my embarassment when I traced
>through the code and noticed the sort routine wandering off
>into parts of the array that weren't there...)

Methinks the embarassment should be consigned solely to the geeks at
Inprise. <very small font> idiots! </very small font>

Re:TList.Sort Access Violation


Quote
In article <6ntk1f$fn...@nnrp1.dejanews.com>, ullr...@math.okstate.edu writes:
>       I haven't tried it, that would be cheating. How much you
>wanna bet that TList.Sort works just fine when Count = 1
>(or even when Count = 0). No fair trying it first, I need the
>money...

It doesn't even go into the sort routine if there's no items in the TList
(Count = 0). If there's only one, it goes into the routine and swps it with
itself. But apart from an initial check before it sorts, nowhere does it check
that its not getting outside the TList array, or even reading nil pointers.

It seems that the only thing that is important in the SortCompare routine is
that it returns 0 when appropriate. I'm not sure what you could do in the
SortCompare routine if you found it was "out of control" (due to nil entries in
TList or accesses outside the TList) except just throw some exception.

Alan Lloyd
alangll...@aol.com

Re:TList.Sort Access Violation


In article <35a30a5b.33612...@news.mia.bellsouth.net>,

Quote
  Mauri...@bellsouth.net wrote:
> On Tue, 07 Jul 1998 16:57:19 GMT, ullr...@math.okstate.edu wrote:

> >       I haven't tried it, that would be cheating. How much you
> >wanna bet that TList.Sort works just fine when Count = 1
> >(or even when Count = 0). No fair trying it first, I need the
> >money...

> Heh! Well, I guess it would work - IF the programmer tested for
> non-existent entries in the comparison routine. (Something I hadn't
> done before; I never guessed it would be necessary. Guess it's time to
> dig up my old sorting routines and override TList.Sort.)

          If you're using the built-in Sort you don't need to
test for non-existent entries in the Compare function - the
only things that get passed to the Compare function are values
of Items[j] for 0 <= j < Count. (That's if you're using the
built-in Sort and if your Compare routine does what the docs
say it's supposed to do - if the Compare routine returns
random values then that can cause problems, but this will
be true of lots of sort algorithms.)

Quote
> >       That is, it works just fine _if_ the Compare function
> >does what the docs say it should do, including returning
> >0 when the items are equal. Those comments on what the
> >Compare function should do are not actually optional (as I
> >discovered long ago when I was figuring out how TList.Sort
> >worked - I tried it with a "random" Compare function, just
> >to get straight how to pass the function to Sort. Imagine
> >my surprise at the GPF, and my embarassment when I traced
> >through the code and noticed the sort routine wandering off
> >into parts of the array that weren't there...)

> Methinks the embarassment should be consigned solely to the geeks at
> Inprise. <very small font> idiots! </very small font>

       Huh? I don't follow this at all. The docs said exactly what
I should do. I read the docs, I did something else, and it didn't
work. How can this be their fault?

       You seem to be suggesting that the Sort method should
test for out-of-bounds indexes or something. If the Compare
function does what it should that's not necessary. And if
the Compare function _doesn't_ do what it should then
having the Sort method check for out-of-bounds indexes
_will_ _not_ _help_: It would fix the GPF - the GPF would
then be replaced either by an infinite loop or by something
that "works", except it won't actually _sort_ the list!

David C. Ullrich

-----== Posted via Deja News, The Leader in Internet Discussion ==-----
http://www.dejanews.com/rg_mkgrp.xp   Create Your Own Free Member Forum

Re:TList.Sort Access Violation


Quote
On Wed, 08 Jul 1998 16:09:20 GMT, ullr...@math.okstate.edu wrote:
>          If you're using the built-in Sort you don't need to
>test for non-existent entries in the Compare function - the
>only things that get passed to the Compare function are values
>of Items[j] for 0 <= j < Count. (That's if you're using the
>built-in Sort and if your Compare routine does what the docs
>say it's supposed to do - if the Compare routine returns
>random values then that can cause problems, but this will
>be true of lots of sort algorithms.)

etc.

Quote
>       Huh? I don't follow this at all. The docs said exactly what
>I should do. I read the docs, I did something else, and it didn't
>work. How can this be their fault?

>       You seem to be suggesting that the Sort method should
>test for out-of-bounds indexes or something. If the Compare
>function does what it should that's not necessary. And if
>the Compare function _doesn't_ do what it should then
>having the Sort method check for out-of-bounds indexes
>_will_ _not_ _help_: It would fix the GPF - the GPF would
>then be replaced either by an infinite loop or by something
>that "works", except it won't actually _sort_ the list!

The original poster said that he had called TList.Sort with
TList.Count=1, and that the Sort routine had then called the
comparison routine three times, each time passing a non-existent item
as one of the two item parameters.

While the original poster's comparison routine SHOULD have tested for
equality (and returned zero if Item1=Item2), all that is beside the
point. The point, in my opinion, is that I've never written a sort
routine that tried to compare an item in the array to a nil pointer -
and that I don't think ANY sorting routine should. If TList.Sort had
simply exited when it found Count=1, this entire thread wouldn't even
have started.

I fail to see how the comparison routine could possibly return a sane
value (when TList.Count=1) WITHOUT checking for nil pointers. The fact
is that, even when Count=1, the comparison routine IS called. Since
the array only contains a single item, one of the two items passed as
parameters will be nil. Typecasting both without checking for nil
values will lead to trouble.

Bottom line: Real-world experience has shown that the comparison
routine probably will be passed nil values. The comparison routine
should therefore check these values before attempting a comparison.

if (Item1=nil) or (Item2=nil) then
  if Item1<>nil then
    Result:=-1
  else
    if Item2<>nil then
      Result:=1
    else
      Result:=0 //both are nil
else
  //do typecasting and compare

Something like that.

Re:TList.Sort Access Violation


In article <35a3b1b4.4134...@news.mia.bellsouth.net>, Mauri...@bellsouth.net

Quote
({*word*104}Cat) writes:
>The original poster said that he had called TList.Sort with
>TList.Count=1, and that the Sort routine had then called the
>comparison routine three times, each time passing a non-existent item
>as one of the two item parameters.

The reason a non-existent item was passed was because the comparison routine
was returning incorrect values. If it had returned a zero when it should have,
the comparison routine would have been called once.

Quote

>While the original poster's comparison routine SHOULD have tested for
>equality (and returned zero if Item1=Item2), all that is beside the
>point. The point, in my opinion, is that I've never written a sort
>routine that tried to compare an item in the array to a nil pointer -
>and that I don't think ANY sorting routine should. If TList.Sort had
>simply exited when it found Count=1, this entire thread wouldn't even
>have started.

It would have started because the problem would arise no matter how many Items
were in the list. The incorrect return of the comparison routine forces the
sort routine to an invalid index and hence a nil or GPF pointer.

Quote
>I fail to see how the comparison routine could possibly return a sane
>value (when TList.Count=1) WITHOUT checking for nil pointers. The fact
>is that, even when Count=1, the comparison routine IS called. Since
>the array only contains a single item, one of the two items passed as
>parameters will be nil.

The pointers passed are those to index 0 and to index Count - 1, hence both
pointers validly point to the single item.

Quote

>if (Item1=nil) or (Item2=nil) then
>  if Item1<>nil then
>    Result:=-1
>  else
>    if Item2<>nil then
>      Result:=1
>    else
>      Result:=0 //both are nil
>else
>  //do typecasting and compare

>Something like that.

I don't think you can code this in isolation without seeing what the sort
routine is doing with the returned values. Does your code solve the problem of
a nil pointer. I think what it it doing is causing the sort routine to go onto
the next pointer. Maybe one needs to delete the nil pointer from the TList

Have a close look at the Sort routine <g>

Alan Lloyd
alangll...@aol.com

Go to page: [1] [2]

Other Threads