Mantis Bug Tracker

View Issue Details Jump to Notes ] Issue History ] Print ]
IDProjectCategoryView StatusDate SubmittedLast Update
0000033OCamlOCaml generalpublic2000-01-27 18:462000-04-17 13:45
Reporteradministrator 
Assigned To 
PrioritynormalSeverityminorReproducibilityalways
StatusclosedResolutionfixed 
PlatformOSOS Version
Product Version 
Target VersionFixed in Version 
Summary0000033: Re: Broken Sort Code in StdLib
DescriptionHi,

Thank you for your message to the Caml mailing list.

However your message seems to be a bug report; hence I send it to the
relevant mailing list

caml-bugs@inria.fr

Thank again for your interest in Caml.

Pierre Weis

INRIA, Projet Cristal, Pierre.Weis@inria.fr, http://cristal.inria.fr/~weis/ [^]


> Dear Caml Crowd...
>
> There still appears to be a problem with the Standard Library Sort.array
> routine. Violation of boundary conditions occur on some occaisions that
> manifest an invalid page fault runtime error.
>
> I have copied the code from the source, modified to explicitly check for
> boundary violations and this appears to fix the problem. My fix is probably
> non-optimal.
>
> The original code fragment is
>
> ...
> let pivot = unsafe_get arr mid in
> let i = ref (lo + 1) and j = ref (hi - 1) in
> while !i < !j do
> while not (cmp pivot (unsafe_get arr !i)) do incr i done;
> while not (cmp (unsafe_get arr !j) pivot) do decr j done;
> if !i < !j then swap arr !i !j;
> incr i; decr j
> done;
> ...
>
> The modified code fragment is:
> (Note the explicit checks in the innermost while loops.)
>
> let pivot = unsafe_get arr hi in
> let i = ref lo and j = ref hi in
> while !i < !j do
> while !i < hi && order (unsafe_get arr !i) pivot do incr i done;
> while !j > lo && order pivot (unsafe_get arr !j) do decr j done;
> if !i < !j then swap arr !i !j
> done;
>
> This problem was first noticed in OCaml 2.03 and has been verified to exist
> in OCaml 2.99.
>
> David McClain, Sr. Scientist
> Raytheon Systems Co.
> Tucson, AZ

TagsNo tags attached.
Attached Files

- Relationships

-  Notes
(0000305)
administrator (administrator)
2000-04-17 13:45

Fixed in 3.00 (Sort.array checks for reflexive ordering relation; code
superceded by Array.sort)

- Issue History
Date Modified Username Field Change
2005-11-18 10:13 administrator New Issue


Copyright © 2000 - 2011 MantisBT Group
Powered by Mantis Bugtracker