Skip to content
New issue

Have a question about this project? Sign up for a free GitHub account to open an issue and contact its maintainers and the community.

By clicking “Sign up for GitHub”, you agree to our terms of service and privacy statement. We’ll occasionally send you account related emails.

Already on GitHub? Sign in to your account

Queue.copy is not tail recursive ! #4079

Closed
vicuna opened this issue Aug 7, 2006 · 1 comment
Closed

Queue.copy is not tail recursive ! #4079

vicuna opened this issue Aug 7, 2006 · 1 comment
Assignees
Milestone

Comments

@vicuna
Copy link

vicuna commented Aug 7, 2006

Original bug ID: 4079
Reporter: Christophe
Assigned to: @gasche
Status: closed (set by @xavierleroy on 2015-12-11T18:19:47Z)
Resolution: fixed
Priority: normal
Severity: minor
Version: 3.09.2
Target version: 4.00.2+dev
Category: standard library
Monitored by: @mmottl

Bug description

Queue.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'
}
@vicuna
Copy link
Author

vicuna commented Jun 16, 2013

Comment author: @gasche

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

@vicuna vicuna closed this as completed Dec 11, 2015
@vicuna vicuna added the stdlib label Mar 14, 2019
@vicuna vicuna added this to the 4.00.2 milestone Mar 14, 2019
@vicuna vicuna added the bug label Mar 19, 2019
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment
Projects
None yet
Development

No branches or pull requests

2 participants