Компьютерные книги
Главное меню
Главная Поиск по сайту Добавить материал О нас Карта книг Карта сайта
Реклама
computersbooks.net -> Добавить материал -> Языки программирования -> Кубенский А.А. -> "Структуры и алгоритмы обработки данных. Объектно-ориентированный подход и реализация на C++" -> 107

Структуры и алгоритмы обработки данных. Объектно-ориентированный подход и реализация на C++ - Кубенский А.А.

Кубенский А.А. Структуры и алгоритмы обработки данных. Объектно-ориентированный подход и реализация на C++ — Спб.: БВХ-Петербург , 2004. — 464 c.
ISBN 5-94157-506-8
Скачать (прямая ссылка): strukturiialgoritmiobrabotkidannih2004.djvu
Предыдущая << 1 .. 101 102 103 104 105 106 < 107 > 108 109 110 111 112 113 .. 161 >> Следующая

'-BiListMemory () { delete [] buffer; }
// Очистка памяти, void clear() {
//В буфере создается кольцевой список из единственного
// блока, размер которого равен размеру всего буфера
freePtr = (FreeBiock *)buffer;
freePtr->length = size;
freePtr->next = freePtr->pred = freePtr;
}
// Операция выделения свободного блока памяти заданного размера void * get(size_t sz);
// Операция возврата выделенного блока памяти в систему void release(void * ptr);
};
//-----------bilistmemory. срр-----------------------------------------------
// Операция выделения свободного блока памяти заданного размера void * BiListMemory::get(size_t sz) {
// 1. Поиск свободного блока подходящей длины if (freePtr == NULL) throw NoMoreMemoryException();
FreeBiock * current = freePtr,
* last = freePtr,
* found = NULL;
do {
if (current->length >= sz + sizeof(BusyBiock)) {
found = current; // свободный блок подходящей длины найден } else {
current = current->next; // переход к следующему блоку
}
} while (found — NULL && current != last);
if (found == NULL) { // нет свободного блока памяти нужного размера! throw NoMoreMemoryException();
}
// 2. Если блок не слишком велик, он выделяется целиком if (found->length < sz + sizeof(BusyBiock) + sizeof(FreeBiock)) { FreeBiock * next = found->next,
* pred = found->pred;
308
Гпава 5
if (next == found) { // Это был последний блок!
freePtr = NULL;
} else {
next->pred = pred; freePtr = pred->next = next;
}
return (char*)found + sizeof(BusyBiock);
// 3. Если блок достаточно велик, то он делится на два } else {
// вычисление новой длины блока: found->length -= sz + sizeof(BusyBiock);
// вычисление адреса возвращаемого блока:
char * retAddress = (char*)found + found->length;
// окончательное формирование выдаваемого блока и выдача результата:
((BusyBiock*)retAddress)->length = sz + sizeof(BusyBiock); return (char*)retAddress + sizeof(BusyBiock);
}
}
// Операция возврата выделенного блока памяти в систему void BiListMemory::release(void * ptr) {
// Сначала вычисляем адрес возвращаемого блока
FreeBiock *releaseBlock = (FreeBiock*)((char*)ptr - sizeof(BusyBiock)); // 1. Находим два соседних свободных блока, один из которых // расположен перед возвращаемым блоком, а другой - после.
// Если в области больших адресов нет свободных блоков, то
// полагаем secondAddr = NULL. Аналогично, если в области
// меньших адресов нет свободных блоков, то считаем firstAddr = NULL
FreeBiock * firstAddr = freePtr,
* secondAddr = freePtr; if (firstAddr != NULL) {
if (firstAddr > releaseBlock) {
while (firstAddr > releaseBlock) { firstAddr = firstAddr->pred; if (firstAddr >= freePtr) break;
}
secondAddr = firstAddr->next; if (firstAddr > releaseBlock) { firstAddr = NULL;
}
} else {
while (secondAddr < releaseBlock) { secondAddr = secondAddr->next;
Алгоритмы распределения памяти
309
if (secondAddr <= freePtr) break;
}
firstAddr = secondAddr->pred; if (secondAddr < releaseBlock) { secondAddr = NULL;
}
}
}
// 2. Рассматриваем три случая:
// 1) возвращаемый блок удается соединить с обоими соседними блоками;
// 2) возвращаемый блок удается соединить с одним из соседних блоков;
// 3) ни одно из указанных соединений невозможно,
if (firstAddr != NULL
&& (char*)firstAddr + firstAddr->length == (char*)releaseBlock) {
// Первый из блоков примыкает к возвращаемому if (secondAddr != NULL &&
(char*)releaseBlock + releaseBlock->length == (char*)secondAddr) { // Второй блок тоже примыкает к возвращаемому - случай (1).
// Второй блок удаляем из системы, а первый расширяем: firstAddr->length += releaseBlock->length + secondAddr->length; firstAddr->next = secondAddr->next; freePtr = secondAddr->next->pred = firstAddr;
} else {
// Случай (2), первый блок расширяется firstAddr->length += releaseBlock->length;
}
} else if (secondAddr != NULL &&
(char*)releaseBlock + releaseBlock->length == (char*)secondAddr) { // Только второй блок примыкает к возвращаемому - случай (2) secondAddr->length += releaseBlock->length; secondAddr->pred->next = releaseBlock;
*releaseBlock = *secondAddr;
freePtr = releaseBlock->next->pred = releaseBlock;
} else {
// Случай (3) - в системе появляется новый свободный блок, if (firstAddr != NULL) {
releaseBlock->pred = firstAddr; releaseBlock->next = firstAddr->next; firstAddr->next->pred = releaseBlock; firstAddr->next = releaseBlock;
} else if (secondAddr != NULL) { releaseBlock->next = secondAddr; releaseBlock->pred = secondAddr->pred;
310
Гпава 5
secondAddr->pred->next = releaseBlock; secondAddr->pred = releaseBlock;
} else {
freePtr = releaseBlock->pred = releaseBlock->next = releaseBlock;
}
}
}
Список свободных блоков в нашей реализации сделан не только двусвязным, но также и кольцевым. Это позволяет считать началом списка любой из блоков и тем самым начинать поиск с любого места. При выдаче свободного блока по запросу в реализации метода get мы ищем блок подходящей длины, и, если такой блок найден, то оставляем указатель на начало списка в том месте, где был закончен поиск. Это позволяет перемещать начало списка свободных блоков в разные места буфера. Если бы начало списка было всегда в одном и том же месте, то из-за внешней фрагментации свободные блоки небольшого размера скапливались бы около него, т. к. именно там наиболее вероятно разбиение блока на две части. В конце концов это приводит к тому, что функция get начинает работать все медленнее, т. к. приходится просматривать все большее число свободных блоков, которые не будут удовлетворять запросу из-за своей небольшой величины. Перемещение начала списка в разные места буфера памяти позволяет более равномерно распределить по буферу мелкие блоки, получающиеся в результате внешней фрагментации, и тем самым повысить скорость работы системы.
Предыдущая << 1 .. 101 102 103 104 105 106 < 107 > 108 109 110 111 112 113 .. 161 >> Следующая
Книги
Web-программирован-
ие
Аппаратное обеспечение Графика Руководство по П.О. Самоучитель Теория программирования Фотошоп Языки программирования
Новые книги
Вирт Н. "Систематическое программирование " (Теория программирования)

Эком "Microsoft Excel 2000 шаг за шагом Русская версия самоучитель " (Самоучитель)

Поляков А.Ю. "Методы и алгоритмы компьютерной графики в примерах Vizual C++" (Графика)

Баяковский Ю.М. "Графическая библиотека Open GL " (Графика)

Валиков А. "Технология " (Языки программирования)
Авторские права © 2013 ComputersBooks. Все права защищены.