Skip to content

Ghidra is a software reverse engineering (SRE) framework

5.9 KB
Raw Blame
/* ###
 * IP: GHIDRA
 *
 * Licensed under the Apache License, Version 2.0 (the "License");
 * you may not use this file except in compliance with the License.
 * You may obtain a copy of the License at
 * 
 *      http://www.apache.org/licenses/LICENSE-2.0
 * 
 * Unless required by applicable law or agreed to in writing, software
 * distributed under the License is distributed on an "AS IS" BASIS,
 * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
 * See the License for the specific language governing permissions and
 * limitations under the License.
 */
package generic;

import java.util.*;
import java.util.Map.Entry;

/**
 * A method outline for setting an entry in a range map where coalescing is desired
 *
 * @param <E> the type of entries
 * @param <D> the type of range bounds
 * @param <R> the type of ranges
 * @param <V> the type of values
 */
public abstract class RangeMapSetter<E, D, R, V> {
	/**
	 * Compare two values as in {@link Comparator#compare(Object, Object)}
	 * 
	 * @param d1 the first value
	 * @param d2 the second value
	 * @return the result
	 */
	protected abstract int compare(D d1, D d2);

	/**
	 * Get the range of the given entry
	 * 
	 * @param entry the entry
	 * @return the range
	 */
	protected abstract R getRange(E entry);

	/**
	 * Get the value of the given entry
	 * 
	 * @param entry the entry
	 * @return the value
	 */
	protected abstract V getValue(E entry);

	/**
	 * Check if two values are equal
	 * 
	 * @param v1 the first value
	 * @param v2 the second value
	 * @return true if equal, false if not
	 */
	protected boolean valuesEqual(V v1, V v2) {
		return Objects.equals(v1, v2);
	}

	/**
	 * Remove an entry from the map
	 * 
	 * @param entry the entry
	 */
	protected abstract void remove(E entry);

	/**
	 * Get the lower bound of the range
	 * 
	 * @param range the range
	 * @return the lower bound
	 */
	protected abstract D getLower(R range);

	/**
	 * Get the upper bound of the range
	 * 
	 * @param range the range
	 * @return the upper bound
	 */
	protected abstract D getUpper(R range);

	/**
	 * Create a closed range with the given bounds
	 * 
	 * @param lower the lower bound
	 * @param upper the upper bound
	 * @return the range
	 */
	protected abstract R toSpan(D lower, D upper);

	/**
	 * Get the number immediately preceding the given bound
	 * 
	 * @param d the bound
	 * @return the previous bound, or null if it doesn't exist
	 */
	protected abstract D getPrevious(D d);

	/**
	 * Get the number immediately following the given bound
	 * 
	 * @param d the bound
	 * @return the next bound, or null if it doesn't exist
	 */
	protected abstract D getNext(D d);

	/**
	 * Get all entries intersecting the closed range formed by the given bounds
	 * 
	 * @param lower the lower bound
	 * @param upper the upper bound
	 * @return the intersecting entries
	 */
	protected abstract Iterable<E> getIntersecting(D lower, D upper);

	/**
	 * Place an entry into the map
	 * 
	 * @param range the range of the entry
	 * @param value the value of the entry
	 * @return the new entry (or an existing entry)
	 */
	protected abstract E put(R range, V value);

	/**
	 * Get the previous bound or this same bound, if the previous doesn't exist
	 * 
	 * @param d the bound
	 * @return the previous or same bound
	 */
	protected D getPreviousOrSame(D d) {
		D prev = getPrevious(d);
		if (prev == null) {
			return d;
		}
		return prev;
	}

	/**
	 * Get the next bound or this same bound, if the next doesn't exist
	 * 
	 * @param d the bound
	 * @return the next or same bound
	 */
	protected D getNextOrSame(D d) {
		D next = getNext(d);
		if (next == null) {
			return d;
		}
		return next;
	}

	/**
	 * Check if the two ranges are connected
	 * 
	 * <p>
	 * The ranges are connected if they intersect, or if their bounds abut.
	 * 
	 * @param r1 the first range
	 * @param r2 the second range
	 * @return true if connected
	 */
	protected boolean connects(R r1, R r2) {
		return compare(getPreviousOrSame(getLower(r1)), getUpper(r2)) <= 0 ||
			compare(getPreviousOrSame(getLower(r2)), getUpper(r1)) <= 0;
	}

	/**
	 * Entry point: Set the given range to the given value, coalescing where possible
	 * 
	 * @param range the range
	 * @param value the value
	 * @return the entry containing the value
	 */
	public E set(R range, V value) {
		return set(getLower(range), getUpper(range), value);
	}

	/**
	 * Entry point: Set the given range to the given value, coalescing where possible
	 * 
	 * @param lower the lower bound
	 * @param upper the upper bound
	 * @param value the value
	 * @return the entry containing the value
	 */
	public E set(D lower, D upper, V value) {
		// Go one out to find abutting ranges, too.
		D prev = getPreviousOrSame(lower);
		D next = getNextOrSame(upper);
		Set<E> toRemove = new LinkedHashSet<>();
		Map<R, V> toPut = new HashMap<>();
		for (E entry : getIntersecting(prev, next)) {
			R r = getRange(entry);
			int cmpMin = compare(getLower(r), lower);
			int cmpMax = compare(getUpper(r), upper);
			boolean sameVal = valuesEqual(getValue(entry), value);
			if (cmpMin <= 0 && cmpMax >= 0 && sameVal) {
				return entry; // The value in this range is already set as specified
			}
			toRemove.add(entry);
			if (cmpMin < 0) {
				if (sameVal) {
					// Expand the new entry to cover the one we just removed
					lower = getLower(r);
				}
				else {
					// Create a truncated entry to replace the one we just removed
					toPut.put(toSpan(getLower(r), prev), getValue(entry));
				}
			}
			if (cmpMax > 0) {
				if (sameVal) {
					// Expand the new entry to cover the one we just removed
					upper = getUpper(r);
				}
				else {
					// Create a truncated entry to replace the one we just removed
					toPut.put(toSpan(next, getUpper(r)), getValue(entry));
				}
			}
		}
		for (E entry : toRemove) {
			remove(entry);
		}
		E result = put(toSpan(lower, upper), value);
		assert toPut.size() <= 2;
		for (Entry<R, V> ent : toPut.entrySet()) {
			put(ent.getKey(), ent.getValue());
		}
		return result;
	}
}