/* exarray.h
Динамические массивы и указатели с
автоматической проверкой индекса
(сокращенный вариант).
http://www.imach.uran.ru/exarray
(C) Р.Н.Шакиров, ИМаш УрО PAH, 1998 - 2000
All Rights Reserved.
*/
// Шаблон динамического массива.
template <class T> class expoint;
template <class T> class exarray
{
T* e; // Базовый массив.
unsigned len; // Число элементов.
// Указатель статического элемента типа T
// с фиксированными значениями, заданными
// конструктором по умолчанию.
static T* stub ();
// Распределение памяти.
void realloc (unsigned size);
// Автоматическое увеличение размера
// при обращении по индексу i.
void grow (unsigned i);
// Конструктор копирования и операция
// присваивания объявлены приватными,
// поэтому при присваивании динамического
// массива или передаче его в функцию по
// значению выдается сообщение об ошибке.
// Динамические массивы можно передавать в
// функцию по ссылке, через динамический
// указатель, а также через const T*.
exarray (const exarray<T>&);
exarray<T>& operator = (const exarray<T>&);
public:
// Конструктор динамического массива.
// Распределение памяти будет проводиться
// в процессе заполнения массива, поэтому
// начальное значение len равно 0.
// Значение e задается методом stub() и
// трактуется, как "сигнатура" пустого
// динамического массива.
exarray () { e = stub(); len = 0; }
// Деструктор.
~exarray() { realloc (0); }
// Доступ к массиву с проверкой индекса.
// При выходе индекса за границы массива
// размер массива автоматически увеличивается,
// за исключением следующих особых ситуаций:
// 1) Переполнение разрядной сетки индекса -
// вызывается функция abort().
// 2) Нехватка памяти - вызывается функция,
// установленная по set_new_handler из
// new.h, а если ее нет - то abort().
// Отрицательный индекс интерпретируется,
// как большое положительное число, что
// для всех базовых типов T, кроме char,
// приводит к вызову abort().
// При увеличении размера проводится обнуление
// памяти, после чего для всех новых элементов
// выполняются конструкторы по умолчанию.
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 (unsigned i) { return (e [i]); }
T* base () { return (e); }
// Автоматическое преобразование в const T*
// применяется при передаче базового массива
// в функцию через параметр const T*, а также
// при логической проверке, сравнении и вычи-
// тании динамических массивов и указателей.
// Если массив пустой, то выдается указатель,
// на статический элемент, сформированный
// методом stub() - это позволяет передавать
// пустой массив exarray<char> в качестве
// параметра __src функций strcpy и strcat.
// Операции логической проверки, сравнения и
// вычитания выполняются для базового массива
// по штатным правилам языка C.
// В частности, логическая проверка любого
// динамического массива, в том числе и
// пустого, всегда выдает истину.
operator const T* () { return (base()); }
// Арифметические операции.
expoint<T> operator + (unsigned i)
{ return (expoint<T> (*this, i)); }
expoint<T> operator + (int i)
{ return (expoint<T> (*this, i)); }
expoint<T> operator - (unsigned i)
{ return (expoint<T> (*this, 0-i)); }
expoint<T> operator - (int i)
{ return (expoint<T> (*this, 0-i)); }
};
// Функция exmrealloc выделяет, удлиняет,
// укорачивает и освобождает блоки памяти,
// заполненные нулями, а также обрабатывает
// ошибки. См. exarray.cpp.
void exmrealloc (void **p, unsigned size,
unsigned oldsize);
// Функция excalcsize вычисляет размер блока
// памяти в байтах, который должен быть не
// меньше требуемого. См. exarray.cpp.
unsigned excalcsize (unsigned size);
// Функция exmuladd вычисляет значение
// n * s + k, которое должно укладываться
// в разрядную сетку int.
// При переполнении выдается ~0u.
inline unsigned exmuladd
(unsigned s, unsigned n, unsigned k)
{
return ((n <= ((~0u>>1)-k)/s)? (n*s+k): ~0u);
}
// Фиктивный класс для вызова конструкторов
// и деструкторов без распределения памяти.
template <class T> struct __EXRELOC
{
T value;
void* operator new (size_t, void* p)
{ return p; }
void operator delete (void*) { ; }
};
// Приватный метод stub выдает указатель
// статического элемента с фиксированным
// значением, заданным конструктором T.
template <class T> T* exarray<T>::stub()
{
static T _stub;
return (&_stub);
}
// Приватный метод realloc устанавливает
// размер динамического массива в байтах.
// При увеличении размера выполняется
// обнуление и вызываются конструкторы
// элементов, а при уменьшении размера
// вызываются деструкторы элементов.
template <class T> void exarray<T>::realloc
(unsigned size)
{
unsigned n = size/sizeof (T); // Новая длина.
if (len == 0)
{
// Если динамический массив пустой, то
// проверяем корректность значения e.
// Это позволяет, в частности, запретить
// обращение по "нулевому" динамическому
// указателю. Присваивание size = ~0u
// обеспечивает вызов функции abort().
if (e != stub()) size = ~0u;
// Если динамический массив пустой, то перед
// распределением памяти e следует обнулить.
e = 0;
}
// Вызов деструкторов при укорочении массива.
while (len > n)
{ len--; delete (__EXRELOC<T> *) (e + len); }
// Распределение памяти.
exmrealloc ((void **)&e, size, sizeof(T) * len);
// Вызов конструкторов при удлинении массива.
while (len < n)
{ new (e + len)__EXRELOC<T>; len++; }
// Для пустого динамического массива значение
// e задается методом stub().
if (len == 0) e = stub();
}
// Приватный метод grow распределяет память
// для элементов с индексами от 0 до >= i,
// выполняя дополнительное резервирование.
template <class T> void exarray<T>::grow (unsigned i)
{
realloc (excalcsize (
exmuladd (sizeof(T), i, sizeof(T))
));
}
// Заглушка динамического массива,
// Используется при присваивании динамическим
// указателям значения 0. В отличие от
// обычного динамического массива, логическая
// проверка заглушки выдает 0.
// Заглушка определена в exarray.cpp.
extern class { void* e; unsigned len; } __EXNULL;
// Шаблон динамического указателя.
// Динамический указатель содержит смещение
// относительно начала динамического массива,
// которое может выходить за границу массива,
// а также может быть отрицательным.
// Отрицательное смещение эквивалентно
// большому положительному смещению с
// тем же двоичным кодом.
template <class T> class expoint
{
exarray<T>* a; // Динамический массив.
int k; // Смещение в массиве.
public:
// Конструктор динамического указателя.
// с начальным значением 0.
// Если указателю не присвоен динамический
// массив, то его логическая выдает ложь,
// а при попытке обращения по указателю
// вызывается функция abort().
expoint () {a=(exarray<T>*)&__EXNULL; k=0;}
// Конструктор для присваивания числового
// значения динамическому указателю.
// В отличие от обычного указателя,
// динамическому указателю можно без
// явного преобразования типа присвоить
// ненулевое числовое значение.
// Независимо от числового значения,
// логическая проверка указателя выдает ложь,
// а при попытке обращения по указателю
// вызывается функция abort().
expoint (int i) {a=(exarray<T>*)&__EXNULL; k=i;}
// Конструкторы для присваивания динамического
// массива динамическому указателю.
// После присваивания логическая проверка
// указателя выдает истину и становится
// возможным обращение к элементам массива
// с автоматическим увеличением его размера.
expoint (exarray<T>&m) { a = &m; k = 0; }
expoint (exarray<T>&m, int i) { a = &m; k = i; }
// Доступ к массиву с проверкой индекса.
T& operator [] (unsigned i) { return (*a)[k+i];}
T& operator [] (int i) { return (*a)[k+i];}
T& operator * () { return (*a)[k]; }
// Доступ к массиву без проверки индекса.
T& item (int i) { return (a->item(k + i)); }
T* base () { return (a->base() + k); }
// Автоматическое преобразование в const T*
// применяется при передаче базового массива
// в функцию через параметр const T*, а также
// при логической проверке, сравнении и вычи-
// тании динамических массивов и указателей.
// НЕ гарантируется, что указатель будет
// установлен на размещенный элемент.
operator const T* () { return (a->base()); }
// Арифметические операции.
expoint<T> operator + (unsigned i)
{ return (expoint<T>(*a, k + i)); }
expoint<T> operator + (int i)
{ return (expoint<T>(*a, k + i)); }
expoint<T> operator - (unsigned i)
{ return (expoint<T>(*a, k - i)); }
expoint<T> operator - (int i)
{ return (expoint<T>(*a, k - i)); }
expoint<T>& operator += (unsigned i)
{ k += i; return (*this); }
expoint<T>& operator += (int i)
{ k += i; return (*this); }
expoint<T>& operator -= (unsigned i)
{ k -= i; return (*this); }
expoint<T>& operator -= (int i)
{ k -= i; return (*this); }
expoint<T>& operator ++ ()
{ k++; return (*this); }
expoint<T>& operator -- ()
{ k--; return (*this); }
expoint<T> operator ++ (int)
{ expoint<T>t = *this; k++; return t; }
expoint<T> operator -- (int)
{ expoint<T>t = *this; k--; return t; }
};
// Примеры переопределения функций string.h.
#include<string.h>
// Обходим ошибку в Borland C++
#ifdef __BORLANDC__
#pragma warn -ill
#pragma intrinsic -strcpy
#pragma intrinsic -strcat
#pragma warn .ill
#endif
inline expoint<char>
strcpy (expoint<char>__dest, const char *__src)
{
__dest [strlen (__src)]; // Увеличиваем размер.
strcpy (__dest.base(), __src);
return (__dest);
}
inline expoint<char>
strcat (expoint<char>__dest, const char *__src)
{
strcpy (__dest + strlen (__dest), __src);
return (__dest);
}