УКАЗАТЕЛИ И ДИНАМИЧЕСКАЯ ПАМЯТЬ

  6.2 Адреса и указатели 
  6.3 Объявления указателей
  6.4 Выделения и освобождение динамической памяти
  6.5 Использование указателей 
  6.6 Процедуры и функции для работы с динамической памятью
  6.7 Администратор кучи
  6.8 Связанные ссылки
  Тест на закрепление темы
оглавление


6.1. ДИНАМИЧЕСКАЯ ПАМЯТЬ

 


   Все переменные, объявленные в программе, размещаются в одной непрерывной области оперативной памяти, которая называется сегментом данных. Длина сегмента данных определяется архитектурой микропроцессора 8086 и составляет 65536 байт, что может вызвать известные затруднения при обработке больших массивов данных. С другой стороны объем памяти ПК (обычно не менее 640 Кбайт) достаточен для успешного решения задач с большой размерностью данных. Выходом из положения) может служить использование так называемой динамической памяти.
   Динамическая память - это оперативная память ПК, предоставляемая программе при ее работе, за вычетом сегмента данных (64 Кбайт), стека (обычно 16 Кбайт) и собственно тела программы. Размер динамической памяти можно варьировать в широких пределах (см. прил.1). По умолчанию этот размер определяется всей доступной памятью ПК и, как правило, составляет не менее 200...300 Кбайт. 
   Динамическая память - это фактически единственная возможность обработки массивов данных большой размерности. Многие практические задачи трудно или невозможно решить без использования динамической памяти. Такая необходимость возникает, например, при разработке систем автоматизированного проектирования (САПР): размерность математических моделей, используемых в САПР, может значительно отличаться в разных проектах; статическое (т.е. на этапе разработки САПР) распределение памяти в этом случае, как правило, невозможно. Наконец, динамическая память широко используется для временного запоминания данных при работе с графическими и звуковыми средствами ПК.
   Динамическое размещение данных означает использование динамической памяти непосредственно при работе программы. В отличие от этого статическое размещение осуществляется компилятором Турбо Паскаля в процессе компиляции программы. При динамическом размещении заранее не известны ни тип, ни количество размещаемых данных, к ним нельзя обращаться по именам, как к статическим переменным.

            

                       Вверх

6.2. АДРЕСА И УКАЗАТЕЛИ


   Оперативная память ПК представляет собой совокупность элементарных ячеек для хранения информации - байтов, каждый из которых имеет собственный номер. Эти номера называются адресами, они позволяют обращаться к любому байту памяти.
Турбо Паскаль предоставляет в распоряжение программиста гибкое средство управления динамической памятью - так называемые указатели.;
   Указатель - это переменная, которая в качестве своего значения содержит адрес байта памяти.
   В ПК адреса задаются совокупностью двух шестнадцатиразрядных слов, которые называются сегментом и смещением. Сегмент - это участок памяти, имеющий длину 65536 байт (64 Кбайт) и начинающийся с физического адреса, кратного 16 (т.е. 0,16,32,48 и т.д.). Смещение указывает, сколько байт от начала сегмента необходимо пропустить, чтобы обратиться к нужному адресу.
   Адресное пространство ПК составляет 1 Мбайт (речь идет о так называемой основной памяти ПК; на компьютерах класса IBM PC/AT адресное пространство составляет 16 Мбайт; такие ПК могут иметь до 15 Мбайт дополнительной памяти, однако в Турбо Паскале нет средств, поддерживающих работу с дополнительной памятью). Для адресации в пределах 1 Мбайта нужно 20 двоичных разрядов, которые получаются из двух шестнадцатиразрядных слов (сегмента и смещения) следующим образом (рис.7): содержимое сегмента смещается влево на 4 разряда, освободившиеся правые разряды заполняются нулями, результат складывается с содержимым смещения.

            
 
Рис.7. Схема формирования адреса в ПК


   Фрагмент памяти в 16 байт называется параграфом, поэтому можно сказать, что сегмент адресует память с точностью до параграфа, а смещение - с точностью до байта. Каждому сегменту соответствует непрерывная и отдельно адресуемая область памяти. Сегменты могут следовать в памяти один за другим без промежутков или с некоторым интервалом, или, наконец, перекрывать друг друга.
   Таким образом, по своей внутренней структуре любой указатель представляет собой совокупность двух слов (данных типа WORD), трактуемых как сегмент и смещение. С помощью указателей можно размещать в динамической памяти любой из известных в Турбо Паскале типов данных. Лишь некоторые из них (BYTE, CHAR, SHORTINT, BOOLEAN) занимают во внутреннем представлении один байт, остальные - несколько смежных. Поэтому на самом деле указатель адресует лишь первый байт данных.

                              Вверх

