Mantis Bug Tracker

View Issue Details Jump to Notes ] Issue History ] Print ]
IDProjectCategoryView StatusDate SubmittedLast Update
0004079OCamlOCaml standard librarypublic2006-08-07 15:582013-06-16 18:20
ReporterChristophe 
Assigned Togasche 
PrioritynormalSeverityminorReproducibilityalways
StatusresolvedResolutionfixed 
PlatformOSOS Version
Product Version3.09.2 
Target Version4.00.2+devFixed in Version 
Summary0004079: Queue.copy is not tail recursive !
DescriptionQueue.copy is not tail recursive. Hence, large queue can not be safely duplicated.
This would be very simple to make it tail-recursive. I propose here a solution ;


let copy q =
  if q.length = 0 then
    create()
  else
    let tail = q.tail in

    let rec tail' = {
      content = tail.content;
      next = tail'
    } in

    let rec copy prev cell =
      if cell != tail
      then let res = {
        content = cell.content;
        next = tail'
      } in prev.next <- res;
      copy res cell.next in

    copy tail' tail.next;
    {
      length = q.length;
      tail = tail'
    }
TagsNo tags attached.
Attached Files

- Relationships

-  Notes
(0009514)
gasche (developer)
2013-06-16 18:20

I reviewed the patch and observed good performance results (even on smallish queues). Applied, as is, to 4.01 and trunk.

- Issue History
Date Modified Username Field Change
2006-08-07 15:58 Christophe New Issue
2006-08-29 16:41 doligez Status new => acknowledged
2012-07-11 16:41 doligez Target Version => 4.01.0+dev
2012-07-29 17:57 frisch Category OCaml general => OCaml standard library
2012-07-31 13:37 doligez Target Version 4.01.0+dev => 4.00.1+dev
2012-09-11 17:00 doligez Target Version 4.00.1+dev => 4.00.2+dev
2013-06-16 18:20 gasche Note Added: 0009514
2013-06-16 18:20 gasche Status acknowledged => resolved
2013-06-16 18:20 gasche Resolution open => fixed
2013-06-16 18:20 gasche Assigned To => gasche


Copyright © 2000 - 2011 MantisBT Group
Powered by Mantis Bugtracker