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

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

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

// Обращение к рекурсивной функции, выдающей смещение свободного блока size_t request = getRec(р);
if (request == null) throw NoMoreMemoryException();
// В начало блока помещаем его размерность и выдаем адрес char * block = buffer + request;
*block = p;
return block + sizeof(char);
}
// Рекурсивная функция выделения свободного блока памяти size_t BinTwinsMemory::getRec(char p) {
// 1. Проверка: если запрашивается блок слишком большого размера,
// значит, свободной памяти больше нет if (р > power) return null;
// 2. Проверяем список свободных блоков нужного размера if (freeLists[р] == null) {
// Список пуст; запрашиваем вдвое больший блок. size_t doubleBlock = getRec(р + 1);
// Если запрос закончился неудачно, то возвращаем пустой указатель, if (doubleBlock == null) return null;
// Блок вдвое большего размера делится пополам;
// адрес блока-близнеца записывается в соответствующий список size_t twinBlock = doubleBlock + (1 « р);
* (size__t *) (buffer + twinBlock) = null; freeLists[p] = twinBlock; return doubleBlock;
} else {
// Свободный блок нужного размера найден; он исключается //из списка и его адрес выдается в качестве результата size_t result = freeLists[р];
freeLists[р] = *(size_t *)(buffer + freeLists[p]); return result;
}
// Операция возврата выделенного блока памяти в систему void BinTwinsMemory: : release (void * ptr) {
324
Гпава 5
11 Вычисляем адрес блока и его размерность р char * block = (char*)ptr - sizeof(char); char p = *block;
// Обращаемся к рекурсивной функции возврата блока в систему releaseRec(block - buffer, р);
}
// Рекурсивная функция возврата выделенного блока памяти в систему void BinTwinsMemory::releaseRec(size_t block, char p) {
// Вычисляем адрес близнеца size_t twinBlock = (1 « p) Л block;
// Организуем поиск блока-близнеца в списке свободных блоков size_t* ptr = &freeLists[р]; while (*ptr != null && *ptr != twinBlock) { ptr = (size_t*)(buffer + *ptr);
}
if (*ptr = null) {
// Адрес близнеца не найден - блок присоединяется к списку *(size_t*)(buffer + block) = freeLists[р]; freeLists[p] = block;
} else {
// Блок-близнец исключается из списка свободных блоков *ptr = *(size_t*)(buffer + *ptr);
// Рекурсивный вызов для освобождения блока удвоенного размера releaseRec(block & ~(lu « р), р+1);
}
}
Мы можем проверить работу метода двоичных близнецов, так же как и раньше, заставив отводить память внутри нашей системы с помощью переопределения операторов new И delete ДЛЯ класса Expression. В папке "Chapter5 \5.3\BinTwins" приложенного компакт-диска приведенная в листинге 5.8 система распределения памяти дополнена методами для подсчета некоторых статистических данных. Если воспользоваться для трансляции примера компилятором G++ фирмы Delorie Software, имеющемся на том же диске, то в нашем небольшом примере, где система распределения памяти используется для размещения в ней выражений при их дифференцировании и упрощении, статистика запросов к памяти выгляди!' очень плохо. Из-за потерь, вызванных внутренней фрагментацией памяти, память используется только на 50 процентов. Это происходит из-за того, что запросы к системе идут на выделение блоков по 8 и 16 байтов, а поскольку система для каждого блока вынуждена выделять еще один дополнительный байт, где помещается размер-
Алгоритмы распределения памяти
325
ность блока, то фактически каждый раз выделяется блок вдвое большей длины, чем необходимо.
На самом деле таких потерь памяти можно избежать, если не хранить длину блока в самом выделенном участке памяти. Вместо этого пользователи системы могут сами запоминать информацию о том, сколько памяти они запрашивали у системы, и передавать эту информацию позже в виде дополнительного аргумента метода release при освобождении памяти. В методе двоичных близнецов длины блоков всегда стандартные, а значит, система всегда может вычислить размер освобождаемого блока по значению переданного аргумента.
В папке "Chapter5\5.3\BinTwinsMod" приложенного компакт-диска такая модификация сделана, в результате чего использование памяти резко улучшилось: потерь памяти теперь нет вовсе. Изменения, которые пришлось сделать в коде реализации и использования системы распределения памяти, очень небольшие. Во-первых, теперь размерность блока не хранится в самом блоке, а вычисляется по значению второго аргумента метода release, во-вторых, оператор delete теперь приходится переопределять явно для всех классов, наследующих класс Expression, поскольку размер освобождаемого объекта теперь надо явно передавать системе в качестве аргумента, например:
class Varaible : public Expression { public :
void operator delete(void * ptr) {
memoryManagement->release(ptr, sizeof(Variable));
}
};
Еще раз напомним (см. разд. 4.3), что применение деструктора к выражениям, полученным в результате преобразования других выражений, опасно из-за того, что некоторые части этих выражений могут использоваться в дереве неоднократно, а значит, применение деструктора к такому дереву может вызвать повторное использование деструктора к одному и тому же объекту. Надежным способом очистки памяти после работы с выражениями служит очистка всей памяти сразу. Если вы программируете систему распределения памяти сами, то это можно легко сделать с помощью метода clear класса, реализующего такую систему, или путем применения деструктора сразу ко всей системе распределения памяти.
Предыдущая << 1 .. 107 108 109 110 111 112 < 113 > 114 115 116 117 118 119 .. 161 >> Следующая
Книги
Web-программирован-
ие
Аппаратное обеспечение Графика Руководство по П.О. Самоучитель Теория программирования Фотошоп Языки программирования
Новые книги
Завалишин Д. "Интернетско-русский разговорник" (Web-программирование)

Заенцев И.В. "Нейронные сети: основные модели" (Web-программирование)

Владимиров А.А. "Wi-фу: «боевые» приемы взлома и защиты беспроводных сетей" (Web-программирование)

Вьейра Р. "SQL Server 2000. Программирование в 2 ч." (Web-программирование)

Веллинг Л.Т. "Разработка web приложений с помощью php и mysql" (Web-программирование)
Авторские права © 2013 ComputersBooks. Все права защищены.

c1c0fc952cf0704ad12d6af2ad3bf47e03017fed