Помощь - Поиск - Пользователи - Календарь
Полная версия: Реализовать вектор в Ada 95 с быстрым доступом
Форум «Всё о Паскале» > НИФ СП > Переносимый Ассемблер (Си)
OCTAGRAM
Работа выполняется в GNAT -gnat95.

За основу программного интерфейса берётся Vector из библиотеки контейнеров. В GNAT явно указано, что то, что выше private, имеет происхождение из ISO стандарта Ada, и общедоступен. У нас будет солянка. Производный от общедоступного продукт можно лицензировать под Апаче. Расписывать, какой метод повторяет то, что есть в стандарте, а какой — нет, можно заскучать. Я предлагаю ограничиться пометкой, как в GNAT, что нечто, но не всё, имеет происхождение из ISO стандарта Ada, но в отличие от GNAT, не расписывать.


Реализовать нужно как минимум добавление и определение количества элементов.

Также нужно реализовать по аналогии с Fast_Strings быстрый доступ к элементам.

При разработке необходимо учесть «любовь» транслятора к избыточному копированию. Учёт этого обстоятельства заключается в том, что реализуется копирование при записи. Вектор по своей природе содержит ссылки, это нормально, но, как правило, структура, на которую сделана ссылка, уникальна. Придётся уникальностью пожертвовать.

В отличие от TList<>, IList<> и TArray<> в Delphi, и аналогично Ada 2005+ контейнерам, значения типа Vector считаются независимыми после копирования. Так что для чтения можно разделять структуры данных, но и только. Перед любыми изменяющими операциями выполняется публично доступная процедура Unique, приводящая вектор к состоянию уникальности содержимого, если счётчик ссылок не 1.

Структура в динамической памяти не должна быть tagged. Массив, из которого структура состоит, должен быть из Storage_Element, но с выравниванием, как у Element. Впоследствии, при выделении элементов используется специальный выделитель памяти, который при выделении возвращает заранее известный адрес, а при освобождении — ничего не делает. С его помощью инициализируются и финализируются элементы в векторе.

Под быстрым доступом имеется в виду возможность закрепить на стеке структуру Vector_View, посредством которой можно обозревать содержимое на чтение. Для этого используется дискриминант неограниченного указателя на массив элементов. И тогда это закрепление добавляет ссылку на время своего существования. В Fixed_Strings это достигалось копированием Unbounded_String внутрь себя. В данном проекте Vector предполагает наличие внутри себя замков на запись, и тогда класть копию Vector внутри себя не очень хорошо. Придётся сделать ещё раз Initialize/Finalize для подсчёта ссылок.

Для доступа на запись структура Vector_Edit. Аналогично String_Edit, забирает на время своего существования содержимое исходного вектора, ведь редактировать можно только уникальное содержимое. А если не забирать, уникальным оно не будет. В Finalize гипотетически может обнаружиться, что в том векторе, откуда забирали содержимое, снова что-то есть. Значит, уничтожить и заменить своим.

В Fast_Strings String_View — это функция, возвращающая Ada 2012 ссылку, а String_Edit — структура, производящая манипуляции над собой и целью в Initialize и Finalize. В Ada 95 нельзя из функции вернуть limited. Позволить этим структурам быть копируемыми тоже нельзя. Поэтому и View, и Edit будут устроены как Edit.

Такой вектор должен будет стать фундаментом для аналога Unbounded_Wide_Wide_String.



Куда складывать, напишу позже.
OCTAGRAM
Публикация в

https://osdn.net/projects/paf/scm/hg/Ada95FL/

Новое хранилище в пустой директории создаётся командой hg init .
Или из TortoiseHg.

Потом hg add добавляются нужные файлы или, что аналогично, проставляются галочки у файлов в TortoiseHg. Игнорируемые артифакты сборки добавляются по маскам или по поддиректориям в .hgignore (пункт Игнорировать контекстного меню у лишнего файла). В директории, которые нужны для успешной сборки, добавляется пустой файл .hgignore, иначе TortoiseHg директории при клонировании не создаст.

В такой директории можно выполнить

Код
touch .hgignore
hg add .hgignore
Sergey Dukov

Задачу в первом приближении понял. Настраиваюсь на работу.
Sergey Dukov

Первоначальная реализация векторов байт на севере.

Реализованы различные методы добавления байт в вектор.
Вьювер реализован с помощью функции "To_Array".
Функциональность типа "редактора" я не совсем понял. По всей видимости, функциональность редактирования нужно реализовывать за счёт введения новых процедур работы с самим вектором.

Проект я только откомпилировал, но не проверял. На создание тестера у меня не хватает воображения. Помогите мне с этим вопросом. Напишите исходник тестера, а я его соберу и пропущу через отладчик.

Нужно ли реализовывать процедуры чтения из потока и записи в поток?
OCTAGRAM
Цитата(Sergey Dukov @ 14.09.2019 5:24) *
Функциональность типа "редактора" я не совсем понял. По всей видимости, функциональность редактирования нужно реализовывать за счёт введения новых процедур работы с самим вектором.


Нет, это Limited_Controlled с access discriminant, указывающим на вектор. В Initialize он переносит данные к себе и требует уникальности, в Finalize переносит обратно.

Цитата(Sergey Dukov @ 14.09.2019 5:24) *
Проект я только откомпилировал, но не проверял. На создание тестера у меня не хватает воображения. Помогите мне с этим вопросом. Напишите исходник тестера, а я его соберу и пропущу через отладчик.


С этим до сих пор завал sad.gif

Цитата(Sergey Dukov @ 14.09.2019 5:24) *
Нужно ли реализовывать процедуры чтения из потока и записи в поток?


Нет. Предполагается, что если вектор инстанциировать для октетов и открыть на чтение или редактирование, то чтение/запись можно делать обычными массивными функциями.
Sergey Dukov

Я реализовал преобразование UTF-8 в UTF-32. И, поневоле, пришлось создать простенький тестер для этой функциональности. Преобразование происходит правильно, но возникла проблема с удалением массивов из памяти. Попробовал исправить ошибки при размещении массивов в памяти, но это не помогло.

Вообще-то я с самого начала принял неправильный подход к построению реализации векторов октетов. Я лишь посмотрел, и то не совсем внимательно, приватную часть спецификации пакета от AdaCore и сделал почти всё по своему. Тип вектора я наследовал от Limited_Controlled, а не от Controlled. Испугался того, что во втором случае деструктор объекта может вызываться несколько раз. Не посмотрел как эта проблема решается стандартным способом. Далее начал городить свой огород исходя из меры своей распущенности, даже не подсматривая реализацию AdaCore. Ничего хорошего из этого не получилось.

При обнаружении проблем я решил посмотреть, а как всё устроено в Unbounded_String? Оказалась там всё гораздо проще чем в векторах. Нет ничего лишнего, привнесённого из контейнеров. Можно сказать -- просто и элегантно! Я решил взять за основу Unbounded_String, а не Vectors.

Сейчас разрабатываю проект "Unbouded_Array". Функциональность "Vector_View" здесь реализуется через массивы "Array_Of_Byte_Type" или "String", полученные с помощью функций "To_Constant_Array" или "To_Constant_String". Тут надо помнить, что это не копии, а ссылки на данные в объекте "Unbounded_Array_Type". Функциональность "Vector_Edit" здесь реализуется за счёт подобных массивов, но полученных с помощью фукций "Get_Array_Variable" и "Get_String_Variable". При вызове этих функций исходный объект "Unbounded_Array_Type" блокируется на изменение. Всякая дальнейшая попытка изменить объект, включая вызов деструктура, вызывает исключение "Buffer_Locked". Снятие блокировки обеспечивается вызовом процедуры "Unlock_Change".

Проблему, затрагивающуюся в теме "Поддержка 32битного Юникода для Ada 95", я уже обдумывал до появления этой темы. Пакет "XmlAda" совместим с АДА95, потому что в нём не применяются типы "Wide_Wide_***", "Wide_***", а типы "UTF8String", "UTF16**String и "UTF32**String" просто алиасы типа "String". Исходя из подобной идеи, я для каждой процедуры, работающей с "Array_Of_Byte_Type", ввёл альтернативную для "String". Думаю ввести в струкру "Referenced_Buffer" для объекта "Unbounded_Array_Type" признаки "UTF32" и "BOM" (вернее "BE"). А также, за счёт манипуляции с указателями, обеспечить работу с массивами 32-х кодов UTF32.

