Fix block insertion in replace_chunk

[hed.git] / libhed / file.c

/* $Id$ */

/*
 * hed - Hexadecimal editor
 * Copyright (C) 2004  Petr Baudis <pasky@ucw.cz>
 *
 * This program is free software; you can redistribute it and/or modify
 * it under the terms of version 2 of the GNU General Public License as
 * published by the Free Software Foundation.
 * 
 * This program is distributed in the hope that it will be useful,
 * but WITHOUT ANY WARRANTY; without even the implied warranty of
 * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
 * GNU General Public License for more details.
 * 
 * You should have received a copy of the GNU General Public License
 * along with this program; if not, write to the Free Software
 * Foundation, Inc., 59 Temple Place, Suite 330, Boston, MA  02111-1307  USA
 */

/*
 * There hammer on the anvil smote,
 * There chisel clove, and graver wrote;
 * There forged was blade, and bound was hilt;
 * The delver mined, the mason built.
 * There beryl, pearl, and opal pale,
 * And metal wrought like fishes' mail,
 * Buckler and corslet, axe and sword,
 * And shining spears were laid in hoard.
 */

/* Feature macros needed for:
 *  - memrchr
 *  - pread, pwrite
 *  - stpcpy
 */
#define _GNU_SOURCE

#include <config.h>

#include <errno.h>
#include <fcntl.h>
#include <limits.h>
#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#include <sys/ioctl.h>
#include <unistd.h>
#include <linux/fs.h>   /* BLKGETSIZE and BLKGETSIZE64 */

#include "file.h"
#include "access.h"
#include "cache.h"
#include "swap.h"
#include "tree.h"
#include "expr.h"

/* memrchr() might not be available */
#ifndef HAVE_MEMRCHR
# include "memrchr.c"
#endif  /* HAVE_MEMRCHR */

/*
 * `Piles of jewels?' said Gandalf. `No. The Orcs have often plundered Moria;
 * there is nothing left in the upper halls. And since the dwarves fled, no one
 * dares to seek the shafts and treasuries down in the deep places: they are
 * drowned in water--or in a shadow of fear.'
 */

/* TODO: Currently the file blocks allocation is not very sophisticated and
 * when the weather is bad it could probably have rather horrible results. */

#undef BLOCKS_DEBUG
#ifdef BLOCKS_DEBUG
#define BDEBUG(x...) fprintf(stderr, x)
#else
#define BDEBUG(x...)
#endif

/* Number of blocks in cache */
#define CACHE_LENGTH 64

/* Blocks for readahead */
#define FILE_READAHEAD  (CACHE_LENGTH/2)

#define file_block      hed_block
#define blockoff_t      hed_cursor_t

#define first_block(f) next_block(last_block(f))
#define prev_block(b) (tree_entry(prev_in_tree(&(b)->t),struct file_block,t))
#define next_block(b) (tree_entry(next_in_tree(&(b)->t),struct file_block,t))
#define last_block(f) (&(f)->eof_block)

#define block_offset(b)         tree_block_offset(&(b)->t)

#define recalc_block_recursive(b)       recalc_node_recursive(&(b)->t)

#define chain_block_before(tree,b,p) insert_into_tree((tree), &(b)->t, &(p)->t)
#define recalc_chain_block_before(tree,b,p) do { \
        chain_block_before((tree), (b), (p)); \
        recalc_block_recursive((b)); \
} while (0)

#define unchain_block(tree,b) del_from_tree((tree), &(b)->t)
#define recalc_unchain_block(tree,b) recalc_del_from_tree((tree), &(b)->t)

#define init_block_list(tree,b) init_tree(tree, &(b)->t)
#define init_block_link(b) init_node(&(b)->t)

#define find_block(tree,o)      tree_entry(find_in_tree((tree),(o)),struct file_block,t)

#define file_size       hed_file_size
#define file_blocks     hed_file_blocks

#ifdef HED_CONFIG_SWAP

/* Return the swp file object */
static inline struct swp_file *
file_swp(struct hed_file *file)
{
        return file->swp;
}

#else

/* Provide a stub for the non-swap case */
static inline void *
file_swp(struct hed_file *file)
{
        return NULL;
}

#endif

#ifdef HED_CONFIG_READAHEAD

#define file_ra_none(f)         ((f)->readahead == HED_RA_NONE)
#define file_ra_forward(f)      ((f)->readahead == HED_RA_FORWARD)
#define file_ra_backward(f)     ((f)->readahead == HED_RA_BACKWARD)

#else

#define file_ra_none(f)         (1)
#define file_ra_forward(f)      (0)
#define file_ra_backward(f)     (0)

#endif  /* HED_CONFIG_READAHEAD */

/* Get the physical offset of the byte immediately following @block. */
static inline hed_uoff_t
phys_end(const struct hed_block *block)
{
        return hed_block_is_inserted(block)
                ? block->phys_pos
                : block->phys_pos + hed_block_size(block);
}

static struct hed_block *
next_nonzero_block(struct hed_block *block)
{
        while (!hed_block_is_eof(block)) {
                block = next_block(block);
                if (hed_block_size(block))
                        return block;
        }
        return NULL;
}

static struct hed_block *
prev_nonzero_block(struct hed_block *block)
{
        do {
                block = prev_block(block);
                if (hed_block_is_eof(block))
                        return NULL;
        } while (!hed_block_size(block));
        return block;
}

bool
hed_block_is_after_erase(struct hed_block *block)
{
        struct hed_block *prev = prev_nonzero_block(block);
        return prev
                ? block->phys_pos > phys_end(prev)
                : !!block->phys_pos;
}

bool
hed_block_is_after_insert(struct hed_block *block)
{
        struct hed_block *prev = prev_nonzero_block(block);
        return prev && hed_block_is_inserted(prev);
}

#ifndef BLOCKS_DEBUG
# define dump_blocks(file)      {}
#else

static hed_uoff_t
block_phys_size(struct hed_file *file, struct file_block *block)
{
        struct file_block *next;

        if (hed_block_is_eof(block))
                return 0;
        next = next_block(block);
        return next->phys_pos - block->phys_pos;
}

static void
dump_block(int level, struct hed_file *file, struct hed_tree_node *node,
           hed_uoff_t *cur_offset, hed_uoff_t *cur_poffset)
{
        struct hed_block *block = tree_entry(node, struct hed_block, t);
        bool virtual = hed_block_is_virtual(block);
        unsigned char *p;
        hed_cursor_t *cur;
        char t[21] = "                    ";

        if (node->left)
                dump_block(level + 1, file, node->left, cur_offset, cur_poffset);
        p = hed_block_data(block);
        if (level < 20) t[level] = '>'; else t[19] = '.';
        fprintf(stderr, "%s [%06llx] [%06llx] %c%c%c %05llx %05llx"
                " {%02x%02x%02x%02x} -- %p ^%p [%06llx]\n",
                t,
                (unsigned long long) *cur_offset,
                (unsigned long long) *cur_poffset,
                virtual ? 'v' : ' ',
                hed_block_is_inserted(block) ? 'i' : ' ',
                hed_block_is_dirty(block) ? '*' : ' ',
                (unsigned long long) node->size,
                (unsigned long long) block_phys_size(file, block),
                p && block->t.size > 0 ? p[0] : 0,
                p && block->t.size > 1 ? p[1] : 0,
                p && block->t.size > 2 ? p[2] : 0,
                p && block->t.size > 3 ? p[3] : 0,
                node, node->up,
                (unsigned long long) node->cover_size
                );
        list_for_each_entry (cur, &block->refs, list) {
                fprintf(stderr, "  <%p>: %llx->%p:%llx\n",
                        cur, (long long)cur->pos,
                        cur->block, (unsigned long long)cur->off);
        }
        assert(*cur_poffset == block->phys_pos);
        *cur_offset += node->size;
        *cur_poffset += block_phys_size(file, block);
        if (node->right)
                dump_block(level + 1, file, node->right, cur_offset, cur_poffset);
        assert(node->cover_size == (node->left ? node->left->cover_size : 0)
                                    + (node->right ? node->right->cover_size : 0)
                                    + node->size);
}

/* Walk the tree manually here, because foreach_block() does not provide
 * the tree structure.
 * TODO: Change this if you plan to debug any other block containers.
 */
static void
dump_blocks(struct hed_file *file)
{
        struct file_block *first = first_block(file);
        hed_uoff_t cur_offset, cur_poffset;

        fprintf(stderr, "-- blocks dump --\n");
        cur_offset = 0;
        cur_poffset = first->phys_pos;
        dump_block(0, file, file_blocks(file)->root,
                   &cur_offset, &cur_poffset);
        fprintf(stderr, "-- blocks dump end --\n");
}
#endif

static void
get_cursor(struct hed_file *file, hed_uoff_t offset, hed_cursor_t *curs)
{
        struct file_block *block;

        block = find_block(file_blocks(file), offset);
        assert(block != NULL);
        curs->pos = offset;
        curs->block = block;
        curs->off = offset - block_offset(block);
        list_add(&curs->list, &block->refs);

        BDEBUG("Mapped %llx to %llx+%llx/%llx\n",
               offset, offset - curs->off, curs->off, block->t.size);
}

void
hed_get_cursor(struct hed_file *file, hed_uoff_t offset, hed_cursor_t *curs)
{
        get_cursor(file, offset, curs);
}

static inline void
put_cursor(hed_cursor_t *curs)
{
        list_del(&curs->list);
}

