УДК 681.3.02                  Интеллектуальные САПР-2003            Безопасность информационных технологий


ШАБЛОНЫ ДЛЯ ОРГАНИЗАЦИИ КОНТРОЛЯ ИНДЕКСОВ В ПРОГРАММАХ НА ЯЗЫКАХ C++ И С

 

Шакиров Рауль Нурович, к.т.н.

Институт машиноведения УрО РАН, Россия, 620219, г. Екатеринбург, ул. Комсомольская, 34,

тел. (3432)75-35-80, факс (3432)74-53-30, E-mail: raul@imach.uran.ru

 

Аннотация: Шаблоны многомерных динамических массивов реализуют технику автоматического выделения памяти и защиту от ошибок индексации без существенного снижения производительности. Шаблоны применяются для реализации вычислительных алгоритмов, переноса 16-разрядных программ в 32-разрядную среду и организации отладочного контроля индексов в программах на языках C++ и C.

 

1. Введение

 

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

 

К числу машинно-ориентированных языков относятся язык C и его объектная модификация C++, стандартизованная ISO/IEC в 1998 году [1]. Машинная ориентация выражается в выборе примитивов, имеющих наиболее простую и эффективную аппаратную реализацию. Компромисс с человеком заключается в синтаксических удобствах, которые помогают программисту воспринимать машинную логику. Благодаря этому сочетанию высокой эффективности и синтаксического комфорта язык C стал фетишем суперпрограммистов - и одновременно проклятием для конечных пользователей, вынужденных иметь дело с многочисленными ошибками в программном обеспечении.

 

Создатели языков C и C++ последовательны: всякий раз, когда приходится выбирать между эффективностью и надежностью, выбор делается в пользу эффективности. В то же время язык С++ наделен развитыми синтаксическими средствами – классами и шаблонами, которые позволяют вводить нестандартные примитивы. Мы покажем, что нестандартные примитивы позволяют реализовать более естественную для человека логику программирования без существенной потери эффективности.

 

Нашей целью будет исследование вопроса о реализации многомерных динамических массивов и средств контроля индексов при обращении к элементам этих массивов. Пользуясь механизмом шаблонов, мы введем эти средства в язык C++ и сравним их со штатными примитивами по критериям наглядность-надежность-производительность. В качестве примеров применения динамических массивов будет описана методика портирования унаследованных 16-разрядных программ в 32-разрядную среду, а также макросы для организации отладочного контроля индексов в программах на языке С.

 

1. Автоматическая проверка индекса

 

Возможность автоматической проверки индекса при обращении к элементу массива предусмотрена в ряде языков программирования, из которых наиболее известными из которых являются Java [2] и C# [3]. В языке Java контроль индексов является обязательным, а в языке C# его можно отключить в блоке “небезопасного” кода. В языках C и C++ контроля индексов нет, как применительно к стандартным массивам, так и применительно к контейнерным объектам STL. Отсутствие автоматической проверки индекса означает, что программист должен гарантировать корректность индекса - в противном случае программа будет содержать скрытую ошибку, например, такую, как знаменитая ошибка переполнения буфера в программе sendmail.

 

Считается, что отсутствие автоматической проверки индекса имеет и свои положительные стороны - большую свободу для профессионального программиста и более высокую производительность программы.

 

2. Динамические массивы

 

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

 

Динамические массивы реализованы в классе Vector языка Java и в шаблоне vector библиотеки STL языка C++. Реализация основана на технике хранения элементов в непрерывной области памяти, с последовательным удвоением ее размеров по мере заполнения массива данными. В табл. 1 проводится сравнение непрерывных динамических массивов и динамических структур, основанных на хранении элементов в несмежных областях памяти - таких, как связный список и двоичное дерево.

                                  Структуры

Свойства

Динамический массив

Динамические структуры с несмежным размещением элементов

Время доступа к элементу по его индексу

Не зависит от числа элементов

Пропорционально числу элементов или логарифму числа элементов

Число операций распределения памяти

Пропорционально логарифму числа элементов

Пропорционально числу элементов

 

