1 /*
2  * Copyright (C) 2017 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.ahat.heapdump;
18 
19 import java.util.Comparator;
20 import java.util.Iterator;
21 import java.util.List;
22 
23 /**
24  * A collection of instances that can be searched for by id.
25  */
26 class Instances<T extends AhatInstance> implements Iterable<T> {
27 
28   private final List<T> mInstances;
29 
30   /**
31    * Create a collection of instances that can be looked up by id.
32    * Note: this takes ownership of the given list of instances.
33    */
Instances(List<T> instances)34   public Instances(List<T> instances) {
35     mInstances = instances;
36 
37     // Sort the instances by id so we can use binary search to lookup
38     // instances by id.
39     instances.sort(new Comparator<AhatInstance>() {
40       @Override
41       public int compare(AhatInstance a, AhatInstance b) {
42         return Long.compare(a.getId(), b.getId());
43       }
44     });
45   }
46 
47   /**
48    * Look up an instance by id.
49    * Returns null if no instance with the given id is found.
50    */
get(long id)51   public T get(long id) {
52     // Binary search over the sorted instances.
53     int start = 0;
54     int end = mInstances.size();
55     while (start < end) {
56       int mid = start + ((end - start) / 2);
57       T midInst = mInstances.get(mid);
58       long midId = midInst.getId();
59       if (id == midId) {
60         return midInst;
61       } else if (id < midId) {
62         end = mid;
63       } else {
64         start = mid + 1;
65       }
66     }
67     return null;
68   }
69 
70   @Override
iterator()71   public Iterator<T> iterator() {
72     return mInstances.iterator();
73   }
74 }
75 
76