fixup_cursor_slow: always stop at terminal block

[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 "file_priv.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)

/* Searches for data object don't care about the EOF flag */
#define STATEMASK_SANS_EOF      (HED_BLOCK_STATEMASK & ~HED_BLOCK_EOF)

#define first_block(f) next_block(last_block(f))
#define prev_block(b) (tree_entry(prev_in_tree(&(b)->t),struct hed_block,t))
#define next_block(b) (tree_entry(next_in_tree(&(b)->t),struct hed_block,t))
#define last_block(f) (&(f)->terminal_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 hed_block,t)

#define block_is_loadable(b)    \
        (((b)->flags & (HED_BLOCK_VIRTUAL | HED_BLOCK_EOF | HED_BLOCK_BAD)) \
         == HED_BLOCK_VIRTUAL)

#ifdef HED_CONFIG_SWAP

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

#else

/* Provide a stub for the non-swap case */
static inline void *
file_swp(struct file_priv *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)

static inline void
set_readahead(struct file_priv *file, int val)
{
        file->readahead = val;
}

#else

#define file_ra_none(f)         (1)
#define file_ra_forward(f)      (0)
#define file_ra_backward(f)     (0)
#define set_readahead(file,t) do {} while(0)

#endif  /* HED_CONFIG_READAHEAD */

void
hed_file_set_readahead(struct hed_file *file, enum hed_readahead val)
{
        set_readahead(file_private(file), val);
}


/* 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_terminal(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_terminal(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);
}

/* Get the blocks tree */
static inline struct hed_tree *
hed_file_blocks(struct file_priv *file)
{
        return &file->blocks;
}

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

static hed_uoff_t
block_phys_size(struct hed_block *block)
{
        struct hed_block *next;

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

static void
dump_block(int level, struct file_priv *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);
        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%c%c %05llx %05llx"
                " {%02x%02x%02x%02x} -- %p ^%p [%06llx]\n",
                t,
                (unsigned long long) *cur_offset,
                (unsigned long long) *cur_poffset,
                hed_block_is_bad(block) ? 'b' : ' ',
                hed_block_is_eof(block) ? 'e' : ' ',
                hed_block_is_virtual(block) ? 'v' : ' ',
                hed_block_is_inserted(block) ? 'i' : ' ',
                hed_block_is_dirty(block) ? '*' : ' ',
                (unsigned long long) node->size,
                (unsigned long long) block_phys_size(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(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 file_priv *file)
{
        struct hed_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, hed_file_blocks(file)->root,
                   &cur_offset, &cur_poffset);
        fprintf(stderr, "-- blocks dump end --\n");
}
#endif

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

        block = find_block(hed_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_private(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_private(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(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_terminal(block));
}

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

        if (! (new = swp_zalloc(file_swp(file), sizeof(struct hed_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 file_priv *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 file_priv *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 file_priv *file, struct hed_block *block)
{
        if (block->dataobj)
                cache_put(file->cache, block->dataobj);
        list_del(&block->lru);

        swp_free(file_swp(file), block);
}

static void
merge_and_free(struct file_priv *file, struct hed_block *block,
               struct hed_block *merger, hed_off_t off)
{
        /* A bit more efficient than move_cursors() */
        update_cursors(block, merger, off);
        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 += hed_block_size(block);
        recalc_block_recursive(merger);

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

/* 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
kill_block(struct file_priv *file, struct hed_block *block)
{
        struct hed_block *prev, *next;

        assert(!hed_block_is_dirty(block) || !hed_block_size(block));

        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 */
                block->flags = HED_BLOCK_EXCACHE | HED_BLOCK_VIRTUAL |
                        (block->flags & HED_BLOCK_EOF);
        }

        prev = prev_block(block);
        if (prev->flags == block->flags &&
            prev->phys_pos + hed_block_size(prev) == block->phys_pos) {
                merge_and_free(file, block, prev, hed_block_size(prev));
                block = prev;
        }

        next = next_block(block);
        if (next->flags == block->flags &&
            block->phys_pos + hed_block_size(block) == next->phys_pos) {
                update_cursors(next, next, hed_block_size(block));
                next->phys_pos -= hed_block_size(block);
                merge_and_free(file, block, next, 0);
                block = next;
        }

        if (!hed_block_size(block)) {
                /* No recalculation needed, zero size. */
                unchain_block(hed_file_blocks(file), block);
                file_free_block(file, block);
        }
}

static bool
kill_block_if_empty(struct file_priv *file, struct hed_block *block)
{
        if (!hed_block_is_terminal(block) && hed_block_size(block) == 0 &&
            list_empty(&block->refs)) {
                kill_block(file, block);
                return true;
        }
        return false;
}

static struct hed_block *
split_block(struct file_priv *file, struct hed_block *block,
            hed_uoff_t splitpoint)
{
        struct hed_block *head;

        head = new_block(file, block->flags & ~HED_BLOCK_TERMINAL);
        if (!head)
                return NULL;

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

        head->t.size = splitpoint;
        head->phys_pos = block->phys_pos;

        block->t.size -= splitpoint;
        if (!hed_block_is_inserted(block))
                block->phys_pos += splitpoint;
        recalc_block_recursive(block);
        recalc_chain_block_before(hed_file_blocks(file), head, block);

        move_cursors(block, head, 0, splitpoint - 1, 0);
        update_cursors(block, block, -splitpoint);

        return head;
}

/* Replace a chunk in @block with @newblock */
static int
replace_chunk(struct file_priv *file, struct hed_block *block,
              hed_uoff_t offset, struct hed_block *newblock)
{
        size_t len;

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

        /* Re-create the head block if necessary */
        if (offset && !split_block(file, block, offset))
                return -1;

        /* Move pointers to the new block */
        len = hed_block_size(newblock);
        assert(len > 0);
        move_cursors(block, newblock, 0, len - 1, 0);

        /* Shorten the tail block */
        len = hed_block_size(newblock);
        block->t.size -= len;
        block->dataoff += len;
        assert(!hed_block_is_inserted(block));
        block->phys_pos += len;
        recalc_block_recursive(block);
        update_cursors(block, block, -len);

        /* Insert the new block */
        recalc_chain_block_before(hed_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 *p = NULL;         /* bogus assignment to silence a warning */
        char *ret;

        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 *f)
{
        struct file_priv *file = file_private(f);
        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 file_priv *
file_swp_init(const char *name)
{
        char *swpname, *newswpname;
        struct swp_file *swp;
        struct file_priv *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 file_priv)
               <= 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 file_priv *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 */
}

int
hed_file_has_swap(struct hed_file *f)
{
        struct file_priv *file = file_private(f);
        return file->swpname != file->newswpname;
}

char *
hed_file_swap_name(struct hed_file *f)
{
        struct file_priv *file = file_private(f);
        return file->swpname;
}

#else  /* HED_CONFIG_SWAP */

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

static inline void
file_swp_done(struct file_priv *file)
{
        free(file);
}

int
hed_file_has_swap(struct hed_file *file)
{
        return 0;
}

int
hed_file_remove_swap(struct hed_file *file)
{
        return 0;
}

char *
hed_file_swap_name(struct hed_file *file)
{
        return NULL;
}

#endif  /* HED_CONFIG_SWAP */

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

int
hed_file_update_size(struct hed_file *f)
{
        struct file_priv *file = file_private(f);
        hed_uoff_t oldsize = file->f.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->f.phys_size)) {
                        unsigned long size_in_blocks;
                        if (ioctl(file->fd, BLKGETSIZE, &size_in_blocks))
                                return -1;
                        file->f.phys_size = (hed_uoff_t)size_in_blocks << 9;
                }
        } else if (S_ISREG(file_stat(file)->st_mode)) {
                file->f.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->f.phys_size = (hed_uoff_t)OFF_MAX + 1;
        } else {
                errno = EINVAL;
                return -1;
        }

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

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

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

static int
file_setup_blocks(struct file_priv *file)
{
        hed_uoff_t phys_size = file->f.phys_size;
        struct hed_block *block;

        block = &file->terminal_block;
        block->flags =  HED_BLOCK_EXCACHE | HED_BLOCK_VIRTUAL
                | HED_BLOCK_EOF | HED_BLOCK_TERMINAL;
        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(hed_file_blocks(file), block);

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

        return 0;
}

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

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

        if (!file)
                goto fail;

        file->f.name = name;
        INIT_LIST_HEAD(&file->lru);

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

        if (do_file_open(file))
                goto fail_file;

        if (file_setup_blocks(file))
                goto fail_file;

        fixup_register(file);

        return &file->f;

 fail_file:
        hed_close(&file->f);
 fail:
        return NULL;
}

void
hed_close(struct hed_file *f)
{
        struct file_priv *file = file_private(f);
        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 hed_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 (!hed_block_is_terminal(block) && 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 file_priv *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 hed_block *block;

                assert(!list_empty(&file->lru));
                block = list_entry(file->lru.next, struct hed_block, lru);
                BDEBUG("Killing block at physical %llx\n", block->phys_pos);
                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 file_priv *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 file_priv *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) {
                        memset(data + total, 0, segsize - total);
                        break;
                }
                if (rsize < 0) {
                        cache_put(file->cache,
                                  caches[total >> FILE_BLOCK_SHIFT]);
                        caches[total >> FILE_BLOCK_SHIFT] = NULL;
                        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 file_priv *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_block *block, hed_uoff_t segstart)
{
        struct hed_block *prev = block;
        do {
                block = prev;
                prev = prev_block(prev);
        } while (!hed_block_is_terminal(prev) && phys_end(prev) > segstart);
        return block;
}

static int
load_blocks(struct file_priv *file, const hed_cursor_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;
        int ret;

        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->f.phys_size - segstart)
                ra_fwd = file->f.phys_size - segstart;

        segstart -= ra_bkw;
        ra_fwd += ra_bkw;
        pos.block = first_load_block(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);

        ret = -1;               /* be a pessimist */
        if (file_load_data(file, preload, nblocks, segstart))
                goto out;

        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);
                if (!newblock)
                        goto out;

                /* 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);
                        goto out;
                }

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

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

        dump_blocks(file);
        return ret;
}

/* 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_block *block, size_t len, long state)
{
        struct hed_block *prev;
        size_t maxgrow;

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

        /* The previous block must exist: */
        prev = prev_block(block);
        if (hed_block_is_terminal(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 - prev->dataoff);
        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_block *block, size_t len, long state)
{
        struct hed_block *next;
        hed_uoff_t off;

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

        /* The next block must exist: */
        if (hed_block_is_terminal(block))
                return 0;
        next = next_block(block);

        /* 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 file_priv *file, const hed_cursor_t *curs, long state)
{
        struct hed_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_terminal(block = prev_block(block))) {
                if (block->phys_pos < physpos)
                        break;
                if ((block->flags & STATEMASK_SANS_EOF) == state) {
                        BDEBUG(" found at %llx\n", block->phys_pos);
                        assert(block->dataobj);
                        return block->dataobj;
                }
        }

        /* Search forwards */
        block = curs->block;
        while (!hed_block_is_terminal(block)) {
                block = next_block(block);
                if (block->phys_pos >= physpos + FILE_BLOCK_SIZE)
                        break;
                if ((block->flags & STATEMASK_SANS_EOF) == 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 file_priv *file, const hed_cursor_t *curs,
                  struct hed_block_data *data)
{
        struct hed_block *physblock;
        struct hed_block *block = curs->block;
        hed_uoff_t block_offset = curs->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 @curs will
 * be in a non-virtual block when this function returns 0.
 */
static int
devirtualize_clean(struct file_priv *file, const hed_cursor_t *curs)
{
        struct hed_block *block = curs->block;
        hed_uoff_t block_offset = curs->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(block, hed_block_size(block), 0) > block_offset
            || shrink_at_end(block, hed_block_size(block), 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, curs, 0);
        return data
                ? reuse_loaded_data(file, curs, data)
                : load_blocks(file, curs);
}

/* Unles the block at @curs is already dirty, replace at most
 * @len bytes at @curs with a newly allocated out-of-cache block.
 * The block is marked dirty and its data is left uninitialized.
 * Note that this function may devirtualize less than @len bytes.
 * In the worst case only 1 byte at @curs will be available.
 */
static int
prepare_modify(struct file_priv *file, hed_cursor_t *curs, size_t len)
{
        struct hed_block *block = curs->block;
        hed_uoff_t block_offset = curs->off;
        hed_uoff_t remain = block->t.size - block_offset;
        long newstate = HED_BLOCK_DIRTY | (block->flags & HED_BLOCK_EOF);
        struct hed_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(block, len, newstate)) ||
            (remain == len &&
             shrink_at_end(block, len, newstate) >= len)) {
                kill_block_if_empty(file, block);
                dump_blocks(file);
                return 0;
        }

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

        /* Allocate data */
        if ( (newblock->dataobj = search_data(file, curs, 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 *f, const hed_cursor_t *curs, size_t len)
{
        struct file_priv *file = file_private(f);
        struct hed_block *block = curs->block;
        if (block_is_loadable(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;
}

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

        pos->pos += count;
        while (count && (cpylen = hed_prepare_read(&file->f, pos, count))) {
                if (hed_block_is_bad(pos->block))
                        break;
                else 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)
{
        hed_cursor_t mypos;
        size_t ret;

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

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

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

int
hed_file_set_byte(struct hed_file *f, hed_cursor_t *curs, unsigned char byte)
{
        struct file_priv *file = file_private(f);

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

        hed_block_data(curs->block)[curs->off] = byte;

        if (hed_block_is_terminal(next_block(curs->block)))
                file->f.size = curs->pos + 1;

        return 0;
}

size_t
hed_file_set_block(struct hed_file *f, hed_cursor_t *curs,
                   unsigned char *buf, size_t len)
{
        struct file_priv *file = file_private(f);
        while (len) {
                size_t span;

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

                span = hed_cursor_chunk_len(curs, len);
                memcpy(hed_cursor_data(curs), buf, span);
                buf += span;
                len -= span;
                move_rel_fast(curs, span);
        }

        if (hed_block_is_terminal(curs->block))
                file->f.size = curs->pos;

        return len;
}

hed_uoff_t
hed_file_set_bytes(struct hed_file *f, hed_cursor_t *curs,
                   unsigned char byte, hed_uoff_t rep)
{
        struct file_priv *file = file_private(f);
        while (rep) {
                size_t span;

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

                span = hed_cursor_chunk_len(curs, rep);
                memset(hed_cursor_data(curs), byte, span);
                rep -= span;
                move_rel_fast(curs, span);
        }

        if (hed_block_is_terminal(curs->block))
                file->f.size = curs->pos;

        return rep;
}

static int
file_erase_continuous(struct file_priv *file, hed_cursor_t *curs, size_t len)
{
        struct hed_block *block = curs->block;
        hed_uoff_t block_offset = curs->off;

        /* Find the new position */
        hed_move_relative(curs, 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, curs);

        if (!block_offset) {
                block->dataoff += len;
                if (!hed_block_is_inserted(block))
                        block->phys_pos += len;
        } else if (block_offset + len < block->t.size) {
                block = split_block(file, block, block_offset + len);
                if (!block)
                        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 *f, hed_cursor_t *curs, hed_uoff_t len)
{
        struct file_priv *file = file_private(f);
        hed_uoff_t todo;

        todo = len;
        while (!hed_block_is_terminal(curs->block) && todo) {
                size_t span = hed_cursor_chunk_len(curs, todo);

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

                todo -= span;
        }
        len -= todo;

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

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

        struct hed_block *slideblock = prev_block(curs->block);
        if (hed_block_is_terminal(slideblock))
                slideblock = curs->block;
        slide_cursors(slideblock, curs->pos, -len);

        return hed_block_is_terminal(curs->block) ? 0 : todo;
}

/* Note that @curs may be detached from the block reference list
 * with put_cursor(). Only the pos, block and off fields are used.
 * This is an implementation detail currently required by
 * hed_file_insert_block(), which sets @curs and @curs_ins to the
 * same value. Other users of the library must not rely on it.
 */
int
hed_file_insert_begin(struct hed_file *f, const hed_cursor_t *curs,
                      hed_cursor_t *curs_ins)
{
        struct file_priv *file = file_private(f);
        struct hed_block *newblock;

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

        newblock = new_block(file, (HED_BLOCK_EXCACHE |
                                    HED_BLOCK_INSERTED | HED_BLOCK_DIRTY |
                                    (curs->block->flags & HED_BLOCK_EOF)));
        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;
        }

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

        chain_block_before(hed_file_blocks(file), newblock, curs->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 *f, hed_cursor_t *curs_ins)
{
        struct file_priv *file = file_private(f);
        struct hed_block *block = curs_ins->block;

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

        curs_ins->block = NULL;
        list_del(&curs_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 file_priv *file, hed_cursor_t *curs,
             unsigned char *buf, size_t len)
{
        struct hed_block *block = curs->block;
        hed_uoff_t offset = curs->pos;

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

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

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

size_t
hed_file_insert_block(struct hed_file *f, hed_cursor_t *curs,
                      unsigned char *buf, size_t len)
{
        struct file_priv *file = file_private(f);
        size_t todo = len;
        while (todo) {
                struct hed_block *block = curs->block;
                size_t remain;

                remain = block->dataobj->size - block->dataoff - curs->off;
                if (!remain) {
                        put_cursor(curs);
                        curs->block = next_block(block);
                        curs->off = 0;

                        if (hed_file_insert_begin(&file->f, curs, curs))
                                break;

                        continue;
                }

                if (remain > todo)
                        remain = todo;

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

        if (curs->pos > file->f.size)
                file->f.size = curs->pos;
        else
                file->f.size += len;

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

        return todo;
}

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

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

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

struct commit_control {
        struct file_priv *file;
        int wfd;                /* file descriptor for writing */
        hed_cursor_t begoff, endoff;
        void *buffer;           /* write buffer (one block) */
};

static ssize_t
commit_write(struct commit_control *cc, hed_uoff_t pos, ssize_t len)
{
        BDEBUG(" -> write %lx bytes at %llx\n",
               (unsigned long)len, pos);
        return pwrite(cc->wfd, cc->buffer, len, pos);
}

/* Commit forwards. */
static int
commit_forwards(struct commit_control *cc)
{
        int ret = 0;

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

        while (cc->begoff.pos < cc->endoff.pos) {
                size_t left;
                ssize_t written;

                left = copy_in(cc->file, cc->buffer,
                               FILE_BLOCK_SIZE, &cc->begoff);
                if (left) {
                        move_rel_fast(&cc->begoff, left);
                        ret = -1;
                        continue;
                }

                written = commit_write(cc, cc->begoff.pos - FILE_BLOCK_SIZE,
                                       FILE_BLOCK_SIZE);
                if (written < FILE_BLOCK_SIZE)
                        ret = -1;
        }

        return ret;
}

/* Commit backwards. */
static int
commit_backwards(struct commit_control *cc)
{
        hed_cursor_t curs;
        int ret = 0;

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

        hed_dup_cursor(&cc->endoff, &curs);
        while (curs.pos > cc->begoff.pos) {
                size_t left;
                ssize_t written;

                move_rel_fast(&curs, -FILE_BLOCK_SIZE);
                left = hed_file_cpin(&cc->file->f, cc->buffer,
                                     FILE_BLOCK_SIZE, &curs);
                if (left) {
                        ret = -1;
                        continue;
                }

                written = commit_write(cc, curs.pos, FILE_BLOCK_SIZE);
                if (written < FILE_BLOCK_SIZE)
                        ret = -1;
        }
        hed_put_cursor(&curs);

        return ret;
}

/* Return the number of clean bytes following @curs.
 * Usage note: the caller must ensure that the starting position
 *             is clean.
 */
static hed_uoff_t
clean_span(hed_cursor_t *curs)
{
        hed_uoff_t next_pos;
        struct hed_block *block = curs->block;
        hed_uoff_t ret = -curs->off;

        assert(!hed_block_is_dirty(block));

        do {
                ret += hed_block_size(block);
                next_pos = block->phys_pos + hed_block_size(block);
                block = next_nonzero_block(block);
        } while (block->phys_pos == next_pos && /* no insertions, deletions */
                 !hed_block_is_dirty(block) &&  /* no modifications */
                 !hed_block_is_terminal(block));
        return ret;
}

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

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

        next = first_block(file);
        while (!hed_block_is_terminal(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_terminal(block)) {
                next = next_block(block);
                kill_block(file, block);
                block = next;
        }

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

static int
commit_init(struct commit_control *cc, struct file_priv *file)
{
        cc->file = file;
        cc->buffer = malloc(FILE_BLOCK_SIZE);
        if (!cc->buffer)
                goto err;

        if (file->fd < 0) {
                file->fd = open(file->f.name, O_RDONLY | O_CREAT, 0666);
                if (file->fd < 0)
                        goto err_free;
        }

        cc->wfd = open(file->f.name, O_WRONLY);
        if (cc->wfd < 0)
                goto err_free;

        return 0;

 err_free:
        free(cc->buffer);
 err:
        return -1;
}

int
hed_file_commit(struct hed_file *f)
{
        struct file_priv *file = file_private(f);
        struct commit_control cc;
        hed_off_t shift;
        int ret = 0;

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

        dump_blocks(file);

        get_cursor(file, 0,&cc.begoff);
        hed_dup_cursor(&cc.begoff, &cc.endoff);
        shift = -cc.begoff.block->phys_pos;
        while(!hed_block_is_terminal(cc.endoff.block)) {
                hed_uoff_t skip;
                hed_off_t newshift;

                if (!shift && !hed_block_is_dirty(cc.endoff.block)) {
                        skip = FILE_BLOCK_ROUND(clean_span(&cc.endoff));
                        if (skip) {
                                ret |= commit_forwards(&cc);

                                BDEBUG("Skipping %llx-%llx\n",
                                       cc.endoff.pos, cc.endoff.pos + skip);
                                hed_move_relative(&cc.endoff, skip);
                                hed_dup2_cursor(&cc.endoff, &cc.begoff);
                                continue;
                        }
                }

                skip = FILE_BLOCK_ROUND(hed_cursor_span(&cc.endoff));
                hed_move_relative(&cc.endoff, skip ?: FILE_BLOCK_SIZE);

                newshift = !hed_block_is_eof(cc.endoff.block)
                        ? cc.endoff.pos - hed_cursor_phys_pos(&cc.endoff)
                        : 0;

                if (shift <= 0 && newshift > 0) {
                        move_rel_fast(&cc.endoff, -FILE_BLOCK_SIZE);
                        ret |= commit_forwards(&cc);
                        hed_dup2_cursor(&cc.endoff, &cc.begoff);
                } else if (shift > 0 && newshift <= 0) {
                        ret |= commit_backwards(&cc);
                        hed_dup2_cursor(&cc.endoff, &cc.begoff);
                }
                shift = newshift;
        }
        assert(cc.endoff.pos >= hed_file_size(&file->f));

        ret |= commit_forwards(&cc);
        put_cursor(&cc.begoff);
        put_cursor(&cc.endoff);

        ftruncate(cc.wfd, hed_file_size(&file->f));
        file->f.phys_size = hed_file_size(&file->f);

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

        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_private(file)));
}

static int
do_read_swap(struct file_priv *file, struct swp_file *swp, hed_cursor_t *pos)
{
        struct file_priv *swpfile = swp_private(swp);
        struct hed_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*, hed_cursor_t*,
                                  unsigned char*, size_t);
                void *data;
                size_t res;

                if (swp_cpin(swp, &block, cur, sizeof(struct hed_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->f, 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->f, pos, data, hed_block_size(&block));
                free(data);
                if (res) {
                        perror("Cannot merge data");
                        return -1;
                }
        } while (cur = next_block(&block), !hed_block_is_terminal(&block));

        dump_blocks(file);
        return 0;
}

int
hed_file_read_swap(struct hed_file *f)
{
        struct file_priv *file = file_private(f);
        struct swp_file *swp;
        hed_cursor_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;
}

#else

int
hed_file_write_swap(struct hed_file *file)
{
        return 0;
}

int
hed_file_read_swap(struct hed_file *file)
{
        return -1;
}

#endif  /* HED_CONFIG_SWAP */

/* Check if the search string is all zero */
static bool
is_allzero(unsigned char *s, size_t len)
{
       while (len--)
               if (*s++)
                       return false;
       return true;
}

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;
        f = 0;                  /* bogus assignment to silence a warning */
        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*
search_buf(unsigned char *buf, size_t buflen, unsigned char *needle,
           size_t maxidx, ssize_t *badchar, ssize_t *goodsfx)
{
        if (!maxidx)
                return memchr(buf, *needle, buflen);

        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*
search_buf_rev(unsigned char *buf, size_t buflen, unsigned char *needle,
               size_t maxidx, ssize_t *badchar, ssize_t *goodsfx)
{
        if (!maxidx)
                return memrchr(buf, *needle, buflen);

        buf += buflen - maxidx - 1;
        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 using the Boyer-Moore algorithm. */
static int
find_bytestr(struct file_priv *file, hed_cursor_t *from, int dir,
             unsigned char *needle, size_t len)
{
        void *dynalloc;
        ssize_t *badchar, *goodsfx;
        unsigned char *readbuf;
        unsigned char *p, *q;
        size_t remain;
        bool allzero;
        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;
        }

        assert(!hed_block_is_terminal(from->block));

        allzero = is_allzero(needle, len);
        --len;                  /* simplify offset computing */

        ret = HED_FINDOFF_NO_MATCH;
        if (dir < 0) {
                remain = -len;
                while (move_rel_fast(from, -remain),
                       ret && from->pos >= len) {

                        if (!hed_prepare_read(&file->f, from, SIZE_MAX)) {
                                ret = HED_FINDOFF_ERROR;
                                break;
                        }
                        remain = from->off;

                        if (remain < len) {
                                remain += len;
                                if (remain > from->pos)
                                        remain = from->pos;
                                move_rel_fast(from, -remain);
                                ++remain;
                                if (hed_file_cpin(&file->f, readbuf,
                                                  remain, from)) {
                                        remain = -len + 1;
                                        continue;
                                }
                                p = readbuf;
                        } else if (!hed_block_is_virtual(from->block)) {
                                p = from->block->dataobj->data +
                                        from->block->dataoff;
                                from->off -= remain;
                                from->pos -= remain;
                                ++remain;
                        } else if (!hed_block_is_bad(from->block) && allzero) {
                                ret = 0;
                                remain = len;
                                continue;
                        } else {
                                ++remain;
                                continue;
                        }

                        q = search_buf_rev(p, remain, needle, len,
                                           badchar, goodsfx);
                        if (q) {
                                ret = 0;
                                remain = p - q;
                        } else
                                remain = -len + 1;
                }
        } else {
                for ( ; ret && !hed_block_is_terminal(from->block);
                      move_rel_fast(from, remain)) {

                        remain = hed_prepare_read(&file->f, from, SIZE_MAX);
                        if (!remain) {
                                ret = HED_FINDOFF_ERROR;
                                break;
                        }

                        if (remain <= len) {
                                remain += len;
                                remain = copy_in(file, readbuf, remain, from);
                                if (remain) {
                                        remain -= len;
                                        continue;
                                }
                                p = readbuf;
                        } else if (!hed_block_is_virtual(from->block)) {
                                p = from->block->dataobj->data +
                                        from->block->dataoff + from->off;
                                from->off += remain;
                                from->pos += remain;
                        } else if (!hed_block_is_bad(from->block) && allzero) {
                                ret = 0;
                                remain = 0;
                                continue;
                        } else {
                                remain -= len;
                                continue;
                        }

                        q = search_buf(p, remain, needle, len,
                                       badchar, goodsfx);
                        if (q) {
                                ret = 0;
                                remain = q - p - remain;
                        } else
                                remain = -len;
                }
        }

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

static int
find_expr(struct file_priv *file, hed_cursor_t *from, int dir,
          struct hed_expr *expr)
{
        size_t len = hed_expr_len(expr);
        unsigned char *buf;

        if (!len)
                return HED_FINDOFF_NO_MATCH;

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

                if (hed_expr_eval(expr) & HED_AEF_ERROR)
                        return HED_FINDOFF_ERROR;
                buf = hed_expr_buf(expr);

                hed_dup_cursor(from, &match);
                p = NULL;       /* bogus assignment to silence a warning */
                remain = 0;
                for (pos = 0; pos < len; pos++) {
                        if (!remain) {
                                remain = hed_prepare_read(&file->f, &match,
                                                          SIZE_MAX);
                                if (!remain ||
                                    hed_block_is_bad(match.block))
                                        break;
                                p = hed_cursor_data(&match);
                                cursor_next_block(&match);
                        }
                        if ((p ? *p++ : 0) != buf[pos])
                                break;
                        remain--;
                }
                put_cursor(&match);

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

                if (dir < 0 && hed_block_is_terminal(from->block)) {
                        from->pos -= from->off;
                        from->off = 0;
                }
                move_rel_fast(from, dir);
                if (hed_block_is_terminal(from->block))
                        break;

                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 *f, hed_cursor_t *pos, int dir,
                   struct hed_expr *expr)
{
        struct file_priv *file = file_private(f);
        int res;

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

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

        return res;
}