1 /* 2 * Copyright (C) 2007 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.dexgen.util; 18 19 import com.android.dexgen.rop.ByteBlock; 20 21 /** 22 * A list of labeled items, allowing easy lookup by label. 23 */ 24 public class LabeledList extends FixedSizeList { 25 26 /** 27 * Sparse array indexed by label to FixedSizeList index. 28 * -1 = invalid label. 29 */ 30 private final IntList labelToIndex; 31 32 /** @inheritDoc */ LabeledList(int size)33 public LabeledList(int size) { 34 super(size); 35 36 labelToIndex = new IntList(size); 37 } 38 39 /** 40 * Constructs a new instance that is a copy of the old instance. 41 * 42 * @param old instance to copy 43 */ LabeledList(LabeledList old)44 protected LabeledList(LabeledList old) { 45 super(old.size()); 46 labelToIndex = old.labelToIndex.mutableCopy(); 47 48 int sz = old.size(); 49 50 for (int i = 0; i < sz; i++) { 51 Object one = old.get0(i); 52 if (one != null) { 53 set0(i, one); 54 } 55 } 56 } 57 58 /** 59 * Gets the maximum label (exclusive) of any block added to this instance. 60 * 61 * @return {@code >= 0;} the maximum label 62 */ getMaxLabel()63 public int getMaxLabel() { 64 int sz = labelToIndex.size(); 65 66 // Gobble any deleted labels that may be at the end... 67 int i; 68 for (i = sz - 1; (i >= 0) && (labelToIndex.get(i) < 0); i--) 69 ; 70 71 int newSize = i+1; 72 73 labelToIndex.shrink(newSize); 74 75 return newSize; 76 } 77 78 /** 79 * Removes a label from the label-to-index mapping 80 * @param oldLabel label to remove 81 */ removeLabel(int oldLabel)82 protected void removeLabel(int oldLabel) { 83 labelToIndex.set(oldLabel, -1); 84 } 85 86 /** 87 * Adds a label and index to the label-to-index mapping 88 * @param label new label 89 * @param index index of block. 90 */ addLabelIndex(int label, int index)91 protected void addLabelIndex(int label, int index) { 92 int origSz = labelToIndex.size(); 93 94 for (int i = 0; i <= (label - origSz); i++) { 95 labelToIndex.add(-1); 96 } 97 98 labelToIndex.set(label, index); 99 } 100 101 /** 102 * Gets the index of the first item in the list with the given 103 * label, if any. 104 * 105 * @param label {@code >= 0;} the label to look for 106 * @return {@code >= -1;} the index of the so-labelled item, or {@code -1} 107 * if none is found 108 */ indexOfLabel(int label)109 public int indexOfLabel(int label) { 110 if (label >= labelToIndex.size()) { 111 return -1; 112 } else { 113 return labelToIndex.get(label); 114 } 115 } 116 117 /** @inheritDoc */ 118 @Override shrinkToFit()119 public void shrinkToFit() { 120 super.shrinkToFit(); 121 122 rebuildLabelToIndex(); 123 } 124 125 /** 126 * Rebuilds the label-to-index mapping after a shrinkToFit(). 127 * Note: assumes that the labels that are in the list are the same 128 * although the indicies may have changed. 129 */ rebuildLabelToIndex()130 protected void rebuildLabelToIndex() { 131 int szItems = size(); 132 133 for (int i = 0; i < szItems; i++) { 134 LabeledItem li = (LabeledItem)get0(i); 135 136 if (li != null) { 137 labelToIndex.set(li.getLabel(), i); 138 } 139 } 140 } 141 142 /** 143 * Sets the element at the given index. 144 * 145 * @param n {@code >= 0, < size();} which element 146 * @param item {@code null-ok;} the value to store 147 */ set(int n, LabeledItem item)148 protected void set(int n, LabeledItem item) { 149 LabeledItem old = (LabeledItem) getOrNull0(n); 150 151 set0(n, item); 152 153 if (old != null) { 154 removeLabel(old.getLabel()); 155 } 156 157 if (item != null) { 158 addLabelIndex(item.getLabel(), n); 159 } 160 } 161 } 162