По закону Кирхгофа ti+t2+l = п. Общее время выполнения равно (34n+4ti +За-5Ь-8)и, где п - количество маркированных узлов, не являющихся атомами, а - количество маркированных атомов, b - количество связей Л, которые встречаются в маркированных узлах, не являющихся атомами, ti -число переходов вниз по связям ALINK {О < ti < п).

5. (Приведенный ниже алгоритм является самым быстрым из известных до сих пор алгоритмов маркировки для одноуровневой памяти.)

51. Установить MARK(PO) <- 1. Если АТОМ(РО) = 1, то выполнение алгоритма прекращается; в противном случае установить S •(- О, R •(- РО, Т •(- Л.

52. Установить Р •(- BLINK (R). Если Р = Л или MARK(P) = 1, перейти к шагу S3. В противном случае установить MARK(P) <- 1. Теперь, если АТОМ(Р) = 1, перейти к шагу S3; в противном случае, если S < N, установить S <- S -Ь 1, STACK [S] <- Р и перейти к шагу S3; в противном случае перейти к шагу S5.

53. Установить Р •(- ALINK(R). Если Р = Л или MARK(P) = 1, то перейти к шагу S4. В противном случае установить MARK(P) •(- 1. Теперь, если АТОМ(Р) = 1, перейти к шагу S4; в противном случае установить R <- Р и вернуться к шагу S2.

54. Если S = О, то прекратить выполнение алгоритма; в противном случае установить R i- STACK [S] , S •(- S - 1 и перейти к шагу S2.

55. Установить Q •(- ALINK (Р). Если Q = Л или MARK(Q) = 1, то перейти к шагу S6. В противном случае установить MARK(Q) •(- 1. Теперь, если ATOM(Q) = 1, перейти к шагу S6; в противном случае установить АТОМ(Р) •(- 1, ALINK(Р) •(- Т, Т •(- Р, Р •(- Q и перейти к шагу S5.

56. Установить Q •(- BLINK(Р). Если Q = Л или MARK(Q) = 1, то перейти к шагу S7; в противном случае установить MARK(Q) •(- 1. Теперь, если ATOM(Q) = 1, перейти к шагу S7; в противном случае установить BLINK (Р) •(- Т, Т-(- Р, Р-(-Qn перейти к шагу S5.

57. Если Т = Л, то перейти к шагу S3. В противном случае установить Q <- Т. Если ATOM(Q) = 1, то установить ATOM(Q) <- О, Т <- ALINK(Q), ALINK(Q) <- Р, Р 4- Q и вернуться к шагу S6. Если ATOM(Q) = О, то установить Т •(- BLINK(Q), BLINK (Q) •(- Р, Р •(- Q и вернуться к шагу S7.

[См. САСМ 10 (1967), 501-506.]

6. Он включен в связи с выполнением второй фазы сборки мусора (или начальной фазы, если все маркировочные биты инициализируются в это время нулями).

7. Следует удалить шаги Е2 и ЕЗ. а также команду "АТОМ(Р) •(- 1" на шаге Е4. Установить MARK(P) •(- 1 на шаге Е5 и использовать команду "MARK(Q) = О", "MARK(Q) = 1" на шаге Е6 вместо команд "ATOM(Q) = 1", "ATOM(Q) = О" соответственно. Основная идея здесь заключается в установке маркировочного бита MARK только после маркирования левого поддерева. Этот алгоритм вполне пригоден, даже если дерево имеет перекрывающиеся (совместно используемые) поддеревья, ио его нельзя применить для всех рекурсивных структур Списка, в которых узел NODE (ALINK (Q)) предшествует узлу NODE(Q). (Обратите внимание, что связь ALINK маркированного узла никогда не меняется.)

8. Решение 1. Оно аналогично алгоритму Е, но проще. F1. Установить Т •(- Л, Р •(- РО.

F2. Установить MARK(P) •(- 1 и Р •(- Р -Ь SIZE(P). F3. Если MARK(P) = 1, перейти к шагу F5.

F4. Установить Q <- LINK(P). Если Q Л и MARK(Q) = О, то установить LINK(P) <- Т, Т <- Р, Р <- Q и перейти к шагу F2. В противном случае установить Р <- Р - 1 и вернуться к шагу F3.

F5. Если Т = Л, прекратить выполнение алгоритма. В противном случае установить Q •(- Т, Т •(- LINK(Q), LINK(Q) -(-Р, P-(-Q-1h вернуться к шагу F3.

Аналогичный алгоритм, который иногда позволяет сократить связанные с выделением памяти накладные расходы и избежать размещения всех указателей внутри узлов, предложил Ларс-Эрик Торелли (Lars-Erik Thorelli); см. BIT 12 (1972), 555-568.

Решение 2. Оно аналогично алгоритму D. В этом решении предполагается, что поле SIZE достаточно велико и в нем можно разместить адрес связи. Такое допущение, вероятно, не оправдано в данной постановке задачи, но оно позволяет получить несколько более быстрый алгоритм, чем алгоритм из первого решения.

G1. Установить Т <- Л, МАЯК(РО) 4- 1. Р <- РО -Ь SIZE(PO).

G2. Если MARK(P) = 1, перейти к шагу G5.

G3. Установить Q •(- LINK(P), Р <- Р - 1.

G4. Если Q / Л и MARK(Q) = О, то установить MARK(Q) 4- 1, S <- SIZE(Q), SIZE(Q) 4- Т, Т 4- Q -Ь S. Вернуться к шагу G2.

G5. Если Т = Л, прекратить выполнение алгоритма. В противном случае установить Р4-Т и найти первое значение среди Q =Р, Р-1,Р-2,для которого MARK(Q) =1; установить Т 4- SIZE(Q) и SIZE(Q) 4- Р - Q. Вернуться к шагу G2.

9. HI. Установить L 4- О, К 4- М -f 1, MARK(O) 4- 1, MARK(M -(-1)4-0.

Н2. Увеличить L на единицу и, если MARK(L) = 1, повторить этот шаг.

НЗ. Уменьшить К на единицу и, если MARK (К) = О, повторить этот шаг.

Н4. Если L > К, то перейти к шагу Н5; в противном случае установить NODE(L) 4-NODE(K), ALINK (К) 4- L, MARK (К) 4- О и вернуться к шагу Н2.

Н5. Для L = 1, 2, ..., К выполнить такие действия. Установить MARK(L) 4- 0. Если ATOM(L) = О и ALINK(L) > К, то установить ALINK(L) 4- ALINK (ALINK(L)). Еспи ATOM (L) = О и BLINK (L) Ж, то установить BLINK (L) 4- ALINK (BLINK (L)).

[Cm. также упр. 2.5-33.]

10. ZI. [Инициализация.] Установить F 4- PO, R *= AVAIL, NODE(R) 4- NODE(F), REF(F) 4- R.

(Здесь F и R-указатели очереди в полях REF всех встретившихся узлов-згцО-ловков.)

Z2. [Начало нового Списка.] Установить Р 4- F, Q 4- REF(P).

Z3. [Продвижение вправо.] Установить Р 4- RLINK (Р). Если Р = Л, то перейти к шагу Z6.

Z4. [Копирование одного узла.] Установить Q1 AVAIL, RLINK(Q) 4- QI, Q 4- QI, NODE(Q) 4- NODE(P).

Z5. [Преобразование связи подСписка.] Если Т(Р) = 1, то установить Р1 4- REF(P) и, если REF(Pl) = Л, установить REF(R) 4- PI, R AVAIL, REF(Pl) 4- R, NODE(R) 4-NODE(Pl), REF(Q) 4- R. Если T(P) = 1 и REF(Pl) / A, то установить REF(Q) 4-REF(Pl). Перейти к шагу Z3.

Z6. [Переход к следующему списку.] Установить RLINK (Q) 4- Л. Если REF(F) / R, то установить F 4- REF(REF(F)) и вернуться к шагу Z2. В противном случае установить REF(R) 4- Л, Р 4- РО.

Z7. [Окончательная зачистка.] Установить Q 4- REF(P). Если Q / Л, то установить REF(P) 4- Л и Р 4- Q и повторить шаг Z7.

Конечно, такое применение полей REF не позволяет использовать метод сборки мусора с помощью алгоритма D; более того, алгоритм D непригоден здесь еще и потому, что во время копирования не сохраняется структура Списков.