org.spearce.jgit/src/org/spearce/jgit/revwalk/BlockObjQueue.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 class BlockObjQueue {
  41         private BlockFreeList free;
  42
  43         private Block head;
  44
  45         private Block tail;
  46
  47         /** Create an empty queue. */
  48         BlockObjQueue() {
  49                 free = new BlockFreeList();
  50         }
  51
  52         void add(final RevObject c) {
  53                 Block b = tail;
  54                 if (b == null) {
  55                         b = free.newBlock();
  56                         b.add(c);
  57                         head = b;
  58                         tail = b;
  59                         return;
  60                 } else if (b.isFull()) {
  61                         b = free.newBlock();
  62                         tail.next = b;
  63                         tail = b;
  64                 }
  65                 b.add(c);
  66         }
  67
  68         RevObject next() {
  69                 final Block b = head;
  70                 if (b == null)
  71                         return null;
  72
  73                 final RevObject c = b.pop();
  74                 if (b.isEmpty()) {
  75                         head = b.next;
  76                         if (head == null)
  77                                 tail = null;
  78                         free.freeBlock(b);
  79                 }
  80                 return c;
  81         }
  82
  83         static final class BlockFreeList {
  84                 private Block next;
  85
  86                 Block newBlock() {
  87                         Block b = next;
  88                         if (b == null)
  89                                 return new Block();
  90                         next = b.next;
  91                         b.clear();
  92                         return b;
  93                 }
  94
  95                 void freeBlock(final Block b) {
  96                         b.next = next;
  97                         next = b;
  98                 }
  99         }
 100
 101         static final class Block {
 102                 private static final int BLOCK_SIZE = 256;
 103
 104                 /** Next block in our chain of blocks; null if we are the last. */
 105                 Block next;
 106
 107                 /** Our table of queued objects. */
 108                 final RevObject[] objects = new RevObject[BLOCK_SIZE];
 109
 110                 /** Next valid entry in {@link #objects}. */
 111                 int headIndex;
 112
 113                 /** Next free entry in {@link #objects} for addition at. */
 114                 int tailIndex;
 115
 116                 boolean isFull() {
 117                         return tailIndex == BLOCK_SIZE;
 118                 }
 119
 120                 boolean isEmpty() {
 121                         return headIndex == tailIndex;
 122                 }
 123
 124                 void add(final RevObject c) {
 125                         objects[tailIndex++] = c;
 126                 }
 127
 128                 RevObject pop() {
 129                         return objects[headIndex++];
 130                 }
 131
 132                 void clear() {
 133                         next = null;
 134                         headIndex = 0;
 135                         tailIndex = 0;
 136                 }
 137         }
 138 }