6.3. ОБЪЯВЛЕНИЕ УКАЗАТЕЛЕЙ


   Как правило, в Турбо Паскале указатель связывается с некоторым типом данных. Такие указатели будем называть типизированными. Для объявления типизированного указателя используется значок ^, который помещается перед соответствующим типом, например:

 

var

 p1 :^ integer;

p2: ^ real;

  type

    PerconPointer = ^ PerconPointer

   PerconRecord = record

        Name : string;

       Job : string;

      Next : PerconPointer

        end; 
 
   Обратите внимание: при объявлении типа PERCONPOINTER мы сослались на тип PERCONRECORD, который предварительно в программе объявлен не был. Как уже отмечалось, в Турбо Паскале последовательно проводится в жизнь принцип, в соответствии с которым перед использованием какого-либо идентификатора он должен быть описан. Исключение сделано только для указателей, которые могут ссылаться на еще не объявленный тип данных. Это исключение сделано не случайно. Динамическая память дает возможность реализовать широко используемую в некоторых программах организацию данных в виде списков. Каждый элемент списка имеет в своем составе указатель на соседний элемент (рис. 8), что обеспечивает возможность просмотра и коррекции списка. Если бы в Турбо Паскале не было этого исключения, реализация списков была бы значительно затруднена.


 
Рис. 8. Пример списочной структуры данных. 
   В Турбо Паскале можно объявлять указатель и не связывать его при этом с каким-либо конкретным типом данных. Для этого служит стандартный тип POINTER, например:
var 
  рр : pointer:
   Указатели такого рода будем называть нетипизированными. Поскольку нетипизированные указатели не связаны с конкретным типом, с их помощью удобно динамически размещать данные, структура и тип которых меняются в ходе работы программы.
   Как уже говорилось, значениями указателей являются адреса переменных в памяти, поэтому следовало бы ожидать, что значение одного указателя можно передавать другому. На самом деле это не совсем так. В Турбо Паскале можно передавать значения только между указателями, связанными с одним и тем же типом данных. Если, например,
var 
  p1, p2 : ^Integer;
  рЗ : ^real;
  рр : pointer;
то присваивание
  р1 := Р2; вполне допустимо, в то время как
  р1 := РЗ;
запрещено, поскольку Р1 и РЗ указывают на разные типы данных. Это ограничение, однако, не распространяется на нетипизированные указатели, поэтому мы могли бы записать
  рр := рЗ;
  р1 := РР: и тем самым достичь нужного результата.
   Читатель вправе задать вопрос, стоило ли вводить ограничения и тут же давать средства для их обхода. Все дело в том, что любое ограничение, с одной стороны, вводится для повышения надежности программ, а с другой - уменьшает мощность языка, делает его менее пригодным для каких-то применений. В Турбо Паскале немногочисленные исключения в отношении типов данных придают языку необходимую гибкость, но их использование требует от программиста дополнительных усилий и таким образом свидетельствует о вполне осознанном действии.

                             Вверх

6.4. ВЫДЕЛЕНИЕ И ОСВОБОЖДЕНИЕ ДИНАМИЧЕСКОЙ ПАМЯТИ


   Вся динамическая память в Турбо Паскале рассматривается как сплошной массив байтов, который называется кучей. Физически куча располагается в старших адресах сразу за областью памяти, которую занимает тело программы.
   Начало кучи хранится в стандартной переменной HEAPORG (рис. 9), конец - в переменной HEAPEND. Текущую границу незанятой динамической памяти указывает указатель HEAPPTR.
0                 ———> Старший адрес ———>                                                   640К
| Системная область | Программа |         куча        | Системная область |
HeapOrg ————————1                    1          1
HeapPtr ——————————————1          1
HeapEND ————————————————1
Рис. 9. Расположение кучи в памяти ПК
   Память под любую динамически размещаемую переменную выделяется процедурой NEW. Параметром обращения к этой процедуре является типизированный указатель. В результате обращения указатель приобретает значение, соответствующее динамическому адресу, начиная с которого можно разместить данные, например:
var
  i, J : ^Integer; 
  r : ^real;
begin
  new(l);
   После выполнения этого фрагмента указатель I приобретет значение, которое перед этим имел указатель кучи HEAPPTR, а сам HEAPPTR увеличит свое значение на 2, так как длина внутреннего представления типа INTEGER, с которым связан указатель I, составляет 2 байта (на самом деле это не совсем так: память под любую переменную выделяется порциями, кратными 8 байтам - см. п.6.7). Оператор

