| package android.os; |
| |
| import android.util.Log; |
| |
| import java.util.Arrays; |
| |
| /** |
| * Describes the source of some work that may be done by someone else. |
| * Currently the public representation of what a work source is is not |
| * defined; this is an opaque container. |
| */ |
| public class WorkSource implements Parcelable { |
| static final String TAG = "WorkSource"; |
| static final boolean DEBUG = false; |
| |
| int mNum; |
| int[] mUids; |
| String[] mNames; |
| |
| /** |
| * Internal statics to avoid object allocations in some operations. |
| * The WorkSource object itself is not thread safe, but we need to |
| * hold sTmpWorkSource lock while working with these statics. |
| */ |
| static final WorkSource sTmpWorkSource = new WorkSource(0); |
| /** |
| * For returning newbie work from a modification operation. |
| */ |
| static WorkSource sNewbWork; |
| /** |
| * For returning gone work form a modification operation. |
| */ |
| static WorkSource sGoneWork; |
| |
| /** |
| * Create an empty work source. |
| */ |
| public WorkSource() { |
| mNum = 0; |
| } |
| |
| /** |
| * Create a new WorkSource that is a copy of an existing one. |
| * If <var>orig</var> is null, an empty WorkSource is created. |
| */ |
| public WorkSource(WorkSource orig) { |
| if (orig == null) { |
| mNum = 0; |
| return; |
| } |
| mNum = orig.mNum; |
| if (orig.mUids != null) { |
| mUids = orig.mUids.clone(); |
| mNames = orig.mNames != null ? orig.mNames.clone() : null; |
| } else { |
| mUids = null; |
| mNames = null; |
| } |
| } |
| |
| /** @hide */ |
| public WorkSource(int uid) { |
| mNum = 1; |
| mUids = new int[] { uid, 0 }; |
| mNames = null; |
| } |
| |
| /** @hide */ |
| public WorkSource(int uid, String name) { |
| if (name == null) { |
| throw new NullPointerException("Name can't be null"); |
| } |
| mNum = 1; |
| mUids = new int[] { uid, 0 }; |
| mNames = new String[] { name, null }; |
| } |
| |
| WorkSource(Parcel in) { |
| mNum = in.readInt(); |
| mUids = in.createIntArray(); |
| mNames = in.createStringArray(); |
| } |
| |
| /** @hide */ |
| public int size() { |
| return mNum; |
| } |
| |
| /** @hide */ |
| public int get(int index) { |
| return mUids[index]; |
| } |
| |
| /** @hide */ |
| public String getName(int index) { |
| return mNames != null ? mNames[index] : null; |
| } |
| |
| /** |
| * Clear names from this WorkSource. Uids are left intact. |
| * |
| * <p>Useful when combining with another WorkSource that doesn't have names. |
| * @hide |
| */ |
| public void clearNames() { |
| if (mNames != null) { |
| mNames = null; |
| // Clear out any duplicate uids now that we don't have names to disambiguate them. |
| int destIndex = 1; |
| int newNum = mNum; |
| for (int sourceIndex = 1; sourceIndex < mNum; sourceIndex++) { |
| if (mUids[sourceIndex] == mUids[sourceIndex - 1]) { |
| newNum--; |
| } else { |
| mUids[destIndex] = mUids[sourceIndex]; |
| destIndex++; |
| } |
| } |
| mNum = newNum; |
| } |
| } |
| |
| /** |
| * Clear this WorkSource to be empty. |
| */ |
| public void clear() { |
| mNum = 0; |
| } |
| |
| @Override |
| public boolean equals(Object o) { |
| return o instanceof WorkSource && !diff((WorkSource)o); |
| } |
| |
| @Override |
| public int hashCode() { |
| int result = 0; |
| for (int i = 0; i < mNum; i++) { |
| result = ((result << 4) | (result >>> 28)) ^ mUids[i]; |
| } |
| if (mNames != null) { |
| for (int i = 0; i < mNum; i++) { |
| result = ((result << 4) | (result >>> 28)) ^ mNames[i].hashCode(); |
| } |
| } |
| return result; |
| } |
| |
| /** |
| * Compare this WorkSource with another. |
| * @param other The WorkSource to compare against. |
| * @return If there is a difference, true is returned. |
| */ |
| public boolean diff(WorkSource other) { |
| int N = mNum; |
| if (N != other.mNum) { |
| return true; |
| } |
| final int[] uids1 = mUids; |
| final int[] uids2 = other.mUids; |
| final String[] names1 = mNames; |
| final String[] names2 = other.mNames; |
| for (int i=0; i<N; i++) { |
| if (uids1[i] != uids2[i]) { |
| return true; |
| } |
| if (names1 != null && names2 != null && !names1[i].equals(names2[i])) { |
| return true; |
| } |
| } |
| return false; |
| } |
| |
| /** |
| * Replace the current contents of this work source with the given |
| * work source. If <var>other</var> is null, the current work source |
| * will be made empty. |
| */ |
| public void set(WorkSource other) { |
| if (other == null) { |
| mNum = 0; |
| return; |
| } |
| mNum = other.mNum; |
| if (other.mUids != null) { |
| if (mUids != null && mUids.length >= mNum) { |
| System.arraycopy(other.mUids, 0, mUids, 0, mNum); |
| } else { |
| mUids = other.mUids.clone(); |
| } |
| if (other.mNames != null) { |
| if (mNames != null && mNames.length >= mNum) { |
| System.arraycopy(other.mNames, 0, mNames, 0, mNum); |
| } else { |
| mNames = other.mNames.clone(); |
| } |
| } else { |
| mNames = null; |
| } |
| } else { |
| mUids = null; |
| mNames = null; |
| } |
| } |
| |
| /** @hide */ |
| public void set(int uid) { |
| mNum = 1; |
| if (mUids == null) mUids = new int[2]; |
| mUids[0] = uid; |
| mNames = null; |
| } |
| |
| /** @hide */ |
| public void set(int uid, String name) { |
| if (name == null) { |
| throw new NullPointerException("Name can't be null"); |
| } |
| mNum = 1; |
| if (mUids == null) { |
| mUids = new int[2]; |
| mNames = new String[2]; |
| } |
| mUids[0] = uid; |
| mNames[0] = name; |
| } |
| |
| /** @hide */ |
| public WorkSource[] setReturningDiffs(WorkSource other) { |
| synchronized (sTmpWorkSource) { |
| sNewbWork = null; |
| sGoneWork = null; |
| updateLocked(other, true, true); |
| if (sNewbWork != null || sGoneWork != null) { |
| WorkSource[] diffs = new WorkSource[2]; |
| diffs[0] = sNewbWork; |
| diffs[1] = sGoneWork; |
| return diffs; |
| } |
| return null; |
| } |
| } |
| |
| /** |
| * Merge the contents of <var>other</var> WorkSource in to this one. |
| * |
| * @param other The other WorkSource whose contents are to be merged. |
| * @return Returns true if any new sources were added. |
| */ |
| public boolean add(WorkSource other) { |
| synchronized (sTmpWorkSource) { |
| return updateLocked(other, false, false); |
| } |
| } |
| |
| /** @hide */ |
| public WorkSource addReturningNewbs(WorkSource other) { |
| synchronized (sTmpWorkSource) { |
| sNewbWork = null; |
| updateLocked(other, false, true); |
| return sNewbWork; |
| } |
| } |
| |
| /** @hide */ |
| public boolean add(int uid) { |
| if (mNum <= 0) { |
| mNames = null; |
| insert(0, uid); |
| return true; |
| } |
| if (mNames != null) { |
| throw new IllegalArgumentException("Adding without name to named " + this); |
| } |
| int i = Arrays.binarySearch(mUids, 0, mNum, uid); |
| if (DEBUG) Log.d(TAG, "Adding uid " + uid + " to " + this + ": binsearch res = " + i); |
| if (i >= 0) { |
| return false; |
| } |
| insert(-i-1, uid); |
| return true; |
| } |
| |
| /** @hide */ |
| public boolean add(int uid, String name) { |
| if (mNum <= 0) { |
| insert(0, uid, name); |
| return true; |
| } |
| if (mNames == null) { |
| throw new IllegalArgumentException("Adding name to unnamed " + this); |
| } |
| int i; |
| for (i=0; i<mNum; i++) { |
| if (mUids[i] > uid) { |
| break; |
| } |
| if (mUids[i] == uid) { |
| int diff = mNames[i].compareTo(name); |
| if (diff > 0) { |
| break; |
| } |
| if (diff == 0) { |
| return false; |
| } |
| } |
| } |
| insert(i, uid, name); |
| return true; |
| } |
| |
| /** @hide */ |
| public WorkSource addReturningNewbs(int uid) { |
| synchronized (sTmpWorkSource) { |
| sNewbWork = null; |
| sTmpWorkSource.mUids[0] = uid; |
| updateLocked(sTmpWorkSource, false, true); |
| return sNewbWork; |
| } |
| } |
| |
| public boolean remove(WorkSource other) { |
| if (mNum <= 0 || other.mNum <= 0) { |
| return false; |
| } |
| if (mNames == null && other.mNames == null) { |
| return removeUids(other); |
| } else { |
| if (mNames == null) { |
| throw new IllegalArgumentException("Other " + other + " has names, but target " |
| + this + " does not"); |
| } |
| if (other.mNames == null) { |
| throw new IllegalArgumentException("Target " + this + " has names, but other " |
| + other + " does not"); |
| } |
| return removeUidsAndNames(other); |
| } |
| } |
| |
| /** @hide */ |
| public WorkSource stripNames() { |
| if (mNum <= 0) { |
| return new WorkSource(); |
| } |
| WorkSource result = new WorkSource(); |
| int lastUid = -1; |
| for (int i=0; i<mNum; i++) { |
| int uid = mUids[i]; |
| if (i == 0 || lastUid != uid) { |
| result.add(uid); |
| } |
| } |
| return result; |
| } |
| |
| private boolean removeUids(WorkSource other) { |
| int N1 = mNum; |
| final int[] uids1 = mUids; |
| final int N2 = other.mNum; |
| final int[] uids2 = other.mUids; |
| boolean changed = false; |
| int i1 = 0, i2 = 0; |
| if (DEBUG) Log.d(TAG, "Remove " + other + " from " + this); |
| while (i1 < N1 && i2 < N2) { |
| if (DEBUG) Log.d(TAG, "Step: target @ " + i1 + " of " + N1 + ", other @ " + i2 |
| + " of " + N2); |
| if (uids2[i2] == uids1[i1]) { |
| if (DEBUG) Log.d(TAG, "i1=" + i1 + " i2=" + i2 + " N1=" + N1 |
| + ": remove " + uids1[i1]); |
| N1--; |
| changed = true; |
| if (i1 < N1) System.arraycopy(uids1, i1+1, uids1, i1, N1-i1); |
| i2++; |
| } else if (uids2[i2] > uids1[i1]) { |
| if (DEBUG) Log.d(TAG, "i1=" + i1 + " i2=" + i2 + " N1=" + N1 + ": skip i1"); |
| i1++; |
| } else { |
| if (DEBUG) Log.d(TAG, "i1=" + i1 + " i2=" + i2 + " N1=" + N1 + ": skip i2"); |
| i2++; |
| } |
| } |
| |
| mNum = N1; |
| |
| return changed; |
| } |
| |
| private boolean removeUidsAndNames(WorkSource other) { |
| int N1 = mNum; |
| final int[] uids1 = mUids; |
| final String[] names1 = mNames; |
| final int N2 = other.mNum; |
| final int[] uids2 = other.mUids; |
| final String[] names2 = other.mNames; |
| boolean changed = false; |
| int i1 = 0, i2 = 0; |
| if (DEBUG) Log.d(TAG, "Remove " + other + " from " + this); |
| while (i1 < N1 && i2 < N2) { |
| if (DEBUG) Log.d(TAG, "Step: target @ " + i1 + " of " + N1 + ", other @ " + i2 |
| + " of " + N2 + ": " + uids1[i1] + " " + names1[i1]); |
| if (uids2[i2] == uids1[i1] && names2[i2].equals(names1[i1])) { |
| if (DEBUG) Log.d(TAG, "i1=" + i1 + " i2=" + i2 + " N1=" + N1 |
| + ": remove " + uids1[i1] + " " + names1[i1]); |
| N1--; |
| changed = true; |
| if (i1 < N1) { |
| System.arraycopy(uids1, i1+1, uids1, i1, N1-i1); |
| System.arraycopy(names1, i1+1, names1, i1, N1-i1); |
| } |
| i2++; |
| } else if (uids2[i2] > uids1[i1] |
| || (uids2[i2] == uids1[i1] && names2[i2].compareTo(names1[i1]) > 0)) { |
| if (DEBUG) Log.d(TAG, "i1=" + i1 + " i2=" + i2 + " N1=" + N1 + ": skip i1"); |
| i1++; |
| } else { |
| if (DEBUG) Log.d(TAG, "i1=" + i1 + " i2=" + i2 + " N1=" + N1 + ": skip i2"); |
| i2++; |
| } |
| } |
| |
| mNum = N1; |
| |
| return changed; |
| } |
| |
| private boolean updateLocked(WorkSource other, boolean set, boolean returnNewbs) { |
| if (mNames == null && other.mNames == null) { |
| return updateUidsLocked(other, set, returnNewbs); |
| } else { |
| if (mNum > 0 && mNames == null) { |
| throw new IllegalArgumentException("Other " + other + " has names, but target " |
| + this + " does not"); |
| } |
| if (other.mNum > 0 && other.mNames == null) { |
| throw new IllegalArgumentException("Target " + this + " has names, but other " |
| + other + " does not"); |
| } |
| return updateUidsAndNamesLocked(other, set, returnNewbs); |
| } |
| } |
| |
| private static WorkSource addWork(WorkSource cur, int newUid) { |
| if (cur == null) { |
| return new WorkSource(newUid); |
| } |
| cur.insert(cur.mNum, newUid); |
| return cur; |
| } |
| |
| private boolean updateUidsLocked(WorkSource other, boolean set, boolean returnNewbs) { |
| int N1 = mNum; |
| int[] uids1 = mUids; |
| final int N2 = other.mNum; |
| final int[] uids2 = other.mUids; |
| boolean changed = false; |
| int i1 = 0, i2 = 0; |
| if (DEBUG) Log.d(TAG, "Update " + this + " with " + other + " set=" + set |
| + " returnNewbs=" + returnNewbs); |
| while (i1 < N1 || i2 < N2) { |
| if (DEBUG) Log.d(TAG, "Step: target @ " + i1 + " of " + N1 + ", other @ " + i2 |
| + " of " + N2); |
| if (i1 >= N1 || (i2 < N2 && uids2[i2] < uids1[i1])) { |
| // Need to insert a new uid. |
| if (DEBUG) Log.d(TAG, "i1=" + i1 + " i2=" + i2 + " N1=" + N1 |
| + ": insert " + uids2[i2]); |
| changed = true; |
| if (uids1 == null) { |
| uids1 = new int[4]; |
| uids1[0] = uids2[i2]; |
| } else if (N1 >= uids1.length) { |
| int[] newuids = new int[(uids1.length*3)/2]; |
| if (i1 > 0) System.arraycopy(uids1, 0, newuids, 0, i1); |
| if (i1 < N1) System.arraycopy(uids1, i1, newuids, i1+1, N1-i1); |
| uids1 = newuids; |
| uids1[i1] = uids2[i2]; |
| } else { |
| if (i1 < N1) System.arraycopy(uids1, i1, uids1, i1+1, N1-i1); |
| uids1[i1] = uids2[i2]; |
| } |
| if (returnNewbs) { |
| sNewbWork = addWork(sNewbWork, uids2[i2]); |
| } |
| N1++; |
| i1++; |
| i2++; |
| } else { |
| if (!set) { |
| // Skip uids that already exist or are not in 'other'. |
| if (DEBUG) Log.d(TAG, "i1=" + i1 + " i2=" + i2 + " N1=" + N1 + ": skip"); |
| if (i2 < N2 && uids2[i2] == uids1[i1]) { |
| i2++; |
| } |
| i1++; |
| } else { |
| // Remove any uids that don't exist in 'other'. |
| int start = i1; |
| while (i1 < N1 && (i2 >= N2 || uids2[i2] > uids1[i1])) { |
| if (DEBUG) Log.d(TAG, "i1=" + i1 + " i2=" + i2 + ": remove " + uids1[i1]); |
| sGoneWork = addWork(sGoneWork, uids1[i1]); |
| i1++; |
| } |
| if (start < i1) { |
| System.arraycopy(uids1, i1, uids1, start, N1-i1); |
| N1 -= i1-start; |
| i1 = start; |
| } |
| // If there is a matching uid, skip it. |
| if (i1 < N1 && i2 < N2 && uids2[i2] == uids1[i1]) { |
| if (DEBUG) Log.d(TAG, "i1=" + i1 + " i2=" + i2 + " N1=" + N1 + ": skip"); |
| i1++; |
| i2++; |
| } |
| } |
| } |
| } |
| |
| mNum = N1; |
| mUids = uids1; |
| |
| return changed; |
| } |
| |
| /** |
| * Returns 0 if equal, negative if 'this' is before 'other', positive if 'this' is after 'other'. |
| */ |
| private int compare(WorkSource other, int i1, int i2) { |
| final int diff = mUids[i1] - other.mUids[i2]; |
| if (diff != 0) { |
| return diff; |
| } |
| return mNames[i1].compareTo(other.mNames[i2]); |
| } |
| |
| private static WorkSource addWork(WorkSource cur, int newUid, String newName) { |
| if (cur == null) { |
| return new WorkSource(newUid, newName); |
| } |
| cur.insert(cur.mNum, newUid, newName); |
| return cur; |
| } |
| |
| private boolean updateUidsAndNamesLocked(WorkSource other, boolean set, boolean returnNewbs) { |
| final int N2 = other.mNum; |
| final int[] uids2 = other.mUids; |
| String[] names2 = other.mNames; |
| boolean changed = false; |
| int i1 = 0, i2 = 0; |
| if (DEBUG) Log.d(TAG, "Update " + this + " with " + other + " set=" + set |
| + " returnNewbs=" + returnNewbs); |
| while (i1 < mNum || i2 < N2) { |
| if (DEBUG) Log.d(TAG, "Step: target @ " + i1 + " of " + mNum + ", other @ " + i2 |
| + " of " + N2); |
| int diff = -1; |
| if (i1 >= mNum || (i2 < N2 && (diff=compare(other, i1, i2)) > 0)) { |
| // Need to insert a new uid. |
| changed = true; |
| if (DEBUG) Log.d(TAG, "i1=" + i1 + " i2=" + i2 + " N1=" + mNum |
| + ": insert " + uids2[i2] + " " + names2[i2]); |
| insert(i1, uids2[i2], names2[i2]); |
| if (returnNewbs) { |
| sNewbWork = addWork(sNewbWork, uids2[i2], names2[i2]); |
| } |
| i1++; |
| i2++; |
| } else { |
| if (!set) { |
| if (DEBUG) Log.d(TAG, "i1=" + i1 + " i2=" + i2 + " N1=" + mNum + ": skip"); |
| if (i2 < N2 && diff == 0) { |
| i2++; |
| } |
| i1++; |
| } else { |
| // Remove any uids that don't exist in 'other'. |
| int start = i1; |
| while (diff < 0) { |
| if (DEBUG) Log.d(TAG, "i1=" + i1 + " i2=" + i2 + ": remove " + mUids[i1] |
| + " " + mNames[i1]); |
| sGoneWork = addWork(sGoneWork, mUids[i1], mNames[i1]); |
| i1++; |
| if (i1 >= mNum) { |
| break; |
| } |
| diff = i2 < N2 ? compare(other, i1, i2) : -1; |
| } |
| if (start < i1) { |
| System.arraycopy(mUids, i1, mUids, start, mNum-i1); |
| System.arraycopy(mNames, i1, mNames, start, mNum-i1); |
| mNum -= i1-start; |
| i1 = start; |
| } |
| // If there is a matching uid, skip it. |
| if (i1 < mNum && diff == 0) { |
| if (DEBUG) Log.d(TAG, "i1=" + i1 + " i2=" + i2 + " N1=" + mNum + ": skip"); |
| i1++; |
| i2++; |
| } |
| } |
| } |
| } |
| |
| return changed; |
| } |
| |
| private void insert(int index, int uid) { |
| if (DEBUG) Log.d(TAG, "Insert in " + this + " @ " + index + " uid " + uid); |
| if (mUids == null) { |
| mUids = new int[4]; |
| mUids[0] = uid; |
| mNum = 1; |
| } else if (mNum >= mUids.length) { |
| int[] newuids = new int[(mNum*3)/2]; |
| if (index > 0) { |
| System.arraycopy(mUids, 0, newuids, 0, index); |
| } |
| if (index < mNum) { |
| System.arraycopy(mUids, index, newuids, index+1, mNum-index); |
| } |
| mUids = newuids; |
| mUids[index] = uid; |
| mNum++; |
| } else { |
| if (index < mNum) { |
| System.arraycopy(mUids, index, mUids, index+1, mNum-index); |
| } |
| mUids[index] = uid; |
| mNum++; |
| } |
| } |
| |
| private void insert(int index, int uid, String name) { |
| if (mUids == null) { |
| mUids = new int[4]; |
| mUids[0] = uid; |
| mNames = new String[4]; |
| mNames[0] = name; |
| mNum = 1; |
| } else if (mNum >= mUids.length) { |
| int[] newuids = new int[(mNum*3)/2]; |
| String[] newnames = new String[(mNum*3)/2]; |
| if (index > 0) { |
| System.arraycopy(mUids, 0, newuids, 0, index); |
| System.arraycopy(mNames, 0, newnames, 0, index); |
| } |
| if (index < mNum) { |
| System.arraycopy(mUids, index, newuids, index+1, mNum-index); |
| System.arraycopy(mNames, index, newnames, index+1, mNum-index); |
| } |
| mUids = newuids; |
| mNames = newnames; |
| mUids[index] = uid; |
| mNames[index] = name; |
| mNum++; |
| } else { |
| if (index < mNum) { |
| System.arraycopy(mUids, index, mUids, index+1, mNum-index); |
| System.arraycopy(mNames, index, mNames, index+1, mNum-index); |
| } |
| mUids[index] = uid; |
| mNames[index] = name; |
| mNum++; |
| } |
| } |
| |
| @Override |
| public int describeContents() { |
| return 0; |
| } |
| |
| @Override |
| public void writeToParcel(Parcel dest, int flags) { |
| dest.writeInt(mNum); |
| dest.writeIntArray(mUids); |
| dest.writeStringArray(mNames); |
| } |
| |
| @Override |
| public String toString() { |
| StringBuilder result = new StringBuilder(); |
| result.append("WorkSource{"); |
| for (int i = 0; i < mNum; i++) { |
| if (i != 0) { |
| result.append(", "); |
| } |
| result.append(mUids[i]); |
| if (mNames != null) { |
| result.append(" "); |
| result.append(mNames[i]); |
| } |
| } |
| result.append("}"); |
| return result.toString(); |
| } |
| |
| public static final Parcelable.Creator<WorkSource> CREATOR |
| = new Parcelable.Creator<WorkSource>() { |
| public WorkSource createFromParcel(Parcel in) { |
| return new WorkSource(in); |
| } |
| public WorkSource[] newArray(int size) { |
| return new WorkSource[size]; |
| } |
| }; |
| } |
