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.tree;
  
The abstract class that defines the various representations used to represent an array of target pointers to children of an IN node. These arrays can be sparse, so the non-default representations are designed to make efficient representations for the sparse cases. Each specialized representation is a subclass of INTargetReps. A new IN node starts out with the None representation and grows through a sparse into the full default representation. Subsequently, the default representation can be compacted into a Sparse or None representation whenever an IN is stripped. Note that representations do not currently move to more compact forms when entries are nulled to minimize the possibility of tansitionary representation changes, since each representation change has a cpu cost and a gc cost associated with it.
 
 public abstract class INTargetRep
     extends INArrayRep<INTargetRepINTargetRep.TypeNode> {
 
     /* Single instance used for None rep. */
     public static final None NONE = new None();
 
     /* Enumeration for the different types of supported representations. */
     public enum Type { DEFAULT, SPARSE, NONE }
 
     public INTargetRep() {
     }
 
     /* The default non-sparse representation. It simply wraps an array. */
     public static class Default extends INTargetRep {
 
         /* The target nodes */
         private final Node[] targets;
 
         @Override
         public Type getType() {
             return .;
         }
 
         @Override
         public long calculateMemorySize() {
             return . +
                    MemoryBudget.objectArraySize(.);
         }
 
         public Default(int capacity) {
             this. = new Node[capacity];
         }
 
         /* Only for use by the Sizeof utility. */
         public Default(@SuppressWarnings("unused"SizeofMarker marker) {
              = null;
         }
 
         @Override
         public Node get(int idx) {
             return [idx];
         }
 
         @Override
         public INTargetRep set(int idxNode nodeIN parent) {
             [idx] = node;
             return this;
         }
 
         @Override
         public INTargetRep copy(int fromint toint nIN parent) {
             System.arraycopy(fromton);
             return this;
         }
 
         @Override
         public INTargetRep compact(IN parent) {
             int count = 0;
             for (Node target : ) {
                 if (target != null) {
                     count++;
                 }
             }
 
             if ((count > .) ||
                 (. > .)) {
                 return this;
             }
 
             INTargetRep newRep = null;
             if (count == 0) {
                 newRep = ;
            } else {
                newRep = new Sparse(.);
                for (int i=0; i < .i++) {
                    if ([i] != null) {
                        newRep.set(i[i], parent);
                    }
                }
            }
            noteRepChange(newRepparent);
            return newRep;
        }
        @Override
        public void updateCacheStats(@SuppressWarnings("unused")
                                     boolean increment,
                                     @SuppressWarnings("unused")
                                     Evictor evictor) {
            /* No stats for this default rep. */
        }
    }

    
Representation used when 1-4 children are cached. Note that the IN itself may have more children, but they are not currently cached. The INArrayRep is represented by two parallel arrays: an array of indices (idxs) and an array of values (targets). All elements that are not explicitly represented are null.
    public static class Sparse extends INTargetRep {
        /* The maximum number of entries that can be represented. */
        public static final int MAX_ENTRIES = 4;
        /* The maximum index that can be represented. */
        public static final int MAX_INDEX.;
        /*
         * The parallel arrays implementing the INArrayRep.
         */
        final short idxs[] = new short[];
        final Node targets[] = new Node[];
        @Override
        public Type getType() {
            return .;
        }
        @Override
        public long calculateMemorySize() {
            /*
             * Note that fixed array sizes are already accounted for in the
             * SPARSE_TARGET_ENTRY_OVERHEAD computed vis Sizeof.
             */
            return .;
        }
        public Sparse(int capacity) {
            /* Unroll initialization. */
            [0] = [1] = [2] = [3] = -1;
        }
        /* Only for use by the Sizeof utility. */
        public Sparse(@SuppressWarnings("unused"SizeofMarker marker) {
        }
        @Override
        public INTargetRep copy(int fromint toint nIN parent) {
            INTargetRep target = this;
            if ((to == from) || (n == 0)) {
                /* Nothing to do */
            } else if (to < from) {
                /* Copy ascending */
                for (int i = 0; i < ni++) {
                    target = target.set(to++, get(from++), parent);
                }
            } else {
                /* to > form. Copy descending */
                from += n;
                to += n;
                for (int i = 0; i < ni++) {
                    target = target.set(--toget(--from), parent);
                }
            }
            return target;
        }
        @Override
        public Node get(int j) {
            assert (j >= 0) && (j <= );
            /* Unrolled for loop */
            if ([0] == j) {
                return [0];
            }
            if ([1] == j) {
                return [1];
            }
            if ([2] == j) {
                return [2];
            }
            if ([3] == j) {
                return [3];
            }
            return null;
        }
        @Override
        public INTargetRep set(int jNode nodeIN parent) {
            assert (j >= 0) && (j <= );
            int slot = -1;
            for (int i=0; i < .i++) {
                if ([i] == j) {
                    [i] = node;
                    return this;
                }
                if ((slot < 0) && ([i] == null)) {
                   slot = i;
                }
            }
            /* Have a free slot, use it. */
            if (slot >= 0) {
                [slot] = node;
                [slot] = (short)j;
                return this;
            }
            /* It's full, mutate it. */
            Default fe = new Default(parent.getMaxEntries());
            noteRepChange(feparent);
            for (int i=0; i < .i++) {
                if ([i] != null) {
                    fe.set([i], [i], parent);
                }
            }
            return fe.set(jnodeparent);
        }
        @Override
        public INTargetRep compact(IN parent) {
            int count = 0;
            for (Node target : ) {
                if (target != null) {
                    count++;
                }
            }
            if (count == 0) {
                None newRep = ;
                noteRepChange(newRepparent);
                return newRep;
            }
            return this;
        }
        @Override
        public void updateCacheStats(boolean incrementEvictor evictor) {
            if (increment) {
                evictor.getNINSparseTarget().incrementAndGet();
            } else {
                evictor.getNINSparseTarget().decrementAndGet();
            }
        }
    }

    
Representation used when an IN has no children cached.
    public static class None extends INTargetRep {
        @Override
        public Type getType() {
            return .;
        }
        private None() {
        }
        /* Only for use by the Sizeof utility. */
        public None(@SuppressWarnings("unused"SizeofMarker marker) {
        }
        @Override
        public Node get(@SuppressWarnings("unused"int idx) {
            return null;
        }
        @Override
        public INTargetRep set(int idxNode nodeIN parent) {
            INTargetRep targets = new Sparse(parent.getMaxEntries());
            noteRepChange(targetsparent);
            return targets.set(idxnodeparent);
        }
        @Override
        public INTargetRep copy(@SuppressWarnings("unused"int from,
                                @SuppressWarnings("unused"int to,
                                @SuppressWarnings("unused"int n,
                                @SuppressWarnings("unused"IN parent) {
            /* Nothing to copy. */
            return this;
        }
        @Override
        public long calculateMemorySize() {
            /* A single static instance is used. */
            return 0;
        }
        @Override
        public INTargetRep compact(IN parent) {
            return this;
        }
        @Override
        public void updateCacheStats(boolean incrementEvictor evictor) {
            if (increment) {
                evictor.getNINNoTarget().incrementAndGet();
            } else {
                evictor.getNINNoTarget().decrementAndGet();
            }
        }
    }
New to GrepCode? Check out our FAQ X