*
* "modpages-in-memory" approach
* =============================
* This approach divides the underlying File into seamless blocks of
* equal size. These blocks are called "pages". Two kinds of pages exist:
* modified and unmodified pages.
* Right after construction, all pages are unmodified. (We may use a tree
* that contains only modified pages. So this tree is empty right after
* construction).
* If a write-(or read-)operation spans multiple pages, it is treated as
* multiple discrete write-(or read-)operations not spanning multiple pages.
* Whenever an attempt is made to write() to a page, it is made sure
* that this page is modified. If it is not modified, "page-size" bytes of
* memory are allocated and filled with the corresponding bytes from the
* underlying file. The write is then performed in memory.
* read()s are served from modified pages if possible.
* extend() and truncate() are treated like writes with zeros.
* But they must create new pages and/or change the size of the last page
* and realloc().
* insert() and cut() have "naive" implementations, which
* translates them into a combination of extend()/read()/write() and
* read()/write()/truncate(), respectively.
*
* Performance analysis (performance grades are relative to the probability of the event):
* - read() and write() cause little trouble. good performance.
* - truncate() and extend() cause little trouble. good performance.
* - insert() and cut() cause big trouble. bad performance.
* - memory consumption is high only for insert()/extend(). kind-of memory-efficient.
* This approach is easy to implement. It has been used extensively used
* in HT 0.7.x and its predecessors.
*
* "modareas-in-memory" approach
* =============================
* This is the approach used by a FileModificator. This is meant
* to be a more progressive approach compared to the above.
* As is well known from complexity-theory (and a programmer's all-day
* work) you can often save memory by wasting some more (CPU-)time and
* vice-versa.
* As pointed out in both analyses above the insert() and cut()
* operations cause these approaches to comsume very much memory (about as much
* as the file's size !).
* We will combine these two statements into a new approach:
* It's derived from the "modpages-in-memory" approach, with some exceptions:
* - "seamless blocks of equal size" become "seamless, dynamically sized blocks".
* We will call them areas.
* - due to their dynamic size, areas also have dynamic start offsets.
*
* Taking the notions from "modpages-in-memory" we have then also:
* "modified and unmodified areas".
* But we will now call the unmodified areas "copied areas".
* (And both copied and modified areas must to registered in a tree).
* insert() and cut() can now be implemented by simple
* operations on the areas. Memory consumption drops drastically on huge
* files (as compared to all other methods).
* This approach is hard to implement (the code written is complex).
* It will be used in (at least) HT 2.x.x .
*/
class FileModificator: public FileLayer {
protected:
AVLTree mods;
FileOfs newsize;
FileOfs pos;
int mcount;
int inv_mcount;
bool cut1(ObjHandle h, FileOfs rstart, FileOfs size);
ObjHandle findArea(FileOfs o);
void flushMods();
void invalidateMods();
bool isModified() const;
bool isModifiedByte(FileOfs o);
void makeAreaModified(ObjHandle h, FileOfs rstart, FileOfs size);
void read1(FileArea *a, FileOfs rstart, byte *buf, uint count);
void write1(FileArea *a, FileOfs rstart, const byte *buf, uint count);
public:
FileModificator(File *file, bool own_file);
/*