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 import java.util.function.Predicate;
23 
24 /**
25  * A collection of instances that can be searched for by id.
26  */
27 class Instances<T extends AhatInstance> implements Iterable<T> {
28 
29   private final List<T> mInstances;
30 
31   /**
32    * Create a collection of instances that can be looked up by id.
33    * Note: this takes ownership of the given list of instances.
34    */
Instances(List<T> instances)35   public Instances(List<T> instances) {
36     mInstances = instances;
37 
38     // Sort the instances by id so we can use binary search to lookup
39     // instances by id.
40     instances.sort(new Comparator<AhatInstance>() {
41       @Override
42       public int compare(AhatInstance a, AhatInstance b) {
43         return Long.compare(a.getId(), b.getId());
44       }
45     });
46 
47     // Ensure there is a one-to-one mapping between ids and instances by
48     // removing instances that have the same id as a previous instance. The
49     // heap dump really ought not to include multiple instances with the same
50     // id, but this happens on some older versions of ART and in some versions
51     // of the RI.
52     Predicate<T> isDuplicate = new Predicate<T>() {
53       private long previous = -1;
54 
55       @Override
56       public boolean test(T x) {
57         if (x.getId() == previous) {
58           return true;
59         }
60         previous = x.getId();
61         return false;
62       }
63     };
64     mInstances.removeIf(isDuplicate);
65   }
66 
67   /**
68    * Look up an instance by id.
69    * Returns null if no instance with the given id is found.
70    */
get(long id)71   public T get(long id) {
72     // Binary search over the sorted instances.
73     int start = 0;
74     int end = mInstances.size();
75     while (start < end) {
76       int mid = start + ((end - start) / 2);
77       T midInst = mInstances.get(mid);
78       long midId = midInst.getId();
79       if (id == midId) {
80         return midInst;
81       } else if (id < midId) {
82         end = mid;
83       } else {
84         start = mid + 1;
85       }
86     }
87     return null;
88   }
89 
removeIf(Predicate<T> predicate)90   public void removeIf(Predicate<T> predicate) {
91     mInstances.removeIf(predicate);
92   }
93 
size()94   public int size() {
95     return mInstances.size();
96   }
97 
98   @Override
iterator()99   public Iterator<T> iterator() {
100     return mInstances.iterator();
101   }
102 }
103 
104