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];
}
};
}