Табл. 1. Сравнение различных динамических структур

 

Реализация Vector в языке Java страдает из-за концептуальных ограничений этого языка. Из-за отсутствия в языке Java шаблонов базовый массив класса Vector содержит не значения, а ссылки на объекты, расположенные в динамической памяти. Это снижает производительность массива, повышает расход памяти и увеличивает нагрузку на процесс сборки “мусора”. Java не позволяет переопределять операторы, поэтому для обращения к элементу массива вместо оператора [] предлагается использовать методы ElementAt и SetElementAt. При обращении к несуществующему элементу массива возбуждается исключение. Размер массива надо устанавливать вручную с помощью метода EnsureCapacity.

 

Реализация vector в библиотеке STL основана на применении шаблонов и по производительности не отличается от обычных встроенных массивов. Обращение к элементу массива выполняется с помощью оператора []. В связи с установкой на максимальную производительность проверка индекса не выполняется - т.е. программист не может рассчитывать на предсказуемое поведение программы в случае ошибочной индексации. Для обращения к элементу массива с контролем индекса предусмотрен метод at. Управление размером массива выполняется вручную с помощью метода resize.

 

3. Динамические массивы с автоматическим увеличением размера

 

Как упоминалось, автоматическая проверка индекса при обращении к элементу массива уже реализовано в языках Java и C#, При выходе индекса за границы массива виртуальная машина возбуждает исключение. Возможность увеличения размера массива в этих языках не предусмотрена, т.к. размер массива фиксируется при его создании. Альтернативное решение заключается в автоматическом увеличении размера массива, что позволяет продолжать работу программы в штатном режиме. Так мы приходим к понятию динамического массива с автоматическим увеличением размера.

 

