;;; Code for garbage collection lecture
;;; Do not try to run this code, as you'll get errors on 
;;; undefined variables.  Code is meant to be Scheme-pseudocode

;;; Code for mark and sweep
;;; Two phases: 
;;;    1. Mark good cells.  
;;;    2. Chain together free list while clearing marks (sweep phase)

(define (mark object)
  (cond ((not (pair? object)) #f)
	((not (= 1 (vector-ref the-marks object)))
	 (vector-set! the-marks object 1)
	 (mark (car object))
	 (mark (cdr object)))))

(define (sweep i)
  (cond ((not (= i size)) (cond ((= 1 (vector-ref the-marks i))
				 (vector-set! the-marks i 0))
				(else (set-cdr! (int-to-pointer i) free)
				      (set! free (int-to-pointer i))))
			  (sweep (+ i 1)))))


(define (gc)
  (mark root)
  (sweep 0))


;;; Code for stop and copy
;;; Start by copying the root and leave forwarding address (not shown
;;; in code below)
;;; Then scan cars and cdrs of copied cells to copy good cells

(define (gccopy scan)
  (if (not (= scan free))
      (begin
	(set-car! scan (forward (vector-ref the-cars scan)))
	(set-cdr! scan (forward (vector-ref the-cdrs scan)))
	(gccopy (+ scan 1)))))

(define (forward pointer)
  (cond ((pair? pointer) (let ((oldcar (car pointer)))
			   (if (forward? oldcar)
			       (int-to-pointer oldcar)
			       (let ((newptr (int-to-pointer free)))
				 (set-car! newptr oldcar)
				 (set-cdr! newptr (cdr pointer))
				 (set! free (+ 1 free))
				 (set-car! pointer (int-to-pointer newptr))
				 newptr))))
	(else pointer)))