1package android.os;
2
3import com.android.internal.util.ArrayUtils;
4
5import java.util.Arrays;
6
7/**
8 * Describes the source of some work that may be done by someone else.
9 * Currently the public representation of what a work source is is not
10 * defined; this is an opaque container.
11 */
12public class WorkSource implements Parcelable {
13    int mNum;
14    int[] mUids;
15
16    /**
17     * Internal statics to avoid object allocations in some operations.
18     * The WorkSource object itself is not thread safe, but we need to
19     * hold sTmpWorkSource lock while working with these statics.
20     */
21    static final WorkSource sTmpWorkSource = new WorkSource(0);
22    /**
23     * For returning newbie work from a modification operation.
24     */
25    static WorkSource sNewbWork;
26    /**
27     * For returning gone work form a modification operation.
28     */
29    static WorkSource sGoneWork;
30
31    /**
32     * Create an empty work source.
33     */
34    public WorkSource() {
35        mNum = 0;
36    }
37
38    /**
39     * Create a new WorkSource that is a copy of an existing one.
40     * If <var>orig</var> is null, an empty WorkSource is created.
41     */
42    public WorkSource(WorkSource orig) {
43        if (orig == null) {
44            mNum = 0;
45            return;
46        }
47        mNum = orig.mNum;
48        if (orig.mUids != null) {
49            mUids = orig.mUids.clone();
50        } else {
51            mUids = null;
52        }
53    }
54
55    /** @hide */
56    public WorkSource(int uid) {
57        mNum = 1;
58        mUids = new int[] { uid, 0 };
59    }
60
61    WorkSource(Parcel in) {
62        mNum = in.readInt();
63        mUids = in.createIntArray();
64    }
65
66    /** @hide */
67    public int size() {
68        return mNum;
69    }
70
71    /** @hide */
72    public int get(int index) {
73        return mUids[index];
74    }
75
76    /**
77     * Clear this WorkSource to be empty.
78     */
79    public void clear() {
80        mNum = 0;
81    }
82
83    @Override
84    public boolean equals(Object o) {
85        return o instanceof WorkSource && !diff((WorkSource)o);
86    }
87
88    @Override
89    public int hashCode() {
90        int result = 0;
91        for (int i = 0; i < mNum; i++) {
92            result = ((result << 4) | (result >>> 28)) ^ mUids[i];
93        }
94        return result;
95    }
96
97    /**
98     * Compare this WorkSource with another.
99     * @param other The WorkSource to compare against.
100     * @return If there is a difference, true is returned.
101     */
102    public boolean diff(WorkSource other) {
103        int N = mNum;
104        if (N != other.mNum) {
105            return true;
106        }
107        final int[] uids1 = mUids;
108        final int[] uids2 = other.mUids;
109        for (int i=0; i<N; i++) {
110            if (uids1[i] != uids2[i]) {
111                return true;
112            }
113        }
114        return false;
115    }
116
117    /**
118     * Replace the current contents of this work source with the given
119     * work source.  If <var>other</var> is null, the current work source
120     * will be made empty.
121     */
122    public void set(WorkSource other) {
123        if (other == null) {
124            mNum = 0;
125            return;
126        }
127        mNum = other.mNum;
128        if (other.mUids != null) {
129            if (mUids != null && mUids.length >= mNum) {
130                System.arraycopy(other.mUids, 0, mUids, 0, mNum);
131            } else {
132                mUids = other.mUids.clone();
133            }
134        } else {
135            mUids = null;
136        }
137    }
138
139    /** @hide */
140    public void set(int uid) {
141        mNum = 1;
142        if (mUids == null) mUids = new int[2];
143        mUids[0] = uid;
144    }
145
146    /** @hide */
147    public WorkSource[] setReturningDiffs(WorkSource other) {
148        synchronized (sTmpWorkSource) {
149            sNewbWork = null;
150            sGoneWork = null;
151            updateLocked(other, true, true);
152            if (sNewbWork != null || sGoneWork != null) {
153                WorkSource[] diffs = new WorkSource[2];
154                diffs[0] = sNewbWork;
155                diffs[1] = sGoneWork;
156                return diffs;
157            }
158            return null;
159        }
160    }
161
162    /**
163     * Merge the contents of <var>other</var> WorkSource in to this one.
164     *
165     * @param other The other WorkSource whose contents are to be merged.
166     * @return Returns true if any new sources were added.
167     */
168    public boolean add(WorkSource other) {
169        synchronized (sTmpWorkSource) {
170            return updateLocked(other, false, false);
171        }
172    }
173
174    /** @hide */
175    public WorkSource addReturningNewbs(WorkSource other) {
176        synchronized (sTmpWorkSource) {
177            sNewbWork = null;
178            updateLocked(other, false, true);
179            return sNewbWork;
180        }
181    }
182
183    /** @hide */
184    public boolean add(int uid) {
185        synchronized (sTmpWorkSource) {
186            sTmpWorkSource.mUids[0] = uid;
187            return updateLocked(sTmpWorkSource, false, false);
188        }
189    }
190
191    /** @hide */
192    public WorkSource addReturningNewbs(int uid) {
193        synchronized (sTmpWorkSource) {
194            sNewbWork = null;
195            sTmpWorkSource.mUids[0] = uid;
196            updateLocked(sTmpWorkSource, false, true);
197            return sNewbWork;
198        }
199    }
200
201    public boolean remove(WorkSource other) {
202        int N1 = mNum;
203        final int[] uids1 = mUids;
204        final int N2 = other.mNum;
205        final int[] uids2 = other.mUids;
206        boolean changed = false;
207        int i1 = 0;
208        for (int i2=0; i2<N2 && i1<N1; i2++) {
209            if (uids2[i2] == uids1[i1]) {
210                N1--;
211                if (i1 < N1) System.arraycopy(uids1, i1+1, uids1, i1, N1-i1);
212            }
213            while (i1 < N1 && uids2[i2] > uids1[i1]) {
214                i1++;
215            }
216        }
217
218        mNum = N1;
219
220        return changed;
221    }
222
223    private boolean updateLocked(WorkSource other, boolean set, boolean returnNewbs) {
224        int N1 = mNum;
225        int[] uids1 = mUids;
226        final int N2 = other.mNum;
227        final int[] uids2 = other.mUids;
228        boolean changed = false;
229        int i1 = 0;
230        for (int i2=0; i2<N2; i2++) {
231            if (i1 >= N1 || uids2[i2] < uids1[i1]) {
232                // Need to insert a new uid.
233                changed = true;
234                if (uids1 == null) {
235                    uids1 = new int[4];
236                    uids1[0] = uids2[i2];
237                } else if (i1 >= uids1.length) {
238                    int[] newuids = new int[(uids1.length*3)/2];
239                    if (i1 > 0) System.arraycopy(uids1, 0, newuids, 0, i1);
240                    if (i1 < N1) System.arraycopy(uids1, i1, newuids, i1+1, N1-i1);
241                    uids1 = newuids;
242                    uids1[i1] = uids2[i2];
243                } else {
244                    if (i1 < N1) System.arraycopy(uids1, i1, uids1, i1+1, N1-i1);
245                    uids1[i1] = uids2[i2];
246                }
247                if (returnNewbs) {
248                    if (sNewbWork == null) {
249                        sNewbWork = new WorkSource(uids2[i2]);
250                    } else {
251                        sNewbWork.addLocked(uids2[i2]);
252                    }
253                }
254                N1++;
255                i1++;
256            } else {
257                if (!set) {
258                    // Skip uids that already exist or are not in 'other'.
259                    do {
260                        i1++;
261                    } while (i1 < N1 && uids2[i2] >= uids1[i1]);
262                } else {
263                    // Remove any uids that don't exist in 'other'.
264                    int start = i1;
265                    while (i1 < N1 && uids2[i2] > uids1[i1]) {
266                        if (sGoneWork == null) {
267                            sGoneWork = new WorkSource(uids1[i1]);
268                        } else {
269                            sGoneWork.addLocked(uids1[i1]);
270                        }
271                        i1++;
272                    }
273                    if (start < i1) {
274                        System.arraycopy(uids1, i1, uids1, start, i1-start);
275                        N1 -= i1-start;
276                        i1 = start;
277                    }
278                    // If there is a matching uid, skip it.
279                    if (i1 < N1 && uids2[i1] == uids1[i1]) {
280                        i1++;
281                    }
282                }
283            }
284        }
285
286        mNum = N1;
287        mUids = uids1;
288
289        return changed;
290    }
291
292    private void addLocked(int uid) {
293        if (mUids == null) {
294            mUids = new int[4];
295            mUids[0] = uid;
296            mNum = 1;
297            return;
298        }
299        if (mNum >= mUids.length) {
300            int[] newuids = new int[(mNum*3)/2];
301            System.arraycopy(mUids, 0, newuids, 0, mNum);
302            mUids = newuids;
303        }
304
305        mUids[mNum] = uid;
306        mNum++;
307    }
308
309    @Override
310    public int describeContents() {
311        return 0;
312    }
313
314    @Override
315    public void writeToParcel(Parcel dest, int flags) {
316        dest.writeInt(mNum);
317        dest.writeIntArray(mUids);
318    }
319
320    @Override
321    public String toString() {
322        StringBuilder result = new StringBuilder();
323        result.append("{WorkSource: uids=[");
324        for (int i = 0; i < mNum; i++) {
325            if (i != 0) {
326                result.append(", ");
327            }
328            result.append(mUids[i]);
329        }
330        result.append("]}");
331        return result.toString();
332    }
333
334    public static final Parcelable.Creator<WorkSource> CREATOR
335            = new Parcelable.Creator<WorkSource>() {
336        public WorkSource createFromParcel(Parcel in) {
337            return new WorkSource(in);
338        }
339        public WorkSource[] newArray(int size) {
340            return new WorkSource[size];
341        }
342    };
343}
344