Використання вільної пам'яті

5. Великі масиви у вільній пам'ятіПодання послідовностей даних списками є досить гнучким. Особливо зручним воно є у випадках, коли дані додаються та вилучаються в процесі виконання програми. Але воно призводить до неефективного використання пам'яті, особливо коли дані, записані в елементах списку, невеликі за розміром. Справді, кожний елемент послідовності потребує додатково 4 байти під вказівник, або навіть 8, коли список двозв'язаний. Крім того, доступність елемента залежить від його розташування в списку. Відсутність прямого доступу до елементів створює незручності програмування і в багатьох випадках веде до того, що при виконанні програми пошук елемента стає занадто довгим.

Існує багато задач, в яких вимагається швидкий пошук значень і не потрібна гнучкість спискового подання. Прикладами є задачі наступних розділів. Там, як правило, не треба додавати чи вилучати довільні елементи з послідовності. Використання масивів там набагато зручніше.

Система Турбо Паскаль має обмеження на розміри як статичної, так і автоматичної пам'яті, що надається програмі. Тому у випадках, коли потрібні масиви розміром, наприклад, у сотні тисяч байтів, слід зберігати їх у вільній пам'яті, адже її обсяг залежить головним чином від обсягу наявної оперативної пам'яті комп'ютера.

Розглянемо засоби системи Турбо Паскаль, за допомогою яких зручно задавати обробку масивів у вільній пам'яті.

По-перше, корисними є функції MEMAVAIL і MAXAVAIL, з яких повертається загальний розмір незайнятої частини купи та найбільший розмір суцільної незайнятої ділянки (у байтах, типу Longint).

Масив у купі повинен ідентифікуватися вказівником, установленим на його перший елемент. В означенні типу масиву головне – задати індекс і тип його першого елемента. Наприклад, type Arl=array[0..0]of longint. Далі означимо тип вказівника на такий масив: Parl=^Arl. Вказівник, який встановлюється на масив у купі, означається як безтиповий– він може мати значеннями адреси даних будь-яких типів і розмірів. Для цього в Турбо Паскаль є тип з іменем Pointer.

"Захоплення" ділянки вільної пам'яті заданого розміру та встановлення безтипового вказівника на її перший байт задається процедурою GETMEM. Першим аргументом у її виклику є ім'я вказівника, другим – вираз типу Longint, що задає довжину ділянки в байтах. Наприклад, якщо

var p : Pointer; num : word = 16383;

то за виконання виклику

getmem(p, num*sizeof(Longint))

вказівник p встановлюється на ділянку вільної пам'яті розміром у

num*sizeof(Longint) = 16383*4 = 65532

байти. Звільнення ділянки задається аналогічним викликом процедури FREEMEM: freemem(p, num*sizeof(Longint)). У програмі слід звільняти ділянки такого самого розміру, що одержувалися, інакше наслідки можуть стати непередбачуваними.

Погляд на ділянку пам'яті як на послідовність елементів типу T реалізується за допомогою безтипового вказівника, перетвореного до типу ^T. Перетворений вказівник позначається виразом вигляду

^T(ім'я-вказівника).

Наприклад, якщо p – безтиповий вказівник, то вираз Parl(p) позначає вказівник, перетворений до типу Parl=^Arl. Тоді вираз Parl(p)^ задає адресу першого байта ділянки, на яку встановлено p. І, нарешті, вираз Parl(p)^[k], 0 k 16383, позначає елемент масиву з індексом k. Тобто замість імені масиву вживається вираз вигляду ^T(ім'я-вказівника).

Перешкодою є те, що розмір ділянки пам'яті не може бути більше ніж 65532 байти, тобто максимальна кількість елементів масиву типу T – 65532/sizeof(T). Але подолати це обмеження дуже просто за допомогою масиву безтипових вказівників. Наприклад, якщо нам потрібний масив у сто тисяч елементів типу Longint, означимо масив із 10 вказівників та кількість елементів 10000 у одній ділянці вільної пам'яті: