Теоретический вопрос: изменение файла

Most languages / file systems don't let you truncate the beginning of file.

придется переписать, либо если свободного меств нет сделать такой трюк:

mmap его, пройтись по нему перевернув файл, truncate, пройтись опять перевернув файл.

>mmap его, пройтись по нему перевернув файл, truncate, пройтись опять перевернув файл.

Клево, я бы не додумался =)

Думаю что надо по любому. Представим такую ситуацию: файл в файловой системе представляет собой последовательность 5-и блоков по 1024 байта. Надо удалить 1 байт в начале. По любому надо будет двигать все байты во всех пяти блоках.

Я не знаю суть задачи которая должна быть решена. Но может лучше использовать файл как FIFO/очередь. Т.е. делаем файл фиксированного размера. В начале файла храним два числа: смещение «головы» и смещение «хвоста». При добавлении в очередь некоторого числа байт размещаем данные в «хвост» и увеличиваем смещение «хвоста». Извлекаем байты соотвественно из «головы». Если смещение должно выйти за пределы установленного размера, то смещение сбрасывается на начало блока.

>mmap его, пройтись по нему перевернув файл, truncate, пройтись опять перевернув файл.

Интересное решение. Только непонятно зачем проходиться по файлу дважды? Можно ведь file_array[i]=file_array[i+num_to_delete] для каждого байта файла сделать (за исключением последних байт)

> Можно ведь file_array[i]=file_array[i+num_to_delete] для каждого байта файла сделать (за исключением последних байт)

man memmove он умеет копировать перекрывающиеся области памяти.

точно

> Но может лучше использовать файл как FIFO/очередь.

Или просто хранить записи в отдельных файлах. Если там записи, а не просто поток байтов.

> Думаю что надо по любому. Представим такую ситуацию: файл в файловой системе представляет собой последовательность 5-и блоков по 1024 байта. Надо удалить 1 байт в начале. По любому надо будет двигать все байты во всех пяти блоках.

Исходя из этого и возник вопрос =)

> Я не знаю суть задачи которая должна быть решена. Но может лучше использовать файл как FIFO/очередь. Т.е. делаем файл фиксированного размера. В начале файла храним два числа: смещение «головы» и смещение «хвоста». При добавлении в очередь некоторого числа байт размещаем данные в «хвост» и увеличиваем смещение «хвоста». Извлекаем байты соотвественно из «головы». Если смещение должно выйти за пределы установленного размера, то смещение сбрасывается на начало блока.

А не выйдет ли это дольше чем считать весь файл/записать?

> Думаю что надо по любому. Представим такую ситуацию: файл в файловой системе представляет собой последовательность 5-и блоков по 1024 байта. Надо удалить 1 байт в начале. По любому надо будет двигать все байты во всех пяти блоках.

Как по мне то все зависит от ФС и ее реализации. Можно представить себе такой вариант в котором эта операция будет дешевой:
Пусть в иноде хранится указатель на первый кластер файла и смещение в нем. Тогда при обрезании головы файла мы можем легко переместить его начало на 1 байт изменив лишь смещение.

> Как по мне то все зависит от ФС и ее реализации.

Пусть в иноде хранится указатель на первый кластер файла и смещение в нем. Тогда при обрезании головы файла мы можем легко переместить его начало на 1 байт изменив лишь смещение.

Вот уж ололо так ололо. Ну расскажи, каким системным вызовом будет производится операция удаления первого байта? remove_first_byte()?

> Как по мне то все зависит от ФС и ее реализации. Можно представить себе такой вариант в котором эта операция будет дешевой

вообще, по сути дела ФС это такой персистентный STL:) В 21 веке можно ожидать поддержки и чего то большего чем вектор:)

Мм... Значит откат.

>А не выйдет ли это дольше чем считать весь файл/записать?

Ты видимо вообще не понял о том, что я говорил. Скорость - это как раз таки главное достоинство этого метода. Тут по барабану удаляем некоторое количество байт из файла размером 10 кб или из файла размером 10 Гб. Если файл будет очень большим, то предложенный вариант с memmove() загнется.

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

Инструкция:

1. http://ru.wikipedia.org/wiki/FIFO - читаем небольшой раздел про реализацию очередей на базе массива

2. читаем man mmap

3. ...

4. PROFIT

Забыл указать ещё один недостаток - фиксированный размер файла.

Не фиксированный. Очередь можно легко расширять и сокращать, если в конце пусто.

>Не фиксированный. Очередь можно легко расширять и сокращать, если в конце пусто.

Действительно. Об этом я не подумал.

