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