Сейчас, всё что я наваял, опубликую на сервере OSDN.
OCTAGRAM
Цитата(Sergey Dukov @ 27.09.2019 3:40) *
Я реализовал преобразование UTF-8 в UTF-32. И, поневоле, пришлось создать простенький тестер для этой функциональности. Преобразование происходит правильно, но возникла проблема с удалением массивов из памяти. Попробовал исправить ошибки при размещении массивов в памяти, но это не помогло.


Кстати, пожелание сделать его двухпроходным. За первый проход вычислить требуемую длину, выделить нужной длины. И за второй проход наполнить данными.

Цитата(Sergey Dukov @ 27.09.2019 3:40) *
Вообще-то я с самого начала принял неправильный подход к построению реализации векторов октетов. Я лишь посмотрел, и то не совсем внимательно, приватную часть спецификации пакета от AdaCore и сделал почти всё по своему. Тип вектора я наследовал от Limited_Controlled, а не от Controlled. Испугался того, что во втором случае деструктор объекта может вызываться несколько раз. Не посмотрел как эта проблема решается стандартным способом. Далее начал городить свой огород исходя из меры своей распущенности, даже не подсматривая реализацию AdaCore. Ничего хорошего из этого не получилось.

При обнаружении проблем я решил посмотреть, а как всё устроено в Unbounded_String? Оказалась там всё гораздо проще чем в векторах. Нет ничего лишнего, привнесённого из контейнеров. Можно сказать -- просто и элегантно! Я решил взять за основу Unbounded_String, а не Vectors.


А не глядя в Unbounded_String, не получится?

Там максимум тайного знания может требоваться — про линейную амортизированную сложность мультипликативной стратегии выделения памяти и эмпирический коэффициент, который в Delphi, кажется, 1.2. По возможности этот коэффициент нужно задать двумя константами, числителем и знаменателем, то есть, 6 и 5.

В принципе, в Unbounded_String примерно как надо сделано, только я решительно против разделяемой пустой строки, за счётчик ссылок которой конкурируют все использующие строки потоки, ведь строковые переменные часто бывают пустыми.

Смотреть в реализации AdaCore бывает вредно.
Sergey Dukov
Цитата
Кстати, пожелание сделать его двухпроходным. За первый проход вычислить требуемую длину, выделить нужной длины. И за второй проход наполнить данными.

Это можно, но какие издержки больше: издержки на редкие вызовы процедуры увеличения буфера или издержки на повторный запуск преобразования?

Цитата
А не глядя в Unbounded_String, не получится?

Будет очень трудно и очень накладно заново изобретать велосипед. Я считаю "Unbounded_String" очень хорошей основой для "Unbounded_Array" и "Unbounded_Unicode_String".

Цитата
В принципе, в Unbounded_String примерно как надо сделано, только я решительно против разделяемой пустой строки, за счётчик ссылок которой конкурируют все использующие строки потоки, ведь строковые переменные часто бывают пустыми.

А разве предел счётчика в четыре миллиарда не достаточен? В большинстве случаев счётчик для разделяемой пустой строки не увеличивается. Он сначала уменьшается на единицу, а в конце процедуры снова увеличивается. Уменьшение счетчика безопасно для разделяемой пустой строки. Разделяемая пустая строка никогда не удаляется из памяти. На этом всё построено. За счёт разделяемой пустой строки решается проблема с повторными вызовами деструкторов. Так что без разделяемой пустой строки никак!

Если взять за основу "Unbounded_String", нужен ли прототип "Vector_Edit"? Разве мощности "Unbounded_String" для изменения данных не достаточно?



Добавлено через 7 мин.

Цитата
В принципе, в Unbounded_String примерно как надо сделано, только я решительно против разделяемой пустой строки, за счётчик ссылок которой конкурируют все использующие строки потоки, ведь строковые переменные часто бывают пустыми.

А разве в вашем проекте "Referece" не присутствует подобный объект?
OCTAGRAM
Цитата(Sergey Dukov @ 27.09.2019 22:05) *

Цитата
Кстати, пожелание сделать его двухпроходным. За первый проход вычислить требуемую длину, выделить нужной длины. И за второй проход наполнить данными.

Это можно, но какие издержки больше: издержки на редкие вызовы процедуры увеличения буфера или издержки на повторный запуск преобразования?


