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