void
hed_put_cursor(hed_cursor_t *curs)
{
        put_cursor(curs);
}

void
hed_update_cursor(struct hed_file *file, hed_uoff_t offset, hed_cursor_t *curs)
{
        put_cursor(curs);
        get_cursor(file, offset, curs);
}

void
hed_dup_cursor(const hed_cursor_t *src, hed_cursor_t *dst)
{
        dst->pos = src->pos;
        dst->block = src->block;
        dst->off = src->off;
        list_add_tail(&dst->list, &src->block->refs);
}

void
hed_dup2_cursor(const hed_cursor_t *src, hed_cursor_t *dst)
{
        if (hed_is_a_cursor(dst))
                put_cursor(dst);
        hed_dup_cursor(src, dst);
}

/* Move cursors from @old to @new, adding @off to their block
 * offsets to keep them at the same position. */
static void
update_cursors(const struct hed_block *old, struct hed_block *new,
               hed_off_t off)
{
        hed_cursor_t *curs;

        BDEBUG("Updating cursors from <%p> to <%p>%c%llx\n",
               old, new, off >= 0 ? '+' : '-', off >= 0 ? off : -off);

        list_for_each_entry(curs, &old->refs, list) {
                curs->block = new;
                curs->off += off;
        }
}

/* Move cursors in the range <@start;@end> from @old to @new,
 * adding @off to their block offset, plus moving the reference list. */
static void
move_cursors(const struct hed_block *old, struct hed_block *new,
             hed_uoff_t start, hed_uoff_t end, hed_off_t off)
{
        hed_cursor_t *curs, *nextcurs;

        BDEBUG("Moving cursors from <%p>:%llx:%llx to <%p>%c%llx\n",
               old, start, end, new,
               off >= 0 ? '+' : '-', off >= 0 ? off : -off);

        list_for_each_entry_safe(curs, nextcurs, &old->refs, list)
                if (curs->off >= start && curs->off <= end) {
                        curs->block = new;
                        curs->off += off;
                        list_move(&curs->list, &new->refs);
                }
}

/* Move cursors in the range @block:<@start;@end> to @newpos */
static void
move_cursors_abs(const struct hed_block *block,
                 hed_uoff_t start, hed_uoff_t end,
                 const hed_cursor_t *newpos)
{
        hed_cursor_t *curs, *nextcurs;

        BDEBUG("Moving cursors from <%p>:%llx:%llx to <%p>:%llx\n",
               block, start, end, newpos->block, newpos->off);

        list_for_each_entry_safe(curs, nextcurs, &block->refs, list)
                if (curs->off >= start && curs->off <= end) {
                        curs->pos = newpos->pos;
                        curs->block = newpos->block;
                        curs->off = newpos->off;
                        list_move(&curs->list, &newpos->block->refs);
                }
}

/* Update the positions of cursors at and after @start for all
 * blocks starting at @block */
static void
slide_cursors(struct hed_file *file, const struct hed_block *block,
              hed_uoff_t start, hed_off_t off)
{
        hed_cursor_t *curs;
        const struct hed_block *nblock;

        BDEBUG("Sliding cursors >= %llx by %c%llx, starting at <%p>\n",
               start, off >= 0 ? '+' : '-', off >= 0 ? off : -off, block);
        nblock = block;
        do {
                block = nblock;
                list_for_each_entry(curs, &block->refs, list)
                        if (curs->pos >= start)
                                curs->pos += off;
                nblock = next_block(block);
        } while (!hed_block_is_eof(block));
}

static struct hed_block *
new_block(struct hed_file *file, long flags)
{
        struct file_block *new;

        if (! (new = swp_zalloc(file_swp(file), sizeof(struct file_block))) )
                return NULL;

        new->flags = flags;
        init_block_link(new);
        INIT_LIST_HEAD(&new->refs);
        if (flags & HED_BLOCK_EXCACHE)
                INIT_LIST_HEAD(&new->lru);
        else
                list_add_tail(&new->lru, &file->lru);

        return new;
}

static struct hed_block *
new_virt_block(struct hed_file *file, hed_uoff_t pos, hed_uoff_t size,
               long extraflags)
{
        struct hed_block *new =
                new_block(file, (HED_BLOCK_EXCACHE |
                                 HED_BLOCK_VIRTUAL |
                                 extraflags));
        if (!new)
                return NULL;

        new->t.size = size;
        new->phys_pos = pos;
        BDEBUG("Spawned new virtual block [%llx] at %llx\n", size, pos);
        return new;
}

static struct hed_block *
new_data_block(struct hed_file *file, hed_uoff_t pos, hed_uoff_t size,
               struct hed_block_data *dataobj)
{
        struct hed_block *new =
                new_block(file, 0);
        if (!new)
                return NULL;

        cache_get(dataobj);
        new->dataobj = dataobj;
        new->t.size = size;
        new->phys_pos = pos;
        new->dataoff = FILE_BLOCK_OFF(pos);
        BDEBUG("Spawned new data block [%llx] at %llx\n", size, pos);
        return new;
}

static void
file_free_block(struct hed_file *file, struct file_block *block)
{
        if (block->dataobj)
                cache_put(file->cache, block->dataobj);
        list_del(&block->lru);

        swp_free(file_swp(file), block);
}

static bool
kill_block_if_empty(struct hed_file *file, struct file_block *block)
{
        if (!hed_block_is_eof(block) && block->t.size == 0 &&
            list_empty(&block->refs)) {
                /* No recalculation needed, zero size. */
                unchain_block(file_blocks(file), block);
                file_free_block(file, block);
                return true;
        }
        return false;
}

/* This may kill the previous block as well, if it can be merged
 * with the next one. It will never kill anything which _follows_. */
static void
file_kill_block(struct hed_file *file, struct file_block *block)
{
        hed_uoff_t phys_pos = block->phys_pos;
        struct file_block *prev = prev_block(block);
        struct file_block *next = next_block(block);
        struct file_block *merger;
        bool killprev = false;

        /* We should never kill a dirty block! */
        assert(!hed_block_is_dirty(block));
        /* We shouldn't get with an empty block here (that might
         * need special considerations with virtualization). */
        assert(block->t.size > 0);

        if (!hed_block_is_eof(block) &&
            hed_block_is_inner_virtual(next) &&
            phys_pos + block->t.size == next->phys_pos) {
                if (!hed_block_is_eof(prev) &&
                    hed_block_is_inner_virtual(prev) &&
                    prev->phys_pos + prev->t.size == phys_pos)
                        killprev = true;
                merger = next;
                merger->phys_pos -= block->t.size;
                update_cursors(merger, merger, block->t.size);
                update_cursors(block, merger, 0);
        } else if (!hed_block_is_eof(prev) &&
                   hed_block_is_inner_virtual(prev) &&
                   prev->phys_pos + prev->t.size == phys_pos) {
                merger = prev;
                update_cursors(block, merger, merger->t.size);
        } else if (!hed_block_is_virtual(block)) {
                /* Convert physical to virtual */
                assert(block->dataobj);
                cache_put(file->cache, block->dataobj);
                block->dataobj = NULL;

                list_del_init(&block->lru); /* unlink the block from LRU */
                hed_block_set_excache(block); /* say it's unlinked */
                hed_block_set_virtual(block);
                return;
        } else
                /* Already virtual and cannot merge */
                return;

        list_splice(&block->refs, &merger->refs);

        /* Messing with block sizes and unchaining is a bit tricky
         * since unchain_block() can splay(). So we really need
         * to recalc_block_recursive() right after we update the size.
         * If this place turns out to be a hot-spot, we can optimize
         * the tree operations here. */
        merger->t.size += block->t.size;
        recalc_block_recursive(merger);

        /* Destroy the block */
        recalc_unchain_block(file_blocks(file), block);
        file_free_block(file, block);

        if (killprev)
                file_kill_block(file, prev);
}

static struct file_block *
split_block(struct hed_file *file, struct hed_block *block,
            hed_uoff_t splitpoint)
{
        struct file_block *next;

        next = new_block(file, block->flags);
        if (!next)
                return NULL;

        if ( (next->dataobj = block->dataobj) ) {
                cache_get(next->dataobj);
                next->dataoff = block->dataoff + splitpoint;
        } else
                assert(hed_block_is_virtual(block));

        next->t.size = block->t.size - splitpoint;
        next->phys_pos = block->phys_pos;
        if (!hed_block_is_inserted(block))
                next->phys_pos += splitpoint;

        block->t.size = splitpoint;
        recalc_block_recursive(block);
        recalc_chain_block_before(file_blocks(file), next, next_block(block));

        move_cursors(block, next, splitpoint, UOFF_MAX, -splitpoint);

        return next;
}

/* Replace a chunk in @block with @newblock */
static int
replace_chunk(struct hed_file *file, struct hed_block *block,
              hed_uoff_t offset, struct hed_block *newblock)
{
        size_t len = newblock->t.size;
        hed_uoff_t leadlen = offset + len;

        assert(offset < block->t.size);
        assert(len <= block->t.size - offset);

        /* Re-create the head block if necessary */
        if (offset) {
                struct file_block *head;

                head = new_block(file, block->flags & ~HED_BLOCK_EOF);
                if (!head)
                        return -1;
                head->t.size = offset;
                head->dataobj = block->dataobj;
                head->dataoff = block->dataoff;
                head->phys_pos = block->phys_pos;

                recalc_chain_block_before(hed_file_blocks(file),
                                          head, block);

                /* Move cursors to the head */
                move_cursors(block, head, 0, offset - 1, 0);
        }

        /* Move pointers to the new block */
        assert(leadlen > 0);
        move_cursors(block, newblock, offset, leadlen - 1, -offset);

        /* Shorten the tail block */
        block->t.size -= leadlen;
        block->dataoff += leadlen;
        assert(!hed_block_is_inserted(block));
        block->phys_pos += leadlen;
        recalc_block_recursive(block);
        move_cursors(block, block, leadlen, UOFF_MAX, -leadlen);

        /* Insert the new block */
        recalc_chain_block_before(file_blocks(file), newblock, block);

        /* Kill the leading block if possible */
        kill_block_if_empty(file, block);

        return 0;
}

