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 }