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[] findMember(final String s, final byte slast) throws IOException {
  99                 return findMember(s.getBytes(Constants.CHARACTER_ENCODING), slast, 0);
 100         }
 101
 102         public TreeEntry[] findMember(final byte[] s, final byte slast, final int offset)
 103                         throws IOException {
 104                 final int srcCnt = sources.length;
 105                 int slash;
 106                 final int p;
 107
 108                 for (slash = offset; slash < s.length && s[slash] != '/'; slash++) {
 109                         // search for path component terminator
 110                 }
 111                 byte xlast = slash<s.length ? (byte)'/' : slast;
 112                 p = binarySearch(merged, srcCnt, s, xlast, offset, slash);
 113                 if (p < 0)
 114                         return null;
 115
 116                 if (slash == s.length) {
 117                         final TreeEntry[] r = new TreeEntry[srcCnt];
 118                         for (int j = 0, k = p * srcCnt; j < srcCnt; j++, k++)
 119                                 r[j] = merged[k];
 120                         return r;
 121                 }
 122
 123                 if (subtrees == null)
 124                         subtrees = new MergedTree[merged.length / srcCnt];
 125                 if (subtrees[p] == null) {
 126                         final Tree[] subs = new Tree[srcCnt];
 127                         for (int j = 0, k = p * srcCnt; j < srcCnt; j++, k++)
 128                                 subs[j] = merged[k] instanceof Tree ? (Tree) merged[k] : null;
 129                         subtrees[p] = new MergedTree(subs);
 130                 }
 131                 return subtrees[p].findMember(s, slast, slash + 1);
 132         }
 133
 134         public TreeEntry[] findBlobMember(String s) throws IOException {
 135                 return findMember(s,(byte)0);
 136         }
 137
 138         public TreeEntry[] findTreeMember(String s) throws IOException {
 139                 return findMember(s,(byte)'/');
 140         }
 141
 142         private void matchByName() throws IOException {
 143                 final int srcCnt = sources.length;
 144                 final int[] treeIndexes = new int[srcCnt];
 145                 final TreeEntry[][] entries = new TreeEntry[srcCnt][];
 146                 int pos = merged != null ? merged.length / srcCnt : 0;
 147                 int done = 0;
 148                 int treeId;
 149                 TreeEntry[] newMerged;
 150
 151                 for (int srcId = srcCnt - 1; srcId >= 0; srcId--) {
 152                         if (sources[srcId] != null) {
 153                                 final TreeEntry[] ents = sources[srcId].members();
 154                                 entries[srcId] = ents;
 155                                 pos = Math.max(pos, ents.length);
 156                                 if (ents.length == 0)
 157                                         done++;
 158                         } else {
 159                                 entries[srcId] = Tree.EMPTY_TREE;
 160                                 done++;
 161                         }
 162                 }
 163
 164                 if (done == srcCnt) {
 165                         merged = Tree.EMPTY_TREE;
 166                         return;
 167                 }
 168
 169                 newMerged = new TreeEntry[pos * srcCnt];
 170                 for (pos = 0, treeId = 0; done < srcCnt; pos += srcCnt, treeId++) {
 171                         byte[] minName = null;
 172                         int minNameLast = 0;
 173
 174                         if ((pos + srcCnt) >= newMerged.length) {
 175                                 final TreeEntry[] t = new TreeEntry[newMerged.length * 2];
 176                                 for (int j = newMerged.length - 1; j >= 0; j--)
 177                                         t[j] = newMerged[j];
 178                                 newMerged = t;
 179                         }
 180
 181                         for (int srcId = 0; srcId < srcCnt; srcId++) {
 182                                 final int ti = treeIndexes[srcId];
 183                                 final TreeEntry[] ents = entries[srcId];
 184                                 if (ti == ents.length)
 185                                         continue;
 186
 187                                 final TreeEntry thisEntry = ents[ti];
 188                                 final int cmp = minName == null ? -1 : Tree.compareNames(
 189                                                 thisEntry.getNameUTF8(), minName, TreeEntry.lastChar(thisEntry), minNameLast);
 190
 191                                 if (cmp < 0) {
 192                                         minName = thisEntry.getNameUTF8();
 193                                         minNameLast = TreeEntry.lastChar(thisEntry);
 194                                         for (int j = srcId - 1; j >= 0; j--) {
 195                                                 if (newMerged[pos + j] != null) {
 196                                                         newMerged[pos + j] = null;
 197                                                         if (treeIndexes[j]-- == entries[j].length)
 198                                                                 done--;
 199                                                 }
 200                                         }
 201                                 }
 202
 203                                 if (cmp <= 0) {
 204                                         newMerged[pos + srcId] = thisEntry;
 205                                         if (++treeIndexes[srcId] == ents.length)
 206                                                 done++;
 207                                 }
 208                         }
 209                 }
 210
 211                 if (newMerged.length == pos)
 212                         merged = newMerged;
 213                 else {
 214                         merged = new TreeEntry[pos];
 215                         for (int j = pos - 1; j >= 0; j--)
 216                                 merged[j] = newMerged[j];
 217                 }
 218         }
 219 }