Из Википедии, свободной энциклопедии
Перейти к навигацииПерейти к поиску

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

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

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

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

 ^ AI 1 ^ 2 г. н.э. фу ^ AE 2 бар ^ AI 2 баз ^ AE 2 ^ AE 1

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

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

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

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

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

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

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

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

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

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

См. Также

Ссылки

  1. ^ http://www.basepath.com/aup/talks/SCCS-Slideshow.pdf Рохкинд, Марк. «Система управления исходным кодом (SCCS)». IEEE Transactions по разработке программного обеспечения 1, вып. 4 (1975)
  2. ^ Тихи, Уолтер (1982). «Разработка, внедрение и оценка системы контроля версий» . ICSE '82 Труды 6-й Международной конференции по программной инженерии : 58–67 . Проверено 12 июня 2012 года .
  3. ^ http://sccs.sourceforge.net/man/sccsfile.4.html sccsfile (4) страница руководства
  4. ^ «Введение в бинарное переплетение» . www.bitkeeper.org .
  5. ^ https://web.archive.org/web/20061006032137/http://blog.fxa.org/articles/2005/09/30/bzr-weaving-its-way-to-the-front
  6. ^ "BzrWeaveFormat" . Bzr Wiki . Проверено 16 января 2020 года .