#ifdef HED_CONFIG_SWAP

static char *
swp_filename(const char *filename)
{
        size_t fnlen = strlen(filename);
        char *swp;
        char *file;

        if (!(swp = malloc(fnlen + 9)) )
                return NULL;
        strcpy(swp, filename);

        file = strrchr(swp, '/');
        file = file ? file + 1 : swp;
        *file = '.';
        strcpy(stpcpy(file + 1, filename + (file -swp)), ".hedswp");
        return swp;
}

static char *
newswp_filename(char *swpname)
{
        char *ret, *p;

        ret = swpname;
        while (!access(ret, F_OK)) {
                if (ret == swpname) {
                        if (! (ret = strdup(swpname)) )
                                return NULL;
                        p = ret + strlen(ret) - 1;
                }

                if (*p == 'a') {
                        free(ret);
                        return NULL;
                }
                --*p;
        }
        return ret;
}

int
hed_file_remove_swap(struct hed_file *file)
{
        if (remove(file->swpname))
                return -1;
        if (rename(file->newswpname, file->swpname))
                return -1;

        free(file->newswpname);
        file->newswpname = file->swpname;
        return 0;
}

static inline struct hed_file *
file_swp_init(const char *name)
{
        char *swpname, *newswpname;
        struct swp_file *swp;
        struct hed_file *file;

        swpname = swp_filename(name);
        if (!swpname)
                goto fail;
        newswpname = newswp_filename(swpname);
        if (!newswpname)
                goto fail_free_name;
        swp = swp_init_write(newswpname);
        if (!swp)
                goto fail_free_newname;

        assert(sizeof(struct swp_header) + sizeof(struct hed_file)
               <= FILE_BLOCK_SIZE);
        file = swp_private(swp);
        memset(file, 0, sizeof *file);

        file->swp = swp;
        file->swpname = swpname;
        file->newswpname = newswpname;

        return file;

 fail_free_newname:
        free(newswpname);
 fail_free_name:
        if (swpname != newswpname)
                free(swpname);
 fail:
        return NULL;
}

static inline void
file_swp_done(struct hed_file *file)
{
        remove(file->newswpname);
        if (file->newswpname != file->swpname)
                free(file->newswpname);
        free(file->swpname);
        swp_done(file_swp(file));
        /* file was de-allocated automatically with file->swp */
}

#else  /* HED_CONFIG_SWAP */

static inline struct hed_file *
file_swp_init(const char *name)
{
        return calloc(1, sizeof(struct hed_file));
}

static inline void
file_swp_done(struct hed_file *file)
{
}

#endif  /* HED_CONFIG_SWAP */

static inline struct stat *
file_stat(struct hed_file *file)
{
        return &file->s;
}

int
hed_file_update_size(struct hed_file *file)
{
        hed_uoff_t oldsize = file->phys_size;

        if(fstat(file->fd, file_stat(file)) < 0)
                return -1;

        if (S_ISBLK(file_stat(file)->st_mode)) {
                if (ioctl(file->fd, BLKGETSIZE64, &file->phys_size)) {
                        unsigned long size_in_blocks;
                        if (ioctl(file->fd, BLKGETSIZE, &size_in_blocks))
                                return -1;
                        file->phys_size = (hed_uoff_t)size_in_blocks << 9;
                }
        } else if (S_ISREG(file_stat(file)->st_mode)) {
                file->phys_size = file_stat(file)->st_size;
        } else if (S_ISCHR(file_stat(file)->st_mode)) {
                if (lseek(file->fd, 0, SEEK_SET) < 0)
                        return -1;
                file->phys_size = (hed_uoff_t)OFF_MAX + 1;
        } else {
                errno = EINVAL;
                return -1;
        }

        file->size += file->phys_size - oldsize;
        return 0;
}

static int
do_file_open(struct hed_file *file)
{
        file->fd = open(file->name, O_RDONLY);
        if (file->fd < 0) {
                if (errno != ENOENT)
                        return errno;
                fprintf(stderr, "Warning: File %s does not exist\n",
                        file->name);
                memset(file_stat(file), 0, sizeof(struct stat));

        } else if (hed_file_update_size(file)) {
                int errsv = errno;
                close(file->fd);
                return errsv;
        }
        return 0;
}

static int
file_setup_blocks(struct hed_file *file)
{
        hed_uoff_t phys_size = file->phys_size;
        struct file_block *block;

        block = &file->eof_block;
        block->flags =  HED_BLOCK_EXCACHE | HED_BLOCK_VIRTUAL | HED_BLOCK_EOF;
        INIT_LIST_HEAD(&block->lru);
        INIT_LIST_HEAD(&block->refs);
        block->t.size = OFF_MAX - phys_size + 1;
        block->phys_pos = phys_size;

        init_block_list(file_blocks(file), block);

        if (phys_size) {
                block = new_virt_block(file, 0, phys_size, 0);
                if (!block)
                        return -1;
                recalc_chain_block_before(file_blocks(file), block,
                                          &file->eof_block);
        }

        return 0;
}

int
libhed_init(void)
{
        return file_access_init();
}

struct hed_file *
hed_open(const char *name)
{
        struct hed_file *file;

        if (! (file = file_swp_init(name)) )
                goto fail;

        file->name = name;

        file->cache = cache_init(CACHE_LENGTH, file_swp(file));
        if (!file->cache)
                goto fail_file;
        INIT_LIST_HEAD(&file->lru);

        if (do_file_open(file))
                goto fail_file;

        if (file_setup_blocks(file))
                goto fail_file;

        fixup_register(file);

        return file;

 fail_file:
        hed_close(file);
 fail:
        return NULL;
}

void
hed_close(struct hed_file *file)
{
        assert(file);

        /* Do not check for errors:
         *  1. This FD is read-only => no data loss possbile
         *  2. We're about to exit anyway => no resource leak
         */
        if (file->fd >= 0)
                close(file->fd);

        fixup_deregister(file);

        /* No need to free file blocks here, because all data is
         * allocated either from the cache or from the swap file
         * and both is going to be destroyed now.
         */

        if (file->cache)
                cache_done(file->cache);

        file_swp_done(file);
}

/* Adjust a cursor after off gets outside its block */
static void
fixup_cursor_slow(hed_cursor_t *curs)
{
        struct file_block *block = curs->block;
        hed_uoff_t off = curs->off;

        do {
                if ((hed_off_t)off < 0) {
                        block = prev_block(block);
                        off += block->t.size;
                } else {
                        off -= block->t.size;
                        block = next_block(block);
                }
        } while (off >= block->t.size);

        curs->block = block;
        curs->off = off;
        list_move(&curs->list, &block->refs);
}

/* Adjust a cursor if off gets outside its block.
 * This is separate from fixup_cursor_slow, because it is supposed
 * to be small enough to be inlined (which is a win, because most of
 * the time no fixup has to be done, so the fast inlined path is used).
 */
static inline void
fixup_cursor(hed_cursor_t *curs)
{
        if (curs->off >= curs->block->t.size)
                fixup_cursor_slow(curs);
}

hed_off_t
hed_move_relative(hed_cursor_t *curs, hed_off_t num)
{
        hed_off_t newpos = curs->pos + num;
        if (newpos < 0) {
                newpos = num < 0 ? 0 : OFF_MAX;
                num = newpos - curs->pos;
        }
        curs->pos = newpos;
        curs->off += num;
        fixup_cursor(curs);
        return num;
}

/* Relative move with no checking (and only by a small amount) */
static inline void
move_rel_fast(hed_cursor_t *curs, ssize_t num)
{
        curs->off += num;
        curs->pos += num;
        fixup_cursor(curs);
}

static void
alloc_caches(struct hed_file *file, struct hed_block_data **caches, int n)
{
        struct remap_control rc;
        int i;

        BDEBUG("Allocate %d caches (%d free slots available)\n",
               n, file->cache->nfree);

        assert(n <= CACHE_LENGTH);
        while (file->cache->nfree < n) {
                struct file_block *block;

                assert(!list_empty(&file->lru));
                block = list_entry(file->lru.next, struct file_block, lru);
                BDEBUG("Killing block at physical %llx\n", block->phys_pos);
                file_kill_block(file, block);
        }

        for (i = 0; i < n; ++i) {
                caches[i] = cache_alloc(file->cache);
                assert(caches[i]);
        }

        remap_init(&rc);
        remap_compact(&rc, file->cache, caches, n);
        for (i = 0; i < n; ++i)
                remap_add(&rc, caches[i]->data);
        remap_finish(&rc);
}

static inline void
free_caches(struct hed_file *file, struct hed_block_data **preload, int n)
{
        int i;

        for (i = 0; i < n; ++i)
                if (preload[i])
                        cache_put(file->cache, preload[i]);
}