new(r):
вызовет еще раз смещение указателя HEAPPTR, но теперь уже на 6 байт, потому что такова длина внутреннего представления типа REAL. Аналогичным образом выделяется память и для переменной любого другого типа.
   После того, как указатель приобрел некоторое значение, т.е. стал указывать на конкретный физический байт памяти, по этому адресу можно разместить любое значение соответствующего типа. Для этого сразу за указателем без каких-либо пробелов ставится значок ^, например:
I^ := 2; (в область памяти i помещено значение 2} 
R^ := 2*р1; {в область памяти r помешено значение 6.28}
   Таким образом, значение, на которое указывает указатель, т.е. собственно данные, размещенные в куче, обозначаются значком ^, который ставится сразу за указателем. Если за указателем нет значка ^, то имеется в виду адрес, по которому размещены данные. Имеет смысл еще раз задуматься над только что сказанным: значением любого указателя является адрес, а чтобы указать, что речь идет не об адресе, а о тех данных, которые размещены по этому адресу, за указателем ставится ^ . Если Вы четко уясните себе это, у Вас не будет проблем при работе с динамической памятью.
   Динамически размещенные данные можно использовать в любом месте программы, где это допустимо для констант и переменных соответствующего типа, например:
r^:= sqr(r^) + i^ - 17; 
Разумеется, совершенно недопустим оператор
r := sqr(r^) + i^ - 17;
так как указателю R нельзя присвоить значение вещественного выражения. Точно так же недопустим оператор
r^ := sqr(r);
поскольку значением указателя R является адрес, и его (в отличие от того значения, которое размещено по этому адресу) нельзя возводить в квадрат. Ошибочным будет и такое присваивание:
г^ := I;
так как вещественным данным, на которые указывает R^ , нельзя присвоить значение указателя (адрес).
   Динамическую память можно не только забирать из кучи, но и возвращать обратно. Для этого используется процедура DISPOSE. Например, операторы
dispose(r);
dIspose(i); 
вернут в кучу 8 байт, которые ранее были выделены указателям I и R (см. выше).
   Отметим, что процедура DISPOSE(PTR) не изменяет значения указателя PTR, а лишь возвращает в кучу память, ранее связанную с этим указателем. Однако повторное применение процедуры к свободному указателю приведет к возникновению ошибки периода исполнения. Освободившийся указатель программист может пометить зарезервированным словом NIL.
   К указателям можно применять операции отношения, в том числе и сравнение с NIL, например:
const
  p : ^real = NIL;
………………
  if p = NIL then new(p);
………………
  dispose(p); 
  p := NIL;
   Этот фрагмент иллюстрирует предпочтительный способ объявления указателя в виде типизированной константы с одновременным присвоением ему значения NIL (см. гл. 7). Следует учесть, что начальное значение указателя (при его объявлении в разделе переменных) может быть произвольным. Использование указателей, которым не присвоено значение процедурой NEW или другим способом, не контролируется системой и может привести к непредсказуемым результатам.
   Чередование обращений к процедурам NEW и DISPOSE обычно приводит к «ячеистой» структуре памяти. Дело в том, что все операции с кучей выполняются под управлением особой программы, которая называется администратором кучи. Она ведет у чет всех свободных фрагментов в куче. При очередном обращении к процедуре NEW эти программа отыскивает наименьший свободный фрагмент, в котором еще может разместиться требуемая переменная. Адрес начала найденного фрагмента возвращается в указателе, а сам фрагмент или его часть нужной длины помечается как занятая часть кучи. (Подробнее о работе администратора кучи см. п.6.7).
   Другая возможность состоит в освобождении целого фрагмента кучи. С этой целью перед началом выделения динамической памяти текущее значение указателя HEAPPTR запоминается в переменной-указателе с помощью процедуры MARK. Теперь можно в любой момент освободить фрагмент кучи, начиная от того адреса, который запомнила процедура MARK, и до конца динамической памяти. Для этого используется процедура RELEASE. Например:

     var

               p,p1,p2,p3,p4,p5:^ integer;

              begin

                            new(p1);

                  new(p2);

                            new(p3);

                  new(p4);

                            new(p5);

                    release(p);


   В этом примере процедурой MARK(P) в указатель, P было помещено текущее значение HEAPPTR, однако память под переменную не резервировалась. Обращение RELEASE(P) освободило динамическую память от помеченного места до конца кучи. Рис. 10 иллюстрирует механизм работы процедур NEW-DISPOSE и NEW-MARK-RELEASE для рассмотренной примера и для случая, когда вместо оператора RELEASE(P) используется, например, DISPOSE(P3).

                 
a                             b                                        c


Рис. 10. Состояние динамической памяти:
а - перед освобождением; Ь - после DISPOSE (РЗ);
с - после RELEASE (Р)
   Следует учесть, что вызов RELEASE уничтожает список свободных фрагментов в куче, созданных до этого процедурой DISPOSE, поэтому совместное использование обоих механизмов освобождения памяти в рамках одной программы не рекомендуется. 
