text: package org.basex.io.random;
  
  import static org.basex.data.DataText.*;
  
  import java.io.*;
  import java.nio.channels.*;
  import java.util.*;
  
  import org.basex.core.*;
  import org.basex.data.*;
  import org.basex.io.*;
  import org.basex.io.in.DataInput;
  import org.basex.io.out.DataOutput;
  import org.basex.util.*;
  
  /**
   * This class stores the table on disk and reads it page-wise.
   *
   * @author BaseX Team 2005-20, BSD License
   * @author Christian Gruen
   * @author Tim Petrowsky
   */
  public final class TableDiskAccess extends TableAccess {
    /** Buffer manager. */
    private final Buffers buffers = new Buffers();
    /** File storing all pages. */
    private final RandomAccessFile file;
    /** Bitmap storing free (=0) and used (=1) pages. */
    private BitArray usedPages;
    /** File lock. */
    private FileLock lock;
  
    /** First pre values (ascending order); will be initialized with the first update. */
    private int[] fPreIndex;
    /** Page index; will be initialized with the first update. */
    private int[] pageIndex;
    /** Total number of pages. */
    private int pages;
    /** Number of used pages. */
    private int used;
  
    /** Pointer to current page. */
    private int page = -1;
    /** Pre value of the first entry in the current page. */
    private int firstPre = -1;
    /** First pre value of the next page. */
    private int nextPre = -1;
  
    /**
     * Constructor.
     * @param meta meta data
     * @param write write lock
     * @throws IOException I/O exception
     */
    public TableDiskAccess(final MetaData meta, final boolean write) throws IOException {
      super(meta);
  
      // read meta and index data
      try(DataInput in = new DataInput(meta.dbFile(DATATBL + 'i'))) {
        // total number of pages
        pages = in.readNum();
        // number of used pages (0: empty table; MAX: no mapping)
        used = in.readNum();
        if(used == Integer.MAX_VALUE) {
          // no mapping: total and used number of pages is identical
          used = pages;
        } else if(used != 0) {
          // read page index and first pre values from disk
          fPreIndex = in.readNums();
          pageIndex = in.readNums();
          // read block bitmap
          final int s = in.readNum();
          usedPages = new BitArray(in.readLongs(s), used);
        }
      }
  
      // initialize data file
      file = new RandomAccessFile(meta.dbFile(DATATBL).file(), "rw");
      if(!lock(write)) throw new BaseXException(Text.DB_PINNED_X, meta.name);
    }
  
    /**
     * Checks if the table of the specified database is locked.
     * @param db name of database
     * @param ctx database context
     * @return result of check
     */
    public static boolean locked(final String db, final Context ctx) {
      final IOFile table = MetaData.file(ctx.soptions.dbPath(db), DATATBL);
      if(!table.exists()) return false;
  
      try(FileChannel fc = new RandomAccessFile(table.file(), "rw").getChannel()) {
        return fc.tryLock() == null;
      } catch(final IOException ex) {
        Util.debug(ex);
        return true;
      }
    }
  
    @Override
    public synchronized void flush(final boolean all) throws IOException {
      for(final Buffer buffer : buffers.all()) {
        write(buffer);
      }
      if(!dirty || !all) return;
  
      try(DataOutput out = new DataOutput(meta.dbFile(DATATBL + 'i'))) {
        final int p = pages;
        boolean regular = true;
  
        // check if page mapping is regular (are all pages used and in ascending order?)
        if(fPreIndex != null) {
          regular = p == used;
          for(int i = 0; i < p && regular; i++) regular = fPreIndex[i] == i * IO.ENTRIES;
          for(int i = 0; i < p && regular; i++) regular = pageIndex[i] == i;
          if(regular) removeMapping();
        }
  
        if(regular) {
          // no mapping available or required (0: empty table; MAX: no mapping, see TableOutput#close)
          out.writeNum(p);
          out.writeNum(used == 0 ? 0 : Integer.MAX_VALUE);
        } else {
          out.writeNum(p);
          out.writeNum(used);
          out.writeNum(p);
          for(int s = 0; s < p; s++) out.writeNum(fPreIndex[s]);
          out.writeNum(p);
          for(int s = 0; s < p; s++) out.writeNum(pageIndex[s]);
          out.writeLongs(usedPages.toArray());
        }
      }
      dirty = false;
    }
  
    @Override
    public synchronized void close() throws IOException {
      flush(true);
      file.close();
    }
  
    @Override
    public boolean lock(final boolean write) {
      try {
        if(lock != null) {
          if(write != lock.isShared()) return true;
          lock.release();
        }
        lock = file.getChannel().tryLock(0, Long.MAX_VALUE, !write);
        return lock != null;
      } catch(final IOException ex) {
        throw Util.notExpected(ex);
      }
    }
  
    @Override
    public synchronized int read1(final int pre, final int offset) {
      final int o = offset + cursor(pre);
      final byte[] data = buffers.current().data;
      return data[o] & 0xFF;
    }
  
    @Override
    public synchronized int read2(final int pre, final int offset) {
      final int o = offset + cursor(pre);
      final byte[] data = buffers.current().data;
      return ((data[o] & 0xFF) << 8) + (data[o + 1] & 0xFF);
    }
  
    @Override
    public synchronized int read4(final int pre, final int offset) {
      final int o = offset + cursor(pre);
      final byte[] data = buffers.current().data;
      return ((data[o] & 0xFF) << 24) + ((data[o + 1] & 0xFF) << 16) +
        ((data[o + 2] & 0xFF) << 8) + (data[o + 3] & 0xFF);
    }
  
    @Override
    public synchronized long read5(final int pre, final int offset) {
      final int o = offset + cursor(pre);
      final byte[] data = buffers.current().data;
      return ((long) (data[o] & 0xFF) << 32) + ((long) (data[o + 1] & 0xFF) << 24) +
        ((data[o + 2] & 0xFF) << 16) + ((data[o + 3] & 0xFF) << 8) + (data[o + 4] & 0xFF);
    }
  
    @Override
    public void write1(final int pre, final int offset, final int value) {
      final int o = offset + cursor(pre);
      final Buffer buffer = buffers.current();
      buffer.data[o] = (byte) value;
      buffer.dirty = true;
    }
  
    @Override
    public void write2(final int pre, final int offset, final int value) {
      final int o = offset + cursor(pre);
      final Buffer buffer = buffers.current();
      final byte[] data = buffer.data;
      data[o] = (byte) (value >>> 8);
      data[o + 1] = (byte) value;
      buffer.dirty = true;
    }
  
    @Override
    public void write4(final int pre, final int offset, final int value) {
      final int o = offset + cursor(pre);
      final Buffer buffer = buffers.current();
      final byte[] data = buffer.data;
      data[o]     = (byte) (value >>> 24);
      data[o + 1] = (byte) (value >>> 16);
      data[o + 2] = (byte) (value >>> 8);
      data[o + 3] = (byte) value;
      buffer.dirty = true;
    }
  
    @Override
    public void write5(final int pre, final int offset, final long value) {
      final int o = offset + cursor(pre);
      final Buffer buffer = buffers.current();
      final byte[] data = buffer.data;
      data[o]     = (byte) (value >>> 32);
      data[o + 1] = (byte) (value >>> 24);
      data[o + 2] = (byte) (value >>> 16);
      data[o + 3] = (byte) (value >>> 8);
      data[o + 4] = (byte) value;
      buffer.dirty = true;
    }
  
    @Override
    protected void copy(final byte[] entries, final int pre, final int last) {
      for(int o = 0, i = pre; i < last; ++i, o += IO.NODESIZE) {
        final int off = cursor(i);
        final Buffer buffer = buffers.current();
        Array.copy(entries, o, IO.NODESIZE, buffer.data, off);
        buffer.dirty = true;
      }
    }
  
    @Override
    public void delete(final int pre, final int count) {
      if(count == 0) return;
  
      // get first page
      dirty();
      cursor(pre);
  
      // some useful variables to make code more readable
      int from = pre - firstPre;
      final int last = pre + count;
  
      // check if all entries are in current page
      if(last <= nextPre) {
        // move entries in current page and decreases pointers to pre values
        if(last < nextPre) delete(buffers.current(), from, from + count, nextPre - last);
        decreasePre(count);
  
        // if whole page was deleted, remove it from the index
        if(firstPre == nextPre) {
          // mark the page as empty
          usedPages.clear(pageIndex[page]);
          deletePages(1);
          readPage(page);
        }
      } else {
        // handle pages whose entries are to be deleted entirely
  
        // first count them
        int unused = 0;
        while(last > nextPre) {
          if(from == 0) {
            ++unused;
            // mark the pages as empty; range clear cannot be used because the
            // pages may not be consecutive
            usedPages.clear(pageIndex[page]);
          }
          setPage(page + 1);
          from = 0;
        }
  
        // if the last page is empty, clear the corresponding bit
        read(pageIndex[page]);
        final Buffer buffer = buffers.current();
        if(last == nextPre) {
          usedPages.clear((int) buffer.pos);
          ++unused;
          if(page + 1 < used) readPage(page + 1);
          else ++page;
        } else {
          // delete entries at beginning of current (last) page
          delete(buffer, 0, last - firstPre, nextPre - last);
        }
  
        // now remove them from the index
        if(unused > 0) {
          page -= unused;
          deletePages(unused);
        }
  
        // update index entry for this page
        fPreIndex[page] = pre;
        firstPre = pre;
        decreasePre(count);
      }
      if(used == 0) {
        buffers.init();
        removeMapping();
        pages = 1;
      }
    }
  
    @Override
    public void insert(final int pre, final byte[] entries) {
      final int nnew = entries.length;
      if(nnew == 0) return;
      dirty();
  
      // number of entries to be inserted
      final int nr = nnew >>> IO.NODEPOWER;
  
      int split = 0;
      if(used == 0) {
        // special case: insert new data into first page if database is empty
        readPage(0);
        usedPages.set(0);
        ++used;
      } else if(pre > 0) {
        // find the offset within the page where the new records will be inserted
        split = cursor(pre - 1) + IO.NODESIZE;
      }
  
      // number of bytes occupied by old records in the current page
      final int nold = nextPre - firstPre << IO.NODEPOWER;
      // number of bytes occupied by old records which will be moved at the end
      final int moved = nold - split;
  
      // special case: all entries fit in the current page
      Buffer buffer = buffers.current();
      if(nold + nnew <= IO.BLOCKSIZE) {
        Array.insert(buffer.data, split, nnew, nold, entries);
        buffer.dirty = true;
  
        // increment first pre-values of pages after the last modified page
        for(int i = page + 1; i < used; ++i) fPreIndex[i] += nr;
        // update cached variables (fpre is not changed)
        nextPre += nr;
        meta.size += nr;
        return;
      }
  
      // append old entries at the end of the new entries
      final byte[] all = new byte[nnew + moved];
      Array.copy(entries, nnew, all);
      Array.copy(buffer.data, split, moved, all, nnew);
  
      // fill in the current page with new entries
      // number of bytes which fit in the first page
      int nrem = IO.BLOCKSIZE - split;
      if(nrem > 0) {
        Array.copyFromStart(all, nrem, buffer.data, split);
        buffer.dirty = true;
      }
  
      // number of new required pages and remaining bytes
      final int req = all.length - nrem;
      int needed = req / IO.BLOCKSIZE;
      final int remain = req % IO.BLOCKSIZE;
  
      if(remain > 0) {
        // check if the last entries can fit in the page after the current one
        if(page + 1 < used) {
          final int o = occSpace(page + 1) << IO.NODEPOWER;
          if(remain <= IO.BLOCKSIZE - o) {
            // copy the last records
            readPage(page + 1);
            buffer = buffers.current();
            Array.copyFromStart(buffer.data, o, buffer.data, remain);
            Array.copyToStart(all, all.length - remain, remain, buffer.data);
            buffer.dirty = true;
            // reduce the pre value, since it will be later incremented with nr
            fPreIndex[page] -= remain >>> IO.NODEPOWER;
            // go back to the previous page
            readPage(page - 1);
          } else {
            // there is not enough space in the page - allocate a new one
            ++needed;
          }
        } else {
          // this is the last page - allocate a new one
          ++needed;
        }
      }
  
      // number of expected pages: existing pages + needed page - empty pages
      final int exp = pages + needed - (pages - used);
      if(exp > fPreIndex.length) {
        // resize directory arrays if existing ones are too small
        final int ns = Math.max(fPreIndex.length << 1, exp);
        fPreIndex = Arrays.copyOf(fPreIndex, ns);
        pageIndex = Arrays.copyOf(pageIndex, ns);
      }
  
      // make place for the pages where the new entries will be written
      Array.insert(fPreIndex, page + 1, needed, used, null);
      Array.insert(pageIndex, page + 1, needed, used, null);
  
      // write the all remaining entries
      while(needed-- > 0) {
        final int p = usedPages.nextFree();
        usedPages.set(p);
        read(p);
        ++used;
        ++page;
        nrem += write(all, nrem);
        fPreIndex[page] = fPreIndex[page - 1] + IO.ENTRIES;
        pageIndex[page] = (int) buffers.current().pos;
      }
  
      // increment all fpre values after the last modified page
      for(int i = page + 1; i < used; ++i) fPreIndex[i] += nr;
  
      meta.size += nr;
  
      // update cached variables
      firstPre = fPreIndex[page];
      nextPre = page + 1 < used && fPreIndex[page + 1] < meta.size ? fPreIndex[page + 1] : meta.size;
    }
  
    @Override
    protected void dirty() {
      // initialize data structures required for performing updates
      if(fPreIndex == null) {
        fPreIndex = new int[pages];
        for(int i = 0; i < pages; i++) fPreIndex[i] = i * IO.ENTRIES;
        pageIndex = new int[pages];
        for(int i = 0; i < pages; i++) pageIndex[i] = i;
        usedPages = new BitArray(used, true);
      }
      dirty = true;
    }
  
    @Override
    public String toString() {
      final StringBuilder sb = new StringBuilder();
      sb.append(Util.className(this)).append(" (").append("pages: ").append(pages);
      sb.append(", used: ").append(used).append(", page: ").append(page);
      sb.append(", firstPre: ").append(firstPre).append(", nextPre: ").append(nextPre).append(")");
      if(fPreIndex != null) sb.append("\n- FPres: ").append(Arrays.toString(fPreIndex));
      if(pageIndex != null) sb.append("\n- Pages: ").append(Arrays.toString(pageIndex));
      if(usedPages != null) sb.append("\n- Used Pages: ").append(usedPages);
      return sb.toString();
    }
  
    // PRIVATE METHODS ==============================================================================
  
    /**
     * Searches for the page containing the entry for the specified pre value.
     * Reads the page and returns its offset inside the page.
     * @param pre pre of the entry to search for
     * @return offset of the entry in the page
     */
    private int cursor(final int pre) {
      int fp = firstPre, np = nextPre;
      if(pre < fp || pre >= np) {
        final int last = used - 1;
        int l = 0, h = last, m = page;
        while(l <= h) {
          if(pre < fp) h = m - 1;
          else if(pre >= np) l = m + 1;
          else break;
          m = h + l >>> 1;
          fp = fpre(m);
          np = m == last ? meta.size : fpre(m + 1);
        }
        if(l > h) throw Util.notExpected(
            "Data Access out of bounds:" +
            "\n- pre value: " + pre +
            "\n- table size: " + meta.size +
            "\n- first/next pre value: " + fp + '/' + np +
            "\n- #total/used pages: " + pages + '/' + used +
            "\n- accessed page: " + m + " (" + l + " > " + h + ']');
        readPage(m);
      }
      return pre - firstPre << IO.NODEPOWER;
    }
  
    /**
     * Updates the page pointers.
     * @param pre page index
     */
    private void setPage(final int pre) {
      page = pre;
      firstPre = fpre(pre);
      nextPre = pre + 1 >= used ? meta.size : fpre(pre + 1);
    }
  
    /**
     * Updates the index pointers and fetches the requested page.
     * @param pre page index
     */
    private void readPage(final int pre) {
      setPage(pre);
      read(pageIndex == null ? pre : pageIndex[pre]);
    }
  
    /**
     * Return the specified pre value.
     * @param pre index of the page to fetch
     * @return pre value
     */
    private int fpre(final int pre) {
      return fPreIndex == null ? pre * IO.ENTRIES : fPreIndex[pre];
    }
  
    /**
     * Reads a page from disk.
     * @param pre page to fetch
     */
    private void read(final int pre) {
      if(!buffers.cursor(pre)) return;
  
      final Buffer buffer = buffers.current();
      try {
        write(buffer);
        buffer.pos = pre;
        if(pre >= pages) {
          pages = pre + 1;
        } else {
          file.seek(buffer.pos * IO.BLOCKSIZE);
          file.readFully(buffer.data);
        }
      } catch(final IOException ex) {
        Util.stack(ex);
      }
    }
  
    /**
     * Writes the specified buffer to disk and resets the dirty flag.
     * @param buffer buffer to write
     * @throws IOException I/O exception
     */
    private void write(final Buffer buffer) throws IOException {
      if(!buffer.dirty) return;
  
      file.seek(buffer.pos * IO.BLOCKSIZE);
      file.write(buffer.data);
      buffer.dirty = false;
    }
  
    /**
     * Deletes pages in the page mapping.
     * @param count number of pages to delete
     */
    private void deletePages(final int count) {
      Array.remove(fPreIndex, page, count, used);
      Array.remove(pageIndex, page, count, used);
      used -= count;
    }
  
    /**
     * Decreases pointers to pre value.
     * @param count number of entries to move
     */
    private void decreasePre(final int count) {
      final int nextPage = page + 1;
      for(int i = nextPage; i < used; ++i) fPreIndex[i] -= count;
      meta.size -= count;
      nextPre = nextPage < used && fPreIndex[nextPage] < meta.size ? fPreIndex[nextPage] : meta.size;
    }
  
    /**
     * Convenience method for deleting buffer entries.
     * @param buffer buffer
     * @param from first entry to delete
     * @param to last entry to delete
     * @param length source length
     */
    private static void delete(final Buffer buffer, final int from, final int to, final int length) {
      final byte[] array = buffer.data;
      Array.copy(array, to << IO.NODEPOWER, length << IO.NODEPOWER, array, from << IO.NODEPOWER);
      buffer.dirty = true;
    }
  
    /**
     * Fills the current buffer with bytes from the specified array and offset.
     * @param array source array
     * @param offset array offset
     * @return number of written bytes
     */
    private int write(final byte[] array, final int offset) {
      final Buffer buffer = buffers.current();
      final int len = Math.min(IO.BLOCKSIZE, array.length - offset);
      Array.copyToStart(array, offset, len, buffer.data);
      buffer.dirty = true;
      return len;
    }
  
    /**
     * Calculates the occupied space in a page.
     * @param index page index
     * @return occupied space in number of records
     */
    private int occSpace(final int index) {
      return (index + 1 < used ? fPreIndex[index + 1] : meta.size) - fPreIndex[index];
    }
  
    /**
     * Removes the page index.
     */
    private void removeMapping() {
      fPreIndex = null;
      pageIndex = null;
      usedPages = null;
    }
  }
  