+/**
+ * Overlay
+ */
+static struct {
+ struct Source source;
+ struct Region *table;
+ size_t count;
+ size_t limit;
+} overlay;
+
+static void usage();
+
+#define FRAG(m) (overlay.table+m)
+#define BEG(m) (FRAG(m)->pos)
+#define END(m) (FRAG(m)->pos + FRAG(m)->size)
+
+static ssize_t overlay_prior_fragment(off_t pos) {
+ size_t lo = 0, hi = overlay.count;
+ while ( lo < hi ) {
+ size_t m = ( lo + hi ) / 2;
+ if ( m == lo ) {
+ return BEG( m ) < pos? m : -1;
+ }
+ if ( BEG( m ) <= pos ) {
+ lo = m;
+ } else {
+ hi = m;
+ }
+ }
+ return -1;
+}
+
+static void overlay_save_count() {
+ lseek( overlay.source.fd, overlay.source.to, SEEK_SET );
+ size_t size = sizeof( overlay.count );
+ char *p = (char *) &overlay.count ;
+ while ( size > 0 ) {
+ size_t n = write( overlay.source.fd, p, size );
+ if ( n < 0 ) {
+ perror( overlay.source.filename );
+ exit( 1 );
+ }
+ size -= n;
+ p += n;
+ }
+ if ( overlay.source.dirty++ > 1000 ) {
+ fsync( overlay.source.fd );
+ overlay.source.dirty = 0;
+ }
+}
+
+static void overlay_save_table(size_t lo,size_t hi) {
+ char *p = (char *) FRAG(lo);
+ size_t pos = overlay.source.to + sizeof( overlay.count ) +
+ lo * sizeof( struct Region );
+ size_t size = ( hi - lo ) * sizeof( struct Region );
+ if ( pos != lseek( overlay.source.fd, pos, SEEK_SET ) ) {
+ fprintf( stderr, "%s: seek error\n", overlay.source.filename );
+ exit( 1 );
+ }
+ while ( size > 0 ) {
+ size_t n = write( overlay.source.fd, p, size );
+ if ( n < 0 ) {
+ perror( overlay.source.filename );
+ exit( 1 );
+ }
+ size -= n;
+ p += n;
+ }
+ if ( overlay.source.dirty++ > 1000 ) {
+ fsync( overlay.source.fd );
+ overlay.source.dirty = 0;
+ }
+}
+
+static void overlay_insert(size_t p,off_t pos,size_t size) {
+ size_t bytes;
+ if ( overlay.count >= overlay.limit ) {
+ overlay.limit = overlay.count + 10;
+ bytes = overlay.limit * sizeof( struct Region );
+ overlay.table = overlay.table?
+ realloc( overlay.table, bytes ) : malloc( bytes );
+ }
+ bytes = ( overlay.count++ - p ) * sizeof( struct Region );
+ if ( bytes ) {
+ memmove( FRAG( p+1 ), FRAG( p ), bytes );
+ }
+ FRAG( p )->pos = pos;
+ FRAG( p )->size = size;
+ overlay_save_count();
+}
+
+static void overlay_delete(size_t p) {
+ if ( p < --overlay.count ) {
+ size_t size = ( overlay.count - p ) * sizeof( struct Region );
+ memmove( FRAG(p), FRAG(p+1), size );
+ }
+ overlay_save_count();
+}
+
+static void overlay_mark(off_t pos,size_t size) {
+#if DEBUG
+ fprintf( stderr, "overlay_mark( %ld, %ld )\n", pos, size );
+#endif
+ int deleted = 0;
+ ssize_t q;
+ ssize_t p = overlay_prior_fragment( pos );
+ // p is the nearest region below pos (or -1)
+ if ( p >= 0 && pos <= END(p) ) {
+ // p overlaps mark region
+ if ( END(p) >= pos + size ) {
+#if DEBUG
+ fprintf( stderr, "overlay size 1( %ld )\n", FRAG(p)->size );
+#endif
+ return; // new mark within existing.
+ }
+ // new mark region extends existing
+ FRAG(p)->size = pos + size - BEG(p);
+ q = p+1;
+ while ( q < overlay.count && BEG(q) <= END(p) ) {
+ if ( END(q) > END(p) ) {
+ FRAG(p)->size = END(q) - BEG(p);
+ }
+ overlay_delete( q );
+ deleted++;
+ }
+ overlay_save_table( p, deleted? overlay.count : q );
+#if DEBUG
+ fprintf( stderr, "overlay size 2( %ld ) deleted %d\n",
+ FRAG(p)->size, deleted );
+#endif
+ return;
+ }
+ // The region p does not expand into new mark region
+ p++; // subsequent region
+ if ( p >= overlay.count || BEG(p) > pos + size ) {
+ // New mark is separate region at p
+ overlay_insert( p, pos, size);
+#if DEBUG
+ fprintf( stderr, "overlay size 4( %ld )\n", FRAG(p)->size );
+#endif
+ overlay_save_table( p, overlay.count );
+ return;
+ }
+ // New marks start before and overlap with the region
+ if ( BEG(p) + FRAG(p)->size < pos + size ) {
+ FRAG(p)->size = size; // new mark covers old region
+ } else {
+ FRAG(p)->size += BEG(p) - pos;
+ }
+ BEG(p) = pos;
+ q = p+1;
+ while ( q < overlay.count && BEG(q) <= END(p) ) {
+ if ( END(q) > END(p) ) {
+ FRAG(p)->size = END(q) - BEG(p);
+ }
+ overlay_delete( q );
+ deleted++;
+ }
+ overlay_save_table( p, deleted? overlay.count : q );
+#if DEBUG
+ fprintf( stderr, "overlay size 4( %ld ) deleted %d\n",
+ FRAG(p)->size, deleted );
+#endif
+}
+
+static void setup_overlay(char *filename) {
+ overlay.source.filename = filename;
+ overlay.source.fd = open( filename, O_RDWR | O_CREAT, S_IRUSR | S_IWUSR );
+ if ( overlay.source.fd < 0 ) {
+ perror( filename );
+ usage();
+ }
+}