001/*
002 * The contents of this file are subject to the terms of the Common Development and
003 * Distribution License (the License). You may not use this file except in compliance with the
004 * License.
005 *
006 * You can obtain a copy of the License at legal/CDDLv1.0.txt. See the License for the
007 * specific language governing permission and limitations under the License.
008 *
009 * When distributing Covered Software, include this CDDL Header Notice in each file and include
010 * the License file at legal/CDDLv1.0.txt. If applicable, add the following below the CDDL
011 * Header, with the fields enclosed by brackets [] replaced by your own identifying
012 * information: "Portions Copyright [year] [name of copyright owner]".
013 *
014 * Copyright 2010 Sun Microsystems, Inc.
015 * Portions Copyright 2011-2016 ForgeRock AS.
016 */
017package org.opends.server.api;
018
019import java.util.AbstractMap;
020import java.util.AbstractSet;
021import java.util.Collection;
022import java.util.HashMap;
023import java.util.Iterator;
024import java.util.Map;
025import java.util.NoSuchElementException;
026import java.util.Set;
027
028import org.forgerock.opendj.ldap.DN;
029
030/**
031 * The DITCacheMap class implements custom Map for structural storage of
032 * arbitrary objects in Directory Information Tree (DIT) like structure.
033 * <p>
034 * This Map intended usage is for caching various server objects which can be
035 * subject to subtree operations like retrieval or removal of all objects under
036 * a specific DN. While using a regular Map it would require the entire Map
037 * iteration to achieve, this Map implementation maintains such internal
038 * structure that subtree operations are more efficient and do not require
039 * iterations over the entire map, instead additional subtree operations methods
040 * are provided by this Map to do just that.
041 * <p>
042 * API wise it behaves exactly like a regular Map implementation except for
043 * providing additional subtree methods. All required linkage and structuring is
044 * performed within this Map implementation itself and not exposed via the API
045 * in any way. For example, putting these key/value pairs:
046 *
047 * <pre>
048 * cn=Object1,ou=Objects,dc=example,dc=com : object1
049 * cn=Object2,ou=Objects,dc=example,dc=com : object2
050 * cn=Object3,ou=Objects,dc=example,dc=com : object3
051 * </pre>
052 *
053 * then invoking a subtree method on this Map with any of these keys:
054 *
055 * <pre>
056 * ou=Objects,dc=example,dc=com
057 * dc=example,dc=com
058 * dc=com
059 * </pre>
060 *
061 * would bring all three objects previously stored in this map into subtree
062 * operation scope. Standard Map API methods can only work with the objects
063 * previously stored in this map explicitly.
064 * <p>
065 * Note that this Map implementation is not synchronized.
066 *
067 * @param <T>
068 *          arbitrary object type.
069 */
070public final class DITCacheMap<T> extends AbstractMap<DN,T>
071{
072  /**
073   * Node class for object storage and
074   * linking to any subordinate nodes.
075   * @param <T> arbitrary storage object.
076   */
077  private static final class Node<T>
078  {
079    /** Node DN. */
080    DN dn;
081    /** Storage object or null if this node exist only to support the DIT like structuring. */
082    T element;
083    /** Parent. */
084    Node<T> parent;
085    /** First child. */
086    Node<T> child;
087    /** Next sibling. */
088    Node<T> next;
089    /** Previous sibling. */
090    Node<T> previous;
091
092    @Override
093    public String toString()
094    {
095      return element != null ? "node(" + element + ")" : "glue";
096    }
097  }
098
099  /** Map size reflecting only nodes containing non empty elements. */
100  private int size;
101
102  /** Backing Map implementation. */
103  private final Map<DN,Node<T>> ditCacheMap = new HashMap<>();
104
105  /** Default constructor. */
106  public DITCacheMap()
107  {
108  }
109
110  @Override
111  public int size()
112  {
113    return size;
114  }
115
116  @Override
117  public boolean isEmpty()
118  {
119    return ditCacheMap.isEmpty();
120  }
121
122  @Override
123  public boolean containsKey(Object key)
124  {
125    return get(key) != null;
126  }
127
128  @Override
129  public boolean containsValue(Object value)
130  {
131    for (Node<T> node : ditCacheMap.values())
132    {
133      if (node.element != null && node.element.equals(value))
134      {
135        return true;
136      }
137    }
138    return false;
139  }
140
141  @Override
142  public T get(Object key)
143  {
144    Node<T> node = ditCacheMap.get(key);
145    return node != null ? node.element : null;
146  }
147
148  /**
149   * Returns a set of stored objects subordinate to subtree DN.
150   * @param key subtree DN.
151   * @return collection of stored objects subordinate to subtree DN.
152   */
153  public Collection<T> getSubtree(DN key)
154  {
155    return new DITSubtreeSet(key);
156  }
157
158  @Override
159  public T put(DN key, T value)
160  {
161    final Node<T> existingNode = ditCacheMap.get(key);
162    if (existingNode != null)
163    {
164      final T returnValue = existingNode.element;
165      existingNode.element = value;
166      return returnValue;
167    }
168
169    Node<T> node = new Node<>();
170    node.dn = key;
171    node.element = value;
172    node.parent = null;
173    node.child = null;
174    node.next = null;
175    node.previous = null;
176
177    ditCacheMap.put(key, node);
178    size++;
179
180    // Update parent hierarchy.
181    for (DN parentDN = key.parent();
182         parentDN != null;
183         parentDN = parentDN.parent())
184    {
185      final Node<T> parentNode = ditCacheMap.get(parentDN);
186
187      if (parentNode == null)
188      {
189        // Add glue node.
190        final Node<T> newParentNode = new Node<>();
191        newParentNode.dn = parentDN;
192        newParentNode.element = null;
193        newParentNode.parent = null;
194        newParentNode.child = node;
195        newParentNode.next = null;
196        newParentNode.previous = null;
197        ditCacheMap.put(parentDN, newParentNode);
198        node.parent = newParentNode;
199        node = newParentNode;
200      }
201      else
202      {
203        if (parentNode.child != null)
204        {
205          Node<T> lastNode = parentNode.child;
206          while (lastNode.next != null)
207          {
208            lastNode = lastNode.next;
209          }
210          node.previous = lastNode;
211          lastNode.next = node;
212        }
213        else
214        {
215          parentNode.child = node;
216        }
217        node.parent = parentNode;
218        break;
219      }
220    }
221    return null;
222  }
223
224  @Override
225  public T remove(Object key)
226  {
227    final DN dn = (DN) key;
228    final Node<T> node = ditCacheMap.get(dn);
229    if (node == null)
230    {
231      return null;
232    }
233
234    final T returnValue = node.element;
235    if (returnValue == null)
236    {
237      return null;
238    }
239
240    // Remove element from DIT.
241    size--;
242    node.element = null;
243
244    if (node.child == null)
245    {
246      // This node is now glue, so remove it completely and fix up
247      // any other nodes which reference it.
248      ditCacheMap.remove(dn);
249      fixNodeReferences(node);
250    }
251
252    return returnValue;
253  }
254
255  /**
256   * Remove references to a node after it has been removed.
257   * @param node The node which has just been removed.
258   */
259  private void fixNodeReferences(Node<T> node)
260  {
261    while (true)
262    {
263      // Fix siblings.
264      final Node<T> nextNode = node.next;
265      final Node<T> previousNode = node.previous;
266
267      if (nextNode != null)
268      {
269        nextNode.previous = previousNode;
270      }
271
272      if (previousNode != null)
273      {
274        previousNode.next = nextNode;
275      }
276
277      // Fix parent, if it exists.
278      final Node<T> parentNode = node.parent;
279      if (parentNode == null)
280      {
281        // Reached the top of the DIT, so no parents to fix.
282        break;
283      }
284
285      if (parentNode.child != node)
286      {
287        // The parent references another sibling and does not need fixing.
288        break;
289      }
290
291      if (nextNode != null)
292      {
293        // Update child pointer and return.
294        parentNode.child = nextNode;
295        break;
296      }
297
298      if (parentNode.element != null)
299      {
300        // Parent node is still needed as it contains data.
301        break;
302      }
303
304      // The parent node is glue so remove it.
305      ditCacheMap.remove(parentNode.dn);
306
307      // Smash pointers.
308      node.parent = null;
309      node.previous = null;
310      node.next = null;
311
312      // Continue up tree.
313      node = parentNode;
314    }
315  }
316
317  /**
318   * Returns {@code true} if there are stored objects subordinate to subtree DN.
319   * @param key subtree DN.
320   * @return {@code true} if there are stored objects subordinate to subtree DN.
321   */
322  public boolean containsSubtree(DN key)
323  {
324    return ditCacheMap.containsKey(key);
325  }
326
327  /**
328   * Removes a set of stored objects subordinate to subtree DN.
329   * @param key subtree DN.
330   * @param values collection for removed objects subordinate
331   *               to subtree DN or <code>null</code>.
332   * @return <code>true</code> on success or <code>false</code> otherwise.
333   */
334  public boolean removeSubtree(DN key, Collection<? super T> values)
335  {
336    final Node<T> node = ditCacheMap.remove(key);
337    if (node != null)
338    {
339      // Fix up sibling and parent references.
340      fixNodeReferences(node);
341
342      // Collect all elements and update the size.
343      adjustSizeAndCollectElements(node, values);
344      return true;
345    }
346    return false;
347  }
348
349  /**
350   * Iterate through detached subtree counting and collecting any elements.
351   *
352   * @param node
353   *          The node to be collected.
354   * @param values
355   *          Collection in which to put elements.
356   */
357  private void adjustSizeAndCollectElements(final Node<T> node,
358      Collection<? super T> values)
359  {
360    if (node.element != null)
361    {
362      if (values != null)
363      {
364        values.add(node.element);
365      }
366      node.element = null;
367      size--;
368    }
369
370    // Repeat for each child.
371    Node<T> child = node.child;
372    while (child != null)
373    {
374      final Node<T> next = child.next;
375      adjustSizeAndCollectElements(child, values);
376      child = next;
377    }
378
379    // Smash pointers.
380    node.parent = null;
381    node.child = null;
382    node.previous = null;
383    node.next = null;
384
385    // Remove node from map.
386    ditCacheMap.remove(node.dn);
387  }
388
389  @Override
390  public void putAll(Map<? extends DN, ? extends T> m)
391  {
392    for (Entry<? extends DN, ? extends T> entry : m.entrySet())
393    {
394      put(entry.getKey(), entry.getValue());
395    }
396  }
397
398  @Override
399  public void clear()
400  {
401    ditCacheMap.clear();
402    size = 0;
403  }
404
405  @Override
406  public Set<Entry<DN, T>> entrySet()
407  {
408    return new DITCacheEntrySet();
409  }
410
411  /** EntrySet class implementation for the DITCacheMap. */
412  private class DITCacheEntrySet extends AbstractSet<Entry<DN, T>>
413  {
414    /** Iterator class implementation for the DITCacheEntrySet. */
415    private class EntryIterator implements Iterator<Entry<DN, T>>
416    {
417      private Iterator<Entry<DN, Node<T>>> ditCacheMapIterator;
418      private Entry<DN, Node<T>> currentEntry;
419      private Entry<DN, Node<T>> nextEntry;
420      private boolean hasNext;
421
422      /** Default constructor. */
423      public EntryIterator()
424      {
425        ditCacheMapIterator = ditCacheMap.entrySet().iterator();
426        currentEntry = null;
427        nextEntry = null;
428        hasNext = false;
429      }
430
431      @Override
432      public boolean hasNext()
433      {
434        if (hasNext)
435        {
436          return true;
437        }
438        while (ditCacheMapIterator.hasNext())
439        {
440          Entry<DN, Node<T>> entry = ditCacheMapIterator.next();
441          Node<T> node = entry.getValue();
442          if (node != null && node.element != null)
443          {
444            nextEntry = entry;
445            hasNext = true;
446            return true;
447          }
448        }
449        nextEntry = null;
450        return false;
451      }
452
453      @Override
454      public Entry<DN, T> next()
455      {
456        if (nextEntry != null)
457        {
458          Node<T> node = nextEntry.getValue();
459          currentEntry = nextEntry;
460          nextEntry = null;
461          hasNext = false;
462          return new DITCacheMapEntry(node.dn, node.element);
463        }
464        while (ditCacheMapIterator.hasNext())
465        {
466          Entry<DN, Node<T>> entry = ditCacheMapIterator.next();
467          Node<T> node = entry.getValue();
468          if (node != null && node.element != null)
469          {
470            currentEntry = entry;
471            hasNext = false;
472            return new DITCacheMapEntry(node.dn, node.element);
473          }
474        }
475        throw new NoSuchElementException();
476      }
477
478      @Override
479      public void remove()
480      {
481        if (currentEntry != null)
482        {
483          Entry<DN, Node<T>> oldIteratorEntry = null;
484          if (hasNext())
485          {
486            oldIteratorEntry = nextEntry;
487          }
488          if (DITCacheMap.this.remove(currentEntry.getKey()) != null)
489          {
490            ditCacheMapIterator = ditCacheMap.entrySet().iterator();
491            currentEntry = null;
492            nextEntry = null;
493            hasNext = false;
494            while (hasNext())
495            {
496              Entry<DN, T> newIteratorEntry = next();
497              if (oldIteratorEntry != null
498                  && oldIteratorEntry.getKey().equals(newIteratorEntry.getKey())
499                  && oldIteratorEntry.getValue().element.equals(newIteratorEntry.getValue()))
500              {
501                nextEntry = currentEntry;
502                hasNext = true;
503                return;
504              }
505            }
506            currentEntry = null;
507            nextEntry = null;
508            hasNext = false;
509            return;
510          }
511        }
512        throw new IllegalStateException();
513      }
514    }
515
516    @Override
517    public int size()
518    {
519      return DITCacheMap.this.size();
520    }
521
522    @Override
523    public Iterator<Entry<DN, T>> iterator()
524    {
525      return new EntryIterator();
526    }
527  }
528
529  /** Map.Entry class implementation for the DITCacheMap. */
530  private class DITCacheMapEntry implements Map.Entry<DN, T>
531  {
532    private DN key;
533    private T  value;
534
535    /**
536     * Constructs a new DITCacheMapEntry
537     * with given key and value.
538     * @param key Map.Entry key.
539     * @param value Map.Entry value.
540     */
541    public DITCacheMapEntry(DN key, T value)
542    {
543      this.key = key;
544      this.value = value;
545    }
546
547    @Override
548    public DN getKey()
549    {
550      return key;
551    }
552
553    @Override
554    public T getValue()
555    {
556      return value;
557    }
558
559    @Override
560    public T setValue(T value)
561    {
562      Node<T> node = ditCacheMap.get(key);
563      T oldValue = this.value;
564      node.element = value;
565      this.value = value;
566      return oldValue;
567    }
568  }
569
570  /** SubtreeSet class implementation. */
571  private class DITSubtreeSet extends AbstractSet<T>
572  {
573    /** Set key. */
574    private DN key;
575
576    /**
577     * Keyed constructor.
578     * @param key to construct
579     *        this set from.
580     */
581    public DITSubtreeSet(DN key)
582    {
583      this.key = key;
584    }
585
586    /** Iterator class implementation for SubtreeSet. */
587    private class SubtreeSetIterator implements Iterator<T>
588    {
589      /** Iterator key. */
590      private DN key;
591
592      /** Iterator root node. */
593      private Node<T> rootNode;
594
595      /** Iterator current node. */
596      private Node<T> node;
597
598      /** Default constructor. */
599      public SubtreeSetIterator()
600      {
601        this.key = DITSubtreeSet.this.key;
602        rootNode = ditCacheMap.get(this.key);
603        node = rootNode;
604      }
605
606      /**
607       * Keyed constructor.
608       * @param key to cue this
609       *        iterator from.
610       */
611      public SubtreeSetIterator(DN key)
612      {
613        this.key = key;
614        rootNode = ditCacheMap.get(this.key);
615        node = rootNode;
616      }
617
618      @Override
619      public boolean hasNext()
620      {
621        if (rootNode != null)
622        {
623          if (node == rootNode && rootNode.element != null)
624          {
625            return true;
626          }
627          while (node != null)
628          {
629            if (node.element != null)
630            {
631              return true;
632            }
633            if (node.child != null)
634            {
635              node = node.child;
636            }
637            else
638            {
639              while (node.next == null && node.parent != rootNode)
640              {
641                node = node.parent;
642              }
643              node = node.next;
644            }
645          }
646        }
647        return false;
648      }
649
650      @Override
651      public T next()
652      {
653        T element = null;
654
655        if (rootNode != null)
656        {
657          if (node == rootNode)
658          {
659            node = rootNode.child;
660            if (rootNode.element != null)
661            {
662              return rootNode.element;
663            }
664          }
665          while (node != null)
666          {
667            element = node.element;
668            if (node.child != null)
669            {
670              node = node.child;
671            }
672            else
673            {
674              while (node.next == null && node.parent != rootNode)
675              {
676                node = node.parent;
677              }
678              node = node.next;
679            }
680            if (element != null)
681            {
682              return element;
683            }
684          }
685        }
686        throw new NoSuchElementException();
687      }
688
689      @Override
690      public void remove()
691      {
692        throw new UnsupportedOperationException();
693      }
694    }
695
696    @Override
697    public Iterator<T> iterator()
698    {
699      return new SubtreeSetIterator();
700    }
701
702    @Override
703    public boolean isEmpty()
704    {
705      return !new SubtreeSetIterator(this.key).hasNext();
706    }
707
708    @Override
709    public int size()
710    {
711      int size = 0;
712
713      Iterator<T> iterator = new SubtreeSetIterator(this.key);
714      while (iterator.hasNext())
715      {
716        iterator.next();
717        size++;
718      }
719
720      return size;
721    }
722  }
723}