1package android.os;
2
3import android.os.WorkSourceProto;
4import android.util.Log;
5import android.util.proto.ProtoOutputStream;
6
7import java.util.Arrays;
8
9/**
10 * Describes the source of some work that may be done by someone else.
11 * Currently the public representation of what a work source is is not
12 * defined; this is an opaque container.
13 */
14public class WorkSource implements Parcelable {
15    static final String TAG = "WorkSource";
16    static final boolean DEBUG = false;
17
18    int mNum;
19    int[] mUids;
20    String[] mNames;
21
22    /**
23     * Internal statics to avoid object allocations in some operations.
24     * The WorkSource object itself is not thread safe, but we need to
25     * hold sTmpWorkSource lock while working with these statics.
26     */
27    static final WorkSource sTmpWorkSource = new WorkSource(0);
28    /**
29     * For returning newbie work from a modification operation.
30     */
31    static WorkSource sNewbWork;
32    /**
33     * For returning gone work form a modification operation.
34     */
35    static WorkSource sGoneWork;
36
37    /**
38     * Create an empty work source.
39     */
40    public WorkSource() {
41        mNum = 0;
42    }
43
44    /**
45     * Create a new WorkSource that is a copy of an existing one.
46     * If <var>orig</var> is null, an empty WorkSource is created.
47     */
48    public WorkSource(WorkSource orig) {
49        if (orig == null) {
50            mNum = 0;
51            return;
52        }
53        mNum = orig.mNum;
54        if (orig.mUids != null) {
55            mUids = orig.mUids.clone();
56            mNames = orig.mNames != null ? orig.mNames.clone() : null;
57        } else {
58            mUids = null;
59            mNames = null;
60        }
61    }
62
63    /** @hide */
64    public WorkSource(int uid) {
65        mNum = 1;
66        mUids = new int[] { uid, 0 };
67        mNames = null;
68    }
69
70    /** @hide */
71    public WorkSource(int uid, String name) {
72        if (name == null) {
73            throw new NullPointerException("Name can't be null");
74        }
75        mNum = 1;
76        mUids = new int[] { uid, 0 };
77        mNames = new String[] { name, null };
78    }
79
80    WorkSource(Parcel in) {
81        mNum = in.readInt();
82        mUids = in.createIntArray();
83        mNames = in.createStringArray();
84    }
85
86    /** @hide */
87    public int size() {
88        return mNum;
89    }
90
91    /** @hide */
92    public int get(int index) {
93        return mUids[index];
94    }
95
96    /** @hide */
97    public String getName(int index) {
98        return mNames != null ? mNames[index] : null;
99    }
100
101    /**
102     * Clear names from this WorkSource.  Uids are left intact.
103     *
104     * <p>Useful when combining with another WorkSource that doesn't have names.
105     * @hide
106     */
107    public void clearNames() {
108        if (mNames != null) {
109            mNames = null;
110            // Clear out any duplicate uids now that we don't have names to disambiguate them.
111            int destIndex = 1;
112            int newNum = mNum;
113            for (int sourceIndex = 1; sourceIndex < mNum; sourceIndex++) {
114                if (mUids[sourceIndex] == mUids[sourceIndex - 1]) {
115                    newNum--;
116                } else {
117                    mUids[destIndex] = mUids[sourceIndex];
118                    destIndex++;
119                }
120            }
121            mNum = newNum;
122        }
123    }
124
125    /**
126     * Clear this WorkSource to be empty.
127     */
128    public void clear() {
129        mNum = 0;
130    }
131
132    @Override
133    public boolean equals(Object o) {
134        return o instanceof WorkSource && !diff((WorkSource)o);
135    }
136
137    @Override
138    public int hashCode() {
139        int result = 0;
140        for (int i = 0; i < mNum; i++) {
141            result = ((result << 4) | (result >>> 28)) ^ mUids[i];
142        }
143        if (mNames != null) {
144            for (int i = 0; i < mNum; i++) {
145                result = ((result << 4) | (result >>> 28)) ^ mNames[i].hashCode();
146            }
147        }
148        return result;
149    }
150
151    /**
152     * Compare this WorkSource with another.
153     * @param other The WorkSource to compare against.
154     * @return If there is a difference, true is returned.
155     */
156    public boolean diff(WorkSource other) {
157        int N = mNum;
158        if (N != other.mNum) {
159            return true;
160        }
161        final int[] uids1 = mUids;
162        final int[] uids2 = other.mUids;
163        final String[] names1 = mNames;
164        final String[] names2 = other.mNames;
165        for (int i=0; i<N; i++) {
166            if (uids1[i] != uids2[i]) {
167                return true;
168            }
169            if (names1 != null && names2 != null && !names1[i].equals(names2[i])) {
170                return true;
171            }
172        }
173        return false;
174    }
175
176    /**
177     * Replace the current contents of this work source with the given
178     * work source.  If <var>other</var> is null, the current work source
179     * will be made empty.
180     */
181    public void set(WorkSource other) {
182        if (other == null) {
183            mNum = 0;
184            return;
185        }
186        mNum = other.mNum;
187        if (other.mUids != null) {
188            if (mUids != null && mUids.length >= mNum) {
189                System.arraycopy(other.mUids, 0, mUids, 0, mNum);
190            } else {
191                mUids = other.mUids.clone();
192            }
193            if (other.mNames != null) {
194                if (mNames != null && mNames.length >= mNum) {
195                    System.arraycopy(other.mNames, 0, mNames, 0, mNum);
196                } else {
197                    mNames = other.mNames.clone();
198                }
199            } else {
200                mNames = null;
201            }
202        } else {
203            mUids = null;
204            mNames = null;
205        }
206    }
207
208    /** @hide */
209    public void set(int uid) {
210        mNum = 1;
211        if (mUids == null) mUids = new int[2];
212        mUids[0] = uid;
213        mNames = null;
214    }
215
216    /** @hide */
217    public void set(int uid, String name) {
218        if (name == null) {
219            throw new NullPointerException("Name can't be null");
220        }
221        mNum = 1;
222        if (mUids == null) {
223            mUids = new int[2];
224            mNames = new String[2];
225        }
226        mUids[0] = uid;
227        mNames[0] = name;
228    }
229
230    /** @hide */
231    public WorkSource[] setReturningDiffs(WorkSource other) {
232        synchronized (sTmpWorkSource) {
233            sNewbWork = null;
234            sGoneWork = null;
235            updateLocked(other, true, true);
236            if (sNewbWork != null || sGoneWork != null) {
237                WorkSource[] diffs = new WorkSource[2];
238                diffs[0] = sNewbWork;
239                diffs[1] = sGoneWork;
240                return diffs;
241            }
242            return null;
243        }
244    }
245
246    /**
247     * Merge the contents of <var>other</var> WorkSource in to this one.
248     *
249     * @param other The other WorkSource whose contents are to be merged.
250     * @return Returns true if any new sources were added.
251     */
252    public boolean add(WorkSource other) {
253        synchronized (sTmpWorkSource) {
254            return updateLocked(other, false, false);
255        }
256    }
257
258    /** @hide */
259    public WorkSource addReturningNewbs(WorkSource other) {
260        synchronized (sTmpWorkSource) {
261            sNewbWork = null;
262            updateLocked(other, false, true);
263            return sNewbWork;
264        }
265    }
266
267    /** @hide */
268    public boolean add(int uid) {
269        if (mNum <= 0) {
270            mNames = null;
271            insert(0, uid);
272            return true;
273        }
274        if (mNames != null) {
275            throw new IllegalArgumentException("Adding without name to named " + this);
276        }
277        int i = Arrays.binarySearch(mUids, 0, mNum, uid);
278        if (DEBUG) Log.d(TAG, "Adding uid " + uid + " to " + this + ": binsearch res = " + i);
279        if (i >= 0) {
280            return false;
281        }
282        insert(-i-1, uid);
283        return true;
284    }
285
286    /** @hide */
287    public boolean add(int uid, String name) {
288        if (mNum <= 0) {
289            insert(0, uid, name);
290            return true;
291        }
292        if (mNames == null) {
293            throw new IllegalArgumentException("Adding name to unnamed " + this);
294        }
295        int i;
296        for (i=0; i<mNum; i++) {
297            if (mUids[i] > uid) {
298                break;
299            }
300            if (mUids[i] == uid) {
301                int diff = mNames[i].compareTo(name);
302                if (diff > 0) {
303                    break;
304                }
305                if (diff == 0) {
306                    return false;
307                }
308            }
309        }
310        insert(i, uid, name);
311        return true;
312    }
313
314    /** @hide */
315    public WorkSource addReturningNewbs(int uid) {
316        synchronized (sTmpWorkSource) {
317            sNewbWork = null;
318            sTmpWorkSource.mUids[0] = uid;
319            updateLocked(sTmpWorkSource, false, true);
320            return sNewbWork;
321        }
322    }
323
324    public boolean remove(WorkSource other) {
325        if (mNum <= 0 || other.mNum <= 0) {
326            return false;
327        }
328        if (mNames == null && other.mNames == null) {
329            return removeUids(other);
330        } else {
331            if (mNames == null) {
332                throw new IllegalArgumentException("Other " + other + " has names, but target "
333                        + this + " does not");
334            }
335            if (other.mNames == null) {
336                throw new IllegalArgumentException("Target " + this + " has names, but other "
337                        + other + " does not");
338            }
339            return removeUidsAndNames(other);
340        }
341    }
342
343    /** @hide */
344    public WorkSource stripNames() {
345        if (mNum <= 0) {
346            return new WorkSource();
347        }
348        WorkSource result = new WorkSource();
349        int lastUid = -1;
350        for (int i=0; i<mNum; i++) {
351            int uid = mUids[i];
352            if (i == 0 || lastUid != uid) {
353                result.add(uid);
354            }
355        }
356        return result;
357    }
358
359    private boolean removeUids(WorkSource other) {
360        int N1 = mNum;
361        final int[] uids1 = mUids;
362        final int N2 = other.mNum;
363        final int[] uids2 = other.mUids;
364        boolean changed = false;
365        int i1 = 0, i2 = 0;
366        if (DEBUG) Log.d(TAG, "Remove " + other + " from " + this);
367        while (i1 < N1 && i2 < N2) {
368            if (DEBUG) Log.d(TAG, "Step: target @ " + i1 + " of " + N1 + ", other @ " + i2
369                    + " of " + N2);
370            if (uids2[i2] == uids1[i1]) {
371                if (DEBUG) Log.d(TAG, "i1=" + i1 + " i2=" + i2 + " N1=" + N1
372                        + ": remove " + uids1[i1]);
373                N1--;
374                changed = true;
375                if (i1 < N1) System.arraycopy(uids1, i1+1, uids1, i1, N1-i1);
376                i2++;
377            } else if (uids2[i2] > uids1[i1]) {
378                if (DEBUG) Log.d(TAG, "i1=" + i1 + " i2=" + i2 + " N1=" + N1 + ": skip i1");
379                i1++;
380            } else {
381                if (DEBUG) Log.d(TAG, "i1=" + i1 + " i2=" + i2 + " N1=" + N1 + ": skip i2");
382                i2++;
383            }
384        }
385
386        mNum = N1;
387
388        return changed;
389    }
390
391    private boolean removeUidsAndNames(WorkSource other) {
392        int N1 = mNum;
393        final int[] uids1 = mUids;
394        final String[] names1 = mNames;
395        final int N2 = other.mNum;
396        final int[] uids2 = other.mUids;
397        final String[] names2 = other.mNames;
398        boolean changed = false;
399        int i1 = 0, i2 = 0;
400        if (DEBUG) Log.d(TAG, "Remove " + other + " from " + this);
401        while (i1 < N1 && i2 < N2) {
402            if (DEBUG) Log.d(TAG, "Step: target @ " + i1 + " of " + N1 + ", other @ " + i2
403                    + " of " + N2 + ": " + uids1[i1] + " " + names1[i1]);
404            if (uids2[i2] == uids1[i1] && names2[i2].equals(names1[i1])) {
405                if (DEBUG) Log.d(TAG, "i1=" + i1 + " i2=" + i2 + " N1=" + N1
406                        + ": remove " + uids1[i1] + " " + names1[i1]);
407                N1--;
408                changed = true;
409                if (i1 < N1) {
410                    System.arraycopy(uids1, i1+1, uids1, i1, N1-i1);
411                    System.arraycopy(names1, i1+1, names1, i1, N1-i1);
412                }
413                i2++;
414            } else if (uids2[i2] > uids1[i1]
415                    || (uids2[i2] == uids1[i1] && names2[i2].compareTo(names1[i1]) > 0)) {
416                if (DEBUG) Log.d(TAG, "i1=" + i1 + " i2=" + i2 + " N1=" + N1 + ": skip i1");
417                i1++;
418            } else {
419                if (DEBUG) Log.d(TAG, "i1=" + i1 + " i2=" + i2 + " N1=" + N1 + ": skip i2");
420                i2++;
421            }
422        }
423
424        mNum = N1;
425
426        return changed;
427    }
428
429    private boolean updateLocked(WorkSource other, boolean set, boolean returnNewbs) {
430        if (mNames == null && other.mNames == null) {
431            return updateUidsLocked(other, set, returnNewbs);
432        } else {
433            if (mNum > 0 && mNames == null) {
434                throw new IllegalArgumentException("Other " + other + " has names, but target "
435                        + this + " does not");
436            }
437            if (other.mNum > 0 && other.mNames == null) {
438                throw new IllegalArgumentException("Target " + this + " has names, but other "
439                        + other + " does not");
440            }
441            return updateUidsAndNamesLocked(other, set, returnNewbs);
442        }
443    }
444
445    private static WorkSource addWork(WorkSource cur, int newUid) {
446        if (cur == null) {
447            return new WorkSource(newUid);
448        }
449        cur.insert(cur.mNum, newUid);
450        return cur;
451    }
452
453    private boolean updateUidsLocked(WorkSource other, boolean set, boolean returnNewbs) {
454        int N1 = mNum;
455        int[] uids1 = mUids;
456        final int N2 = other.mNum;
457        final int[] uids2 = other.mUids;
458        boolean changed = false;
459        int i1 = 0, i2 = 0;
460        if (DEBUG) Log.d(TAG, "Update " + this + " with " + other + " set=" + set
461                + " returnNewbs=" + returnNewbs);
462        while (i1 < N1 || i2 < N2) {
463            if (DEBUG) Log.d(TAG, "Step: target @ " + i1 + " of " + N1 + ", other @ " + i2
464                    + " of " + N2);
465            if (i1 >= N1 || (i2 < N2 && uids2[i2] < uids1[i1])) {
466                // Need to insert a new uid.
467                if (DEBUG) Log.d(TAG, "i1=" + i1 + " i2=" + i2 + " N1=" + N1
468                        + ": insert " + uids2[i2]);
469                changed = true;
470                if (uids1 == null) {
471                    uids1 = new int[4];
472                    uids1[0] = uids2[i2];
473                } else if (N1 >= uids1.length) {
474                    int[] newuids = new int[(uids1.length*3)/2];
475                    if (i1 > 0) System.arraycopy(uids1, 0, newuids, 0, i1);
476                    if (i1 < N1) System.arraycopy(uids1, i1, newuids, i1+1, N1-i1);
477                    uids1 = newuids;
478                    uids1[i1] = uids2[i2];
479                } else {
480                    if (i1 < N1) System.arraycopy(uids1, i1, uids1, i1+1, N1-i1);
481                    uids1[i1] = uids2[i2];
482                }
483                if (returnNewbs) {
484                    sNewbWork = addWork(sNewbWork, uids2[i2]);
485                }
486                N1++;
487                i1++;
488                i2++;
489            } else {
490                if (!set) {
491                    // Skip uids that already exist or are not in 'other'.
492                    if (DEBUG) Log.d(TAG, "i1=" + i1 + " i2=" + i2 + " N1=" + N1 + ": skip");
493                    if (i2 < N2 && uids2[i2] == uids1[i1]) {
494                        i2++;
495                    }
496                    i1++;
497                } else {
498                    // Remove any uids that don't exist in 'other'.
499                    int start = i1;
500                    while (i1 < N1 && (i2 >= N2 || uids2[i2] > uids1[i1])) {
501                        if (DEBUG) Log.d(TAG, "i1=" + i1 + " i2=" + i2 + ": remove " + uids1[i1]);
502                        sGoneWork = addWork(sGoneWork, uids1[i1]);
503                        i1++;
504                    }
505                    if (start < i1) {
506                        System.arraycopy(uids1, i1, uids1, start, N1-i1);
507                        N1 -= i1-start;
508                        i1 = start;
509                    }
510                    // If there is a matching uid, skip it.
511                    if (i1 < N1 && i2 < N2 && uids2[i2] == uids1[i1]) {
512                        if (DEBUG) Log.d(TAG, "i1=" + i1 + " i2=" + i2 + " N1=" + N1 + ": skip");
513                        i1++;
514                        i2++;
515                    }
516                }
517            }
518        }
519
520        mNum = N1;
521        mUids = uids1;
522
523        return changed;
524    }
525
526    /**
527     * Returns 0 if equal, negative if 'this' is before 'other', positive if 'this' is after 'other'.
528     */
529    private int compare(WorkSource other, int i1, int i2) {
530        final int diff = mUids[i1] - other.mUids[i2];
531        if (diff != 0) {
532            return diff;
533        }
534        return mNames[i1].compareTo(other.mNames[i2]);
535    }
536
537    private static WorkSource addWork(WorkSource cur, int newUid, String newName) {
538        if (cur == null) {
539            return new WorkSource(newUid, newName);
540        }
541        cur.insert(cur.mNum, newUid, newName);
542        return cur;
543    }
544
545    private boolean updateUidsAndNamesLocked(WorkSource other, boolean set, boolean returnNewbs) {
546        final int N2 = other.mNum;
547        final int[] uids2 = other.mUids;
548        String[] names2 = other.mNames;
549        boolean changed = false;
550        int i1 = 0, i2 = 0;
551        if (DEBUG) Log.d(TAG, "Update " + this + " with " + other + " set=" + set
552                + " returnNewbs=" + returnNewbs);
553        while (i1 < mNum || i2 < N2) {
554            if (DEBUG) Log.d(TAG, "Step: target @ " + i1 + " of " + mNum + ", other @ " + i2
555                    + " of " + N2);
556            int diff = -1;
557            if (i1 >= mNum || (i2 < N2 && (diff=compare(other, i1, i2)) > 0)) {
558                // Need to insert a new uid.
559                changed = true;
560                if (DEBUG) Log.d(TAG, "i1=" + i1 + " i2=" + i2 + " N1=" + mNum
561                        + ": insert " + uids2[i2] + " " + names2[i2]);
562                insert(i1, uids2[i2], names2[i2]);
563                if (returnNewbs) {
564                    sNewbWork = addWork(sNewbWork, uids2[i2], names2[i2]);
565                }
566                i1++;
567                i2++;
568            } else {
569                if (!set) {
570                    if (DEBUG) Log.d(TAG, "i1=" + i1 + " i2=" + i2 + " N1=" + mNum + ": skip");
571                    if (i2 < N2 && diff == 0) {
572                        i2++;
573                    }
574                    i1++;
575                } else {
576                    // Remove any uids that don't exist in 'other'.
577                    int start = i1;
578                    while (diff < 0) {
579                        if (DEBUG) Log.d(TAG, "i1=" + i1 + " i2=" + i2 + ": remove " + mUids[i1]
580                                + " " + mNames[i1]);
581                        sGoneWork = addWork(sGoneWork, mUids[i1], mNames[i1]);
582                        i1++;
583                        if (i1 >= mNum) {
584                            break;
585                        }
586                        diff = i2 < N2 ? compare(other, i1, i2) : -1;
587                    }
588                    if (start < i1) {
589                        System.arraycopy(mUids, i1, mUids, start, mNum-i1);
590                        System.arraycopy(mNames, i1, mNames, start, mNum-i1);
591                        mNum -= i1-start;
592                        i1 = start;
593                    }
594                    // If there is a matching uid, skip it.
595                    if (i1 < mNum && diff == 0) {
596                        if (DEBUG) Log.d(TAG, "i1=" + i1 + " i2=" + i2 + " N1=" + mNum + ": skip");
597                        i1++;
598                        i2++;
599                    }
600                }
601            }
602        }
603
604        return changed;
605    }
606
607    private void insert(int index, int uid)  {
608        if (DEBUG) Log.d(TAG, "Insert in " + this + " @ " + index + " uid " + uid);
609        if (mUids == null) {
610            mUids = new int[4];
611            mUids[0] = uid;
612            mNum = 1;
613        } else if (mNum >= mUids.length) {
614            int[] newuids = new int[(mNum*3)/2];
615            if (index > 0) {
616                System.arraycopy(mUids, 0, newuids, 0, index);
617            }
618            if (index < mNum) {
619                System.arraycopy(mUids, index, newuids, index+1, mNum-index);
620            }
621            mUids = newuids;
622            mUids[index] = uid;
623            mNum++;
624        } else {
625            if (index < mNum) {
626                System.arraycopy(mUids, index, mUids, index+1, mNum-index);
627            }
628            mUids[index] = uid;
629            mNum++;
630        }
631    }
632
633    private void insert(int index, int uid, String name)  {
634        if (mUids == null) {
635            mUids = new int[4];
636            mUids[0] = uid;
637            mNames = new String[4];
638            mNames[0] = name;
639            mNum = 1;
640        } else if (mNum >= mUids.length) {
641            int[] newuids = new int[(mNum*3)/2];
642            String[] newnames = new String[(mNum*3)/2];
643            if (index > 0) {
644                System.arraycopy(mUids, 0, newuids, 0, index);
645                System.arraycopy(mNames, 0, newnames, 0, index);
646            }
647            if (index < mNum) {
648                System.arraycopy(mUids, index, newuids, index+1, mNum-index);
649                System.arraycopy(mNames, index, newnames, index+1, mNum-index);
650            }
651            mUids = newuids;
652            mNames = newnames;
653            mUids[index] = uid;
654            mNames[index] = name;
655            mNum++;
656        } else {
657            if (index < mNum) {
658                System.arraycopy(mUids, index, mUids, index+1, mNum-index);
659                System.arraycopy(mNames, index, mNames, index+1, mNum-index);
660            }
661            mUids[index] = uid;
662            mNames[index] = name;
663            mNum++;
664        }
665    }
666
667    @Override
668    public int describeContents() {
669        return 0;
670    }
671
672    @Override
673    public void writeToParcel(Parcel dest, int flags) {
674        dest.writeInt(mNum);
675        dest.writeIntArray(mUids);
676        dest.writeStringArray(mNames);
677    }
678
679    @Override
680    public String toString() {
681        StringBuilder result = new StringBuilder();
682        result.append("WorkSource{");
683        for (int i = 0; i < mNum; i++) {
684            if (i != 0) {
685                result.append(", ");
686            }
687            result.append(mUids[i]);
688            if (mNames != null) {
689                result.append(" ");
690                result.append(mNames[i]);
691            }
692        }
693        result.append("}");
694        return result.toString();
695    }
696
697    /** @hide */
698    public void writeToProto(ProtoOutputStream proto, long fieldId) {
699        final long workSourceToken = proto.start(fieldId);
700        for (int i = 0; i < mNum; i++) {
701            final long contentProto = proto.start(WorkSourceProto.WORK_SOURCE_CONTENTS);
702            proto.write(WorkSourceProto.WorkSourceContentProto.UID, mUids[i]);
703            if (mNames != null) {
704                proto.write(WorkSourceProto.WorkSourceContentProto.NAME, mNames[i]);
705            }
706            proto.end(contentProto);
707        }
708        proto.end(workSourceToken);
709    }
710
711    public static final Parcelable.Creator<WorkSource> CREATOR
712            = new Parcelable.Creator<WorkSource>() {
713        public WorkSource createFromParcel(Parcel in) {
714            return new WorkSource(in);
715        }
716        public WorkSource[] newArray(int size) {
717            return new WorkSource[size];
718        }
719    };
720}
721