В языках группы C (C++/Java/C#) таких массивов нет, поэтому реализация проводилась автором для языка C++ [4]. Результаты разработки представлены на листингах 1 и 2 в виде упрошенного заголовочного файла Exarray.h и вспомогательного модуля Exarray.cpp. Полные версии указанных файлов находятся на странице http://www.imach.uran.ru/exarray.

 

Чтобы облегчить применение динамических массивов, следует избавить программиста от необходимости переучиваться. Для этого класс exarray объявлен так, чтобы перевод программы на использование неограниченных массивов можно было выполнить путем простой замены деклараций, без необходимости коррекции исполняемого кода.

 

Динамический массив создается с указанием типа элементов:

                exarray<тип> имя;

Например, целочисленный массив row объявляется так:

                exarray<int> row;

 

Размер массива не задается. Вместо этого принимается, что массив имеет неограниченное число элементов, которым первоначально присвоены нулевые значения, либо значения, заданные конструктором класса по умолчанию. Фактически, массив первоначально имеет нулевой размер, но при обращении к любому элементу размер массива автоматически увеличивается. При переполнении разрядной сетки индекса или нехватке памяти программа завершит работу с выдачей диагностики. Отсутствие ограничений на число элементов сокращает число особых ситуаций, которые могут возникнуть при выполнении программы. Фиксация начальных значений исключает возможность заполнения массива случайными значениями. Это облегчает процесс верификации и тестирования программы, в том числе с применением формальных методов, подобных описанным в [5]


template <class T> class exarray

{

  T*          e;       // Базовый массив

  unsigned       len;       // Число элементов

                    // Распределение памяти

  void realloc (unsigned size);

  void grow    (unsigned i);

 

public:

 

// Конструктор динамического массива.

  exarray ()       { len = 0; e = 0; }

 

// Конструктор копирования и операция

// присваивания. Реализация отсутствует,

// поэтому при попытке присваивания

// динамических массивов выдается

// сообщение об ошибке.

  exarray (const exarray<T>&);

  exarray<T>& operator =

    (const exarray<T>&);

// Деструктор динамического массива.

  ~exarray()       { realloc (0);       }

 

// Доступ к массиву с проверкой индекса.

// При выходе индекса за границы массива

// размер массива увеличивается, далее

// проводится обнуление памяти и вызов

// конструкторов по умолчанию для всех

// вновь организованных элементов.

  T&    operator [] (unsigned i)

   { if (len<=i) grow(i); return e[i]; }

 

  T&    operator [] (int i)

   { return (operator[]((unsigned)i)); }

 

  T&    operator *  ()

   { if (len<=0) grow(0); return e[0]; }

 

// Доступ к массиву без проверки индекса.

  T&   item (int i)       { return (e[i]);}

  T*   base ()             { return (e);   }

 

// Автоматическое преобразование в

// const T* для передачи массива в

// функцию через параметр const T*.

  operator const T* () { return (e);   }

};

 

 

// Прототипы функций файла Exarray.cpp.

void       exmrealloc (void **p,

       unsigned size, unsigned oldsize);

unsigned excalcsize (unsigned size);

 

// Функция exmuladd вычисляет n*s + k.

// При переполнении выдается ~0u.

inline unsigned exmuladd

  (unsigned s, unsigned n, unsigned k)

{ return((n<=(~0u-k)/s)? n*s + k: ~0u);}

 

// Фиктивный класс для вызова

// конструкторов и деструкторов без

// распределения памяти.

template <class T> struct __EXRELOC

{

  T value;

  void* operator new (unsigned, void* p)

                        { return p ;}

  void  operator delete (void*) {  ;}

};

 

// Приватный метод realloc устанавливает

// размер динамического массива в байтах.

// При увеличении размера вызываются

// конструкторы элементов, а при

// уменьшении размера - деструкторы.

template <class T> void exarray<T>::realloc (unsigned size)

{

  unsigned i = len, n = size/sizeof (T);

 

  while (i > n)     // Вызов деструкторов

  { i--; delete (__EXRELOC<T> *)(e + i);}

 

  exmrealloc       // Распределение памяти

       ((void **)&e, size, sizeof(T)*i);

  len = n;

  while (i < n)     // Вызов конструкторов

  { new (e + i)__EXRELOC<T>; i++; }

}

 

// Приватный метод grow распределяет

// память для элементов с индексами от 0

// до i c дополнительным резервированим.

template <class T> void exarray<T>::grow (unsigned i)

{

  realloc (excalcsize (

    exmuladd (sizeof(T), i, sizeof(T))));

}


Листинг  1.   Шаблон динамических массивов Exarray.h

 


#include <malloc.h>

#include <string.h>

#include <stdlib.h>

 

// Функция exmrealloc выделяет, удлиняет,

// укорачивает и освобождает блоки

// памяти, заполненные нулями.

void       exmrealloc (void **p,

       unsigned size, unsigned oldsize)

{

  if (size)         // Выделение памяти

  {

    if (size > (~0u)-9)

      abort();            // Переполнение size

    if ((*p = realloc (*p, size))==NULL)

      abort();            // Ошибка размещения

    if (size > oldsize)

      memset          // Обнуление

    ((char*)*p+oldsize, 0, size-oldsize);

  }

  else              // Оcвобождение памяти.

  {

    if (*p) { free (*p); *p = NULL; }

  }

}

// Функция excalcsize вычисляет размер

// блока памяти в байтах, который должен

// быть не меньше требуемого, для чего

// начальный размер SIZE_MOD поочередно

// умножается на 2 и 1.5.

// При переполнении выдается ~0u.

// Для уменьшения фрагментации

// динамической памяти учитывается

// размер системных данных SIZE_SYS,

// добавляемых функцией realloc.

#define SIZE_MOD (112)

#define SIZE_SYS (sizeof(int) * 2)

unsigned excalcsize (unsigned size)

{

  unsigned n = SIZE_MOD, k = 0;

  for (;; k = ~k,

       (k? (n <<= 1): (n += (n >> 1))))

  {

    n -= SIZE_SYS; if (n  >= size) break;

    n += SIZE_SYS; if ((int)n < 0)

                      { n = ~0u; break;}

  }

  return (n);

}


Листинг 2.  Вспомогательный модуль Exarray.cpp

 

Для определения многомерного динамического массива применяется оператор typedef. Например, двумерная целочисленная матрица matrix объявляется так:

                typedef exarray<int> row;

                exarray<row> matrix;

 

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

                typedef int int5 [5];

                exarray<int5> matrix;

 

Для передачи динамического массива в функцию в ней объявляется параметр:

                exarray<тип>& имя;

 

Для обращения к элементу массива с целью его чтения или записи применяется стандартная нотация:

                имя [индекс]

Повторное обращение к элементу массива может проводиться без контроля индекса по методу item:

                имя.item (индекс)

 

4. Динамические указатели

 

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

 

Указанное ограничение можно снять, если реализовать динамический массив в виде непрерывного массива указателей на значения элементов, а сами значения размещать по фиксированным адресам в различных фрагментах динамической памяти. Такое решение напоминает схему, принятую в языке Java и характеризуется невысокой производительностью, т.к. на каждое обращение к элементу динамического массива приходится два обращения к оперативной памяти. С одной из реализаций этой идеи можно познакомиться в работе [6].

 

Альтернативное решение содержится в полном варианте файла Exarray.h, где определен шаблон динамических указателей. Динамические указатели не имеет аналогов ни в языке Java, ни в библиотеке STL. Каждый динамический указатель привязан к определенному неограниченному массиву и характеризуется смещением в этом массиве, которое разрешается менять с помощью арифметических операций. При обращении через указатель к несуществующему элементу фактический размер массива автоматически увеличивается.

 

Динамический указатель объявляется как

                expoint<тип> имя;

При определении указатель может быть инициализирован динамическим массивом. Например, указатель на динамический массив row из разд.3 объявляется так:

                 expoint<int> p = row;

Далее можно выполнять привычные операции над указателем типа p [3], p += 3, *p++, p = NULL и т.п.

 

Динамические указатели могут применяться только для адресации одномерных динамических массивов и старшего динамического измерения многомерных массивов.

 

5. Производительность динамических массивов

Для проведения сравнительных испытаний использовались программы перемножения матриц matrix1.cpp и matrix2.cpp на листингах 3 и 4. Программа matrix1 написана в традиционном стиле с использованием статических массивов. Программа matrix2 использует динамические массивы. Различия в текстах программ выделены жирным шрифтом. Входные данные программ поступают из текстового файла, в котором содержится размер матриц и далее - сами матрицы. Разбиение файла на строки – произвольное.


Сравнивая программы, отметим, что в программе matrix1 нет проверки индексов, поэтому при попытке перемножения матриц с размером dim более 500 программа ведет себя непредсказуемо. Другой недостаток заключается в том, что для увеличения максимального размера матриц следует увеличить размер статических массивов; при этом увеличенный объем памяти потребуется даже при перемножении небольших матриц.


// Программа matrix1.cpp

#include <fstream.h>

#define  DIM 500

 

int    main       (int argc, char **argv)

{

  if (argc < 3) return 1;

  static int m1[DIM][DIM];

  static int m2[DIM][DIM];

  static int m3[DIM][DIM];

  int i,j,k,dim = 0;

 

  // Ввод исходных данных

  ifstream fin (argv[1]);

  if (!fin) return 1;

  fin >> dim;

  for (i = 0; i < dim; i++)

    for (j = 0; j < dim; j++)

      fin >> m1[i][j];

  for (i = 0; i < dim; i++)

    for (j = 0; j < dim; j++)

      fin >> m2[i][j];

 

  // Перемножение матриц

  for (i = 0; i < dim; i++)

    for (j = 0; j < dim; j++)

    {

      int sum = 0;

      for (k = 0; k < dim; k++)

        sum += m1[i][k] * m2[k][j];

      m3[i][j] = sum;

    }

 

  // Вывод результата

  ofstream fout (argv[2]);

  if (!fout) return 1;

  for (i = 0; i < dim; i++)

  {

    for (j = 0; j < dim; j++)

    { fout.width(6); fout << m3[i][j]; }

    fout << '\n';

  }

  return 0;

}

 

// Программа matrix2.cpp

#include <fstream.h>

#include "Exarray.h"

int    main       (int argc, char **argv)

{

  if (argc < 3) return 1;

 

  typedef exarray<int> row;

  exarray <row> m1,m2,m3;

  int i,j,k,dim = 0;

 

  // Ввод исходных данных

  ifstream fin (argv[1]);

  if (!fin) return 1;

  fin >> dim;

  for (i = 0; i < dim; i++)

    for (j = 0; j < dim; j++)

      fin >> m1[i][j];

  for (i = 0; i < dim; i++)

    for (j = 0; j < dim; j++)

      fin >> m2[i][j];

 

  // Перемножение матриц

  for (i = 0; i < dim; i++)

    for (j = 0; j < dim; j++)

    {

      int sum = 0;

      for (k = 0; k < dim; k++)

        sum += m1[i][k] * m2[k][j];

      m3[i][j] = sum;

    }

 

  // Вывод результата

  ofstream fout (argv[2]);

  if (!fout) return 1;

  for (i = 0; i < dim; i++)

  {

    for (j = 0; j < dim; j++)

    { fout.width(6); fout << m3[i][j]; }

    fout << '\n';

  }

  return 0;

}


Листинги 3, 4.  Программы перемножения матриц matrix1 и matrix2

 

Указанные недостатки программы matrix1 можно преодолеть за счет применения оператора динамического распределения памяти new, но это сделает программу более громоздкой, а ее алгоритм – труднее читаемым. По наблюдениям автора, прикладные программисты предпочитает создавать некорректные и расточительные, но удобочитаемые программы, подобные matrix1. Интересно в связи с этим отметить, как стремительно растут требования к оперативной памяти в современном системном и прикладном обеспечении – при относительно небольшом росте функциональности. И все эти программы пишутся на языке С++, который считается языком высокоэффективного программирования!

 

Программа matrix2, при полном сохранении удобочитаемости, не обладает ни одним из недостатков программы matrix1. Оперативная память распределяется автоматически по мере необходимости, а при ее нехватке программа прекращает работу.

 

Результаты испытания программ для различных компиляторов, платформ и размеров матриц приведены на странице http://www.imach.uran.ru/exarray. Отношение времени перемножения матриц на программе matrix2 к времени программе matrix1 составляет от 67 до 300% при средних показателях 120-180%. При сравнении производительности не учитывалось время, затраченное на запуск программы и ввод-вывод данных. При небольших размерах матриц программа matrix2 запускается быстрее, чем matrix1 в силу меньшего расхода оперативной памяти.

6. Возможности ручной оптимизации программ

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

 

После ручной оптимизации программ matrix1 и matrix2 время их работы становится одинаковым. Текст оптимизированного варианта matrix2 приведен на листинге 5. В оптимизированном варианте применяется транспонированная матрица m2, а критический участок кода выделен в подпрограмму scalar, использующую обычные указатели.

 


// Программа matrix3.cpp

// Оптимизированное перемножение матриц

#include <fstream.h>

#include "Exarray.h"

 

// Скалярное произведение

int scalar (const int* p1, const int *p2,

int dim)

{

  int sum = 0;

  while (--dim >= 0)

       sum += (*p1++) * (*p2++);

  return (sum);

}

 

int    main       (int argc, char **argv)

{

  if (argc < 3) return 1;

 

  typedef exarray<int> row;

  exarray <row> m1,m2,m3;

  int i,j,k,dim = 0;

 

  // Ввод исходных данных

  ifstream fin (argv [1]);

  if (!fin) return 1;

  fin >> dim;

  for (i = 0; i < dim; i++)

    for (j = 0; j < dim; j++)

      fin >> m1[i][j];

  for (i = 0; i < dim; i++)

    for (j = 0; j < dim; j++)

      fin >> m2[j][i];       // Транспонирование

 

  // Перемножение матриц

  for (i = 0; i < dim; i++)

    for (j = 0; j < dim; j++)

      m3[i][j] = scalar(m1[i],m2[j],dim);

 

  // Вывод результата

  ofstream fout (argv[2]);

  if (!fout) return 1;

  for (i = 0; i < dim; i++)

  {

    for (j = 0; j < dim; j++)

    { fout.width(6); fout << m3[i][j]; }

    fout << '\n';

  }

  return 0;

}


 

Листинг 5.  Оптимизированная программа перемножения матриц matrix3

 

7. Применение динамических массивов для обновления унаследованных программ

 

Одна из областей применения динамических массивов связана с переводом существующих 16-разрядных программ в 32-разрядный режим для увеличения размера обрабатываемых данных. Во многих 16-разрядных программах используется статическое распределение памяти в пределах 640 КБайт, доступных для MS-DOS. В 32-разрядном варианте программы желательно иметь динамическое распределение памяти, зависящее от объема обрабатываемых данных. Для этого программа переводится на использование динамических массивов:

1.        Если в тексте программы имеются операторы & или sizeof применительно к массивам, то & удаляется (это тавтология), а sizeof заменяется размерными переменными или константами. Если в программе применяются функции malloc/calloc и free, то они заменяются, соответственно, на new и delete.

2.        Параметры-массивы всех функций подразделяются на входные и выходные. К указателям, соответствующим входным массивам, добавляется модификатор const (применение модификатора const входит в понятие грамотного программирования, но многие реальные программисты этим пренебрегают).

3.        Там, где это требуется, обычные массивы и указатели заменяются на динамические массивы и указатели.

4.        При передаче динамического массива или указателя в качестве входного параметра функции выполняется автоматическое преобразование к обычному const-указателю. Доступ к динамическому массиву по const-указателю выполняется без проверки индексов в пределах заполненной части массива. Существенный момент заключается в том, что в процессе выполнения функции входной динамический массив не должен менять свой размер - для этого следует обеспечить, чтобы при вызове функции этот же массив не передавался в качестве одного из ее выходных параметров.

5.        Если динамический массив передается в качестве выходного параметра функции, то соответствующий параметр объявляется как exarray&<тип> или expoint<тип>. Первый вариант предпочтителен с точки зрения производительности. Для передачи динамического указателя следует использовать параметр вида expoint<тип>. Если динамический массив или указатель передается в качестве выходного параметра стандартной функции, текст которой недоступен, то создается функция-оболочка, управляющая размером массива (оболочки для функций из string.h входят в состав файла exstring.h).

 

Описанная методика была применена разработчиками САПР Диско и Совет [7,8] для перевода в 32-разрядный режим различных программ общим объемом около 20000 строк.

 

8. Управление размером массива

 

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

                int a [10];

                for (int i = 0; i <= 10; i++) a [i] = 0;

Указанный цикл обнуляет элементы a[0]...a[9] и заодно несуществующий элемент a[10]. В зависимости от фактического объема распределенной памяти, это может привести к наложению данных или к нарушению защиты памяти. Применение неограниченных динамических массивов гарантирует отсутствие указанных неприятных эффектов, т.к. в этом случае объем распределенной памяти всегда соответствует объему использованной памяти.

 

Таким образом, неограниченные динамические массивы обладают свойством “компенсации ошибок”; между тем, многие программисты более склонны к тому, чтобы выявлять ошибки, а не прятать их. Для этой в полной версии шаблона реализовано ручное управление размером массива – при создании массива или динамически с помощью метода resize. В ручном режиме автоматическое увеличение размера заблокировано, а при выходе за границу массива срабатывает контроль индекса.

 

В качестве примера, заменим в нашем ошибочном коде обычный массив на динамический массив с управляемым размером:

                exvector<int> a(10);

                for (i = 0; i++; i <=10) a [i] = 0;

Здесь при присваивании a[10] = 0 сработает контроль индекса.

 

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

 

9.  Ограниченные указатели

 

Контроль индексов можно организовать и в тех случаях, когда распределение памяти выполняется  штатными средствами языка C++. Для этого в полной версии Exarray.h определен шаблон ограниченных указателей.  Ограниченный указатель содержит в себе ссылку на область памяти, занятую массивом и информацию о границах массива. При попытке обращения за установленными границами массива срабатывает контроль индексов. В остальном ограниченный указатель подобен обычному указателю.

 

При создании ограниченного указателя ему можно сопоставить обычный массив конструктором:

                exptr<тип> имя (массив, размер);

 

В качестве примера приведем код обнуления массива, аналогичный коду в разделе 8:

                int a[10];

                exptr<int> p (a, sizeof (a)/sizeof(*a));

                for (int i = 0; i <= 10; i++) p [i] = 0;

При присваивании a[10] = 0 сработает контроль индекса.

 

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

 

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

 

10. Отладочные макросы

 

Ограниченные указатели не могут применяться в языке С из-за отсутствия в последнем поддержки шаблонов. Но и для этого усеченного языка можно реализовать контроль индексов. Идея заключается в применении отладочных макросов, зависящих от режима трансляции. В отладочном режиме вместо макросов подставляется ограниченные указатели, а в рабочем режиме (при включенном макро NDEBUG) – штатные указатели языка С. В отладочном режиме следует применять транслятор С++, а рабочем - С. При трансляции в рабочем режиме отладочные указатели отключатся на уровне исходного кода и полностью заменяются штатными указателями языка С  - это позволяет транслятору генерировать эффективный исполняемый код.

 

Отладочные макросы реализованы в файле Exdebug.h:

                   EXARR(T,m,n)                    - Определение массива m из n элементов типа T.

                    EXPTR(T)                            - Неинициализированный указатель на массив элементов типа T.

                   EXPTRTO(T,m,n)                         - Указатель на обычный массив m из n элементов типа T.

                    EXPTRNEW(T,n)                   - Динамическое распределение памяти под n элементов типа T.

                    EXPTRDELETE(p)                  - Освобождение блока динамической памяти, присвоенного указателю р.

 

В качестве примера приведем код обнуления массива, аналогичный коду в разделе 9:

                EXARR(int, a, 10);

                for (int i = 0; i <= 10; i++) a [i] = 0;

При присваивании a[10] = 0 в режиме отладки сработает контроль индекса.

 

Отладочные макросы применялись для разработки ряда программ на языке C, которые по техническим условиям не могли быть переведены на С++, а также при разработке класса cBigNumber, реализующего арифметику целых знаковых чисел неограниченной разрядности (http://www.imach.uran.ru/cbignum). В классе cBigNumber отладочные макросы применялись для организации интерфейса с подпрограммами нижнего уровня, написанными на языке С с ассемблерными вставками.

 

Применение отладочных макросов показало высокую эффективность этой методики. В частности, в реализации класса cBigNumber было выявлено несколько десятков ошибок распределения памяти, из которых более 10 относились к категории “компенсированных”, т.е. они никак не проявляли себя при тестировании класса в рабочем режиме.

 

Выводы

 

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

 

Программное обеспечение динамических массивов размещено на странице http://www.imach.uran.ru/exarray.

 

Список литературы

 

1.        ISO/IEC 14822:1998(E) Programming languages – C++.

2.        Патрик Нотон. Java. Справочное руководство. M.: Восточная книжная компания, 1996. 448с

3.        Гуннерсон Э. Введение в С#. Библиотека программиста, Питер. 2001 г., 304 стр.

4.        Р.Н.Шакиров. Оценка эффективности динамических массивов с автоматической проверкой индекса // Новые информационные технологии в исследовании сложных структур: Докл. III Всеросс. конф. с межд. участием. Томск, 10-12 сентября 2002. С.383-388.

5.        Роберт Лоренс Бейбер. Программное обеспечение без ошибок. M.: Радио и связь, 1996. 176с.

6.        Tom Cargill. C++ Gadfly. C++ Report Reprints: Jan 1994

7.        Захарова Г.Б., Кононенко И.А., Титов В.Г., Чистов В.П. Система автоматизации структурно-логического этапа проектирования // Proceedings of Third International Conference   "Computer-Aided Design of Discrete Devices CAD DD'99. Minsk, Nov. 10-12, 1999, с. 108-115.

8.        Чистов В.П., Захарова Г.Б., Кононенко И.А., Титов В.Г. Компьютерный тренажер для операторов технологических процессов доменного производства на основе моделей нечеткой логики // Программные продукты и системы. 2002 г., с. 42-45.