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