Как уже отмечалось, параметром процедуры NEW может быть только типизированный указатель. Для работы с нетипизированными указателями используются процедуры:
GETMEM (Р, SIZE) - резервирование памяти;
FREEMEM(P, SIZE) - освобождение памяти.
Здесь Р - нетипизированный указатель;
SIZE - размер в байтах требуемой или освобождаемой части кучи, 
За одно обращение к куче процедурой GETMEM можно зарезервировать до 65521 байта динамической памяти.
   Использование процедур GETMEM-FREEMEM, как и вообще вся работа с динамической памятью, требует особой осторожности и тщательного соблюдения простого правила: освобождать нужно ровно столько памяти, сколько ее было зарезервировано, и именно с того адреса, с которого она была зарезервирована.
   Нетрудно обнаружить, что наличие нетипизированных указателей в Турбо Паскале (в стандартном Паскале их нет) открывает широки возможности неявного преобразования типов. К сожалению, трудно обнаруживаемые ошибки в программе, связанные с некорректно используемыми обращениями к процедурам NEW и DISPOSE, также могут привести к нежелательному преобразованию типов. В самом деле, пусть имеется программа:
               var

i,j: ^ integer;

r: real;

      Begin

        new(i); {i:= HeapOrg; HeapPtr:= HeapOrg+2}

     j:= i;            {j:= HeapOrg}

    j^:= 2; 

 dispose(i);

new(r);       {r:= HeapOrg; HeapPtr:= HeapOrg+6}

 r^:= pi;

writeln(j^)                     {??}

end.
 
   Что будет выведено на экран дисплея? Чтобы ответить на этот вопрос, проследим за значениями указателя HEAPPTR. Перед исполнением программы этот указатель имел значение адреса начала кучи HEAPORG, которое и было передано указателю i, а затем и j. После выполнения DISPOSE(I) указатель кучи вновь приобрел значение HEAPORG, этот адрес передан указателю R в процедуре NEW(R). После того, как по адресу R разместилось вещественное число РI-3.14159, первые 2 байта кучи оказались заняты под часть внутреннего представления этого числа. 5 то же время J все еще сохраняет адрес HEAPORG, поэтому оператор WRITELN(J^) будет рассматривать 2 байта числа PI как внутреннее представление целого числа (ведь J - это указатель на тип INTEGER) и выведет 8578.

                                 Вверх

6.5. ИСПОЛЬЗОВАНИЕ УКАЗАТЕЛЕЙ


   Подведем некоторые итоги. Итак, динамическая память составляет 200... 300 Кбайт или больше, ее начало хранится в переменной HEAPORG, а конец соответствует адресу переменной HEAPEND. Текущий адрес свободного участка динамической памяти хранится в указателе HEAPPTR.
   Посмотрим, как можно использовать динамическую память для размещения крупных массивов данных. Пусть, например, требуется обеспечить доступ к элементам прямоугольной матрицы 100x200 типа EXTENDED. Для размещения такого массива требуется память 200000 байт (100*200*10).
   Казалось бы, эту проблему можно решить следующим образом:
var
  I,J : integer;
  PtrArr : array [1..100, 1..200] of ^rеаl;
  for i := 1 to 100 do for j := 1 to 200 do
  new(PtrArr[l.J]); 
Теперь к любому элементу вновь созданного динамического массива можно обратиться по адресу, например:
  PtrАrr[1,1]^ := 0; 
  if PtrArr[i , j*2]^ > 1 then ......
   Вспомним, однако, что длина внутреннего представления указателя составляет 4 байта, поэтому для размещения массива PTRARR потребуется 100*200*4 - 80000 байт, что превышает размер сегмента данных (65536 байт), доступный, как уже отмечалось, программе для статического размещения данных.
   Выходом из положения могла бы послужить адресная арифметика т.е. арифметика над указателями, потому что в этом случае можно был бы отказаться от создания массива указателей PTRARR и вычислять адрес любого элемента прямоугольной матрицы непосредственно перед обращением к нему. Однако в Турбо Паскале над указателями не определены никакие операции, кроме операций присвоения и отношения.
   Тем не менее, решить указанную задачу все-таки можно. Как мы уже знаем, любой указатель состоит из двух слов типа WORD, в которых хранятся сегмент и смещение. В Турбо Паскале определены две встроенные функции типа WORD, позволяющие получить содержимое этих слов
SEG(X) - возвращает сегментную часть адреса;
OFS(X) - возвращает смещение.
Аргументом X при обращении к этим функциям может служил любая переменная, в том числе и та, на которую указывает указатель. Например, если имеем
var

p:^real;

................

new(p);

