| /* |
| * Copyright (C) 2011 The Android Open Source Project |
| * |
| * Licensed under the Apache License, Version 2.0 (the "License"); |
| * you may not use this file except in compliance with the License. |
| * You may obtain a copy of the License at |
| * |
| * http://www.apache.org/licenses/LICENSE-2.0 |
| * |
| * Unless required by applicable law or agreed to in writing, software |
| * distributed under the License is distributed on an "AS IS" BASIS, |
| * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied. |
| * See the License for the specific language governing permissions and |
| * limitations under the License. |
| */ |
| |
| package com.android.internal.telephony; |
| |
| import java.util.ArrayList; |
| import java.util.Iterator; |
| |
| /** |
| * Clients can enable reception of SMS-CB messages for specific ranges of |
| * message identifiers (channels). This class keeps track of the currently |
| * enabled message identifiers and calls abstract methods to update the |
| * radio when the range of enabled message identifiers changes. |
| * |
| * An update is a call to {@link #startUpdate} followed by zero or more |
| * calls to {@link #addRange} followed by a call to {@link #finishUpdate}. |
| * Calls to {@link #enableRange} and {@link #disableRange} will perform |
| * an incremental update operation if the enabled ranges have changed. |
| * A full update operation (i.e. after a radio reset) can be performed |
| * by a call to {@link #updateRanges}. |
| * |
| * Clients are identified by String (the name associated with the User ID |
| * of the caller) so that a call to remove a range can be mapped to the |
| * client that enabled that range (or else rejected). |
| */ |
| public abstract class IntRangeManager { |
| |
| /** |
| * Initial capacity for IntRange clients array list. There will be |
| * few cell broadcast listeners on a typical device, so this can be small. |
| */ |
| private static final int INITIAL_CLIENTS_ARRAY_SIZE = 4; |
| |
| /** |
| * One or more clients forming the continuous range [startId, endId]. |
| * <p>When a client is added, the IntRange may merge with one or more |
| * adjacent IntRanges to form a single combined IntRange. |
| * <p>When a client is removed, the IntRange may divide into several |
| * non-contiguous IntRanges. |
| */ |
| private class IntRange { |
| int mStartId; |
| int mEndId; |
| // sorted by earliest start id |
| final ArrayList<ClientRange> mClients; |
| |
| /** |
| * Create a new IntRange with a single client. |
| * @param startId the first id included in the range |
| * @param endId the last id included in the range |
| * @param client the client requesting the enabled range |
| */ |
| IntRange(int startId, int endId, String client) { |
| mStartId = startId; |
| mEndId = endId; |
| mClients = new ArrayList<ClientRange>(INITIAL_CLIENTS_ARRAY_SIZE); |
| mClients.add(new ClientRange(startId, endId, client)); |
| } |
| |
| /** |
| * Create a new IntRange for an existing ClientRange. |
| * @param clientRange the initial ClientRange to add |
| */ |
| IntRange(ClientRange clientRange) { |
| mStartId = clientRange.mStartId; |
| mEndId = clientRange.mEndId; |
| mClients = new ArrayList<ClientRange>(INITIAL_CLIENTS_ARRAY_SIZE); |
| mClients.add(clientRange); |
| } |
| |
| /** |
| * Create a new IntRange from an existing IntRange. This is used for |
| * removing a ClientRange, because new IntRanges may need to be created |
| * for any gaps that open up after the ClientRange is removed. A copy |
| * is made of the elements of the original IntRange preceding the element |
| * that is being removed. The following elements will be added to this |
| * IntRange or to a new IntRange when a gap is found. |
| * @param intRange the original IntRange to copy elements from |
| * @param numElements the number of elements to copy from the original |
| */ |
| IntRange(IntRange intRange, int numElements) { |
| mStartId = intRange.mStartId; |
| mEndId = intRange.mEndId; |
| mClients = new ArrayList<ClientRange>(intRange.mClients.size()); |
| for (int i=0; i < numElements; i++) { |
| mClients.add(intRange.mClients.get(i)); |
| } |
| } |
| |
| /** |
| * Insert new ClientRange in order by start id, then by end id |
| * <p>If the new ClientRange is known to be sorted before or after the |
| * existing ClientRanges, or at a particular index, it can be added |
| * to the clients array list directly, instead of via this method. |
| * <p>Note that this can be changed from linear to binary search if the |
| * number of clients grows large enough that it would make a difference. |
| * @param range the new ClientRange to insert |
| */ |
| void insert(ClientRange range) { |
| int len = mClients.size(); |
| int insert = -1; |
| for (int i=0; i < len; i++) { |
| ClientRange nextRange = mClients.get(i); |
| if (range.mStartId <= nextRange.mStartId) { |
| // ignore duplicate ranges from the same client |
| if (!range.equals(nextRange)) { |
| // check if same startId, then order by endId |
| if (range.mStartId == nextRange.mStartId |
| && range.mEndId > nextRange.mEndId) { |
| insert = i + 1; |
| if (insert < len) { |
| // there may be more client following with same startId |
| // new [1, 5] existing [1, 2] [1, 4] [1, 7] |
| continue; |
| } |
| break; |
| } |
| mClients.add(i, range); |
| } |
| return; |
| } |
| } |
| if (insert != -1 && insert < len) { |
| mClients.add(insert, range); |
| return; |
| } |
| mClients.add(range); // append to end of list |
| } |
| } |
| |
| /** |
| * The message id range for a single client. |
| */ |
| private class ClientRange { |
| final int mStartId; |
| final int mEndId; |
| final String mClient; |
| |
| ClientRange(int startId, int endId, String client) { |
| mStartId = startId; |
| mEndId = endId; |
| mClient = client; |
| } |
| |
| @Override |
| public boolean equals(Object o) { |
| if (o != null && o instanceof ClientRange) { |
| ClientRange other = (ClientRange) o; |
| return mStartId == other.mStartId && |
| mEndId == other.mEndId && |
| mClient.equals(other.mClient); |
| } else { |
| return false; |
| } |
| } |
| |
| @Override |
| public int hashCode() { |
| return (mStartId * 31 + mEndId) * 31 + mClient.hashCode(); |
| } |
| } |
| |
| /** |
| * List of integer ranges, one per client, sorted by start id. |
| */ |
| private ArrayList<IntRange> mRanges = new ArrayList<IntRange>(); |
| |
| protected IntRangeManager() {} |
| |
| /** |
| * Enable a range for the specified client and update ranges |
| * if necessary. If {@link #finishUpdate} returns failure, |
| * false is returned and the range is not added. |
| * |
| * @param startId the first id included in the range |
| * @param endId the last id included in the range |
| * @param client the client requesting the enabled range |
| * @return true if successful, false otherwise |
| */ |
| public synchronized boolean enableRange(int startId, int endId, String client) { |
| int len = mRanges.size(); |
| |
| // empty range list: add the initial IntRange |
| if (len == 0) { |
| if (tryAddRanges(startId, endId, true)) { |
| mRanges.add(new IntRange(startId, endId, client)); |
| return true; |
| } else { |
| return false; // failed to update radio |
| } |
| } |
| |
| for (int startIndex = 0; startIndex < len; startIndex++) { |
| IntRange range = mRanges.get(startIndex); |
| if ((startId) >= range.mStartId && (endId) <= range.mEndId) { |
| // exact same range: new [1, 1] existing [1, 1] |
| // range already enclosed in existing: new [3, 3], [1,3] |
| // no radio update necessary. |
| // duplicate "client" check is done in insert, attempt to insert. |
| range.insert(new ClientRange(startId, endId, client)); |
| return true; |
| } else if ((startId - 1) == range.mEndId) { |
| // new [3, x] existing [1, 2] OR new [2, 2] existing [1, 1] |
| // found missing link? check if next range can be joined |
| int newRangeEndId = endId; |
| IntRange nextRange = null; |
| if ((startIndex + 1) < len) { |
| nextRange = mRanges.get(startIndex + 1); |
| if ((nextRange.mStartId - 1) <= endId) { |
| // new [3, x] existing [1, 2] [5, 7] OR new [2 , 2] existing [1, 1] [3, 5] |
| if (endId <= nextRange.mEndId) { |
| // new [3, 6] existing [1, 2] [5, 7] |
| newRangeEndId = nextRange.mStartId - 1; // need to enable [3, 4] |
| } |
| } else { |
| // mark nextRange to be joined as null. |
| nextRange = null; |
| } |
| } |
| if (tryAddRanges(startId, newRangeEndId, true)) { |
| range.mEndId = endId; |
| range.insert(new ClientRange(startId, endId, client)); |
| |
| // found missing link? check if next range can be joined |
| if (nextRange != null) { |
| if (range.mEndId < nextRange.mEndId) { |
| // new [3, 6] existing [1, 2] [5, 10] |
| range.mEndId = nextRange.mEndId; |
| } |
| range.mClients.addAll(nextRange.mClients); |
| mRanges.remove(nextRange); |
| } |
| return true; |
| } else { |
| return false; // failed to update radio |
| } |
| } else if (startId < range.mStartId) { |
| // new [1, x] , existing [5, y] |
| // test if new range completely precedes this range |
| // note that [1, 4] and [5, 6] coalesce to [1, 6] |
| if ((endId + 1) < range.mStartId) { |
| // new [1, 3] existing [5, 6] non contiguous case |
| // insert new int range before previous first range |
| if (tryAddRanges(startId, endId, true)) { |
| mRanges.add(startIndex, new IntRange(startId, endId, client)); |
| return true; |
| } else { |
| return false; // failed to update radio |
| } |
| } else if (endId <= range.mEndId) { |
| // new [1, 4] existing [5, 6] or new [1, 1] existing [2, 2] |
| // extend the start of this range |
| if (tryAddRanges(startId, range.mStartId - 1, true)) { |
| range.mStartId = startId; |
| range.mClients.add(0, new ClientRange(startId, endId, client)); |
| return true; |
| } else { |
| return false; // failed to update radio |
| } |
| } else { |
| // find last range that can coalesce into the new combined range |
| for (int endIndex = startIndex+1; endIndex < len; endIndex++) { |
| IntRange endRange = mRanges.get(endIndex); |
| if ((endId + 1) < endRange.mStartId) { |
| // new [1, 10] existing [2, 3] [14, 15] |
| // try to add entire new range |
| if (tryAddRanges(startId, endId, true)) { |
| range.mStartId = startId; |
| range.mEndId = endId; |
| // insert new ClientRange before existing ranges |
| range.mClients.add(0, new ClientRange(startId, endId, client)); |
| // coalesce range with following ranges up to endIndex-1 |
| // remove each range after adding its elements, so the index |
| // of the next range to join is always startIndex+1. |
| // i is the index if no elements were removed: we only care |
| // about the number of loop iterations, not the value of i. |
| int joinIndex = startIndex + 1; |
| for (int i = joinIndex; i < endIndex; i++) { |
| // new [1, 10] existing [2, 3] [5, 6] [14, 15] |
| IntRange joinRange = mRanges.get(joinIndex); |
| range.mClients.addAll(joinRange.mClients); |
| mRanges.remove(joinRange); |
| } |
| return true; |
| } else { |
| return false; // failed to update radio |
| } |
| } else if (endId <= endRange.mEndId) { |
| // new [1, 10] existing [2, 3] [5, 15] |
| // add range from start id to start of last overlapping range, |
| // values from endRange.startId to endId are already enabled |
| if (tryAddRanges(startId, endRange.mStartId - 1, true)) { |
| range.mStartId = startId; |
| range.mEndId = endRange.mEndId; |
| // insert new ClientRange before existing ranges |
| range.mClients.add(0, new ClientRange(startId, endId, client)); |
| // coalesce range with following ranges up to endIndex |
| // remove each range after adding its elements, so the index |
| // of the next range to join is always startIndex+1. |
| // i is the index if no elements were removed: we only care |
| // about the number of loop iterations, not the value of i. |
| int joinIndex = startIndex + 1; |
| for (int i = joinIndex; i <= endIndex; i++) { |
| IntRange joinRange = mRanges.get(joinIndex); |
| range.mClients.addAll(joinRange.mClients); |
| mRanges.remove(joinRange); |
| } |
| return true; |
| } else { |
| return false; // failed to update radio |
| } |
| } |
| } |
| |
| // new [1, 10] existing [2, 3] |
| // endId extends past all existing IntRanges: combine them all together |
| if (tryAddRanges(startId, endId, true)) { |
| range.mStartId = startId; |
| range.mEndId = endId; |
| // insert new ClientRange before existing ranges |
| range.mClients.add(0, new ClientRange(startId, endId, client)); |
| // coalesce range with following ranges up to len-1 |
| // remove each range after adding its elements, so the index |
| // of the next range to join is always startIndex+1. |
| // i is the index if no elements were removed: we only care |
| // about the number of loop iterations, not the value of i. |
| int joinIndex = startIndex + 1; |
| for (int i = joinIndex; i < len; i++) { |
| // new [1, 10] existing [2, 3] [5, 6] |
| IntRange joinRange = mRanges.get(joinIndex); |
| range.mClients.addAll(joinRange.mClients); |
| mRanges.remove(joinRange); |
| } |
| return true; |
| } else { |
| return false; // failed to update radio |
| } |
| } |
| } else if ((startId + 1) <= range.mEndId) { |
| // new [2, x] existing [1, 4] |
| if (endId <= range.mEndId) { |
| // new [2, 3] existing [1, 4] |
| // completely contained in existing range; no radio changes |
| range.insert(new ClientRange(startId, endId, client)); |
| return true; |
| } else { |
| // new [2, 5] existing [1, 4] |
| // find last range that can coalesce into the new combined range |
| int endIndex = startIndex; |
| for (int testIndex = startIndex+1; testIndex < len; testIndex++) { |
| IntRange testRange = mRanges.get(testIndex); |
| if ((endId + 1) < testRange.mStartId) { |
| break; |
| } else { |
| endIndex = testIndex; |
| } |
| } |
| // no adjacent IntRanges to combine |
| if (endIndex == startIndex) { |
| // new [2, 5] existing [1, 4] |
| // add range from range.endId+1 to endId, |
| // values from startId to range.endId are already enabled |
| if (tryAddRanges(range.mEndId + 1, endId, true)) { |
| range.mEndId = endId; |
| range.insert(new ClientRange(startId, endId, client)); |
| return true; |
| } else { |
| return false; // failed to update radio |
| } |
| } |
| // get last range to coalesce into start range |
| IntRange endRange = mRanges.get(endIndex); |
| // Values from startId to range.endId have already been enabled. |
| // if endId > endRange.endId, then enable range from range.endId+1 to endId, |
| // else enable range from range.endId+1 to endRange.startId-1, because |
| // values from endRange.startId to endId have already been added. |
| int newRangeEndId = (endId <= endRange.mEndId) ? endRange.mStartId - 1 : endId; |
| // new [2, 10] existing [1, 4] [7, 8] OR |
| // new [2, 10] existing [1, 4] [7, 15] |
| if (tryAddRanges(range.mEndId + 1, newRangeEndId, true)) { |
| newRangeEndId = (endId <= endRange.mEndId) ? endRange.mEndId : endId; |
| range.mEndId = newRangeEndId; |
| // insert new ClientRange in place |
| range.insert(new ClientRange(startId, endId, client)); |
| // coalesce range with following ranges up to endIndex |
| // remove each range after adding its elements, so the index |
| // of the next range to join is always startIndex+1 (joinIndex). |
| // i is the index if no elements had been removed: we only care |
| // about the number of loop iterations, not the value of i. |
| int joinIndex = startIndex + 1; |
| for (int i = joinIndex; i <= endIndex; i++) { |
| IntRange joinRange = mRanges.get(joinIndex); |
| range.mClients.addAll(joinRange.mClients); |
| mRanges.remove(joinRange); |
| } |
| return true; |
| } else { |
| return false; // failed to update radio |
| } |
| } |
| } |
| } |
| |
| // new [5, 6], existing [1, 3] |
| // append new range after existing IntRanges |
| if (tryAddRanges(startId, endId, true)) { |
| mRanges.add(new IntRange(startId, endId, client)); |
| return true; |
| } else { |
| return false; // failed to update radio |
| } |
| } |
| |
| /** |
| * Disable a range for the specified client and update ranges |
| * if necessary. If {@link #finishUpdate} returns failure, |
| * false is returned and the range is not removed. |
| * |
| * @param startId the first id included in the range |
| * @param endId the last id included in the range |
| * @param client the client requesting to disable the range |
| * @return true if successful, false otherwise |
| */ |
| public synchronized boolean disableRange(int startId, int endId, String client) { |
| int len = mRanges.size(); |
| |
| for (int i=0; i < len; i++) { |
| IntRange range = mRanges.get(i); |
| if (startId < range.mStartId) { |
| return false; // not found |
| } else if (endId <= range.mEndId) { |
| // found the IntRange that encloses the client range, if any |
| // search for it in the clients list |
| ArrayList<ClientRange> clients = range.mClients; |
| |
| // handle common case of IntRange containing one ClientRange |
| int crLength = clients.size(); |
| if (crLength == 1) { |
| ClientRange cr = clients.get(0); |
| if (cr.mStartId == startId && cr.mEndId == endId && cr.mClient.equals(client)) { |
| // mRange contains only what's enabled. |
| // remove the range from mRange then update the radio |
| mRanges.remove(i); |
| if (updateRanges()) { |
| return true; |
| } else { |
| // failed to update radio. insert back the range |
| mRanges.add(i, range); |
| return false; |
| } |
| } else { |
| return false; // not found |
| } |
| } |
| |
| // several ClientRanges: remove one, potentially splitting into many IntRanges. |
| // Save the original start and end id for the original IntRange |
| // in case the radio update fails and we have to revert it. If the |
| // update succeeds, we remove the client range and insert the new IntRanges. |
| // clients are ordered by startId then by endId, so client with largest endId |
| // can be anywhere. Need to loop thru to find largestEndId. |
| int largestEndId = Integer.MIN_VALUE; // largest end identifier found |
| boolean updateStarted = false; |
| |
| // crlength >= 2 |
| for (int crIndex=0; crIndex < crLength; crIndex++) { |
| ClientRange cr = clients.get(crIndex); |
| if (cr.mStartId == startId && cr.mEndId == endId && cr.mClient.equals(client)) { |
| // found the ClientRange to remove, check if it's the last in the list |
| if (crIndex == crLength - 1) { |
| if (range.mEndId == largestEndId) { |
| // remove [2, 5] from [1, 7] [2, 5] |
| // no channels to remove from radio; return success |
| clients.remove(crIndex); |
| return true; |
| } else { |
| // disable the channels at the end and lower the end id |
| clients.remove(crIndex); |
| range.mEndId = largestEndId; |
| if (updateRanges()) { |
| return true; |
| } else { |
| clients.add(crIndex, cr); |
| range.mEndId = cr.mEndId; |
| return false; |
| } |
| } |
| } |
| |
| // copy the IntRange so that we can remove elements and modify the |
| // start and end id's in the copy, leaving the original unmodified |
| // until after the radio update succeeds |
| IntRange rangeCopy = new IntRange(range, crIndex); |
| |
| if (crIndex == 0) { |
| // removing the first ClientRange, so we may need to increase |
| // the start id of the IntRange. |
| // We know there are at least two ClientRanges in the list, |
| // because check for just one ClientRanges case is already handled |
| // so clients.get(1) should always succeed. |
| int nextStartId = clients.get(1).mStartId; |
| if (nextStartId != range.mStartId) { |
| updateStarted = true; |
| rangeCopy.mStartId = nextStartId; |
| } |
| // init largestEndId |
| largestEndId = clients.get(1).mEndId; |
| } |
| |
| // go through remaining ClientRanges, creating new IntRanges when |
| // there is a gap in the sequence. After radio update succeeds, |
| // remove the original IntRange and append newRanges to mRanges. |
| // Otherwise, leave the original IntRange in mRanges and return false. |
| ArrayList<IntRange> newRanges = new ArrayList<IntRange>(); |
| |
| IntRange currentRange = rangeCopy; |
| for (int nextIndex = crIndex + 1; nextIndex < crLength; nextIndex++) { |
| ClientRange nextCr = clients.get(nextIndex); |
| if (nextCr.mStartId > largestEndId + 1) { |
| updateStarted = true; |
| currentRange.mEndId = largestEndId; |
| newRanges.add(currentRange); |
| currentRange = new IntRange(nextCr); |
| } else { |
| if (currentRange.mEndId < nextCr.mEndId) { |
| currentRange.mEndId = nextCr.mEndId; |
| } |
| currentRange.mClients.add(nextCr); |
| } |
| if (nextCr.mEndId > largestEndId) { |
| largestEndId = nextCr.mEndId; |
| } |
| } |
| |
| // remove any channels between largestEndId and endId |
| if (largestEndId < endId) { |
| updateStarted = true; |
| currentRange.mEndId = largestEndId; |
| } |
| newRanges.add(currentRange); |
| |
| // replace the original IntRange with newRanges |
| mRanges.remove(i); |
| mRanges.addAll(i, newRanges); |
| if (updateStarted && !updateRanges()) { |
| // failed to update radio. revert back mRange. |
| mRanges.removeAll(newRanges); |
| mRanges.add(i, range); |
| return false; |
| } |
| |
| return true; |
| } else { |
| // not the ClientRange to remove; save highest end ID seen so far |
| if (cr.mEndId > largestEndId) { |
| largestEndId = cr.mEndId; |
| } |
| } |
| } |
| } |
| } |
| |
| return false; // not found |
| } |
| |
| /** |
| * Perform a complete update operation (enable all ranges). Useful |
| * after a radio reset. Calls {@link #startUpdate}, followed by zero or |
| * more calls to {@link #addRange}, followed by {@link #finishUpdate}. |
| * @return true if successful, false otherwise |
| */ |
| public boolean updateRanges() { |
| startUpdate(); |
| |
| populateAllRanges(); |
| return finishUpdate(); |
| } |
| |
| /** |
| * Enable or disable a single range of message identifiers. |
| * @param startId the first id included in the range |
| * @param endId the last id included in the range |
| * @param selected true to enable range, false to disable range |
| * @return true if successful, false otherwise |
| */ |
| protected boolean tryAddRanges(int startId, int endId, boolean selected) { |
| |
| startUpdate(); |
| populateAllRanges(); |
| // This is the new range to be enabled |
| addRange(startId, endId, selected); // adds to mConfigList |
| return finishUpdate(); |
| } |
| |
| /** |
| * Returns whether the list of ranges is completely empty. |
| * @return true if there are no enabled ranges |
| */ |
| public boolean isEmpty() { |
| return mRanges.isEmpty(); |
| } |
| |
| /** |
| * Called when attempting to add a single range of message identifiers |
| * Populate all ranges of message identifiers. |
| */ |
| private void populateAllRanges() { |
| Iterator<IntRange> itr = mRanges.iterator(); |
| // Populate all ranges from mRanges |
| while (itr.hasNext()) { |
| IntRange currRange = (IntRange) itr.next(); |
| addRange(currRange.mStartId, currRange.mEndId, true); |
| } |
| } |
| |
| /** |
| * Called when attempting to add a single range of message identifiers |
| * Populate all ranges of message identifiers using clients' ranges. |
| */ |
| private void populateAllClientRanges() { |
| int len = mRanges.size(); |
| for (int i = 0; i < len; i++) { |
| IntRange range = mRanges.get(i); |
| |
| int clientLen = range.mClients.size(); |
| for (int j=0; j < clientLen; j++) { |
| ClientRange nextRange = range.mClients.get(j); |
| addRange(nextRange.mStartId, nextRange.mEndId, true); |
| } |
| } |
| } |
| |
| /** |
| * Called when the list of enabled ranges has changed. This will be |
| * followed by zero or more calls to {@link #addRange} followed by |
| * a call to {@link #finishUpdate}. |
| */ |
| protected abstract void startUpdate(); |
| |
| /** |
| * Called after {@link #startUpdate} to indicate a range of enabled |
| * or disabled values. |
| * |
| * @param startId the first id included in the range |
| * @param endId the last id included in the range |
| * @param selected true to enable range, false to disable range |
| */ |
| protected abstract void addRange(int startId, int endId, boolean selected); |
| |
| /** |
| * Called to indicate the end of a range update started by the |
| * previous call to {@link #startUpdate}. |
| * @return true if successful, false otherwise |
| */ |
| protected abstract boolean finishUpdate(); |
| } |