static int
file_load_data(struct hed_file *file,
               struct hed_block_data **caches, int n,
               hed_uoff_t offset)
{
        struct hed_block_data *dataobj = caches[0];
        void *data = dataobj->data;
        ssize_t rsize, total, segsize;

        segsize = n << FILE_BLOCK_SHIFT;
        for (total = 0; total < segsize; total += rsize) {
                rsize = pread(file->fd, data + total,
                              segsize - total, offset + total);
                if (!rsize)
                        break;
                if (rsize < 0) {
                        dataobj = caches[total >> FILE_BLOCK_SHIFT];
                        caches[total >> FILE_BLOCK_SHIFT] = NULL;
                        data = dataobj->data;
                        cache_put(file->cache, dataobj);
                        total = FILE_BLOCK_ROUND(total);
                        rsize = FILE_BLOCK_SIZE;
                        BDEBUG("Error reading block at phys %llx: %s\n",
                               offset + total, strerror(errno));
                } 
        }

        BDEBUG("Loaded data at phys %llx up to %llx\n",
               offset, offset + segsize);
        return 0;
}

#ifdef HED_CONFIG_MMAP

static int
file_load_data_mmap(struct hed_file *file,
                    struct hed_block_data **caches, int n,
                    hed_uoff_t offset)
{
        void *data;
        ssize_t segsize;
        int i;

        segsize = n << FILE_BLOCK_SHIFT;
        data = mmap(NULL, segsize,
                    PROT_READ | PROT_WRITE,
                    MAP_PRIVATE | (file->fd < 0 ? MAP_ANONYMOUS : 0),
                    file->fd, offset);

        if (data == MAP_FAILED) {
                BDEBUG("mmap failed at %llx: fail over to traditional read\n",
                        offset);

                data = mmap(NULL, segsize,
                            PROT_READ | PROT_WRITE,
                            MAP_PRIVATE | MAP_ANONYMOUS,
                            0, 0);
                if (data == MAP_FAILED)
                        return -1;

                for (i = 0; i < n; ++i)
                        caches[i]->data = data + (i << FILE_BLOCK_SHIFT);
                return file_load_data(file, caches, n, offset);
        }

        for (i = 0; i < n; ++i)
                caches[i]->data = data + (i << FILE_BLOCK_SHIFT);

        BDEBUG("Loaded data at phys %llx up to %llx\n",
               offset, offset + segsize);
        return 0;
}
# define file_load_data file_load_data_mmap

#endif

/* Find the block with the lowest physical position that intersects
 * the loaded segment. The search starts at @block.
*/
static struct hed_block *
first_load_block(struct hed_tree *tree, struct hed_block *block,
                 hed_uoff_t segstart)
{
        struct hed_block *prev = block;
        do {
                block = prev;
                prev = prev_block(prev);
        } while (!hed_block_is_eof(prev) && phys_end(prev) > segstart);
        return block;
}

static int
load_blocks(struct hed_file *file, const blockoff_t *from)
{
        hed_uoff_t physpos, segstart;
        struct hed_block_data *preload[FILE_READAHEAD];
        size_t ra_bkw, ra_fwd, ra_off;
        hed_cursor_t pos;
        int nblocks;

        segstart = hed_cursor_phys_pos(from);
        ra_bkw = FILE_BLOCK_OFF(segstart);
        ra_fwd = FILE_BLOCK_SIZE - ra_bkw;

        if (file_ra_forward(file))
                ra_fwd += (FILE_READAHEAD - 1) << FILE_BLOCK_SHIFT;
        else if (file_ra_backward(file))
                ra_bkw += (FILE_READAHEAD - 1) << FILE_BLOCK_SHIFT;

        if (ra_bkw > segstart)
                ra_bkw = segstart;
        if (ra_fwd > file->phys_size - segstart)
                ra_fwd = file->phys_size - segstart;

        segstart -= ra_bkw;
        ra_fwd += ra_bkw;
        pos.block = first_load_block(file_blocks(file), from->block, segstart);
        pos.off = segstart >= pos.block->phys_pos
                ? segstart - pos.block->phys_pos
                : 0;

        list_add(&pos.list, &pos.block->refs);
        nblocks = ((ra_fwd - 1) >> FILE_BLOCK_SHIFT) + 1;
        alloc_caches(file, preload, nblocks);
        put_cursor(&pos);

        if (file_load_data(file, preload, nblocks, segstart)) {
                free_caches(file, preload, nblocks);
                return -1;
        }

        while (physpos = hed_cursor_phys_pos(&pos),
               ra_off = physpos - segstart,
               ra_off < ra_fwd) {
                struct hed_block_data *dataobj;
                struct hed_block *newblock;
                size_t datalen;

                if (!hed_block_is_virtual(pos.block)) {
                        pos.block = next_block(pos.block);
                        pos.off = 0;
                        continue;
                }

                datalen = FILE_BLOCK_SIZE - FILE_BLOCK_OFF(physpos);
                if (datalen > hed_block_size(pos.block) - pos.off)
                        datalen = hed_block_size(pos.block) - pos.off;

                dataobj = preload[ra_off >> FILE_BLOCK_SHIFT];
                newblock = dataobj
                        ? new_data_block(file, physpos, datalen, dataobj)
                        : new_virt_block(file, physpos, datalen,
                                         HED_BLOCK_BAD);

                /* Punch the new block */
                BDEBUG("Add %s block at %llx, length %llx\n",
                       hed_block_is_virtual(newblock) ? "error" : "physical",
                       newblock->phys_pos, newblock->t.size);
                if (replace_chunk(file, pos.block, pos.off, newblock)) {
                        file_free_block(file, newblock);
                        free_caches(file, preload, nblocks);
                        return -1;
                }

                pos.block = next_block(newblock);
                pos.off = 0;
        }

        /* All cache objects now have an extra reference from the
         * allocation.  Drop it.  */
        free_caches(file, preload, nblocks);

        dump_blocks(file);
        return 0;
}

/* Shorten a block at beginning and enlarge the preceding block.
 *
 * Re-allocate at most @len bytes from the beginning of @block to the
 * end of the preceding block.
 * If @block is virtual, this will effectively devirtualize the range.
 * If @block is not virtual, this will change the backing store of
 * the bytes in the range.
 * Returns: the number of bytes actually moved.
 */
static size_t
shrink_at_begin(struct hed_file *file, struct file_block *block,
                size_t len, long state)
{
        struct file_block *prev = prev_block(block);
        size_t maxgrow;

        /* Basic assumptions */
        assert(!(state & HED_BLOCK_VIRTUAL));

        /* The previous block must exist: */
        if (hed_block_is_eof(prev))
                return 0;

        /* The block flags must match the requested @state: */
        if ((prev->flags & HED_BLOCK_STATEMASK) != state)
                return 0;

        /* No deletions at end, or similar: */
        if (prev->phys_pos + prev->t.size != block->phys_pos)
                return 0;

        /* Append less bytes than requested if not all are available */
        assert(prev->t.size <= prev->dataobj->size);
        maxgrow = prev->dataobj->size - prev->dataoff - prev->t.size;
        if (len > maxgrow)
                len = maxgrow;
        if (!len)
                return 0;

        BDEBUG("Appending 0:%lx to the previous block\n", len);

        /* Move cursors away from the to-be-chopped beginning */
        move_cursors(block, prev, 0, len - 1, prev->t.size);

        /* Enlarge the previous block */
        prev->t.size += len;
        recalc_block_recursive(prev);

        /* Shorten the original block */
        block->t.size -= len;
        block->dataoff += len;
        block->phys_pos += len;
        recalc_block_recursive(block);
        return len;
}

/* Shorten a block at end and enlarge the following block.
 *
 * Re-allocate at most @len bytes from the end of @block to the
 * beginning of the following block.
 * If @block is virtual, this will effectively devirtualize the range.
 * If @block is not virtual, this will change the backing store of
 * the bytes in the range.
 * Returns: the number of bytes actually moved.
 */
static size_t
shrink_at_end(struct hed_file *file, struct file_block *block,
              size_t len, long state)
{
        struct file_block *next = next_block(block);
        hed_uoff_t off;

        /* Basic assumptions */
        assert(!(state & HED_BLOCK_VIRTUAL));

        /* The next block must exist: */
        if (hed_block_is_eof(block))
                return 0;

        /* The block flags must match the requested @state: */
        if ((next->flags & HED_BLOCK_STATEMASK) != state)
                return 0;

        /* No deletions at end, or similar: */
        if (block->phys_pos + block->t.size != next->phys_pos)
                return 0;

        /* Prepend less bytes than requested if not all are available */
        if (len > next->dataoff)
                len = next->dataoff;
        if (!len)
                return 0;
        off = block->t.size - len;

        BDEBUG("Prepending %llx:%lx to the next block\n", off, len);

        /* Shift cursors in the new physical block */
        update_cursors(next, next, len);

        /* Move cursors away from the to-be-chopped end */
        move_cursors(block, next, off, UOFF_MAX, -off);

        /* Enlarge the next block */
        next->dataoff -= len;
        next->phys_pos -= len;
        next->t.size += len;
        recalc_block_recursive(next);

        /* Shorten the original block */
        block->t.size -= len;
        recalc_block_recursive(block);
        return len;
}

/* Search for an existing data object within the same physical block
 * as @curs, and having the given @state flags.
 */
