1 /******************************************************************************* 2 * Copyright (c) 2015, 2016 Google, Inc and others. 3 * 4 * This program and the accompanying materials 5 * are made available under the terms of the Eclipse Public License 2.0 6 * which accompanies this distribution, and is available at 7 * https://www.eclipse.org/legal/epl-2.0/ 8 * 9 * SPDX-License-Identifier: EPL-2.0 10 * 11 * Contributors: 12 * Stefan Xenos (Google) - Initial implementation 13 *******************************************************************************/ 14 package org.eclipse.jdt.internal.core.nd.field; 15 16 import java.util.ArrayList; 17 import java.util.List; 18 19 import org.eclipse.jdt.internal.core.nd.ITypeFactory; 20 import org.eclipse.jdt.internal.core.nd.Nd; 21 import org.eclipse.jdt.internal.core.nd.NdNode; 22 import org.eclipse.jdt.internal.core.nd.db.BTree; 23 import org.eclipse.jdt.internal.core.nd.db.ModificationLog; 24 import org.eclipse.jdt.internal.core.nd.db.Database; 25 import org.eclipse.jdt.internal.core.nd.db.ModificationLog.Tag; 26 import org.eclipse.jdt.internal.core.nd.db.IBTreeComparator; 27 import org.eclipse.jdt.internal.core.nd.db.IBTreeVisitor; 28 import org.eclipse.jdt.internal.core.nd.db.IString; 29 import org.eclipse.jdt.internal.core.nd.db.IndexException; 30 31 /** 32 * Declares a field representing a case-insensitive search tree over elements which are a subtype of NdNode. 33 */ 34 public class FieldSearchIndex<T extends NdNode> extends BaseField implements IDestructableField { 35 private final ITypeFactory<BTree> btreeFactory; 36 FieldSearchKey<?> searchKey; 37 private final Tag destructTag; 38 private static IResultRank anything = new IResultRank() { 39 @Override 40 public long getRank(Nd nd, long address) { 41 return 1; 42 } 43 }; 44 45 public static final class SearchCriteria { 46 private boolean matchCase = true; 47 private boolean isPrefix = false; 48 private char[] searchString; 49 private short requiredNodeType = -1; 50 private boolean matchingParentNodeAddress = false; 51 SearchCriteria(char[] searchString)52 private SearchCriteria(char[] searchString) { 53 this.searchString = searchString; 54 } 55 create(String searchString)56 public static SearchCriteria create(String searchString) { 57 return create(searchString.toCharArray()); 58 } 59 create(char[] searchString)60 public static SearchCriteria create(char[] searchString) { 61 return new SearchCriteria(searchString); 62 } 63 requireNodeType(short type)64 public SearchCriteria requireNodeType(short type) { 65 this.requiredNodeType = type; 66 return this; 67 } 68 allowAnyNodeType()69 public SearchCriteria allowAnyNodeType() { 70 this.requiredNodeType = -1; 71 return this; 72 } 73 matchCase(boolean match)74 public SearchCriteria matchCase(boolean match) { 75 this.matchCase = match; 76 return this; 77 } 78 prefix(boolean isPrefixSearch)79 public SearchCriteria prefix(boolean isPrefixSearch) { 80 this.isPrefix = isPrefixSearch; 81 return this; 82 } 83 // 84 // public SearchCriteria requireParentNode(long parentNameAddress) { 85 // this.requiredParentNodeAddress = parentNameAddress; 86 // return this; 87 // } 88 isMatchingParentNodeAddress()89 public boolean isMatchingParentNodeAddress() { 90 return this.matchingParentNodeAddress; 91 } 92 isMatchingCase()93 public boolean isMatchingCase() { 94 return this.matchCase; 95 } 96 isPrefixSearch()97 public boolean isPrefixSearch() { 98 return this.isPrefix; 99 } 100 getSearchString()101 public char[] getSearchString() { 102 return this.searchString; 103 } 104 // 105 // public long getRequiredParentAddress() { 106 // return this.requiredParentNodeAddress; 107 // } 108 acceptsNodeType(short nodeType)109 public boolean acceptsNodeType(short nodeType) { 110 return this.requiredNodeType == -1 || this.requiredNodeType == nodeType; 111 } 112 requiresSpecificNodeType()113 public boolean requiresSpecificNodeType() { 114 return this.requiredNodeType != -1; 115 } 116 } 117 118 public static interface IResultRank { getRank(Nd nd, long address)119 public long getRank(Nd nd, long address); 120 } 121 122 private abstract class SearchCriteriaToBtreeVisitorAdapter implements IBTreeVisitor { 123 private final SearchCriteria searchCriteria; 124 private final Nd nd; 125 SearchCriteriaToBtreeVisitorAdapter(SearchCriteria searchCriteria, Nd nd)126 public SearchCriteriaToBtreeVisitorAdapter(SearchCriteria searchCriteria, Nd nd) { 127 this.searchCriteria = searchCriteria; 128 this.nd = nd; 129 } 130 131 @Override compare(long address)132 public int compare(long address) throws IndexException { 133 IString key = FieldSearchIndex.this.searchKey.get(this.nd, address); 134 135 if (this.searchCriteria.isPrefixSearch()) { 136 return key.comparePrefix(this.searchCriteria.getSearchString(), false); 137 } else { 138 return key.compareCompatibleWithIgnoreCase(this.searchCriteria.getSearchString()); 139 } 140 } 141 142 @Override visit(long address)143 public boolean visit(long address) throws IndexException { 144 if (this.searchCriteria.requiresSpecificNodeType()) { 145 short nodeType = NdNode.NODE_TYPE.get(this.nd, address); 146 147 if (!this.searchCriteria.acceptsNodeType(nodeType)) { 148 return true; 149 } 150 } 151 152 IString key = FieldSearchIndex.this.searchKey.get(this.nd, address); 153 154 if (this.searchCriteria.isMatchingCase()) { 155 if (this.searchCriteria.isPrefixSearch()) { 156 if (key.comparePrefix(this.searchCriteria.getSearchString(), true) != 0) { 157 return true; 158 } 159 } else { 160 if (key.compare(this.searchCriteria.getSearchString(), true) != 0) { 161 return true; 162 } 163 } 164 } 165 166 return acceptResult(address); 167 } 168 acceptResult(long address)169 protected abstract boolean acceptResult(long address); 170 } 171 FieldSearchIndex(FieldSearchKey<?> searchKey, String structName, int fieldNumber)172 private FieldSearchIndex(FieldSearchKey<?> searchKey, String structName, int fieldNumber) { 173 this.btreeFactory = BTree.getFactory(new IBTreeComparator() { 174 @Override 175 public int compare(Nd nd, long record1, long record2) { 176 IString key1 = FieldSearchIndex.this.searchKey.get(nd, record1); 177 IString key2 = FieldSearchIndex.this.searchKey.get(nd, record2); 178 179 int cmp = key1.compareCompatibleWithIgnoreCase(key2); 180 if (cmp == 0) { 181 cmp = Long.signum(record1 - record2); 182 } 183 184 return cmp; 185 } 186 }); 187 188 if (searchKey != null) { 189 if (searchKey.searchIndex != null && searchKey.searchIndex != this) { 190 throw new IllegalArgumentException( 191 "Attempted to construct a FieldSearchIndex referring to a search key that " //$NON-NLS-1$ 192 + "is already in use by a different index"); //$NON-NLS-1$ 193 } 194 searchKey.searchIndex = this; 195 } 196 this.searchKey = searchKey; 197 setFieldName("field " + fieldNumber + ", a " + getClass().getSimpleName() //$NON-NLS-1$//$NON-NLS-2$ 198 + " in struct " + structName); //$NON-NLS-1$ 199 this.destructTag = ModificationLog.createTag("Destructing " + getFieldName()); //$NON-NLS-1$ 200 } 201 create(StructDef<B> builder, final FieldSearchKey<B> searchKey)202 public static <T extends NdNode, B> FieldSearchIndex<T> create(StructDef<B> builder, 203 final FieldSearchKey<B> searchKey) { 204 205 FieldSearchIndex<T> result = new FieldSearchIndex<T>(searchKey, builder.getStructName(), builder.getNumFields()); 206 207 builder.add(result); 208 builder.addDestructableField(result); 209 210 return result; 211 } 212 get(Nd nd, long address)213 public BTree get(Nd nd, long address) { 214 return this.btreeFactory.create(nd, address + this.offset); 215 } 216 217 @Override destruct(Nd nd, long address)218 public void destruct(Nd nd, long address) { 219 Database db = nd.getDB(); 220 db.getLog().start(this.destructTag); 221 try { 222 this.btreeFactory.destruct(nd, address); 223 } finally { 224 db.getLog().end(this.destructTag); 225 } 226 } 227 228 @Override getRecordSize()229 public int getRecordSize() { 230 return this.btreeFactory.getRecordSize(); 231 } 232 findFirst(final Nd nd, long address, final SearchCriteria searchCriteria)233 public T findFirst(final Nd nd, long address, final SearchCriteria searchCriteria) { 234 return findBest(nd, address, searchCriteria, anything); 235 } 236 237 @SuppressWarnings("unchecked") findBest(final Nd nd, long address, final SearchCriteria searchCriteria, final IResultRank rankFunction)238 public T findBest(final Nd nd, long address, final SearchCriteria searchCriteria, final IResultRank rankFunction) { 239 final long[] resultRank = new long[1]; 240 final long[] result = new long[1]; 241 get(nd, address).accept(new SearchCriteriaToBtreeVisitorAdapter(searchCriteria, nd) { 242 @Override 243 protected boolean acceptResult(long resultAddress) { 244 long rank = rankFunction.getRank(nd, resultAddress); 245 if (rank >= resultRank[0]) { 246 resultRank[0] = rank; 247 result[0] = resultAddress; 248 } 249 return true; 250 } 251 }); 252 253 if (result[0] == 0) { 254 return null; 255 } 256 return (T)NdNode.load(nd, result[0]); 257 } 258 259 public interface Visitor<T> { visit(T toVisit)260 boolean visit(T toVisit); 261 } 262 visitAll(final Nd nd, long address, final SearchCriteria searchCriteria, final Visitor<T> visitor)263 public boolean visitAll(final Nd nd, long address, final SearchCriteria searchCriteria, final Visitor<T> visitor) { 264 return get(nd, address).accept(new SearchCriteriaToBtreeVisitorAdapter(searchCriteria, nd) { 265 @SuppressWarnings("unchecked") 266 @Override 267 protected boolean acceptResult(long resultAddress) { 268 return visitor.visit((T)NdNode.load(nd, resultAddress)); 269 } 270 }); 271 } 272 273 public List<T> findAll(final Nd nd, long address, final SearchCriteria searchCriteria) { 274 final List<T> result = new ArrayList<T>(); 275 get(nd, address).accept(new SearchCriteriaToBtreeVisitorAdapter(searchCriteria, nd) { 276 @SuppressWarnings("unchecked") 277 @Override 278 protected boolean acceptResult(long resultAddress) { 279 result.add((T)NdNode.load(nd, resultAddress)); 280 return true; 281 } 282 }); 283 284 return result; 285 } 286 287 public List<T> findAll(final Nd nd, long address, final SearchCriteria searchCriteria, final int count) { 288 final List<T> result = new ArrayList<T>(); 289 get(nd, address).accept(new SearchCriteriaToBtreeVisitorAdapter(searchCriteria, nd) { 290 291 int remainingCount = count; 292 293 @SuppressWarnings("unchecked") 294 @Override 295 protected boolean acceptResult(long resultAddress) { 296 result.add((T) NdNode.load(nd, resultAddress)); 297 this.remainingCount--; 298 return this.remainingCount > 0; 299 } 300 }); 301 return result; 302 } 303 304 /** 305 * Returns the entire contents of the index as a single list. 306 */ 307 public List<T> asList(final Nd nd, long address) { 308 final List<T> result = new ArrayList<T>(); 309 get(nd, address).accept(new IBTreeVisitor() { 310 @Override 311 public int compare(long record) { 312 return 0; 313 } 314 315 @SuppressWarnings("unchecked") 316 @Override 317 public boolean visit(long resultAddress) { 318 result.add((T)NdNode.load(nd, resultAddress)); 319 return true; 320 } 321 }); 322 323 return result; 324 } 325 } 326