Ну Пётр Алмазов первым представил самое лучшее по понятности решение. Хотя там есть нюансы (внутри цикла prev выставляется как начало предыдущего указателя, а не место по его окончанию, надо + SIZE(ANYPTR)).
Ну и моё.
Сначала я немного потупил, взяв отдельно ползунок возможных смещений для числа (ползущий с каким-то шагом) и итератор по ptroffs. После чего инвариант, объединяющий движение по двум последовательностям, получался мама не горюй.
Потом понял, что нужно сформулировать задачу только относительно ptroffs.
Получилось: "Найти такой ptroffs[i], перед которым есть место для целого числа, или достичь конца".
Разумеется, в конце уже проверка на то, нет ли места в конце.
Получился типовой линейный поиск с удачным выбором переменных цикла (чтобы они могли быть хорошо определены и до цикла, и в нём, и после, а не как в случае с i и i-1 или с переменной, задающей НАЧАЛО предыдущего указателя, а если его не было, строить от отрицательного смещения?) и некоторыми поддерживающими рассуждениями после.
Код с некоторыми сопутствующими рассуждениями (писал не для форума, так и есть в коде):
Код:
PROCEDURE LookupMarkOffs (t: Kernel.Type): INTEGER;
VAR spaceBeg, pi: INTEGER;
BEGIN
spaceBeg := 0; (* Где заканчивается предыдущий указатель *)
pi := 0;
(* Найти такой указатель среди ptroffs, перед которым есть свободное место для целого числа *)
WHILE (t.ptroffs[pi] # -1) & ~(spaceBeg + SIZE(INTEGER) <= t.ptroffs[pi]) DO
spaceBeg := t.ptroffs[pi] + SIZE(ANYPTR);
INC(pi)
END;
(* Q: Если pi найден (ptroffs[pi] # -1), то spaceBeg - начало свободного пространства перед ним (=> spaceBeg + SIZE(INTEGER) < t.size)
Если pi не найден, то spaceBeg - пространство после последнего указателя.
Надо проверить, что spaceBeg + SIZE(INTEGER) < t.size *)
IF spaceBeg + SIZE(INTEGER) <= t.size THEN
RETURN spaceBeg
ELSE
RETURN -1
END
END LookupMarkOffs;