LINUX.ORG.RU

Можно ли обмануть malloc/free?


0

0

Допустим, мы захватываем память при помощи

int *p = (int*) malloc( 5*sizeof(int) );

Теперь, указатель p указывает на кусок памяти в 5 целых чисел. После некоторых операций, среди которых может быть например такая

int *q = p + 1;

Надо освободить память от первого элемента массива, а на остальные 4 элемента должен благополучно ссылаться q. Понятно, что тупое

free( p ); /* не годится */

убьет весь блок памяти. А надо, чтобы освободилась только первое целое число.

Можно ли это сделать и если можно то КАК???????

★★★
Ответ на: комментарий от cobold

> а фрагментации не боитесь?

На самом деле я так с фрагментацие борюсь :). Просто детали не приводил.

atoku ★★★
() автор топика

А у вас там действительно целые числа?

Потому что может лучше вместо массива список организовать?

anonymfus ★★★★
()
Ответ на: комментарий от anonymfus

> А у вас там действительно целые числа?

Там на самом деле список чего-то. Например, указателей :). Хочется дефрагментировать список. Я делал функцию копирования (дубликата) списка. Чтобы по быстрому скопировать один список в другой, пытался маллоком захватить память. Длина списка у меня храниться, так что это была разовая операция. А потом связать элементы массива как у списка. Все было бы ничего, кабы потом у списка не надо было бы, скажем, удалять элементы.

Вот тогда хлопается весь массив, а надо, чтобы только голова.

atoku ★★★
() автор топика
Ответ на: комментарий от atoku

> Там на самом деле список чего-то. Например, указателей :). Хочется дефрагментировать список. Я делал функцию копирования (дубликата) списка. Чтобы по быстрому скопировать один список в другой, пытался маллоком захватить память. Длина списка у меня храниться, так что это была разовая операция. А потом связать элементы массива как у списка. Все было бы ничего, кабы потом у списка не надо было бы, скажем, удалять элементы.

> Вот тогда хлопается весь массив, а надо, чтобы только голова.

Это ты так с фрагментацией боришься? Или оптимизируешь, что бы список в кеш процессора попадал?

Если первое, и элементы списка одинакового размера, то проще сделать пул элементов списка: http://en.wikipedia.org/wiki/Memory_pool .

outdoor_profanity
()

я думаю тебе нужен memmove + realloc

тормознуто но шуршать будет

или если размер елемента кратен(выровнен) 4К то наверное можно поигратся с mmap()

cvv ★★★★★
()
Ответ на: комментарий от outdoor_profanity

> ты так с фрагментацией боришься? Или оптимизируешь, что бы список в кеш процессора попадал?

Чтобы список в кэш попадал. Дело вот в чем, сделал я для списка сортировки: merge sort и combsort. Первый переставляет элементы, сортирует обалденно быстро (мало вызовов функции сравнения) и устойчивый. А второй просто переставляет значения (не перевязывает элементы). И хотя он вызывает функцию сравнения в несколько раз чаще, работает в два раза быстрее! Из-за того, что элементы списка остаются в том же порядке и близко друг к другу. А merge их перемешивает в памяти. Отсюда пришла эта идея. Но malloc/free слишком слабые для ее реализации. Надо уметь освобождать память того размера, какого хочется.

atoku ★★★
() автор топика
Ответ на: комментарий от cvv

> я думаю тебе нужен memmove + realloc

Боюсь что лекарство будет тяжелее болезни. :( Видимо надо мне на это все положить пока, а уже после, если будут у пользователей пожелания быстрых списков, то сделать их на динамических массивах, уже с тем самым realloc, когда пользователь перелезает за лимит. Кажется так сделано в STL.

А может не надо и мучиться, а то придется расставаться с красивыми вещами вроде реверса за O(n) или merge сортировки на месте с расходом памяти O(1). Каждый список для своих задач :)

Но есть еще надежда, что моя идея дубликации больших маломеняющихся списков удастся. Только надо как-то сварганить функцию освобождения памяти типа free с параметром - размером освобождаемой памяти.

В общем, вопрос теперь таков: как освободить память по указателю, но того размера, какого хочецца?

atoku ★★★
() автор топика
Ответ на: комментарий от atoku

> Чтобы список в кэш попадал. Дело вот в чем, сделал я для списка сортировки: merge sort и combsort. Первый переставляет элементы, сортирует обалденно быстро (мало вызовов функции сравнения) и устойчивый. А второй просто переставляет значения (не перевязывает элементы). И хотя он вызывает функцию сравнения в несколько раз чаще, работает в два раза быстрее! Из-за того, что элементы списка остаются в том же порядке и близко друг к другу. А merge их перемешивает в памяти. Отсюда пришла эта идея. Но malloc/free слишком слабые для ее реализации. Надо уметь освобождать память того размера, какого хочется.

Не совсем понятно как при сортировке появляются избыточные элементы, которые нужно удалять. И, если разница действительно в один элемент, то овчина, видимо, не стоит выделки. Хотя наверняка можно было бы изменить алгоритм таким образом, что бы список выравнивался по началу а не по концу (что бы p было равно q), ну или на крайняк приделать списку заголовок, где указывать размер списка и смещение первого элемента от начала списка.

HEBECTb_KTO
()
Ответ на: комментарий от atoku

>В общем, вопрос теперь таков: как освободить память по указателю, но того размера, какого хочецца?

написать свой free()

или вообще свою реализацию кучи

cvv ★★★★★
()
Ответ на: комментарий от atoku

> Все было бы ничего, кабы потом у списка не надо было бы, скажем, удалять элементы.

OMG. А не проще просто удаляемый элемент поменять местами с последним, и сделать realloc на элемент меньше?

anonymous
()

Боюсь я что писать придется свой аллокатор или вообще свою реализацию работы с кучей :(

catap ★★★★★
()
Вы не можете добавлять комментарии в эту тему. Тема перемещена в архив.