Start line:  
End line:  

Snippet Preview

Snippet HTML Code

Stack Overflow Questions
  /*-
   * See the file LICENSE for redistribution information.
   *
   * Copyright (c) 2002, 2013 Oracle and/or its affiliates.  All rights reserved.
   *
   */
  
  package com.sleepycat.je.cleaner;
  
List of LSN offsets as a linked list of segments. The reasons for using a list of this type and not a java.util.List are:
  • Segements reduce memory overhead by storing long primitives rather than Long objects. Many longs per segment reduce link overhead.
  • Memory is only allocated for new segments, reducing the number of calls to update the memory budget.
  • This is an append-only list that supports a single appender thread and multiple unsynchronized reader threads. The caller is responsible for synchronizing such that only one thread calls add() at one time. The reader threads see data as it is changing but do not see inconsistent data (corrupt longs) and do not require synchronization for thread safety.

The algorithms here use traversal of the list segments rather than recursion to avoid using a lot of stack space.

 
 public class OffsetList {
 
     static final int SEGMENT_CAPACITY = 100;
 
     /*
      * Once the size of the list goes over this limit, we should not assert
      * (self-check) by doing sequential searches though the list.  Assertions
      * can't be too expensive or they interfere with normal operation.
      */
     static final int TOO_BIG_FOR_SELF_CHECK = 100;
 
     private Segment head;
     private Segment tail;
     private int size;
 
     public OffsetList() {
          = new Segment();
          = ;
     }

    
Adds the given value and returns whether a new segment was allocated.
 
     public boolean add(long valueboolean checkDupOffsets) {
 
         /* Each value added should be unique. */
         assert !checkDupOffsets ||
                 >  ||
                !contains(value) :
                LoggerUtils.getStackTrace
                    (new Exception("Dup Offset " + Long.toHexString(value)));
 
         /*
          * Do not increment the size until the value is added so that reader
          * threads do not try to read a value before it has been added.
          */
         Segment oldTail = ;
          = .add(value);
          += 1;
         return  != oldTail;
     }
 
     public int size() {
         return ;
     }

    
Merges the given list and returns whether a segment was freed.
 
     boolean merge(OffsetList other) {
 
         boolean oneSegFreed = true;
         Segment seg = other.head;
         while (true) {
             Segment next = seg.next();
             if (next != null) {
                 /* Insert a full segment at the beginning of the list. */
                 seg.setNext();
                  = seg;
                 seg = next;
             } else {
                 /* Copy the last segment and discard it. */
                 for (int i = 0; i < seg.size(); i += 1) {
                     if (add(seg.get(i), false)) {
                         /* The two partial segments did not fit into one. */
                         oneSegFreed = false;
                     }
                 }
                 break;
             }
        }
        return oneSegFreed;
    }

    
Returns an array of all values as longs. If a writer thread is appending to the list while this method is excuting, some values may be missing from the returned array, but the operation is safe.
    public long[] toArray() {
        long[] a = new long[];
        int next = 0;
        segments: for (Segment seg = seg != nullseg = seg.next()) {
            for (int i = 0; i < seg.size(); i += 1) {
                if (next >= a.length) {
                    break segments;
                }
                a[next] = seg.get(i);
                next += 1;
            }
        }
        return a;
    }

    
Returns whether this list contains the given offset.
    boolean contains(long offset) {
        for (Segment seg = seg != nullseg = seg.next()) {
            for (int i = 0; i < seg.size(); i += 1) {
                if (seg.get(i) == offset) {
                    return true;
                }
            }
        }
        return false;
    }

    
One segment of a OffsetList containing at most SEGMENT_CAPACITY values. public for Sizeof.
    public static class Segment {
        private int index;
        private Segment next;
        private final int[] values;
        /* public for Sizeof. */
        public Segment() {
             = new int[];
        }

        
Call this method on the tail. The new tail is returned, if allocating a new tail is necessary.
        Segment add(long value) {
            if ( < .) {
                /*
                 * Increment index after adding the offset so that reader
                 * threads won't see a partial long value.
                 */
                [] = (intvalue;
                 += 1;
                return this;
            } else {
                /*
                 * Add the value to the new segment before assigning the next
                 * field so that reader threads can rely on more values being
                 * available whenever the next field is non-null.
                 */
                Segment seg = new Segment();
                seg.values[0] = (intvalue;
                seg.index = 1;
                 = seg;
                return seg;
            }
        }

        
Returns the value at the given index from this segment only.
        long get(int i) {
            return ((long[i]) & 0xFFFFFFFF;
        }

        
Returns the next segment or null if this is the tail segment.
        Segment next() {
            return ;
        }

        
Sets the next pointer during a merge.
        void setNext(Segment next) {
            this. = next;
        }

        
Returns the number of values in this segment.
        int size() {
            return ;
        }
    }
New to GrepCode? Check out our FAQ X