1 /* 2 * Copyright (C) 2011 The Android Open Source Project 3 * 4 * Licensed under the Apache License, Version 2.0 (the "License"); 5 * you may not use this file except in compliance with the License. 6 * You may obtain a copy of the License at 7 * 8 * http://www.apache.org/licenses/LICENSE-2.0 9 * 10 * Unless required by applicable law or agreed to in writing, software 11 * distributed under the License is distributed on an "AS IS" BASIS, 12 * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied. 13 * See the License for the specific language governing permissions and 14 * limitations under the License. 15 */ 16 17 package com.android.internal.telephony; 18 19 import android.annotation.UnsupportedAppUsage; 20 import java.util.ArrayList; 21 import java.util.Iterator; 22 23 /** 24 * Clients can enable reception of SMS-CB messages for specific ranges of 25 * message identifiers (channels). This class keeps track of the currently 26 * enabled message identifiers and calls abstract methods to update the 27 * radio when the range of enabled message identifiers changes. 28 * 29 * An update is a call to {@link #startUpdate} followed by zero or more 30 * calls to {@link #addRange} followed by a call to {@link #finishUpdate}. 31 * Calls to {@link #enableRange} and {@link #disableRange} will perform 32 * an incremental update operation if the enabled ranges have changed. 33 * A full update operation (i.e. after a radio reset) can be performed 34 * by a call to {@link #updateRanges}. 35 * 36 * Clients are identified by String (the name associated with the User ID 37 * of the caller) so that a call to remove a range can be mapped to the 38 * client that enabled that range (or else rejected). 39 */ 40 public abstract class IntRangeManager { 41 42 /** 43 * Initial capacity for IntRange clients array list. There will be 44 * few cell broadcast listeners on a typical device, so this can be small. 45 */ 46 private static final int INITIAL_CLIENTS_ARRAY_SIZE = 4; 47 48 /** 49 * One or more clients forming the continuous range [startId, endId]. 50 * <p>When a client is added, the IntRange may merge with one or more 51 * adjacent IntRanges to form a single combined IntRange. 52 * <p>When a client is removed, the IntRange may divide into several 53 * non-contiguous IntRanges. 54 */ 55 private class IntRange { 56 int mStartId; 57 int mEndId; 58 // sorted by earliest start id 59 final ArrayList<ClientRange> mClients; 60 61 /** 62 * Create a new IntRange with a single client. 63 * @param startId the first id included in the range 64 * @param endId the last id included in the range 65 * @param client the client requesting the enabled range 66 */ IntRange(int startId, int endId, String client)67 IntRange(int startId, int endId, String client) { 68 mStartId = startId; 69 mEndId = endId; 70 mClients = new ArrayList<ClientRange>(INITIAL_CLIENTS_ARRAY_SIZE); 71 mClients.add(new ClientRange(startId, endId, client)); 72 } 73 74 /** 75 * Create a new IntRange for an existing ClientRange. 76 * @param clientRange the initial ClientRange to add 77 */ IntRange(ClientRange clientRange)78 IntRange(ClientRange clientRange) { 79 mStartId = clientRange.mStartId; 80 mEndId = clientRange.mEndId; 81 mClients = new ArrayList<ClientRange>(INITIAL_CLIENTS_ARRAY_SIZE); 82 mClients.add(clientRange); 83 } 84 85 /** 86 * Create a new IntRange from an existing IntRange. This is used for 87 * removing a ClientRange, because new IntRanges may need to be created 88 * for any gaps that open up after the ClientRange is removed. A copy 89 * is made of the elements of the original IntRange preceding the element 90 * that is being removed. The following elements will be added to this 91 * IntRange or to a new IntRange when a gap is found. 92 * @param intRange the original IntRange to copy elements from 93 * @param numElements the number of elements to copy from the original 94 */ IntRange(IntRange intRange, int numElements)95 IntRange(IntRange intRange, int numElements) { 96 mStartId = intRange.mStartId; 97 mEndId = intRange.mEndId; 98 mClients = new ArrayList<ClientRange>(intRange.mClients.size()); 99 for (int i=0; i < numElements; i++) { 100 mClients.add(intRange.mClients.get(i)); 101 } 102 } 103 104 /** 105 * Insert new ClientRange in order by start id, then by end id 106 * <p>If the new ClientRange is known to be sorted before or after the 107 * existing ClientRanges, or at a particular index, it can be added 108 * to the clients array list directly, instead of via this method. 109 * <p>Note that this can be changed from linear to binary search if the 110 * number of clients grows large enough that it would make a difference. 111 * @param range the new ClientRange to insert 112 */ insert(ClientRange range)113 void insert(ClientRange range) { 114 int len = mClients.size(); 115 int insert = -1; 116 for (int i=0; i < len; i++) { 117 ClientRange nextRange = mClients.get(i); 118 if (range.mStartId <= nextRange.mStartId) { 119 // ignore duplicate ranges from the same client 120 if (!range.equals(nextRange)) { 121 // check if same startId, then order by endId 122 if (range.mStartId == nextRange.mStartId 123 && range.mEndId > nextRange.mEndId) { 124 insert = i + 1; 125 if (insert < len) { 126 // there may be more client following with same startId 127 // new [1, 5] existing [1, 2] [1, 4] [1, 7] 128 continue; 129 } 130 break; 131 } 132 mClients.add(i, range); 133 } 134 return; 135 } 136 } 137 if (insert != -1 && insert < len) { 138 mClients.add(insert, range); 139 return; 140 } 141 mClients.add(range); // append to end of list 142 } 143 } 144 145 /** 146 * The message id range for a single client. 147 */ 148 private class ClientRange { 149 final int mStartId; 150 final int mEndId; 151 final String mClient; 152 ClientRange(int startId, int endId, String client)153 ClientRange(int startId, int endId, String client) { 154 mStartId = startId; 155 mEndId = endId; 156 mClient = client; 157 } 158 159 @Override equals(Object o)160 public boolean equals(Object o) { 161 if (o != null && o instanceof ClientRange) { 162 ClientRange other = (ClientRange) o; 163 return mStartId == other.mStartId && 164 mEndId == other.mEndId && 165 mClient.equals(other.mClient); 166 } else { 167 return false; 168 } 169 } 170 171 @Override hashCode()172 public int hashCode() { 173 return (mStartId * 31 + mEndId) * 31 + mClient.hashCode(); 174 } 175 } 176 177 /** 178 * List of integer ranges, one per client, sorted by start id. 179 */ 180 @UnsupportedAppUsage 181 private ArrayList<IntRange> mRanges = new ArrayList<IntRange>(); 182 IntRangeManager()183 protected IntRangeManager() {} 184 185 /** 186 * Enable a range for the specified client and update ranges 187 * if necessary. If {@link #finishUpdate} returns failure, 188 * false is returned and the range is not added. 189 * 190 * @param startId the first id included in the range 191 * @param endId the last id included in the range 192 * @param client the client requesting the enabled range 193 * @return true if successful, false otherwise 194 */ enableRange(int startId, int endId, String client)195 public synchronized boolean enableRange(int startId, int endId, String client) { 196 int len = mRanges.size(); 197 198 // empty range list: add the initial IntRange 199 if (len == 0) { 200 if (tryAddRanges(startId, endId, true)) { 201 mRanges.add(new IntRange(startId, endId, client)); 202 return true; 203 } else { 204 return false; // failed to update radio 205 } 206 } 207 208 for (int startIndex = 0; startIndex < len; startIndex++) { 209 IntRange range = mRanges.get(startIndex); 210 if ((startId) >= range.mStartId && (endId) <= range.mEndId) { 211 // exact same range: new [1, 1] existing [1, 1] 212 // range already enclosed in existing: new [3, 3], [1,3] 213 // no radio update necessary. 214 // duplicate "client" check is done in insert, attempt to insert. 215 range.insert(new ClientRange(startId, endId, client)); 216 return true; 217 } else if ((startId - 1) == range.mEndId) { 218 // new [3, x] existing [1, 2] OR new [2, 2] existing [1, 1] 219 // found missing link? check if next range can be joined 220 int newRangeEndId = endId; 221 IntRange nextRange = null; 222 if ((startIndex + 1) < len) { 223 nextRange = mRanges.get(startIndex + 1); 224 if ((nextRange.mStartId - 1) <= endId) { 225 // new [3, x] existing [1, 2] [5, 7] OR new [2 , 2] existing [1, 1] [3, 5] 226 if (endId <= nextRange.mEndId) { 227 // new [3, 6] existing [1, 2] [5, 7] 228 newRangeEndId = nextRange.mStartId - 1; // need to enable [3, 4] 229 } 230 } else { 231 // mark nextRange to be joined as null. 232 nextRange = null; 233 } 234 } 235 if (tryAddRanges(startId, newRangeEndId, true)) { 236 range.mEndId = endId; 237 range.insert(new ClientRange(startId, endId, client)); 238 239 // found missing link? check if next range can be joined 240 if (nextRange != null) { 241 if (range.mEndId < nextRange.mEndId) { 242 // new [3, 6] existing [1, 2] [5, 10] 243 range.mEndId = nextRange.mEndId; 244 } 245 range.mClients.addAll(nextRange.mClients); 246 mRanges.remove(nextRange); 247 } 248 return true; 249 } else { 250 return false; // failed to update radio 251 } 252 } else if (startId < range.mStartId) { 253 // new [1, x] , existing [5, y] 254 // test if new range completely precedes this range 255 // note that [1, 4] and [5, 6] coalesce to [1, 6] 256 if ((endId + 1) < range.mStartId) { 257 // new [1, 3] existing [5, 6] non contiguous case 258 // insert new int range before previous first range 259 if (tryAddRanges(startId, endId, true)) { 260 mRanges.add(startIndex, new IntRange(startId, endId, client)); 261 return true; 262 } else { 263 return false; // failed to update radio 264 } 265 } else if (endId <= range.mEndId) { 266 // new [1, 4] existing [5, 6] or new [1, 1] existing [2, 2] 267 // extend the start of this range 268 if (tryAddRanges(startId, range.mStartId - 1, true)) { 269 range.mStartId = startId; 270 range.mClients.add(0, new ClientRange(startId, endId, client)); 271 return true; 272 } else { 273 return false; // failed to update radio 274 } 275 } else { 276 // find last range that can coalesce into the new combined range 277 for (int endIndex = startIndex+1; endIndex < len; endIndex++) { 278 IntRange endRange = mRanges.get(endIndex); 279 if ((endId + 1) < endRange.mStartId) { 280 // new [1, 10] existing [2, 3] [14, 15] 281 // try to add entire new range 282 if (tryAddRanges(startId, endId, true)) { 283 range.mStartId = startId; 284 range.mEndId = endId; 285 // insert new ClientRange before existing ranges 286 range.mClients.add(0, new ClientRange(startId, endId, client)); 287 // coalesce range with following ranges up to endIndex-1 288 // remove each range after adding its elements, so the index 289 // of the next range to join is always startIndex+1. 290 // i is the index if no elements were removed: we only care 291 // about the number of loop iterations, not the value of i. 292 int joinIndex = startIndex + 1; 293 for (int i = joinIndex; i < endIndex; i++) { 294 // new [1, 10] existing [2, 3] [5, 6] [14, 15] 295 IntRange joinRange = mRanges.get(joinIndex); 296 range.mClients.addAll(joinRange.mClients); 297 mRanges.remove(joinRange); 298 } 299 return true; 300 } else { 301 return false; // failed to update radio 302 } 303 } else if (endId <= endRange.mEndId) { 304 // new [1, 10] existing [2, 3] [5, 15] 305 // add range from start id to start of last overlapping range, 306 // values from endRange.startId to endId are already enabled 307 if (tryAddRanges(startId, endRange.mStartId - 1, true)) { 308 range.mStartId = startId; 309 range.mEndId = endRange.mEndId; 310 // insert new ClientRange before existing ranges 311 range.mClients.add(0, new ClientRange(startId, endId, client)); 312 // coalesce range with following ranges up to endIndex 313 // remove each range after adding its elements, so the index 314 // of the next range to join is always startIndex+1. 315 // i is the index if no elements were removed: we only care 316 // about the number of loop iterations, not the value of i. 317 int joinIndex = startIndex + 1; 318 for (int i = joinIndex; i <= endIndex; i++) { 319 IntRange joinRange = mRanges.get(joinIndex); 320 range.mClients.addAll(joinRange.mClients); 321 mRanges.remove(joinRange); 322 } 323 return true; 324 } else { 325 return false; // failed to update radio 326 } 327 } 328 } 329 330 // new [1, 10] existing [2, 3] 331 // endId extends past all existing IntRanges: combine them all together 332 if (tryAddRanges(startId, endId, true)) { 333 range.mStartId = startId; 334 range.mEndId = endId; 335 // insert new ClientRange before existing ranges 336 range.mClients.add(0, new ClientRange(startId, endId, client)); 337 // coalesce range with following ranges up to len-1 338 // remove each range after adding its elements, so the index 339 // of the next range to join is always startIndex+1. 340 // i is the index if no elements were removed: we only care 341 // about the number of loop iterations, not the value of i. 342 int joinIndex = startIndex + 1; 343 for (int i = joinIndex; i < len; i++) { 344 // new [1, 10] existing [2, 3] [5, 6] 345 IntRange joinRange = mRanges.get(joinIndex); 346 range.mClients.addAll(joinRange.mClients); 347 mRanges.remove(joinRange); 348 } 349 return true; 350 } else { 351 return false; // failed to update radio 352 } 353 } 354 } else if ((startId + 1) <= range.mEndId) { 355 // new [2, x] existing [1, 4] 356 if (endId <= range.mEndId) { 357 // new [2, 3] existing [1, 4] 358 // completely contained in existing range; no radio changes 359 range.insert(new ClientRange(startId, endId, client)); 360 return true; 361 } else { 362 // new [2, 5] existing [1, 4] 363 // find last range that can coalesce into the new combined range 364 int endIndex = startIndex; 365 for (int testIndex = startIndex+1; testIndex < len; testIndex++) { 366 IntRange testRange = mRanges.get(testIndex); 367 if ((endId + 1) < testRange.mStartId) { 368 break; 369 } else { 370 endIndex = testIndex; 371 } 372 } 373 // no adjacent IntRanges to combine 374 if (endIndex == startIndex) { 375 // new [2, 5] existing [1, 4] 376 // add range from range.endId+1 to endId, 377 // values from startId to range.endId are already enabled 378 if (tryAddRanges(range.mEndId + 1, endId, true)) { 379 range.mEndId = endId; 380 range.insert(new ClientRange(startId, endId, client)); 381 return true; 382 } else { 383 return false; // failed to update radio 384 } 385 } 386 // get last range to coalesce into start range 387 IntRange endRange = mRanges.get(endIndex); 388 // Values from startId to range.endId have already been enabled. 389 // if endId > endRange.endId, then enable range from range.endId+1 to endId, 390 // else enable range from range.endId+1 to endRange.startId-1, because 391 // values from endRange.startId to endId have already been added. 392 int newRangeEndId = (endId <= endRange.mEndId) ? endRange.mStartId - 1 : endId; 393 // new [2, 10] existing [1, 4] [7, 8] OR 394 // new [2, 10] existing [1, 4] [7, 15] 395 if (tryAddRanges(range.mEndId + 1, newRangeEndId, true)) { 396 newRangeEndId = (endId <= endRange.mEndId) ? endRange.mEndId : endId; 397 range.mEndId = newRangeEndId; 398 // insert new ClientRange in place 399 range.insert(new ClientRange(startId, endId, client)); 400 // coalesce range with following ranges up to endIndex 401 // remove each range after adding its elements, so the index 402 // of the next range to join is always startIndex+1 (joinIndex). 403 // i is the index if no elements had been removed: we only care 404 // about the number of loop iterations, not the value of i. 405 int joinIndex = startIndex + 1; 406 for (int i = joinIndex; i <= endIndex; i++) { 407 IntRange joinRange = mRanges.get(joinIndex); 408 range.mClients.addAll(joinRange.mClients); 409 mRanges.remove(joinRange); 410 } 411 return true; 412 } else { 413 return false; // failed to update radio 414 } 415 } 416 } 417 } 418 419 // new [5, 6], existing [1, 3] 420 // append new range after existing IntRanges 421 if (tryAddRanges(startId, endId, true)) { 422 mRanges.add(new IntRange(startId, endId, client)); 423 return true; 424 } else { 425 return false; // failed to update radio 426 } 427 } 428 429 /** 430 * Disable a range for the specified client and update ranges 431 * if necessary. If {@link #finishUpdate} returns failure, 432 * false is returned and the range is not removed. 433 * 434 * @param startId the first id included in the range 435 * @param endId the last id included in the range 436 * @param client the client requesting to disable the range 437 * @return true if successful, false otherwise 438 */ disableRange(int startId, int endId, String client)439 public synchronized boolean disableRange(int startId, int endId, String client) { 440 int len = mRanges.size(); 441 442 for (int i=0; i < len; i++) { 443 IntRange range = mRanges.get(i); 444 if (startId < range.mStartId) { 445 return false; // not found 446 } else if (endId <= range.mEndId) { 447 // found the IntRange that encloses the client range, if any 448 // search for it in the clients list 449 ArrayList<ClientRange> clients = range.mClients; 450 451 // handle common case of IntRange containing one ClientRange 452 int crLength = clients.size(); 453 if (crLength == 1) { 454 ClientRange cr = clients.get(0); 455 if (cr.mStartId == startId && cr.mEndId == endId && cr.mClient.equals(client)) { 456 // mRange contains only what's enabled. 457 // remove the range from mRange then update the radio 458 mRanges.remove(i); 459 if (updateRanges()) { 460 return true; 461 } else { 462 // failed to update radio. insert back the range 463 mRanges.add(i, range); 464 return false; 465 } 466 } else { 467 return false; // not found 468 } 469 } 470 471 // several ClientRanges: remove one, potentially splitting into many IntRanges. 472 // Save the original start and end id for the original IntRange 473 // in case the radio update fails and we have to revert it. If the 474 // update succeeds, we remove the client range and insert the new IntRanges. 475 // clients are ordered by startId then by endId, so client with largest endId 476 // can be anywhere. Need to loop thru to find largestEndId. 477 int largestEndId = Integer.MIN_VALUE; // largest end identifier found 478 boolean updateStarted = false; 479 480 // crlength >= 2 481 for (int crIndex=0; crIndex < crLength; crIndex++) { 482 ClientRange cr = clients.get(crIndex); 483 if (cr.mStartId == startId && cr.mEndId == endId && cr.mClient.equals(client)) { 484 // found the ClientRange to remove, check if it's the last in the list 485 if (crIndex == crLength - 1) { 486 if (range.mEndId == largestEndId) { 487 // remove [2, 5] from [1, 7] [2, 5] 488 // no channels to remove from radio; return success 489 clients.remove(crIndex); 490 return true; 491 } else { 492 // disable the channels at the end and lower the end id 493 clients.remove(crIndex); 494 range.mEndId = largestEndId; 495 if (updateRanges()) { 496 return true; 497 } else { 498 clients.add(crIndex, cr); 499 range.mEndId = cr.mEndId; 500 return false; 501 } 502 } 503 } 504 505 // copy the IntRange so that we can remove elements and modify the 506 // start and end id's in the copy, leaving the original unmodified 507 // until after the radio update succeeds 508 IntRange rangeCopy = new IntRange(range, crIndex); 509 510 if (crIndex == 0) { 511 // removing the first ClientRange, so we may need to increase 512 // the start id of the IntRange. 513 // We know there are at least two ClientRanges in the list, 514 // because check for just one ClientRanges case is already handled 515 // so clients.get(1) should always succeed. 516 int nextStartId = clients.get(1).mStartId; 517 if (nextStartId != range.mStartId) { 518 updateStarted = true; 519 rangeCopy.mStartId = nextStartId; 520 } 521 // init largestEndId 522 largestEndId = clients.get(1).mEndId; 523 } 524 525 // go through remaining ClientRanges, creating new IntRanges when 526 // there is a gap in the sequence. After radio update succeeds, 527 // remove the original IntRange and append newRanges to mRanges. 528 // Otherwise, leave the original IntRange in mRanges and return false. 529 ArrayList<IntRange> newRanges = new ArrayList<IntRange>(); 530 531 IntRange currentRange = rangeCopy; 532 for (int nextIndex = crIndex + 1; nextIndex < crLength; nextIndex++) { 533 ClientRange nextCr = clients.get(nextIndex); 534 if (nextCr.mStartId > largestEndId + 1) { 535 updateStarted = true; 536 currentRange.mEndId = largestEndId; 537 newRanges.add(currentRange); 538 currentRange = new IntRange(nextCr); 539 } else { 540 if (currentRange.mEndId < nextCr.mEndId) { 541 currentRange.mEndId = nextCr.mEndId; 542 } 543 currentRange.mClients.add(nextCr); 544 } 545 if (nextCr.mEndId > largestEndId) { 546 largestEndId = nextCr.mEndId; 547 } 548 } 549 550 // remove any channels between largestEndId and endId 551 if (largestEndId < endId) { 552 updateStarted = true; 553 currentRange.mEndId = largestEndId; 554 } 555 newRanges.add(currentRange); 556 557 // replace the original IntRange with newRanges 558 mRanges.remove(i); 559 mRanges.addAll(i, newRanges); 560 if (updateStarted && !updateRanges()) { 561 // failed to update radio. revert back mRange. 562 mRanges.removeAll(newRanges); 563 mRanges.add(i, range); 564 return false; 565 } 566 567 return true; 568 } else { 569 // not the ClientRange to remove; save highest end ID seen so far 570 if (cr.mEndId > largestEndId) { 571 largestEndId = cr.mEndId; 572 } 573 } 574 } 575 } 576 } 577 578 return false; // not found 579 } 580 581 /** 582 * Perform a complete update operation (enable all ranges). Useful 583 * after a radio reset. Calls {@link #startUpdate}, followed by zero or 584 * more calls to {@link #addRange}, followed by {@link #finishUpdate}. 585 * @return true if successful, false otherwise 586 */ updateRanges()587 public boolean updateRanges() { 588 startUpdate(); 589 590 populateAllRanges(); 591 return finishUpdate(); 592 } 593 594 /** 595 * Enable or disable a single range of message identifiers. 596 * @param startId the first id included in the range 597 * @param endId the last id included in the range 598 * @param selected true to enable range, false to disable range 599 * @return true if successful, false otherwise 600 */ tryAddRanges(int startId, int endId, boolean selected)601 protected boolean tryAddRanges(int startId, int endId, boolean selected) { 602 603 startUpdate(); 604 populateAllRanges(); 605 // This is the new range to be enabled 606 addRange(startId, endId, selected); // adds to mConfigList 607 return finishUpdate(); 608 } 609 610 /** 611 * Returns whether the list of ranges is completely empty. 612 * @return true if there are no enabled ranges 613 */ isEmpty()614 public boolean isEmpty() { 615 return mRanges.isEmpty(); 616 } 617 618 /** 619 * Called when attempting to add a single range of message identifiers 620 * Populate all ranges of message identifiers. 621 */ populateAllRanges()622 private void populateAllRanges() { 623 Iterator<IntRange> itr = mRanges.iterator(); 624 // Populate all ranges from mRanges 625 while (itr.hasNext()) { 626 IntRange currRange = (IntRange) itr.next(); 627 addRange(currRange.mStartId, currRange.mEndId, true); 628 } 629 } 630 631 /** 632 * Called when attempting to add a single range of message identifiers 633 * Populate all ranges of message identifiers using clients' ranges. 634 */ populateAllClientRanges()635 private void populateAllClientRanges() { 636 int len = mRanges.size(); 637 for (int i = 0; i < len; i++) { 638 IntRange range = mRanges.get(i); 639 640 int clientLen = range.mClients.size(); 641 for (int j=0; j < clientLen; j++) { 642 ClientRange nextRange = range.mClients.get(j); 643 addRange(nextRange.mStartId, nextRange.mEndId, true); 644 } 645 } 646 } 647 648 /** 649 * Called when the list of enabled ranges has changed. This will be 650 * followed by zero or more calls to {@link #addRange} followed by 651 * a call to {@link #finishUpdate}. 652 */ startUpdate()653 protected abstract void startUpdate(); 654 655 /** 656 * Called after {@link #startUpdate} to indicate a range of enabled 657 * or disabled values. 658 * 659 * @param startId the first id included in the range 660 * @param endId the last id included in the range 661 * @param selected true to enable range, false to disable range 662 */ addRange(int startId, int endId, boolean selected)663 protected abstract void addRange(int startId, int endId, boolean selected); 664 665 /** 666 * Called to indicate the end of a range update started by the 667 * previous call to {@link #startUpdate}. 668 * @return true if successful, false otherwise 669 */ finishUpdate()670 protected abstract boolean finishUpdate(); 671 } 672