Ищу алгоритм удаления
Вспомнил проблемку которую давно решил, но совершенно не помню как.
Что имеем?
Некий файл, хранилище данных, данные туда записываются поблочно, типа 100, 200, 500 байт. Этих блоков может быть дофига, миллионы и больше.
Каждый блок имеет свой адрес (смещение от начала файла). Этот адрес может записываться в другие блоки, то бишь блоки желательно не перемещать.
С записью проблем проблем нет, пиши всегда в конец. Но блоки нужно удалять, либо вместо малого блока записать более большой, когда при обновлении блока данных стало больше.
Удаленные блоки можно записывать в список удаленных, после оттуда выбирать подходящие. Из больших блоков можно делать маленькие, а два маленьких соседних блока объединять в большой.
Вот как сделать этот список удаленных блоков лучшим образом? Он же тоже место будет занимать.
Удалили 1000 блоков, а после использовали 900. Список остался, но уже не такой большой.
Вот как сделать этот список удаленных блоков лучшим образом? Он же тоже место будет занимать.
И что?
Раз вы решили управление файлами вынести на более высокий уровень прикладного кода, то и создавайте на этом уровне что-то вроде файловой таблицы. Только вместо файлов в ней будут ваши блоки.
А почему, собственно, пишете в один файл, вместо того, чтобы по файлу на блок?
это классическая задача аллокаторов памяти. В каждый блок в начале записываете структурку, которая связана соседями линейным двухсвязанным списком (чтобы детектировать, что соседний блок удалили и надо объединить свободное пространство), а в каждый удаленный - дополнительно пишем структуру динамически балансируемого дерева, в котором все отсортировано по размеру этого свободного пространства.
При запросе на новый блок в за логарифмическое время находите первый блок по размеру, который удовлетворяет (или если нет, то пишем в конец).
При удалении пользуемся линейным списком чтобы понять соседа и, если сосед пустой, объединяем (еще два реквеста в бинарное дерево).
Если программа имеет информация о блоках и при удалении может сказать еще размер блока, то двухсвязанный список можно не хранить, чтобы память сэкономить, но тогда надо иметь еще одно бинарное дерево, в котором сортировка уже идет по местоположению в памяти.
Так устроенный аллокатор памяти реально ускоряет алгоритмы, в которых часто надо аллоцировать-деаллоцировать, и последний раз я проверял в линуксе и винде несколько лет назад, ускорение было разы по сравнению со штатными системными средствами.
Стандартно - блоки помечаются - удаленные.
Ну пометил, а как искать? не лазить же по всему файлу.
проводится ужимание
каким образом? Позицию "занятых" блоков менять нельзя, разве что системные блоки, которые еще можно контролировать как то.
блобы вполне подходят
В базе? нет, никакой прослойки, быстродействие резко упадет думаю.
Вот как раз проблема перед глазами. Была отличная прога каталогизатор файлов с бинарным сохранением данных.
Сделали новую и решили пользовать SQLite. Пользоваться прогой невозможно стало и медленней и размеры сохранённых данных увеличились
а как искать?
-------
по индексу перестроенному после изменения
менять нельзя
------
Можно. Разумеется с коррекцией ссылок.
Можно подумать над чем-то похожим на FAT (FAT16,FAT32,FAT64)
быстродействие резко упадет думаю
-----
Не-а...
Пока ты добъешься такого же - последняя весна закончится
невозможно стало
-----
Кури доку на sqlite.Я об нем ничего не знаю
Что Я знаю на 100% - нормальный сервер БД с большим объемом данных работает быстрее самописок.
С единственным исключением - когда данные статичны и денормализованны - самописка будет быстрее. Но! Статичных данных у нас не бывает.
а как искать? ------- по индексу перестроенному после изменения
Так как раз в дополнительных данных и проблема, как их сделать динамическими?
Можно. Разумеется с коррекцией ссылок.
Ссылки менять не могу - это прерогатива пользователя.
Не-а...Пока ты добъешься такого же - последняя весна закончится
очень сомневаюсь
нормальный сервер БД с большим объемом данных работает быстрее самописок
многое зависит от данных и их организации
Ну так как проблема как раз в этом дереве. На каждый удаленный блок пишется дополнительная структура. Блок взяли а что делать со структурой?
проблемы-то нет. Каждая структура (или класс, если на С++) листка этого бинарного дерева сидит в блоке со свободной памятью - вы же ее удалить не можете, так как после нее есть блок с занятой памятью. Очевидно, если блок был в конце файла, то лучше его просто удалить и из бинарного дерева и из файла. А вот головка, или корень этого бинарного дерева - это несколько десятков байт, и их можно в оперативке сохранить.
Самописный код бинарного дерева
380 725 7945 bintree.c
83 191 1942 bintree.h
463 916 9887 итого
меньше 500 строк сишника, в современном С++ есть соответствующий класс, и не надо велосипед выдумывать. Предполагаю, что в других языках и бинарное дерево, и двухсвязанные списки тоже в стандартных библиотеках имеются. Весь код такого аллокатора:
380 725 7945 bintree.c
83 191 1942 bintree.h
112 216 2158 decmem.c
463 969 11349 dmem.c
93 267 3159 dmem.h
336 592 5963 memc.c
62 170 1358 memc.h
292 1127 7883 memf.f
303 639 6732 quemem.c
2124 4896 48489 итого
у меня в свое время получился слегка больше двух тысяч строк и в 90-х я это примерно за месяц запрограммировал и радовался. Как я говорю, сейчас все это решается стандартными средствами С++, поэтому код дарить не буду, но рассказать-объяснить постараюсь. Если хотите, или так будет проще, могу войсом, тогда в личке телефонами обменяться
надо будет.
и их можно в оперативке сохранить.
В том и дело, что нельзя.
Открыл прогу, добавил данных, ушел.
Открыл прогу удалил данные, ушел.
Открыл прогу, добавил данных, ушел.
и в 90-х я это
Там именно я и об этом. В каком - то журнале было описание процесса сохранения данных, мне так понравилось, что в следующем проекте это и использовал. Было просто и удобно.
Сейчас что подобное хочется, но детали забылись.
поэтому код дарить не буду
Да код и не нужен, спасибо. Главное идея, а уж реализовать дело вторичное.
Относительно телефона нет проблем, но эта не та проблема, на которую нужно еще тратить ваше время. Это если вам, что понадобится просто с кем то обсудить, то всегда пож.
Ну и Си с плюсами я уже давно не пользую. Только С#.
Стандартная и очень частая задача. Ну например ссылки в Яве, DNS (именя в IP адреса) и т.п.
Решается путем введения двух идентификаторв: физического представления блока (смещение) и его логического представления (ссылка на блок), а также отображения между ними. Используется только логические ссылки. Физическое представление только в реализации.
BlockRef // Логический идентификатор, напрмер, int BlockOffset // Физическое расположение например смещение в файле interface Storage BlockRef alloc(size int) delete(BlockRef) resize(new_size int) byte[] read(BlockRef) write(BlockRef, byte[]) class FileStorage implements Storage File file // Здесь все храним Map block_allocation<BlockRef, BlockOffset> // Фактически таблица размещения это главная структура (тоже интерфейс) gc() // Запускаем периодически для сборки мусора, уплотнения и пр. оптимизаций
Главное это как отображать логические ссылки в физическое расположение. В простейшем случае это map. Но в реальности думаю есть миллионы разных способов для разных применений. Как говорится "зависит от контекста". Ну например можно хранить во многих файлах или большие блоки отдельно от маленьких или реализовать очередь запросов в случае конкурентного доступа и т.п. Надо конечно заниматься подсчетом использования ссылок, но это все просто для простых применений, а для сложных можно постепенно улучшать, поскольку интерфейс определен.
> и их можно в оперативке сохранить.
В том и дело, что нельзя.
можно, не значит нужно, если надо полностью иметь структуру на диске, то эта сотня байт спокойно помещаются в начало файла с данными, или в любой другой дополнительный файл.
Только С#.
не знаю его библиотеки и шарпом не пользуюсь, но предполагаю, что можно присовокупить соответствующий класс их С++ и средствами шарпа сохранить на диск туда, где ему нужно быть. Остальную логику я вроде рассказал. Если не понятно объяснил, не стесняйтесь, спрашивайте.
Это если вам, что понадобится просто с кем то обсудить, то всегда пож.
спасибо, не, у меня такой задачи сейчас нет, была когда в 90-х диссер писал, и с тех пор особо не менял
там ничего, работает же, и есть доказательство оптимальности при определенных условиях.
С записью проблем проблем нет, пиши всегда в конец. Но блоки нужно удалять, либо вместо малого блока записать более большой, когда при обновлении блока данных стало больше.Удаленные блоки можно записывать в список удаленных, после оттуда выбирать подходящие. Из больших блоков можно делать маленькие, а два маленьких соседних блока объединять в большой.Вот как сделать этот список удаленных блоков лучшим образом? Он же тоже место будет занимать. Удалили 1000 блоков, а после использовали 900. Список остался, но уже не такой большой.
Ну добавлять всегда в конец это не очень хорошо. Вернее хорошо, если скорость добавления важнее других требований. А так в общем случае можно например завести таблицу выделенных блоков где одна запись описывает один блок. И таблицу свободного пространства (дырок), где одна запись это одна дырка, т.е. свободный блок. Они индексируются по длине, чтобы быстро находить блок или дырку нужного размера. При выделении нового блока находится подходящая дырка. При удалении блока надо либо новую дырку добавить либо расширить соседние дырки. Вопрос только как обновлять таблицу размещения и индекс.
как их сделать динамическими?
------
Апдейтить после каждого изменения исходных данных.
это прерогатива пользователя.
-----
Ну так вообще никаких проблем - подтверждает актуализацию или ждет оной. Не твоя же забота.
зависит от данных и их организации
-----
Не понял.
ты хочешь сравнивать не эквивалентные схемы? Так это изначально бессмысленно.
быстрее чем просто прочитать данные?
------
В некоторых случаях - да.
У тебя получается короткий "индекс" из имен файлов, вместо скана всего файла.
нужно их же перенести на другой комп/ в другой каталог.
-------
Зачем?
Написал батник и запустил без окна - все пройдет довольно быстро.
Ну так это и есть проблема, как ее оптимально организовать.
Это именно решение:
1. список дырок в виде записей <смещение, размер>: <1000, 500>, <2000, 200>, <3000, 700>
2. индекс в виде сортировки по размеру: [1, 0, 2]
Так что не вижу где здесь еще что-то можно решать. Вот это "как ее оптимально организовать" вообще ни о чем, поскольку нет критериев оптимальности: оптимизировать чтение, запись, память (на диске или в памяти), конкурентный доступ, распределенное представление или что-то еще.
А проблемы здесь было 2:
- как избежать обновления ссылок на блоки при перемещении блоков -> Ответ: путем введения логических ссылок
- как управлять таблицей размещения -> Ответ: путем сортировки по размеру (и потом двоичного поиска)
Обе проблемы для технического интервью на мидла наверное.
1. выкидываешь - size - всегда распределяешь стандартными блоками 512, 1024, 8096
2. выкидываешь - freeblockref - цепочка свободных блоков, если нужна, ведется отдельно
3. выкидываешь - leftnode - скан всегда рута
4. заменяешь - rightnode - на - nextblock - это где лежит продолжение, если не уместился
делаешь другую структуру (имя/ключ(8.3?), firstblock, size, removed)
работает так
- начальная разметка - пустой список ключей и зануленная таблица блоков
- добавил- сделал запись ключа, заполнил занятые блоки, последний пометил мах(н) FFF?
- удалил -- пометил ключ как удаленный
- очистка - зануляешь цепочку nextblock и удаляешь ключ
Таблицу структур имя/ключ пишешь в обычный блок и расширяешь по мере необходимости.
Таблицу nextblok'ов - размещаешь целиком на максимальный размер набора.
Это грубая эмуляция FAT. Код есть на сайтах эмбедеров.
Так что не вижу где здесь еще что-то можно решать.
Попробую пояснить.
Есть какой-то список дырок, каждый элемент списка имеет свой размер.
Вначале список пустой, затем увеличивается, после может уменьшаться.
Вот процесс увеличения и уменьшения размера списка и интересует.
Даже скорее уменьшение размера списка дырок.
Ответ: путем введения логических ссылок
Еще один уровень для доступа и еще одна таблица перевода логических ссылок в физические?
Вначале список пустой, затем увеличивается, после может уменьшаться.
--------------
Либо резервируется изначально. Где много вставок - чем больше резервируется - тем лучше.
И зачем уменьшаться? Увеличение всегда дорого.
Если будет совсем плохо - см ISAM. Сишных реализаций не знаю.
Либо резервируется изначально.
Ну вот создал я файл, сколько резервировать?
И зачем уменьшаться
Допустим у меня в папочке 10 тыс. файлой, тогда в моем списке будет 10000+1 записи (папочка+файлы)
удаляю я всю папочку, получаю 10т.+1 описаний дырок. Сканирую следующую папочку с 9т. файлов, остается всего 1т. дырок.
Значит теперь структура описания удаленных файлов содержит 9т ненужных записей.
Всё оставлять?
Ну вот создал я файл, сколько резервировать?
------
размер диска/квоты делишь на размер выбранного блока => получаешь возможное количество блоков
смотришь сколько байт нужно чтобы поместился номер последнего блока
резервируешь: количество блоков * количество байт для номера
И, кстати, будет не вредно сразу прописать весь файлик мусором - чтоб место физически выделилось.
1. Все полезные алгоритмы нужно хранить на флешки/CD/внешнем диске.
2. Даже Microsoft не смогла сделать толком нормальную утилиту по дефрагментации диска, она купила её помойму у Symantec. Когда удаляются файлы, там помечается каким-то флагом что файл удалён, и при этом остаются дырки, а при дефрагметации диска пустые места (дырки) заполняются данными. Дефрагментация это долгий процесс.
3. В файловой системе блоки (сектора) фиксировоной длины, помойму 1 блок (сектор) = 512 байт.
4. Не понял задачу, но как-то так:
#include <iostream>
#include <cstdlib>
#include <cstring>
using namespace std;
// Копирует блок в общую память
void copy_block(char *buf, char *data, int pos) {
memcpy(buf+pos, data, strlen(data));
}
// Удаляет блок из общей памяти
void delete_block(char *buf, int pos, int len) {
memset(buf+pos, '\0', len);
}
int main(int argc, char** argv) {
char *buf; // Общая память
char block1[] = "Hello "; // блок содержащий слово Hello
char block2[] = "Igor"; // блок содержащий слово Igor
char block3[] = "Ann";// блок содержащий слово Ann
buf = (char *)malloc(65535); // Резервируем память 65К
memset(buf, '\0', 65535); // Инициализируем память
copy_block(buf, block1, 0); // Копируем в 0 ячейку памяти Hello
copy_block(buf, block2, strlen(block1)); // Копируем в 5 ячейку памяти Igor
cout << buf << endl; // Выводим на экран Hello Igor
delete_block(buf, strlen(block1), strlen(block2)); // Удаляем в 5 ячейки памяти 3 байта
cout << buf << endl; // Выводим на экран Hello
copy_block(buf, block3, strlen(block1));// Копируем в 5 ячейку памяти Ann
cout << buf << endl; // Выводим на экран Hello Ann
free(buf); // Освобождаем зарервированную память
return 0;
}
А с блоками можно сделать примерно так:
struct BLOCK_1 {
long next_offset;
char buf[5];
};
struct BLOCK_2 {
long next_offset;
char buf[10];
};
struct BLOCK_3 {
long next_offset;
char buf[15];
};
BLOCK_1 block_1;
BLOCK_2 block_2;
BLOCK_3 block_3;
block_1.next_offset = 5;
strcpy(block_1.buf, "Igor");
block_2.next_offset = 5 + 10;
strcpy(block_2.buf, "Ann");
block_3.next_offset = 5 + 10 + 15;
strcpy(block_3.buf, "Mustermann");
P.S.:Извиняюсь если ответил не так, что-то последние три дня плохо соображаю, две ночи плохо спал.
Моя ФЛ Он и Она
Когда удаляются файлы, там помечается каким-то флагом что файл удалён, и при этом остаются дырки, а при дефрагметации диска пустые места (дырки) заполняются данными.
А зачем физически удалять данные, если достаточно пометить их как свободные для перезаписи?
Дефрагментация это долгий процесс.
Вместо вредной и медленной дефрагментации лучше скопировать всё на другой пустой диск, а потом на первом всё удалить. Теперь можно при необходимости повторить процесс, но в обратном направлении.
Чтобы фрагментация меньше доставляла проблем, нужно придерживаться примерно такого же правила, как для RAM - память должна использовать не более, чем на 2/3 от доступной. В идеале не более, чем на половину. Если используется больше, нужно докупить памяти. Оперативка, кстати, тоже страдает от фрагментации, хотя и в меньшей степени из-за своей скорости. Но ещё она страдает вдобавок и от свопа.
Значит вопрос фрагментации не решался.
Всё отлично решалось. И блоки были, только не фиксированной длины, а просто кратные степени 2ки.
Но пока ничего не навеяло на путь решения. Уже на этапе удаления блока, два соседних удалённых блока объединялись и в таблицу удаленных записывался только этот объединённый блок.
А как это повлияет на размер файла?
-------
А должно?
Или как я туда смогу что то записать из данных?
------
Находишь в таблице блоков пустой (000) блок и пишешь туда. Что не вошло - пишешь в следующий пустой.
Там навигация по блокам совершено элементарная - по положению описателя блока сразу получаешь смещение в файле, а описатель содержит номер следующего используемого блока.
не фиксированной длины, а просто кратные степени 2ки.
------
голову примени - либо фрагментация, либо фиксированный размер блока. Другого просто нет. Даже не комбинируется.
У винды, кстати, память управляется блоками фиксированной длины и под это дело уходит хренова куча памяти.
два соседних удалённых блока объединялись
-----
У тебя квота Х.
Ты пишешь последовательно (Х/2-2), (4). (Х/2-2) - полный.
Освобождаешь оба (Х/2-2).
Теперь тебе надо писать ровно (Х/2) - все, приплыли.
Если не приплыли, то как-то без блоков переменой длины.
А как это повлияет на размер файла?-------А должно?
конечно, зачем мне лишний мусор в файле
Находишь в таблице блоков пустой
Речь как то и идет о таблице пустых блоков мне нужно утилизовать записи которые уже не используются.
Что не вошло - пишешь в следующий пустой
Концепт другой, блок заполняется полностью.
зачем мне лишний мусор в файле
------
Чтобы повех него писать новую инфу.
Или т при удалении файла прописываешь занимаемое им место поперемено 0/1?
о таблице пустых блоков
------
А нету такой. За ненадобностью.
мне нужно утилизовать записи
-----
Ну так объявляешь блоки свободными и все.
Концепт другой,
------
Выше написано во что упрешься.
Чтобы поверх него писать новую инфу.
ну так и я о том же.
о таблице пустых блоков
------А нету такой. За ненадобностью.
И как же ты будешь дырки отслеживать?
Ну так объявляешь блоки свободными и все.
Для этого удаленные блоки данных и записываются в таблицу свободных блоков.
Выше написано во что упрешься.
расскажи лучше IBM, что процессор может быть только одноядерным
в таблицу свободных блоков.
------=
В таблицу блоков пишется:
000 - блок свободен для записи
FFF - блок последний в цепочке использованных блоков (первый - указан рядом с именем/ключем)
любое другое - номер следующего использованного этой записью блока
так это уже будет таблица использованных блоков
----------------
Это таки таблица где свободные блоки помечены 000 и порядковый номер(индекс в массиве) однозначно определяет смещение от общей выбранной точки до начала блока.
Если у тебя жопа с размерами данных - можешь сделать несколько групп блоков с разными размерами блоков и писать куда подходит.
Из твоего определения -
-----------
В моем определении сказано - если - смежные - там где кончается один - начинается другой.
Как по твоим цифрькам определить смежность? А то у меня одна из возможностей определить смежность как нахождение на следующей плоскости того же цилиндра да еще с фиксированным сдвигом.
В моем определении сказано - если - смежные - там где кончается один - начинается другой.
А ты случаем не забыл это определение написать?
А то у меня одна из возможностей определить смежность как нахождение на следующей плоскости того же цилиндра да еще с фиксированным сдвигом.
Ну да, если пустую бутылку от столичной обвернуть hex дампом файла, то возможно что то похожее и получится.
Цилиндром со времен ЕС ЭВМ называлось все находящееся по головками в текущем положении.
Ну так тонко и намекаю, что до такого определения цилиндра можно дойти только по ужО выпитой 
и не раз.
Но похоже все идеи по делу уже закончились. Ну ладно, будет пока неоптимальное решение.
либо полная информация и нормальные решения.
У меня такое чувство что ты забрался в раковину и никак не хочешь оттуда вылезти
Только какие то постулаты. Либо только фиксированные блоки либо только таблица обо всех блоках.
Ну вот пишу я миллион записей и ничего не удаляю, на кой мне информация о занятых блоках?
Тем более, что решение было и достаточно простое, раз не запомнилось. Но всё вертелось вокруг того, что размер блоков был кратен степени двойки.
задачу полностью определи
да не знаю что еще добавить, вроде уже всё написано.
Ну вот маленькая часть:
Есть список блоков в файле длина которых кратна степени двойки, соответственно есть начало блока Х и его длина L.
Появляется некий новый блок из того же файла с началом блока Х1 и длиной L1.
Если Х1+L1 = Х или Х+L = Х1, то блоки смежные и их можно объединить.
Ограничения: список блоков находится на диске (в памяти может не поместится), список блоков отсортирован по длине блоков.
Хочется иметь красивый алгоритм поиска смежных блоков. Что помню - это был побочный эффект организации списка блоков.
вроде уже всё написано
-------
Рамазано по постам, что-то учитывается, что опущено.
надо собрать в кучку
Надо обосновать отказ от предложенных вариантов.
Появляется некий новый блок из того же файла
-=-----
Ээээ... что значит - появляется? Его выбрали произвольно, с перекрытием других блоков? Его дописали? Начало? средина? Конец? Перехлест имевшихся блоков?
То, что Ты сам,Я или кто-то еще имеет какое-то свое понимание - не важно - опиши детали.
Х1+L1 = Х или Х+L = Х1
-------
Ну так у тебя написно - проверить текущий (Х1) на "смежность" с предыдущим и следующим.
список блоков отсортирован по длине блоков.
-------
Ну и как ты собираешься искать предыдущий и следующий?
Либо сортировка по Х, либо пороход по списку с выбором пары
побочный эффект организации списка
------
Списка или массива представления списка?
В первом случае у тебя только гарантия сортировки по длине, без информации об положении элементов списка.
Во втором у тебя список остается как был, но элементы можно физически упорядочить по возрастанию Х.
Его выбрали произвольно, с перекрытием других блоков? Его дописали? Начало? средина? Конец? Перехлест имевшихся блоков?
Перехлёст и перекрытие блоков абсолютно невозможно. В блоках же какая то инфа записана.
Да и вообще какая разница откуда он появляется? Если так интересно - его удалили.
не важно - опиши детали.
появляется проблема - нужно ли описывать, что земля не стоит на трёх китах?
Ну так у тебя написано
сам же просишь опиши детали, вот это и важные детали, а то опять цилиндр приплетёшь.
Ну и как ты собираешься искать предыдущий и следующий?
ну это и есть задачка....
Либо А, либо Б
Так не бывает, вполне может быть и С. Так это это чисто твое персональное мнение.
Например, считаем минимальный размер блока 16 байт, тогда все блоки в списке можно представить в двоичном виде
0 0 1 0 0 1 1 1 0 0 1 1000 0,16,32,48,64,80,96,112,128, 144,160, 176 -> адрес
Здесь 3 блока длиной 16,48 и 32 байта, по адресам 32, 80, 160
Тоже самое но без пробелов
001001110011000
добавляем теперь блок в 32 байта, по адресу 48
001111110011000
сразу видно, что с адреса 32 появился большой блок в 6*16=96 байт
это и есть задачка
------
Не-е, это не задачка - у тебя просто нет этой информации
минимальный размер блока 16 байт
-------
256 - не хочешь из-за большой таблицы.
Здесь 3 блока длиной ... добавляем теперь блок в 32 байта, по адресу 48
------
У тебя выше блок определен как 16 байт.
32 байта блоке быть не может - используй другой термин. Пусть будет - сегмент - добавил сегмент из двух блоков.
Что у тебя должно получится в списке? Таблицу ( не список ) занятых/свободных блоков Я вижу.
Остаются три 4 ранее определенных сегмента?
Или их надо конвертирвать в два? В смысле - три - слипаются?
Сегмент удаляется целиком или произвольными блоками?
вторичная сортировка никак невозможна
-------
Тогда что ты понимаешь под тем что список отсортирован?
Физически упорядоченные узлы (нах тогда список?) или логически упорядоченные ( т.е. 9 ссылается на 5 потому что 5 - описывает следующий по размеру сегмент)
Это Я к тому, что логические связки могут быть по размеру, а физический порядок - по номерам начального блока. Изменение одного не меняет второго.
У тебя выше блок определен как 16 байт.
определен только минимальный размер блока
В смысле - три - слипаются?
А что это не естественно? Три смежных свободных сегмента можно смело пустить в дело как один.
Сегмент удаляется целиком или произвольными блоками?
Сегмент или нужен или не нужен. Но у меня есть только блоки переменной длины.
Тогда что ты понимаешь под тем что список отсортирован? (по размеру блока)
Я могу достаточно быстро найти блок зная его размер.
Любой другой поиск не предусмотрен либо может организовываться простым перебором всех элементов.
Это Я к тому, что логические связки могут быть по размеру, а физический порядок - по номерам начального блока
Ну это уже два типа сортировки одних и тех же элементов. Которая осуществляется по мере расширения списка, а не некими дополнительными проходами.
определен только минимальный размер блока
-------
Ну следующий будет 18 байт....
А что это не естественно?
--------
нет.
Три смежных свободных сегмента можно смело пустить в дело как один.
------
Вот тут ты сам себе противоречишь - либо они слипаются, либо остаются отдельными.
Ты говоришь - слипаются, но в то же время у тебя как то имеются смежные не слипшиеся.
Доопределяй.
Но у меня есть только блоки переменной длины.
-------
Т.е. имется 16 байт переменной длины.
может организовываться простым перебором всех элементов.
----------
Ну это Я тебе давно сказал - либо организация, либо перебор.
Ну это уже два типа сортировки одних и тех же элементов.
-------
Аааа... ты необходимости пересортировки боишься.
Зря. Тебе предлагается один список удовлетворяющий обоим критериям одновременно.
Ну следующий будет 18 байт....
не может быть в принципе, следующий 32.
Вот тут ты сам себе противоречишь - либо они слипаются, либо остаются отдельными.
Не вижу никакого противоречия. Есть либо занятые блоки, либо свободные.
У занятых блоков нет операции слияния. Только свободные имеют такое право.
Т.е. имется 16 байт переменной длины.
блоки могут быть переменной длины, 16 байт - абсолютно минимальный размер блока.