Логарифм по основанию 1.2 от, допустим, восьми тысяч всё же должен быть ощутим.

Цитата(Sergey Dukov @ 27.09.2019 22:05) *
Цитата
А не глядя в Unbounded_String, не получится?

Будет очень трудно и очень накладно заново изобретать велосипед. Я считаю "Unbounded_String" очень хорошей основой для "Unbounded_Array" и "Unbounded_Unicode_String".


По возможности, кстати, в нашем проекте, просто String_32.

Или, я вот подумываю, не объявить ли вообще String как 32битный String? Это можно сделать в корневом пакете, а все остальные если потом в него класть, они будут String и Character видеть из корневого пакета, а не из Standard.

Цитата(Sergey Dukov @ 27.09.2019 22:05) *
Цитата
В принципе, в Unbounded_String примерно как надо сделано, только я решительно против разделяемой пустой строки, за счётчик ссылок которой конкурируют все использующие строки потоки, ведь строковые переменные часто бывают пустыми.

А разве предел счётчика в четыре миллиарда не достаточен?
Дело не в количестве, дело в том, что на якобы параллельном языке программирования программы де факто работают последовательно. Все ждут, чтоб дёрнуть счётчик пустой строки. Как на одноядерном компьютере. Или как на Python с его GIL. Это какое-то непрекращающееся унижение. Вот нельзя было 18 лет назад просто взять и сделать как в Delphi.

Цитата(Sergey Dukov @ 27.09.2019 22:05) *
За счёт разделяемой пустой строки решается проблема с повторными вызовами деструкторов. Так что без разделяемой пустой строки никак!


В Delphi пустая строка — тупо nil (null), и всё работает. Динамический массив нулевой длины — тоже nil (null).

Вот у AdaCore как раз и велосипеды. Кривые. Не нравится.

Цитата(Sergey Dukov @ 27.09.2019 22:05) *
Если взять за основу "Unbounded_String", нужен ли прототип "Vector_Edit"? Разве мощности "Unbounded_String" для изменения данных не достаточно?


Да эти мощности ни о чём вообще. Вот прошлись мы по октетам раз, выяснили, сколько это будет codepoints. Выделили строку такой длины. Нам бы на неё теперь как на доступный на запись массив взглянуть и быстро в цикле ещё раз пройтись, записывая байты. А вместо этого предлагается пользоваться процедурами



Цитата(Sergey Dukov @ 27.09.2019 22:05) *
Добавлено через 7 мин.

Цитата
В принципе, в Unbounded_String примерно как надо сделано, только я решительно против разделяемой пустой строки, за счётчик ссылок которой конкурируют все использующие строки потоки, ведь строковые переменные часто бывают пустыми.

А разве в вашем проекте "Referece" не присутствует подобный объект?


Внезапно там банальный null

Кстати, передаваемый одним из параметров generic, ведь пакет спроектирован так, что не может напрямую знать, что первый тип generic — указатель.
Sergey Dukov
Цитата
Дело не в количестве, дело в том, что на якобы параллельном языке программирования программы де факто работают последовательно. Все ждут, чтоб дёрнуть счётчик пустой строки. Как на одноядерном компьютере. Или как на Python с его GIL. Это какое-то непрекращающееся унижение. Вот нельзя было 18 лет назад просто взять и сделать как в Delphi.

Тут всё в наших руках. Нужно сделать так, чтобы счётчик разделяемой пустой строки вообще никогда не менялся. И это очень просто! Цена -- одно сравнение указателей.

Цитата
В Delphi пустая строка — тупо nil (null), и всё работает. Динамический массив нулевой длины — тоже nil (null).

Вот у AdaCore как раз и велосипеды. Кривые. Не нравится.

В Дельфи строки и динамические строки встроенные объекты и строки можно размещать в пуле. В АДА динамических строк не существует и строки нельзя размещать в пуле. И это наследие не 18-летней, более чем 36-летней давности. Для реализации динамических сток в АДЕ были созданы библиотечные пакеты "Ada.Strings.Unbounded_***". Реализацию этих пакетов от AdaCore я считаю очень хорошей.

Цитата
По возможности, кстати, в нашем проекте, просто String_32.

