org.spearce.jgit/src/org/spearce/jgit/lib/MergedTree.java

   1 /*
   2  *  Copyright (C) 2006  Shawn Pearce <spearce@spearce.org>
   3  *
   4  *  This library is free software; you can redistribute it and/or
   5  *  modify it under the terms of the GNU General Public
   6  *  License, version 2, as published by the Free Software Foundation.
   7  *
   8  *  This library is distributed in the hope that it will be useful,
   9  *  but WITHOUT ANY WARRANTY; without even the implied warranty of
  10  *  MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the GNU
  11  *  General Public License for more details.
  12  *
  13  *  You should have received a copy of the GNU General Public
  14  *  License along with this library; if not, write to the Free Software
  15  *  Foundation, Inc., 51 Franklin Street, Fifth Floor, Boston, MA  02110-1301
  16  */
  17 package org.spearce.jgit.lib;
  18
  19 import java.io.IOException;
  20
  21 public class MergedTree {
  22         public static final boolean isAdded(final TreeEntry[] ents) {
  23                 if (ents.length == 2) {
  24                         if (ents[0] == null && ents[1] != null)
  25                                 return true;
  26                         else if (ents[0] != null && ents[1] != null
  27                                         && ents[0].getClass() != ents[1].getClass())
  28                                 return true;
  29                 }
  30                 return false;
  31         }
  32
  33         public static final boolean isRemoved(final TreeEntry[] ents) {
  34                 if (ents.length == 2) {
  35                         if (ents[0] != null && ents[1] == null)
  36                                 return true;
  37                         else if (ents[0] != null && ents[1] != null
  38                                         && ents[0].getClass() != ents[1].getClass())
  39                                 return true;
  40                 }
  41                 return false;
  42         }
  43
  44         public static final boolean isModified(final TreeEntry[] ents) {
  45                 if (ents.length == 2 && ents[0] != null && ents[1] != null) {
  46                         if (ents[0].getId() == null || ents[1].getId() == null)
  47                                 return true;
  48                         else if (ents[0].getClass() == ents[1].getClass()
  49                                         && !ents[0].getId().equals(ents[1].getId()))
  50                                 return true;
  51                 }
  52                 return false;
  53         }
  54
  55         private static final int binarySearch(final TreeEntry[] entries,
  56                         final int width, final byte[] nameUTF8, final byte nameUTF8last, final int nameStart,
  57                         final int nameEnd) {
  58                 if (entries.length == 0)
  59                         return -1;
  60                 int high = entries.length / width;
  61                 int low = 0;
  62                 do {
  63                         final int mid = (low + high) / 2;
  64                         final int cmp;
  65                         int ix = mid * width;
  66                         while (entries[ix] == null)
  67                                 ix++;
  68                         cmp = Tree.compareNames(entries[ix].getNameUTF8(), nameUTF8,
  69                                         nameStart, nameEnd, TreeEntry.lastChar(entries[ix]), nameUTF8last);
  70                         if (cmp < 0)
  71                                 low = mid + 1;
  72                         else if (cmp == 0)
  73                                 return mid;
  74                         else
  75                                 high = mid;
  76                 } while (low < high);
  77                 return -(low + 1);
  78         }
  79
  80         private final Tree[] sources;
  81
  82         private TreeEntry[] merged;
  83
  84         private MergedTree[] subtrees;
  85
  86         public MergedTree(final Tree[] src) throws IOException {
  87                 if (src.length < 2)
  88                         throw new IllegalArgumentException("At least two trees are"
  89                                         + " required to compute a merge.");
  90                 sources = src;
  91                 matchByName();
  92         }
  93
  94         public boolean isModified() {
  95                 return isModified(sources);
  96         }
  97
  98         public TreeEntry[] findTop() {
  99                 return new TreeEntry[] { sources[0], sources[1] };
 100         }
 101
 102         public TreeEntry[] findMember(final String s, final byte slast) throws IOException {
 103                 return findMember(s.getBytes(Constants.CHARACTER_ENCODING), slast, 0);
 104         }
 105
 106         public TreeEntry[] findMember(final byte[] s, final byte slast, final int offset)
 107                         throws IOException {
 108                 final int srcCnt = sources.length;
 109                 int slash;
 110                 final int p;
 111
 112                 for (slash = offset; slash < s.length && s[slash] != '/'; slash++) {
 113                         // search for path component terminator
 114                 }
 115                 byte xlast = slash<s.length ? (byte)'/' : slast;
 116                 p = binarySearch(merged, srcCnt, s, xlast, offset, slash);
 117                 if (p < 0)
 118                         return null;
 119
 120                 if (slash == s.length) {
 121                         final TreeEntry[] r = new TreeEntry[srcCnt];
 122                         for (int j = 0, k = p * srcCnt; j < srcCnt; j++, k++)
 123                                 r[j] = merged[k];
 124                         return r;
 125                 }
 126
 127                 if (subtrees == null)
 128                         subtrees = new MergedTree[merged.length / srcCnt];
 129                 if (subtrees[p] == null) {
 130                         final Tree[] subs = new Tree[srcCnt];
 131                         for (int j = 0, k = p * srcCnt; j < srcCnt; j++, k++)
 132                                 subs[j] = merged[k] instanceof Tree ? (Tree) merged[k] : null;
 133                         subtrees[p] = new MergedTree(subs);
 134                 }
 135                 return subtrees[p].findMember(s, slast, slash + 1);
 136         }
 137
 138         public TreeEntry[] findBlobMember(String s) throws IOException {
 139                 return findMember(s,(byte)0);
 140         }
 141
 142         public TreeEntry[] findTreeMember(String s) throws IOException {
 143                 return findMember(s,(byte)'/');
 144         }
 145
 146         private void matchByName() throws IOException {
 147                 final int srcCnt = sources.length;
 148                 final int[] treeIndexes = new int[srcCnt];
 149                 final TreeEntry[][] entries = new TreeEntry[srcCnt][];
 150                 int pos = merged != null ? merged.length / srcCnt : 0;
 151                 int done = 0;
 152                 int treeId;
 153                 TreeEntry[] newMerged;
 154
 155                 for (int srcId = srcCnt - 1; srcId >= 0; srcId--) {
 156                         if (sources[srcId] != null) {
 157                                 final TreeEntry[] ents = sources[srcId].members();
 158                                 entries[srcId] = ents;
 159                                 pos = Math.max(pos, ents.length);
 160                                 if (ents.length == 0)
 161                                         done++;
 162                         } else {
 163                                 entries[srcId] = Tree.EMPTY_TREE;
 164                                 done++;
 165                         }
 166                 }
 167
 168                 if (done == srcCnt) {
 169                         merged = Tree.EMPTY_TREE;
 170                         return;
 171                 }
 172
 173                 newMerged = new TreeEntry[pos * srcCnt];
 174                 for (pos = 0, treeId = 0; done < srcCnt; pos += srcCnt, treeId++) {
 175                         byte[] minName = null;
 176                         int minNameLast = 0;
 177
 178                         if ((pos + srcCnt) >= newMerged.length) {
 179                                 final TreeEntry[] t = new TreeEntry[newMerged.length * 2];
 180                                 for (int j = newMerged.length - 1; j >= 0; j--)
 181                                         t[j] = newMerged[j];
 182                                 newMerged = t;
 183                         }
 184
 185                         for (int srcId = 0; srcId < srcCnt; srcId++) {
 186                                 final int ti = treeIndexes[srcId];
 187                                 final TreeEntry[] ents = entries[srcId];
 188                                 if (ti == ents.length)
 189                                         continue;
 190
 191                                 final TreeEntry thisEntry = ents[ti];
 192                                 final int cmp = minName == null ? -1 : Tree.compareNames(
 193                                                 thisEntry.getNameUTF8(), minName, TreeEntry.lastChar(thisEntry), minNameLast);
 194
 195                                 if (cmp < 0) {
 196                                         minName = thisEntry.getNameUTF8();
 197                                         minNameLast = TreeEntry.lastChar(thisEntry);
 198                                         for (int j = srcId - 1; j >= 0; j--) {
 199                                                 if (newMerged[pos + j] != null) {
 200                                                         newMerged[pos + j] = null;
 201                                                         if (treeIndexes[j]-- == entries[j].length)
 202                                                                 done--;
 203                                                 }
 204                                         }
 205                                 }
 206
 207                                 if (cmp <= 0) {
 208                                         newMerged[pos + srcId] = thisEntry;
 209                                         if (++treeIndexes[srcId] == ents.length)
 210                                                 done++;
 211                                 }
 212                         }
 213                 }
 214
 215                 if (newMerged.length == pos)
 216                         merged = newMerged;
 217                 else {
 218                         merged = new TreeEntry[pos];
 219                         for (int j = pos - 1; j >= 0; j--)
 220                                 merged[j] = newMerged[j];
 221                 }
 222         }
 223 }