p^:=3.14;
то функция SEG(P) вернет сегментную часть адреса, по которому располагается 4-байтный указатель Р, в то время как SEG(P^) - сегмент 6-бай-тного участка кучи, в котором хранится число 3.14 .
С другой стороны, с помощью встроенной функции 
PTR ( SEG, OFS: WORD ): POINTER
можно создать значение указателя, совместимое с указателями любого типа. Таким образом возможна такая последовательность действий. Вначале процедурой GETMEM из кучи забираются несколько фрагментов подходящей длины (напомню, что за одно обращение к процедуре можно зарезервировать не более 65521 байт динамической памяти). Для рассматриваемого примера удобно резервировать фрагменты такой длины, чтобы в них могли, например, разместиться строки прямоугольной матрицы, т.е. 200 * 10 - 2000 байт.      Начало каждого фрагмента, т.е. фактически начало размещения в памяти каждой строки, запоминается в массиве PTRSTR, состоящем из 100 указателей. Теперь для доступа к любому элементу строки нужно вычислить смещение этого элемента от начала строки и сформировать соответствующий указатель:

                var

 i,j    : integer;

           PtrStr : array[1..100] of pointer;

  Pr    : real;

                  const

   SizeOfReal =6;

                 begin

          for i:= 1 to 100 do

             GetMem(PtrStr[i], SizeOfReal* 200);

.........................................

          {Обращение к элементу матрицы}

pr:=ptr(Seg(PtrStr[i]^),

                         ofs(PtrStr[i]^)+(j-1)* SizeOfReal);

   if pr^> 1 then ...........

 Поскольку оператор вычисления адреса PR:= PTR.. будет, судя по всему, использоваться в программе неоднократно, полезно ввести вспомогательную функцию GETR, возвращающую значение элемента матрицы, и процедуру PUTR, устанавливающую новое значение элемента (правила объявления процедур и функций изложены в гл. 8). Каждая из них, в свою очередь, обращается к функции ADDRR для вычисления адреса. В примере 13 приводится программа, создающая в памяти матрицу из №М случайных чисел и вычисляющая их среднее значение.

 П р и м е р 13.

const

  SizeOfReal = 6;                 {Длина переменной типа Real}

 N= 100;                           {Количество столбцов}

M= 200;                          {Количество строк}

    var

    i,j : integer;

   PtrStr: array[1..N] of pointer;

    s: real;

 type

   RealPoint= ^ real;

{--------------------}

 FUNKTION Add(i, j : word) : RealPoint;

 Begin

    AddrR:= ptr(seg(PtrStr[i])^),

                 ofs(PtrStr[i]^)+(j-1)* SizeOfReal)

 end {AddrR};

{-------------------------}

FUNCTION GetR(i, j : integer): real;

  Begin

  GetR := AddR(i, j)^

 end{GetR};

{----------------------}

Procedure PutR(i, j : integer; x- real);

 Begin

  AddR(i, j)^:=x

 end{PutR};

{------------------------}

Begin {Main}

   for i:= 1 to n do 

         begin 

    GetMem(PtrStr[i], M* SizeOfReal);

     for j:= 1 to M do PutR(i, j, Random)

  end;

s:=0;

 for i:= 1 to N do 

   for j:= 1 to M do

     s:= s+ GetR(i, j);

  writeln(s/(N*M): 12:10)

end{Main}.

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

                                          
                              Вверх
 

6.6. ПРОЦЕДУРЫ И ФУНКЦИИ 
ДЛЯ РАБОТЫ С ДИНАМИЧЕСКОЙ ПАМЯТЬЮ 

   Ниже приводится описание как уже рассмотренных процедур и функций, так и некоторых других, которые могут оказаться полезными при обращении к динамической памяти. 
Функция ADDR. Возвращает результат типа POINTER, в котором содержится адрес аргумента. Обращение:
ADDR(X)
   Здесь X - любой объект программы (имя любой переменной, процедуры, функции). Возвращаемый адрес совместим с указателем любого типа. Отметим, что аналогичный результат возвращает операция @ .
   Функция CSEG. Возвращает значение, хранящееся в регистре CS микропроцессора (в начале работы программы в регистре CS содержится сегмент начала кода программы). Обращение:
CSEG
Результат возвращается в слове типа WORD.
Процедура DISPOSE. Возвращает в кучу фрагмент динамической памяти, который ранее был зарезервирован за типизированным указателем. Обращение:
DISPOSE (TP )
   Здесь ТР - типизированный указатель. При повторном использовании процедуры применительно к уже освобожденному фрагменту возникает ошибка периода исполнения. При освобождении динамических объектов можно указывать вторым параметром обращения к DISPOSE имя деструктора (подробнее см. гл.: 10).
   Функция DSEG. Возвращает значение, хранящееся в регистре DS микропроцессора (в начале работы программы в регистре DS содержится сегмент начала данных программы). Обращение:
