OberonCore

Библиотека  Wiki  Форум  BlackBox  Компоненты  Проекты
Текущее время: Вторник, 27 Июль, 2021 21:56

Часовой пояс: UTC + 3 часа




Начать новую тему Ответить на тему  [ Сообщений: 29 ]  На страницу 1, 2  След.
Автор Сообщение
СообщениеДобавлено: Вторник, 03 Март, 2020 13:47 
Модератор
Аватара пользователя

Зарегистрирован: Понедельник, 14 Ноябрь, 2005 18:39
Сообщения: 9425
Откуда: Россия, Орёл
Коллеги, предлагаю размяться на таком примере:

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

Код:
TYPE
   Type = POINTER TO RECORD [untagged]
      size-: INTEGER;
      mod-: Kernel.Module;
      id-: INTEGER;
      base-: ARRAY 16 OF Kernel.Type;
      fields-: Kernel.Directory;
      ptroffs-: ARRAY 1000000 OF INTEGER
   END;


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

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

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


Вернуться к началу
 Профиль  
 
СообщениеДобавлено: Вторник, 03 Март, 2020 14:53 
Аватара пользователя

Зарегистрирован: Суббота, 16 Февраль, 2008 02:47
Сообщения: 491
.ptroffs полагаем строго монотонно возрастающим?


Вернуться к началу
 Профиль  
 
СообщениеДобавлено: Вторник, 03 Март, 2020 16:08 
Модератор
Аватара пользователя

Зарегистрирован: Понедельник, 14 Ноябрь, 2005 18:39
Сообщения: 9425
Откуда: Россия, Орёл
adimetrius писал(а):
.ptroffs полагаем строго монотонно возрастающим?

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


Вернуться к началу
 Профиль  
 
СообщениеДобавлено: Вторник, 03 Март, 2020 16:48 

Зарегистрирован: Пятница, 13 Март, 2009 16:36
Сообщения: 978
Откуда: Казань
При выделении памяти, менеджер памяти, обычно выделяет память не байт в байт, а определенным блоками. Например, в менедержере памяти Oberon-07M память выделяется от 32 байт до мегабайта кратно степени двойки. А с мегабайта кратно мегабайту. В BlackBox скорее всего примерно то же самое, соответственно в конце блока должно быть еще много места, чтобы не просто INTEGER сохранить, а еще много чего можно сохранить.


Вернуться к началу
 Профиль  
 
СообщениеДобавлено: Вторник, 03 Март, 2020 17:41 
Модератор
Аватара пользователя

Зарегистрирован: Понедельник, 14 Ноябрь, 2005 18:39
Сообщения: 9425
Откуда: Россия, Орёл
Rifat писал(а):
При выделении памяти, менеджер памяти, обычно выделяет память не байт в байт, а определенным блоками. Например, в менедержере памяти Oberon-07M память выделяется от 32 байт до мегабайта кратно степени двойки. А с мегабайта кратно мегабайту. В BlackBox скорее всего примерно то же самое, соответственно в конце блока должно быть еще много места, чтобы не просто INTEGER сохранить, а еще много чего можно сохранить.


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

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

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


Вернуться к началу
 Профиль  
 
СообщениеДобавлено: Вторник, 03 Март, 2020 23:13 
Аватара пользователя

