Перемежающиеся дельты

Чередование дельт , или переплетение SCCS, — это метод, используемый системой контроля исходного кода для хранения всех версий файла. Все строки из всех редакций «сплетены» вместе в единый блок данных с вкраплениями управляющих инструкций, указывающих, какие строки в какие ревизии файла включены. Чередование дельт традиционно реализуется с учетом строковых текстовых файлов, хотя ничто не мешает применить этот метод и к двоичным файлам.

Чередование дельт было впервые реализовано Марком Рочкиндом в SCCS в 1975 году. Его конструкция делает все версии доступными одновременно, так что для получения любой версии требуется одинаковое время. Он также содержит достаточную информацию для идентификации автора каждой строки (обвинения) в одном блоке. ^[1] С другой стороны, поскольку анализируются все версии файла, каждая операция становится медленнее по мере добавления новых версий. Термин «чередующаяся дельта» был придуман позже, в 1982 году, Уолтером Ф. Тичи , автором системы контроля версий , которая сравнивает переплетение SCCS с его новым механизмом обратной дельты в RCS. ^[2]

Реализация в SCCS

В SCCS следующий блок переплетения

 ^AI 1
 ^AD 2
 foo
 ^AE 2
 bar
 ^AI 2
 baz
 ^AE 2
 ^AE 1

представляет файл, содержащий строки «foo» и «bar» в первой версии и строки «bar» и «baz» во второй версии. Строка «^A» обозначает символ управления-A.

Линии управления в чередующемся дельта-блоке имеют следующее значение: ^[3]

^AI серийный Запускает блок строк, вставленный с указанным серийным номером.
^AD серийный Запуск блока строк, который был удален с указанным серийным номером.
^AE серийный номер Конец блока для соответствующего оператора ^AI или ^AD , который использует тот же серийный номер.

Преимущества

Время, необходимое для извлечения любой ревизии из такого чередующегося дельта-блока, пропорционально размеру архива. Размер архива — это сумма размеров всех разных строк во всех ревизиях.

Чтобы извлечь конкретную ревизию, необходимо создать массив структур, сообщающий, будет ли конкретный блок, помеченный серийным номером в чередующихся дельтах, скопирован на выход или нет. Исходная реализация SCCS требует ок. 100 байт памяти для каждого серийного номера в дельтах, чтобы знать, как извлечь конкретную версию. Таким образом, для распаковки файла истории SCCS с одним миллионом дельт потребуется 100 МБ виртуальной памяти. Размер можно уменьшить прибл. 32 байта на дельту, если извлечение файла с аннотациями не требуется.

Преимущества метода плетения заключаются в следующем:

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

Программное обеспечение, использующее чередующиеся дельты

В 2006 году Bazaar намеревался использовать чередующиеся дельты. ^[5] но от него отказались из-за плохой производительности после того, как он был реализован в bzr 0.1. Он по-прежнему предоставляет алгоритм слияния в стиле переплетения. ^[6]

См. также

Дельта-кодирование

Ссылки

^ http://www.basepath.com/aup/talks/SCCS-Slideshow.pdf Рочкинд, Марк. «Система контроля исходного кода (SCCS)». Транзакции IEEE по разработке программного обеспечения 1, вып. 4 (1975)
^ Тичи, Уолтер (1982). «Проектирование, внедрение и оценка системы контроля версий» . ICSE '82 Материалы 6-й Международной конференции по программной инженерии : 58–67 . Проверено 12 июня 2012 г.
^ http://sccs.sourceforge.net/man/sccsfile.4.html страница руководства sccsfile(4).
^ «Введение в бинарное переплетение» . www.bitkeeper.org .
^ «БЗР пробирается на фронт» . blog.fxa.org . Архивировано из оригинала 6 октября 2006 года . Проверено 12 января 2022 г.
^ «БзрВеавеФормат» . Бзр Вики . Проверено 16 января 2020 г. .

[1] ttp://www.basepath.com/aup/talks/SCCS-Slideshow.pdf Рочкинд, Марк. «Система контроля исходного кода (SCCS)». Транзакции IEEE по разработке программного обеспечения 1, вып. 4 (1975)

[rcs-2] Тичи, Уолтер (1982). «Проектирование, внедрение и оценка системы контроля версий» . ICSE '82 Материалы 6-й Международной конференции по программной инженерии : 58–67 . Проверено 12 июня 2012 г.

[3] ttp://sccs.sourceforge.net/man/sccsfile.4.html страница руководства sccsfile(4).

[4] «Введение в бинарное переплетение» . www.bitkeeper.org .

[5] «БЗР пробирается на фронт» . blog.fxa.org . Архивировано из оригинала 6 октября 2006 года . Проверено 12 января 2022 г.

[6] «БзрВеавеФормат» . Бзр Вики . Проверено 16 января 2020 г. .

[1]

[2]

[3]

[4]

[5]

[6]