DSEG ]
Результат возвращается в слове типа WORD.
Процедура FREEMEM. Возвращает в кучу фрагмент динамической памяти, который ранее был зарезервирован за нетипизированным указателем. Обращение:
FREEMEM ( P, SIZE )
Здесь Р - нетипизированный указатель;
SIZE - длина в байтах освобождаемого фрагмента.
При повторном использовании процедуры применительно к уже освобожденному фрагменту возникает ошибка периода исполнения.
Процедура GETMEM. Резервирует за нетипизированным указателем фрагмент динамической памяти требуемого размера. Обращение: 
GETMEM ( Р, SIZE )
   За одно обращение к процедуре можно зарезервировать не более
65521 байта динамической памяти. Если нет свободной памяти требуемого размера, возникает ошибка периода исполнения. Если память не фрагментирована, последовательные обращения к процедуре будут резервировать последовательные участки памяти, так что начало следующего будет располагаться сразу за концом предыдущего. 
   Процедура MARK. Запоминает текущее значение указателя кучи EAPPTR. Обращение:
MARK(PTR)
   Здесь PTR - указатель любого типа, в котором будет возвращено текущее значение HEAPPTR. Используется совместно с процедурой RELEASE для освобождения части кучи.
Функция MAXAVAIL. Возвращает размер в байтах наибольшего непрерывного участка кучи. Обращение:
MAXAVAIL
Результат имеет тип LONGINT. За один вызов процедуры NEW или GЕТМЕМ нельзя зарезервировать памяти больше, чем значение, возвращаемое этой функцией.
Функция MEMAVAIL. Возвращает размер в байтах общего свободного пространства кучи. Обращение:
MEMAVAIL
Результат имеет тип LONGINT.
Процедура NEW. Резервирует фрагмент кучи для размещения переменной. Обращение:
NEW(TP )
Здесь ТР - типизированный указатель. За одно обращение к процедуре можно зарезервировать не более 65521 байта динамической памяти. Если нет свободной памяти требуемого размера, возникает ошибка периода исполнения. Если память не фрагментирована, последовательные обращения к процедуре будут резервировать последовательные участки памяти, так что начало следующего будет располагаться сразу за концом предыдущего.
   Процедура NEW может вызываться как функция. В этом случае параметром обращения к ней является тип переменной, размещаемой в куче, а функция NEW возвращает значение типа указатель. Например:
type
  Pint =^integer; 
var
  p: Pint;
  p :=New(Plnt):
   При размещении в динамической памяти объекта разрешается в качестве второго параметра обращения к NEW указывать имя конструктора (см. гл.10).
   Функция OFS. Возвращает значение типа WORD, содержащее смещение адреса указанного объекта. Вызов:
OFS (X)
   Здесь X - выражение любого типа или имя процедуры. 
Функция PTR. Возвращает значение типа POINTER по заданному сегменту SEG и смещению OFS. Вызов:
PTR ( SEG, OFS )
   Здесь SEC - выражение типа WORD, содержащее сегмент; OFS - выражение типа WORD, содержащее смещение. Значение, возвращаемое функцией, совместимо с указателем любого типа.
   Процедура RELEASE. Освобождает участок кучи. Обращение: 
RELEASE ( PTR )
   Здесь PTR - указатель любого типа, в котором предварительно было сохранено процедурой MARK значение указателя кучи. Освобождается участок кучи от адреса, хранящегося в PTR, до конца кучи. Одновременно уничтожается список всех свободных фрагментов, которые, возможно, были созданы процедурами DISPOSE или FREEMEM.
Функция SEG. Возвращает значение типа WORD, содержащее сегмент адреса указанного объекта. Вызов:
SEG( X)
   Здесь X - выражение любого типа или имя процедуры.
Функция SIZEOF. Возвращает длину в байтах внутреннего представления указанного объекта. Вызов:
SIZEOF( X)
   Здесь X - имя переменной, функции или типа. Например, везде в программе из примера 13 вместо константы SIZEOFREAL можно было бы использовать обращение SIZEOF(REAL).

                                        Вверх

6.7. АДМИНИСТРАТОР КУЧИ

   Как уже отмечалось, администратор кучи - это служебная программа, которая обеспечивает взаимодействие пользовательской программы с кучей. Администратор кучи обрабатывает запросы процедур NEW, GETMEM, DISPOSE, FREEMEM и др. и изменяет значения указателей HEAPPTR и FREELIST. Указатель HEAPPTR содержит адрес нижней границы свободной части кучи, а указатель FREELIST - адрес описателя первого свободного блока. В модуле SYSTEM указатель FREELIST описан как POINTER, однако фактически он указывает на следующую структуру данных:
