src/share/vm/code/dependencies.cpp

*** 678,687 ****
--- 678,695 ----
  
    assert(result == NULL || result->is_klass() || result->is_method(), "must be");
    return result;
  }
  
+ uintptr_t Dependencies::DepStream::get_identity_hash(int i) {
+   if (has_oop_argument()) {
+     return argument_oop(i)->identity_hash();
+   } else {
+     return argument(i)->identity_hash();
+   }
+ }
+ 
  oop Dependencies::DepStream::argument_oop(int i) {
    oop result = recorded_oop_at(argument_index(i));
    assert(result == NULL || result->is_oop(), "must be");
    return result;
  }
*** 713,722 ****
--- 721,844 ----
    // And some dependencies don't have a context type at all,
    // e.g. evol_method.
    return NULL;
  }
  
+ // ----------------- DependencySignatureBuffer --------------------------------------
+ DependencySignatureBuffer::DependencySignatureBuffer(Dependencies::DepType type) {
+   _type = type;
+   _root =  NULL;
+ }
+ 
+ /**
+  * Search binary tree recursively. The key is the identity hash of the first or the second dependency
+  * argument.
+  */
+ DependencySignature* DependencySignatureBuffer::tree_search(DependencySignature* current_node, uintptr_t key) {
+   if (current_node == NULL || key == current_node->key()) {
+     return current_node;
+   }
+   if (key < current_node->key()) {
+     return tree_search(current_node->left(), key);
+   } else {
+     return tree_search(current_node->right(), key);
+   }
+ }
+ 
+ /**
+  * Returns a buffer that contains the dependency signatures of a particular dependency type.
+  */
+ DependencySignatureBuffer* DependencySignatureBuffer::buffer(GrowableArray<DependencySignatureBuffer*>* signature_buffers,
+                                                              Dependencies::DepType type) {
+   for (int i = 0; i < signature_buffers->length(); i++) {
+     DependencySignatureBuffer* current = signature_buffers->at(i);
+     if (current->type() == type) {
+       return current;
+     }
+   }
+ 
+   DependencySignatureBuffer* new_buffer = new DependencySignatureBuffer(type);
+   signature_buffers->append(new_buffer);
+   return new_buffer;
+ }
+ 
+ /**
+  * To remember already checked dependencies, dependencies are represented as dependency
+  * signatures. A dependency signature consists (i) a type and (ii) the identity hashes
+  * of all arguments.
+  * There is a DependencySignatureBuffer object for each dependency type. As a result,
+  * the lookup that is performed by this function does not have to consider the dependency
+  * type.
+  * Dependency signatures are stored in a binary tree where the key is either the identity hash
+  * of the first argument or the identity hash of the second argument of the dependency. Since
+  * dependencies can have more than one argument, each element of the tree (DependencySignature)
+  * maintains a linked list in which dependency signatures that have the same key but different
+  * argument identity hashes are stored.
+  */
+ bool DependencySignatureBuffer::contains(DependencySignature* sig) {
+   // Search binary tree
+   DependencySignature* found = tree_search(_root, sig->key());
+   // Search linked list
+   while (found != NULL) {
+     // Check if arguments are identical. Two dependency signatures are considered
+     // identical, if the type as well as all identity hashes of all arguments are
+     // identical.
+     const int args_count = sig->args_count();
+     int identical_args = 0;
+      for (int i = 0; i < sig->args_count(); i++) {
+        if (sig->arg(i) == found->arg(i)) {
+          identical_args++;
+        }
+      }
+      if (identical_args == args_count) {
+        return true;
+      }
+      found = found->next();
+    }
+    return false;
+ }
+ 
+ /**
+  * Adds element to the binary tree if the binary tree does not contain an element with the specified
+  * key. If the binary tree contains an element of the same key as the element that will be added, the
+  * new dependency signature is appended to the end of a linked list.
+  */
+ void DependencySignatureBuffer::add(DependencySignature* to_add) {
+   DependencySignature* y = NULL;
+   DependencySignature* x = _root;
+   DependencySignature* z = new DependencySignature(to_add);
+ 
+   // Insert into binary search tree
+   while (x != NULL) {
+     y = x;
+     // Found key; add to linked list
+     if (z->key() == x->key()) {
+       // Append to end of linked list
+       while (x->next() != NULL) {
+         x = x->next();
+       }
+       x->set_next(z);
+       return;
+     } else if (z->key() < x->key()) {
+       x = x->left();
+     } else {
+       x = x->right();
+     }
+   }
+   // The dependency signature was not found in the tree. Set links of new element.
+   z->set_parent(y);
+ 
+   if (y == NULL) {
+     _root = z; // tree was empty
+   } else if (z->key() < y->key()) {
+     y->set_left(z);
+   } else {
+     y->set_right(z);
+   }
+ }
+ 
+ 
  /// Checking dependencies:
  
  // This hierarchy walker inspects subtypes of a given type,
  // trying to find a "bad" class which breaks a dependency.
  // Such a class is called a "witness" to the broken dependency.