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 startId; 56 int endId; 57 // sorted by earliest start id 58 final ArrayList<ClientRange> clients; 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 this.startId = startId; 68 this.endId = endId; 69 clients = new ArrayList<ClientRange>(INITIAL_CLIENTS_ARRAY_SIZE); 70 clients.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 startId = clientRange.startId; 79 endId = clientRange.endId; 80 clients = new ArrayList<ClientRange>(INITIAL_CLIENTS_ARRAY_SIZE); 81 clients.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 this.startId = intRange.startId; 96 this.endId = intRange.endId; 97 this.clients = new ArrayList<ClientRange>(intRange.clients.size()); 98 for (int i=0; i < numElements; i++) { 99 this.clients.add(intRange.clients.get(i)); 100 } 101 } 102 103 /** 104 * Insert new ClientRange in order by start 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 = clients.size(); 114 for (int i=0; i < len; i++) { 115 ClientRange nextRange = clients.get(i); 116 if (range.startId <= nextRange.startId) { 117 // ignore duplicate ranges from the same client 118 if (!range.equals(nextRange)) { 119 clients.add(i, range); 120 } 121 return; 122 } 123 } 124 clients.add(range); // append to end of list 125 } 126 } 127 128 /** 129 * The message id range for a single client. 130 */ 131 private class ClientRange { 132 final int startId; 133 final int endId; 134 final String client; 135 136 ClientRange(int startId, int endId, String client) { 137 this.startId = startId; 138 this.endId = endId; 139 this.client = client; 140 } 141 142 @Override 143 public boolean equals(Object o) { 144 if (o != null && o instanceof ClientRange) { 145 ClientRange other = (ClientRange) o; 146 return startId == other.startId && 147 endId == other.endId && 148 client.equals(other.client); 149 } else { 150 return false; 151 } 152 } 153 154 @Override 155 public int hashCode() { 156 return (startId * 31 + endId) * 31 + client.hashCode(); 157 } 158 } 159 160 /** 161 * List of integer ranges, one per client, sorted by start id. 162 */ 163 private ArrayList<IntRange> mRanges = new ArrayList<IntRange>(); 164 165 protected IntRangeManager() {} 166 167 /** 168 * Enable a range for the specified client and update ranges 169 * if necessary. If {@link #finishUpdate} returns failure, 170 * false is returned and the range is not added. 171 * 172 * @param startId the first id included in the range 173 * @param endId the last id included in the range 174 * @param client the client requesting the enabled range 175 * @return true if successful, false otherwise 176 */ 177 public synchronized boolean enableRange(int startId, int endId, String client) { 178 int len = mRanges.size(); 179 180 // empty range list: add the initial IntRange 181 if (len == 0) { 182 if (tryAddSingleRange(startId, endId, true)) { 183 mRanges.add(new IntRange(startId, endId, client)); 184 return true; 185 } else { 186 return false; // failed to update radio 187 } 188 } 189 190 for (int startIndex = 0; startIndex < len; startIndex++) { 191 IntRange range = mRanges.get(startIndex); 192 if (startId < range.startId) { 193 // test if new range completely precedes this range 194 // note that [1, 4] and [5, 6] coalesce to [1, 6] 195 if ((endId + 1) < range.startId) { 196 // insert new int range before previous first range 197 if (tryAddSingleRange(startId, endId, true)) { 198 mRanges.add(startIndex, new IntRange(startId, endId, client)); 199 return true; 200 } else { 201 return false; // failed to update radio 202 } 203 } else if (endId <= range.endId) { 204 // extend the start of this range 205 if (tryAddSingleRange(startId, range.startId - 1, true)) { 206 range.startId = startId; 207 range.clients.add(0, new ClientRange(startId, endId, client)); 208 return true; 209 } else { 210 return false; // failed to update radio 211 } 212 } else { 213 // find last range that can coalesce into the new combined range 214 for (int endIndex = startIndex+1; endIndex < len; endIndex++) { 215 IntRange endRange = mRanges.get(endIndex); 216 if ((endId + 1) < endRange.startId) { 217 // try to add entire new range 218 if (tryAddSingleRange(startId, endId, true)) { 219 range.startId = startId; 220 range.endId = endId; 221 // insert new ClientRange before existing ranges 222 range.clients.add(0, new ClientRange(startId, endId, client)); 223 // coalesce range with following ranges up to endIndex-1 224 // remove each range after adding its elements, so the index 225 // of the next range to join is always startIndex+1. 226 // i is the index if no elements were removed: we only care 227 // about the number of loop iterations, not the value of i. 228 int joinIndex = startIndex + 1; 229 for (int i = joinIndex; i < endIndex; i++) { 230 IntRange joinRange = mRanges.get(joinIndex); 231 range.clients.addAll(joinRange.clients); 232 mRanges.remove(joinRange); 233 } 234 return true; 235 } else { 236 return false; // failed to update radio 237 } 238 } else if (endId <= endRange.endId) { 239 // add range from start id to start of last overlapping range, 240 // values from endRange.startId to endId are already enabled 241 if (tryAddSingleRange(startId, endRange.startId - 1, true)) { 242 range.startId = startId; 243 range.endId = endRange.endId; 244 // insert new ClientRange before existing ranges 245 range.clients.add(0, new ClientRange(startId, endId, client)); 246 // coalesce range with following ranges up to endIndex 247 // remove each range after adding its elements, so the index 248 // of the next range to join is always startIndex+1. 249 // i is the index if no elements were removed: we only care 250 // about the number of loop iterations, not the value of i. 251 int joinIndex = startIndex + 1; 252 for (int i = joinIndex; i <= endIndex; i++) { 253 IntRange joinRange = mRanges.get(joinIndex); 254 range.clients.addAll(joinRange.clients); 255 mRanges.remove(joinRange); 256 } 257 return true; 258 } else { 259 return false; // failed to update radio 260 } 261 } 262 } 263 264 // endId extends past all existing IntRanges: combine them all together 265 if (tryAddSingleRange(startId, endId, true)) { 266 range.startId = startId; 267 range.endId = endId; 268 // insert new ClientRange before existing ranges 269 range.clients.add(0, new ClientRange(startId, endId, client)); 270 // coalesce range with following ranges up to len-1 271 // remove each range after adding its elements, so the index 272 // of the next range to join is always startIndex+1. 273 // i is the index if no elements were removed: we only care 274 // about the number of loop iterations, not the value of i. 275 int joinIndex = startIndex + 1; 276 for (int i = joinIndex; i < len; i++) { 277 IntRange joinRange = mRanges.get(joinIndex); 278 range.clients.addAll(joinRange.clients); 279 mRanges.remove(joinRange); 280 } 281 return true; 282 } else { 283 return false; // failed to update radio 284 } 285 } 286 } else if ((startId + 1) <= range.endId) { 287 if (endId <= range.endId) { 288 // completely contained in existing range; no radio changes 289 range.insert(new ClientRange(startId, endId, client)); 290 return true; 291 } else { 292 // find last range that can coalesce into the new combined range 293 int endIndex = startIndex; 294 for (int testIndex = startIndex+1; testIndex < len; testIndex++) { 295 IntRange testRange = mRanges.get(testIndex); 296 if ((endId + 1) < testRange.startId) { 297 break; 298 } else { 299 endIndex = testIndex; 300 } 301 } 302 // no adjacent IntRanges to combine 303 if (endIndex == startIndex) { 304 // add range from range.endId+1 to endId, 305 // values from startId to range.endId are already enabled 306 if (tryAddSingleRange(range.endId + 1, endId, true)) { 307 range.endId = endId; 308 range.insert(new ClientRange(startId, endId, client)); 309 return true; 310 } else { 311 return false; // failed to update radio 312 } 313 } 314 // get last range to coalesce into start range 315 IntRange endRange = mRanges.get(endIndex); 316 // Values from startId to range.endId have already been enabled. 317 // if endId > endRange.endId, then enable range from range.endId+1 to endId, 318 // else enable range from range.endId+1 to endRange.startId-1, because 319 // values from endRange.startId to endId have already been added. 320 int newRangeEndId = (endId <= endRange.endId) ? endRange.startId - 1 : endId; 321 if (tryAddSingleRange(range.endId + 1, newRangeEndId, true)) { 322 range.endId = endId; 323 // insert new ClientRange in place 324 range.insert(new ClientRange(startId, endId, client)); 325 // coalesce range with following ranges up to endIndex-1 326 // remove each range after adding its elements, so the index 327 // of the next range to join is always startIndex+1 (joinIndex). 328 // i is the index if no elements had been removed: we only care 329 // about the number of loop iterations, not the value of i. 330 int joinIndex = startIndex + 1; 331 for (int i = joinIndex; i < endIndex; i++) { 332 IntRange joinRange = mRanges.get(joinIndex); 333 range.clients.addAll(joinRange.clients); 334 mRanges.remove(joinRange); 335 } 336 return true; 337 } else { 338 return false; // failed to update radio 339 } 340 } 341 } 342 } 343 344 // append new range after existing IntRanges 345 if (tryAddSingleRange(startId, endId, true)) { 346 mRanges.add(new IntRange(startId, endId, client)); 347 return true; 348 } else { 349 return false; // failed to update radio 350 } 351 } 352 353 /** 354 * Disable a range for the specified client and update ranges 355 * if necessary. If {@link #finishUpdate} returns failure, 356 * false is returned and the range is not removed. 357 * 358 * @param startId the first id included in the range 359 * @param endId the last id included in the range 360 * @param client the client requesting to disable the range 361 * @return true if successful, false otherwise 362 */ 363 public synchronized boolean disableRange(int startId, int endId, String client) { 364 int len = mRanges.size(); 365 366 for (int i=0; i < len; i++) { 367 IntRange range = mRanges.get(i); 368 if (startId < range.startId) { 369 return false; // not found 370 } else if (endId <= range.endId) { 371 // found the IntRange that encloses the client range, if any 372 // search for it in the clients list 373 ArrayList<ClientRange> clients = range.clients; 374 375 // handle common case of IntRange containing one ClientRange 376 int crLength = clients.size(); 377 if (crLength == 1) { 378 ClientRange cr = clients.get(0); 379 if (cr.startId == startId && cr.endId == endId && cr.client.equals(client)) { 380 // disable range in radio then remove the entire IntRange 381 if (tryAddSingleRange(startId, endId, false)) { 382 mRanges.remove(i); 383 return true; 384 } else { 385 return false; // failed to update radio 386 } 387 } else { 388 return false; // not found 389 } 390 } 391 392 // several ClientRanges: remove one, potentially splitting into many IntRanges. 393 // Save the original start and end id for the original IntRange 394 // in case the radio update fails and we have to revert it. If the 395 // update succeeds, we remove the client range and insert the new IntRanges. 396 int largestEndId = Integer.MIN_VALUE; // largest end identifier found 397 boolean updateStarted = false; 398 399 for (int crIndex=0; crIndex < crLength; crIndex++) { 400 ClientRange cr = clients.get(crIndex); 401 if (cr.startId == startId && cr.endId == endId && cr.client.equals(client)) { 402 // found the ClientRange to remove, check if it's the last in the list 403 if (crIndex == crLength - 1) { 404 if (range.endId == largestEndId) { 405 // no channels to remove from radio; return success 406 clients.remove(crIndex); 407 return true; 408 } else { 409 // disable the channels at the end and lower the end id 410 if (tryAddSingleRange(largestEndId + 1, range.endId, false)) { 411 clients.remove(crIndex); 412 range.endId = largestEndId; 413 return true; 414 } else { 415 return false; 416 } 417 } 418 } 419 420 // copy the IntRange so that we can remove elements and modify the 421 // start and end id's in the copy, leaving the original unmodified 422 // until after the radio update succeeds 423 IntRange rangeCopy = new IntRange(range, crIndex); 424 425 if (crIndex == 0) { 426 // removing the first ClientRange, so we may need to increase 427 // the start id of the IntRange. 428 // We know there are at least two ClientRanges in the list, 429 // so clients.get(1) should always succeed. 430 int nextStartId = clients.get(1).startId; 431 if (nextStartId != range.startId) { 432 startUpdate(); 433 updateStarted = true; 434 addRange(range.startId, nextStartId - 1, false); 435 rangeCopy.startId = nextStartId; 436 } 437 // init largestEndId 438 largestEndId = clients.get(1).endId; 439 } 440 441 // go through remaining ClientRanges, creating new IntRanges when 442 // there is a gap in the sequence. After radio update succeeds, 443 // remove the original IntRange and append newRanges to mRanges. 444 // Otherwise, leave the original IntRange in mRanges and return false. 445 ArrayList<IntRange> newRanges = new ArrayList<IntRange>(); 446 447 IntRange currentRange = rangeCopy; 448 for (int nextIndex = crIndex + 1; nextIndex < crLength; nextIndex++) { 449 ClientRange nextCr = clients.get(nextIndex); 450 if (nextCr.startId > largestEndId + 1) { 451 if (!updateStarted) { 452 startUpdate(); 453 updateStarted = true; 454 } 455 addRange(largestEndId + 1, nextCr.startId - 1, false); 456 currentRange.endId = largestEndId; 457 newRanges.add(currentRange); 458 currentRange = new IntRange(nextCr); 459 } else { 460 currentRange.clients.add(nextCr); 461 } 462 if (nextCr.endId > largestEndId) { 463 largestEndId = nextCr.endId; 464 } 465 } 466 467 // remove any channels between largestEndId and endId 468 if (largestEndId < endId) { 469 if (!updateStarted) { 470 startUpdate(); 471 updateStarted = true; 472 } 473 addRange(largestEndId + 1, endId, false); 474 currentRange.endId = largestEndId; 475 } 476 newRanges.add(currentRange); 477 478 if (updateStarted && !finishUpdate()) { 479 return false; // failed to update radio 480 } 481 482 // replace the original IntRange with newRanges 483 mRanges.remove(i); 484 mRanges.addAll(i, newRanges); 485 return true; 486 } else { 487 // not the ClientRange to remove; save highest end ID seen so far 488 if (cr.endId > largestEndId) { 489 largestEndId = cr.endId; 490 } 491 } 492 } 493 } 494 } 495 496 return false; // not found 497 } 498 499 /** 500 * Perform a complete update operation (enable all ranges). Useful 501 * after a radio reset. Calls {@link #startUpdate}, followed by zero or 502 * more calls to {@link #addRange}, followed by {@link #finishUpdate}. 503 * @return true if successful, false otherwise 504 */ 505 public boolean updateRanges() { 506 startUpdate(); 507 Iterator<IntRange> iterator = mRanges.iterator(); 508 if (iterator.hasNext()) { 509 IntRange range = iterator.next(); 510 int start = range.startId; 511 int end = range.endId; 512 // accumulate ranges of [startId, endId] 513 while (iterator.hasNext()) { 514 IntRange nextNode = iterator.next(); 515 // [startIdA, endIdA], [endIdA + 1, endIdB] -> [startIdA, endIdB] 516 if (nextNode.startId <= (end + 1)) { 517 if (nextNode.endId > end) { 518 end = nextNode.endId; 519 } 520 } else { 521 addRange(start, end, true); 522 start = nextNode.startId; 523 end = nextNode.endId; 524 } 525 } 526 // add final range 527 addRange(start, end, true); 528 } 529 return finishUpdate(); 530 } 531 532 /** 533 * Enable or disable a single range of message identifiers. 534 * @param startId the first id included in the range 535 * @param endId the last id included in the range 536 * @param selected true to enable range, false to disable range 537 * @return true if successful, false otherwise 538 */ 539 private boolean tryAddSingleRange(int startId, int endId, boolean selected) { 540 startUpdate(); 541 addRange(startId, endId, selected); 542 return finishUpdate(); 543 } 544 545 /** 546 * Returns whether the list of ranges is completely empty. 547 * @return true if there are no enabled ranges 548 */ 549 public boolean isEmpty() { 550 return mRanges.isEmpty(); 551 } 552 553 /** 554 * Called when the list of enabled ranges has changed. This will be 555 * followed by zero or more calls to {@link #addRange} followed by 556 * a call to {@link #finishUpdate}. 557 */ 558 protected abstract void startUpdate(); 559 560 /** 561 * Called after {@link #startUpdate} to indicate a range of enabled 562 * or disabled values. 563 * 564 * @param startId the first id included in the range 565 * @param endId the last id included in the range 566 * @param selected true to enable range, false to disable range 567 */ 568 protected abstract void addRange(int startId, int endId, boolean selected); 569 570 /** 571 * Called to indicate the end of a range update started by the 572 * previous call to {@link #startUpdate}. 573 * @return true if successful, false otherwise 574 */ 575 protected abstract boolean finishUpdate(); 576} 577