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