Или, я вот подумываю, не объявить ли вообще String как 32битный String? Это можно сделать в корневом пакете, а все остальные если потом в него класть, они будут String и Character видеть из корневого пакета, а не из Standard.

Я думаю этого делать не стоит. в АДА всё завязано на тип "String". Лучше пусть будут разные имена типов.

Цитата
Да эти мощности ни о чём вообще. Вот прошлись мы по октетам раз, выяснили, сколько это будет codepoints. Выделили строку такой длины. Нам бы на неё теперь как на доступный на запись массив взглянуть и быстро в цикле ещё раз пройтись, записывая байты. А вместо этого предлагается пользоваться процедурами

Пусть будет так. Но тут нужно работать с указателями на массив, а не с самими массивами. При каждом обращении к элементу массива нужно разыменовывать указатель на массив. В АДЕ, в отличии от ПАСКАЛЯ, нет блоков разыменования переменных. Всё это немного увеличивает длину исходных кодов Хотя длина сгенерированных не увеличивается, компилятор с этой проблемой справляется.

Цитата
Внезапно там банальный null

Кстати, передаваемый одним из параметров generic, ведь пакет спроектирован так, что не может напрямую знать, что первый тип generic — указатель.

with System.Storage_Elements;

package Referencing with Pure, Preelaborate is

private

Dummy_Structure : aliased constant array
(Positive range 1 .. 3) of
System.Storage_Elements.Integer_Address :=
(0, 0, 0);

end Referencing;


В "Unbounded_String" функции структуры "Empty_Shared_String" аналогичны вашей "Dummy_Structure". Это просто реальный объект никогда не исчезающий из памяти.

Вы хотели чтобы проектируемый тип был основой аналога "Unbounded_Wide_Wide_String". Так пусть им будет тип подобный элегантному и мощному "Unbounded_String", чем какой-то там контейнер.
OCTAGRAM
Цитата(Sergey Dukov @ 28.09.2019 1:06) *
Цитата
Дело не в количестве, дело в том, что на якобы параллельном языке программирования программы де факто работают последовательно. Все ждут, чтоб дёрнуть счётчик пустой строки. Как на одноядерном компьютере. Или как на Python с его GIL. Это какое-то непрекращающееся унижение. Вот нельзя было 18 лет назад просто взять и сделать как в Delphi.

Тут всё в наших руках. Нужно сделать так, чтобы счётчик разделяемой пустой строки вообще никогда не менялся. И это очень просто! Цена -- одно сравнение указателей.


Нет, к этой цене надо ещё добавить пустую структуру для каждой инстанциации. У нас ведь не только строки из 32битных символов. Вектора со всякой всячиной могут быть, и для каждой всячины тогда подобная структура. Мне кажется, в Delphi лучше.

Цитата(Sergey Dukov @ 28.09.2019 1:06) *
Цитата
Или, я вот подумываю, не объявить ли вообще String как 32битный String? Это можно сделать в корневом пакете, а все остальные если потом в него класть, они будут String и Character видеть из корневого пакета, а не из Standard.

Я думаю этого делать не стоит. в АДА всё завязано на тип "String".


Всё такое завязанное требуется калёным железом выжигать, и переопределить Character и String — вполне себе метод. Мне нравится статья http://live.julik.nl/2005/12/composition-n…tion-and-morons Требуется в своих проектах более лютый Освенцим, чем в Java.

Цитата(Sergey Dukov @ 28.09.2019 1:06) *
Лучше пусть будут разные имена типов.


Человеческий 32битный тип называется String, а, если очень надо, к историческому недоразумению можно обращаться как к Standard.String

Цитата(Sergey Dukov @ 28.09.2019 1:06) *
Пусть будет так. Но тут нужно работать с указателями на массив, а не с самими массивами. При каждом обращении к элементу массива нужно разыменовывать указатель на массив. В АДЕ, в отличии от ПАСКАЛЯ, нет блоков разыменования переменных. Всё это немного увеличивает длину исходных кодов Хотя длина сгенерированных не увеличивается, компилятор с этой проблемой справляется.


Ada 2012 версия редактора готовит Ada 2012 ссылку, в которой, по существу, жирный указатель на данные. Ada 2012 магически дописывает .Data.all. Ада 95 этого делать не будет, но это не помешает дописать .Data.all вручную. В declare-begin-end после объявления редактора пишется Buffer : String renames Editor.Data.Data.all;, и по Buffer красиво быстро проходимся. На этом некрасота заканчивается.

