Вектор допинга - Dope vector

В компьютерное программирование, а наркотик вектор это структура данных используется для хранения информации о объект данных,[1] особенно его макет памяти.

Цель

Допинговые векторы чаще всего используются для описания массивы, которые обычно хранят несколько экземпляров определенного типа данных как непрерывный блок памяти. Например, для массива из 100 элементов, каждый из которых занимает 32 байта, требуется 100 × 32 байта. Сам по себе такой блок памяти не имеет места для отслеживания того, насколько велик массив (или другой объект) в целом, насколько велик каждый элемент в нем или сколько элементов он содержит. Вектор допинга - это место для хранения такой информации. Допинговые векторы также могут описывать структуры которые могут содержать массивы или переменные элементы.

Если такой массив хранится непрерывно, с первым байтом в ячейке памяти M, то его последний байт находится в местоположении M + 3199. Основным преимуществом такой компоновки является то, что N легко: это начинается с места M + (N × 32). Конечно, значение 32 должно быть известно (это значение обычно называется «шагом» массива или «шириной» элементов массива). Перемещение по структуре данных массива с использованием индекса называется счисление.

Однако такое расположение (без добавления допинговых векторов) означает, что наличия местоположения элемента N недостаточно для определения самого индекса N; или шаг; или есть ли элементы в N − 1 или N + 1. Например, функция или метод могут перебирать все элементы в массиве и передавать каждый из них другой функции или методу, которые вообще не знают, что элемент является частью массива, не говоря уже о том, где и насколько велик массив.

Без вектора допинга даже знание адреса всего массива не скажет вам, насколько он велик. Это важно, потому что запись в N + 1 элемент в массиве, который содержит только N элементы, скорее всего, уничтожат некоторые другие данные. Поскольку многие языки программирования рассматривают символьные строки как своего рода массив, это напрямую ведет к печально известному Переполнение буфера проблема.

Вектор допинга уменьшает эти проблемы, сохраняя небольшое количество метаданные вместе с массивом (или другим объектом). С помощью допинговых векторов компилятор может легко (и необязательно) вставлять код, предотвращающий случайную запись за пределами конца массива или другого объекта. В качестве альтернативы, программист может получить доступ к вектору допинга при желании, для безопасности или для других целей.

Описание

Точный набор метаданных, включенных в вектор допинга, варьируется от одного языка и / или операционной системы к другому, но вектор допинга для массив может содержать:

  • указатель на место в памяти, где начинаются элементы массива (обычно это идентично местоположению нулевого элемента массива (элемент со всеми индексами 0). Это может быть не первый фактический элемент, если индексы не начинаются с нуля .
  • тип каждого элемента массива (целое, логическое, конкретное класс, так далее.),
  • то ранг массива,
  • размер массива (его диапазон индексов). Во многих языках начальный индекс для массивов фиксируется на нуле или единице, но конечный индекс устанавливается, когда массив (пере) выделяется.
  • для массивов, в которых степень использования в данный момент может измениться, могут быть сохранены как максимальная, так и текущая экстенты.
  • то шаг массива, или объем памяти, занимаемый каждым элементом массива.

Затем программа может обратиться к массиву (или другому объекту, использующему вектор допинга), ссылаясь на вектор допинга. Обычно это происходит автоматически в языки высокого уровня. Добраться до элемента массива стоит немного дороже (обычно одна инструкция, которая извлекает указатель на фактические данные из вектора допинга). С другой стороны, выполнение многих других общих операций проще и / или быстрее:

  • Без вектора допинга определение количества элементов в массиве невозможно. Таким образом, обычно в конец массива добавляют дополнительный элемент с «зарезервированным» значением (например, NULL). Затем длину можно определить путем сканирования массива вперед и подсчета элементов до тех пор, пока не будет достигнут этот «конечный маркер». Конечно, это делает проверку длины намного медленнее, чем поиск длины непосредственно в векторе допинга.
  • Не зная размера массива, невозможно свободный() (освободить) эту память, когда она больше не нужна. Таким образом, без допинговых векторов что-то должно хранить эту длину где-то еще. Например, запрос конкретной ОС выделить место для 3200-байтового массива может привести к выделению 3204 байта в некотором месте M; Затем он сохранит размер в первых 4 байтах и ​​сообщит запрашивающей программе, что выделенное пространство начинается с M + 4 (так что вызывающий не будет рассматривать дополнительные 4 байта как часть собственно массива). Эти дополнительные данные не считаются вектором допинга, но служат для достижения тех же целей.
  • Без допинговых векторов необходимо также хранить дополнительную информацию о шаге (или ширине) элементов массива. В C, эта информация обрабатывается компилятором, который должен отслеживать различие типов данных между «указателем на массив элементов шириной 20 байт» и «указателем на массив элементов шириной 1000 байт». Это означает, что указатель на элемент в любом виде массива может быть увеличен или уменьшен, чтобы достичь следующего или предыдущего элемента; но это также означает, что ширину массива необходимо зафиксировать на более раннем этапе.

Даже с вектором допинга наличие (только) указателя на конкретный член массива не позволяет найти позицию в массиве, или местоположение массива, или сам вектор допинга. Если это желательно, такую ​​информацию можно добавить к каждому элементу в массиве. Такая информация по элементам может быть полезной, но не является частью вектора допинга.

Допинговые векторы могут быть общим средством, совместно используемым для нескольких типов данных (не только для массивов и / или строк).[2]

Смотрите также

использованная литература

  1. ^ Pratt, T .; Зельковиц, М. (1996). Языки программирования: разработка и реализация (3-е изд.). Река Верхний Сэдл, Нью-Джерси: Prentice-Hall. п. 114. ISBN  978-0-13-678012-0.
  2. ^ Клейбрук, Билли Г. (13–15 октября 1976 г.). Проектирование структуры шаблона для средства определения обобщенной структуры данных. ICSE '76: 2-я международная конференция по программной инженерии. Сан-Франциско, Калифорния, США: Пресса компьютерного общества IEEE. С. 408–413.