001 /* 002 * CDDL HEADER START 003 * 004 * The contents of this file are subject to the terms of the 005 * Common Development and Distribution License, Version 1.0 only 006 * (the "License"). You may not use this file except in compliance 007 * with the License. 008 * 009 * You can obtain a copy of the license at 010 * trunk/opends/resource/legal-notices/OpenDS.LICENSE 011 * or https://OpenDS.dev.java.net/OpenDS.LICENSE. 012 * See the License for the specific language governing permissions 013 * and limitations under the License. 014 * 015 * When distributing Covered Code, include this CDDL HEADER in each 016 * file and include the License file at 017 * trunk/opends/resource/legal-notices/OpenDS.LICENSE. If applicable, 018 * add the following below this CDDL HEADER, with the fields enclosed 019 * by brackets "[]" replaced with your own identifying information: 020 * Portions Copyright [yyyy] [name of copyright owner] 021 * 022 * CDDL HEADER END 023 * 024 * 025 * Copyright 2006-2008 Sun Microsystems, Inc. 026 */ 027 package org.opends.server.backends.jeb; 028 029 import static org.opends.server.loggers.debug.DebugLogger.*; 030 import org.opends.server.loggers.debug.DebugTracer; 031 import org.opends.server.types.*; 032 033 import java.util.*; 034 035 /** 036 * An implementation of an Indexer for attribute substrings. 037 */ 038 public class SubstringIndexer extends Indexer 039 { 040 /** 041 * The tracer object for the debug logger. 042 */ 043 private static final DebugTracer TRACER = getTracer(); 044 045 046 047 /** 048 * The comparator for index keys generated by this class. 049 */ 050 private static final Comparator<byte[]> comparator = 051 new AttributeIndex.KeyComparator(); 052 053 /** 054 * The attribute type for which this instance will 055 * generate index keys. 056 */ 057 private AttributeType attributeType; 058 059 /** 060 * The substring length. 061 */ 062 private int substrLength; 063 064 /** 065 * Create a new attribute substring indexer for the given index configuration. 066 * @param attributeType The attribute type for which an indexer is 067 * required. 068 * @param substringLength The decomposed substring length. 069 */ 070 public SubstringIndexer(AttributeType attributeType, int substringLength) 071 { 072 this.attributeType = attributeType; 073 this.substrLength = substringLength; 074 } 075 076 /** 077 * Get a string representation of this object. The returned value is 078 * used to name an index created using this object. 079 * @return A string representation of this object. 080 */ 081 public String toString() 082 { 083 return attributeType.getNameOrOID() + ".substring"; 084 } 085 086 /** 087 * Get the comparator that must be used to compare index keys 088 * generated by this class. 089 * 090 * @return A byte array comparator. 091 */ 092 public Comparator<byte[]> getComparator() 093 { 094 return comparator; 095 } 096 097 /** 098 * Generate the set of index keys for an entry. 099 * 100 * @param entry The entry. 101 * @param keys The set into which the generated keys will be inserted. 102 */ 103 public void indexEntry(Entry entry, Set<byte[]> keys) 104 { 105 List<Attribute> attrList = 106 entry.getAttribute(attributeType); 107 if (attrList != null) 108 { 109 indexAttribute(attrList, keys); 110 } 111 } 112 113 /** 114 * Generate the set of index keys to be added and the set of index keys 115 * to be deleted for an entry that has been replaced. 116 * 117 * @param oldEntry The original entry contents. 118 * @param newEntry The new entry contents. 119 * @param modifiedKeys The map into which the modified keys will be inserted. 120 */ 121 public void replaceEntry(Entry oldEntry, Entry newEntry, 122 Map<byte[], Boolean> modifiedKeys) 123 { 124 List<Attribute> newAttributes = newEntry.getAttribute(attributeType, true); 125 List<Attribute> oldAttributes = oldEntry.getAttribute(attributeType, true); 126 127 indexAttribute(oldAttributes, modifiedKeys, false); 128 indexAttribute(newAttributes, modifiedKeys, true); 129 } 130 131 132 133 /** 134 * Generate the set of index keys to be added and the set of index keys 135 * to be deleted for an entry that was modified. 136 * 137 * @param oldEntry The original entry contents. 138 * @param newEntry The new entry contents. 139 * @param mods The set of modifications that were applied to the entry. 140 * @param modifiedKeys The map into which the modified keys will be inserted. 141 */ 142 public void modifyEntry(Entry oldEntry, Entry newEntry, 143 List<Modification> mods, 144 Map<byte[], Boolean> modifiedKeys) 145 { 146 List<Attribute> newAttributes = newEntry.getAttribute(attributeType, true); 147 List<Attribute> oldAttributes = oldEntry.getAttribute(attributeType, true); 148 149 indexAttribute(oldAttributes, modifiedKeys, false); 150 indexAttribute(newAttributes, modifiedKeys, true); 151 } 152 153 154 155 /** 156 * Generate the set of substring index keys for an attribute. 157 * @param attrList The attribute for which substring keys are required. 158 * @param keys The set into which the generated keys will be inserted. 159 */ 160 private void indexAttribute(List<Attribute> attrList, 161 Set<byte[]> keys) 162 { 163 if (attrList == null) return; 164 165 for (Attribute attr : attrList) 166 { 167 indexValues(attr.getValues(), keys); 168 } 169 } 170 171 /** 172 * Generate the set of index keys for a set of attribute values. 173 * @param values The set of attribute values to be indexed. 174 * @param keys The set into which the keys will be inserted. 175 */ 176 private void indexValues(Set<AttributeValue> values, 177 Set<byte[]> keys) 178 { 179 if (values == null) return; 180 181 for (AttributeValue value : values) 182 { 183 try 184 { 185 byte[] normalizedBytes = value.getNormalizedValue().value(); 186 187 substringKeys(normalizedBytes, keys); 188 } 189 catch (DirectoryException e) 190 { 191 if (debugEnabled()) 192 { 193 TRACER.debugCaught(DebugLogLevel.ERROR, e); 194 } 195 } 196 } 197 } 198 199 /** 200 * Decompose an attribute value into a set of substring index keys. 201 * The ID of the entry containing this value should be inserted 202 * into the list of each of these keys. 203 * 204 * @param value A byte array containing the normalized attribute value 205 * @param set A set into which the keys will be inserted. 206 */ 207 private void substringKeys(byte[] value, Set<byte[]> set) 208 { 209 byte[] keyBytes; 210 211 // Example: The value is ABCDE and the substring length is 3. 212 // We produce the keys ABC BCD CDE DE E 213 // To find values containing a short substring such as DE, 214 // iterate through keys with prefix DE. To find values 215 // containing a longer substring such as BCDE, read keys 216 // BCD and CDE. 217 for (int i = 0, remain = value.length; remain > 0; i++, remain--) 218 { 219 int len = Math.min(substrLength, remain); 220 keyBytes = makeSubstringKey(value, i, len); 221 set.add(keyBytes); 222 } 223 } 224 225 /** 226 * Makes a byte array representing a substring index key for 227 * one substring of a value. 228 * 229 * @param bytes The byte array containing the value 230 * @param pos The starting position of the substring 231 * @param len The length of the substring 232 * @return A byte array containing a substring key 233 */ 234 private byte[] makeSubstringKey(byte[] bytes, int pos, int len) 235 { 236 byte[] keyBytes = new byte[len]; 237 System.arraycopy(bytes, pos, keyBytes, 0, len); 238 return keyBytes; 239 } 240 241 /** 242 * Generate the set of index keys for an attribute. 243 * @param attrList The attribute to be indexed. 244 * @param modifiedKeys The map into which the modified 245 * keys will be inserted. 246 * @param insert <code>true</code> if generated keys should 247 * be inserted or <code>false</code> otherwise. 248 */ 249 private void indexAttribute(List<Attribute> attrList, 250 Map<byte[], Boolean> modifiedKeys, 251 Boolean insert) 252 { 253 if (attrList == null) return; 254 255 for (Attribute attr : attrList) 256 { 257 indexValues(attr.getValues(), modifiedKeys, insert); 258 } 259 } 260 261 /** 262 * Generate the set of index keys for a set of attribute values. 263 * @param values The set of attribute values to be indexed. 264 * @param modifiedKeys The map into which the modified 265 * keys will be inserted. 266 * @param insert <code>true</code> if generated keys should 267 * be inserted or <code>false</code> otherwise. 268 */ 269 private void indexValues(Set<AttributeValue> values, 270 Map<byte[], Boolean> modifiedKeys, 271 Boolean insert) 272 { 273 if (values == null) return; 274 275 for (AttributeValue value : values) 276 { 277 try 278 { 279 byte[] normalizedBytes = value.getNormalizedValue().value(); 280 281 substringKeys(normalizedBytes, modifiedKeys, insert); 282 } 283 catch (DirectoryException e) 284 { 285 if (debugEnabled()) 286 { 287 TRACER.debugCaught(DebugLogLevel.ERROR, e); 288 } 289 } 290 } 291 } 292 293 /** 294 * Decompose an attribute value into a set of substring index keys. 295 * The ID of the entry containing this value should be inserted 296 * into the list of each of these keys. 297 * 298 * @param value A byte array containing the normalized attribute value 299 * @param modifiedKeys The map into which the modified 300 * keys will be inserted. 301 * @param insert <code>true</code> if generated keys should 302 * be inserted or <code>false</code> otherwise. 303 */ 304 private void substringKeys(byte[] value, 305 Map<byte[], Boolean> modifiedKeys, 306 Boolean insert) 307 { 308 byte[] keyBytes; 309 310 // Example: The value is ABCDE and the substring length is 3. 311 // We produce the keys ABC BCD CDE DE E 312 // To find values containing a short substring such as DE, 313 // iterate through keys with prefix DE. To find values 314 // containing a longer substring such as BCDE, read keys 315 // BCD and CDE. 316 for (int i = 0, remain = value.length; remain > 0; i++, remain--) 317 { 318 int len = Math.min(substrLength, remain); 319 keyBytes = makeSubstringKey(value, i, len); 320 Boolean cInsert = modifiedKeys.get(keyBytes); 321 if(cInsert == null) 322 { 323 modifiedKeys.put(keyBytes, insert); 324 } 325 else if(!cInsert.equals(insert)) 326 { 327 modifiedKeys.remove(keyBytes); 328 } 329 } 330 } 331 }