Зарегистрирован: Суббота, 16 Февраль, 2008 02:47
Сообщения: 491
Чую подвох, но рискну размяться:
Код:
MODULE M;

   IMPORT Kernel;
   
   PROCEDURE P (IN a: ARRAY OF INTEGER; size: INTEGER): INTEGER;
      VAR i, res: INTEGER;
   BEGIN
      i := 0; WHILE (a[i] # -1) & (a[i] + 8 <= a[i + 1]) DO INC(i) END;
      IF a[i] = -1 THEN res := -1
      ELSE res := a[i] + 4; IF res + 4 > size THEN res := -1 END
      END;
      RETURN res
   END P;
   
   PROCEDURE LookupMarkOffs (t: Kernel.Type): INTEGER;
   BEGIN RETURN P(t.ptroffs, t.size)
   END LookupMarkOffs;

END M.


Вернуться к началу
 Профиль  
 
СообщениеДобавлено: Вторник, 03 Март, 2020 23:32 
Модератор
Аватара пользователя

Зарегистрирован: Понедельник, 14 Ноябрь, 2005 18:39
Сообщения: 9425
Откуда: Россия, Орёл
Не, читается неубедительно - и, по ходу, пропускает случай, когда свободное место есть ещё до первого указателя.


Вернуться к началу
 Профиль  
 
СообщениеДобавлено: Среда, 04 Март, 2020 09:07 

Зарегистрирован: Суббота, 16 Февраль, 2008 07:58
Сообщения: 358
Откуда: Россия, Стерлитамак
Не очень понимаю всех полей, но если правильно понял, то наверное так (исправил предыдущий пример. Верен, если размер указателя такой же, как интегера)
Код:
MODULE M;

   IMPORT Kernel;
   
   PROCEDURE P (IN a: ARRAY OF INTEGER; size: INTEGER): INTEGER;
      VAR i, res, sizeInt: INTEGER;
   BEGIN
      sizeInt := 8;
      IF a[0] > sizeInt THEN
        res := 0;
      ELSE
        i := 0;
        WHILE (a[i + 1] # -1) & (a[i] + sizeInt > a[i + 1]) DO
            INC(i)
        END;

        IF a[i + 1] = -1 THEN
            res := -1
        ELSE
            res := a[i] + sizeInt;
        END;
      END;
      RETURN res
   END P;
   
   PROCEDURE LookupMarkOffs (t: Kernel.Type): INTEGER;
   BEGIN RETURN P(t.ptroffs, t.size)
   END LookupMarkOffs;

END M.


Вернуться к началу
 Профиль  
 
СообщениеДобавлено: Среда, 04 Март, 2020 09:12 

Зарегистрирован: Суббота, 16 Февраль, 2008 07:58
Сообщения: 358
Откуда: Россия, Стерлитамак
Ну и еще предусмотреть случаи, когда количество в массиве меньше 2х


Вернуться к началу
 Профиль  
 
СообщениеДобавлено: Среда, 04 Март, 2020 14:40 

Зарегистрирован: Понедельник, 28 Ноябрь, 2005 10:28
Сообщения: 1381
Код:
i:=0;
WHILE i=p[i] DO INC(i) END;
IF i >= size THEN i := -1 END;


Вернуться к началу
 Профиль  
 
СообщениеДобавлено: Среда, 04 Март, 2020 14:55 
Модератор
Аватара пользователя

Зарегистрирован: Понедельник, 14 Ноябрь, 2005 18:39
Сообщения: 9425
Откуда: Россия, Орёл
Trurl писал(а):
Код:
i:=0;
WHILE i=p[i] DO INC(i) END;
IF i >= size THEN i := -1 END;


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

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


Вернуться к началу
 Профиль  
 
СообщениеДобавлено: Среда, 04 Март, 2020 14:58 
Модератор
Аватара пользователя

Зарегистрирован: Понедельник, 14 Ноябрь, 2005 18:39
Сообщения: 9425
Откуда: Россия, Орёл
adva писал(а):
Не очень понимаю всех полей, но если правильно понял, то наверное так (исправил предыдущий пример. Верен, если размер указателя такой же, как интегера)


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

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


Вернуться к началу
 Профиль  
 
СообщениеДобавлено: Среда, 04 Март, 2020 16:04 

Зарегистрирован: Пятница, 24 Апрель, 2009 16:28
Сообщения: 561
Откуда: Москва
Если я правильно понял условие, то середина такая
Код:
prev=начало области
i=0
WHILE a[i]!=-1 and (a[i] - prev < нужный_кусок) DO
  prev=a[i]
  i=i+1
END


Вернуться к началу
 Профиль  
 
СообщениеДобавлено: Среда, 04 Март, 2020 16:24 

Зарегистрирован: Понедельник, 28 Ноябрь, 2005 10:28
Сообщения: 1381
Илья Ермаков писал(а):
Возможно, Вы считаете, что в ptroffs лежит не смещение в байтах, а что-то другое.

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

тогда так
Код:
i:=0;
WHILE 4*i=p[i] DO INC(i) END;
i := 4*i;
IF i >= size THEN i := -1 END;


Вернуться к началу
 Профиль  
 
СообщениеДобавлено: Среда, 04 Март, 2020 17:03 

Зарегистрирован: Суббота, 16 Февраль, 2008 07:58
Сообщения: 358
Откуда: Россия, Стерлитамак
Илья Ермаков писал(а):
Ну и можно вообще без начальных IF-ов и разбора ситуаций, сразу циклом. В конце, конечно, IF.

А без IF в конце? Так не сработает? Ну и не против увидеть, "разбор правильного решения".
Код:
 res := -1;
 i := 0;
 WHILE (a[i] # -1) & (res = -1) DO
     IF i > 0 & (a[i] - SIZE(anyptr) - SIZE(INTEGER) > a[i - 1])
                OR (a[i] - SIZE(anyptr) - SIZE(INTEGER) >= 0)
           res := a[i] - SIZE(INTEGER)
     END;
     INC(i)
 END;


Вернуться к началу
 Профиль  
 
СообщениеДобавлено: Среда, 04 Март, 2020 17:19 

Зарегистрирован: Пятница, 20 Июль, 2007 17:26
Сообщения: 710
Откуда: Псков
приблизительно
Код:
res:=0;
i:=0;
eof:=FALSE;
WHILE ~eof & res+8>a[i] DO
  eof:= (a[i]=-1) or (i=imax);
  res:=a[i]+8;
  INC(i);
END
IF eof THEN res:=-1 END


Вернуться к началу
 Профиль  
 
СообщениеДобавлено: Среда, 04 Март, 2020 19:35 

Зарегистрирован: Пятница, 11 Январь, 2019 19:26
Сообщения: 237
Откуда: Russia
Код:
i := 0; start := 0; end := ptroffset[ 0 ];
WHILE ( end # -1 ) & ( end - start < 4 ) DO
  INC( i );
  start := end;
  end := ptroffset[ i ];
END;
IF size - start < 4 THEN start := -1; END;



Вернуться к началу
 Профиль  
 
СообщениеДобавлено: Среда, 04 Март, 2020 21:46 
Модератор
Аватара пользователя

Зарегистрирован: Понедельник, 14 Ноябрь, 2005 18:39
Сообщения: 9425
Откуда: Россия, Орёл
Ну Пётр Алмазов первым представил самое лучшее по понятности решение. Хотя там есть нюансы (внутри цикла 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;


Вернуться к началу
 Профиль  
 
СообщениеДобавлено: Среда, 04 Март, 2020 22:05 

Зарегистрирован: Пятница, 24 Апрель, 2009 16:28
Сообщения: 561
Откуда: Москва
Илья Ермаков писал(а):
Хотя там есть нюансы (внутри цикла prev выставляется как начало предыдущего указателя, а не место по его окончанию, надо + SIZE(ANYPTR)).

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


Вернуться к началу
 Профиль  
 
СообщениеДобавлено: Среда, 04 Март, 2020 22:17 

Зарегистрирован: Пятница, 24 Апрель, 2009 16:28
Сообщения: 561
Откуда: Москва
Вообще, Илья, давно пора завязывать с этой ахинеей (базовые паттерны циклов, обожествление линейного поиска) и научиться уже писать циклы.
Инвариант там простой – в просмотренной части нет подходящего свободного куска.


Вернуться к началу
 Профиль  
 
Показать сообщения за:  Поле сортировки  
Начать новую тему Ответить на тему  [ Сообщений: 29 ]  На страницу 1, 2  След.

Часовой пояс: UTC + 3 часа


Кто сейчас на конференции

Сейчас этот форум просматривают: нет зарегистрированных пользователей и гости: 1


Вы не можете начинать темы
Вы не можете отвечать на сообщения
Вы не можете редактировать свои сообщения
Вы не можете удалять свои сообщения
Вы не можете добавлять вложения

Найти:
Вся информация, размещаемая участниками на конференции (тексты сообщений, вложения и пр.) © 2005-2021, участники конференции «OberonCore», если специально не оговорено иное.
Администрация не несет ответственности за мнения, стиль и достоверность высказываний участников, равно как и за безопасность материалов, предоставляемых участниками во вложениях.
Без разрешения участников и ссылки на конференцию «OberonCore» любое воспроизведение и/или копирование высказываний полностью и/или по частям запрещено.
Powered by phpBB® Forum Software © phpBB Group
Русская поддержка phpBB