static struct hed_block_data *
search_data(struct hed_file *file, const hed_cursor_t *curs, long state)
{
        struct file_block *block;
        hed_uoff_t physpos;

        physpos = FILE_BLOCK_ROUND(curs->block->phys_pos + curs->off);
        BDEBUG("Search for already loaded data at %llx starting at %llx...",
               physpos, curs->block->phys_pos);

        /* Search backwards */
        block = curs->block;
        while (!hed_block_is_eof(block = prev_block(block))) {
                if (block->phys_pos < physpos)
                        break;
                if ((block->flags & HED_BLOCK_STATEMASK) == state) {
                        BDEBUG(" found at %llx\n", block->phys_pos);
                        assert(block->dataobj);
                        return block->dataobj;
                }
        }

        /* Search forwards */
        block = curs->block;
        while (!hed_block_is_eof(block)) {
                block = next_block(block);
                if (block->phys_pos >= physpos + FILE_BLOCK_SIZE)
                        break;
                if ((block->flags & HED_BLOCK_STATEMASK) == state) {
                        BDEBUG(" found at %llx\n", block->phys_pos);
                        assert(block->dataobj);
                        return block->dataobj;
                }
        }

        BDEBUG(" not found\n");
        return NULL;
}

static int
reuse_loaded_data(struct hed_file *file, const blockoff_t *blockoff,
                  struct hed_block_data *data)
{
        struct file_block *physblock;
        struct file_block *block = blockoff->block;
        hed_uoff_t block_offset = blockoff->off;
        hed_uoff_t physpos = block->phys_pos + block_offset;
        size_t part = FILE_BLOCK_OFF(physpos);
        size_t len =
                FILE_BLOCK_SIZE - part <= block->t.size - block_offset
                ? FILE_BLOCK_SIZE - part
                : block->t.size - block_offset;

        if (part > block_offset)
                part = block_offset;
        physpos -= part;
        len += part;
        block_offset -= part;

        if (! (physblock = new_data_block(file, physpos, len, data)) )
                return -1;

        BDEBUG("Add physical block at %llx, length %llx\n",
               physblock->phys_pos, physblock->t.size);
        if (replace_chunk(file, block, block_offset, physblock)) {
                file_free_block(file, physblock);
                return -1;
        }

        dump_blocks(file);
        return 0;
}

/* Replace a part of a virtual block with content loaded
 * from disk. The amount of data loaded from the disk depends
 * on various factors with the goal to choose the most efficient
 * ratio. The only guarantee is that the byte at @blockoff will
 * be in a non-virtual block when this function returns 0.
 */
static int
devirtualize_clean(struct hed_file *file, const blockoff_t *blockoff)
{
        struct file_block *block = blockoff->block;
        hed_uoff_t block_offset = blockoff->off;
        hed_uoff_t remain = block->t.size - block_offset;
        struct hed_block_data *data;

        BDEBUG("punch a clean hole at %llx into %llx:%llx\n", block_offset,
               block_offset(block), block->t.size);
        assert(hed_block_is_virtual(block));

        /* Check if we can combine with a neighbouring block */
        if (shrink_at_begin(file, block, SIZE_MAX, 0) > block_offset ||
            shrink_at_end(file, block, SIZE_MAX, 0) >= remain) {
                kill_block_if_empty(file, block);
                dump_blocks(file);
                return 0;
        }

        /* Check if the block is already loaded elsewhere */
        data = search_data(file, blockoff, 0);
        return data
                ? reuse_loaded_data(file, blockoff, data)
                : load_blocks(file, blockoff);
}

/* Replace at most @len bytes of a virtual block with a newly
 * allocated out-of-cache block. The block is marked dirty
 * and its data is left uninitialized.
 * If the block at @blockoff is not virtual, make it dirty.
 * Note that this function may devirtualize less than @len bytes.
 * In the worst case only 1 byte at @blockoff will be available.
 */
static int
prepare_modify(struct hed_file *file, blockoff_t *blockoff, size_t len)
{
        struct file_block *block = blockoff->block;
        hed_uoff_t block_offset = blockoff->off;
        hed_uoff_t remain = block->t.size - block_offset;
        struct file_block *newblock;

        if (hed_block_is_dirty(block))
                return 0;

        if (len > remain)
                len = remain;

        BDEBUG("punch a dirty hole at %llx:%lx into %llx:%llx\n",
               block_offset, len,
               block_offset(block), block->t.size);

        /* Check if we can combine with a neighbouring block */
        if ((block_offset == 0 &&
             shrink_at_begin(file, block, len, HED_BLOCK_DIRTY)) ||
            (remain == len &&
             shrink_at_end(file, block, len, HED_BLOCK_DIRTY) >= len)) {
                kill_block_if_empty(file, block);
                dump_blocks(file);
                return 0;
        }

        /* Initialize a new block */
        newblock = new_block(file, HED_BLOCK_EXCACHE | HED_BLOCK_DIRTY);
        if (!newblock)
                goto out_err;

        /* Allocate data */
        if ( (newblock->dataobj = search_data(file, blockoff,
                                              HED_BLOCK_DIRTY)) )
                cache_get(newblock->dataobj);
        else if (! (newblock->dataobj = block_data_new(file->cache,
                                                       FILE_BLOCK_SIZE)) )
                goto out_err_free;

        newblock->phys_pos = block->phys_pos + block_offset;
        newblock->dataoff = FILE_BLOCK_OFF(newblock->phys_pos);
        if (len > FILE_BLOCK_SIZE - newblock->dataoff)
                len = FILE_BLOCK_SIZE - newblock->dataoff;
        newblock->t.size = len;

        if (replace_chunk(file, block, block_offset, newblock))
                goto out_err_free;

        dump_blocks(file);
        return 0;

 out_err_free:
        file_free_block(file, newblock);
 out_err:
        return -1;
}

/* Ensure that @curs points to an up-to-date non-virtual block.
 * Load the data from disk if necessary, return zero on failure. */
size_t
hed_prepare_read(struct hed_file *file, const hed_cursor_t *curs, size_t len)
{
        struct file_block *block = curs->block;
        if (hed_block_is_inner_virtual(block) &&
            devirtualize_clean(file, curs) < 0)
                return 0;

        return hed_cursor_chunk_len(curs, len);
}

/* Move the block pointer to the next block */
static struct hed_block *
cursor_next_block(hed_cursor_t *curs)
{
        struct hed_block *block = next_nonzero_block(curs->block);

        if (block) {
                curs->block = block;
                curs->off = 0;
                list_move(&curs->list, &block->refs);
        }
        return block;
}

/* This is an optimized way of doing:
 *
 *   hed_move_relative(curs, curs->block->t.size);
 *
 * for the case when curs->off == 0.
 */
static struct hed_block *
move_to_next(hed_cursor_t *curs)
{
        curs->pos += hed_block_size(curs->block);
        return cursor_next_block(curs);
}

/* Copy in @count bytes from @pos.
 * Returns the number of bytes that were not read (i.e. zero on success).
 * The @pos blockoff is moved by the amount of data read.
 * CAUTION: If you read up to MAX_BLOCKOFF, then @pos points one byte
 *          beyond the EOF block upon return.
 */
static size_t
copy_in(struct hed_file *file, void *buf, size_t count, blockoff_t *pos)
{
        size_t cpylen;

        pos->pos += count;
        while (count && (cpylen = hed_prepare_read(file, pos, count))) {
                if (hed_block_is_virtual(pos->block))
                        memset(buf, 0, cpylen);
                else
                        memcpy(buf, hed_cursor_data(pos), cpylen);

                buf += cpylen;
                count -= cpylen;
                if ( (pos->off += cpylen) >= hed_block_size(pos->block) )
                        if (!cursor_next_block(pos))
                                break;
        }
        pos->pos -= count;
        return count;
}

size_t
hed_file_cpin(struct hed_file *file, void *buf, size_t count,
              const hed_cursor_t *pos)
{
        blockoff_t mypos;
        size_t ret;

        hed_dup_cursor(pos, &mypos);
        ret = copy_in(file, buf, count, &mypos);
        put_cursor(&mypos);
        return ret;
}

/* Set the modified flag */
static inline void
set_modified(struct hed_file *file)
{
        file->modified = true;
}

/* Clear the modified flag */
static inline void
clear_modified(struct hed_file *file)
{
        file->modified = false;
}

int
hed_file_set_byte(struct hed_file *file, blockoff_t *blockoff,
                  unsigned char byte)
{
        hed_uoff_t offset = blockoff->pos;

        if (prepare_modify(file, blockoff, 1))
                return -1;
        set_modified(file);

        if (offset >= file->size)
                file->size = offset + 1;

        hed_block_data(blockoff->block)[blockoff->off] = byte;
        return 0;
}

size_t
hed_file_set_block(struct hed_file *file, blockoff_t *blockoff,
                   unsigned char *buf, size_t len)
{
        while (len) {
                size_t span;

                if (prepare_modify(file, blockoff, len))
                        break;
                set_modified(file);

                span = hed_cursor_chunk_len(blockoff, len);
                memcpy(hed_cursor_data(blockoff), buf, span);
                buf += span;
                len -= span;
                move_rel_fast(blockoff, span);
        }
        if (blockoff->pos > file->size)
                file->size = blockoff->pos;

        return len;
}

hed_uoff_t
hed_file_set_bytes(struct hed_file *file, blockoff_t *blockoff,
                   unsigned char byte, hed_uoff_t rep)
{
        while (rep) {
                size_t span;

                if (prepare_modify(file, blockoff, rep))
                        break;
                set_modified(file);

                span = hed_cursor_chunk_len(blockoff, rep);
                memset(hed_cursor_data(blockoff), byte, span);
                rep -= span;
                move_rel_fast(blockoff, span);
        }
        if (blockoff->pos > file->size)
                file->size = blockoff->pos;

        return rep;
}

