OberonCore

Коллеги, предлагаю размяться на таком примере:

- как известно, тип в ББ описывается следующим дескриптором Kernel.Type:



Здесь ptroffs - это смещения, по которым в записи есть указательные поля (для сборщика мусора). Список заканчивается значением -1.

Задача: составить процедуру PROCEDURE LookupMarkOffs (t: Kernel.Type): INTEGER, которая находит смещение в записи, по которому мы можем безопасно положить значение INTEGER, не попав на указательные поля (не сломав зубы сборщику). Если класть некуда, то вернуть -1.

У меня решение уже есть.

.ptroffs полагаем строго монотонно возрастающим?

Да, это обеспечивается реализацией компилятора.

При выделении памяти, менеджер памяти, обычно выделяет память не байт в байт, а определенным блоками. Например, в менедержере памяти Oberon-07M память выделяется от 32 байт до мегабайта кратно степени двойки. А с мегабайта кратно мегабайту. В BlackBox скорее всего примерно то же самое, соответственно в конце блока должно быть еще много места, чтобы не просто INTEGER сохранить, а еще много чего можно сохранить.

Не обязательно, если поля записи кратно уложатся в эту гранулярность.

А в моём случае вообще речь идёт о метке в элементе динамического массива.

А постановка задачи на алгоритмику

Чую подвох, но рискну размяться:

Не, читается неубедительно - и, по ходу, пропускает случай, когда свободное место есть ещё до первого указателя.

Не очень понимаю всех полей, но если правильно понял, то наверное так (исправил предыдущий пример. Верен, если размер указателя такой же, как интегера)

Ну и еще предусмотреть случаи, когда количество в массиве меньше 2х

Не, что-то не то. Возможно, Вы считаете, что в ptroffs лежит не смещение в байтах, а что-то другое.

Пример. Первый указатель лежит по смещению 0. У Вас цикл остановится уже на i = 1. Результатом станет смещение в 1 байт?

У Вас в условии цикла не учитывается ещё то, что от предыдущего ptroffs до начала следующего должно "пролезать" 2 IntSize. Ну, лучше вообще использовать 2 разных размера: SIZE(ANYPTR) и SIZE(INTEGER).

Ну и можно вообще без начальных IF-ов и разбора ситуаций, сразу циклом. В конце, конечно, IF.

Если я правильно понял условие, то середина такая

Ну да. Я считал все в машинных словах.

тогда так

А без IF в конце? Так не сработает? Ну и не против увидеть, "разбор правильного решения".

приблизительно

Ну Пётр Алмазов первым представил самое лучшее по понятности решение. Хотя там есть нюансы (внутри цикла prev выставляется как начало предыдущего указателя, а не место по его окончанию, надо + SIZE(ANYPTR)).

Ну и моё.

Сначала я немного потупил, взяв отдельно ползунок возможных смещений для числа (ползущий с каким-то шагом) и итератор по ptroffs. После чего инвариант, объединяющий движение по двум последовательностям, получался мама не горюй.

Потом понял, что нужно сформулировать задачу только относительно ptroffs.
Получилось: "Найти такой ptroffs[i], перед которым есть место для целого числа, или достичь конца".
Разумеется, в конце уже проверка на то, нет ли места в конце.
Получился типовой линейный поиск с удачным выбором переменных цикла (чтобы они могли быть хорошо определены и до цикла, и в нём, и после, а не как в случае с i и i-1 или с переменной, задающей НАЧАЛО предыдущего указателя, а если его не было, строить от отрицательного смещения?) и некоторыми поддерживающими рассуждениями после.

Код с некоторыми сопутствующими рассуждениями (писал не для форума, так и есть в коде):

Нет, не надо. Там фигурирует "нужный_кусок" - его величина как раз и должна включать добавку.

Вообще, Илья, давно пора завязывать с этой ахинеей (базовые паттерны циклов, обожествление линейного поиска) и научиться уже писать циклы.
Инвариант там простой – в просмотренной части нет подходящего свободного куска.