type
  PFreeRec = ^TFreeRec; 
  TFreeRec = record 
                       Next : pointer; 
                       Size : pointer;
                     end;
   Эта списочная структура предназначена для описания всех свободных блоков памяти, которые расположены ниже границы HEAPPTR. Происхождение блоков связано со случайной последовательностью использования процедур NEW-DISPOSE или GETMEM-FREEMEM («ячеистая» структура кучи). Поле NEXT в записи TFREEREC содержит адрес описателя следующего по списку свободного блока кучи или адрес, совпадающий с HEAPEND, если этот участок последний в списке. Поле SIZE содержит ненормализованную длину свободного блока или 0, если ниже адреса, содержащегося в HEAPPTR, нет свободных блоков. Ненормализованная длина определяется так: в старшем слове этого поля содержится количество свободных параграфов, а в младшем - количество свободных байт в диапазоне 0... 15. Следующая функция преобразует значение поля SIZE в фактическую длину свободного блока: 

Function BlockSIze(SIze: pointer): Longlnt; 
( Функция преобразует ненормализованную длину свободного блока в байты }
type
  PtrRec = record Lo, HI : word
end; 
var
  LengthBlock : longlnt; 
BEGIN
  BlockSize := Longint(PtrRec(Size).HI)*16 + PtrRec(SIze).Lo
END;
   Сразу после загрузки программы указатели HEAPPTR и FREELIST содержат один и тот же адрес, который совпадает с началом кучи (это адрес содержится в указателе HEAPORG). При этом в первых 8 бай - кучи хранится запись, соответствующая типу TFREEREC (поле NE содержит адрес, совпадающий со значением HEAPEND, а поле SIZ ноль, что служит дополнительным признаком отсутствия «ячеек» в динамической памяти). При работе с кучей указателя и FREELIST будут иметь одинаковые значения до тех пор, пока в куче не образует хотя бы один свободный блок ниже границы, содержащейся в указателе HEAPPTR. Как только это произойдет, указатель FREELIST станет ссылаться на начало этого блока, а в первых 8 байтах освобожденного участка памяти будет размещена запись TFREEREC. Используя FREELIST начало списка, программа пользователя всегда сможет просмотреть в список свободных блоков и при необходимости модифицировать его.
   Описанный механизм вскрывает один весьма существенный недостаток, связанный с работой администратора кучи в версии 6.0: в любой освободившийся блок администратор должен поместить описатель этого блока, а это означает, что длина блока не может быть меньше 8 байтов Администратор кучи всегда выделяет память блоками, размер которого кратен размеру записи TFREEREC, т.е. кратен 8 байтам. Даже ее программа запросит 1 байт, администратор выделит ей фактически 8 байт. Те же 8 байт будут выделены при запросе 2, 3 ,..., 8 байт; при запрос 9 байт будет выделен блок в 16 байт и т.д. Это обстоятельство след учитывать, если Вы хотите минимизировать возможные потери динамической памяти. Если запрашиваемый размер не кратен 8 байтам, в куче образуется «дырка» размером от 1 до 7 байт, причем она не может использоваться ни при каком другом запросе динамической памяти вплоть до момента, когда связанная с ней переменная не будет удалена из кучи.
   Если при очередном обращении к функции NEW или GETM. администратор не может найти в куче нужный свободный блок, он общается к функции, адрес которой содержит переменная HEAPERR Эта функция соответствует следующему процедурному типу:
type
  HeapErrorFun = function (Size : word) : integer; 

   Здесь SIZE - размер той переменной, для которой нет свободной динамической памяти. Стандартная функция, адрес которой при запуске программы содержит переменная HEAPERROR возвращает 0, что приводит к останову программы по ошибке периода счета с кодом 203 (см.: прил. 3). Вы можете переопределить эту функцию и таким образом блокировать останов программы. Для этого необходимо написать собственную функцию и поместить ее адрес в указатель HEAPERROR. Например:

FUNCTION HeapFunc(Size : Word) : integer; far;
Begin
  HeapFunc := 1
end;
  HeapError := @HeapFunc;
   Отметим, что функция типа HEAPERRORFUN вызывается только в том случае, когда обращение с требованием выделения динамической памяти было неуспешным. Она может возвращать одно из трех значений: 
• 0 - прекратить работу программы;
• 1 - присвоить собственному указателю значение NIL и продолжить работу программы; 
• 2 - повторить выделение памяти; разумеется, в этом случае внутри ,
функции типа HEAPERRORFUN необходимо освободить память нужного размера.

              Вверх

 