static int
file_erase_continuous(struct hed_file *file, blockoff_t *blockoff, size_t len)
{
        struct file_block *block = blockoff->block;
        hed_uoff_t block_offset = blockoff->off;

        /* Find the new position */
        hed_move_relative(blockoff, len);

        /* Move all other cursors in the erased range to the new position */
        assert(len > 0);
        move_cursors_abs(block, block_offset,
                         block_offset + len - 1, blockoff);

        if (!block_offset) {
                block->dataoff += len;
                if (!hed_block_is_inserted(block))
                        block->phys_pos += len;
        } else if (block_offset + len < block->t.size &&
                   !split_block(file, block, block_offset + len))
                return -1;

        move_cursors(block, block, block_offset, UOFF_MAX, -(hed_uoff_t)len);

        block->t.size -= len;
        recalc_block_recursive(block);

        kill_block_if_empty(file, block);
        return 0;
}

size_t
hed_file_erase_block(struct hed_file *file, blockoff_t *blockoff,
                     hed_uoff_t len)
{
        hed_uoff_t offset;
        hed_uoff_t todo;

        offset = blockoff->pos;
        if (offset > file_size(file))
                return 0;
        else if (len > file_size(file) - offset)
                len = file_size(file) - offset;

        todo = len;
        while (todo) {
                size_t span = hed_cursor_chunk_len(blockoff, todo);

                if (file_erase_continuous(file, blockoff, span))
                        break;

                todo -= span;
        }
        len -= todo;

        file->size -= len;
        set_modified(file);

        file->eof_block.t.size += len;
        recalc_block_recursive(&file->eof_block);

        struct hed_block *slideblock = prev_block(blockoff->block);
        if (hed_block_is_eof(slideblock))
                slideblock = blockoff->block;
        slide_cursors(file, slideblock, blockoff->pos, -len);

        return todo;
}

int
hed_file_insert_begin(struct hed_file *file, const hed_cursor_t *curs,
                      hed_cursor_t *curs_ins)
{
        struct file_block *block, *newblock;

        BDEBUG("Starting insert at %llx\n", curs->pos);

        newblock = new_block(file,
                             HED_BLOCK_EXCACHE | HED_BLOCK_INSERTED);
        if (!newblock)
                return -1;

        newblock->phys_pos = hed_cursor_phys_pos(curs);
        newblock->dataobj = block_data_new(file->cache, FILE_BLOCK_SIZE);
        if (!newblock->dataobj) {
                file_free_block(file, newblock);
                return -1;
        }

        block = curs->block;
        if (curs->off) {
                block = split_block(file, block, curs->off);
                if (!block) {
                        file_free_block(file, newblock);
                        return -1;
                }
        }

        chain_block_before(file_blocks(file), newblock, block);

        curs_ins->pos = curs->pos;
        curs_ins->off = newblock->t.size;
        curs_ins->block = newblock;
        list_add(&curs_ins->list, &newblock->refs);

        dump_blocks(file);
        return 0;
}

void
hed_file_insert_end(struct hed_file *file, blockoff_t *blockoff_ins)
{
        struct file_block *block = blockoff_ins->block;

        BDEBUG("End insert at %llx\n", blockoff_ins->pos);

        blockoff_ins->block = NULL;
        list_del(&blockoff_ins->list);
        if (!kill_block_if_empty(file, block))
                block_data_shrink(file->cache, block->dataobj,
                                  block->dataoff + block->t.size);

        dump_blocks(file);
}

static void
insert_block(struct hed_file *file, blockoff_t *blockoff,
             unsigned char *buf, size_t len)
{
        struct file_block *block = blockoff->block;
        hed_uoff_t offset = blockoff->pos;

        assert(file && offset >= 0);

        assert(hed_block_is_excache(block));
        hed_block_set_dirty(block);
        set_modified(file);

        memcpy(hed_block_data(block) + blockoff->off, buf, len);
        block->t.size += len;
        recalc_block_recursive(block);
        blockoff->off += len;
        blockoff->pos += len;

        if (blockoff->pos > file->size)
                file->size = blockoff->pos;
        else
                file->size += len;

        slide_cursors(file, next_block(block), offset, len);
}

size_t
hed_file_insert_block(struct hed_file *file, blockoff_t *blockoff,
                      unsigned char *buf, size_t len)
{
        while (len) {
                struct file_block *block = blockoff->block;
                size_t remain = block->dataobj->size - blockoff->off;

                if (!remain) {
                        list_del(&blockoff->list);
                        blockoff->block = next_block(block);
                        blockoff->off = 0;

                        if (!hed_file_insert_begin(file, blockoff, blockoff))
                                continue;

                        blockoff->block = block;
                        blockoff->off = block->t.size;
                        list_add(&blockoff->list, &block->refs);
                        break;
                }

                if (remain > len)
                        remain = len;

                BDEBUG("Append %ld bytes to the insert block\n",
                       (long) remain);
                insert_block(file, blockoff, buf, remain);
                buf += remain;
                len -= remain;
        }
        return len;
}

int
hed_file_insert_byte(struct hed_file *file, blockoff_t *blockoff,
                     unsigned char byte)
{
        return hed_file_insert_block(file, blockoff, &byte, 1);
}

size_t
hed_file_insert_once(struct hed_file *file, blockoff_t *blockoff,
                     unsigned char *buf, size_t len)
{
        blockoff_t insert;

        if (!hed_file_insert_begin(file, blockoff, &insert)) {
                len = hed_file_insert_block(file, &insert, buf, len);
                hed_file_insert_end(file, &insert);
        }
        return len;
}

struct commit_control {
        struct hed_file *file;
        int wfd;                /* file descriptor for writing */
        int needwrite;          /* non-zero if write is needed */
        blockoff_t begoff, endoff;
        hed_off_t shift;
        void *partbuf;          /* allocated 3*FILE_BLOCK_SIZE  */
        void *partial;          /* pointer into partbuf */
};

/* Get the logical<->physical shift value after the specified block.
 * It is essential to get the value _AFTER_ the block, because the
 * shift value is used to decide how the current block will be handled.
 */
static hed_off_t
get_shift(const blockoff_t *blockoff)
{
        struct file_block *block = blockoff->block;
        size_t curshift = hed_block_is_inserted(block) ? block->t.size : 0;
        return curshift +
                blockoff->pos - blockoff->off - block->phys_pos;
}

static void
switch_partial(struct commit_control *cc)
{
        cc->partial += FILE_BLOCK_SIZE;
        if (cc->partial >= cc->partbuf + 3*FILE_BLOCK_SIZE)
                cc->partial = cc->partbuf;
}

/* Write @writelen bytes from the partial buffer at @cc->begoff. */
static int
commit_block(struct commit_control *cc, size_t len)
{
        ssize_t written;

        assert(len > 0);
        BDEBUG(" -> write %lx bytes at %llx\n",
               (unsigned long)len, cc->begoff.pos - len);
        written = pwrite(cc->wfd, cc->partial, len, cc->begoff.pos - len);
        if (written < len)
                /* TODO: keep data in a new list of dirty blocks */
                return -1;
        return 0;
}

static int
commit_partial(struct commit_control *cc)
{
        size_t partoff, remain, left;
        size_t writelen;

        partoff = FILE_BLOCK_OFF(cc->begoff.pos);
        remain = FILE_BLOCK_SIZE - partoff;
        if (remain > cc->endoff.pos - cc->begoff.pos)
                remain = cc->endoff.pos - cc->begoff.pos;
        if ((writelen = partoff + remain) == 0)
                return 0;

        BDEBUG("Fill partial %llx-%llx\n",
               cc->begoff.pos, cc->begoff.pos + remain);

        left = copy_in(cc->file, cc->partial + partoff, remain, &cc->begoff);
        if (left) {
                hed_move_relative(&cc->begoff, left);
                return -1;
        }

        if (FILE_BLOCK_OFF(cc->begoff.pos) &&
            !hed_block_is_eof(cc->begoff.block))
                return 0;

        return commit_block(cc, writelen);
}

/* Commit forwards.
 * Beware, cc->begoff is undefined upon return!
 */
static int
commit_forwards(struct commit_control *cc)
{
        hed_uoff_t endpos = cc->endoff.pos;
        int ret = 0;

        BDEBUG("Writing forwards %llx-%llx\n",
               cc->begoff.pos, cc->endoff.pos);

        if (!cc->needwrite)
                return 0;

        while (cc->begoff.pos < endpos)
                ret |= commit_partial(cc);

        return ret;
}

/* Commit forwards.
 * Beware, cc->begoff is undefined upon return!
 */
static int
commit_backwards(struct commit_control *cc)
{
        void *retpartial = cc->partial;
        hed_uoff_t begpos = cc->begoff.pos;
        hed_uoff_t blkpos;      /* start of current partial block */
        int ret = 0;

        BDEBUG("Writing backwards %llx-%llx\n",
               cc->begoff.pos, cc->endoff.pos);

        if (!cc->needwrite)
                return 0;

        blkpos = FILE_BLOCK_ROUND(cc->endoff.pos);
        if (blkpos <= begpos)
                goto final;

        /* Handle the trailing partial block */
        hed_update_cursor(cc->file, blkpos, &cc->begoff);
        switch_partial(cc);
        ret |= commit_partial(cc);
        retpartial = cc->partial;

        /* Handle the middle part */
        switch_partial(cc);
        while ( (blkpos -= FILE_BLOCK_SIZE) > begpos) {
                hed_update_cursor(cc->file, blkpos, &cc->begoff);
                ret |= commit_partial(cc);
        }
        switch_partial(cc);     /* wrap around */

 final:
        /* Handle the first block (partiall or not) */
        hed_update_cursor(cc->file, begpos, &cc->begoff);
        ret |= commit_partial(cc);

        cc->partial = retpartial;
        return ret;
}

