Главная
Блог разработчиков phpBB
 
+ 17 предустановленных модов
+ SEO-оптимизация форума
+ авторизация через соц. сети
+ защита от спама

C и копирование перекрывающихся областей памяти

Anna | 24.06.2014 | нет комментариев

Программируя на Си многие сталкивались с такими функциями как memcpy() и memmove(), по сути, функции делают одно и тоже, но вторая правильно отрабатывает обстановку, когда области памяти перекрываются (на что возникают добавочные убыточные расходы).

В мире С никто не воспрещает пользоваться этими функциями (Зачастую эти функции применяют разные механизмы оптимизации и могут статься стремительней своих собратьев из мира C ), но есть и больше родное средство, работающее через итераторы: std::copy. Это средство применимо не только к POD типам, а к любым сущностям, поддерживающим итераторы. О деталях реализации в эталоне ничего не сказано, но дозволено предположить, что разработчики библиотеки не настоль тупы, что бы не применять, оптимизированные memcpy()/memmove() когда это допустимо.

Но по вдохновению, хочется посмотреть, а что там с пересекающимися областями (overlapping memory blocks)? чай задача, на самом деле, не такая уж редкая. К примеру, хотим мы читать MPEG-TS пакеты (размер всякого 188 байт, всякий пакет начинается с 0×47 /sync byte/) из какого-то потока, и есть вероятность, что первое (а может и дальнейшее: скажем, имеем дело с M2TS контейнером, размер блока которого 192 байт и лишние 4 байта в большинстве случаем мы можем игнорировать /timestamp/) чтение может попасть на середину пакета. В таких случаях традиционно делается так: вычитываем блок 188 байт, дальше ищем байт синхронизации, если он в нулевой позиции — всё чудесно, если нет, то данные от него и до конца, необходимо переместить в предисловие блока, в освободившееся место необходимо дочитать недостающую долю, позже чего пакет считается вычитанным и дозволено отдавать его на обработку.

Наглядно процесс копирования данных в предисловие блока дозволено показать этой картинкой:
image

Т.е. видим, что есть перекрытие. Разумно было бы применить какой-то аналог memmove(), но в стандартной библиотеке есть только std::move тот, что делает абсолютно не то (здесь необходимо улыбнуться). Но при этом, читая изложение для std::copy видим следующую строчку:

The ranges shall not overlap in such a way that result points to an element in the range [first,last).

т.е. на самом деле, если предисловие области (result) куда копировать, лежит вне области [first,last), то всё должно быть ок. И это реально так.

Но посмотрим такую схему копирования с перекрытием:
image

пока не обращаем внимание на то, что result здесь в конце. Толк картинки в том, что блок памяти необходимо сдвинуть от начала на какое-то смещение вперёд, соответственно, если это смещение поменьше размера сдвигаемого блока, то адрес назначения у нас будет лежать в пределах [first,last), таким образом условие применимости std::copy не соблюдаются. И если применить его, мы легко затрём данным в перекрывающейся области.

Но здесь на поддержка нам приходит его собрат, как раз решающий эту задачу: std::copy_backward, всё различие этой функции в том, что он осуществляет копирование с конца. Т.е. для случая изображённой на 2-й картинке, он возьмёт (дальше дюже дерзко) элемент из last и ложится в result, дальше из last-1 в result-1, дальше из last-2 в result-2 и так дальше.

Видно, что при такой схеме копирования, когда мы начнём писать в перекрывающуюся область, данные в ней теснее будут обработаны. Т.е. для нас всё отлично. Комично, что условие применимости при перекрывающийся областях для std::copy_backward слово в слово повторяет данное условие для std::copy.

Выходит, резюмируя, примитивное правило:

  1. Если result < first («сдвиг блока к началу /или влево/»), то применяем std::copy, в качестве result указываем предисловие блока-назначения.
  2. Если result > first («сдвиг блока к концу /или вправо/»), то применяем std::copy_backward, в качестве result указываем конец блока-назначения.

Текст является творческим переосмыслением англоязычной статьи: www.trilithium.com/johan/2006/02/copy-confusion, картинки взяты от туда же, пример из собств

Источник: programmingmaster.ru

Оставить комментарий
БАЗА ЗНАНИЙ
СЛУЧАЙНАЯ СТАТЬЯ
СЛУЧАЙНЫЙ БЛОГ
СЛУЧАЙНЫЙ МОД
СЛУЧАЙНЫЙ СКИН
НОВЫЕ МОДЫ
НОВЫЕ СКИНЫ
НАКОПЛЕННЫЙ ОПЫТ
Форум phpBB, русская поддержка форума phpBB
Рейтинг@Mail.ru 2008 - 2017 © BB3x.ru - русская поддержка форума phpBB