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