/* Handle the partial block before a skipped one. */
static int
begin_skip(struct commit_control *cc)
{
        size_t minsize = FILE_BLOCK_SIZE - FILE_BLOCK_OFF(cc->endoff.pos);
        size_t remain;
        int ret = 0;

        /* Check if at least one complete physical block can be skipped */
        if (cc->endoff.block->t.size < minsize)
                return 0;

        /* Write out the partially dirty block */
        remain = FILE_BLOCK_OFF(minsize);
        hed_move_relative(&cc->endoff, remain);
        if (cc->shift <= 0)
                ret |= commit_forwards(cc);
        else
                ret |= commit_backwards(cc);
        hed_move_relative(&cc->endoff, -(hed_off_t)remain);
        hed_dup2_cursor(&cc->endoff, &cc->begoff);

        cc->needwrite = 0;
        return ret;
}

/* Handle the last partially skipped physical block. */
static int
end_skip(struct commit_control *cc)
{
        size_t partlen;
        int ret = 0;

        /* Find the beginning of the physical block */
        hed_dup2_cursor(&cc->endoff, &cc->begoff);
        partlen = FILE_BLOCK_OFF(cc->begoff.pos);
        hed_move_relative(&cc->begoff, -(hed_off_t)partlen);

        /* Read the partial data before this block */
        if (hed_file_cpin(cc->file, cc->partial, partlen, &cc->begoff))
                ret = -1;

        cc->needwrite = 1;
        return ret;
}

static void
undirty_blocks(struct hed_file *file)
{
        struct file_block *block, *next;
        hed_uoff_t pos = 0;

        BDEBUG("Undirtying blocks:\n");
        dump_blocks(file);

        next = first_block(file);
        while (!hed_block_is_eof(next)) {
                block = next;
                next = next_block(block);

                if (kill_block_if_empty(file, block))
                        continue;

                if (!hed_block_is_virtual(block)) {
                        cache_put(file->cache, block->dataobj);
                        block->dataobj = NULL;
                        list_del_init(&block->lru);
                        block->flags = HED_BLOCK_EXCACHE | HED_BLOCK_VIRTUAL;
                }

                block->phys_pos = pos;
                pos += block->t.size;
        }

        block = first_block(file);
        while (!hed_block_is_eof(block)) {
                next = next_block(block);
                file_kill_block(file, block);
                block = next;
        }

        BDEBUG("After undirtying\n");
        dump_blocks(file);
}

static int
commit_init(struct commit_control *cc, struct hed_file *file)
{
        cc->file = file;

        cc->partbuf = malloc(3*FILE_BLOCK_SIZE);
        if (!cc->partbuf)
                goto err;

        cc->wfd = open(file->name,
                       O_RDWR | (file->fd < 0 ? O_CREAT : 0), 0666);
        if (cc->wfd < 0)
                goto err_free;

        if (file->fd < 0 &&
            (file->fd = open(file->name, O_RDONLY)) < 0)
                goto err_close;

        return 0;

 err_close:
        close(cc->wfd);
 err_free:
        free(cc->partbuf);
 err:
        return -1;
}

int
hed_file_commit(struct hed_file *file)
{
        struct commit_control cc;
        int ret = 0;

        if (commit_init(&cc, file))
                return -1;

        dump_blocks(file);

        cc.partial = cc.partbuf;
        get_cursor(file, 0,&cc.begoff);
        hed_dup_cursor(&cc.begoff, &cc.endoff);
        cc.shift = -cc.begoff.block->phys_pos;
        cc.needwrite = 0;
        while(!hed_block_is_eof(cc.endoff.block)) {
                hed_off_t newshift = cc.endoff.pos < file->phys_size
                        ? get_shift(&cc.endoff)
                        : 0;

                if (cc.shift <= 0 && newshift > 0) {
                        ret |= commit_forwards(&cc);
                        hed_dup2_cursor(&cc.endoff, &cc.begoff);
                } else if (cc.shift > 0 && newshift <= 0) {
                        ret |= commit_backwards(&cc);
                        hed_dup2_cursor(&cc.endoff, &cc.begoff);
                }
                cc.shift = newshift;

                if (!newshift && !hed_block_is_dirty(cc.endoff.block)) {
                        if (cc.needwrite)
                                ret |= begin_skip(&cc);
                } else if (!cc.needwrite)
                        ret |= end_skip(&cc);

                if (!move_to_next(&cc.endoff))
                        break;
        }
        assert(cc.endoff.pos == file_size(file));

        if (cc.begoff.pos < file_size(file)) {
                if (cc.shift <= 0)
                        ret |= commit_forwards(&cc);
                else
                        ret |= commit_backwards(&cc);
        }

        put_cursor(&cc.begoff);
        put_cursor(&cc.endoff);

        ftruncate(cc.wfd, file_size(file));
        file->phys_size = file_size(file);

        ret |= close(cc.wfd);
        free(cc.partbuf);

        undirty_blocks(file);

        if (!ret)
                clear_modified(file);

        return ret;
}

#ifdef HED_CONFIG_SWAP
int
hed_file_write_swap(struct hed_file *file)
{
        return swp_write(file_swp(file));
}

static int
do_read_swap(struct hed_file *file, struct swp_file *swp, blockoff_t *pos)
{
        struct hed_file *swpfile = swp_private(swp);
        struct file_block *cur, block;
        hed_uoff_t phys_pos;

        if (file_stat(swpfile)->st_size != file_stat(file)->st_size ||
            file_stat(swpfile)->st_mtime != file_stat(file)->st_mtime) {
                fprintf(stderr, "stat info mismatch (you modified the file since hed ran on it; refusing to touch it)\n");
                return -1;
        }

        BDEBUG("Swap header match\n");

        phys_pos = 0;
        cur = first_block(swpfile);
        do {
                struct hed_block_data dataobj;
                size_t (*mergefn)(struct hed_file*, blockoff_t*,
                                  unsigned char*, size_t);
                void *data;
                size_t res;

                if (swp_cpin(swp, &block, cur, sizeof(struct file_block))) {
                        perror("Cannot read block descriptor");
                        return -1;
                }
                BDEBUG("BLOCK %p: flags %02lx phys 0x%02llx size 0x%llx\n",
                       cur, block.flags, (long long)block.phys_pos,
                       (long long)hed_block_size(&block));

                if (block.phys_pos - phys_pos) {
                        if (hed_file_erase_block(file, pos,
                                                 block.phys_pos - phys_pos)) {
                                perror("Cannot erase");
                                return -1;
                        }
                        phys_pos = block.phys_pos;
                }

                if (!hed_block_is_inserted(&block))
                        phys_pos += hed_block_size(&block);

                if (!hed_block_is_dirty(&block)) {
                        hed_move_relative(pos, hed_block_size(&block));
                        continue;
                }

                if (swp_cpin(swp, &dataobj, block.dataobj,
                             sizeof(struct hed_block_data))) {
                        perror("Cannot read data descriptor");
                        return -1;
                }
                BDEBUG("DATA %p: size 0x%lx\n",
                       block.dataobj, (long)dataobj.size);

                if (! (data = malloc(hed_block_size(&block))) ) {
                        perror("Cannot allocate data");
                        return -1;
                }

                if (swp_cpin(swp, data, dataobj.data + block.dataoff,
                             hed_block_size(&block))) {
                        perror("Cannot read data");
                        return -1;
                }

                mergefn = hed_block_is_inserted(&block)
                        ? hed_file_insert_once
                        : hed_file_set_block;
                res = mergefn(file, pos, data, hed_block_size(&block));
                free(data);
                if (res) {
                        perror("Cannot merge data");
                        return -1;
                }
        } while (cur = next_block(&block), !hed_block_is_eof(&block));

        dump_blocks(file);
        return 0;
}

int
hed_file_read_swap(struct hed_file *file)
{
        struct swp_file *swp;
        blockoff_t pos;
        int ret;

        if (! (swp = swp_init_read(file->swpname)) )
                return -1;

        get_cursor(file, 0, &pos);
        ret = do_read_swap(file, swp, &pos);
        put_cursor(&pos);

        swp_done(swp);
        return ret;
}

#endif  /* HED_CONFIG_SWAP */

struct ffb_hookdata {
        struct hed_file *file;
        blockoff_t *pos;
        hed_expr_reg_cb base_ecb;
        void *base_ecb_data;
};

static long
eval_reg_cb(void *hookdata, char reg, hed_off_t ofs,
            unsigned char *scramble, size_t len)
{
        struct ffb_hookdata *data = hookdata;
        if (reg == '.') {
                blockoff_t pos;
                long ret = HED_AEF_DYNAMIC;

                hed_dup_cursor(data->pos, &pos);
                hed_move_relative(&pos, ofs);
                if (copy_in(data->file, scramble, len, &pos))
                        ret = HED_AEF_ERROR;
                put_cursor(&pos);
                return ret;
        }

        return data->base_ecb(data->base_ecb_data, reg, ofs, scramble, len);
}

