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}