WorkSource.java revision a31510e47a0f0c2525702c2f10a85064322a28f2 
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        mNames = null;
227    }
228
229    /** @hide */
230    public WorkSource[] setReturningDiffs(WorkSource other) {
231        synchronized (sTmpWorkSource) {
232            sNewbWork = null;
233            sGoneWork = null;
234            updateLocked(other, true, true);
235            if (sNewbWork != null || sGoneWork != null) {
236                WorkSource[] diffs = new WorkSource[2];
237                diffs[0] = sNewbWork;
238                diffs[1] = sGoneWork;
239                return diffs;
240            }
241            return null;
242        }
243    }
244
245    /**
246     * Merge the contents of <var>other</var> WorkSource in to this one.
247     *
248     * @param other The other WorkSource whose contents are to be merged.
249     * @return Returns true if any new sources were added.
250     */
251    public boolean add(WorkSource other) {
252        synchronized (sTmpWorkSource) {
253            return updateLocked(other, false, false);
254        }
255    }
256
257    /** @hide */
258    public WorkSource addReturningNewbs(WorkSource other) {
259        synchronized (sTmpWorkSource) {
260            sNewbWork = null;
261            updateLocked(other, false, true);
262            return sNewbWork;
263        }
264    }
265
266    /** @hide */
267    public boolean add(int uid) {
268        if (mNum <= 0) {
269            mNames = null;
270            insert(0, uid);
271            return true;
272        }
273        if (mNames != null) {
274            throw new IllegalArgumentException("Adding without name to named " + this);
275        }
276        int i = Arrays.binarySearch(mUids, 0, mNum, uid);
277        if (DEBUG) Log.d(TAG, "Adding uid " + uid + " to " + this + ": binsearch res = " + i);
278        if (i >= 0) {
279            return false;
280        }
281        insert(-i-1, uid);
282        return true;
283    }
284
285    /** @hide */
286    public boolean add(int uid, String name) {
287        if (mNum <= 0) {
288            insert(0, uid, name);
289            return true;
290        }
291        if (mNames == null) {
292            throw new IllegalArgumentException("Adding name to unnamed " + this);
293        }
294        int i;
295        for (i=0; i<mNum; i++) {
296            if (mUids[i] > uid) {
297                break;
298            }
299            if (mUids[i] == uid) {
300                int diff = mNames[i].compareTo(name);
301                if (diff > 0) {
302                    break;
303                }
304                if (diff == 0) {
305                    return false;
306                }
307            }
308        }
309        insert(i, uid, name);
310        return true;
311    }
312
313    /** @hide */
314    public WorkSource addReturningNewbs(int uid) {
315        synchronized (sTmpWorkSource) {
316            sNewbWork = null;
317            sTmpWorkSource.mUids[0] = uid;
318            updateLocked(sTmpWorkSource, false, true);
319            return sNewbWork;
320        }
321    }
322
323    public boolean remove(WorkSource other) {
324        if (mNum <= 0 || other.mNum <= 0) {
325            return false;
326        }
327        if (mNames == null && other.mNames == null) {
328            return removeUids(other);
329        } else {
330            if (mNames == null) {
331                throw new IllegalArgumentException("Other " + other + " has names, but target "
332                        + this + " does not");
333            }
334            if (other.mNames == null) {
335                throw new IllegalArgumentException("Target " + this + " has names, but other "
336                        + other + " does not");
337            }
338            return removeUidsAndNames(other);
339        }
340    }
341
342    /** @hide */
343    public WorkSource stripNames() {
344        if (mNum <= 0) {
345            return new WorkSource();
346        }
347        WorkSource result = new WorkSource();
348        int lastUid = -1;
349        for (int i=0; i<mNum; i++) {
350            int uid = mUids[i];
351            if (i == 0 || lastUid != uid) {
352                result.add(uid);
353            }
354        }
355        return result;
356    }
357
358    private boolean removeUids(WorkSource other) {
359        int N1 = mNum;
360        final int[] uids1 = mUids;
361        final int N2 = other.mNum;
362        final int[] uids2 = other.mUids;
363        boolean changed = false;
364        int i1 = 0, i2 = 0;
365        if (DEBUG) Log.d(TAG, "Remove " + other + " from " + this);
366        while (i1 < N1 && i2 < N2) {
367            if (DEBUG) Log.d(TAG, "Step: target @ " + i1 + " of " + N1 + ", other @ " + i2
368                    + " of " + N2);
369            if (uids2[i2] == uids1[i1]) {
370                if (DEBUG) Log.d(TAG, "i1=" + i1 + " i2=" + i2 + " N1=" + N1
371                        + ": remove " + uids1[i1]);
372                N1--;
373                changed = true;
374                if (i1 < N1) System.arraycopy(uids1, i1+1, uids1, i1, N1-i1);
375                i2++;
376            } else if (uids2[i2] > uids1[i1]) {
377                if (DEBUG) Log.d(TAG, "i1=" + i1 + " i2=" + i2 + " N1=" + N1 + ": skip i1");
378                i1++;
379            } else {
380                if (DEBUG) Log.d(TAG, "i1=" + i1 + " i2=" + i2 + " N1=" + N1 + ": skip i2");
381                i2++;
382            }
383        }
384
385        mNum = N1;
386
387        return changed;
388    }
389
390    private boolean removeUidsAndNames(WorkSource other) {
391        int N1 = mNum;
392        final int[] uids1 = mUids;
393        final String[] names1 = mNames;
394        final int N2 = other.mNum;
395        final int[] uids2 = other.mUids;
396        final String[] names2 = other.mNames;
397        boolean changed = false;
398        int i1 = 0, i2 = 0;
399        if (DEBUG) Log.d(TAG, "Remove " + other + " from " + this);
400        while (i1 < N1 && i2 < N2) {
401            if (DEBUG) Log.d(TAG, "Step: target @ " + i1 + " of " + N1 + ", other @ " + i2
402                    + " of " + N2 + ": " + uids1[i1] + " " + names1[i1]);
403            if (uids2[i2] == uids1[i1] && names2[i2].equals(names1[i1])) {
404                if (DEBUG) Log.d(TAG, "i1=" + i1 + " i2=" + i2 + " N1=" + N1
405                        + ": remove " + uids1[i1] + " " + names1[i1]);
406                N1--;
407                changed = true;
408                if (i1 < N1) {
409                    System.arraycopy(uids1, i1+1, uids1, i1, N1-i1);
410                    System.arraycopy(names1, i1+1, names1, i1, N1-i1);
411                }
412                i2++;
413            } else if (uids2[i2] > uids1[i1]
414                    || (uids2[i2] == uids1[i1] && names2[i2].compareTo(names1[i1]) > 0)) {
415                if (DEBUG) Log.d(TAG, "i1=" + i1 + " i2=" + i2 + " N1=" + N1 + ": skip i1");
416                i1++;
417            } else {
418                if (DEBUG) Log.d(TAG, "i1=" + i1 + " i2=" + i2 + " N1=" + N1 + ": skip i2");
419                i2++;
420            }
421        }
422
423        mNum = N1;
424
425        return changed;
426    }
427
428    private boolean updateLocked(WorkSource other, boolean set, boolean returnNewbs) {
429        if (mNames == null && other.mNames == null) {
430            return updateUidsLocked(other, set, returnNewbs);
431        } else {
432            if (mNum > 0 && mNames == null) {
433                throw new IllegalArgumentException("Other " + other + " has names, but target "
434                        + this + " does not");
435            }
436            if (other.mNum > 0 && other.mNames == null) {
437                throw new IllegalArgumentException("Target " + this + " has names, but other "
438                        + other + " does not");
439            }
440            return updateUidsAndNamesLocked(other, set, returnNewbs);
441        }
442    }
443
444    private static WorkSource addWork(WorkSource cur, int newUid) {
445        if (cur == null) {
446            return new WorkSource(newUid);
447        }
448        cur.insert(cur.mNum, newUid);
449        return cur;
450    }
451
452    private boolean updateUidsLocked(WorkSource other, boolean set, boolean returnNewbs) {
453        int N1 = mNum;
454        int[] uids1 = mUids;
455        final int N2 = other.mNum;
456        final int[] uids2 = other.mUids;
457        boolean changed = false;
458        int i1 = 0, i2 = 0;
459        if (DEBUG) Log.d(TAG, "Update " + this + " with " + other + " set=" + set
460                + " returnNewbs=" + returnNewbs);
461        while (i1 < N1 || i2 < N2) {
462            if (DEBUG) Log.d(TAG, "Step: target @ " + i1 + " of " + N1 + ", other @ " + i2
463                    + " of " + N2);
464            if (i1 >= N1 || (i2 < N2 && uids2[i2] < uids1[i1])) {
465                // Need to insert a new uid.
466                if (DEBUG) Log.d(TAG, "i1=" + i1 + " i2=" + i2 + " N1=" + N1
467                        + ": insert " + uids2[i2]);
468                changed = true;
469                if (uids1 == null) {
470                    uids1 = new int[4];
471                    uids1[0] = uids2[i2];
472                } else if (N1 >= uids1.length) {
473                    int[] newuids = new int[(uids1.length*3)/2];
474                    if (i1 > 0) System.arraycopy(uids1, 0, newuids, 0, i1);
475                    if (i1 < N1) System.arraycopy(uids1, i1, newuids, i1+1, N1-i1);
476                    uids1 = newuids;
477                    uids1[i1] = uids2[i2];
478                } else {
479                    if (i1 < N1) System.arraycopy(uids1, i1, uids1, i1+1, N1-i1);
480                    uids1[i1] = uids2[i2];
481                }
482                if (returnNewbs) {
483                    sNewbWork = addWork(sNewbWork, uids2[i2]);
484                }
485                N1++;
486                i1++;
487                i2++;
488            } else {
489                if (!set) {
490                    // Skip uids that already exist or are not in 'other'.
491                    if (DEBUG) Log.d(TAG, "i1=" + i1 + " i2=" + i2 + " N1=" + N1 + ": skip");
492                    if (i2 < N2 && uids2[i2] == uids1[i1]) {
493                        i2++;
494                    }
495                    i1++;
496                } else {
497                    // Remove any uids that don't exist in 'other'.
498                    int start = i1;
499                    while (i1 < N1 && (i2 >= N2 || uids2[i2] > uids1[i1])) {
500                        if (DEBUG) Log.d(TAG, "i1=" + i1 + " i2=" + i2 + ": remove " + uids1[i1]);
501                        sGoneWork = addWork(sGoneWork, uids1[i1]);
502                        i1++;
503                    }
504                    if (start < i1) {
505                        System.arraycopy(uids1, i1, uids1, start, N1-i1);
506                        N1 -= i1-start;
507                        i1 = start;
508                    }
509                    // If there is a matching uid, skip it.
510                    if (i1 < N1 && i2 < N2 && uids2[i2] == uids1[i1]) {
511                        if (DEBUG) Log.d(TAG, "i1=" + i1 + " i2=" + i2 + " N1=" + N1 + ": skip");
512                        i1++;
513                        i2++;
514                    }
515                }
516            }
517        }
518
519        mNum = N1;
520        mUids = uids1;
521
522        return changed;
523    }
524
525    /**
526     * Returns 0 if equal, negative if 'this' is before 'other', positive if 'this' is after 'other'.
527     */
528    private int compare(WorkSource other, int i1, int i2) {
529        final int diff = mUids[i1] - other.mUids[i2];
530        if (diff != 0) {
531            return diff;
532        }
533        return mNames[i1].compareTo(other.mNames[i2]);
534    }
535
536    private static WorkSource addWork(WorkSource cur, int newUid, String newName) {
537        if (cur == null) {
538            return new WorkSource(newUid, newName);
539        }
540        cur.insert(cur.mNum, newUid, newName);
541        return cur;
542    }
543
544    private boolean updateUidsAndNamesLocked(WorkSource other, boolean set, boolean returnNewbs) {
545        final int N2 = other.mNum;
546        final int[] uids2 = other.mUids;
547        String[] names2 = other.mNames;
548        boolean changed = false;
549        int i1 = 0, i2 = 0;
550        if (DEBUG) Log.d(TAG, "Update " + this + " with " + other + " set=" + set
551                + " returnNewbs=" + returnNewbs);
552        while (i1 < mNum || i2 < N2) {
553            if (DEBUG) Log.d(TAG, "Step: target @ " + i1 + " of " + mNum + ", other @ " + i2
554                    + " of " + N2);
555            int diff = -1;
556            if (i1 >= mNum || (i2 < N2 && (diff=compare(other, i1, i2)) > 0)) {
557                // Need to insert a new uid.
558                changed = true;
559                if (DEBUG) Log.d(TAG, "i1=" + i1 + " i2=" + i2 + " N1=" + mNum
560                        + ": insert " + uids2[i2] + " " + names2[i2]);
561                insert(i1, uids2[i2], names2[i2]);
562                if (returnNewbs) {
563                    sNewbWork = addWork(sNewbWork, uids2[i2], names2[i2]);
564                }
565                i1++;
566                i2++;
567            } else {
568                if (!set) {
569                    if (DEBUG) Log.d(TAG, "i1=" + i1 + " i2=" + i2 + " N1=" + mNum + ": skip");
570                    if (i2 < N2 && diff == 0) {
571                        i2++;
572                    }
573                    i1++;
574                } else {
575                    // Remove any uids that don't exist in 'other'.
576                    int start = i1;
577                    while (diff < 0) {
578                        if (DEBUG) Log.d(TAG, "i1=" + i1 + " i2=" + i2 + ": remove " + mUids[i1]
579                                + " " + mNames[i1]);
580                        sGoneWork = addWork(sGoneWork, mUids[i1], mNames[i1]);
581                        i1++;
582                        if (i1 >= mNum) {
583                            break;
584                        }
585                        diff = i2 < N2 ? compare(other, i1, i2) : -1;
586                    }
587                    if (start < i1) {
588                        System.arraycopy(mUids, i1, mUids, start, mNum-i1);
589                        System.arraycopy(mNames, i1, mNames, start, mNum-i1);
590                        mNum -= i1-start;
591                        i1 = start;
592                    }
593                    // If there is a matching uid, skip it.
594                    if (i1 < mNum && diff == 0) {
595                        if (DEBUG) Log.d(TAG, "i1=" + i1 + " i2=" + i2 + " N1=" + mNum + ": skip");
596                        i1++;
597                        i2++;
598                    }
599                }
600            }
601        }
602
603        return changed;
604    }
605
606    private void insert(int index, int uid)  {
607        if (DEBUG) Log.d(TAG, "Insert in " + this + " @ " + index + " uid " + uid);
608        if (mUids == null) {
609            mUids = new int[4];
610            mUids[0] = uid;
611            mNum = 1;
612        } else if (mNum >= mUids.length) {
613            int[] newuids = new int[(mNum*3)/2];
614            if (index > 0) {
615                System.arraycopy(mUids, 0, newuids, 0, index);
616            }
617            if (index < mNum) {
618                System.arraycopy(mUids, index, newuids, index+1, mNum-index);
619            }
620            mUids = newuids;
621            mUids[index] = uid;
622            mNum++;
623        } else {
624            if (index < mNum) {
625                System.arraycopy(mUids, index, mUids, index+1, mNum-index);
626            }
627            mUids[index] = uid;
628            mNum++;
629        }
630    }
631
632    private void insert(int index, int uid, String name)  {
633        if (mUids == null) {
634            mUids = new int[4];
635            mUids[0] = uid;
636            mNames = new String[4];
637            mNames[0] = name;
638            mNum = 1;
639        } else if (mNum >= mUids.length) {
640            int[] newuids = new int[(mNum*3)/2];
641            String[] newnames = new String[(mNum*3)/2];
642            if (index > 0) {
643                System.arraycopy(mUids, 0, newuids, 0, index);
644                System.arraycopy(mNames, 0, newnames, 0, index);
645            }
646            if (index < mNum) {
647                System.arraycopy(mUids, index, newuids, index+1, mNum-index);
648                System.arraycopy(mNames, index, newnames, index+1, mNum-index);
649            }
650            mUids = newuids;
651            mNames = newnames;
652            mUids[index] = uid;
653            mNames[index] = name;
654            mNum++;
655        } else {
656            if (index < mNum) {
657                System.arraycopy(mUids, index, mUids, index+1, mNum-index);
658                System.arraycopy(mNames, index, mNames, index+1, mNum-index);
659            }
660            mUids[index] = uid;
661            mNames[index] = name;
662            mNum++;
663        }
664    }
665
666    @Override
667    public int describeContents() {
668        return 0;
669    }
670
671    @Override
672    public void writeToParcel(Parcel dest, int flags) {
673        dest.writeInt(mNum);
674        dest.writeIntArray(mUids);
675        dest.writeStringArray(mNames);
676    }
677
678    @Override
679    public String toString() {
680        StringBuilder result = new StringBuilder();
681        result.append("WorkSource{");
682        for (int i = 0; i < mNum; i++) {
683            if (i != 0) {
684                result.append(", ");
685            }
686            result.append(mUids[i]);
687            if (mNames != null) {
688                result.append(" ");
689                result.append(mNames[i]);
690            }
691        }
692        result.append("}");
693        return result.toString();
694    }
695
696    public static final Parcelable.Creator<WorkSource> CREATOR
697            = new Parcelable.Creator<WorkSource>() {
698        public WorkSource createFromParcel(Parcel in) {
699            return new WorkSource(in);
700        }
701        public WorkSource[] newArray(int size) {
702            return new WorkSource[size];
703        }
704    };
705}
706