Цитата(Sergey Dukov @ 28.09.2019 1:06) *
В "Unbounded_String" функции структуры "Empty_Shared_String" аналогичны вашей "Dummy_Structure". Это просто реальный объект никогда не исчезающий из памяти.


Причина, по которой я его объявил, принципиально иная. В ходе инициализации редактор конструирует внутри себя жирный указатель на редактируемую строку. Но до того, как он начнёт это делать, объект внутри уже должен быть чем-то инициализирован, а потом перезаписывается полезным значением. Я хотел дать гарантии, что объект не может быть null. Но тогда и до инициализации он не может быть null, а чем-то тогда должен быть, проходящим языковые проверки. Никакой другой полезной нагрузки эта структура не несёт, насколько я помню.

Цитата(Sergey Dukov @ 28.09.2019 1:06) *
Вы хотели чтобы проектируемый тип был основой аналога "Unbounded_Wide_Wide_String". Так пусть им будет тип подобный элегантному и мощному "Unbounded_String", чем какой-то там контейнер.


А чем Unbounded_* не контейнер? В Delphi динамические строки и динамические массивы почти по одним и тем же принципам работают.

Но вообще некоторая разница есть. У вектора есть блокировки на обновление и т.п. Я планировал порешать эту проблему так, что у строк и векторов общая структура в динамической памяти, и из массива в строку и обратно можно эти структуры переливать, но ни вектор не содержит в себе строку, ни наоборот.
Sergey Dukov
Цитата
Нет, к этой цене надо ещё добавить пустую структуру для каждой инстанциации. У нас ведь не только строки из 32битных символов. Вектора со всякой всячиной могут быть, и для каждой всячины тогда подобная структура. Мне кажется, в Delphi лучше.

В реализации Unbounded_String от GNAT структура "Empty_Shared_String" является заглушкой для пустой строки. Использовать значение null для поля Unbounded_String.Reference в АДЕ очень и очень неудобно. Компилятор ДЕЛЬФИ для встроенных типов сам с этим разбирается. В АДЕ для Библиотечных типов это недопустимо. Иначе нужно бы было разбираться с исключениями доступа к содержимому нулевого указателя. А в смысле "инстанциации" что присваивать полю Unbounded_String.Reference значение null или указатель на статический объект "Empty_Shared_String" по затратам совершенно одинаково. Но зачем AdaCore, при достижении длины строки нулевого значения, увеличивает счётчик объекта "Empty_Shared_String" (и этот счётчик никогда не уменьшается) совершенно непонятно. Я в своём проекте "Unbouded_Array" это удалил и мой объект "Empty_Referenced_Buffer" стал как бы константой.

Цитата
Или, я вот подумываю, не объявить ли вообще String как 32битный String? Это можно сделать в корневом пакете, а все остальные если потом в него класть, они будут String и Character видеть из корневого пакета, а не из Standard.

Я попробовал в своём проекте применить ваши спецификации "Ada_Magic_Forward". Компилятор GNAT на типы "Wide_Wide_***" выдаёт кучу предупреждений, а я "ВАРНИНГИ" очень не люблю. В этих спецификациях я объявил два типа -- Character_32 и String_32, а всё остальное удалил. Наверное, придётся только этим и довольствоваться.


Я скоро закончу проект "Unbouded_Array". Это будет полнофункциональным аналогом сразу двух пакетов: "Ada.Strings.Unbounded" и "Ada.Strings.Wide_Wide_Unbounded".
Функцинальность редактора я организовал с помощью двух процедур:
  procedure Start_Edit(Object : in out Unbounded_Array_Type;
Cookie_Value : Integer);
pragma Inline(Start_Edit);

procedure End_Edit(Object : in out Unbounded_Array_Type;
Cookie_Value : Integer;
New_Array : Array_Of_Byte_Type);


Пример использования редактирования без копирования в тестере.

Очень прошу посмотреть сегодняшнее состояние этого проекта на сервере OSDN и высказать замечания по существу этого проекта.
Это текстовая версия — только основной контент. Для просмотра полной версии этой страницы, пожалуйста, нажмите сюда.