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    }