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