6.8. Ссылки
 
  Ссылки являются простым механизмом, позволяющим строить данные со сложной и меняющейся (и даже рекурсивной) структурой. Если тип Т определяет записи с одним или несколькими полями типа Р, то с их помощью можно строить структуры, эквивалентные произвольному конечному графу, причем идентифицированные переменные будут представлять вершины, а ссылки — ребра.
Программа 10.1 иллюстрирует, как с помощью ссылок можно моделировать очередь клиентов. (Процедуры рассматриваются в следующей главе.)
program WaitingList;
const
NameLength = 15;
type
NameString = String[NameLength];
Natural = 0..MaxInt;
ClientPointer = ^Client;
Client = record
Name : NameString;
Nxt : ClientPointer;
end;

var Head, Tail : ClientPointer;
Name : NameString;
i : integer;

procedure AddClientToList;
var
NewClient : ClientPointer;
begin
New(NewClient);
if Head = nil then Head := NewClient
else Tail^.Nxt := NewClient;
NewClient^.Name := Name;
NewClient^.Nxt := nil;
Tail := NewClient;
end;

procedure ServeClients (HowMany : Natural);
var
ClientToServe : ClientPointer;
begin
while (HowMany > 0) and (Head <> nil) do
Begin
ClientToServe := Head;
Head :=Head^.Nxt;
Writeln(ClientToServe^.Name);
Dispose(ClientToServe);
HowMany := HowMany-1
end;
end;

BEGIN
Writeln;
Head := nil;
Writeln(' End of Input - Ctrl+Z');
while not eof(input) do
begin
Readln(Name);
AddClientToList;
end;
Writeln;
ServeClients(5);
END.
 Даёт в качестве результатов:
Hikita
       Balasubramanyam
Nagel
  Lecarme
Bello
Pokrovsky
Barron
Yuen
Sale
Price
Hikita
      Balasubramanyam
Nagel
В качестве другого примера рассмотрим «банк данных», включающий определенную группу лиц. Предположим, каждый человек представляется такой записью.которая. Если добавить в нее поле ссылочного типа, то из таких записей можно формировать цепочки или связные списки и использовать их для поиска и включения информации:
type Link =^ TPerson;
 Person = record
Next; Link;
end;
Связный список из п лиц можно представить так, как показано
на рис. 1,0.3.
Каждый квадрат соответствует одному человеку:
 
Переменная типа Link с именем First указывает на первого человека из этого списка. Поле же Next у «последнего человека» имеет значение nil. Заметим, что обозначение
Firstf.Nextt.Next указывает на третьего человека в списке.
Если допустить, например, что мы можем читать целые данные, относящиеся к росту человека, то с помощью приведенного ниже фрагмента программы можно построить упомянутую цепочку.
var First, P: Link; H,I: Integer;
First := nil
for I := 1 to N do
begin Read(H); New(P);
Pt.Next := First;
Pt.Height := H; InitializeOtherFields(PT);
First := P end
Обратите внимание, что список растет в обратном направлении. Для обращения к элементам мы введем еще одну переменную, скажем Pt типа Link, которая будет свободно перемещаться по списку. Чтобы показать, как происходит поиск, представим себе, что есть информация о человеке с Height, равным 175, и нам нужно получить доступ к ней. В этом случае будем двигать Pt «вдоль» Next до тех пор, пока не обнаружим желаемое.
Pt := First;
while PtT.Height.<> 175 do Pt := Ptt.Next
Словами это можно выразить следующим образом: «Сначала Pt указывает на первого человека. До тех пор пока рост (Height) человека, на которого указывает Pt, не будет равен 175, будем присваивать Pt значение ссылки, находящееся в поле Next (это опять же ссылка) записи, на которую в данный момент указывает
Pt».
Такая простая процедура поиска будет работать только в том случае, если есть уверенность, что найдется по крайней мере один человек с Height, равным 175. Но разве это реальное предположение? Поэтому для правильной работы нужно было бы еще и опознавать конец списка. Сначала это можно попытаться сделать так:
Pt:=First;
while(Pt<> nil) and (Pt^Height<> 175) do
Pt :=Pt^next
 
Вспомним, однако, о чем говорилось в разд. 4.1. Если Pt = nil, то переменная, на которую ссылаются во втором терме условия окончания, вообще не существует, это ошибка! Поэтому в данной ситуации можно выбрать любое из двух таких решений — и то и другое в этой ситуации работают правильно.

(1) Pt:= First; В := true;
wltile (Pt <> nil) and В do
if Ptt.Height = 175 then В := false else Pt := PtT.Next
(2) Pt := First;
while Pt <> nil do
begin if Ptt.Height = 175 then goto 13;
Pt := PtT.Next end; 
13:
                                 Вверх  оглавление

 

Хостинг от uCoz