/*
|
* CDDL HEADER START
|
*
|
* The contents of this file are subject to the terms of the
|
* Common Development and Distribution License, Version 1.0 only
|
* (the "License"). You may not use this file except in compliance
|
* with the License.
|
*
|
* You can obtain a copy of the license at legal-notices/CDDLv1_0.txt
|
* or http://forgerock.org/license/CDDLv1.0.html.
|
* See the License for the specific language governing permissions
|
* and limitations under the License.
|
*
|
* When distributing Covered Code, include this CDDL HEADER in each
|
* file and include the License file at legal-notices/CDDLv1_0.txt.
|
* If applicable, add the following below this CDDL HEADER, with the
|
* fields enclosed by brackets "[]" replaced with your own identifying
|
* information:
|
* Portions Copyright [yyyy] [name of copyright owner]
|
*
|
* CDDL HEADER END
|
*
|
*
|
* Copyright 2010 Sun Microsystems, Inc.
|
* Portions Copyright 2011-2014 ForgeRock AS
|
*/
|
package org.opends.server.api;
|
|
import java.util.AbstractMap;
|
import java.util.AbstractSet;
|
import java.util.Collection;
|
import java.util.HashMap;
|
import java.util.Iterator;
|
import java.util.Map;
|
import java.util.NoSuchElementException;
|
import java.util.Set;
|
|
import org.opends.server.types.DN;
|
|
/**
|
* The DITCacheMap class implements custom Map for structural storage of
|
* arbitrary objects in Directory Information Tree (DIT) like structure.
|
* <p>
|
* This Map intended usage is for caching various server objects which can be
|
* subject to subtree operations like retrieval or removal of all objects under
|
* a specific DN. While using a regular Map it would require the entire Map
|
* iteration to achieve, this Map implementation maintains such internal
|
* structure that subtree operations are more efficient and do not require
|
* iterations over the entire map, instead additional subtree operations methods
|
* are provided by this Map to do just that.
|
* <p>
|
* API wise it behaves exactly like a regular Map implementation except for
|
* providing additional subtree methods. All required linkage and structuring is
|
* performed within this Map implementation itself and not exposed via the API
|
* in any way. For example, putting these key/value pairs:
|
*
|
* <pre>
|
* cn=Object1,ou=Objects,dc=example,dc=com : object1
|
* cn=Object2,ou=Objects,dc=example,dc=com : object2
|
* cn=Object3,ou=Objects,dc=example,dc=com : object3
|
* </pre>
|
*
|
* then invoking a subtree method on this Map with any of these keys:
|
*
|
* <pre>
|
* ou=Objects,dc=example,dc=com
|
* dc=example,dc=com
|
* dc=com
|
* </pre>
|
*
|
* would bring all three objects previously stored in this map into subtree
|
* operation scope. Standard Map API methods can only work with the objects
|
* previously stored in this map explicitly.
|
* <p>
|
* Note that this Map implementation is not synchronized.
|
*
|
* @param <T>
|
* arbitrary object type.
|
*/
|
public final class DITCacheMap<T> extends AbstractMap<DN,T>
|
{
|
/**
|
* Node class for object storage and
|
* linking to any subordinate nodes.
|
* @param <T> arbitrary storage object.
|
*/
|
private static final class Node<T>
|
{
|
/** Node DN. */
|
DN dn;
|
/**
|
* Storage object or null if this node exist
|
* only to support the DIT like structuring.
|
*/
|
T element;
|
/** Parent. */
|
Node<T> parent;
|
/** First child. */
|
Node<T> child;
|
/** Next sibling. */
|
Node<T> next;
|
/** Previous sibling. */
|
Node<T> previous;
|
|
/** {@inheritDoc} */
|
@Override
|
public String toString()
|
{
|
if (element != null)
|
{
|
return "node(" + element + ")";
|
}
|
else
|
{
|
return "glue";
|
}
|
}
|
}
|
|
/** Map size reflecting only nodes containing non empty elements. */
|
private int size;
|
|
/** Backing Map implementation. */
|
private Map<DN,Node<T>> ditCacheMap;
|
|
/** Default constructor. */
|
public DITCacheMap()
|
{
|
ditCacheMap = new HashMap<DN,Node<T>>();
|
}
|
|
/**
|
* Constructs a new DITCacheMap from a given Map.
|
* @param m existing Map to construct new
|
* DITCacheMap from.
|
*/
|
public DITCacheMap(Map<? extends DN, ? extends T> m)
|
{
|
ditCacheMap = new HashMap<DN,Node<T>>();
|
this.putAll(m);
|
}
|
|
/** {@inheritDoc} */
|
@Override
|
public int size()
|
{
|
return size;
|
}
|
|
/** {@inheritDoc} */
|
@Override
|
public boolean isEmpty()
|
{
|
return ditCacheMap.isEmpty();
|
}
|
|
/** {@inheritDoc} */
|
@Override
|
public boolean containsKey(Object key)
|
{
|
return get(key) != null;
|
}
|
|
/** {@inheritDoc} */
|
@Override
|
public boolean containsValue(Object value)
|
{
|
for (Node<T> node : ditCacheMap.values())
|
{
|
if (node.element != null && node.element.equals(value))
|
{
|
return true;
|
}
|
}
|
return false;
|
}
|
|
/** {@inheritDoc} */
|
@Override
|
public T get(Object key)
|
{
|
Node<T> node = ditCacheMap.get(key);
|
return node != null ? node.element : null;
|
}
|
|
/**
|
* Returns a set of stored objects
|
* subordinate to subtree DN.
|
* @param key subtree DN.
|
* @return collection of stored objects
|
* subordinate to subtree DN.
|
*/
|
public Collection<T> getSubtree(DN key)
|
{
|
return new DITSubtreeSet(key);
|
}
|
|
/** {@inheritDoc} */
|
@Override
|
public T put(DN key, T value)
|
{
|
final Node<T> existingNode = ditCacheMap.get(key);
|
if (existingNode != null)
|
{
|
final T returnValue = existingNode.element;
|
existingNode.element = value;
|
return returnValue;
|
}
|
|
Node<T> node = new Node<T>();
|
node.dn = key;
|
node.element = value;
|
node.parent = null;
|
node.child = null;
|
node.next = null;
|
node.previous = null;
|
|
ditCacheMap.put(key, node);
|
size++;
|
|
// Update parent hierarchy.
|
for (DN parentDN = key.parent();
|
parentDN != null;
|
parentDN = parentDN.parent())
|
{
|
final Node<T> parentNode = ditCacheMap.get(parentDN);
|
|
if (parentNode == null)
|
{
|
// Add glue node.
|
final Node<T> newParentNode = new Node<T>();
|
newParentNode.dn = parentDN;
|
newParentNode.element = null;
|
newParentNode.parent = null;
|
newParentNode.child = node;
|
newParentNode.next = null;
|
newParentNode.previous = null;
|
ditCacheMap.put(parentDN, newParentNode);
|
node.parent = newParentNode;
|
node = newParentNode;
|
}
|
else
|
{
|
if (parentNode.child != null)
|
{
|
Node<T> lastNode = parentNode.child;
|
while (lastNode.next != null)
|
{
|
lastNode = lastNode.next;
|
}
|
node.previous = lastNode;
|
lastNode.next = node;
|
}
|
else
|
{
|
parentNode.child = node;
|
}
|
node.parent = parentNode;
|
break;
|
}
|
}
|
return null;
|
}
|
|
/** {@inheritDoc} */
|
@Override
|
public T remove(Object key)
|
{
|
final DN dn = (DN) key;
|
final Node<T> node = ditCacheMap.get(dn);
|
if (node == null)
|
{
|
return null;
|
}
|
|
final T returnValue = node.element;
|
if (returnValue == null)
|
{
|
return null;
|
}
|
|
// Remove element from DIT.
|
size--;
|
node.element = null;
|
|
if (node.child == null)
|
{
|
// This node is now glue, so remove it completely and fix up
|
// any other nodes which reference it.
|
ditCacheMap.remove(dn);
|
fixNodeReferences(node);
|
}
|
|
return returnValue;
|
}
|
|
|
|
/**
|
* Remove references to a node after it has been removed.
|
* @param node The node which has just been removed.
|
*/
|
private void fixNodeReferences(Node<T> node)
|
{
|
while (true)
|
{
|
// Fix siblings.
|
final Node<T> nextNode = node.next;
|
final Node<T> previousNode = node.previous;
|
|
if (nextNode != null)
|
{
|
nextNode.previous = previousNode;
|
}
|
|
if (previousNode != null)
|
{
|
previousNode.next = nextNode;
|
}
|
|
// Fix parent, if it exists.
|
final Node<T> parentNode = node.parent;
|
if (parentNode == null)
|
{
|
// Reached the top of the DIT, so no parents to fix.
|
break;
|
}
|
|
if (parentNode.child != node)
|
{
|
// The parent references another sibling and does not need fixing.
|
break;
|
}
|
|
if (nextNode != null)
|
{
|
// Update child pointer and return.
|
parentNode.child = nextNode;
|
break;
|
}
|
|
if (parentNode.element != null)
|
{
|
// Parent node is still needed as it contains data.
|
break;
|
}
|
|
// The parent node is glue so remove it.
|
ditCacheMap.remove(parentNode.dn);
|
|
// Smash pointers.
|
node.parent = null;
|
node.previous = null;
|
node.next = null;
|
|
// Continue up tree.
|
node = parentNode;
|
}
|
}
|
|
|
|
/**
|
* Removes a set of stored objects subordinate to subtree DN.
|
* @param key subtree DN.
|
* @param values collection for removed objects subordinate
|
* to subtree DN or <code>null</code>.
|
* @return <code>true</code> on success or <code>false</code> otherwise.
|
*/
|
public boolean removeSubtree(DN key, Collection<? super T> values)
|
{
|
final Node<T> node = ditCacheMap.remove(key);
|
if (node != null)
|
{
|
// Fix up sibling and parent references.
|
fixNodeReferences(node);
|
|
// Collect all elements and update the size.
|
adjustSizeAndCollectElements(node, values);
|
return true;
|
}
|
return false;
|
}
|
|
|
|
/**
|
* Iterate through detached subtree counting and collecting any elements.
|
*
|
* @param node
|
* The node to be collected.
|
* @param values
|
* Collection in which to put elements.
|
*/
|
private void adjustSizeAndCollectElements(final Node<T> node,
|
Collection<? super T> values)
|
{
|
if (node.element != null)
|
{
|
if (values != null)
|
{
|
values.add(node.element);
|
}
|
node.element = null;
|
size--;
|
}
|
|
// Repeat for each child.
|
Node<T> child = node.child;
|
while (child != null)
|
{
|
final Node<T> next = child.next;
|
adjustSizeAndCollectElements(child, values);
|
child = next;
|
}
|
|
// Smash pointers.
|
node.parent = null;
|
node.child = null;
|
node.previous = null;
|
node.next = null;
|
|
// Remove node from map.
|
ditCacheMap.remove(node.dn);
|
}
|
|
|
|
/** {@inheritDoc} */
|
@Override
|
public void putAll(Map<? extends DN, ? extends T> m)
|
{
|
for (Entry<? extends DN, ? extends T> entry : m.entrySet())
|
{
|
put(entry.getKey(), entry.getValue());
|
}
|
}
|
|
/** {@inheritDoc} */
|
@Override
|
public void clear()
|
{
|
ditCacheMap.clear();
|
size = 0;
|
}
|
|
/** {@inheritDoc} */
|
@Override
|
public Set<Entry<DN, T>> entrySet()
|
{
|
return new DITCacheEntrySet();
|
}
|
|
/** EntrySet class implementation for the DITCacheMap. */
|
private class DITCacheEntrySet extends AbstractSet<Entry<DN, T>>
|
{
|
/** Iterator class implementation for the DITCacheEntrySet. */
|
private class EntryIterator implements Iterator<Entry<DN, T>>
|
{
|
private Iterator<Entry<DN, Node<T>>> ditCacheMapIterator;
|
private Entry<DN, Node<T>> currentEntry;
|
private Entry<DN, Node<T>> nextEntry;
|
private boolean hasNext;
|
|
/** Default constructor. */
|
public EntryIterator()
|
{
|
ditCacheMapIterator = ditCacheMap.entrySet().iterator();
|
currentEntry = null;
|
nextEntry = null;
|
hasNext = false;
|
}
|
|
/** {@inheritDoc} */
|
@Override
|
public boolean hasNext()
|
{
|
if (hasNext)
|
{
|
return true;
|
}
|
while (ditCacheMapIterator.hasNext())
|
{
|
Entry<DN, Node<T>> entry = ditCacheMapIterator.next();
|
Node<T> node = entry.getValue();
|
if (node != null && node.element != null)
|
{
|
nextEntry = entry;
|
hasNext = true;
|
return true;
|
}
|
}
|
nextEntry = null;
|
return false;
|
}
|
|
/** {@inheritDoc} */
|
@Override
|
public Entry<DN, T> next()
|
{
|
if (nextEntry != null)
|
{
|
Node<T> node = nextEntry.getValue();
|
currentEntry = nextEntry;
|
nextEntry = null;
|
hasNext = false;
|
return new DITCacheMapEntry(node.dn, node.element);
|
}
|
while (ditCacheMapIterator.hasNext())
|
{
|
Entry<DN, Node<T>> entry = ditCacheMapIterator.next();
|
Node<T> node = entry.getValue();
|
if (node != null && node.element != null)
|
{
|
currentEntry = entry;
|
hasNext = false;
|
return new DITCacheMapEntry(node.dn, node.element);
|
}
|
}
|
throw new NoSuchElementException();
|
}
|
|
/** {@inheritDoc} */
|
@Override
|
public void remove()
|
{
|
if (currentEntry != null)
|
{
|
Entry<DN, Node<T>> oldIteratorEntry = null;
|
if (hasNext())
|
{
|
oldIteratorEntry = nextEntry;
|
}
|
if (DITCacheMap.this.remove(currentEntry.getKey()) != null)
|
{
|
ditCacheMapIterator = ditCacheMap.entrySet().iterator();
|
currentEntry = null;
|
nextEntry = null;
|
hasNext = false;
|
while (hasNext())
|
{
|
Entry<DN, T> newIteratorEntry = next();
|
if (oldIteratorEntry != null
|
&& oldIteratorEntry.getKey().equals(newIteratorEntry.getKey())
|
&& oldIteratorEntry.getValue().element.equals(newIteratorEntry.getValue()))
|
{
|
nextEntry = currentEntry;
|
hasNext = true;
|
return;
|
}
|
}
|
currentEntry = null;
|
nextEntry = null;
|
hasNext = false;
|
return;
|
}
|
}
|
throw new IllegalStateException();
|
}
|
}
|
|
/** {@inheritDoc} */
|
@Override
|
public int size()
|
{
|
return DITCacheMap.this.size();
|
}
|
|
/** {@inheritDoc} */
|
@Override
|
public Iterator<Entry<DN, T>> iterator()
|
{
|
return new EntryIterator();
|
}
|
}
|
|
/** Map.Entry class implementation for the DITCacheMap. */
|
private class DITCacheMapEntry implements Map.Entry<DN, T>
|
{
|
private DN key;
|
private T value;
|
|
/**
|
* Constructs a new DITCacheMapEntry
|
* with given key and value.
|
* @param key Map.Entry key.
|
* @param value Map.Entry value.
|
*/
|
public DITCacheMapEntry(DN key, T value)
|
{
|
this.key = key;
|
this.value = value;
|
}
|
|
/** {@inheritDoc} */
|
@Override
|
public DN getKey()
|
{
|
return key;
|
}
|
|
/** {@inheritDoc} */
|
@Override
|
public T getValue()
|
{
|
return value;
|
}
|
|
/** {@inheritDoc} */
|
@Override
|
public T setValue(T value)
|
{
|
Node<T> node = ditCacheMap.get(key);
|
T oldValue = this.value;
|
node.element = value;
|
this.value = value;
|
return oldValue;
|
}
|
}
|
|
/** SubtreeSet class implementation. */
|
private class DITSubtreeSet extends AbstractSet<T>
|
{
|
/** Set key. */
|
private DN key;
|
|
/**
|
* Keyed constructor.
|
* @param key to construct
|
* this set from.
|
*/
|
public DITSubtreeSet(DN key)
|
{
|
this.key = key;
|
}
|
|
/** Iterator class implementation for SubtreeSet. */
|
private class SubtreeSetIterator implements Iterator<T>
|
{
|
/** Iterator key. */
|
private DN key;
|
|
/** Iterator root node. */
|
private Node<T> rootNode;
|
|
/** Iterator current node. */
|
private Node<T> node;
|
|
/** Default constructor. */
|
public SubtreeSetIterator()
|
{
|
this.key = DITSubtreeSet.this.key;
|
rootNode = ditCacheMap.get(this.key);
|
node = rootNode;
|
}
|
|
/**
|
* Keyed constructor.
|
* @param key to cue this
|
* iterator from.
|
*/
|
public SubtreeSetIterator(DN key)
|
{
|
this.key = key;
|
rootNode = ditCacheMap.get(this.key);
|
node = rootNode;
|
}
|
|
/** {@inheritDoc} */
|
@Override
|
public boolean hasNext()
|
{
|
if (rootNode != null)
|
{
|
if (node == rootNode && rootNode.element != null)
|
{
|
return true;
|
}
|
while (node != null)
|
{
|
if (node.element != null)
|
{
|
return true;
|
}
|
if (node.child != null)
|
{
|
node = node.child;
|
}
|
else
|
{
|
while (node.next == null && node.parent != rootNode)
|
{
|
node = node.parent;
|
}
|
node = node.next;
|
}
|
}
|
}
|
return false;
|
}
|
|
/** {@inheritDoc} */
|
@Override
|
public T next()
|
{
|
T element = null;
|
|
if (rootNode != null)
|
{
|
if (node == rootNode)
|
{
|
node = rootNode.child;
|
if (rootNode.element != null)
|
{
|
return rootNode.element;
|
}
|
}
|
while (node != null)
|
{
|
element = node.element;
|
if (node.child != null)
|
{
|
node = node.child;
|
}
|
else
|
{
|
while (node.next == null && node.parent != rootNode)
|
{
|
node = node.parent;
|
}
|
node = node.next;
|
}
|
if (element != null)
|
{
|
return element;
|
}
|
}
|
}
|
throw new NoSuchElementException();
|
}
|
|
/** {@inheritDoc} */
|
@Override
|
public void remove()
|
{
|
throw new UnsupportedOperationException();
|
}
|
}
|
|
/** {@inheritDoc} */
|
@Override
|
public Iterator<T> iterator()
|
{
|
return new SubtreeSetIterator();
|
}
|
|
/** {@inheritDoc} */
|
@Override
|
public int size()
|
{
|
int size = 0;
|
|
Iterator<T> iterator = new SubtreeSetIterator(this.key);
|
while (iterator.hasNext())
|
{
|
iterator.next();
|
size++;
|
}
|
|
return size;
|
}
|
}
|
|
/**
|
* Returns the size of the internal map. Used for testing purposes only.
|
*
|
* @return The size of the internal map.
|
*/
|
int getMapSize()
|
{
|
return ditCacheMap.size();
|
}
|
}
|
