1 package android.os; 2 3 import android.util.Log; 4 5 import 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 */ 12 public 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 */ WorkSource()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 */ WorkSource(WorkSource orig)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 */ WorkSource(int uid)62 public WorkSource(int uid) { 63 mNum = 1; 64 mUids = new int[] { uid, 0 }; 65 mNames = null; 66 } 67 68 /** @hide */ WorkSource(int uid, String name)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 WorkSource(Parcel in)78 WorkSource(Parcel in) { 79 mNum = in.readInt(); 80 mUids = in.createIntArray(); 81 mNames = in.createStringArray(); 82 } 83 84 /** @hide */ size()85 public int size() { 86 return mNum; 87 } 88 89 /** @hide */ get(int index)90 public int get(int index) { 91 return mUids[index]; 92 } 93 94 /** @hide */ getName(int index)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 */ clearNames()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 */ clear()126 public void clear() { 127 mNum = 0; 128 } 129 130 @Override equals(Object o)131 public boolean equals(Object o) { 132 return o instanceof WorkSource && !diff((WorkSource)o); 133 } 134 135 @Override hashCode()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 */ diff(WorkSource other)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 */ set(WorkSource other)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 */ set(int uid)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 */ set(int uid, String name)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 */ setReturningDiffs(WorkSource other)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 */ add(WorkSource other)250 public boolean add(WorkSource other) { 251 synchronized (sTmpWorkSource) { 252 return updateLocked(other, false, false); 253 } 254 } 255 256 /** @hide */ addReturningNewbs(WorkSource other)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 */ add(int uid)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 */ add(int uid, String name)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 */ addReturningNewbs(int uid)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 remove(WorkSource other)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 */ stripNames()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 removeUids(WorkSource other)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 removeUidsAndNames(WorkSource other)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 updateLocked(WorkSource other, boolean set, boolean returnNewbs)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 addWork(WorkSource cur, int newUid)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 updateUidsLocked(WorkSource other, boolean set, boolean returnNewbs)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 */ compare(WorkSource other, int i1, int i2)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 addWork(WorkSource cur, int newUid, String newName)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 updateUidsAndNamesLocked(WorkSource other, boolean set, boolean returnNewbs)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