static void
reverse(unsigned char *p, size_t len)
{
        unsigned char *q = p + len;
        while (p < q) {
                unsigned char x = *p;
                *p++ = *--q;
                *q = x;
        }
}

static void
compute_badchar(ssize_t *badchar, const unsigned char *s, ssize_t len)
{
        size_t i = 1;
        while (i < len)
                badchar[*s++] = i++;
}

static void
compute_sfx(ssize_t *sfx, const unsigned char *s, ssize_t len)
{
        ssize_t f, g, i;

        sfx[len - 1] = len;
        g = len - 1;
        for (i = len - 2; i >= 0; --i) {
                if (i > g && sfx[i + len - 1 - f] < i - g)
                        sfx[i] = sfx[i + len - 1 - f];
                else {
                        if (i < g)
                                g = i;
                        f = i;
                        while (g >= 0 && s[g] == s[g + len - 1 - f])
                                --g;
                        sfx[i] = f - g;
                }
        }
}

static void
compute_goodsfx(ssize_t *goodsfx, const unsigned char *s, ssize_t len)
{
        ssize_t i, j, *sfx = goodsfx + len;

        compute_sfx(sfx, s, len);

        for (i = 0; i < len; ++i)
                goodsfx[i] = len;
        j = 0;
        for (i = len - 1; i >= 0; --i)
                if (sfx[i] == i + 1)
                        for (; j < len - 1 - i; ++j)
                                if (goodsfx[j] == len)
                                        goodsfx[j] = len - 1 - i;
        for (i = 0; i <= len - 2; ++i)
                goodsfx[len - 1 - sfx[i]] = len - 1 - i;
}

/* Search for a constant byte string using the Boyer-Moore algorithm. */
static inline unsigned char*
bm_find(unsigned char *buf, size_t buflen, unsigned char *needle,
        size_t maxidx, ssize_t *badchar, ssize_t *goodsfx)
{
        while (buflen > maxidx) {
                unsigned char *p;
                size_t i;
                ssize_t shift;

                for (p = buf + maxidx, i = maxidx; p >= buf; --p, --i)
                        if (needle[i] != *p)
                                break;
                if (p < buf)
                        return buf;

                shift = i + 1 - badchar[*p];
                if (shift < goodsfx[i])
                        shift = goodsfx[i];

                buf += shift;
                buflen -= shift;
        }
        return NULL;
}

/* Search for a constant byte string backwards. */
static inline unsigned char*
bm_find_rev(unsigned char *buf, size_t buflen, unsigned char *needle,
            size_t maxidx, ssize_t *badchar, ssize_t *goodsfx)
{
        buf -= maxidx;
        while (buflen > maxidx) {
                unsigned char *p;
                size_t i;
                ssize_t shift;

                for (p = buf, i = maxidx; p <= buf + maxidx; ++p, --i)
                        if (needle[i] != *p)
                                break;
                if (p > buf + maxidx)
                        return buf;

                shift = i + 1 - badchar[*p];
                if (shift < goodsfx[i])
                        shift = goodsfx[i];

                buf -= shift;
                buflen -= shift;
        }
        return NULL;
}

/* Search for a constant byte string in @buf.
 * If @buflen is negative, search backwards, otherwise search forwards.
 */
static inline unsigned char*
find_bytestr_buf(unsigned char *buf, ssize_t buflen,
                 unsigned char *needle, ssize_t maxidx,
                 ssize_t *badchar, ssize_t *goodsfx)
{
        if (buflen < 0) {
                buflen = -buflen;
                if (!maxidx)
                        return memrchr(buf - buflen + 1, *needle, buflen);
                return bm_find_rev(buf, buflen, needle, maxidx,
                                   badchar, goodsfx);
        } else {
                if (!maxidx)
                        return memchr(buf, *needle, buflen);
                return bm_find(buf, buflen, needle, maxidx,
                               badchar, goodsfx);
        }
}

/* Search for a constant byte string using the Boyer-Moore algorithm. */
static int
find_bytestr(struct hed_file *file, blockoff_t *from, int dir,
             unsigned char *needle, ssize_t len)
{
        void *dynalloc;
        ssize_t *badchar, *goodsfx;
        unsigned char *readbuf;
        ssize_t slen;
        int ret;

        if (len > 1) {
                dynalloc = calloc(sizeof(ssize_t) * (256 + 2*len)
                                  + 2*(len-1), 1);
                if (!dynalloc)
                        return HED_FINDOFF_ERROR;
                badchar = dynalloc;
                goodsfx = badchar + 256;
                readbuf = dynalloc + sizeof(ssize_t) * (256 + 2*len);

                if (dir < 0)
                        reverse(needle, len);
                compute_badchar(badchar, needle, len);
                compute_goodsfx(goodsfx, needle, len);
        } else {
                dynalloc = NULL;
                badchar = goodsfx = NULL;
                readbuf = NULL;
        }

        --len;                  /* simplify offset computing */
        if (dir < 0) {
                from->off += len;
                from->pos += len;
                slen = -len;
        } else
                slen = len;

        ret = HED_FINDOFF_NO_MATCH;
        while (from->pos >= 0) {
                ssize_t remain;

                fixup_cursor(from);
                if (hed_block_is_eof(from->block))
                        break;

                remain = hed_prepare_read(file, from, SSIZE_MAX);
                if (!remain) {
                        ret = HED_FINDOFF_ERROR;
                        break;
                }
                if (dir < 0)
                        remain = -(from->off + 1);

                if (!hed_block_is_bad(from->block)) {
                        unsigned char *p, *q;

                        if ((dir >= 0 && remain > slen) ||
                            (dir < 0 && remain < slen)) {
                                assert(!hed_block_is_virtual(from->block));
                                assert(from->block->dataobj);
                                p = from->block->dataobj->data + from->off;
                                from->off += remain;
                                from->pos += remain;
                        } else if (dir >= 0) {
                                remain += slen;
                                if (copy_in(file, readbuf, remain, from)) {
                                        ret = HED_FINDOFF_ERROR;
                                        break;
                                }
                                p = readbuf;
                        } else {
                                remain += slen;
                                from->off += remain + 1;
                                from->pos += remain + 1;
                                if (from->pos < 0)
                                        break;
                                fixup_cursor_slow(from);
                                if (copy_in(file, readbuf, -remain, from)) {
                                        ret = HED_FINDOFF_ERROR;
                                        break;
                                }
                                from->off -= -remain + 1;
                                from->pos -= -remain + 1;
                                p = readbuf + (-remain - 1);
                        }

                        q = find_bytestr_buf(p, remain, needle, len,
                                             badchar, goodsfx);
                        if (q) {
                                move_rel_fast(from, q - p - remain);
                                ret = 0;
                                break;
                        }
                        from->off -= slen;
                        from->pos -= slen;
                } else {
                        /* bad blocks cannot match anything */
                        from->off += remain;
                        from->pos += remain;
                }
        }

        if (dynalloc)
                free(dynalloc);
        return ret;
}

static int
find_expr(struct hed_file *file, blockoff_t *from, int dir,
          struct hed_expr *expr, struct ffb_hookdata *data)
{
        int len = hed_expr_len(expr);
        unsigned char *buf;

        assert(len > 0);

        if (len > file_size(file))
                return HED_FINDOFF_NO_MATCH;
        if ((hed_off_t)file_size(file) - from->pos - len < 0)
                hed_move_relative(from,
                                  (hed_off_t)file_size(file) - from->pos - len);

        for (;;) {
                blockoff_t match;
                size_t remain;
                unsigned char *p;
                int pos;

                buf = hed_expr_eval(expr, eval_reg_cb, NULL, data);
                if (!buf)
                        return HED_FINDOFF_ERROR;

                hed_dup_cursor(from, &match);
                remain = 0;
                for (pos = 0; pos < len; pos++) {
                        if (!remain) {
                                remain = hed_prepare_read(file, &match,
                                                          SIZE_MAX);
                                if (!remain ||
                                    hed_block_is_bad(match.block))
                                        break;
                                p = hed_cursor_data(&match);
                                cursor_next_block(&match);
                        }
                        if (*p++ != buf[pos])
                                break;
                        remain--;
                }
                put_cursor(&match);

                if (pos == len)
                        return 0;
                if (!remain)
                        return HED_FINDOFF_ERROR;

                from->pos += dir;
                from->off += dir;
                if (0 > from->pos || from->pos > file_size(file) - len)
                        break;
                fixup_cursor(from);

                if (! (hed_expr_flags(expr) & HED_AEF_DYNAMIC) )
                        return find_bytestr(file, from, dir, buf, len);
        }

        return HED_FINDOFF_NO_MATCH;
}

int
hed_file_find_expr(struct hed_file *file, blockoff_t *pos, int dir,
                   struct hed_expr *expr,
                   hed_expr_reg_cb expr_cb, void *expr_cb_data)
{
        struct ffb_hookdata data;
        int res;

        assert(dir == 1 || dir == -1);

        data.file = file;
        data.pos = pos;
        data.base_ecb = expr_cb;
        data.base_ecb_data = expr_cb_data;

        hed_file_set_readahead(file,
                               dir > 0 ? HED_RA_FORWARD : HED_RA_BACKWARD);
        res = find_expr(file, pos, dir, expr, &data);
        hed_file_set_readahead(file, HED_RA_NONE);

        return res;
}