Думаю что надо по любому. Представим такую ситуацию: файл в файловой системе представляет собой последовательность 5-и блоков по 1024 байта. Надо удалить 1 байт в начале. По любому надо будет двигать все байты во всех пяти блоках.

А вот если надо сдвинуть на размер блока, думаю большинство ФС архитектурно вполне позволят это сделать (первый блок помечаем как свободный, ставим указатель начала на второй блок). Более того, даже если файл занимает 1 байт, там будет (блок - 1) байтов неиспользуемого места. И какая разница, будет этот padding только в конце или в конце и в начале.

Т.е. вопрос вполне разумный и ФС можно сделать так, чтобы эти операции были быстрые. Видимо пока это никому особенно не было нужно.

>А вот если надо сдвинуть на размер блока, думаю большинство ФС архитектурно вполне позволят это сделать

Согласен, но тогда будет зависимость от конкретной реализации ФС, что ИМХО плохо. Да и зачем выносить эту возможность в общий API.

Я смотрю так или иначе задача сводится с созданию собственной файловой системы внутри файла, от простенькой до сложной. Что далеко не всегда есть минус. К примеру игры часто хранят свои ресурсы в подобных фнутренних файловых системах, что позволяет в разы увеличить скорость чтения за счёт экономии на операциях с файловыми дескрипторами. Тот же ZIP позволяет инкрементально добавлять файлы в архив любой степени вложености, при этом хранит структуру директории именно в конце файла по той же причине - быстрая операция truncate/append. Лично я ничего плохого в таком велосипедостроении не вижу.

> Ты видимо вообще не понял о том, что я говорил. Скорость - это как раз таки главное достоинство этого метода. Тут по барабану удаляем некоторое количество байт из файла размером 10 кб или из файла размером 10 Гб. Если файл будет очень большим, то предложенный вариант с memmove() загнется.

Ну что такое FIFO вроде тоже знаю, использовал дня IPC =) А получится ли применить FIFO к УЖЕ существующему файлу?

>Ну что такое FIFO вроде тоже знаю, использовал дня IPC =)

IPC??? Ты надеюсь не путаешь с pipe. FIFO - (рус.) первым вошел, первым вышел. Это просто структура данных типа «очередь». Ещё FIFO называют спец. файл (named pipe) для межпроцессного обмена, он создается с помощью mkfifo(). Но это совсем другая вещь, я говорил о FIFO именно как о структуре данных.

А получится ли применить FIFO к УЖЕ существующему файлу?

http://ru.wikipedia.org/wiki/FIFO - читай до состояния просветления. Тогда и получишь ответ на свой вопрос. Похоже на то, что я уже не в силах помочь тебе.

> позволяет в разы увеличить скорость чтения за счёт экономии на операциях с файловыми дескрипторами.

А чего только в разы? Почему не в десятки, сотни, тысячи раз?

Дело не в дескрипторах, разумеется, и не в проверках прав (это копейки), дело в фрагментации: много мелких файлов почти наверняка окажутся в разных углах НЖМД. К тому-же игроделы заботятся о виндузятниках, не имеющих reiserfs и страшно боящихся больших количеств мелких файлов.

> Дело в фрагментации: много мелких файлов почти наверняка окажутся в разных углах НЖМД.

Будучи записаны последовательно друг за другом на диск, с фрагменатцией в 2-3%, как большинство ntfs/etx{2,3} партиций?

К тому-же игроделы заботятся о виндузятниках,... страшно боящихся больших количеств мелких файлов.

Городская легенда.

> http://ru.wikipedia.org/wiki/FIFO - читай до состояния просветления. Тогда и получишь ответ на свой вопрос. Похоже на то, что я уже не в силах помочь тебе.

Хорошо. Походу придется перейти на практику. Как это реализовать? Ну скажем на Си.

За что купил, за то и продаю. Сам бенчмарков не делал. Но игроделов миллион и все пакуют ресурсы, это о чём-то говорит.

один знакомый уровня технического директора из околоигровой сферы отзывался примерно в том духе, что увязнуть в написании своей ФС — это жопа.

[Head|Tail]... Да вы, батенька, прологом увлеклись... :)

Каждый второй школьник уже написал модуль для fuse, а техдиректор боится? Он такой один, несомненно. Там же не настоящая фс нужна, а что-то типа tar, даже проще.

> Он такой один, несомненно. Там же не настоящая фс нужна, а что-то типа tar, даже проще.

ну он из сферы защиты игр от копирования, ему с шифрованием еще нужно было:)

> это о чём-то говорит.

Это говорит о том, что ресурсы игры - ридонли. ;)