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

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

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

* (unsigned char *) &freePtr [size - MARKER_SIZE] = FREE_MARKER;
*(size_t*)&freePtr[size - MARKER_SIZE - SIZE_SIZE] = size;
}
// Операция выделения свободного блока памяти заданного размера void * get(size__t sz) ;
// Операция возврата выделенного блока памяти в систему void release(void * ptr);
};
//-------boardmarkers. срр--------------------------------------------------
// Операция выделения свободного блока памяти заданного размера void * BoardMarkersMemory::get(size_t sz) {
// 1. Поиск свободного блока подходящей длины if (freePtr == NULL) throw NoMoreMemoryException();
char * current = freePtr, // текущий блок при поиске
* last = freePtr, // отмечаем конец поиска
* found = NULL; // адрес найденного свободного блока
do {
if (*(size_t*)&current[MARKER_SIZE] >=
sz + SIZE_SIZE + 2 *MARKER_SIZE) { found = current; // свободный блок подходящей длины найден } else {
// переход к следующему блоку
current = *(char**)&current[MARKER_SIZE + SIZE_SIZE + PTR_SIZE];
}
316
Гпава 5
} while (found == NULL && current != last);
if (found = NULL) { // нет свободного блока памяти нужного размера! throw NoMoreMemoryException () ;
}
// 2. Разметка блока: устанавливаем указатели на служебную информацию
size_t * pLength = (size_t*)&found[MARKER_SIZE];
char ** pPred = (char**) &found[MARKER_SIZE + SIZE_SIZE];
char ** pNext = (char**)Sfound[MARKER_SIZE + SIZE_SIZE + PTR_SIZE];
unsigned char * pEndMarker =
(unsigned char *)Sfound[*pLength - MARKER_SIZE];
// 3. Если блок не слишком велик, он выделяется целиком if (*pLength < sz + 3*SIZE_SIZE + 4*MARKER_SIZE + 2*PTR_SIZE) { if (*pNext == found) { // Это был последний свободный блок
freePtr = NULL;
} else { // Исключаем блок из списка
*(char**)(*pPred + MARKER_SIZE + SIZE_SIZE+PTR_SIZE) =
freePtr = *pNext;
*(char**)(*pNext + MARKER_SIZE + SIZE_SIZE) = *pPred;
}
// Маркируем блок как занятый
*found = *pEndMarker = BUSY_MARKER;
// Возвращаем указатель на выделенное пространство return found + MARKER_SIZE + SIZE_SIZE;
// 4. Если блок достаточно велик, то он делится на два } else {
// вычисление новой длины свободного блока:
*pLength -= sz + SIZE_SIZE + 2*MARKER_SIZE;
// дополнительная разметка служебной информации на границе блоков: char * busyBlock = found + *pLength;
size_t* busyLength = (size_t*)(busyBlock + MARKER_SIZE); unsigned char * pFreeEndMarker =
(unsigned char *)(busyBlock - MARKER_SIZE); size_t * pEndLength = (size_t*)((chau:*)pFreeEndMarker - PTR_SIZE);
// формирование верхней границы нового блока:
*pEndLength = *pLength;
*pFreeEndMarker = FREE_MARKER;
// Переносим указатель списка свободных блоков freePtr = found;
// окончательное формирование выдаваемого блока и выдача результата: *busyBlock = *pEndMarker = BUSY_MARKER;
*busyLength = sz + SIZE_SIZE + 2 *MARKER_SIZE;
Алгоритмы распределения памяти
317
return busyBlock + MARKER_SIZE + SIZE_SIZE;
}
}
// Операция возврата выделенного блока памяти в систему void BoardMarkersMemory::release(void * ptr) {
// Сначала вычисляем адрес возвращаемого блока
char * releaseBlock = (char*)ptr - SIZE_SIZE - MARKER_SIZE;
// 1. Проверяем соседние блоки и вычисляем их адреса, если это // свободные блоки. Отсутствие свободного блока помечается // пустой ссылкой, char * firstAddr =
releaseBlock > buffer &&
((unsigned char *)releaseBlock)[-MARKER_SIZE] = FREE_MARKER ? releaseBlock - *(size_t*)&releaseBlock[-MARKER_SIZE - SIZE_SIZE] : NULL;
char * secondAddr = releaseBlock + (size_t*)SreleaseBlock[MARKER_SIZE]; if (secondAddr == buffer + size ||
*(unsigned char *)secondAddr != FREE_MARKER) {
secondAddr = NULL;
}
// 2. Рассматриваем три случая:
// 1) возвращаемый блок удается соединить с обоими соседними блоками;
// 2) возвращаемый блок удается соединить с одним из соседних блоков;
// 3) ни один из соседних блоков не свободен,
if (firstAddr != NULL) {
// Первый из блоков примыкает к возвращаемому if (secondAddr != NULL) {
// Второй блок тоже примыкает к возвращаемому - случай (1).
// Второй блок удаляем из системы, а первый расширяем: size_t newLen = (* (size_t*) & firstAddr [MARKER_SIZE] +=
*(size_t*)SreleaseBlock[MARKER_SIZE] +
* (size_t*)SsecondAddr[MARKER_SIZE]);
*(size_t*)&firstAddr[MARKER_SIZE] = newLen;
*(size_t*)&firstAddr[newLen - MARKER_SIZE - SIZE_SIZE] = newLen; char * predBlock = *(char**)&secondAddr[MARKER_SIZE + SIZE_SIZE]; char * nextBlock =
*(char**)&secondAddr[MARKER_SIZE + SIZE_SIZE + PTR_SIZE];
*(char**)&predBlock[MARKER_SIZE + SIZE_SIZE + PTRJSIZE] =
nextBlock;
*(char**)SnextBlock[MARKER SIZE + SIZE SIZE] = predBlock;
й
} else {
// Случай (2): первый блок расширяется
size_t newLen = *(size_t*)&firstAddr[MARKER_SIZE] +
*(size t*)&releaseBlock[MARKER SIZE];
318
Гпава 5
*(size_t*)&firstAddr[MARKER_SIZE] = newLen; firstAddr[newLen - MARKER_SIZE] = FREE_MARKER;
*(size_t*)&firstAddr[newLen - MARKER_SIZE - SIZE_SIZE] = newLen;
}
} else if (secondAddr != NULL) {
//Из примыкающих к возвращаемому есть только второй блок: случай (2)
*releaseBlock = FREE_MARKER;
Предыдущая << 1 .. 104 105 106 107 108 109 < 110 > 111 112 113 114 115 116 .. 161 >> Следующая
Книги
Web-программирован-
ие
Аппаратное обеспечение Графика Руководство по П.О. Самоучитель Теория программирования Фотошоп Языки программирования
Новые книги
Вирт Н. "Систематическое программирование " (Теория программирования)

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

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

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

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