private void searchForDeltas()

in org.eclipse.jgit/src/org/eclipse/jgit/internal/storage/pack/PackWriter.java [1460:1593]
98 lines of code
30 McCabe index (conditional complexity)

	private void searchForDeltas(ProgressMonitor monitor)
			throws MissingObjectException, IncorrectObjectTypeException,
			IOException {
		// Commits and annotated tags tend to have too many differences to
		// really benefit from delta compression. Consequently just don't
		// bother examining those types here.
		//
		ObjectToPack[] list = new ObjectToPack[
				  objectsLists[OBJ_TREE].size()
				+ objectsLists[OBJ_BLOB].size()
				+ edgeObjects.size()];
		int cnt = 0;
		cnt = findObjectsNeedingDelta(list, cnt, OBJ_TREE);
		cnt = findObjectsNeedingDelta(list, cnt, OBJ_BLOB);
		if (cnt == 0)
			return;
		int nonEdgeCnt = cnt;

		// Queue up any edge objects that we might delta against.  We won't
		// be sending these as we assume the other side has them, but we need
		// them in the search phase below.
		//
		for (ObjectToPack eo : edgeObjects) {
			eo.setWeight(0);
			list[cnt++] = eo;
		}

		// Compute the sizes of the objects so we can do a proper sort.
		// We let the reader skip missing objects if it chooses. For
		// some readers this can be a huge win. We detect missing objects
		// by having set the weights above to 0 and allowing the delta
		// search code to discover the missing object and skip over it, or
		// abort with an exception if we actually had to have it.
		//
		final long sizingStart = System.currentTimeMillis();
		beginPhase(PackingPhase.GETTING_SIZES, monitor, cnt);
		AsyncObjectSizeQueue<ObjectToPack> sizeQueue = reader.getObjectSize(
				Arrays.<ObjectToPack> asList(list).subList(0, cnt), false);
		try {
			final long limit = Math.min(
					config.getBigFileThreshold(),
					Integer.MAX_VALUE);
			for (;;) {
				try {
					if (!sizeQueue.next())
						break;
				} catch (MissingObjectException notFound) {
					monitor.update(1);
					if (ignoreMissingUninteresting) {
						ObjectToPack otp = sizeQueue.getCurrent();
						if (otp != null && otp.isEdge()) {
							otp.setDoNotDelta();
							continue;
						}

						otp = objectsMap.get(notFound.getObjectId());
						if (otp != null && otp.isEdge()) {
							otp.setDoNotDelta();
							continue;
						}
					}
					throw notFound;
				}

				ObjectToPack otp = sizeQueue.getCurrent();
				if (otp == null)
					otp = objectsMap.get(sizeQueue.getObjectId());

				long sz = sizeQueue.getSize();
				if (DeltaIndex.BLKSZ < sz && sz < limit)
					otp.setWeight((int) sz);
				else
					otp.setDoNotDelta(); // too small, or too big
				monitor.update(1);
			}
		} finally {
			sizeQueue.release();
		}
		endPhase(monitor);
		stats.timeSearchingForSizes = System.currentTimeMillis() - sizingStart;

		// Sort the objects by path hash so like files are near each other,
		// and then by size descending so that bigger files are first. This
		// applies "Linus' Law" which states that newer files tend to be the
		// bigger ones, because source files grow and hardly ever shrink.
		//
		Arrays.sort(list, 0, cnt, (ObjectToPack a, ObjectToPack b) -> {
			int cmp = (a.isDoNotDelta() ? 1 : 0) - (b.isDoNotDelta() ? 1 : 0);
			if (cmp != 0) {
				return cmp;
			}

			cmp = a.getType() - b.getType();
			if (cmp != 0) {
				return cmp;
			}

			cmp = (a.getPathHash() >>> 1) - (b.getPathHash() >>> 1);
			if (cmp != 0) {
				return cmp;
			}

			cmp = (a.getPathHash() & 1) - (b.getPathHash() & 1);
			if (cmp != 0) {
				return cmp;
			}

			cmp = (a.isEdge() ? 0 : 1) - (b.isEdge() ? 0 : 1);
			if (cmp != 0) {
				return cmp;
			}

			return b.getWeight() - a.getWeight();
		});

		// Above we stored the objects we cannot delta onto the end.
		// Remove them from the list so we don't waste time on them.
		while (0 < cnt && list[cnt - 1].isDoNotDelta()) {
			if (!list[cnt - 1].isEdge())
				nonEdgeCnt--;
			cnt--;
		}
		if (cnt == 0)
			return;

		final long searchStart = System.currentTimeMillis();
		searchForDeltas(monitor, list, cnt);
		stats.deltaSearchNonEdgeObjects = nonEdgeCnt;
		stats.timeCompressing = System.currentTimeMillis() - searchStart;

		for (int i = 0; i < cnt; i++)
			if (!list[i].isEdge() && list[i].isDeltaRepresentation())
				stats.deltasFound++;
	}