org.spearce.jgit/src/org/spearce/jgit/revwalk/RevObjectList.java

   1 /*
   2  * Copyright (C) 2008, Shawn O. Pearce <spearce@spearce.org>
   3  *
   4  * All rights reserved.
   5  *
   6  * Redistribution and use in source and binary forms, with or
   7  * without modification, are permitted provided that the following
   8  * conditions are met:
   9  *
  10  * - Redistributions of source code must retain the above copyright
  11  *   notice, this list of conditions and the following disclaimer.
  12  *
  13  * - Redistributions in binary form must reproduce the above
  14  *   copyright notice, this list of conditions and the following
  15  *   disclaimer in the documentation and/or other materials provided
  16  *   with the distribution.
  17  *
  18  * - Neither the name of the Git Development Community nor the
  19  *   names of its contributors may be used to endorse or promote
  20  *   products derived from this software without specific prior
  21  *   written permission.
  22  *
  23  * THIS SOFTWARE IS PROVIDED BY THE COPYRIGHT HOLDERS AND
  24  * CONTRIBUTORS "AS IS" AND ANY EXPRESS OR IMPLIED WARRANTIES,
  25  * INCLUDING, BUT NOT LIMITED TO, THE IMPLIED WARRANTIES
  26  * OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE
  27  * ARE DISCLAIMED. IN NO EVENT SHALL THE COPYRIGHT OWNER OR
  28  * CONTRIBUTORS BE LIABLE FOR ANY DIRECT, INDIRECT, INCIDENTAL,
  29  * SPECIAL, EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING, BUT
  30  * NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES;
  31  * LOSS OF USE, DATA, OR PROFITS; OR BUSINESS INTERRUPTION) HOWEVER
  32  * CAUSED AND ON ANY THEORY OF LIABILITY, WHETHER IN CONTRACT,
  33  * STRICT LIABILITY, OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE)
  34  * ARISING IN ANY WAY OUT OF THE USE OF THIS SOFTWARE, EVEN IF
  35  * ADVISED OF THE POSSIBILITY OF SUCH DAMAGE.
  36  */
  37
  38 package org.spearce.jgit.revwalk;
  39
  40 import java.util.AbstractList;
  41
  42 /**
  43  * An ordered list of {@link RevObject} subclasses.
  44  *
  45  * @param <E>
  46  *            type of subclass of RevObject the list is storing.
  47  */
  48 public class RevObjectList<E extends RevObject> extends AbstractList<E> {
  49         static final int BLOCK_SHIFT = 8;
  50
  51         static final int BLOCK_SIZE = 1 << BLOCK_SHIFT;
  52
  53         Block contents;
  54
  55         int size;
  56
  57         /** Create an empty object list. */
  58         public RevObjectList() {
  59                 clear();
  60         }
  61
  62         public void add(final int index, final E element) {
  63                 if (index != size)
  64                         throw new UnsupportedOperationException("Not add-at-end: " + index);
  65                 set(index, element);
  66                 size++;
  67         }
  68
  69         public E set(int index, E element) {
  70                 Block s = contents;
  71                 while (index >> s.shift >= BLOCK_SIZE) {
  72                         s = new Block(s.shift + BLOCK_SHIFT);
  73                         s.contents[0] = contents;
  74                         contents = s;
  75                 }
  76                 while (s.shift > 0) {
  77                         final int i = index >> s.shift;
  78                         index -= i << s.shift;
  79                         if (s.contents[i] == null)
  80                                 s.contents[i] = new Block(s.shift - BLOCK_SHIFT);
  81                         s = (Block) s.contents[i];
  82                 }
  83                 final Object old = s.contents[index];
  84                 s.contents[index] = element;
  85                 return (E) old;
  86         }
  87
  88         public E get(int index) {
  89                 Block s = contents;
  90                 if (index >> s.shift >= 1024)
  91                         return null;
  92                 while (s != null && s.shift > 0) {
  93                         final int i = index >> s.shift;
  94                         index -= i << s.shift;
  95                         s = (Block) s.contents[i];
  96                 }
  97                 return s != null ? (E) s.contents[index] : null;
  98         }
  99
 100         public int size() {
 101                 return size;
 102         }
 103
 104         @Override
 105         public void clear() {
 106                 contents = new Block(0);
 107                 size = 0;
 108         }
 109
 110         static class Block {
 111                 final Object[] contents = new Object[BLOCK_SIZE];
 112
 113                 final int shift;
 114
 115                 Block(final int s) {
 116                         shift = s;
 117                 }
 118         }
 119 }