Start line:  
End line:  

Snippet Preview

Snippet HTML Code

Stack Overflow Questions
  /*-
   * See the file LICENSE for redistribution information.
   *
   * Copyright (c) 2004, 2010 Oracle and/or its affiliates.  All rights reserved.
   *
   */
  
  package com.sleepycat.je.rep.util.ldiff;
  
 import java.util.List;
 
A rolling window of key/data pairs used by the ldiff algorithm.
 
 public class Window {
     private final Cursor cursor;
     private List<byte[]> window;
     private final MessageDigest md;
     private final int windowSize;
     private long chksum;
 
     /* The begin key/data pair of a window. */
     private byte[] beginKey;
     private byte[] beginData;
     /* The size of a different area. */
     private long diffSize;

    
Create a window of the given size, starting at the next record pointed at by the Cursor.

Parameters:
cursor an open cursor on the database being diff'd
windowSize the number of records to include in the window
Throws:
java.lang.Exception
 
     public Window(Cursor cursorint windowSize)
         throws Exception {
 
         this. = cursor;
         this. = windowSize;
         /* To compute a MD5 hash for each block. */
         try {
              = MessageDigest.getInstance("MD5");
         } catch (NoSuchAlgorithmException e) {
             e.printStackTrace();
             throw new Exception("MD5 hashes are required for ldiff.");
         }
 
         nextWindow();
     }

    
Roll a window forward by one key. The rolling checksum is adjusted to account for this move past one key/value pair. Note that the md5 hash associated with the window is computed on demand and is not updated here.
 
     public void rollWindow()
         throws Exception {
 
         DatabaseEntry key = new DatabaseEntry();
         DatabaseEntry data = new DatabaseEntry();
         if (.getNext(keydata.) ==
             .) {
             byte[] keyValue = LDiffUtil.concatByteArray(key.getData(),
                                                         data.getData());
             int removeXi = LDiffUtil.getXi(.remove(0));
             .add(keyValue);
             int addXi = LDiffUtil.getXi(keyValue);
             rollChecksum(removeXiaddXi);
         } else {
              = 0;
         }
         ++;
     }

    
Advance the window to the next block of records and update the rolling checksum.
 
     public void nextWindow() {
         /* DatabaseEntry represents the key and data of each record. */
         DatabaseEntry key = new DatabaseEntry();
         DatabaseEntry data = new DatabaseEntry();
         int i = 0;
          = new ArrayList<byte[]>();
          = 0;
 
         /* Please pay attention to the check order in while loop. */
         while ((i < ) &&
                (.getNext(keydata.) ==
                 .)) {
            if (i == 0) {
                 = key.getData();
                 = data.getData();
            }
            .add(LDiffUtil.concatByteArray(key.getData(),
                                                 data.getData()));
            i++;
        }
        setChecksum();
    }

    
The checksum for the window.

Returns:
the checksum for the window.
    public long getChecksum() {
        return ;
    }
    public byte[] getBeginKey() {
        return ;
    }
    public byte[] getBeginData() {
        return ;
    }
    public long getDiffSize() {
        return ;
    }

    
Compute the MD5 hash for the window. This is an expensive operation and should be used sparingly.

Returns:
the MD5 for the window.
    public byte[] getMd5Hash() {
        /* Reset the Message Digest first. */
        .reset();
        /* Feed the data into the Message Digest. */
        for (byte[] ba : ) {
            .update(ba);
        }
        return .digest();
    }

    
The number of records in the window. The size of the window will match the value set during instantiation, until the end of the database is reached.

Returns:
the number of records in the window.
    public int size() {
        return .size();
    }

    
We use the rsync rolling checksum algorithm with the following changes: 1. Each byte (Xi in the tech report) is replaced by a 32 bit Adler checksum of the bytes representing the concatenation of the key/value pair. 2. The value for M is 64 instead of 32 to reduce the chances of false collisions on the rolling checksum, given our adaptation of the original algorithm to logically use 32 bit bytes.
    private void setChecksum() {
        /* Adler32 to compute the rolling checksum of key/data pair. */
        Adler32 adler32 = new Adler32();
        int a = 0, b = 0;
        for (int i = 0; i < size(); i++) {
            byte[] element = .get(i);
            adler32.reset();
            adler32.update(element, 0, element.length);
            final int xi = (intadler32.getValue(); /* It's really 32 bits */
            a += xi;
            b += (xi * (size() - i));
        }
         = (a & .) | ((longb << 32);
    }

    
Update the checksum by removing removeXi and adding addXi, according to the rsync algorithm.

Parameters:
removeXi the value to remove from the checksum
addXi the value to add to the checksum
    private void rollChecksum(int removeXiint addXi) {
        final int a = (int - removeXi + addXi;
        final int b = (int) ( >> 32) - (removeXi * size()) + a;
         = (a & .) | ((longb << 32);
    }
New to GrepCode? Check out our FAQ X